ceph/src/boost/libs/detail/test/binary_search_test.cpp

   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         for (const_iterator p = start; p != finish; ++p)
 200         {
 201             if (p == l)
 202                 found_l = true;
 203
 204             if (p == u)
 205             {
 206                 assert(found_l);
 207                 found_u = true;
 208             }
 209
 210             unsigned value = to_int(*p);
 211             assert(value >= last_value);
 212             last_value = value;
 213
 214             if (!found_l)
 215             {
 216                 ++index;
 217                 assert(to_int(*p) < key);
 218             }
 219             else if (!found_u)
 220             {
 221                 ++count;
 222                 assert(to_int(*p) == key);
 223             }
 224             else
 225                 assert(to_int(*p) > key);
 226         }
 227         assert(found_l || l == finish);
 228         assert(found_u || u == finish);
 229
 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);
 234
 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";
 238     }
 239 }
 240
 241 }
 242
 243 int main()
 244 {
 245     string_vector x;
 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);
 250
 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";
 257     return 0;
 258 }