From 0b9fe94d346b7448a0e092cc9f43013aadfe9548 Mon Sep 17 00:00:00 2001 From: Aina Niemetz Date: Fri, 26 Feb 2021 11:59:38 -0800 Subject: [PATCH] google test: util: Migrate binary_heap_black. (#6012) --- test/unit/util/CMakeLists.txt | 2 +- test/unit/util/binary_heap_black.cpp | 233 +++++++++++++++++++++++++++ test/unit/util/binary_heap_black.h | 226 -------------------------- 3 files changed, 234 insertions(+), 227 deletions(-) create mode 100644 test/unit/util/binary_heap_black.cpp delete mode 100644 test/unit/util/binary_heap_black.h diff --git a/test/unit/util/CMakeLists.txt b/test/unit/util/CMakeLists.txt index bdc5a2b54..28d0ff148 100644 --- a/test/unit/util/CMakeLists.txt +++ b/test/unit/util/CMakeLists.txt @@ -13,7 +13,7 @@ cvc4_add_cxx_unit_test_white(array_store_all_white util) cvc4_add_unit_test_white(assert_white util) -cvc4_add_cxx_unit_test_black(binary_heap_black util) +cvc4_add_unit_test_black(binary_heap_black util) cvc4_add_cxx_unit_test_black(bitvector_black util) cvc4_add_cxx_unit_test_black(boolean_simplification_black util) cvc4_add_cxx_unit_test_black(cardinality_public util) diff --git a/test/unit/util/binary_heap_black.cpp b/test/unit/util/binary_heap_black.cpp new file mode 100644 index 000000000..a6a84f6e6 --- /dev/null +++ b/test/unit/util/binary_heap_black.cpp @@ -0,0 +1,233 @@ +/********************* */ +/*! \file binary_heap_black.cpp + ** \verbatim + ** Top contributors (to current version): + ** Aina Niemetz, Morgan Deters + ** This file is part of the CVC4 project. + ** Copyright (c) 2009-2020 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.\endverbatim + ** + ** \brief Black box testing of CVC4::BinaryHeap + ** + ** Black box testing of CVC4::BinaryHeap. + **/ + +#include +#include + +#include "test.h" +#include "util/bin_heap.h" + +namespace CVC4 { +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 heap; + + // First test a heap of 1 element + ASSERT_EQ(heap.size(), 0u); + ASSERT_TRUE(heap.empty()); +#ifdef CVC4_ASSERTIONS + ASSERT_DEATH(heap.top(), "!empty\\(\\)"); + ASSERT_DEATH(heap.pop(), "!empty\\(\\)"); +#endif + ASSERT_EQ(heap.begin(), heap.end()); + + BinaryHeap::handle h5 = heap.push(5); + ASSERT_TRUE(h5 == h5); + ASSERT_EQ(heap.top(), 5); + ASSERT_EQ(heap.size(), 1u); + ASSERT_FALSE(heap.empty()); + ASSERT_NE(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 CVC4_ASSERTIONS + ASSERT_DEATH(heap.top(), "!empty\\(\\)"); + ASSERT_DEATH(heap.pop(), "!empty\\(\\)"); +#endif + + // Next test a heap of 4 elements + h5 = heap.push(5); + BinaryHeap::handle h3 = heap.push(3); + BinaryHeap::handle h10 = heap.push(10); + BinaryHeap::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_NE(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::const_iterator i = heap.begin(); + ASSERT_NE(i, heap.end()); + ASSERT_NO_THROW(*i++); + ASSERT_NE(i, heap.end()); + ASSERT_NO_THROW(*i++); + ASSERT_NE(i, heap.end()); + ASSERT_NO_THROW(*i++); + ASSERT_NE(i, heap.end()); + ASSERT_NO_THROW(*i++); + ASSERT_EQ(i, heap.end()); + ASSERT_FALSE(heap.empty()); + ASSERT_EQ(heap.size(), 4u); + ASSERT_NO_THROW(heap.pop()); + ASSERT_NE(heap.begin(), 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_NE(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_NE(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_EQ(heap.begin(), heap.end()); + ASSERT_TRUE(heap.empty()); + ASSERT_EQ(heap.size(), 0u); +#ifdef CVC4_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 heap(Cmp(0)); + std::vector::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 CVC4 diff --git a/test/unit/util/binary_heap_black.h b/test/unit/util/binary_heap_black.h deleted file mode 100644 index 9514b62e9..000000000 --- a/test/unit/util/binary_heap_black.h +++ /dev/null @@ -1,226 +0,0 @@ -/********************* */ -/*! \file binary_heap_black.h - ** \verbatim - ** Top contributors (to current version): - ** Morgan Deters, Mathias Preiner, Andres Noetzli - ** This file is part of the CVC4 project. - ** Copyright (c) 2009-2020 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.\endverbatim - ** - ** \brief Black box testing of CVC4::BinaryHeap - ** - ** Black box testing of CVC4::BinaryHeap. - **/ - -#include - -#include -#include - -#include "test_utils.h" -#include "util/bin_heap.h" - -using namespace CVC4; -using namespace std; - -class BinaryHeapBlack : public CxxTest::TestSuite { - public: - void setUp() override {} - - void tearDown() override {} - - /** - * 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. - */ - void testHeapSeries() - { - BinaryHeap heap; - - // First test a heap of 1 element - TS_ASSERT_EQUALS(heap.size(), 0u); - TS_ASSERT(heap.empty()); -#ifdef CVC4_ASSERTIONS - TS_UTILS_EXPECT_ABORT(heap.top()); - TS_UTILS_EXPECT_ABORT(heap.pop()); -#endif /* CVC4_ASSERTIONS */ - TS_ASSERT_EQUALS(heap.begin(), heap.end()); - - BinaryHeap::handle h5 = heap.push(5); - TS_ASSERT(h5 == h5); - TS_ASSERT_EQUALS(heap.top(), 5); - TS_ASSERT_EQUALS(heap.size(), 1u); - TS_ASSERT(! heap.empty()); - TS_ASSERT_DIFFERS(heap.begin(), heap.end()); - TS_ASSERT_EQUALS(*h5, 5); - TS_ASSERT_EQUALS(*heap.begin(), 5); - TS_ASSERT_THROWS_NOTHING(heap.erase(h5)); - TS_ASSERT(heap.empty()); - TS_ASSERT_EQUALS(heap.size(), 0u); -#ifdef CVC4_ASSERTIONS - TS_UTILS_EXPECT_ABORT(heap.top()); - TS_UTILS_EXPECT_ABORT(heap.pop()); -#endif /* CVC4_ASSERTIONS */ - - // Next test a heap of 4 elements - h5 = heap.push(5); - BinaryHeap::handle h3 = heap.push(3); - BinaryHeap::handle h10 = heap.push(10); - BinaryHeap::handle h2 = heap.push(2); - TS_ASSERT_DIFFERS(h5, h3); - TS_ASSERT_DIFFERS(h5, h10); - TS_ASSERT_DIFFERS(h5, h2); - TS_ASSERT_DIFFERS(h3, h10); - TS_ASSERT_DIFFERS(h3, h2); - TS_ASSERT_DIFFERS(h10, h2); - TS_ASSERT_DIFFERS(heap.begin(), heap.end()); - TS_ASSERT_EQUALS(*heap.begin(), 10); - TS_ASSERT_EQUALS(*h2, 2); - TS_ASSERT_EQUALS(*h3, 3); - TS_ASSERT_EQUALS(*h5, 5); - TS_ASSERT_EQUALS(*h10, 10); - TS_ASSERT_EQUALS(heap.top(), 10); - // test the iterator (note the order of elements isn't guaranteed!) - BinaryHeap::const_iterator i = heap.begin(); - TS_ASSERT_DIFFERS(i, heap.end()); - TS_ASSERT_THROWS_NOTHING(*i++); - TS_ASSERT_DIFFERS(i, heap.end()); - TS_ASSERT_THROWS_NOTHING(*i++); - TS_ASSERT_DIFFERS(i, heap.end()); - TS_ASSERT_THROWS_NOTHING(*i++); - TS_ASSERT_DIFFERS(i, heap.end()); - TS_ASSERT_THROWS_NOTHING(*i++); - TS_ASSERT_EQUALS(i, heap.end()); - TS_ASSERT(!heap.empty()); - TS_ASSERT_EQUALS(heap.size(), 4u); - TS_ASSERT_THROWS_NOTHING(heap.pop()); - TS_ASSERT_DIFFERS(heap.begin(), heap.end()); - TS_ASSERT_EQUALS(*heap.begin(), 5); - TS_ASSERT_EQUALS(heap.top(), 5); - TS_ASSERT(!heap.empty()); - TS_ASSERT_EQUALS(heap.size(), 3u); - TS_ASSERT_THROWS_NOTHING(heap.pop()); - TS_ASSERT_DIFFERS(heap.begin(), heap.end()); - TS_ASSERT_EQUALS(*heap.begin(), 3); - TS_ASSERT_EQUALS(heap.top(), 3); - TS_ASSERT(!heap.empty()); - TS_ASSERT_EQUALS(heap.size(), 2u); - TS_ASSERT_THROWS_NOTHING(heap.pop()); - TS_ASSERT_DIFFERS(heap.begin(), heap.end()); - TS_ASSERT_EQUALS(*heap.begin(), 2); - TS_ASSERT_EQUALS(heap.top(), 2); - TS_ASSERT(!heap.empty()); - TS_ASSERT_EQUALS(heap.size(), 1u); - TS_ASSERT_THROWS_NOTHING(heap.pop()); - TS_ASSERT_EQUALS(heap.begin(), heap.end()); - TS_ASSERT(heap.empty()); - TS_ASSERT_EQUALS(heap.size(), 0u); -#ifdef CVC4_ASSERTIONS - TS_UTILS_EXPECT_ABORT(heap.top()); - TS_UTILS_EXPECT_ABORT(heap.pop()); -#endif /* CVC4_ASSERTIONS */ - - // Now with a few updates - h5 = heap.push(5); - h3 = heap.push(3); - h10 = heap.push(10); - h2 = heap.push(2); - - TS_ASSERT_EQUALS(*h5, 5); - TS_ASSERT_EQUALS(*h3, 3); - TS_ASSERT_EQUALS(*h10, 10); - TS_ASSERT_EQUALS(*h2, 2); - - TS_ASSERT_EQUALS(heap.top(), 10); - heap.update(h10, -10); - TS_ASSERT_EQUALS(*h10, -10); - TS_ASSERT_EQUALS(heap.top(), 5); - heap.erase(h2); - TS_ASSERT_EQUALS(heap.top(), 5); - heap.update(h3, -20); - TS_ASSERT_EQUALS(*h3, -20); - TS_ASSERT_EQUALS(heap.top(), 5); - heap.pop(); - TS_ASSERT_EQUALS(heap.top(), -10); - heap.pop(); - TS_ASSERT_EQUALS(heap.top(), -20); - } - - struct Elem { - int x; - Elem(int y) : x(y) {} - };/* struct Elem */ - - struct Cmp { - bool valid; - Cmp() : valid(false) {} - Cmp(int x) : valid(true) {} - bool operator()(Elem x, Elem y) const { - // ensure BinaryHeap<> calls our Cmp instance and not some fresh one - TS_ASSERT(valid); - return x.x > y.x; - } - };/* struct Cmp */ - - void testLargeHeap() { - BinaryHeap heap(Cmp(0)); - vector::handle> handles; - TS_ASSERT(heap.empty()); - for(int x = 0; x < 1000; ++x) { - handles.push_back(heap.push(Elem(x))); - } - TS_ASSERT(!heap.empty()); - TS_ASSERT_EQUALS(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); - TS_ASSERT_EQUALS(heap.size(), 1000u); - heap.erase(handles[10]); - TS_ASSERT_EQUALS(heap.size(), 999u); - TS_ASSERT(!heap.empty()); - handles.clear(); - Elem last = heap.top(); - for(int x = 0; x < 800; ++x) { - TS_ASSERT_LESS_THAN_EQUALS(last.x, heap.top().x); - last = heap.top(); - heap.pop(); - TS_ASSERT_EQUALS(heap.size(), 998u - x); - TS_ASSERT(!heap.empty()); - } - TS_ASSERT_EQUALS(heap.size(), 199u); - for(int 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]).x); - heap.update(handles[x / 105], (*handles[x / 4]).x - 294); - heap.update(handles[x / 33], 6 * (*handles[x / 82]).x / 5 - 1); - TS_ASSERT_EQUALS(heap.size(), size_t(x) + ((x + 4) / 10) + 200); - } - TS_ASSERT_EQUALS(heap.size(), 11199u); - TS_ASSERT(!heap.empty()); - last = heap.top(); - while(!heap.empty()) { - TS_ASSERT_LESS_THAN_EQUALS(last.x, heap.top().x); - last = heap.top(); - heap.pop(); - } - TS_ASSERT(heap.empty()); - heap.clear(); - TS_ASSERT(heap.empty()); - } - -};/* class BinaryHeapBlack */ -- 2.30.2