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)
12 #include <stdlib.h> // for rand(). Would use cstdlib but VC6.4 doesn't put it in std::
15 #include <boost/detail/binary_search.hpp>
16 #include <boost/detail/workaround.hpp>
19 #if defined(__SGI_STL_PORT) ? defined(__SGI_STL_OWN_IOSTREAMS) : (!defined(__GNUC__) || __GNUC__ > 2)
31 // In order to get ADL to find the comparison operators defined below, they have
32 struct mystring
: std::string
34 typedef std::string base
;
36 mystring(std::string
const& x
)
40 typedef std::vector
<mystring
> string_vector
;
42 const std::size_t sequence_length
= 1000;
44 unsigned random_number()
46 return static_cast<unsigned>(::rand()) % sequence_length
;
52 unfreezer(std::ostrstream
& s
) : m_stream(s
) {}
53 ~unfreezer() { m_stream
.freeze(false); }
55 std::ostrstream
& m_stream
;
60 void push_back_random_number_string(T
& seq
)
62 unsigned value
= random_number();
63 # if defined(__SGI_STL_PORT) ? defined(__SGI_STL_OWN_IOSTREAMS) : (!defined(__GNUC__) || __GNUC__ > 2)
66 seq
.push_back(s
.str());
69 auto unfreezer
unfreeze(s
);
70 s
<< value
<< char(0);
71 seq
.push_back(std::string(s
.str()));
75 inline unsigned to_int(unsigned x
) { return x
; }
76 inline unsigned to_int(const std::string
& x
) { return atoi(x
.c_str()); }
80 template <class A1
, class A2
>
81 inline bool operator()(const A1
& a1
, const A2
& a2
) const
83 return to_int(a1
) < to_int(a2
);
87 inline bool operator<(const mystring
& x
, const unsigned y
)
92 inline bool operator<(const unsigned y
, const mystring
& x
)
98 void sort_by_value(T
& x
);
101 void sort_by_value_(T
& v
, long)
103 std::sort(v
.begin(), v
.end(), cmp());
107 void random_sorted_sequence(T
& seq
)
110 for (std::size_t i
= 0; i
< sequence_length
; ++i
)
112 push_back_random_number_string(seq
);
117 template <class T
, class A
>
118 void sort_by_value_(std::list
<T
,A
>& l
, int)
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()
123 seq
.reserve(sequence_length
);
124 std::copy(l
.begin(), l
.end(), std::back_inserter(seq
));
126 std::copy(seq
.begin(), seq
.end(), l
.begin());
133 void sort_by_value(T
& x
)
135 (sort_by_value_
)(x
, 1);
138 // A way to select the comparisons with/without a Compare parameter for testing.
139 template <class Compare
> struct searches
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
); }
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
); }
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
); }
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
); }
158 struct no_compare
{};
160 template <> struct searches
<no_compare
>
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
); }
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
); }
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
); }
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
); }
179 template <class Sequence
, class Compare
>
180 void test_loop(Sequence
& x
, Compare cmp
, unsigned long test_count
)
182 typedef typename
Sequence::const_iterator const_iterator
;
184 for (unsigned long i
= 0; i
< test_count
; ++i
)
186 random_sorted_sequence(x
);
187 const const_iterator start
= x
.begin();
188 const const_iterator finish
= x
.end();
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
);
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 for (const_iterator p
= start
; p
!= finish
; ++p
)
210 unsigned value
= to_int(*p
);
211 assert(value
>= last_value
);
217 assert(to_int(*p
) < key
);
222 assert(to_int(*p
) == key
);
225 assert(to_int(*p
) > key
);
227 assert(found_l
|| l
== finish
);
228 assert(found_u
|| u
== finish
);
230 std::pair
<const_iterator
, const_iterator
>
231 range
= searches
<Compare
>::equal_range(start
, finish
, key
, cmp
);
232 assert(range
.first
== l
);
233 assert(range
.second
== u
);
235 bool found
= searches
<Compare
>::binary_search(start
, finish
, key
, cmp
);
236 assert(found
== (u
!= l
));
237 std::cout
<< "found " << count
<< " copies of " << key
<< " at index " << index
<< "\n";
246 std::cout
<< "=== testing random-access iterators with <: ===\n";
247 test_loop(x
, no_compare(), 25);
248 std::cout
<< "=== testing random-access iterators with compare: ===\n";
249 test_loop(x
, cmp(), 25);
251 std::list
<mystring
> y
;
252 std::cout
<< "=== testing bidirectional iterators with <: ===\n";
253 test_loop(y
, no_compare(), 25);
254 std::cout
<< "=== testing bidirectional iterators with compare: ===\n";
255 test_loop(y
, cmp(), 25);
256 std::cerr
<< "******TEST PASSED******\n";