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