tesseract  5.0.0
nthitem_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 "kdpair.h"
13 
14 #include "include_gunit.h"
15 
16 namespace tesseract {
17 
18 int test_data[] = {8, 1, 2, -4, 7, 9, 65536, 4, 9, 0, -32767, 6, 7};
19 
20 // The fixture for testing GenericHeap and DoublePtr.
21 class NthItemTest : public testing::Test {
22 protected:
23  void SetUp() override {
24  std::locale::global(std::locale(""));
25  }
26 
27 public:
28  ~NthItemTest() override;
29  // Pushes the test data onto the KDVector.
31  for (size_t i = 0; i < countof(test_data); ++i) {
32  IntKDPair pair(test_data[i], i);
33  v->push_back(pair);
34  }
35  }
36 };
37 
38 // Destructor.
39 // It is defined here, so the compiler can create a single vtable
40 // instead of a weak vtable (fixes compiler warning).
41 NthItemTest::~NthItemTest() = default;
42 
43 // Tests basic results.
44 TEST_F(NthItemTest, GeneralTest) {
45  KDVector v;
46  // Push the test data onto the KDVector.
47  PushTestData(&v);
48  // Get the min item.
49  size_t index = 0;
50  std::nth_element(v.begin(), v.begin() + index, v.end());
51  // The result is -32767.
52  EXPECT_EQ(-32767, v[index].key());
53  // Get the max item.
54  index = v.size() - 1;
55  std::nth_element(v.begin(), v.begin() + index, v.end());
56  // The result is 65536.
57  EXPECT_EQ(65536, v[index].key());
58 }
59 
60 // Tests results on boring data with lots of duplication.
61 TEST_F(NthItemTest, BoringTest) {
62  KDVector v;
63  // Push the test data onto the KDVector.
64  int test_data[] = {8, 8, 8, 8, 8, 7, 7, 7, 7};
65  for (size_t i = 0; i < countof(test_data); ++i) {
66  IntKDPair pair(test_data[i], i);
67  v.push_back(pair);
68  }
69  // The 3rd item is 7 but the 4th is 8..
70  size_t index = 3;
71  std::nth_element(v.begin(), v.begin() + index, v.end());
72  // The result is 7.
73  EXPECT_EQ(7, v[index].key());
74  index = 4;
75  std::nth_element(v.begin(), v.begin() + index, v.end());
76  // The result is 8.
77  EXPECT_EQ(8, v[index].key());
78  // Get the min item.
79  index = 0;
80  std::nth_element(v.begin(), v.begin() + index, v.end());
81  // The result is 7.
82  EXPECT_EQ(7, v[index].key());
83  // Get the max item.
84  index = v.size() - 1;
85  std::nth_element(v.begin(), v.begin() + index, v.end());
86  // The result is 8.
87  EXPECT_EQ(8, v[index].key());
88 }
89 
90 // Tests that a unique median in an odd-size array is found correctly.
91 TEST_F(NthItemTest, UniqueTest) {
92  KDVector v;
93  // Push the test data onto the KDVector.
94  PushTestData(&v);
95  // Get the median item.
96  size_t index = v.size() / 2;
97  std::nth_element(v.begin(), v.begin() + index, v.end());
98  // The result is 6, it started out at index 11.
99  EXPECT_EQ(6, v[index].key());
100  EXPECT_EQ(11, v[index].data());
101 }
102 
103 // Tests that an equal median is found correctly.
104 TEST_F(NthItemTest, EqualTest) {
105  KDVector v;
106  // Push the test data onto the KDVector.
107  PushTestData(&v);
108  // Add an extra 8. This makes the median 7.
109  IntKDPair pair(8, 13);
110  v.push_back(pair);
111  // Get the median item.
112  size_t index = v.size() / 2;
113  std::nth_element(v.begin(), v.begin() + index, v.end());
114  // The result is 7, it started out at index 4 or 12.
115  EXPECT_EQ(7, v[index].key());
116  EXPECT_TRUE(v[index].data() == 4 || v[index].data() == 12);
117 }
118 
119 } // 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)
void SetUp() override
Definition: nthitem_test.cc:23
void PushTestData(KDVector *v)
Definition: nthitem_test.cc:30