summaryrefslogtreecommitdiff
path: root/boost/multi_index/detail/ord_index_ops.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/multi_index/detail/ord_index_ops.hpp')
-rw-r--r--boost/multi_index/detail/ord_index_ops.hpp125
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 d42f5f1..84d5cac 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_()));
}
}