boost_ext/boost/multi_index/detail/ord_index_ops.hpp

   1 /* Copyright 2003-2007 Joaquín M López Muñoz.
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE_1_0.txt or copy at
   4  * http://www.boost.org/LICENSE_1_0.txt)
   5  *
   6  * See http://www.boost.org/libs/multi_index for library home page.
   7  *
   8  * The internal implementation of red-black trees is based on that of SGI STL
   9  * stl_tree.h file:
  10  *
  11  * Copyright (c) 1996,1997
  12  * Silicon Graphics Computer Systems, Inc.
  13  *
  14  * Permission to use, copy, modify, distribute and sell this software
  15  * and its documentation for any purpose is hereby granted without fee,
  16  * provided that the above copyright notice appear in all copies and
  17  * that both that copyright notice and this permission notice appear
  18  * in supporting documentation.  Silicon Graphics makes no
  19  * representations about the suitability of this software for any
  20  * purpose.  It is provided "as is" without express or implied warranty.
  21  *
  22  *
  23  * Copyright (c) 1994
  24  * Hewlett-Packard Company
  25  *
  26  * Permission to use, copy, modify, distribute and sell this software
  27  * and its documentation for any purpose is hereby granted without fee,
  28  * provided that the above copyright notice appear in all copies and
  29  * that both that copyright notice and this permission notice appear
  30  * in supporting documentation.  Hewlett-Packard Company makes no
  31  * representations about the suitability of this software for any
  32  * purpose.  It is provided "as is" without express or implied warranty.
  33  *
  34  */
  35
  36 #ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_HPP
  37 #define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_HPP
  38
  39 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
  40 #pragma once
  41 #endif
  42
  43 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  44 #include <utility>
  45
  46 namespace boost{
  47
  48 namespace multi_index{
  49
  50 namespace detail{
  51
  52 /* Common code for index memfuns having templatized and
  53  * non-templatized versions.
  54  */
  55
  56 template<
  57   typename Node,typename KeyFromValue,
  58   typename CompatibleKey,typename CompatibleCompare
  59 >
  60 inline Node* ordered_index_find(
  61   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
  62   const CompatibleCompare& comp)
  63 {
  64   Node* y0=y;
  65
  66   while (top){
  67     if(!comp(key(top->value()),x)){
  68       y=top;
  69       top=Node::from_impl(top->left());
  70     }
  71     else top=Node::from_impl(top->right());
  72   }
  73
  74   return (y==y0||comp(x,key(y->value())))?y0:y;
  75 }
  76
  77 template<
  78   typename Node,typename KeyFromValue,
  79   typename CompatibleKey,typename CompatibleCompare
  80 >
  81 inline Node* ordered_index_lower_bound(
  82   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
  83   const CompatibleCompare& comp)
  84 {
  85   while(top){
  86     if(!comp(key(top->value()),x)){
  87       y=top;
  88       top=Node::from_impl(top->left());
  89     }
  90     else top=Node::from_impl(top->right());
  91   }
  92
  93   return y;
  94 }
  95
  96 template<
  97   typename Node,typename KeyFromValue,
  98   typename CompatibleKey,typename CompatibleCompare
  99 >
 100 inline Node* ordered_index_upper_bound(
 101   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
 102   const CompatibleCompare& comp)
 103 {
 104   while(top){
 105     if(comp(x,key(top->value()))){
 106       y=top;
 107       top=Node::from_impl(top->left());
 108     }
 109     else top=Node::from_impl(top->right());
 110   }
 111
 112   return y;
 113 }
 114
 115 template<
 116   typename Node,typename KeyFromValue,
 117   typename CompatibleKey,typename CompatibleCompare
 118 >
 119 inline std::pair<Node*,Node*> ordered_index_equal_range(
 120   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
 121   const CompatibleCompare& comp)
 122 {
 123   while(top){
 124     if(comp(key(top->value()),x)){
 125       top=Node::from_impl(top->right());
 126     }
 127     else if(comp(x,key(top->value()))){
 128       y=top;
 129       top=Node::from_impl(top->left());
 130     }
 131     else{
 132       return std::pair<Node*,Node*>(
 133         ordered_index_lower_bound(Node::from_impl(top->left()),top,key,x,comp),
 134         ordered_index_upper_bound(Node::from_impl(top->right()),y,key,x,comp));
 135     }
 136   }
 137
 138   return std::pair<Node*,Node*>(y,y);
 139 }
 140
 141 } /* namespace multi_index::detail */
 142
 143 } /* namespace multi_index */
 144
 145 } /* namespace boost */
 146
 147 #endif