blob: da27f39df7a8c5d14912aed54b0df7fffa787994 [file] [log] [blame]
Jeff Thompsonef2d5a42013-08-22 19:09:24 -07001// 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 <ndnboost/detail/iterator.hpp>
32# include <utility>
33
34namespace ndnboost { 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 = ndnboost::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 = ndnboost::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 = ndnboost::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 = ndnboost::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 = ndnboost::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 = ndnboost::detail::lower_bound(first, middle, val);
159 std::advance(first, len);
160 right = ndnboost::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 = ndnboost::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 = ndnboost::detail::lower_bound(first, middle, val, comp);
191 std::advance(first, len);
192 right = ndnboost::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 = ndnboost::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 = ndnboost::detail::lower_bound(first, last, val, comp);
211 return i != last && !comp(val, *i);
212}
213
214}} // namespace ndnboost::detail
215
216#endif // BINARY_SEARCH_DWA_122600_H_