GCC Code Coverage Report
Directory: . Exec Total Coverage
File: test/unit/util/binary_heap_black.cpp Lines: 149 149 100.0 %
Date: 2021-03-23 Branches: 468 1818 25.7 %

Line Exec Source
1
/*********************                                                        */
2
/*! \file binary_heap_black.cpp
3
 ** \verbatim
4
 ** Top contributors (to current version):
5
 **   Aina Niemetz, Morgan Deters
6
 ** This file is part of the CVC4 project.
7
 ** Copyright (c) 2009-2021 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 <iostream>
18
#include <sstream>
19
20
#include "test.h"
21
#include "util/bin_heap.h"
22
23
namespace CVC4 {
24
namespace test {
25
26
8
class TestUtilBlackBinaryHeap : public TestInternal
27
{
28
 protected:
29
  struct Elem
30
  {
31
84018
    Elem(int32_t y) : d_x(y) {}
32
    int32_t d_x;
33
  };
34
35
  struct Cmp
36
  {
37
    Cmp() : d_valid(false) {}
38
2
    Cmp(int32_t x) : d_valid(true) {}
39
40
739884
    bool operator()(Elem x, Elem y) const
41
    {
42
      // ensure BinaryHeap<> calls our Cmp instance and not some fresh one
43
739884
      Assert(d_valid);
44
739884
      return x.d_x > y.d_x;
45
    }
46
47
    bool d_valid;
48
  };
49
};
50
51
/**
52
 * Test a a series of simple heaps (push a few then pop all then do others).
53
 * Done as a series to test if the heap structure falls into a bad state
54
 * after prolonged use.
55
 */
