ceph/src/dmclock/support/test/test_indirect_intrusive_heap.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 /*
   5  * Copyright (C) 2016 Red Hat Inc.
   6  */
   7
   8 #include <iostream>
   9 #include <memory>
  10 #include <set>
  11
  12 #include "gtest/gtest.h"
  13
  14 #include "indirect_intrusive_heap.h"
  15
  16
  17 struct Elem {
  18   int data;
  19
  20   crimson::IndIntruHeapData heap_data;
  21   crimson::IndIntruHeapData heap_data_alt;
  22
  23   Elem(int _data) : data(_data) { }
  24
  25   bool operator==(const Elem& other) {
  26     return data == other.data;
  27   }
  28
  29   friend std::ostream& operator<<(std::ostream& out, const Elem& d) {
  30     out << d.data;
  31     return out;
  32   }
  33 };
  34
  35
  36 // sorted low to high
  37 struct ElemCompare {
  38   bool operator()(const Elem& d1, const Elem& d2) const {
  39     return d1.data < d2.data;
  40   }
  41 };
  42
  43
  44 // first all evens precede all odds, then they're sorted high to low
  45 struct ElemCompareAlt {
  46   bool operator()(const Elem& d1, const Elem& d2) {
  47     if (0 == d1.data % 2) {
  48       if (0 == d2.data % 2) {
  49         return d1.data > d2.data;
  50       } else {
  51         return true;
  52       }
  53     } else if (0 == d2.data % 2) {
  54       return false;
  55     } else {
  56       return d1.data > d2.data;
  57     }
  58   }
  59 };
  60
  61
  62 class HeapFixture1: public ::testing::Test {
  63
  64 public:
  65
  66   crimson::IndIntruHeap<std::shared_ptr<Elem>,
  67                         Elem,
  68                         &Elem::heap_data,
  69                         ElemCompare> heap;
  70
  71   std::shared_ptr<Elem> data1, data2, data3, data4, data5, data6, data7;
  72
  73   void SetUp() {
  74     data1 = std::make_shared<Elem>(2);
  75     data2 = std::make_shared<Elem>(99);
  76     data3 = std::make_shared<Elem>(1);
  77     data4 = std::make_shared<Elem>(-5);
  78     data5 = std::make_shared<Elem>(12);
  79     data6 = std::make_shared<Elem>(-12);
  80     data7 = std::make_shared<Elem>(-7);
  81
  82     heap.push(data1);
  83     heap.push(data2);
  84     heap.push(data3);
  85     heap.push(data4);
  86     heap.push(data5);
  87     heap.push(data6);
  88     heap.push(data7);
  89   }
  90
  91   void TearDown() {
  92     // nothing to do
  93   }
  94 }; // class HeapFixture1
  95
  96 TEST(IndIntruHeap, shared_ptr) {
  97   crimson::IndIntruHeap<std::shared_ptr<Elem>,
  98                         Elem,
  99                         &Elem::heap_data,
 100                         ElemCompare> heap;
 101
 102   EXPECT_TRUE(heap.empty());
 103
 104   heap.push(std::make_shared<Elem>(2));
 105
 106   EXPECT_FALSE(heap.empty());
 107
 108   heap.push(std::make_shared<Elem>(99));
 109   heap.push(std::make_shared<Elem>(1));
 110   heap.push(std::make_shared<Elem>(-5));
 111   heap.push(std::make_shared<Elem>(12));
 112   heap.push(std::make_shared<Elem>(-12));
 113   heap.push(std::make_shared<Elem>(-7));
 114
 115   // std::cout << heap << std::endl;
 116
 117   EXPECT_FALSE(heap.empty());
 118
 119   EXPECT_EQ(-12, heap.top().data);
 120   heap.pop();
 121   EXPECT_EQ(-7, heap.top().data);
 122   heap.pop();
 123   EXPECT_EQ(-5, heap.top().data);
 124   heap.pop();
 125   EXPECT_EQ(1, heap.top().data);
 126   heap.pop();
 127   EXPECT_EQ(2, heap.top().data);
 128   heap.pop();
 129   EXPECT_EQ(12, heap.top().data);
 130   heap.pop();
 131   EXPECT_EQ(99, heap.top().data);
 132
 133   EXPECT_FALSE(heap.empty());
 134   heap.pop();
 135   EXPECT_TRUE(heap.empty());
 136 }
 137
 138
 139 TEST(IndIntruHeap, unique_ptr) {
 140   crimson::IndIntruHeap<std::unique_ptr<Elem>,
 141                         Elem,
 142                         &Elem::heap_data,
 143                         ElemCompare> heap;
 144
 145   EXPECT_TRUE(heap.empty());
 146
 147   heap.push(std::unique_ptr<Elem>(new Elem(2)));
 148
 149   EXPECT_FALSE(heap.empty());
 150
 151   heap.push(std::unique_ptr<Elem>(new Elem(99)));
 152   heap.push(std::unique_ptr<Elem>(new Elem(1)));
 153   heap.push(std::unique_ptr<Elem>(new Elem(-5)));
 154   heap.push(std::unique_ptr<Elem>(new Elem(12)));
 155   heap.push(std::unique_ptr<Elem>(new Elem(-12)));
 156   heap.push(std::unique_ptr<Elem>(new Elem(-7)));
 157
 158   EXPECT_FALSE(heap.empty());
 159
 160   EXPECT_EQ(-12, heap.top().data);
 161   heap.pop();
 162   EXPECT_EQ(-7, heap.top().data);
 163   heap.pop();
 164   EXPECT_EQ(-5, heap.top().data);
 165   heap.pop();
 166   EXPECT_EQ(1, heap.top().data);
 167   heap.pop();
 168   EXPECT_EQ(2, heap.top().data);
 169   heap.pop();
 170   EXPECT_EQ(12, heap.top().data);
 171   heap.pop();
 172   EXPECT_EQ(99, heap.top().data);
 173
 174   EXPECT_FALSE(heap.empty());
 175   heap.pop();
 176   EXPECT_TRUE(heap.empty());
 177 }
 178
 179
 180 TEST(IndIntruHeap, regular_ptr) {
 181   crimson::IndIntruHeap<Elem*, Elem, &Elem::heap_data, ElemCompare> heap;
 182
 183   EXPECT_TRUE(heap.empty());
 184
 185   heap.push(new Elem(2));
 186
 187   EXPECT_FALSE(heap.empty());
 188
 189   heap.push(new Elem(99));
 190   heap.push(new Elem(1));
 191   heap.push(new Elem(-5));
 192   heap.push(new Elem(12));
 193   heap.push(new Elem(-12));
 194   heap.push(new Elem(-7));
 195
 196   EXPECT_FALSE(heap.empty());
 197
 198   EXPECT_EQ(-12, heap.top().data);
 199   delete &heap.top();
 200   heap.pop();
 201   EXPECT_EQ(-7, heap.top().data);
 202   delete &heap.top();
 203   heap.pop();
 204   EXPECT_EQ(-5, heap.top().data);
 205   delete &heap.top();
 206   heap.pop();
 207   EXPECT_EQ(1, heap.top().data);
 208   delete &heap.top();
 209   heap.pop();
 210   EXPECT_EQ(2, heap.top().data);
 211   delete &heap.top();
 212   heap.pop();
 213   EXPECT_EQ(12, heap.top().data);
 214   delete &heap.top();
 215   heap.pop();
 216   EXPECT_EQ(99, heap.top().data);
 217
 218   delete &heap.top();
 219
 220   EXPECT_FALSE(heap.empty());
 221   heap.pop();
 222   EXPECT_TRUE(heap.empty());
 223 }
 224
 225
 226 TEST(IndIntruHeap, K_3) {
 227   crimson::IndIntruHeap<std::shared_ptr<Elem>,
 228                         Elem,
 229                         &Elem::heap_data,
 230                         ElemCompare,
 231                         3> heap;
 232
 233   EXPECT_TRUE(heap.empty());
 234
 235   heap.push(std::make_shared<Elem>(2));
 236
 237   EXPECT_FALSE(heap.empty());
 238
 239   heap.push(std::make_shared<Elem>(99));
 240   heap.push(std::make_shared<Elem>(1));
 241   heap.push(std::make_shared<Elem>(-5));
 242   heap.push(std::make_shared<Elem>(12));
 243   heap.push(std::make_shared<Elem>(-12));
 244   heap.push(std::make_shared<Elem>(-7));
 245
 246   // std::cout << heap << std::endl;
 247
 248   EXPECT_FALSE(heap.empty());
 249
 250   EXPECT_EQ(-12, heap.top().data);
 251   heap.pop();
 252   EXPECT_EQ(-7, heap.top().data);
 253   heap.pop();
 254   EXPECT_EQ(-5, heap.top().data);
 255   heap.pop();
 256   EXPECT_EQ(1, heap.top().data);
 257   heap.pop();
 258   EXPECT_EQ(2, heap.top().data);
 259   heap.pop();
 260   EXPECT_EQ(12, heap.top().data);
 261   heap.pop();
 262   EXPECT_EQ(99, heap.top().data);
 263
 264   EXPECT_FALSE(heap.empty());
 265   heap.pop();
 266   EXPECT_TRUE(heap.empty());
 267 }
 268
 269
 270 TEST(IndIntruHeap, K_4) {
 271   crimson::IndIntruHeap<std::shared_ptr<Elem>,
 272                         Elem,
 273                         &Elem::heap_data,
 274                         ElemCompare,
 275                         4> heap;
 276
 277   EXPECT_TRUE(heap.empty());
 278
 279   heap.push(std::make_shared<Elem>(2));
 280
 281   EXPECT_FALSE(heap.empty());
 282
 283   heap.push(std::make_shared<Elem>(99));
 284   heap.push(std::make_shared<Elem>(1));
 285   heap.push(std::make_shared<Elem>(-5));
 286   heap.push(std::make_shared<Elem>(12));
 287   heap.push(std::make_shared<Elem>(-12));
 288   heap.push(std::make_shared<Elem>(-7));
 289
 290   // std::cout << heap << std::endl;
 291
 292   EXPECT_FALSE(heap.empty());
 293
 294   EXPECT_EQ(-12, heap.top().data);
 295   heap.pop();
 296   EXPECT_EQ(-7, heap.top().data);
 297   heap.pop();
 298   EXPECT_EQ(-5, heap.top().data);
 299   heap.pop();
 300   EXPECT_EQ(1, heap.top().data);
 301   heap.pop();
 302   EXPECT_EQ(2, heap.top().data);
 303   heap.pop();
 304   EXPECT_EQ(12, heap.top().data);
 305   heap.pop();
 306   EXPECT_EQ(99, heap.top().data);
 307
 308   EXPECT_FALSE(heap.empty());
 309   heap.pop();
 310   EXPECT_TRUE(heap.empty());
 311 }
 312
 313
 314 TEST(IndIntruHeap, K_10) {
 315   crimson::IndIntruHeap<std::shared_ptr<Elem>,
 316                         Elem,
 317                         &Elem::heap_data,
 318                         ElemCompare,
 319                         10> heap;
 320
 321   EXPECT_TRUE(heap.empty());
 322
 323   heap.push(std::make_shared<Elem>(2));
 324
 325   EXPECT_FALSE(heap.empty());
 326
 327   heap.push(std::make_shared<Elem>(99));
 328   heap.push(std::make_shared<Elem>(1));
 329   heap.push(std::make_shared<Elem>(-5));
 330   heap.push(std::make_shared<Elem>(12));
 331   heap.push(std::make_shared<Elem>(-12));
 332   heap.push(std::make_shared<Elem>(-7));
 333
 334   // std::cout << heap << std::endl;
 335
 336   EXPECT_FALSE(heap.empty());
 337
 338   EXPECT_EQ(-12, heap.top().data);
 339   heap.pop();
 340   EXPECT_EQ(-7, heap.top().data);
 341   heap.pop();
 342   EXPECT_EQ(-5, heap.top().data);
 343   heap.pop();
 344   EXPECT_EQ(1, heap.top().data);
 345   heap.pop();
 346   EXPECT_EQ(2, heap.top().data);
 347   heap.pop();
 348   EXPECT_EQ(12, heap.top().data);
 349   heap.pop();
 350   EXPECT_EQ(99, heap.top().data);
 351
 352   EXPECT_FALSE(heap.empty());
 353   heap.pop();
 354   EXPECT_TRUE(heap.empty());
 355 }
 356
 357
 358 TEST(IndIntruHeap, multi_K) {
 359   crimson::IndIntruHeap<std::shared_ptr<Elem>,
 360                         Elem,
 361                         &Elem::heap_data,
 362                         ElemCompare,
 363                         2> heap2;
 364
 365   crimson::IndIntruHeap<std::shared_ptr<Elem>,
 366                         Elem,
 367                         &Elem::heap_data,
 368                         ElemCompare,
 369                         3> heap3;
 370
 371   crimson::IndIntruHeap<std::shared_ptr<Elem>,
 372                         Elem,
 373                         &Elem::heap_data,
 374                         ElemCompare,
 375                         4> heap4;
 376
 377   crimson::IndIntruHeap<std::shared_ptr<Elem>,
 378                         Elem,
 379                         &Elem::heap_data,
 380                         ElemCompare,
 381                         10> heap10;
 382
 383   // 250 should give us at least 4 levels on all heaps
 384   constexpr size_t count = 250;
 385
 386   std::srand(std::time(0)); // use current time as seed for random generator
 387
 388   // insert same set of random values into the four heaps
 389   for (size_t i = 0; i < count; ++i) {
 390     int value = std::rand() % 201 - 100; // -100...+100
 391     auto data = std::make_shared<Elem>(value);
 392     heap2.push(data);
 393     heap3.push(data);
 394     heap4.push(data);
 395     heap10.push(data);
 396   }
 397
 398   auto bound = std::numeric_limits<decltype(Elem::data)>::min();
 399
 400   for (size_t i = 0; i < count; ++i) {
 401     auto current = heap2.top().data;
 402
 403     EXPECT_GE(current, bound) <<
 404       "we should never go down, only increase or remain the same";
 405     EXPECT_EQ(current, heap3.top().data) <<
 406       "heap1's data and heap3's data should match";
 407     EXPECT_EQ(current, heap4.top().data) <<
 408       "heap1's data and heap4's data should match";
 409     EXPECT_EQ(current, heap10.top().data) <<
 410       "heap1's data and heap10's data should match";
 411
 412     heap2.pop();
 413     heap3.pop();
 414     heap4.pop();
 415     heap10.pop();
 416
 417     bound = current;
 418   }
 419
 420   EXPECT_TRUE(heap2.empty()) << "should be empty after all elements popped";
 421   EXPECT_TRUE(heap3.empty()) << "should be empty after all elements popped";
 422   EXPECT_TRUE(heap4.empty()) << "should be empty after all elements popped";
 423   EXPECT_TRUE(heap10.empty()) << "should be empty after all elements popped";
 424 }
 425
 426
 427 TEST(IndIntruHeap, demote) {
 428   crimson::IndIntruHeap<std::unique_ptr<Elem>,
 429                         Elem,
 430                         &Elem::heap_data,
 431                         ElemCompare> heap;
 432
 433   heap.push(std::unique_ptr<Elem>(new Elem(2)));
 434   heap.push(std::unique_ptr<Elem>(new Elem(99)));
 435   heap.push(std::unique_ptr<Elem>(new Elem(1)));
 436   heap.push(std::unique_ptr<Elem>(new Elem(-5)));
 437   heap.push(std::unique_ptr<Elem>(new Elem(12)));
 438   heap.push(std::unique_ptr<Elem>(new Elem(-12)));
 439   heap.push(std::unique_ptr<Elem>(new Elem(-7)));
 440
 441   heap.top().data = 24;
 442
 443   heap.demote(heap.top());
 444
 445   EXPECT_EQ(-7, heap.top().data);
 446
 447   heap.pop();
 448   heap.pop();
 449   heap.pop();
 450   heap.pop();
 451   heap.pop();
 452
 453   EXPECT_EQ(24, heap.top().data);
 454 }
 455
 456
 457 TEST(IndIntruHeap, demote_not) {
 458   crimson::IndIntruHeap<std::unique_ptr<Elem>,
 459                         Elem,
 460                         &Elem::heap_data,
 461                         ElemCompare> heap;
 462
 463   heap.push(std::unique_ptr<Elem>(new Elem(2)));
 464   heap.push(std::unique_ptr<Elem>(new Elem(99)));
 465   heap.push(std::unique_ptr<Elem>(new Elem(1)));
 466   heap.push(std::unique_ptr<Elem>(new Elem(-5)));
 467   heap.push(std::unique_ptr<Elem>(new Elem(12)));
 468   heap.push(std::unique_ptr<Elem>(new Elem(-12)));
 469   heap.push(std::unique_ptr<Elem>(new Elem(-7)));
 470
 471   heap.top().data = -99;
 472
 473   heap.demote(heap.top());
 474
 475   EXPECT_EQ(-99, heap.top().data);
 476
 477   heap.pop();
 478
 479   EXPECT_EQ(-7, heap.top().data);
 480 }
 481
 482
 483 TEST(IndIntruHeap, promote_and_demote) {
 484   crimson::IndIntruHeap<std::shared_ptr<Elem>,
 485                         Elem,
 486                         &Elem::heap_data,
 487                         ElemCompare> heap;
 488
 489   auto data1 = std::make_shared<Elem>(1);
 490
 491   heap.push(std::make_shared<Elem>(2));
 492   heap.push(std::make_shared<Elem>(99));
 493   heap.push(data1);
 494   heap.push(std::make_shared<Elem>(-5));
 495   heap.push(std::make_shared<Elem>(12));
 496   heap.push(std::make_shared<Elem>(-12));
 497   heap.push(std::make_shared<Elem>(-7));
 498
 499   EXPECT_EQ(-12, heap.top().data);
 500
 501   data1->data = -99;
 502   heap.promote(*data1);
 503
 504   EXPECT_EQ(-99, heap.top().data);
 505
 506   data1->data = 999;
 507   heap.demote(*data1);
 508
 509   EXPECT_EQ(-12, heap.top().data);
 510
 511   data1->data = 9;
 512   heap.promote(*data1);
 513
 514   heap.pop(); // remove -12
 515   heap.pop(); // remove -7
 516   heap.pop(); // remove -5
 517   heap.pop(); // remove 2
 518
 519   EXPECT_EQ(9, heap.top().data);
 520 }
 521
 522
 523 TEST(IndIntruHeap, adjust) {
 524   crimson::IndIntruHeap<std::shared_ptr<Elem>,
 525                         Elem,
 526                         &Elem::heap_data,
 527                         ElemCompare> heap;
 528
 529   auto data1 = std::make_shared<Elem>(1);
 530
 531   heap.push(std::make_shared<Elem>(2));
 532   heap.push(std::make_shared<Elem>(99));
 533   heap.push(data1);
 534   heap.push(std::make_shared<Elem>(-5));
 535   heap.push(std::make_shared<Elem>(12));
 536   heap.push(std::make_shared<Elem>(-12));
 537   heap.push(std::make_shared<Elem>(-7));
 538
 539   // heap.display_sorted(std::cout);
 540
 541   EXPECT_EQ(-12, heap.top().data);
 542
 543   data1->data = 999;
 544   heap.adjust(*data1);
 545
 546   EXPECT_EQ(-12, heap.top().data);
 547
 548   data1->data = -99;
 549   heap.adjust(*data1);
 550
 551   EXPECT_EQ(-99, heap.top().data);
 552
 553   data1->data = 9;
 554   heap.adjust(*data1);
 555
 556   EXPECT_EQ(-12, heap.top().data);
 557
 558   heap.pop(); // remove -12
 559   heap.pop(); // remove -7
 560   heap.pop(); // remove -5
 561   heap.pop(); // remove 2
 562
 563   EXPECT_EQ(9, heap.top().data);
 564 }
 565
 566
 567 TEST(IndIntruHeap, remove_careful) {
 568   // here we test whether a common mistake in implementing remove is
 569   // done; if after we remove an item and move the last element of the
 570   // heap to the position of the removed element, we need to sift it
 571   // rather than sift_down it.
 572
 573   crimson::IndIntruHeap<std::shared_ptr<Elem>,
 574                         Elem,
 575                         &Elem::heap_data,
 576                         ElemCompare,
 577                         2> heap;
 578
 579   heap.push(std::make_shared<Elem>(0));
 580   heap.push(std::make_shared<Elem>(10));
 581   heap.push(std::make_shared<Elem>(100));
 582   heap.push(std::make_shared<Elem>(20));
 583   heap.push(std::make_shared<Elem>(30));
 584   heap.push(std::make_shared<Elem>(200));
 585   heap.push(std::make_shared<Elem>(300));
 586   heap.push(std::make_shared<Elem>(40));
 587
 588   auto k = heap.find(Elem(200));
 589   EXPECT_NE(heap.end(), k) <<
 590     "we should have found an element with the value 200, which we'll remove";
 591   heap.remove(k);
 592
 593   auto i = heap.cbegin();
 594   EXPECT_EQ(0, i->data);
 595   ++i;
 596   EXPECT_EQ(10, i->data);
 597   ++i;
 598   EXPECT_EQ(40, i->data) <<
 599     "this needs to be 40 or there's a mistake in implementation";
 600   ++i;
 601   EXPECT_EQ(20, i->data);
 602   ++i;
 603   EXPECT_EQ(30, i->data);
 604   ++i;
 605   EXPECT_EQ(100, i->data) <<
 606     "this needs to be 100 or there's a mistake in implementation";
 607 }
 608
 609
 610 TEST_F(HeapFixture1, shared_data) {
 611
 612   crimson::IndIntruHeap<std::shared_ptr<Elem>,Elem,&Elem::heap_data_alt,ElemCompareAlt> heap2;
 613
 614   heap2.push(data1);
 615   heap2.push(data2);
 616   heap2.push(data3);
 617   heap2.push(data4);
 618   heap2.push(data5);
 619   heap2.push(data6);
 620   heap2.push(data7);
 621
 622   data3->data = 32;
 623   heap.adjust(*data3);
 624   heap2.adjust(*data3);
 625
 626   EXPECT_EQ(-12, heap.top().data);
 627   heap.pop();
 628   EXPECT_EQ(-7, heap.top().data);
 629   heap.pop();
 630   EXPECT_EQ(-5, heap.top().data);
 631   heap.pop();
 632   EXPECT_EQ(2, heap.top().data);
 633   heap.pop();
 634   EXPECT_EQ(12, heap.top().data);
 635   heap.pop();
 636   EXPECT_EQ(32, heap.top().data);
 637   heap.pop();
 638   EXPECT_EQ(99, heap.top().data);
 639
 640   EXPECT_EQ(32, heap2.top().data);
 641   heap2.pop();
 642   EXPECT_EQ(12, heap2.top().data);
 643   heap2.pop();
 644   EXPECT_EQ(2, heap2.top().data);
 645   heap2.pop();
 646   EXPECT_EQ(-12, heap2.top().data);
 647   heap2.pop();
 648   EXPECT_EQ(99, heap2.top().data);
 649   heap2.pop();
 650   EXPECT_EQ(-5, heap2.top().data);
 651   heap2.pop();
 652   EXPECT_EQ(-7, heap2.top().data);
 653 }
 654
 655
 656 TEST_F(HeapFixture1, iterator_basics) {
 657   {
 658     uint count = 0;
 659     for(auto i = heap.begin(); i != heap.end(); ++i) {
 660       ++count;
 661     }
 662
 663     EXPECT_EQ(7u, count) << "count should be 7";
 664   }
 665
 666   auto i1 = heap.begin();
 667
 668   EXPECT_EQ(-12, i1->data) <<
 669     "first member with * operator must be smallest";
 670
 671   EXPECT_EQ(-12, (*i1).data) <<
 672     "first member with -> operator must be smallest";
 673
 674   Elem& e1 = *i1;
 675   EXPECT_EQ(-12, e1.data) <<
 676     "first member with -> operator must be smallest";
 677
 678   {
 679     std::set<int> values;
 680     values.insert(2);
 681     values.insert(99);
 682     values.insert(1);
 683     values.insert(-5);
 684     values.insert(12);
 685     values.insert(-12);
 686     values.insert(-7);
 687
 688     for(auto i = heap.begin(); i != heap.end(); ++i) {
 689       auto v = *i;
 690       EXPECT_NE(values.end(), values.find(v.data)) <<
 691         "value in heap must be part of original set";
 692       values.erase(v.data);
 693     }
 694     EXPECT_EQ(0u, values.size()) << "all values must have been seen";
 695   }
 696 }
 697
 698
 699 TEST_F(HeapFixture1, const_iterator_basics) {
 700   const auto& cheap = heap;
 701
 702   {
 703     uint count = 0;
 704     for(auto i = cheap.cbegin(); i != cheap.cend(); ++i) {
 705       ++count;
 706     }
 707
 708     EXPECT_EQ(7u, count) << "count should be 7";
 709   }
 710
 711   auto i1 = heap.cbegin();
 712
 713   EXPECT_EQ(-12, i1->data) <<
 714     "first member with * operator must be smallest";
 715
 716   EXPECT_EQ(-12, (*i1).data) <<
 717     "first member with -> operator must be smallest";
 718
 719   const Elem& e1 = *i1;
 720   EXPECT_EQ(-12, e1.data) <<
 721     "first member with -> operator must be smallest";
 722
 723   {
 724     std::set<int> values;
 725     values.insert(2);
 726     values.insert(99);
 727     values.insert(1);
 728     values.insert(-5);
 729     values.insert(12);
 730     values.insert(-12);
 731     values.insert(-7);
 732
 733     for(auto i = heap.cbegin(); i != heap.cend(); ++i) {
 734       auto v = *i;
 735       EXPECT_NE(values.end(), values.find(v.data)) <<
 736         "value in heap must be part of original set";
 737       values.erase(v.data);
 738     }
 739     EXPECT_EQ(0u, values.size()) << "all values must have been seen";
 740   }
 741 }
 742
 743
 744 TEST_F(HeapFixture1, iterator_find_rfind) {
 745   {
 746     auto it1 = heap.find(data7);
 747     EXPECT_NE(heap.end(), it1) <<
 748       "find by indirection for included element should succeed";
 749     EXPECT_EQ(-7, it1->data) <<
 750       "find by indirection for included element should result in right value";
 751
 752     auto fake_data = std::make_shared<Elem>(-7);
 753     auto it2 = heap.find(fake_data);
 754     EXPECT_EQ(heap.end(), it2) <<
 755       "find by indirection for not included element should fail";
 756   }
 757
 758   {
 759     auto it1 = heap.find(Elem(-7));
 760     EXPECT_NE(heap.end(), it1) <<
 761       "find by value for included element should succeed";
 762     EXPECT_EQ(-7, it1->data) <<
 763       "find by value for included element should result in right value";
 764
 765     auto it2 = heap.find(Elem(7));
 766     EXPECT_EQ(heap.end(), it2) <<
 767       "find by value for not included element should fail";
 768   }
 769
 770   {
 771     auto it1 = heap.rfind(data7);
 772     EXPECT_NE(heap.end(), it1) <<
 773       "reverse find by indirecton for included element should succeed";
 774     EXPECT_EQ(-7, it1->data) <<
 775       "reverse find by indirection for included element should result "
 776       "in right value";
 777
 778     auto fake_data = std::make_shared<Elem>(-7);
 779     auto it2 = heap.rfind(fake_data);
 780     EXPECT_EQ(heap.end(), it2) <<
 781       "reverse find by indirection for not included element should fail";
 782   }
 783
 784   {
 785     auto it1 = heap.rfind(Elem(-7));
 786     EXPECT_NE(heap.end(), it1) <<
 787       "reverse find by value for included element should succeed";
 788     EXPECT_EQ(-7, it1->data) <<
 789       "reverse find by value for included element should result "
 790       "in right value";
 791
 792     auto it2 = heap.rfind(Elem(7));
 793     EXPECT_EQ(heap.end(), it2) <<
 794       "reverse find by value for not included element should fail";
 795   }
 796 }
 797
 798
 799 TEST_F(HeapFixture1, const_iterator_find_rfind) {
 800   const auto& c_heap = heap;
 801
 802   {
 803     auto it1 = c_heap.find(data7);
 804     EXPECT_NE(c_heap.cend(), it1) <<
 805       "find by indirection for included element should succeed";
 806     EXPECT_EQ(-7, it1->data) <<
 807       "find by indirection for included element should result in right value";
 808
 809     auto fake_data = std::make_shared<Elem>(-7);
 810     auto it2 = c_heap.find(fake_data);
 811     EXPECT_EQ(c_heap.cend(), it2) <<
 812       "find by indirection for not included element should fail";
 813   }
 814
 815   {
 816     auto it1 = c_heap.find(Elem(-7));
 817     EXPECT_NE(c_heap.cend(), it1) <<
 818       "find by value for included element should succeed";
 819     EXPECT_EQ(-7, it1->data) <<
 820       "find by value for included element should result in right value";
 821
 822     auto it2 = c_heap.find(Elem(7));
 823     EXPECT_EQ(c_heap.cend(), it2) <<
 824       "find by value for not included element should fail";
 825   }
 826
 827   {
 828     auto it1 = c_heap.rfind(data7);
 829     EXPECT_NE(c_heap.cend(), it1) <<
 830       "reverse find by indirecton for included element should succeed";
 831     EXPECT_EQ(-7, it1->data) <<
 832       "reverse find by indirection for included element should result "
 833       "in right value";
 834
 835     auto fake_data = std::make_shared<Elem>(-7);
 836     auto it2 = c_heap.rfind(fake_data);
 837     EXPECT_EQ(c_heap.cend(), it2) <<
 838       "reverse find by indirection for not included element should fail";
 839   }
 840
 841   {
 842     auto it1 = c_heap.rfind(Elem(-7));
 843     EXPECT_NE(c_heap.cend(), it1) <<
 844       "reverse find by value for included element should succeed";
 845     EXPECT_EQ(-7, it1->data) <<
 846       "reverse find by value for included element should result "
 847       "in right value";
 848
 849     auto it2 = c_heap.rfind(Elem(7));
 850     EXPECT_EQ(c_heap.cend(), it2) <<
 851       "reverse find by value for not included element should fail";
 852   }
 853 }
 854
 855
 856 TEST_F(HeapFixture1, iterator_remove) {
 857   auto it1 = heap.find(data7);
 858   EXPECT_NE(heap.end(), it1) << "find for included element should succeed";
 859
 860   heap.remove(it1);
 861
 862   auto it2 = heap.find(data7);
 863   EXPECT_EQ(heap.end(), it2) << "find for removed element should fail";
 864
 865   for (auto it3 = heap.begin(); it3 != heap.end(); ++it3) {
 866     EXPECT_NE(-7, it3->data) <<
 867       "iterating through heap should not find removed value";
 868   }
 869
 870   // move through heap without -7
 871   EXPECT_EQ(-12, heap.top().data);
 872   heap.pop();
 873   EXPECT_EQ(-5, heap.top().data);
 874   heap.pop();
 875   EXPECT_EQ(1, heap.top().data);
 876   heap.pop();
 877   EXPECT_EQ(2, heap.top().data);
 878   heap.pop();
 879   EXPECT_EQ(12, heap.top().data);
 880   heap.pop();
 881   EXPECT_EQ(99, heap.top().data);
 882   heap.pop();
 883 }
 884
 885
 886 TEST_F(HeapFixture1, four_tops) {
 887   Elem& top1 = heap.top();
 888   EXPECT_EQ(-12, top1.data);
 889
 890   const Elem& top2 = heap.top();
 891   EXPECT_EQ(-12, top2.data);
 892
 893   std::shared_ptr<Elem> top3 = heap.top_ind();
 894   EXPECT_EQ(-12, top3->data);
 895
 896   const std::shared_ptr<Elem> top4 = heap.top_ind();
 897   EXPECT_EQ(-12, top4->data);
 898
 899   const auto& c_heap = heap;
 900
 901   const Elem& top5 = c_heap.top();
 902   EXPECT_EQ(-12, top5.data);
 903
 904   const std::shared_ptr<Elem> top6 = c_heap.top_ind();
 905   EXPECT_EQ(-12, top6->data);
 906 }
 907
 908
 909 TEST_F(HeapFixture1, display_sorted) {
 910   std::stringstream ss;
 911
 912   heap.display_sorted(ss);
 913
 914   std::string s = ss.str();
 915
 916   EXPECT_GT(s.length(), 0u);
 917
 918   auto negseven = s.find("-7");
 919   EXPECT_NE(negseven, std::string::npos);
 920
 921   auto ninetynine = s.find("99");
 922   EXPECT_NE(ninetynine, std::string::npos);
 923
 924   // index of -7 should be less than index of 99
 925   EXPECT_LT(negseven, ninetynine);
 926
 927 #if 0
 928   std::cout << s << std::endl;
 929 #endif
 930 }