tesseract  5.0.0-alpha-619-ge9db
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 <string>
13 #include <utility>
14 
15 #include "doubleptr.h"
16 #include "genericheap.h"
18 #include "kdpair.h"
19 
20 #include "include_gunit.h"
21 
22 namespace tesseract {
23 
24 int test_data[] = {8, 1, 2, -4, 7, 9, 65536, 4, 9, 0};
25 
26 // The fixture for testing GenericHeap and DoublePtr.
27 class HeapTest : public testing::Test {
28  protected:
29  void SetUp() {
30  std::locale::global(std::locale(""));
31  }
32 
33  public:
34  virtual ~HeapTest();
35  // Pushes the test data onto both the heap and the KDVector.
37  for (size_t i = 0; i < ARRAYSIZE(test_data); ++i) {
38  IntKDPair pair(test_data[i], i);
39  heap->Push(&pair);
40  v->push_back(pair);
41  }
42  }
43  // Verifies that the data in the heap matches the vector (after sorting) by
44  // popping everything off the heap.
46  EXPECT_FALSE(heap->empty());
47  EXPECT_EQ(heap->size(), v->size());
48  // Sort the vector and check that the keys come out of the heap in the same
49  // order as v.
50  // Also check that the indices match, except for 9, which is duplicated.
51  v->sort();
52  // Check that we have increasing order.
53  EXPECT_LT((*v)[0].key, v->back().key);
54  for (int i = 0; i < v->size(); ++i) {
55  EXPECT_EQ((*v)[i].key, heap->PeekTop().key);
56  // Indices don't necessarily match for equal keys, so don't test them.
57  if (i + 1 < v->size() && (*v)[i + 1].key == (*v)[i].key) {
58  while (i + 1 < v->size() && (*v)[i + 1].key == (*v)[i].key) {
59  heap->Pop(nullptr);
60  ++i;
61  EXPECT_FALSE(heap->empty());
62  EXPECT_EQ((*v)[i].key, heap->PeekTop().key);
63  }
64  } else {
65  // The indices must also match if the key is unique.
66  EXPECT_EQ((*v)[i].data, heap->PeekTop().data);
67  }
68  EXPECT_FALSE(heap->empty());
69  EXPECT_TRUE(heap->Pop(nullptr));
70  }
71  EXPECT_TRUE(heap->empty());
72  }
73 };
74 
75 // Destructor.
76 // It is defined here, so the compiler can create a single vtable
77 // instead of a weak vtable (fixes compiler warning).
78 HeapTest::~HeapTest() = default;
79 
80 // Tests that a sort using a GenericHeap matches the result of a sort using
81 // a KDVector.
82 TEST_F(HeapTest, SortTest) {
84  EXPECT_TRUE(heap.empty());
85  KDVector v;
86  EXPECT_EQ(heap.size(), v.size());
87  // Push the test data onto both the heap and the KDVector.
88  PushTestData(&heap, &v);
89  VerifyHeapVectorMatch(&heap, &v);
90 }
91 
92 // Tests that pushing some stuff, popping some stuff, and then pushing more
93 // stuff results in output that matches the sort using a KDVector.
94 // a KDVector.
95 TEST_F(HeapTest, MixedTest) {
97  KDVector v;
98  // Push the test data onto both the heap and the KDVector.
99  PushTestData(&heap, &v);
100  // Sort the vector and remove the first 5 values from both heap and v.
101  v.sort();
102  for (int i = 0; i < 5; ++i) {
103  heap.Pop(nullptr);
104  v.remove(0);
105  }
106  // Push the test data onto both the heap and the KDVector.
107  PushTestData(&heap, &v);
108  // Heap and vector should still match!
109  VerifyHeapVectorMatch(&heap, &v);
110 }
111 
112 // Tests that PopWorst still leaves the heap in a state such that it still
113 // matches a sorted KDVector.
114 TEST_F(HeapTest, PopWorstTest) {
116  KDVector v;
117  // Push the test data onto both the heap and the KDVector.
118  PushTestData(&heap, &v);
119  // Get the worst element off the heap.
120  IntKDPair pair;
121  heap.PopWorst(&pair);
122  EXPECT_EQ(pair.key, 65536);
123  EXPECT_EQ(pair.data, 6);
124  // Sort and remove the worst element from the vector.
125  v.sort();
126  v.truncate(v.size() - 1);
127  // After that they should still match!
128  VerifyHeapVectorMatch(&heap, &v);
129 }
130 
131 // Tests that Reshuffle works and the heap still matches a KDVector with the
132 // same value changed. Doubles up as a test of DoublePtr.
133 TEST_F(HeapTest, RevalueTest) {
134  // Here the data element of the pair is a DoublePtr, which links the entries
135  // in the vector and heap, and we test a MAX heap.
136  typedef KDPairDec<int, DoublePtr> PtrPair;
139  // Push the test data onto both the heap and the vector.
140  for (size_t i = 0; i < ARRAYSIZE(test_data); ++i) {
141  PtrPair h_pair;
142  h_pair.key = test_data[i];
143  PtrPair v_pair;
144  v_pair.key = test_data[i];
145  h_pair.data.Connect(&v_pair.data);
146  heap.Push(&h_pair);
147  v.push_back(v_pair);
148  }
149  // Test changes both ways. Index 0 is 8, so change it to -1.
150  v[0].key = -1;
151  // v[0].data.OtherEnd() is a pointer to the data element in the appropriate
152  // heap entry, wherever it may be. We can change its value via that pointer.
153  // Without Reshuffle, that would be a terribly bad thing to do, as it violates
154  // the heap invariant, making the heap corrupt.
155  PtrPair* pair_ptr = PtrPair::RecastDataPointer(v[0].data.OtherEnd());
156  pair_ptr->key = v[0].key;
157  heap.Reshuffle(pair_ptr);
158  // Index 1 is 1. Change to 32767.
159  v[1].key = 32767;
160  pair_ptr = PtrPair::RecastDataPointer(v[1].data.OtherEnd());
161  pair_ptr->key = v[1].key;
162  heap.Reshuffle(pair_ptr);
163  // After the changes, popping the heap should still match the sorted order
164  // of the vector.
165  v.sort();
166  EXPECT_GT(v[0].key, v.back().key);
167  for (int i = 0; i < v.size(); ++i) {
168  EXPECT_EQ(v[i].key, heap.PeekTop().key);
169  EXPECT_FALSE(heap.empty());
170  heap.Pop(nullptr);
171  }
172  EXPECT_TRUE(heap.empty());
173 }
174 
175 #if 0
176 // Helper checks that the compiler rejects use of a copy constructor with
177 // a const argument and the default copy constructor is properly hidden by
178 // the non-const version.
179 static void ConstRefTest(const DoublePtr& ptr1) {
180  DoublePtr ptr2(ptr1); // Compiler error here.
181  EXPECT_EQ(&ptr2, ptr2.OtherEnd()->OtherEnd());
182  EXPECT_TRUE(ptr1.OtherEnd() == nullptr);
183 }
184 #endif
185 
186 // Tests that DoublePtr works as expected.
187 TEST_F(HeapTest, DoublePtrTest) {
188  DoublePtr ptr1;
189  DoublePtr ptr2;
190  ptr1.Connect(&ptr2);
191  // Check that the correct copy constructor is used.
192  DoublePtr ptr3(ptr1);
193  EXPECT_EQ(&ptr3, ptr3.OtherEnd()->OtherEnd());
194  EXPECT_TRUE(ptr1.OtherEnd() == nullptr);
195  // Check that the correct operator= is used.
196  ptr1 = ptr3;
197  EXPECT_EQ(&ptr1, ptr1.OtherEnd()->OtherEnd());
198  EXPECT_TRUE(ptr3.OtherEnd() == nullptr);
199 }
200 
201 } // namespace tesseract
tesseract::GenericHeap
Definition: genericheap.h:58
GenericVector::remove
void remove(int index)
Definition: genericvector.h:765
tesseract::GenericHeap::Pop
bool Pop(Pair *entry)
Definition: genericheap.h:118
tesseract::test_data
int test_data[]
Definition: heap_test.cc:24
tesseract::GenericHeap::PeekTop
const Pair & PeekTop() const
Definition: genericheap.h:108
tesseract::HeapTest
Definition: heap_test.cc:27
tesseract::HeapTest::VerifyHeapVectorMatch
void VerifyHeapVectorMatch(GenericHeap< IntKDPair > *heap, KDVector *v)
Definition: heap_test.cc:45
tesseract::GenericHeap::PopWorst
bool PopWorst(Pair *entry)
Definition: genericheap.h:140
ARRAYSIZE
#define ARRAYSIZE(arr)
Definition: include_gunit.h:53
include_gunit.h
tesseract::TEST_F
TEST_F(EquationFinderTest, IdentifySpecialText)
Definition: equationdetect_test.cc:181
tesseract::HeapTest::~HeapTest
virtual ~HeapTest()
tesseract::DoublePtr
Definition: doubleptr.h:41
tesseract::KDPair::key
Key key
Definition: kdpair.h:46
GenericVector::back
T & back() const
Definition: genericvector.h:728
tesseract::GenericHeap::size
int size() const
Definition: genericheap.h:71
genericvector.h
GenericVector::push_back
int push_back(T object)
Definition: genericvector.h:799
tesseract::DoublePtr::OtherEnd
DoublePtr * OtherEnd() const
Definition: doubleptr.h:81
tesseract::KDPair::data
Data data
Definition: kdpair.h:45
tesseract::KDPairDec
Definition: kdpair.h:67
tesseract::KDVector
Definition: kdpair.h:182
kdpair.h
tesseract
Definition: baseapi.h:65
doubleptr.h
GenericVector
Definition: baseapi.h:40
tesseract::KDPairInc
Definition: kdpair.h:51
tesseract::DoublePtr::Connect
void Connect(DoublePtr *other)
Definition: doubleptr.h:67
tesseract::GenericHeap::Push
void Push(Pair *entry)
Definition: genericheap.h:95
tesseract::GenericHeap::Reshuffle
void Reshuffle(Pair *pair)
Definition: genericheap.h:182
tesseract::HeapTest::PushTestData
void PushTestData(GenericHeap< IntKDPair > *heap, KDVector *v)
Definition: heap_test.cc:36
GenericVector::truncate
void truncate(int size)
Definition: genericvector.h:132
tesseract::HeapTest::SetUp
void SetUp()
Definition: heap_test.cc:29
GenericVector::sort
void sort()
Definition: genericvector.h:1102
GenericVector::size
int size() const
Definition: genericvector.h:71
tesseract::GenericHeap::empty
bool empty() const
Definition: genericheap.h:68
genericheap.h