1 /********************* */ 2 /*! \file binary_heap_black.h 3 ** \verbatim 4 ** Top contributors (to current version): 5 ** Morgan Deters, Andres Noetzli 6 ** This file is part of the CVC4 project. 7 ** Copyright (c) 2009-2019 by the authors listed in the file AUTHORS 8 ** in the top-level source directory) and their institutional affiliations. 9 ** All rights reserved. See the file COPYING in the top-level source 10 ** directory for licensing information.\endverbatim 11 ** 12 ** \brief Black box testing of CVC4::BinaryHeap 13 ** 14 ** Black box testing of CVC4::BinaryHeap. 15 **/ 16 17 #include <cxxtest/TestSuite.h> 18 19 #include <iostream> 20 #include <sstream> 21 22 #include "util/bin_heap.h" 23 24 using namespace CVC4; 25 using namespace std; 26 27 class BinaryHeapBlack : public CxxTest::TestSuite { 28 public: setUp()29 void setUp() override {} 30 tearDown()31 void tearDown() override {} 32 33 /** 34 * Test a a series of simple heaps (push a few then pop all then do others). 35 * Done as a series to test if the heap structure falls into a bad state 36 * after prolonged use. 37 */ testHeapSeries()38 void testHeapSeries() 39 { 40 BinaryHeap<int> heap; 41 42 // First test a heap of 1 element 43 TS_ASSERT_EQUALS(heap.size(), 0u); 44 TS_ASSERT(heap.empty()); 45 #ifdef CVC4_ASSERTIONS 46 TS_ASSERT_THROWS_ANYTHING(heap.top()); 47 TS_ASSERT_THROWS_ANYTHING(heap.pop()); 48 #endif /* CVC4_ASSERTIONS */ 49 TS_ASSERT_EQUALS(heap.begin(), heap.end()); 50 51 BinaryHeap<int>::handle h5 = heap.push(5); 52 TS_ASSERT(h5 == h5); 53 TS_ASSERT_EQUALS(heap.top(), 5); 54 TS_ASSERT_EQUALS(heap.size(), 1u); 55 TS_ASSERT(! heap.empty()); 56 TS_ASSERT_DIFFERS(heap.begin(), heap.end()); 57 TS_ASSERT_EQUALS(*h5, 5); 58 TS_ASSERT_EQUALS(*heap.begin(), 5); 59 TS_ASSERT_THROWS_NOTHING(heap.erase(h5)); 60 TS_ASSERT(heap.empty()); 61 TS_ASSERT_EQUALS(heap.size(), 0u); 62 #ifdef CVC4_ASSERTIONS 63 TS_ASSERT_THROWS_ANYTHING(heap.top()); 64 TS_ASSERT_THROWS_ANYTHING(heap.pop()); 65 #endif /* CVC4_ASSERTIONS */ 66 67 // Next test a heap of 4 elements 68 h5 = heap.push(5); 69 BinaryHeap<int>::handle h3 = heap.push(3); 70 BinaryHeap<int>::handle h10 = heap.push(10); 71 BinaryHeap<int>::handle h2 = heap.push(2); 72 TS_ASSERT_DIFFERS(h5, h3); 73 TS_ASSERT_DIFFERS(h5, h10); 74 TS_ASSERT_DIFFERS(h5, h2); 75 TS_ASSERT_DIFFERS(h3, h10); 76 TS_ASSERT_DIFFERS(h3, h2); 77 TS_ASSERT_DIFFERS(h10, h2); 78 TS_ASSERT_DIFFERS(heap.begin(), heap.end()); 79 TS_ASSERT_EQUALS(*heap.begin(), 10); 80 TS_ASSERT_EQUALS(*h2, 2); 81 TS_ASSERT_EQUALS(*h3, 3); 82 TS_ASSERT_EQUALS(*h5, 5); 83 TS_ASSERT_EQUALS(*h10, 10); 84 TS_ASSERT_EQUALS(heap.top(), 10); 85 // test the iterator (note the order of elements isn't guaranteed!) 86 BinaryHeap<int>::const_iterator i = heap.begin(); 87 TS_ASSERT_DIFFERS(i, heap.end()); 88 TS_ASSERT_THROWS_NOTHING(*i++); 89 TS_ASSERT_DIFFERS(i, heap.end()); 90 TS_ASSERT_THROWS_NOTHING(*i++); 91 TS_ASSERT_DIFFERS(i, heap.end()); 92 TS_ASSERT_THROWS_NOTHING(*i++); 93 TS_ASSERT_DIFFERS(i, heap.end()); 94 TS_ASSERT_THROWS_NOTHING(*i++); 95 TS_ASSERT_EQUALS(i, heap.end()); 96 TS_ASSERT(!heap.empty()); 97 TS_ASSERT_EQUALS(heap.size(), 4u); 98 TS_ASSERT_THROWS_NOTHING(heap.pop()); 99 TS_ASSERT_DIFFERS(heap.begin(), heap.end()); 100 TS_ASSERT_EQUALS(*heap.begin(), 5); 101 TS_ASSERT_EQUALS(heap.top(), 5); 102 TS_ASSERT(!heap.empty()); 103 TS_ASSERT_EQUALS(heap.size(), 3u); 104 TS_ASSERT_THROWS_NOTHING(heap.pop()); 105 TS_ASSERT_DIFFERS(heap.begin(), heap.end()); 106 TS_ASSERT_EQUALS(*heap.begin(), 3); 107 TS_ASSERT_EQUALS(heap.top(), 3); 108 TS_ASSERT(!heap.empty()); 109 TS_ASSERT_EQUALS(heap.size(), 2u); 110 TS_ASSERT_THROWS_NOTHING(heap.pop()); 111 TS_ASSERT_DIFFERS(heap.begin(), heap.end()); 112 TS_ASSERT_EQUALS(*heap.begin(), 2); 113 TS_ASSERT_EQUALS(heap.top(), 2); 114 TS_ASSERT(!heap.empty()); 115 TS_ASSERT_EQUALS(heap.size(), 1u); 116 TS_ASSERT_THROWS_NOTHING(heap.pop()); 117 TS_ASSERT_EQUALS(heap.begin(), heap.end()); 118 TS_ASSERT(heap.empty()); 119 TS_ASSERT_EQUALS(heap.size(), 0u); 120 #ifdef CVC4_ASSERTIONS 121 TS_ASSERT_THROWS_ANYTHING(heap.top()); 122 TS_ASSERT_THROWS_ANYTHING(heap.pop()); 123 #endif /* CVC4_ASSERTIONS */ 124 125 // Now with a few updates 126 h5 = heap.push(5); 127 h3 = heap.push(3); 128 h10 = heap.push(10); 129 h2 = heap.push(2); 130 131 TS_ASSERT_EQUALS(*h5, 5); 132 TS_ASSERT_EQUALS(*h3, 3); 133 TS_ASSERT_EQUALS(*h10, 10); 134 TS_ASSERT_EQUALS(*h2, 2); 135 136 TS_ASSERT_EQUALS(heap.top(), 10); 137 heap.update(h10, -10); 138 TS_ASSERT_EQUALS(*h10, -10); 139 TS_ASSERT_EQUALS(heap.top(), 5); 140 heap.erase(h2); 141 TS_ASSERT_EQUALS(heap.top(), 5); 142 heap.update(h3, -20); 143 TS_ASSERT_EQUALS(*h3, -20); 144 TS_ASSERT_EQUALS(heap.top(), 5); 145 heap.pop(); 146 TS_ASSERT_EQUALS(heap.top(), -10); 147 heap.pop(); 148 TS_ASSERT_EQUALS(heap.top(), -20); 149 } 150 151 struct Elem { 152 int x; ElemElem153 Elem(int y) : x(y) {} 154 };/* struct Elem */ 155 156 struct Cmp { 157 bool valid; CmpCmp158 Cmp() : valid(false) {} CmpCmp159 Cmp(int x) : valid(true) {} operatorCmp160 bool operator()(Elem x, Elem y) const { 161 // ensure BinaryHeap<> calls our Cmp instance and not some fresh one 162 TS_ASSERT(valid); 163 return x.x > y.x; 164 } 165 };/* struct Cmp */ 166 testLargeHeap()167 void testLargeHeap() { 168 BinaryHeap<Elem, Cmp> heap(Cmp(0)); 169 vector<BinaryHeap<Elem, Cmp>::handle> handles; 170 TS_ASSERT(heap.empty()); 171 for(int x = 0; x < 1000; ++x) { 172 handles.push_back(heap.push(Elem(x))); 173 } 174 TS_ASSERT(!heap.empty()); 175 TS_ASSERT_EQUALS(heap.size(), 1000u); 176 heap.update(handles[100], 50); 177 heap.update(handles[100], -50); 178 heap.update(handles[600], 2); 179 heap.update(handles[184], -9); 180 heap.update(handles[987], 9555); 181 heap.update(handles[672], -1003); 182 heap.update(handles[781], 481); 183 heap.update(handles[9], 9619); 184 heap.update(handles[919], 111); 185 TS_ASSERT_EQUALS(heap.size(), 1000u); 186 heap.erase(handles[10]); 187 TS_ASSERT_EQUALS(heap.size(), 999u); 188 TS_ASSERT(!heap.empty()); 189 handles.clear(); 190 Elem last = heap.top(); 191 for(int x = 0; x < 800; ++x) { 192 TS_ASSERT_LESS_THAN_EQUALS(last.x, heap.top().x); 193 last = heap.top(); 194 heap.pop(); 195 TS_ASSERT_EQUALS(heap.size(), 998u - x); 196 TS_ASSERT(!heap.empty()); 197 } 198 TS_ASSERT_EQUALS(heap.size(), 199u); 199 for(int x = 0; x < 10000; ++x) { 200 // two-thirds of the time insert large value, one-third insert small value 201 handles.push_back(heap.push(Elem(4 * ((x % 3 == 0) ? -x : x)))); 202 if(x % 10 == 6) { 203 // also every tenth insert somewhere in the middle 204 handles.push_back(heap.push(Elem(x / 10))); 205 } 206 // change a few 207 heap.update(handles[x / 10], 4 * (*handles[x / 10]).x); 208 heap.update(handles[x / 105], (*handles[x / 4]).x - 294); 209 heap.update(handles[x / 33], 6 * (*handles[x / 82]).x / 5 - 1); 210 TS_ASSERT_EQUALS(heap.size(), size_t(x) + ((x + 4) / 10) + 200); 211 } 212 TS_ASSERT_EQUALS(heap.size(), 11199u); 213 TS_ASSERT(!heap.empty()); 214 last = heap.top(); 215 while(!heap.empty()) { 216 TS_ASSERT_LESS_THAN_EQUALS(last.x, heap.top().x); 217 last = heap.top(); 218 heap.pop(); 219 } 220 TS_ASSERT(heap.empty()); 221 heap.clear(); 222 TS_ASSERT(heap.empty()); 223 } 224 225 };/* class BinaryHeapBlack */ 226