source: NonGTP/Boost/boost/detail/binary_search.hpp @ 857

Revision 857, 6.4 KB checked in by igarcia, 19 years ago (diff)
Line 
1// Copyright (c)  2000 David Abrahams.
2// Distributed under the Boost Software License, Version 1.0.
3// (See accompanying file LICENSE_1_0.txt or copy at
4// http://www.boost.org/LICENSE_1_0.txt)
5//
6// Copyright (c) 1994
7// Hewlett-Packard Company
8//
9// Permission to use, copy, modify, distribute and sell this software
10// and its documentation for any purpose is hereby granted without fee,
11// provided that the above copyright notice appear in all copies and
12// that both that copyright notice and this permission notice appear
13// in supporting documentation.  Hewlett-Packard Company makes no
14// representations about the suitability of this software for any
15// purpose.  It is provided "as is" without express or implied warranty.
16//
17// Copyright (c) 1996
18// Silicon Graphics Computer Systems, Inc.
19//
20// Permission to use, copy, modify, distribute and sell this software
21// and its documentation for any purpose is hereby granted without fee,
22// provided that the above copyright notice appear in all copies and
23// that both that copyright notice and this permission notice appear
24// in supporting documentation.  Silicon Graphics makes no
25// representations about the suitability of this software for any
26// purpose.  It is provided "as is" without express or implied warranty.
27//
28#ifndef BINARY_SEARCH_DWA_122600_H_
29# define BINARY_SEARCH_DWA_122600_H_
30
31# include <boost/detail/iterator.hpp>
32# include <utility>
33
34namespace boost { namespace detail {
35
36template <class ForwardIter, class Tp>
37ForwardIter lower_bound(ForwardIter first, ForwardIter last,
38                             const Tp& val)
39{
40    typedef detail::iterator_traits<ForwardIter> traits;
41   
42    typename traits::difference_type len = boost::detail::distance(first, last);
43    typename traits::difference_type half;
44    ForwardIter middle;
45
46    while (len > 0) {
47      half = len >> 1;
48      middle = first;
49      std::advance(middle, half);
50      if (*middle < val) {
51        first = middle;
52        ++first;
53        len = len - half - 1;
54      }
55      else
56        len = half;
57    }
58    return first;
59}
60
61template <class ForwardIter, class Tp, class Compare>
62ForwardIter lower_bound(ForwardIter first, ForwardIter last,
63                              const Tp& val, Compare comp)
64{
65  typedef detail::iterator_traits<ForwardIter> traits;
66
67  typename traits::difference_type len = boost::detail::distance(first, last);
68  typename traits::difference_type half;
69  ForwardIter middle;
70
71  while (len > 0) {
72    half = len >> 1;
73    middle = first;
74    std::advance(middle, half);
75    if (comp(*middle, val)) {
76      first = middle;
77      ++first;
78      len = len - half - 1;
79    }
80    else
81      len = half;
82  }
83  return first;
84}
85
86template <class ForwardIter, class Tp>
87ForwardIter upper_bound(ForwardIter first, ForwardIter last,
88                           const Tp& val)
89{
90  typedef detail::iterator_traits<ForwardIter> traits;
91
92  typename traits::difference_type len = boost::detail::distance(first, last);
93  typename traits::difference_type half;
94  ForwardIter middle;
95
96  while (len > 0) {
97    half = len >> 1;
98    middle = first;
99    std::advance(middle, half);
100    if (val < *middle)
101      len = half;
102    else {
103      first = middle;
104      ++first;
105      len = len - half - 1;
106    }
107  }
108  return first;
109}
110
111template <class ForwardIter, class Tp, class Compare>
112ForwardIter upper_bound(ForwardIter first, ForwardIter last,
113                           const Tp& val, Compare comp)
114{
115  typedef detail::iterator_traits<ForwardIter> traits;
116
117  typename traits::difference_type len = boost::detail::distance(first, last);
118  typename traits::difference_type half;
119  ForwardIter middle;
120
121  while (len > 0) {
122    half = len >> 1;
123    middle = first;
124    std::advance(middle, half);
125    if (comp(val, *middle))
126      len = half;
127    else {
128      first = middle;
129      ++first;
130      len = len - half - 1;
131    }
132  }
133  return first;
134}
135
136template <class ForwardIter, class Tp>
137std::pair<ForwardIter, ForwardIter>
138equal_range(ForwardIter first, ForwardIter last, const Tp& val)
139{
140  typedef detail::iterator_traits<ForwardIter> traits;
141
142  typename traits::difference_type len = boost::detail::distance(first, last);
143  typename traits::difference_type half;
144  ForwardIter middle, left, right;
145
146  while (len > 0) {
147    half = len >> 1;
148    middle = first;
149    std::advance(middle, half);
150    if (*middle < val) {
151      first = middle;
152      ++first;
153      len = len - half - 1;
154    }
155    else if (val < *middle)
156      len = half;
157    else {
158      left = boost::detail::lower_bound(first, middle, val);
159      std::advance(first, len);
160      right = boost::detail::upper_bound(++middle, first, val);
161      return std::pair<ForwardIter, ForwardIter>(left, right);
162    }
163  }
164  return std::pair<ForwardIter, ForwardIter>(first, first);
165}
166
167template <class ForwardIter, class Tp, class Compare>
168std::pair<ForwardIter, ForwardIter>
169equal_range(ForwardIter first, ForwardIter last, const Tp& val,
170              Compare comp)
171{
172  typedef detail::iterator_traits<ForwardIter> traits;
173
174  typename traits::difference_type len = boost::detail::distance(first, last);
175  typename traits::difference_type half;
176  ForwardIter middle, left, right;
177
178  while (len > 0) {
179    half = len >> 1;
180    middle = first;
181    std::advance(middle, half);
182    if (comp(*middle, val)) {
183      first = middle;
184      ++first;
185      len = len - half - 1;
186    }
187    else if (comp(val, *middle))
188      len = half;
189    else {
190      left = boost::detail::lower_bound(first, middle, val, comp);
191      std::advance(first, len);
192      right = boost::detail::upper_bound(++middle, first, val, comp);
193      return std::pair<ForwardIter, ForwardIter>(left, right);
194    }
195  }
196  return std::pair<ForwardIter, ForwardIter>(first, first);
197}           
198
199template <class ForwardIter, class Tp>
200bool binary_search(ForwardIter first, ForwardIter last,
201                   const Tp& val) {
202  ForwardIter i = boost::detail::lower_bound(first, last, val);
203  return i != last && !(val < *i);
204}
205
206template <class ForwardIter, class Tp, class Compare>
207bool binary_search(ForwardIter first, ForwardIter last,
208                   const Tp& val,
209                   Compare comp) {
210  ForwardIter i = boost::detail::lower_bound(first, last, val, comp);
211  return i != last && !comp(val, *i);
212}
213
214}} // namespace boost::detail
215
216#endif // BINARY_SEARCH_DWA_122600_H_
Note: See TracBrowser for help on using the repository browser.