Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	test/unit/util/binary_heap_black.cpp	Lines:	149	149	100.0 %
Date:	2021-11-07	Branches:	468	1818	25.7 %


/******************************************************************************
 * Top contributors (to current version):
 *   Aina Niemetz, Morgan Deters
 *
 * This file is part of the cvc5 project.
 *
 * Copyright (c) 2009-2021 by the authors listed in the file AUTHORS
 * in the top-level source directory and their institutional affiliations.
 * All rights reserved.  See the file COPYING in the top-level source
 * directory for licensing information.
 * ****************************************************************************
 *
 * Black box testing of cvc5::BinaryHeap.
 */

#include <iostream>
#include <sstream>

#include "test.h"
#include "util/bin_heap.h"

namespace cvc5 {
namespace test {

class TestUtilBlackBinaryHeap : public TestInternal
{
 protected:
  struct Elem
  {
    Elem(int32_t y) : d_x(y) {}
    int32_t d_x;
  };

  struct Cmp
  {
    Cmp() : d_valid(false) {}
    Cmp(int32_t x) : d_valid(true) {}

    bool operator()(Elem x, Elem y) const
    {
      // ensure BinaryHeap<> calls our Cmp instance and not some fresh one
      Assert(d_valid);
      return x.d_x > y.d_x;
    }

