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