]>
Commit | Line | Data |
---|---|---|
1 | // (C) Copyright David Abrahams 2000. | |
2 | // Distributed under the Boost Software License, Version 1.0. (See | |
3 | // accompanying file LICENSE_1_0.txt or copy at | |
4 | // http://www.boost.org/LICENSE_1_0.txt) | |
5 | ||
6 | #include <vector> | |
7 | #include <string> | |
8 | #include <memory> | |
9 | #include <climits> | |
10 | #include <iostream> | |
11 | #include <cassert> | |
12 | #include <stdlib.h> // for rand(). Would use cstdlib but VC6.4 doesn't put it in std:: | |
13 | #include <list> | |
14 | #include <algorithm> | |
15 | #include <boost/detail/binary_search.hpp> | |
16 | #include <boost/detail/workaround.hpp> | |
17 | #include <cstddef> | |
18 | ||
19 | #if defined(__SGI_STL_PORT) ? defined(__SGI_STL_OWN_IOSTREAMS) : (!defined(__GNUC__) || __GNUC__ > 2) | |
20 | # define USE_SSTREAM | |
21 | #endif | |
22 | ||
23 | #ifdef USE_SSTREAM | |
24 | # include <sstream> | |
25 | #else | |
26 | # include <strstream> | |
27 | #endif | |
28 | ||
29 | namespace { | |
30 | ||
31 | // In order to get ADL to find the comparison operators defined below, they have | |
32 | struct mystring : std::string | |
33 | { | |
34 | typedef std::string base; | |
35 | ||
36 | mystring(std::string const& x) | |
37 | : base(x) {} | |
38 | }; | |
39 | ||
40 | typedef std::vector<mystring> string_vector; | |
41 | ||
42 | const std::size_t sequence_length = 1000; | |
43 | ||
44 | unsigned random_number() | |
45 | { | |
46 | return static_cast<unsigned>(::rand()) % sequence_length; | |
47 | } | |
48 | ||
49 | # ifndef USE_SSTREAM | |
50 | class unfreezer { | |
51 | public: | |
52 | unfreezer(std::ostrstream& s) : m_stream(s) {} | |
53 | ~unfreezer() { m_stream.freeze(false); } | |
54 | private: | |
55 | std::ostrstream& m_stream; | |
56 | }; | |
57 | # endif | |
58 | ||
59 | template <class T> | |
60 | void push_back_random_number_string(T& seq) | |
61 | { | |
62 | unsigned value = random_number(); | |
63 | # if defined(__SGI_STL_PORT) ? defined(__SGI_STL_OWN_IOSTREAMS) : (!defined(__GNUC__) || __GNUC__ > 2) | |
64 | std::ostringstream s; | |
65 | s << value; | |
66 | seq.push_back(s.str()); | |
67 | # else | |
68 | std::ostrstream s; | |
69 | auto unfreezer unfreeze(s); | |
70 | s << value << char(0); | |
71 | seq.push_back(std::string(s.str())); | |
72 | # endif | |
73 | } | |
74 | ||
75 | inline unsigned to_int(unsigned x) { return x; } | |
76 | inline unsigned to_int(const std::string& x) { return atoi(x.c_str()); } | |
77 | ||
78 | struct cmp | |
79 | { | |
80 | template <class A1, class A2> | |
81 | inline bool operator()(const A1& a1, const A2& a2) const | |
82 | { | |
83 | return to_int(a1) < to_int(a2); | |
84 | } | |
85 | }; | |
86 | ||
87 | inline bool operator<(const mystring& x, const unsigned y) | |
88 | { | |
89 | return to_int(x) < y; | |
90 | } | |
91 | ||
92 | inline bool operator<(const unsigned y, const mystring& x) | |
93 | { | |
94 | return y < to_int(x); | |
95 | } | |
96 | ||
97 | template <class T> | |
98 | void sort_by_value(T& x); | |
99 | ||
100 | template <class T> | |
101 | void sort_by_value_(T& v, long) | |
102 | { | |
103 | std::sort(v.begin(), v.end(), cmp()); | |
104 | } | |
105 | ||
106 | template <class T> | |
107 | void random_sorted_sequence(T& seq) | |
108 | { | |
109 | seq.clear(); | |
110 | for (std::size_t i = 0; i < sequence_length; ++i) | |
111 | { | |
112 | push_back_random_number_string(seq); | |
113 | } | |
114 | sort_by_value(seq); | |
115 | } | |
116 | ||
117 | template <class T, class A> | |
118 | void sort_by_value_(std::list<T,A>& l, int) | |
119 | { | |
120 | # if BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, == 1) && !defined(__SGI_STL_PORT) | |
121 | // VC6's standard lib doesn't have a template member function for list::sort() | |
122 | std::vector<T> seq; | |
123 | seq.reserve(sequence_length); | |
124 | std::copy(l.begin(), l.end(), std::back_inserter(seq)); | |
125 | sort_by_value(seq); | |
126 | std::copy(seq.begin(), seq.end(), l.begin()); | |
127 | # else | |
128 | l.sort(cmp()); | |
129 | # endif | |
130 | } | |
131 | ||
132 | template <class T> | |
133 | void sort_by_value(T& x) | |
134 | { | |
135 | (sort_by_value_)(x, 1); | |
136 | } | |
137 | ||
138 | // A way to select the comparisons with/without a Compare parameter for testing. | |
139 | template <class Compare> struct searches | |
140 | { | |
141 | template <class Iterator, class Key> | |
142 | static Iterator lower_bound(Iterator start, Iterator finish, Key key, Compare cmp) | |
143 | { return boost::detail::lower_bound(start, finish, key, cmp); } | |
144 | ||
145 | template <class Iterator, class Key> | |
146 | static Iterator upper_bound(Iterator start, Iterator finish, Key key, Compare cmp) | |
147 | { return boost::detail::upper_bound(start, finish, key, cmp); } | |
148 | ||
149 | template <class Iterator, class Key> | |
150 | static std::pair<Iterator, Iterator> equal_range(Iterator start, Iterator finish, Key key, Compare cmp) | |
151 | { return boost::detail::equal_range(start, finish, key, cmp); } | |
152 | ||
153 | template <class Iterator, class Key> | |
154 | static bool binary_search(Iterator start, Iterator finish, Key key, Compare cmp) | |
155 | { return boost::detail::binary_search(start, finish, key, cmp); } | |
156 | }; | |
157 | ||
158 | struct no_compare {}; | |
159 | ||
160 | template <> struct searches<no_compare> | |
161 | { | |
162 | template <class Iterator, class Key> | |
163 | static Iterator lower_bound(Iterator start, Iterator finish, Key key, no_compare) | |
164 | { return boost::detail::lower_bound(start, finish, key); } | |
165 | ||
166 | template <class Iterator, class Key> | |
167 | static Iterator upper_bound(Iterator start, Iterator finish, Key key, no_compare) | |
168 | { return boost::detail::upper_bound(start, finish, key); } | |
169 | ||
170 | template <class Iterator, class Key> | |
171 | static std::pair<Iterator, Iterator> equal_range(Iterator start, Iterator finish, Key key, no_compare) | |
172 | { return boost::detail::equal_range(start, finish, key); } | |
173 | ||
174 | template <class Iterator, class Key> | |
175 | static bool binary_search(Iterator start, Iterator finish, Key key, no_compare) | |
176 | { return boost::detail::binary_search(start, finish, key); } | |
177 | }; | |
178 | ||
179 | template <class Sequence, class Compare> | |
180 | void test_loop(Sequence& x, Compare cmp, unsigned long test_count) | |
181 | { | |
182 | typedef typename Sequence::const_iterator const_iterator; | |
183 | ||
184 | for (unsigned long i = 0; i < test_count; ++i) | |
185 | { | |
186 | random_sorted_sequence(x); | |
187 | const const_iterator start = x.begin(); | |
188 | const const_iterator finish = x.end(); | |
189 | ||
190 | unsigned key = random_number(); | |
191 | const const_iterator l = searches<Compare>::lower_bound(start, finish, key, cmp); | |
192 | const const_iterator u = searches<Compare>::upper_bound(start, finish, key, cmp); | |
193 | ||
194 | bool found_l = false; | |
195 | bool found_u = false; | |
196 | std::size_t index = 0; | |
197 | std::size_t count = 0; | |
198 | unsigned last_value = 0; | |
199 | (void)last_value; | |
200 | for (const_iterator p = start; p != finish; ++p) | |
201 | { | |
202 | if (p == l) | |
203 | found_l = true; | |
204 | ||
205 | if (p == u) | |
206 | { | |
207 | assert(found_l); | |
208 | found_u = true; | |
209 | } | |
210 | ||
211 | unsigned value = to_int(*p); | |
212 | assert(value >= last_value); | |
213 | last_value = value; | |
214 | ||
215 | if (!found_l) | |
216 | { | |
217 | ++index; | |
218 | assert(to_int(*p) < key); | |
219 | } | |
220 | else if (!found_u) | |
221 | { | |
222 | ++count; | |
223 | assert(to_int(*p) == key); | |
224 | } | |
225 | else | |
226 | assert(to_int(*p) > key); | |
227 | } | |
228 | assert(found_l || l == finish); | |
229 | assert(found_u || u == finish); | |
230 | ||
231 | std::pair<const_iterator, const_iterator> | |
232 | range = searches<Compare>::equal_range(start, finish, key, cmp); | |
233 | assert(range.first == l); | |
234 | assert(range.second == u); | |
235 | ||
236 | bool found = searches<Compare>::binary_search(start, finish, key, cmp); | |
237 | (void)found; | |
238 | assert(found == (u != l)); | |
239 | std::cout << "found " << count << " copies of " << key << " at index " << index << "\n"; | |
240 | } | |
241 | } | |
242 | ||
243 | } | |
244 | ||
245 | int main() | |
246 | { | |
247 | string_vector x; | |
248 | std::cout << "=== testing random-access iterators with <: ===\n"; | |
249 | test_loop(x, no_compare(), 25); | |
250 | std::cout << "=== testing random-access iterators with compare: ===\n"; | |
251 | test_loop(x, cmp(), 25); | |
252 | ||
253 | std::list<mystring> y; | |
254 | std::cout << "=== testing bidirectional iterators with <: ===\n"; | |
255 | test_loop(y, no_compare(), 25); | |
256 | std::cout << "=== testing bidirectional iterators with compare: ===\n"; | |
257 | test_loop(y, cmp(), 25); | |
258 | std::cerr << "******TEST PASSED******\n"; | |
259 | return 0; | |
260 | } |