| /* Copyright 2003-2008 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) |
| * |
| * See http://www.boost.org/libs/multi_index for library home page. |
| * |
| * The internal implementation of red-black trees is based on that of SGI STL |
| * stl_tree.h file: |
| * |
| * Copyright (c) 1996,1997 |
| * Silicon Graphics Computer Systems, Inc. |
| * |
| * Permission to use, copy, modify, distribute and sell this software |
| * and its documentation for any purpose is hereby granted without fee, |
| * provided that the above copyright notice appear in all copies and |
| * that both that copyright notice and this permission notice appear |
| * in supporting documentation. Silicon Graphics makes no |
| * representations about the suitability of this software for any |
| * purpose. It is provided "as is" without express or implied warranty. |
| * |
| * |
| * Copyright (c) 1994 |
| * Hewlett-Packard Company |
| * |
| * Permission to use, copy, modify, distribute and sell this software |
| * and its documentation for any purpose is hereby granted without fee, |
| * provided that the above copyright notice appear in all copies and |
| * that both that copyright notice and this permission notice appear |
| * in supporting documentation. Hewlett-Packard Company makes no |
| * representations about the suitability of this software for any |
| * purpose. It is provided "as is" without express or implied warranty. |
| * |
| */ |
| |
| #ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_HPP |
| #define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_HPP |
| |
| #if defined(_MSC_VER)&&(_MSC_VER>=1200) |
| #pragma once |
| #endif |
| |
| #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ |
| #include <utility> |
| |
| namespace boost{ |
| |
| namespace multi_index{ |
| |
| namespace detail{ |
| |
| /* Common code for index memfuns having templatized and |
| * non-templatized versions. |
| */ |
| |
| 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) |
| { |
| Node* y0=y; |
| |
| while (top){ |
| if(!comp(key(top->value()),x)){ |
| y=top; |
| top=Node::from_impl(top->left()); |
| } |
| else top=Node::from_impl(top->right()); |
| } |
| |
| return (y==y0||comp(x,key(y->value())))?y0:y; |
| } |
| |
| 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) |
| { |
| while(top){ |
| if(!comp(key(top->value()),x)){ |
| y=top; |
| top=Node::from_impl(top->left()); |
| } |
| else top=Node::from_impl(top->right()); |
| } |
| |
| return y; |
| } |
| |
| 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) |
| { |
| while(top){ |
| if(comp(x,key(top->value()))){ |
| y=top; |
| top=Node::from_impl(top->left()); |
| } |
| else top=Node::from_impl(top->right()); |
| } |
| |
| return y; |
| } |
| |
| 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) |
| { |
| while(top){ |
| if(comp(key(top->value()),x)){ |
| top=Node::from_impl(top->right()); |
| } |
| else if(comp(x,key(top->value()))){ |
| y=top; |
| top=Node::from_impl(top->left()); |
| } |
| 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)); |
| } |
| } |
| |
| return std::pair<Node*,Node*>(y,y); |
| } |
| |
| } /* namespace multi_index::detail */ |
| |
| } /* namespace multi_index */ |
| |
| } /* namespace boost */ |
| |
| #endif |