← Back to branch summary

~ubuntu-branches/ubuntu/warty/aqsis/warty

« back to all changes in this revision

Viewing changes to boost/boost/detail/binary_search.hpp

  • Committer: Bazaar Package Importer
  • Author(s): LaMont Jones
  • Date: 2004-08-24 07:25:04 UTC
  • Revision ID: james.westby@ubuntu.com-20040824072504-zf993vnevvisdsvb
Tags: upstream-0.9.1
Import upstream version 0.9.1

Show diffs side-by-side

added added

removed removed

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