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