    bool d_valid;
  };
};

/**
 * Test a a series of simple heaps (push a few then pop all then do others).
 * Done as a series to test if the heap structure falls into a bad state
 * after prolonged use.
 */
TEST_F(TestUtilBlackBinaryHeap, heap_series)
{
  BinaryHeap<int32_t> heap;

  // First test a heap of 1 element
  ASSERT_EQ(heap.size(), 0u);
  ASSERT_TRUE(heap.empty());
#ifdef CVC5_ASSERTIONS
  ASSERT_DEATH(heap.top(), "!empty\\(\\)");
  ASSERT_DEATH(heap.pop(), "!empty\\(\\)");
#endif
  ASSERT_TRUE(heap.begin() == heap.end());

  BinaryHeap<int32_t>::handle h5 = heap.push(5);
  ASSERT_TRUE(h5 == h5);
  ASSERT_EQ(heap.top(), 5);
  ASSERT_EQ(heap.size(), 1u);
  ASSERT_FALSE(heap.empty());
  ASSERT_TRUE(heap.begin() != heap.end());
  ASSERT_EQ(*h5, 5);
  ASSERT_EQ(*heap.begin(), 5);
  ASSERT_NO_THROW(heap.erase(h5));
  ASSERT_TRUE(heap.empty());
  ASSERT_EQ(heap.size(), 0u);
#ifdef CVC5_ASSERTIONS
  ASSERT_DEATH(heap.top(), "!empty\\(\\)");
  ASSERT_DEATH(heap.pop(), "!empty\\(\\)");
#endif

  // Next test a heap of 4 elements
  h5 = heap.push(5);
  BinaryHeap<int32_t>::handle h3 = heap.push(3);
  BinaryHeap<int32_t>::handle h10 = heap.push(10);
  BinaryHeap<int32_t>::handle h2 = heap.push(2);
  ASSERT_NE(h5, h3);
  ASSERT_NE(h5, h10);
  ASSERT_NE(h5, h2);
  ASSERT_NE(h3, h10);
  ASSERT_NE(h3, h2);
  ASSERT_NE(h10, h2);
  ASSERT_TRUE(heap.begin() != heap.end());
  ASSERT_EQ(*heap.begin(), 10);
  ASSERT_EQ(*h2, 2);
  ASSERT_EQ(*h3, 3);
  ASSERT_EQ(*h5, 5);
  ASSERT_EQ(*h10, 10);
  ASSERT_EQ(heap.top(), 10);
  // test the iterator (note the order of elements isn't guaranteed!)
  BinaryHeap<int32_t>::const_iterator i = heap.begin();
  ASSERT_TRUE(i != heap.end());
  ASSERT_NO_THROW(*i++);
  ASSERT_TRUE(i != heap.end());
  ASSERT_NO_THROW(*i++);
  ASSERT_TRUE(i != heap.end());
  ASSERT_NO_THROW(*i++);
  ASSERT_TRUE(i != heap.end());
  ASSERT_NO_THROW(*i++);
  ASSERT_TRUE(i == heap.end());
  ASSERT_FALSE(heap.empty());
  ASSERT_EQ(heap.size(), 4u);
  ASSERT_NO_THROW(heap.pop());
  ASSERT_TRUE(i != heap.end());
  ASSERT_EQ(*heap.begin(), 5);
  ASSERT_EQ(heap.top(), 5);
  ASSERT_FALSE(heap.empty());
  ASSERT_EQ(heap.size(), 3u);
  ASSERT_NO_THROW(heap.pop());
  ASSERT_TRUE(heap.begin() != heap.end());
  ASSERT_EQ(*heap.begin(), 3);
  ASSERT_EQ(heap.top(), 3);
  ASSERT_FALSE(heap.empty());
  ASSERT_EQ(heap.size(), 2u);
  ASSERT_NO_THROW(heap.pop());
  ASSERT_TRUE(heap.begin() != heap.end());
  ASSERT_EQ(*heap.begin(), 2);
  ASSERT_EQ(heap.top(), 2);
  ASSERT_FALSE(heap.empty());
  ASSERT_EQ(heap.size(), 1u);
  ASSERT_NO_THROW(heap.pop());
  ASSERT_TRUE(heap.begin() == heap.end());
  ASSERT_TRUE(heap.empty());
  ASSERT_EQ(heap.size(), 0u);
#ifdef CVC5_ASSERTIONS
  ASSERT_DEATH(heap.top(), "!empty\\(\\)");
  ASSERT_DEATH(heap.pop(), "!empty\\(\\)");
#endif

  // Now with a few updates
  h5 = heap.push(5);
  h3 = heap.push(3);
  h10 = heap.push(10);
  h2 = heap.push(2);

  ASSERT_EQ(*h5, 5);
  ASSERT_EQ(*h3, 3);
  ASSERT_EQ(*h10, 10);
  ASSERT_EQ(*h2, 2);

  ASSERT_EQ(heap.top(), 10);
  heap.update(h10, -10);
  ASSERT_EQ(*h10, -10);
  ASSERT_EQ(heap.top(), 5);
  heap.erase(h2);
  ASSERT_EQ(heap.top(), 5);
  heap.update(h3, -20);
  ASSERT_EQ(*h3, -20);
  ASSERT_EQ(heap.top(), 5);
  heap.pop();
  ASSERT_EQ(heap.top(), -10);
  heap.pop();
  ASSERT_EQ(heap.top(), -20);
}

TEST_F(TestUtilBlackBinaryHeap, large_heap)
{
  BinaryHeap<Elem, Cmp> heap(Cmp(0));
  std::vector<BinaryHeap<Elem, Cmp>::handle> handles;
  ASSERT_TRUE(heap.empty());
  for (int32_t x = 0; x < 1000; ++x)
  {
    handles.push_back(heap.push(Elem(x)));
  }
  ASSERT_FALSE(heap.empty());
  ASSERT_EQ(heap.size(), 1000u);
  heap.update(handles[100], 50);
  heap.update(handles[100], -50);
  heap.update(handles[600], 2);
  heap.update(handles[184], -9);
  heap.update(handles[987], 9555);
  heap.update(handles[672], -1003);
  heap.update(handles[781], 481);
  heap.update(handles[9], 9619);
  heap.update(handles[919], 111);
  ASSERT_EQ(heap.size(), 1000u);
  heap.erase(handles[10]);
  ASSERT_EQ(heap.size(), 999u);
  ASSERT_FALSE(heap.empty());
  handles.clear();
  Elem last = heap.top();
  for (int32_t x = 0; x < 800; ++x)
  {
    ASSERT_LE(last.d_x, heap.top().d_x);
    last = heap.top();
    heap.pop();
    ASSERT_EQ(heap.size(), 998u - x);
    ASSERT_FALSE(heap.empty());
  }
  ASSERT_EQ(heap.size(), 199u);
  for (int32_t x = 0; x < 10000; ++x)
  {
    // two-thirds of the time insert large value, one-third insert small value
    handles.push_back(heap.push(Elem(4 * ((x % 3 == 0) ? -x : x))));
    if (x % 10 == 6)
    {
      // also every tenth insert somewhere in the middle
      handles.push_back(heap.push(Elem(x / 10)));
    }
    // change a few
    heap.update(handles[x / 10], 4 * (*handles[x / 10]).d_x);
    heap.update(handles[x / 105], (*handles[x / 4]).d_x - 294);
    heap.update(handles[x / 33], 6 * (*handles[x / 82]).d_x / 5 - 1);
    ASSERT_EQ(heap.size(), size_t(x) + ((x + 4) / 10) + 200);
  }
  ASSERT_EQ(heap.size(), 11199u);
  ASSERT_FALSE(heap.empty());
  last = heap.top();
  while (!heap.empty())
  {
    ASSERT_LE(last.d_x, heap.top().d_x);
    last = heap.top();
    heap.pop();
  }
  ASSERT_TRUE(heap.empty());
  heap.clear();
  ASSERT_TRUE(heap.empty());
}
}  // namespace test
}  // namespace cvc5


Generated by: GCOVR (Version 3.2)

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