ceph/src/boost/libs/heap/test/common_heap_tests.hpp

   1 /*=============================================================================
   2     Copyright (c) 2010 Tim Blechmann
   3
   4     Use, modification and distribution is subject to the Boost Software
   5     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6     http://www.boost.org/LICENSE_1_0.txt)
   7 =============================================================================*/
   8
   9 #ifndef COMMON_HEAP_TESTS_HPP_INCLUDED
  10 #define COMMON_HEAP_TESTS_HPP_INCLUDED
  11
  12 #include <algorithm>
  13 #include <vector>
  14
  15 #include <boost/concept/assert.hpp>
  16 #include <boost/concept_archetype.hpp>
  17 #include <boost/shared_ptr.hpp>
  18
  19 #include <boost/heap/heap_concepts.hpp>
  20
  21
  22 typedef boost::default_constructible_archetype<
  23         boost::less_than_comparable_archetype<
  24         boost::copy_constructible_archetype<
  25         boost::assignable_archetype<
  26         > > > > test_value_type;
  27
  28
  29 typedef std::vector<int> test_data;
  30 const int test_size = 32;
  31
  32 struct dummy_run
  33 {
  34     static void run(void)
  35     {}
  36 };
  37
  38
  39 test_data make_test_data(int size, int offset = 0, int strive = 1)
  40 {
  41     test_data ret;
  42
  43     for (int i = 0; i != size; ++i)
  44         ret.push_back(i * strive + offset);
  45     return ret;
  46 }
  47
  48
  49 template <typename pri_queue, typename data_container>
  50 void check_q(pri_queue & q, data_container const & expected)
  51 {
  52     BOOST_REQUIRE_EQUAL(q.size(), expected.size());
  53
  54     for (unsigned int i = 0; i != expected.size(); ++i)
  55     {
  56         BOOST_REQUIRE_EQUAL(q.size(), expected.size() - i);
  57         BOOST_REQUIRE_EQUAL(q.top(), expected[expected.size()-1-i]);
  58         q.pop();
  59     }
  60
  61     BOOST_REQUIRE(q.empty());
  62 }
  63
  64
  65 template <typename pri_queue, typename data_container>
  66 void fill_q(pri_queue & q, data_container const & data)
  67 {
  68     for (unsigned int i = 0; i != data.size(); ++i)
  69         q.push(data[i]);
  70 }
  71
  72 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
  73 template <typename pri_queue, typename data_container>
  74 void fill_emplace_q(pri_queue & q, data_container const & data)
  75 {
  76     for (unsigned int i = 0; i != data.size(); ++i) {
  77         typename pri_queue::value_type value = data[i];
  78         q.emplace(std::move(value));
  79     }
  80 }
  81 #endif
  82
  83 template <typename pri_queue>
  84 void pri_queue_test_sequential_push(void)
  85 {
  86     for (int i = 0; i != test_size; ++i)
  87     {
  88         pri_queue q;
  89         test_data data = make_test_data(i);
  90         fill_q(q, data);
  91         check_q(q, data);
  92     }
  93 }
  94
  95 template <typename pri_queue>
  96 void pri_queue_test_sequential_reverse_push(void)
  97 {
  98     for (int i = 0; i != test_size; ++i)
  99     {
 100         pri_queue q;
 101         test_data data = make_test_data(i);
 102         std::reverse(data.begin(), data.end());
 103         fill_q(q, data);
 104         std::reverse(data.begin(), data.end());
 105         check_q(q, data);
 106     }
 107 }
 108
 109 template <typename pri_queue>
 110 void pri_queue_test_emplace(void)
 111 {
 112 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 113     for (int i = 0; i != test_size; ++i)
 114     {
 115         pri_queue q;
 116         test_data data = make_test_data(i);
 117         std::reverse(data.begin(), data.end());
 118         fill_emplace_q(q, data);
 119         std::reverse(data.begin(), data.end());
 120         check_q(q, data);
 121     }
 122 #endif
 123 }
 124
 125
 126 template <typename pri_queue>
 127 void pri_queue_test_random_push(void)
 128 {
 129     for (int i = 0; i != test_size; ++i)
 130     {
 131         pri_queue q;
 132         test_data data = make_test_data(i);
 133
 134         test_data shuffled (data);
 135         std::random_shuffle(shuffled.begin(), shuffled.end());
 136
 137         fill_q(q, shuffled);
 138
 139         check_q(q, data);
 140     }
 141 }
 142
 143 template <typename pri_queue>
 144 void pri_queue_test_copyconstructor(void)
 145 {
 146     for (int i = 0; i != test_size; ++i)
 147     {
 148         pri_queue q;
 149         test_data data = make_test_data(i);
 150         fill_q(q, data);
 151
 152         pri_queue r(q);
 153
 154         check_q(r, data);
 155     }
 156 }
 157
 158 template <typename pri_queue>
 159 void pri_queue_test_assignment(void)
 160 {
 161     for (int i = 0; i != test_size; ++i)
 162     {
 163         pri_queue q;
 164         test_data data = make_test_data(i);
 165         fill_q(q, data);
 166
 167         pri_queue r;
 168         r = q;
 169
 170         check_q(r, data);
 171     }
 172 }
 173
 174 template <typename pri_queue>
 175 void pri_queue_test_moveconstructor(void)
 176 {
 177 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
 178     pri_queue q;
 179     test_data data = make_test_data(test_size);
 180     fill_q(q, data);
 181
 182     pri_queue r(std::move(q));
 183
 184     check_q(r, data);
 185     BOOST_REQUIRE(q.empty());
 186 #endif
 187 }
 188
 189 template <typename pri_queue>
 190 void pri_queue_test_move_assignment(void)
 191 {
 192 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
 193     pri_queue q;
 194     test_data data = make_test_data(test_size);
 195     fill_q(q, data);
 196
 197     pri_queue r;
 198     r = std::move(q);
 199
 200     check_q(r, data);
 201     BOOST_REQUIRE(q.empty());
 202 #endif
 203 }
 204
 205
 206 template <typename pri_queue>
 207 void pri_queue_test_swap(void)
 208 {
 209     for (int i = 0; i != test_size; ++i)
 210     {
 211         pri_queue q;
 212         test_data data = make_test_data(i);
 213         test_data shuffled (data);
 214         std::random_shuffle(shuffled.begin(), shuffled.end());
 215         fill_q(q, shuffled);
 216
 217         pri_queue r;
 218
 219         q.swap(r);
 220         check_q(r, data);
 221         BOOST_REQUIRE(q.empty());
 222     }
 223 }
 224
 225
 226 template <typename pri_queue>
 227 void pri_queue_test_iterators(void)
 228 {
 229     for (int i = 0; i != test_size; ++i) {
 230         test_data data = make_test_data(test_size);
 231         test_data shuffled (data);
 232         std::random_shuffle(shuffled.begin(), shuffled.end());
 233         pri_queue q;
 234         BOOST_REQUIRE(q.begin() == q.end());
 235         fill_q(q, shuffled);
 236
 237         for (unsigned long j = 0; j != data.size(); ++j)
 238             BOOST_REQUIRE(std::find(q.begin(), q.end(), data[j]) != q.end());
 239
 240         for (unsigned long j = 0; j != data.size(); ++j)
 241             BOOST_REQUIRE(std::find(q.begin(), q.end(), data[j] + data.size()) == q.end());
 242
 243         test_data data_from_queue(q.begin(), q.end());
 244         std::sort(data_from_queue.begin(), data_from_queue.end());
 245
 246         BOOST_REQUIRE(data == data_from_queue);
 247
 248         for (unsigned long j = 0; j != data.size(); ++j) {
 249             BOOST_REQUIRE_EQUAL((long)std::distance(q.begin(), q.end()), (long)(data.size() - j));
 250             q.pop();
 251         }
 252     }
 253 }
 254
 255 template <typename pri_queue>
 256 void pri_queue_test_ordered_iterators(void)
 257 {
 258     for (int i = 0; i != test_size; ++i) {
 259         test_data data = make_test_data(i);
 260         test_data shuffled (data);
 261         std::random_shuffle(shuffled.begin(), shuffled.end());
 262         pri_queue q;
 263         BOOST_REQUIRE(q.ordered_begin() == q.ordered_end());
 264         fill_q(q, shuffled);
 265
 266         test_data data_from_queue(q.ordered_begin(), q.ordered_end());
 267         std::reverse(data_from_queue.begin(), data_from_queue.end());
 268         BOOST_REQUIRE(data == data_from_queue);
 269
 270         for (unsigned long j = 0; j != data.size(); ++j)
 271             BOOST_REQUIRE(std::find(q.ordered_begin(), q.ordered_end(), data[j]) != q.ordered_end());
 272
 273         for (unsigned long j = 0; j != data.size(); ++j)
 274             BOOST_REQUIRE(std::find(q.ordered_begin(), q.ordered_end(), data[j] + data.size()) == q.ordered_end());
 275
 276         for (unsigned long j = 0; j != data.size(); ++j) {
 277             BOOST_REQUIRE_EQUAL((long)std::distance(q.begin(), q.end()), (long)(data.size() - j));
 278             q.pop();
 279         }
 280     }
 281 }
 282
 283
 284 template <typename pri_queue>
 285 void pri_queue_test_equality(void)
 286 {
 287     for (int i = 0; i != test_size; ++i)
 288     {
 289         pri_queue q, r;
 290         test_data data = make_test_data(i);
 291         fill_q(q, data);
 292         std::reverse(data.begin(), data.end());
 293         fill_q(r, data);
 294
 295         BOOST_REQUIRE(r == q);
 296     }
 297 }
 298
 299 template <typename pri_queue>
 300 void pri_queue_test_inequality(void)
 301 {
 302     for (int i = 1; i != test_size; ++i)
 303     {
 304         pri_queue q, r;
 305         test_data data = make_test_data(i);
 306         fill_q(q, data);
 307         data[0] = data.back() + 1;
 308         fill_q(r, data);
 309
 310         BOOST_REQUIRE(r != q);
 311     }
 312 }
 313
 314 template <typename pri_queue>
 315 void pri_queue_test_less(void)
 316 {
 317     for (int i = 1; i != test_size; ++i)
 318     {
 319         pri_queue q, r;
 320         test_data data = make_test_data(i);
 321         test_data r_data(data);
 322         r_data.pop_back();
 323
 324         fill_q(q, data);
 325         fill_q(r, r_data);
 326
 327         BOOST_REQUIRE(r < q);
 328     }
 329
 330     for (int i = 1; i != test_size; ++i)
 331     {
 332         pri_queue q, r;
 333         test_data data = make_test_data(i);
 334         test_data r_data(data);
 335         data.push_back(data.back() + 1);
 336
 337         fill_q(q, data);
 338         fill_q(r, r_data);
 339
 340         BOOST_REQUIRE(r < q);
 341     }
 342
 343     for (int i = 1; i != test_size; ++i)
 344     {
 345         pri_queue q, r;
 346         test_data data = make_test_data(i);
 347         test_data r_data(data);
 348
 349         data.back() += 1;
 350
 351         fill_q(q, data);
 352         fill_q(r, r_data);
 353
 354         BOOST_REQUIRE(r < q);
 355     }
 356
 357     for (int i = 1; i != test_size; ++i)
 358     {
 359         pri_queue q, r;
 360         test_data data = make_test_data(i);
 361         test_data r_data(data);
 362
 363         r_data.front() -= 1;
 364
 365         fill_q(q, data);
 366         fill_q(r, r_data);
 367
 368         BOOST_REQUIRE(r < q);
 369     }
 370
 371 }
 372
 373 template <typename pri_queue>
 374 void pri_queue_test_clear(void)
 375 {
 376     for (int i = 0; i != test_size; ++i)
 377     {
 378         pri_queue q;
 379         test_data data = make_test_data(i);
 380         fill_q(q, data);
 381
 382         q.clear();
 383         BOOST_REQUIRE(q.size() == 0);
 384         BOOST_REQUIRE(q.empty());
 385     }
 386 }
 387
 388
 389 template <typename pri_queue>
 390 void run_concept_check(void)
 391 {
 392     BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<pri_queue>));
 393 }
 394
 395 template <typename pri_queue>
 396 void run_common_heap_tests(void)
 397 {
 398     pri_queue_test_sequential_push<pri_queue>();
 399     pri_queue_test_sequential_reverse_push<pri_queue>();
 400     pri_queue_test_random_push<pri_queue>();
 401     pri_queue_test_equality<pri_queue>();
 402     pri_queue_test_inequality<pri_queue>();
 403     pri_queue_test_less<pri_queue>();
 404     pri_queue_test_clear<pri_queue>();
 405
 406     pri_queue_test_emplace<pri_queue>();
 407 }
 408
 409 template <typename pri_queue>
 410 void run_iterator_heap_tests(void)
 411 {
 412     pri_queue_test_iterators<pri_queue>();
 413 }
 414
 415
 416 template <typename pri_queue>
 417 void run_copyable_heap_tests(void)
 418 {
 419     pri_queue_test_copyconstructor <pri_queue>();
 420     pri_queue_test_assignment<pri_queue>();
 421     pri_queue_test_swap<pri_queue>();
 422 }
 423
 424
 425 template <typename pri_queue>
 426 void run_moveable_heap_tests(void)
 427 {
 428     pri_queue_test_moveconstructor <pri_queue>();
 429     pri_queue_test_move_assignment <pri_queue>();
 430 }
 431
 432
 433 template <typename pri_queue>
 434 void run_reserve_heap_tests(void)
 435 {
 436     test_data data = make_test_data(test_size);
 437     pri_queue q;
 438     q.reserve(6);
 439     fill_q(q, data);
 440
 441     check_q(q, data);
 442 }
 443
 444 template <typename pri_queue>
 445 void run_leak_check_test(void)
 446 {
 447     pri_queue q;
 448     q.push(boost::shared_ptr<int>(new int(0)));
 449 }
 450
 451
 452 struct less_with_T
 453 {
 454     typedef int T;
 455     bool operator()(const int& a, const int& b) const
 456     {
 457         return a < b;
 458     }
 459 };
 460
 461
 462 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 463
 464 class thing {
 465 public:
 466     thing( int a_, int b_, int c_ ) : a(a_), b(b_), c(c_) {}
 467 public:
 468     int a;
 469     int b;
 470     int c;
 471 };
 472
 473 class cmpthings {
 474 public:
 475     bool operator() ( const thing& lhs, const thing& rhs ) const  {
 476         return lhs.a > rhs.a;
 477     }
 478     bool operator() ( const thing& lhs, const thing& rhs ) {
 479         return lhs.a > rhs.a;
 480     }
 481 };
 482
 483 #define RUN_EMPLACE_TEST(HEAP_TYPE)                                     \
 484     do {                                                                \
 485         cmpthings ord;                                                  \
 486         boost::heap::HEAP_TYPE<thing, boost::heap::compare<cmpthings> > vpq(ord); \
 487         vpq.emplace(5, 6, 7);                                           \
 488         boost::heap::HEAP_TYPE<thing, boost::heap::compare<cmpthings>, boost::heap::stable<true> > vpq2(ord); \
 489         vpq2.emplace(5, 6, 7);                                          \
 490     } while(0);
 491
 492 #else
 493 #define RUN_EMPLACE_TEST(HEAP_TYPE)
 494 #endif
 495
 496
 497 #endif // COMMON_HEAP_TESTS_HPP_INCLUDED