Merge c:/dyninst/pc_bluegene/dyninst into dyn_pc_integration
[dyninst.git] / external / boost / detail / binary_search.hpp
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
34 namespace boost { namespace detail {
35
36 template <class ForwardIter, class Tp>
37 ForwardIter 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
61 template <class ForwardIter, class Tp, class Compare>
62 ForwardIter 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
86 template <class ForwardIter, class Tp>
87 ForwardIter 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
111 template <class ForwardIter, class Tp, class Compare>
112 ForwardIter 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
136 template <class ForwardIter, class Tp>
137 std::pair<ForwardIter, ForwardIter>
138 equal_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
167 template <class ForwardIter, class Tp, class Compare>
168 std::pair<ForwardIter, ForwardIter>
169 equal_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
199 template <class ForwardIter, class Tp>
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>
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_