text: /* Copyright 2003-2013 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)
  #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
  