// Copyright (c)  2000 David Abrahams. 

// 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)

// 

// 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.

// 

// Copyright (c) 1996

// 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.

// 

#ifndef BINARY_SEARCH_DWA_122600_H_

# define BINARY_SEARCH_DWA_122600_H_

# include <boost/detail/iterator.hpp>

# include <utility>

namespace boost { namespace detail {

template <class ForwardIter, class Tp>

ForwardIter lower_bound(ForwardIter first, ForwardIter last,

                             const Tp& val) 

{

    typedef detail::iterator_traits<ForwardIter> traits;

    typename traits::difference_type len = boost::detail::distance(first, last);

    typename traits::difference_type half;

    ForwardIter middle;

    while (len > 0) {

      half = len >> 1;

      middle = first;

      std::advance(middle, half);

      if (*middle < val) {

        first = middle;

        ++first;

        len = len - half - 1;

      }

      else

        len = half;

    }

    return first;

}

template <class ForwardIter, class Tp, class Compare>

ForwardIter lower_bound(ForwardIter first, ForwardIter last,

                              const Tp& val, Compare comp)

{

  typedef detail::iterator_traits<ForwardIter> traits;

  typename traits::difference_type len = boost::detail::distance(first, last);

  typename traits::difference_type half;

  ForwardIter middle;

  while (len > 0) {

    half = len >> 1;

    middle = first;

    std::advance(middle, half);

    if (comp(*middle, val)) {

      first = middle;

      ++first;

      len = len - half - 1;

    }

    else

      len = half;

  }

  return first;

}

template <class ForwardIter, class Tp>

ForwardIter upper_bound(ForwardIter first, ForwardIter last,

                           const Tp& val)

{

  typedef detail::iterator_traits<ForwardIter> traits;

  typename traits::difference_type len = boost::detail::distance(first, last);

  typename traits::difference_type half;

  ForwardIter middle;

  while (len > 0) {

    half = len >> 1;

    middle = first;

    std::advance(middle, half);

    if (val < *middle)

      len = half;

    else {

      first = middle;

      ++first;

      len = len - half - 1;

    }

  }

  return first;

}

template <class ForwardIter, class Tp, class Compare>

ForwardIter upper_bound(ForwardIter first, ForwardIter last,

                           const Tp& val, Compare comp)

{

  typedef detail::iterator_traits<ForwardIter> traits;

  typename traits::difference_type len = boost::detail::distance(first, last);

  typename traits::difference_type half;

  ForwardIter middle;

  while (len > 0) {

    half = len >> 1;

    middle = first;

    std::advance(middle, half);

    if (comp(val, *middle))

      len = half;

    else {

      first = middle;

      ++first;

      len = len - half - 1;

    }

  }

  return first;

}

template <class ForwardIter, class Tp>

std::pair<ForwardIter, ForwardIter>

equal_range(ForwardIter first, ForwardIter last, const Tp& val)

{

  typedef detail::iterator_traits<ForwardIter> traits;

  typename traits::difference_type len = boost::detail::distance(first, last);

  typename traits::difference_type half;

  ForwardIter middle, left, right;

  while (len > 0) {

    half = len >> 1;

    middle = first;

    std::advance(middle, half);

    if (*middle < val) {

      first = middle;

      ++first;

      len = len - half - 1;

    }

    else if (val < *middle)

      len = half;

    else {

      left = boost::detail::lower_bound(first, middle, val);

      std::advance(first, len);

      right = boost::detail::upper_bound(++middle, first, val);

      return std::pair<ForwardIter, ForwardIter>(left, right);

    }

  }

  return std::pair<ForwardIter, ForwardIter>(first, first);

}

template <class ForwardIter, class Tp, class Compare>

std::pair<ForwardIter, ForwardIter>

equal_range(ForwardIter first, ForwardIter last, const Tp& val,

              Compare comp)

{

  typedef detail::iterator_traits<ForwardIter> traits;

  typename traits::difference_type len = boost::detail::distance(first, last);

  typename traits::difference_type half;

  ForwardIter middle, left, right;

  while (len > 0) {

    half = len >> 1;

    middle = first;

    std::advance(middle, half);

    if (comp(*middle, val)) {

      first = middle;

      ++first;

      len = len - half - 1;

    }

    else if (comp(val, *middle))

      len = half;

    else {

      left = boost::detail::lower_bound(first, middle, val, comp);

      std::advance(first, len);

      right = boost::detail::upper_bound(++middle, first, val, comp);

      return std::pair<ForwardIter, ForwardIter>(left, right);

    }

  }

  return std::pair<ForwardIter, ForwardIter>(first, first);

}           

template <class ForwardIter, class Tp>

bool binary_search(ForwardIter first, ForwardIter last,

                   const Tp& val) {

  ForwardIter i = boost::detail::lower_bound(first, last, val);

  return i != last && !(val < *i);

}

template <class ForwardIter, class Tp, class Compare>

bool binary_search(ForwardIter first, ForwardIter last,

                   const Tp& val,

                   Compare comp) {

  ForwardIter i = boost::detail::lower_bound(first, last, val, comp);

  return i != last && !comp(val, *i);

}

}} // namespace boost::detail

#endif // BINARY_SEARCH_DWA_122600_H_