/* Copyright 2003-2007 Joaquín M López Muñoz.

 * 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

