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)
6 * See http://www.boost.org/libs/multi_index for library home page.
8 * The internal implementation of red-black trees is based on that of SGI STL
11 * Copyright (c) 1996,1997
12 * Silicon Graphics Computer Systems, Inc.
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.
24 * Hewlett-Packard Company
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.
36 #ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_HPP
37 #define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_HPP
39 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
43 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
48 namespace multi_index{
52 /* Common code for index memfuns having templatized and
53 * non-templatized versions.
57 typename Node,typename KeyFromValue,
58 typename CompatibleKey,typename CompatibleCompare
60 inline Node* ordered_index_find(
61 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
62 const CompatibleCompare& comp)
67 if(!comp(key(top->value()),x)){
69 top=Node::from_impl(top->left());
71 else top=Node::from_impl(top->right());
74 return (y==y0||comp(x,key(y->value())))?y0:y;
78 typename Node,typename KeyFromValue,
79 typename CompatibleKey,typename CompatibleCompare
81 inline Node* ordered_index_lower_bound(
82 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
83 const CompatibleCompare& comp)
86 if(!comp(key(top->value()),x)){
88 top=Node::from_impl(top->left());
90 else top=Node::from_impl(top->right());
97 typename Node,typename KeyFromValue,
98 typename CompatibleKey,typename CompatibleCompare
100 inline Node* ordered_index_upper_bound(
101 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
102 const CompatibleCompare& comp)
105 if(comp(x,key(top->value()))){
107 top=Node::from_impl(top->left());
109 else top=Node::from_impl(top->right());
116 typename Node,typename KeyFromValue,
117 typename CompatibleKey,typename CompatibleCompare
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)
124 if(comp(key(top->value()),x)){
125 top=Node::from_impl(top->right());
127 else if(comp(x,key(top->value()))){
129 top=Node::from_impl(top->left());
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));
138 return std::pair<Node*,Node*>(y,y);
141 } /* namespace multi_index::detail */
143 } /* namespace multi_index */
145 } /* namespace boost */