diff options
Diffstat (limited to 'boost/multi_index/detail/ord_index_ops.hpp')
-rw-r--r-- | boost/multi_index/detail/ord_index_ops.hpp | 125 |
1 files changed, 122 insertions, 3 deletions
diff --git a/boost/multi_index/detail/ord_index_ops.hpp b/boost/multi_index/detail/ord_index_ops.hpp index d42f5f1a29..84d5cacae1 100644 --- a/boost/multi_index/detail/ord_index_ops.hpp +++ b/boost/multi_index/detail/ord_index_ops.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2013 Joaquin M Lopez Munoz. +/* Copyright 2003-2014 Joaquin M Lopez Munoz. * Distributed under the Boost Software License, Version 1.0. * (See accompanying file LICENSE_1_0.txt or copy at * http://www.boost.org/LICENSE_1_0.txt) @@ -41,6 +41,8 @@ #endif #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ +#include <boost/mpl/and.hpp> +#include <boost/multi_index/detail/promotes_arg.hpp> #include <utility> namespace boost{ @@ -51,6 +53,9 @@ namespace detail{ /* Common code for index memfuns having templatized and * non-templatized versions. + * Implementation note: When CompatibleKey is consistently promoted to + * KeyFromValue::result_type for comparison, the promotion is made once in + * advance to increase efficiency. */ template< @@ -61,6 +66,35 @@ inline Node* ordered_index_find( Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, const CompatibleCompare& comp) { + typedef typename KeyFromValue::result_type key_type; + + return ordered_index_find( + top,y,key,x,comp, + mpl::and_< + promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>, + promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleCompare +> +inline Node* ordered_index_find( + Node* top,Node* y,const KeyFromValue& key, + const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x, + const CompatibleCompare& comp,mpl::true_) +{ + return ordered_index_find(top,y,key,x,comp,mpl::false_()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleKey,typename CompatibleCompare +> +inline Node* ordered_index_find( + Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, + const CompatibleCompare& comp,mpl::false_) +{ Node* y0=y; while (top){ @@ -82,6 +116,33 @@ inline Node* ordered_index_lower_bound( Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, const CompatibleCompare& comp) { + typedef typename KeyFromValue::result_type key_type; + + return ordered_index_lower_bound( + top,y,key,x,comp, + promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey>()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleCompare +> +inline Node* ordered_index_lower_bound( + Node* top,Node* y,const KeyFromValue& key, + const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x, + const CompatibleCompare& comp,mpl::true_) +{ + return ordered_index_lower_bound(top,y,key,x,comp,mpl::false_()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleKey,typename CompatibleCompare +> +inline Node* ordered_index_lower_bound( + Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, + const CompatibleCompare& comp,mpl::false_) +{ while(top){ if(!comp(key(top->value()),x)){ y=top; @@ -101,6 +162,33 @@ inline Node* ordered_index_upper_bound( Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, const CompatibleCompare& comp) { + typedef typename KeyFromValue::result_type key_type; + + return ordered_index_upper_bound( + top,y,key,x,comp, + promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleCompare +> +inline Node* ordered_index_upper_bound( + Node* top,Node* y,const KeyFromValue& key, + const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x, + const CompatibleCompare& comp,mpl::true_) +{ + return ordered_index_upper_bound(top,y,key,x,comp,mpl::false_()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleKey,typename CompatibleCompare +> +inline Node* ordered_index_upper_bound( + Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, + const CompatibleCompare& comp,mpl::false_) +{ while(top){ if(comp(x,key(top->value()))){ y=top; @@ -120,6 +208,35 @@ inline std::pair<Node*,Node*> ordered_index_equal_range( Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, const CompatibleCompare& comp) { + typedef typename KeyFromValue::result_type key_type; + + return ordered_index_equal_range( + top,y,key,x,comp, + mpl::and_< + promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>, + promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleCompare +> +inline std::pair<Node*,Node*> ordered_index_equal_range( + Node* top,Node* y,const KeyFromValue& key, + const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x, + const CompatibleCompare& comp,mpl::true_) +{ + return ordered_index_equal_range(top,y,key,x,comp,mpl::false_()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleKey,typename CompatibleCompare +> +inline std::pair<Node*,Node*> ordered_index_equal_range( + Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, + const CompatibleCompare& comp,mpl::false_) +{ while(top){ if(comp(key(top->value()),x)){ top=Node::from_impl(top->right()); @@ -130,8 +247,10 @@ inline std::pair<Node*,Node*> ordered_index_equal_range( } else{ return std::pair<Node*,Node*>( - ordered_index_lower_bound(Node::from_impl(top->left()),top,key,x,comp), - ordered_index_upper_bound(Node::from_impl(top->right()),y,key,x,comp)); + ordered_index_lower_bound( + Node::from_impl(top->left()),top,key,x,comp,mpl::false_()), + ordered_index_upper_bound( + Node::from_impl(top->right()),y,key,x,comp,mpl::false_())); } } |