56
11
TEST_F(TestUtilBlackBinaryHeap, heap_series)
57
{
58
4
  BinaryHeap<int32_t> heap;
59
60
  // First test a heap of 1 element
61
2
  ASSERT_EQ(heap.size(), 0u);
62
2
  ASSERT_TRUE(heap.empty());
63
#ifdef CVC4_ASSERTIONS
64
2
  ASSERT_DEATH(heap.top(), "!empty\\(\\)");
65
2
  ASSERT_DEATH(heap.pop(), "!empty\\(\\)");
66
#endif
67
2
  ASSERT_TRUE(heap.begin() == heap.end());
68
69
2
  BinaryHeap<int32_t>::handle h5 = heap.push(5);
70
2
  ASSERT_TRUE(h5 == h5);
71
2
  ASSERT_EQ(heap.top(), 5);
72
2
  ASSERT_EQ(heap.size(), 1u);
73
2
  ASSERT_FALSE(heap.empty());
74
2
  ASSERT_TRUE(heap.begin() != heap.end());
75
2
  ASSERT_EQ(*h5, 5);
76
2
  ASSERT_EQ(*heap.begin(), 5);
77
2
  ASSERT_NO_THROW(heap.erase(h5));
78
2
  ASSERT_TRUE(heap.empty());
79
2
  ASSERT_EQ(heap.size(), 0u);
80
#ifdef CVC4_ASSERTIONS
81
2
  ASSERT_DEATH(heap.top(), "!empty\\(\\)");
82
2
  ASSERT_DEATH(heap.pop(), "!empty\\(\\)");
83
#endif
84
85
  // Next test a heap of 4 elements
86
2
  h5 = heap.push(5);
87
2
  BinaryHeap<int32_t>::handle h3 = heap.push(3);
88
2
  BinaryHeap<int32_t>::handle h10 = heap.push(10);
89
2
  BinaryHeap<int32_t>::handle h2 = heap.push(2);
90
2
  ASSERT_NE(h5, h3);
91
2
  ASSERT_NE(h5, h10);
92
2
  ASSERT_NE(h5, h2);
93
2
  ASSERT_NE(h3, h10);
94
2
  ASSERT_NE(h3, h2);
95
2
  ASSERT_NE(h10, h2);
96
2
  ASSERT_TRUE(heap.begin() != heap.end());
97
2
  ASSERT_EQ(*heap.begin(), 10);
98
2
  ASSERT_EQ(*h2, 2);
99
2
  ASSERT_EQ(*h3, 3);
100
2
  ASSERT_EQ(*h5, 5);
101
2
  ASSERT_EQ(*h10, 10);
102
2
  ASSERT_EQ(heap.top(), 10);
103
  // test the iterator (note the order of elements isn't guaranteed!)
104
2
  BinaryHeap<int32_t>::const_iterator i = heap.begin();
105
2
  ASSERT_TRUE(i != heap.end());
106
2
  ASSERT_NO_THROW(*i++);
107
2
  ASSERT_TRUE(i != heap.end());
108
2
  ASSERT_NO_THROW(*i++);
109
2
  ASSERT_TRUE(i != heap.end());
110
2
  ASSERT_NO_THROW(*i++);
111
2
  ASSERT_TRUE(i != heap.end());
112
2
  ASSERT_NO_THROW(*i++);
113
2
  ASSERT_TRUE(i == heap.end());
114
2
  ASSERT_FALSE(heap.empty());
115
2
  ASSERT_EQ(heap.size(), 4u);
116
2
  ASSERT_NO_THROW(heap.pop());
117
2
  ASSERT_TRUE(i != heap.end());
118
2
  ASSERT_EQ(*heap.begin(), 5);
119
2
  ASSERT_EQ(heap.top(), 5);
120
2
  ASSERT_FALSE(heap.empty());
121
2
  ASSERT_EQ(heap.size(), 3u);
122
2
  ASSERT_NO_THROW(heap.pop());
123
2
  ASSERT_TRUE(heap.begin() != heap.end());
124
2
  ASSERT_EQ(*heap.begin(), 3);
125
2
  ASSERT_EQ(heap.top(), 3);
126
2
  ASSERT_FALSE(heap.empty());
127
2
  ASSERT_EQ(heap.size(), 2u);
128
2
  ASSERT_NO_THROW(heap.pop());
129
2
  ASSERT_TRUE(heap.begin() != heap.end());
130
2
  ASSERT_EQ(*heap.begin(), 2);
131
2
  ASSERT_EQ(heap.top(), 2);
132
2
  ASSERT_FALSE(heap.empty());
133
2
  ASSERT_EQ(heap.size(), 1u);
134
2
  ASSERT_NO_THROW(heap.pop());
135
2
  ASSERT_TRUE(heap.begin() == heap.end());
136
2
  ASSERT_TRUE(heap.empty());
137
2
  ASSERT_EQ(heap.size(), 0u);
138
#ifdef CVC4_ASSERTIONS
139
2
  ASSERT_DEATH(heap.top(), "!empty\\(\\)");
140
2
  ASSERT_DEATH(heap.pop(), "!empty\\(\\)");
141
#endif
142
143
  // Now with a few updates
144
2
  h5 = heap.push(5);
145
2
  h3 = heap.push(3);
146
2
  h10 = heap.push(10);
147
2
  h2 = heap.push(2);
148
149
2
  ASSERT_EQ(*h5, 5);
150
2
  ASSERT_EQ(*h3, 3);
151
2
  ASSERT_EQ(*h10, 10);
152
2
  ASSERT_EQ(*h2, 2);
153
154
2
  ASSERT_EQ(heap.top(), 10);
155
2
  heap.update(h10, -10);
156
2
  ASSERT_EQ(*h10, -10);
157
2
  ASSERT_EQ(heap.top(), 5);
158
2
  heap.erase(h2);
159
2
  ASSERT_EQ(heap.top(), 5);
160
2
  heap.update(h3, -20);
161
2
  ASSERT_EQ(*h3, -20);
162
2
  ASSERT_EQ(heap.top(), 5);
163
2
  heap.pop();
164
2
  ASSERT_EQ(heap.top(), -10);
165
2
  heap.pop();
166
2
  ASSERT_EQ(heap.top(), -20);
167
}
168
169
11
TEST_F(TestUtilBlackBinaryHeap, large_heap)
170
{
171
4
  BinaryHeap<Elem, Cmp> heap(Cmp(0));
172
4
  std::vector<BinaryHeap<Elem, Cmp>::handle> handles;
173
2
  ASSERT_TRUE(heap.empty());
174
2002
  for (int32_t x = 0; x < 1000; ++x)
175
  {
176
2000
    handles.push_back(heap.push(Elem(x)));
177
  }
178
2
  ASSERT_FALSE(heap.empty());
179
2
  ASSERT_EQ(heap.size(), 1000u);
180
2
  heap.update(handles[100], 50);
181
2
  heap.update(handles[100], -50);
182
2
  heap.update(handles[600], 2);
183
2
  heap.update(handles[184], -9);
184
2
  heap.update(handles[987], 9555);
185
2
  heap.update(handles[672], -1003);
186
2
  heap.update(handles[781], 481);
187
2
  heap.update(handles[9], 9619);
188
2
  heap.update(handles[919], 111);
189
2
  ASSERT_EQ(heap.size(), 1000u);
190
2
  heap.erase(handles[10]);
191
2
  ASSERT_EQ(heap.size(), 999u);
192
2
  ASSERT_FALSE(heap.empty());
193
2
  handles.clear();
194
2
  Elem last = heap.top();
195
1602
  for (int32_t x = 0; x < 800; ++x)
196
  {
197
1600
    ASSERT_LE(last.d_x, heap.top().d_x);
198
1600
    last = heap.top();
199
1600
    heap.pop();
200
1600
    ASSERT_EQ(heap.size(), 998u - x);
201
1600
    ASSERT_FALSE(heap.empty());
202
  }
203
2
  ASSERT_EQ(heap.size(), 199u);
204
20002
  for (int32_t x = 0; x < 10000; ++x)
205
  {
206
    // two-thirds of the time insert large value, one-third insert small value
207
20000
    handles.push_back(heap.push(Elem(4 * ((x % 3 == 0) ? -x : x))));
208
20000
    if (x % 10 == 6)
209
    {
210
      // also every tenth insert somewhere in the middle
211
2000
      handles.push_back(heap.push(Elem(x / 10)));
212
    }
213
    // change a few
214
20000
    heap.update(handles[x / 10], 4 * (*handles[x / 10]).d_x);
215
20000
    heap.update(handles[x / 105], (*handles[x / 4]).d_x - 294);
216
20000
    heap.update(handles[x / 33], 6 * (*handles[x / 82]).d_x / 5 - 1);
217
20000
    ASSERT_EQ(heap.size(), size_t(x) + ((x + 4) / 10) + 200);
218
  }
219
2
  ASSERT_EQ(heap.size(), 11199u);
220
2
  ASSERT_FALSE(heap.empty());
221
2
  last = heap.top();
222
44798
  while (!heap.empty())
223
  {
224
22398
    ASSERT_LE(last.d_x, heap.top().d_x);
225
22398
    last = heap.top();
226
22398
    heap.pop();
227
  }
228
2
  ASSERT_TRUE(heap.empty());
229
2
  heap.clear();
230
2
  ASSERT_TRUE(heap.empty());
231
}
232
}  // namespace test
233
9
}  // namespace CVC4