tesseract  5.0.0
heap_test.cc
Go to the documentation of this file.
1 // (C) Copyright 2017, Google Inc.
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 // http://www.apache.org/licenses/LICENSE-2.0
6 // Unless required by applicable law or agreed to in writing, software
7 // distributed under the License is distributed on an "AS IS" BASIS,
8 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
9 // See the License for the specific language governing permissions and
10 // limitations under the License.
11 
12 #include "include_gunit.h"
13 
14 #include "doubleptr.h"
15 #include "genericheap.h"
16 #include "kdpair.h"
17 
18 #include <string>
19 #include <utility>
20 
21 namespace tesseract {
22 
23 int test_data[] = {8, 1, 2, -4, 7, 9, 65536, 4, 9, 0};
24 
25 // The fixture for testing GenericHeap and DoublePtr.
26 class HeapTest : public testing::Test {
27 protected:
28  void SetUp() override {
29  std::locale::global(std::locale(""));
30  }
31 
32 public:
33  ~HeapTest() override;
34  // Pushes the test data onto both the heap and the KDVector.
36  for (size_t i = 0; i < countof(test_data); ++i) {
37  IntKDPair pair(test_data[i], i);
38  heap->Push(&pair);
39  v->push_back(pair);
40  }
41  }
42  // Verifies that the data in the heap matches the vector (after sorting) by
43  // popping everything off the heap.
45  EXPECT_FALSE(heap->empty());
46  EXPECT_EQ(heap->size(), v->size());
47  // Sort the vector and check that the keys come out of the heap in the same
48  // order as v.
49  // Also check that the indices match, except for 9, which is duplicated.
50  std::sort(v->begin(), v->end());
51  // Check that we have increasing order.
52  EXPECT_LT((*v)[0].key(), v->back().key());
53  for (unsigned i = 0; i < v->size(); ++i) {
54  EXPECT_EQ((*v)[i].key(), heap->PeekTop().key());
55  // Indices don't necessarily match for equal keys, so don't test them.
56  if (i + 1 < v->size() && (*v)[i + 1].key() == (*v)[i].key()) {
57  while (i + 1 < v->size() && (*v)[i + 1].key() == (*v)[i].key()) {
58  heap->Pop(nullptr);
59  ++i;
60  EXPECT_FALSE(heap->empty());
61  EXPECT_EQ((*v)[i].key(), heap->PeekTop().key());
62  }
63  } else {
64  // The indices must also match if the key is unique.
65  EXPECT_EQ((*v)[i].data(), heap->PeekTop().data());
66  }
67  EXPECT_FALSE(heap->empty());
68  EXPECT_TRUE(heap->Pop(nullptr));
69  }
70  EXPECT_TRUE(heap->empty());
71  }
72 };
73 
74 // Destructor.
75 // It is defined here, so the compiler can create a single vtable
76 // instead of a weak vtable (fixes compiler warning).
77 HeapTest::~HeapTest() = default;
78 
79 // Tests that a sort using a GenericHeap matches the result of a sort using
80 // a KDVector.
81 TEST_F(HeapTest, SortTest) {
83  EXPECT_TRUE(heap.empty());
84  KDVector v;
85  EXPECT_EQ(heap.size(), v.size());
86  // Push the test data onto both the heap and the KDVector.
87  PushTestData(&heap, &v);
88  VerifyHeapVectorMatch(&heap, &v);
89 }
90 
91 // Tests that pushing some stuff, popping some stuff, and then pushing more
92 // stuff results in output that matches the sort using a KDVector.
93 // a KDVector.
94 TEST_F(HeapTest, MixedTest) {
96  KDVector v;
97  // Push the test data onto both the heap and the KDVector.
98  PushTestData(&heap, &v);
99  // Sort the vector and remove the first 5 values from both heap and v.
100  std::sort(v.begin(), v.end());
101  for (int i = 0; i < 5; ++i) {
102  heap.Pop(nullptr);
103  v.erase(v.begin());
104  }
105  // Push the test data onto both the heap and the KDVector.
106  PushTestData(&heap, &v);
107  // Heap and vector should still match!
108  VerifyHeapVectorMatch(&heap, &v);
109 }
110 
111 // Tests that PopWorst still leaves the heap in a state such that it still
112 // matches a sorted KDVector.
113 TEST_F(HeapTest, PopWorstTest) {
115  KDVector v;
116  // Push the test data onto both the heap and the KDVector.
117  PushTestData(&heap, &v);
118  // Get the worst element off the heap.
119  IntKDPair pair;
120  heap.PopWorst(&pair);
121  EXPECT_EQ(pair.key(), 65536);
122  EXPECT_EQ(pair.data(), 6);
123  // Sort and remove the worst element from the vector.
124  std::sort(v.begin(), v.end());
125  v.resize(v.size() - 1);
126  // After that they should still match!
127  VerifyHeapVectorMatch(&heap, &v);
128 }
129 
130 // Tests that Reshuffle works and the heap still matches a KDVector with the
131 // same value changed. Doubles up as a test of DoublePtr.
132 TEST_F(HeapTest, RevalueTest) {
133  // Here the data element of the pair is a DoublePtr, which links the entries
134  // in the vector and heap, and we test a MAX heap.
135  typedef KDPairDec<int, DoublePtr> PtrPair;
137  std::vector<PtrPair> v;
138  // Push the test data onto both the heap and the vector.
139  for (int i : test_data) {
140  PtrPair h_pair;
141  h_pair.key() = i;
142  PtrPair v_pair;
143  v_pair.key() = i;
144  h_pair.data().Connect(&v_pair.data());
145  heap.Push(&h_pair);
146  v.push_back(v_pair);
147  }
148  // Test changes both ways. Index 0 is 8, so change it to -1.
149  v[0].key() = -1;
150  // v[0].data.OtherEnd() is a pointer to the data element in the appropriate
151  // heap entry, wherever it may be. We can change its value via that pointer.
152  // Without Reshuffle, that would be a terribly bad thing to do, as it violates
153  // the heap invariant, making the heap corrupt.
154  auto *pair_ptr = reinterpret_cast<PtrPair *>(v[0].data().OtherEnd());
155  pair_ptr->key() = v[0].key();
156  heap.Reshuffle(pair_ptr);
157  // Index 1 is 1. Change to 32767.
158  v[1].key() = 32767;
159  pair_ptr = reinterpret_cast<PtrPair *>(v[1].data().OtherEnd());
160  pair_ptr->key() = v[1].key();
161  heap.Reshuffle(pair_ptr);
162  // After the changes, popping the heap should still match the sorted order
163  // of the vector.
164  std::sort(v.begin(), v.end());
165  EXPECT_GT(v[0].key(), v.back().key());
166  for (auto &i : v) {
167  EXPECT_EQ(i.key(), heap.PeekTop().key());
168  EXPECT_FALSE(heap.empty());
169  heap.Pop(nullptr);
170  }
171  EXPECT_TRUE(heap.empty());
172 }
173 
174 #if 0
175 // Helper checks that the compiler rejects use of a copy constructor with
176 // a const argument and the default copy constructor is properly hidden by
177 // the non-const version.
178 static void ConstRefTest(const DoublePtr& ptr1) {
179  DoublePtr ptr2(ptr1); // Compiler error here.
180  EXPECT_EQ(&ptr2, ptr2.OtherEnd()->OtherEnd());
181  EXPECT_TRUE(ptr1.OtherEnd() == nullptr);
182 }
183 #endif
184 
185 // Tests that DoublePtr works as expected.
186 TEST_F(HeapTest, DoublePtrTest) {
187  DoublePtr ptr1;
188  DoublePtr ptr2;
189  ptr1.Connect(&ptr2);
190  // Check that the correct copy constructor is used.
191  DoublePtr ptr3(ptr1);
192  EXPECT_EQ(&ptr3, ptr3.OtherEnd()->OtherEnd());
193  EXPECT_TRUE(ptr1.OtherEnd() == nullptr);
194  // Check that the correct operator= is used.
195  ptr1 = ptr3;
196  EXPECT_EQ(&ptr1, ptr1.OtherEnd()->OtherEnd());
197  EXPECT_TRUE(ptr3.OtherEnd() == nullptr);
198 }
199 
200 } // namespace tesseract
constexpr size_t countof(T const (&)[N]) noexcept
Definition: serialis.h:42
int test_data[]
Definition: heap_test.cc:23
TEST_F(EuroText, FastLatinOCR)
bool empty() const
Definition: genericheap.h:68
bool PopWorst(Pair *entry)
Definition: genericheap.h:144
bool Pop(Pair *entry)
Definition: genericheap.h:120
const Pair & PeekTop() const
Definition: genericheap.h:108
void Reshuffle(Pair *pair)
Definition: genericheap.h:193
void Push(Pair *entry)
Definition: genericheap.h:95
Key & key()
Definition: kdpair.h:47
Data & data()
Definition: kdpair.h:41
void Connect(DoublePtr *other)
Definition: doubleptr.h:66
DoublePtr * OtherEnd() const
Definition: doubleptr.h:80
void VerifyHeapVectorMatch(GenericHeap< IntKDPair > *heap, KDVector *v)
Definition: heap_test.cc:44
~HeapTest() override
void SetUp() override
Definition: heap_test.cc:28
void PushTestData(GenericHeap< IntKDPair > *heap, KDVector *v)
Definition: heap_test.cc:35