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