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 <utility>
32 # include <iterator>
33
34 namespace boost { namespace detail {
35
36 template <class ForwardIter, class Tp>
lower_bound(ForwardIter first,ForwardIter last,const Tp & val)37 ForwardIter lower_bound(ForwardIter first, ForwardIter last,
38 const Tp& val)
39 {
40 typedef std::iterator_traits<ForwardIter> traits;
41
42 typename traits::difference_type len = std::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
61 template <class ForwardIter, class Tp, class Compare>
lower_bound(ForwardIter first,ForwardIter last,const Tp & val,Compare comp)62 ForwardIter lower_bound(ForwardIter first, ForwardIter last,
63 const Tp& val, Compare comp)
64 {
65 typedef std::iterator_traits<ForwardIter> traits;
66
67 typename traits::difference_type len = std::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
86 template <class ForwardIter, class Tp>
upper_bound(ForwardIter first,ForwardIter last,const Tp & val)87 ForwardIter upper_bound(ForwardIter first, ForwardIter last,
88 const Tp& val)
89 {
90 typedef std::iterator_traits<ForwardIter> traits;
91
92 typename traits::difference_type len = std::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
111 template <class ForwardIter, class Tp, class Compare>
upper_bound(ForwardIter first,ForwardIter last,const Tp & val,Compare comp)112 ForwardIter upper_bound(ForwardIter first, ForwardIter last,
113 const Tp& val, Compare comp)
114 {
115 typedef std::iterator_traits<ForwardIter> traits;
116
117 typename traits::difference_type len = std::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
136 template <class ForwardIter, class Tp>
137 std::pair<ForwardIter, ForwardIter>
equal_range(ForwardIter first,ForwardIter last,const Tp & val)138 equal_range(ForwardIter first, ForwardIter last, const Tp& val)
139 {
140 typedef std::iterator_traits<ForwardIter> traits;
141
142 typename traits::difference_type len = std::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
167 template <class ForwardIter, class Tp, class Compare>
168 std::pair<ForwardIter, ForwardIter>
equal_range(ForwardIter first,ForwardIter last,const Tp & val,Compare comp)169 equal_range(ForwardIter first, ForwardIter last, const Tp& val,
170 Compare comp)
171 {
172 typedef std::iterator_traits<ForwardIter> traits;
173
174 typename traits::difference_type len = std::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
199 template <class ForwardIter, class Tp>
binary_search(ForwardIter first,ForwardIter last,const Tp & val)200 bool 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
206 template <class ForwardIter, class Tp, class Compare>
binary_search(ForwardIter first,ForwardIter last,const Tp & val,Compare comp)207 bool 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_
217