tesseract  5.0.0-alpha-619-ge9db
indexmapbidi_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 <cmath>
13 #include <cstdio>
14 #include <string>
15 
16 #include "indexmapbidi.h"
17 
18 #include "include_gunit.h"
19 
22 
23 const int kPrimeLimit = 1000;
24 
25 namespace {
26 
27 class IndexMapBiDiTest : public testing::Test {
28  protected:
29  void SetUp() {
30  std::locale::global(std::locale(""));
31  }
32 
33  public:
34  std::string OutputNameToPath(const std::string& name) {
35  return file::JoinPath(FLAGS_test_tmpdir, name);
36  }
37  // Computes primes up to kPrimeLimit, using the sieve of Eratosthenes.
38  void ComputePrimes(IndexMapBiDi* map) {
39  map->Init(kPrimeLimit + 1, false);
40  map->SetMap(2, true);
41  // Set all the odds to true.
42  for (int i = 3; i <= kPrimeLimit; i += 2) map->SetMap(i, true);
43  int factor_limit = static_cast<int>(sqrt(1.0 + kPrimeLimit));
44  for (int f = 3; f <= factor_limit; f += 2) {
45  if (map->SparseToCompact(f) >= 0) {
46  for (int m = 2; m * f <= kPrimeLimit; ++m) map->SetMap(f * m, false);
47  }
48  }
49  map->Setup();
50  }
51 
52  void TestPrimes(const IndexMap& map) {
53  // Now all primes are mapped in the sparse map to their index.
54  // According to Wikipedia, the 168th prime is 997, and it has compact
55  // index 167 because we are indexing from 0.
56  EXPECT_EQ(167, map.SparseToCompact(997));
57  EXPECT_EQ(997, map.CompactToSparse(167));
58  // 995, 996, 998, 999 are not prime.
59  EXPECT_EQ(-1, map.SparseToCompact(995));
60  EXPECT_EQ(-1, map.SparseToCompact(996));
61  EXPECT_EQ(-1, map.SparseToCompact(998));
62  EXPECT_EQ(-1, map.SparseToCompact(999));
63  // The 167th prime is 991.
64  EXPECT_EQ(991, map.CompactToSparse(166));
65  // There are 168 primes in 0..1000.
66  EXPECT_EQ(168, map.CompactSize());
67  EXPECT_EQ(kPrimeLimit + 1, map.SparseSize());
68  }
69 };
70 
71 // Tests the sieve of Eratosthenes as a way of testing setup.
72 TEST_F(IndexMapBiDiTest, Primes) {
73  IndexMapBiDi map;
74  ComputePrimes(&map);
75  TestPrimes(map);
76  // It still works if we assign it to another.
77  IndexMapBiDi map2;
78  map2.CopyFrom(map);
79  TestPrimes(map2);
80  // Or if we assign it to a base class.
81  IndexMap base_map;
82  base_map.CopyFrom(map);
83  TestPrimes(base_map);
84  // Test file i/o too.
85  std::string filename = OutputNameToPath("primesmap");
86  FILE* fp = fopen(filename.c_str(), "wb");
87  CHECK(fp != nullptr);
88  EXPECT_TRUE(map.Serialize(fp));
89  fclose(fp);
90  fp = fopen(filename.c_str(), "rb");
91  CHECK(fp != nullptr);
92  IndexMapBiDi read_map;
93  EXPECT_TRUE(read_map.DeSerialize(false, fp));
94  fclose(fp);
95  TestPrimes(read_map);
96 }
97 
98 // Tests the many-to-one setup feature.
99 TEST_F(IndexMapBiDiTest, ManyToOne) {
100  // Test the example in the comment on CompleteMerges.
101  IndexMapBiDi map;
102  map.Init(13, false);
103  map.SetMap(2, true);
104  map.SetMap(4, true);
105  map.SetMap(7, true);
106  map.SetMap(9, true);
107  map.SetMap(11, true);
108  map.Setup();
109  map.Merge(map.SparseToCompact(2), map.SparseToCompact(9));
110  map.Merge(map.SparseToCompact(4), map.SparseToCompact(11));
111  map.CompleteMerges();
112  EXPECT_EQ(3, map.CompactSize());
113  EXPECT_EQ(13, map.SparseSize());
114  EXPECT_EQ(1, map.SparseToCompact(4));
115  EXPECT_EQ(4, map.CompactToSparse(1));
116  EXPECT_EQ(1, map.SparseToCompact(11));
117 }
118 
119 } // namespace.
file::JoinPath
static std::string JoinPath(const std::string &s1, const std::string &s2)
Definition: include_gunit.h:43
string
std::string string
Definition: equationdetect_test.cc:21
tesseract::IndexMapBiDi::CompleteMerges
void CompleteMerges()
Definition: indexmapbidi.cpp:160
tesseract::IndexMapBiDi::SparseToCompact
int SparseToCompact(int sparse_index) const override
Definition: indexmapbidi.h:138
include_gunit.h
tesseract::TEST_F
TEST_F(EquationFinderTest, IdentifySpecialText)
Definition: equationdetect_test.cc:181
tesseract::IndexMap::CompactToSparse
int CompactToSparse(int compact_index) const
Definition: indexmapbidi.h:53
tesseract::IndexMap
Definition: indexmapbidi.h:42
tesseract::IndexMap::SparseToCompact
virtual int SparseToCompact(int sparse_index) const
Definition: indexmapbidi.cpp:32
tesseract::IndexMapBiDi::Serialize
bool Serialize(FILE *fp) const
Definition: indexmapbidi.cpp:198
tesseract::IndexMapBiDi::DeSerialize
bool DeSerialize(bool swap, FILE *fp)
Definition: indexmapbidi.cpp:216
CHECK
#define CHECK(test)
Definition: include_gunit.h:57
tesseract::IndexMapBiDi::Merge
bool Merge(int compact_index1, int compact_index2)
Definition: indexmapbidi.cpp:128
FLAGS_test_tmpdir
const char * FLAGS_test_tmpdir
Definition: include_gunit.h:20
tesseract::IndexMap::CopyFrom
void CopyFrom(const IndexMap &src)
Definition: indexmapbidi.cpp:38
tesseract::IndexMapBiDi::Setup
void Setup()
Definition: indexmapbidi.cpp:102
tesseract::IndexMapBiDi::CopyFrom
void CopyFrom(const IndexMapBiDi &src)
Definition: indexmapbidi.cpp:119
tesseract::IndexMap::SparseSize
virtual int SparseSize() const
Definition: indexmapbidi.h:57
tesseract::IndexMapBiDi::SparseSize
int SparseSize() const override
Definition: indexmapbidi.h:142
tesseract::IndexMapBiDi
Definition: indexmapbidi.h:102
tesseract::IndexMapBiDi::Init
void Init(int size, bool all_mapped)
Definition: indexmapbidi.cpp:86
tesseract::IndexMapBiDi::SetMap
void SetMap(int sparse_index, bool mapped)
Definition: indexmapbidi.cpp:95
tesseract::IndexMap::CompactSize
int CompactSize() const
Definition: indexmapbidi.h:61
kPrimeLimit
const int kPrimeLimit
Definition: indexmapbidi_test.cc:23
indexmapbidi.h