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