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