#ifndef MULTI_INDEX_ALGORITHMS_HPP
#define MULTI_INDEX_ALGORITHMS_HPP

#if defined(_MSC_VER)&&(_MSC_VER>=1200)
#pragma once
#endif

#pragma once

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/detail/ord_index_node.hpp>
#include <boost/multi_index/detail/ord_index_ops.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/mem_fun.hpp> 
#include <functional>
#include <utility>

namespace boost{

namespace multi_index{

namespace detail{

/*
PARAMETERS OF THE TEMPLATE

index_iterator is a type of iterator in a multi_index_container's index

ARGUMENTS OF THE FUNCTION

iter is an iterator in the multi_index_container's index

PRECONDITIONS

iter must NOT point to the end (after-the-last) of the multi_index_container's
index; i.e. iter must be dereferenceable

RETURN VALUE

A pair of pointers to special nodes of the underlying internal tree:
root and header
*/
template<class index_iterator>
std::pair<
  typename index_iterator::node_type*,
  typename index_iterator::node_type*
>
find_root_and_header(index_iterator const& iter)
{
  typedef typename index_iterator::node_type node_type;

  node_type* root=iter.get_node();
  node_type* header=
	node_type::from_impl(root->parent());
  node_type* next=
	node_type::from_impl(header->parent());

  while(root!=next) {
	root=header;
	header=next;
	next=node_type::from_impl(next->parent());
  }

  return std::make_pair(root,header);
}

/*
just for typename abbreviation
*/
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  #define BOOST_MULTI_INDEX_ITERATOR                               \
    boost::multi_index::safe_mode::safe_iterator<                  \
      boost::multi_index::detail::bidir_node_iterator<             \
		boost::multi_index::detail::ordered_index_node<NodeBase>   \
	  >,                                                           \
	  OrderedIndex                                                 \
	>
#else
  #define BOOST_MULTI_INDEX_ITERATOR                               \
    boost::multi_index::detail::bidir_node_iterator<               \
	  boost::multi_index::detail::ordered_index_node<NodeBase>     \
	>
#endif


/*
Consider a container with iterators. Let us use the following notations:
  (j{k)  means "position j precedes k in the container/index"
  (j{=k) means "position j precedes or is the same as k",
  (x~y)  means "not(x<y) and not(y<x)".
It is guaranteed that (*j<*k) => (j{k), for all iters j and k in [begin,end).

Given: iterators first and last, such that (begin {= first { last {= end),
and an iter i, (begin{=i{=end), such that (i{=j) for all such j that (*i~*j).
Find its projection p on interval [first, last) defined as follows:
  a) p = last if last { i
  b) p = first if i { first
  c) p = i in all other cases, i.e. if (first {= i {= last)
*/
template<
  typename NodeBase,
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  typename OrderedIndex,
#endif
  typename CompatibleCompare
>
BOOST_MULTI_INDEX_ITERATOR iterator_projection_on_interval(
  ordered_index_node<NodeBase>* i,
  BOOST_MULTI_INDEX_ITERATOR first, 
  BOOST_MULTI_INDEX_ITERATOR last, 
  ordered_index_node<NodeBase>* end,
  CompatibleCompare comp
) {
  /* (i=end) means that (last{=i), case a */
  if(i==end)
	return last;
  /* (*last<*i), provided that (last{end), means that (last{i), case a */
  if((last.get_node()!=end) && (comp(*last,i->value())))
	  return last;
  /* if nothing above is true, i.e. (i{end) and either (last=end) or (*last~*i)
  or (*i<*last), then (i{=last), and it remains to compare it with first */
  /* case b */
  if(!comp(*first,i->value()))
    return first;
  /* case c */
  return BOOST_MULTI_INDEX_ITERATOR( i 
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  , const_cast<OrderedIndex*>(first.owner())
#endif
  );
}

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */


namespace std{

/*
PARAMETERS OF THE TEMPLATE

NodeBase is the type of the multi_index_container's node (internal data
structure used to store elements).

CompatibleKey is either the type of values stored in the multi_index_container,
or some type to which it can be converted.

CompatibleCompare is a strict weak ordering on values of type CompatibleKey

When instatiating a concrete function from this template, there is no need to
specify template parameters explicitly: the compiler must deduce ell them from
argument types

ARGUMENTS OF THE FUNCTION

first, last are iterators that restrict the search area

x is the value to search in the multi_index_container's index in the given range

comp is a functional object that compares values of the type CompatibleKey.
Optional: if omitted, defaults to operator< (must be defined for the values)

PRECONDITIONS

[first, last) must be a valid range in the multi_index_container's index.
In particular,
first must NOT point to the end (after-the-last) of the multi_index_container's
index; i.e. first must be dereferenceable

comp ordering must be the same or weaker than the ordering of the
multi_index_container's index

RETURN VALUE:

the furthermost iterator i in [first, last) such that, for every iterator j
in [first, i), *j < value (or comp(*j, value) is true)
*/

/* uses a custom comparator */
template<
  typename NodeBase,
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  typename OrderedIndex,
#endif
  typename CompatibleKey,
  typename CompatibleCompare
>
BOOST_MULTI_INDEX_ITERATOR lower_bound( 
  BOOST_MULTI_INDEX_ITERATOR first,
  BOOST_MULTI_INDEX_ITERATOR last, 
  const CompatibleKey& x, CompatibleCompare comp
) {
  typedef boost::multi_index::detail::ordered_index_node<NodeBase> node_type;

  if(first==last) return last;

  std::pair<node_type*,node_type*> root_and_header=
	find_root_and_header(first);

  /* we work with values themselves, not with their keys */
  boost::multi_index::identity<BOOST_MULTI_INDEX_ITERATOR::value_type>
	  key_extractor;
  node_type* i=
	boost::multi_index::detail::ordered_index_lower_bound(root_and_header.first,
	  root_and_header.second,key_extractor,x,comp);

  return boost::multi_index::detail::iterator_projection_on_interval<
	  NodeBase,
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
	  OrderedIndex,
#endif
	  CompatibleCompare
  >(i,first,last,root_and_header.second,comp);
}

/* uses operator< */
template<
  typename NodeBase,
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  typename OrderedIndex,
#endif
  typename CompatibleKey
>
BOOST_MULTI_INDEX_ITERATOR lower_bound( 
  BOOST_MULTI_INDEX_ITERATOR first,
  BOOST_MULTI_INDEX_ITERATOR last, 
  const CompatibleKey& x
)
{
	return lower_bound(first,last,x,std::less<CompatibleKey>());
}


/*
PARAMETERS OF THE TEMPLATE,
ARGUMENTS OF THE FUNCTION,
PRECONDITIONS:

see lower_bound

RETURN VALUE:

the furthermost iterator i in [first, last) such that, for every iterator j
in [first, i), value < *j is false (or comp(value, *j) is false).
*/


// uses a custom comparator
template<
  typename NodeBase,
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  typename OrderedIndex,
#endif
  typename CompatibleKey,
  typename CompatibleCompare
>
BOOST_MULTI_INDEX_ITERATOR upper_bound( 
  BOOST_MULTI_INDEX_ITERATOR first, 
  BOOST_MULTI_INDEX_ITERATOR last,
  const CompatibleKey& x, CompatibleCompare comp
)
{
  typedef boost::multi_index::detail::ordered_index_node<NodeBase> node_type;

  if(first==last) return last;

  std::pair<node_type*,node_type*> root_and_header=find_root_and_header(first);
  
  /* we work with values themselves, not with their keys */
  boost::multi_index::identity<BOOST_MULTI_INDEX_ITERATOR::value_type>
	  key_extractor;
  node_type* i=
	boost::multi_index::detail::ordered_index_upper_bound(root_and_header.first,
	  root_and_header.second,key_extractor,x,comp);

  return boost::multi_index::detail::iterator_projection_on_interval<
	  NodeBase,
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
	  OrderedIndex,
#endif
	  CompatibleCompare
  >(i,first,last,root_and_header.second,comp);
}

// uses std::less
template<
  typename NodeBase,
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  typename OrderedIndex,
#endif
  typename CompatibleKey
>
BOOST_MULTI_INDEX_ITERATOR upper_bound(
  BOOST_MULTI_INDEX_ITERATOR first,
  BOOST_MULTI_INDEX_ITERATOR last,
  const CompatibleKey& x
)
{
	return upper_bound(first,last,x,std::less<CompatibleKey>());
}


/*
PARAMETERS OF THE TEMPLATE,
ARGUMENTS OF THE FUNCTION,
PRECONDITIONS:

see lower_bound

RETURN VALUE:

a pair of iterators: lower_bound and upper_bound (see)
*/

// uses a custom comparator
template<
  typename NodeBase,
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  typename OrderedIndex,
#endif
  typename CompatibleKey,
  typename CompatibleCompare
>
std::pair<BOOST_MULTI_INDEX_ITERATOR,BOOST_MULTI_INDEX_ITERATOR>
equal_range(
  BOOST_MULTI_INDEX_ITERATOR first,
  BOOST_MULTI_INDEX_ITERATOR last,
  const CompatibleKey& x, CompatibleCompare comp
)
{
  typedef boost::multi_index::detail::ordered_index_node<NodeBase> node_type;

  if(first==last) return std::make_pair(last, last);

  std::pair<node_type*,node_type*> root_and_header=find_root_and_header(first);

  /* we work with values themselves, not with their keys */
  boost::multi_index::identity<BOOST_MULTI_INDEX_ITERATOR::value_type>
	  key_extractor;
  std::pair<node_type*,node_type*> p=
	boost::multi_index::detail::ordered_index_equal_range(root_and_header.first,
	  root_and_header.second,key_extractor, x, comp);

  return std::make_pair(
    boost::multi_index::detail::iterator_projection_on_interval<
	  NodeBase,
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
	  OrderedIndex,
#endif
	  CompatibleCompare
	>(p.first, first,last,root_and_header.second,comp),
    boost::multi_index::detail::iterator_projection_on_interval<
	  NodeBase,
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
	  OrderedIndex,
#endif
	  CompatibleCompare
	>(p.second,first,last,root_and_header.second,comp)
  );
}

// uses std::less
template<
  typename NodeBase,
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  typename OrderedIndex,
#endif
  typename CompatibleKey
>
std::pair<
  BOOST_MULTI_INDEX_ITERATOR,
  BOOST_MULTI_INDEX_ITERATOR 
>
equal_range(
  BOOST_MULTI_INDEX_ITERATOR first,
  BOOST_MULTI_INDEX_ITERATOR last,
  const CompatibleKey& x
)
{
  return equal_range(first,last,x,std::less<CompatibleKey>());
}


/*
PARAMETERS OF THE TEMPLATE,
ARGUMENTS OF THE FUNCTION,
PRECONDITIONS:

see lower_bound

RETURN VALUE:

true if and only if the range [first,last) contains an element whose value is
equivalent to x (with respect to the given ordering relation), false otherwise
*/


/* uses a custom comparator */
template<
  typename NodeBase,
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  typename OrderedIndex,
#endif
  typename CompatibleKey,
  typename CompatibleCompare
>
bool binary_search( 
  BOOST_MULTI_INDEX_ITERATOR first,
  BOOST_MULTI_INDEX_ITERATOR last,
  const CompatibleKey& x, CompatibleCompare comp
) {
  first = lower_bound(first, last, x, comp);
  return (first != last && !comp(x, *first));
}

/* uses operator< */
template<
  typename NodeBase,
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  typename OrderedIndex,
#endif
  typename CompatibleKey
>
bool binary_search( 
  BOOST_MULTI_INDEX_ITERATOR first,
  BOOST_MULTI_INDEX_ITERATOR last, 
  const CompatibleKey& x
)
{
	return binary_search(first,last,x,std::less<CompatibleKey>());
}


} /* namespace std */


#endif /* MULTI_INDEX_ALGORITHMS_HPP */