sl@0: // Copyright (c)  2000 David Abrahams. 
sl@0: // Distributed under the Boost Software License, Version 1.0. 
sl@0: // (See accompanying file LICENSE_1_0.txt or copy at 
sl@0: // http://www.boost.org/LICENSE_1_0.txt)
sl@0: // 
sl@0: // Copyright (c) 1994
sl@0: // Hewlett-Packard Company
sl@0: // 
sl@0: // Permission to use, copy, modify, distribute and sell this software
sl@0: // and its documentation for any purpose is hereby granted without fee,
sl@0: // provided that the above copyright notice appear in all copies and
sl@0: // that both that copyright notice and this permission notice appear
sl@0: // in supporting documentation.  Hewlett-Packard Company makes no
sl@0: // representations about the suitability of this software for any
sl@0: // purpose.  It is provided "as is" without express or implied warranty.
sl@0: // 
sl@0: // Copyright (c) 1996
sl@0: // Silicon Graphics Computer Systems, Inc.
sl@0: // 
sl@0: // Permission to use, copy, modify, distribute and sell this software
sl@0: // and its documentation for any purpose is hereby granted without fee,
sl@0: // provided that the above copyright notice appear in all copies and
sl@0: // that both that copyright notice and this permission notice appear
sl@0: // in supporting documentation.  Silicon Graphics makes no
sl@0: // representations about the suitability of this software for any
sl@0: // purpose.  It is provided "as is" without express or implied warranty.
sl@0: // 
sl@0: #ifndef BINARY_SEARCH_DWA_122600_H_
sl@0: # define BINARY_SEARCH_DWA_122600_H_
sl@0: 
sl@0: # include <boost/detail/iterator.hpp>
sl@0: # include <utility>
sl@0: 
sl@0: namespace boost { namespace detail {
sl@0: 
sl@0: template <class ForwardIter, class Tp>
sl@0: ForwardIter lower_bound(ForwardIter first, ForwardIter last,
sl@0:                              const Tp& val) 
sl@0: {
sl@0:     typedef detail::iterator_traits<ForwardIter> traits;
sl@0:     
sl@0:     typename traits::difference_type len = boost::detail::distance(first, last);
sl@0:     typename traits::difference_type half;
sl@0:     ForwardIter middle;
sl@0: 
sl@0:     while (len > 0) {
sl@0:       half = len >> 1;
sl@0:       middle = first;
sl@0:       std::advance(middle, half);
sl@0:       if (*middle < val) {
sl@0:         first = middle;
sl@0:         ++first;
sl@0:         len = len - half - 1;
sl@0:       }
sl@0:       else
sl@0:         len = half;
sl@0:     }
sl@0:     return first;
sl@0: }
sl@0: 
sl@0: template <class ForwardIter, class Tp, class Compare>
sl@0: ForwardIter lower_bound(ForwardIter first, ForwardIter last,
sl@0:                               const Tp& val, Compare comp)
sl@0: {
sl@0:   typedef detail::iterator_traits<ForwardIter> traits;
sl@0: 
sl@0:   typename traits::difference_type len = boost::detail::distance(first, last);
sl@0:   typename traits::difference_type half;
sl@0:   ForwardIter middle;
sl@0: 
sl@0:   while (len > 0) {
sl@0:     half = len >> 1;
sl@0:     middle = first;
sl@0:     std::advance(middle, half);
sl@0:     if (comp(*middle, val)) {
sl@0:       first = middle;
sl@0:       ++first;
sl@0:       len = len - half - 1;
sl@0:     }
sl@0:     else
sl@0:       len = half;
sl@0:   }
sl@0:   return first;
sl@0: }
sl@0: 
sl@0: template <class ForwardIter, class Tp>
sl@0: ForwardIter upper_bound(ForwardIter first, ForwardIter last,
sl@0:                            const Tp& val)
sl@0: {
sl@0:   typedef detail::iterator_traits<ForwardIter> traits;
sl@0: 
sl@0:   typename traits::difference_type len = boost::detail::distance(first, last);
sl@0:   typename traits::difference_type half;
sl@0:   ForwardIter middle;
sl@0: 
sl@0:   while (len > 0) {
sl@0:     half = len >> 1;
sl@0:     middle = first;
sl@0:     std::advance(middle, half);
sl@0:     if (val < *middle)
sl@0:       len = half;
sl@0:     else {
sl@0:       first = middle;
sl@0:       ++first;
sl@0:       len = len - half - 1;
sl@0:     }
sl@0:   }
sl@0:   return first;
sl@0: }
sl@0: 
sl@0: template <class ForwardIter, class Tp, class Compare>
sl@0: ForwardIter upper_bound(ForwardIter first, ForwardIter last,
sl@0:                            const Tp& val, Compare comp)
sl@0: {
sl@0:   typedef detail::iterator_traits<ForwardIter> traits;
sl@0: 
sl@0:   typename traits::difference_type len = boost::detail::distance(first, last);
sl@0:   typename traits::difference_type half;
sl@0:   ForwardIter middle;
sl@0: 
sl@0:   while (len > 0) {
sl@0:     half = len >> 1;
sl@0:     middle = first;
sl@0:     std::advance(middle, half);
sl@0:     if (comp(val, *middle))
sl@0:       len = half;
sl@0:     else {
sl@0:       first = middle;
sl@0:       ++first;
sl@0:       len = len - half - 1;
sl@0:     }
sl@0:   }
sl@0:   return first;
sl@0: }
sl@0: 
sl@0: template <class ForwardIter, class Tp>
sl@0: std::pair<ForwardIter, ForwardIter>
sl@0: equal_range(ForwardIter first, ForwardIter last, const Tp& val)
sl@0: {
sl@0:   typedef detail::iterator_traits<ForwardIter> traits;
sl@0: 
sl@0:   typename traits::difference_type len = boost::detail::distance(first, last);
sl@0:   typename traits::difference_type half;
sl@0:   ForwardIter middle, left, right;
sl@0: 
sl@0:   while (len > 0) {
sl@0:     half = len >> 1;
sl@0:     middle = first;
sl@0:     std::advance(middle, half);
sl@0:     if (*middle < val) {
sl@0:       first = middle;
sl@0:       ++first;
sl@0:       len = len - half - 1;
sl@0:     }
sl@0:     else if (val < *middle)
sl@0:       len = half;
sl@0:     else {
sl@0:       left = boost::detail::lower_bound(first, middle, val);
sl@0:       std::advance(first, len);
sl@0:       right = boost::detail::upper_bound(++middle, first, val);
sl@0:       return std::pair<ForwardIter, ForwardIter>(left, right);
sl@0:     }
sl@0:   }
sl@0:   return std::pair<ForwardIter, ForwardIter>(first, first);
sl@0: }
sl@0: 
sl@0: template <class ForwardIter, class Tp, class Compare>
sl@0: std::pair<ForwardIter, ForwardIter>
sl@0: equal_range(ForwardIter first, ForwardIter last, const Tp& val,
sl@0:               Compare comp)
sl@0: {
sl@0:   typedef detail::iterator_traits<ForwardIter> traits;
sl@0: 
sl@0:   typename traits::difference_type len = boost::detail::distance(first, last);
sl@0:   typename traits::difference_type half;
sl@0:   ForwardIter middle, left, right;
sl@0: 
sl@0:   while (len > 0) {
sl@0:     half = len >> 1;
sl@0:     middle = first;
sl@0:     std::advance(middle, half);
sl@0:     if (comp(*middle, val)) {
sl@0:       first = middle;
sl@0:       ++first;
sl@0:       len = len - half - 1;
sl@0:     }
sl@0:     else if (comp(val, *middle))
sl@0:       len = half;
sl@0:     else {
sl@0:       left = boost::detail::lower_bound(first, middle, val, comp);
sl@0:       std::advance(first, len);
sl@0:       right = boost::detail::upper_bound(++middle, first, val, comp);
sl@0:       return std::pair<ForwardIter, ForwardIter>(left, right);
sl@0:     }
sl@0:   }
sl@0:   return std::pair<ForwardIter, ForwardIter>(first, first);
sl@0: }           
sl@0: 
sl@0: template <class ForwardIter, class Tp>
sl@0: bool binary_search(ForwardIter first, ForwardIter last,
sl@0:                    const Tp& val) {
sl@0:   ForwardIter i = boost::detail::lower_bound(first, last, val);
sl@0:   return i != last && !(val < *i);
sl@0: }
sl@0: 
sl@0: template <class ForwardIter, class Tp, class Compare>
sl@0: bool binary_search(ForwardIter first, ForwardIter last,
sl@0:                    const Tp& val,
sl@0:                    Compare comp) {
sl@0:   ForwardIter i = boost::detail::lower_bound(first, last, val, comp);
sl@0:   return i != last && !comp(val, *i);
sl@0: }
sl@0: 
sl@0: }} // namespace boost::detail
sl@0: 
sl@0: #endif // BINARY_SEARCH_DWA_122600_H_