multi_index/detail/ord_index_ops.hpp

0001 /* Copyright 2003-2014 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/multi_index for library home page.
0007  *
0008  * The internal implementation of red-black trees is based on that of SGI STL
0009  * stl_tree.h file:
0010  *
0011  * Copyright (c) 1996,1997
0012  * Silicon Graphics Computer Systems, Inc.
0013  *
0014  * Permission to use, copy, modify, distribute and sell this software
0015  * and its documentation for any purpose is hereby granted without fee,
0016  * provided that the above copyright notice appear in all copies and
0017  * that both that copyright notice and this permission notice appear
0018  * in supporting documentation.  Silicon Graphics makes no
0019  * representations about the suitability of this software for any
0020  * purpose.  It is provided "as is" without express or implied warranty.
0021  *
0022  *
0023  * Copyright (c) 1994
0024  * Hewlett-Packard Company
0025  *
0026  * Permission to use, copy, modify, distribute and sell this software
0027  * and its documentation for any purpose is hereby granted without fee,
0028  * provided that the above copyright notice appear in all copies and
0029  * that both that copyright notice and this permission notice appear
0030  * in supporting documentation.  Hewlett-Packard Company makes no
0031  * representations about the suitability of this software for any
0032  * purpose.  It is provided "as is" without express or implied warranty.
0033  *
0034  */
0035
0036 #ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_HPP
0037 #define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_HPP
0038
0039 #if defined(_MSC_VER)
0040 #pragma once
0041 #endif
0042
0043 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
0044 #include <boost/mpl/and.hpp>
0045 #include <boost/multi_index/detail/promotes_arg.hpp>
0046 #include <utility>
0047
0048 namespace boost{
0049
0050 namespace multi_index{
0051
0052 namespace detail{
0053
0054 /* Common code for index memfuns having templatized and
0055  * non-templatized versions.
0056  * Implementation note: When CompatibleKey is consistently promoted to
0057  * KeyFromValue::result_type for comparison, the promotion is made once in
0058  * advance to increase efficiency.
0059  */
0060
0061 template<
0062   typename Node,typename KeyFromValue,
0063   typename CompatibleKey,typename CompatibleCompare
0064 >
0065 inline Node* ordered_index_find(
0066   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0067   const CompatibleCompare& comp)
0068 {
0069   typedef typename KeyFromValue::result_type key_type;
0070
0071   return ordered_index_find(
0072     top,y,key,x,comp,
0073     mpl::and_<
0074       promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
0075       promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
0076 }
0077
0078 template<
0079   typename Node,typename KeyFromValue,
0080   typename CompatibleCompare
0081 >
0082 inline Node* ordered_index_find(
0083   Node* top,Node* y,const KeyFromValue& key,
0084   const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
0085   const CompatibleCompare& comp,mpl::true_)
0086 {
0087   return ordered_index_find(top,y,key,x,comp,mpl::false_());
0088 }
0089
0090 template<
0091   typename Node,typename KeyFromValue,
0092   typename CompatibleKey,typename CompatibleCompare
0093 >
0094 inline Node* ordered_index_find(
0095   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0096   const CompatibleCompare& comp,mpl::false_)
0097 {
0098   Node* y0=y;
0099
0100   while (top){
0101     if(!comp(key(top->value()),x)){
0102       y=top;
0103       top=Node::from_impl(top->left());
0104     }
0105     else top=Node::from_impl(top->right());
0106   }
0107
0108   return (y==y0||comp(x,key(y->value())))?y0:y;
0109 }
0110
0111 template<
0112   typename Node,typename KeyFromValue,
0113   typename CompatibleKey,typename CompatibleCompare
0114 >
0115 inline Node* ordered_index_lower_bound(
0116   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0117   const CompatibleCompare& comp)
0118 {
0119   typedef typename KeyFromValue::result_type key_type;
0120
0121   return ordered_index_lower_bound(
0122     top,y,key,x,comp,
0123     promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey>());
0124 }
0125
0126 template<
0127   typename Node,typename KeyFromValue,
0128   typename CompatibleCompare
0129 >
0130 inline Node* ordered_index_lower_bound(
0131   Node* top,Node* y,const KeyFromValue& key,
0132   const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
0133   const CompatibleCompare& comp,mpl::true_)
0134 {
0135   return ordered_index_lower_bound(top,y,key,x,comp,mpl::false_());
0136 }
0137
0138 template<
0139   typename Node,typename KeyFromValue,
0140   typename CompatibleKey,typename CompatibleCompare
0141 >
0142 inline Node* ordered_index_lower_bound(
0143   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0144   const CompatibleCompare& comp,mpl::false_)
0145 {
0146   while(top){
0147     if(!comp(key(top->value()),x)){
0148       y=top;
0149       top=Node::from_impl(top->left());
0150     }
0151     else top=Node::from_impl(top->right());
0152   }
0153
0154   return y;
0155 }
0156
0157 template<
0158   typename Node,typename KeyFromValue,
0159   typename CompatibleKey,typename CompatibleCompare
0160 >
0161 inline Node* ordered_index_upper_bound(
0162   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0163   const CompatibleCompare& comp)
0164 {
0165   typedef typename KeyFromValue::result_type key_type;
0166
0167   return ordered_index_upper_bound(
0168     top,y,key,x,comp,
0169     promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>());
0170 }
0171
0172 template<
0173   typename Node,typename KeyFromValue,
0174   typename CompatibleCompare
0175 >
0176 inline Node* ordered_index_upper_bound(
0177   Node* top,Node* y,const KeyFromValue& key,
0178   const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
0179   const CompatibleCompare& comp,mpl::true_)
0180 {
0181   return ordered_index_upper_bound(top,y,key,x,comp,mpl::false_());
0182 }
0183
0184 template<
0185   typename Node,typename KeyFromValue,
0186   typename CompatibleKey,typename CompatibleCompare
0187 >
0188 inline Node* ordered_index_upper_bound(
0189   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0190   const CompatibleCompare& comp,mpl::false_)
0191 {
0192   while(top){
0193     if(comp(x,key(top->value()))){
0194       y=top;
0195       top=Node::from_impl(top->left());
0196     }
0197     else top=Node::from_impl(top->right());
0198   }
0199
0200   return y;
0201 }
0202
0203 template<
0204   typename Node,typename KeyFromValue,
0205   typename CompatibleKey,typename CompatibleCompare
0206 >
0207 inline std::pair<Node*,Node*> ordered_index_equal_range(
0208   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0209   const CompatibleCompare& comp)
0210 {
0211   typedef typename KeyFromValue::result_type key_type;
0212
0213   return ordered_index_equal_range(
0214     top,y,key,x,comp,
0215     mpl::and_<
0216       promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
0217       promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
0218 }
0219
0220 template<
0221   typename Node,typename KeyFromValue,
0222   typename CompatibleCompare
0223 >
0224 inline std::pair<Node*,Node*> ordered_index_equal_range(
0225   Node* top,Node* y,const KeyFromValue& key,
0226   const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
0227   const CompatibleCompare& comp,mpl::true_)
0228 {
0229   return ordered_index_equal_range(top,y,key,x,comp,mpl::false_());
0230 }
0231
0232 template<
0233   typename Node,typename KeyFromValue,
0234   typename CompatibleKey,typename CompatibleCompare
0235 >
0236 inline std::pair<Node*,Node*> ordered_index_equal_range(
0237   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0238   const CompatibleCompare& comp,mpl::false_)
0239 {
0240   while(top){
0241     if(comp(key(top->value()),x)){
0242       top=Node::from_impl(top->right());
0243     }
0244     else if(comp(x,key(top->value()))){
0245       y=top;
0246       top=Node::from_impl(top->left());
0247     }
0248     else{
0249       return std::pair<Node*,Node*>(
0250         ordered_index_lower_bound(
0251           Node::from_impl(top->left()),top,key,x,comp,mpl::false_()),
0252         ordered_index_upper_bound(
0253           Node::from_impl(top->right()),y,key,x,comp,mpl::false_()));
0254     }
0255   }
0256
0257   return std::pair<Node*,Node*>(y,y);
0258 }
0259
0260 } /* namespace multi_index::detail */
0261
0262 } /* namespace multi_index */
0263
0264 } /* namespace boost */
0265
0266 #endif