1#include <dawgdic/dawg-builder.h>
2#include <dawgdic/dictionary-builder.h>
3#include <dawgdic/guide-builder.h>
4#include <dawgdic/ranked-completer.h>
5#include <dawgdic/ranked-guide-builder.h>
6
7#include <algorithm>
8#include <cstdlib>
9#include <ctime>
10#include <iostream>
11#include <string>
12#include <vector>
13
14namespace {
15
16static const std::size_t NUM_KEYS = 1 << 16;
17static const std::size_t KEY_LENGTH = 6;
18static const int MAX_VALUE = 100;
19
20class Comparer {
21 public:
22 explicit Comparer(const std::vector<int> &values) : values_(&values) {}
23
24 bool operator()(const dawgdic::ValueType &lhs,
25 const dawgdic::ValueType &rhs) const {
26 return (*values_)[lhs] < (*values_)[rhs];
27 }
28
29 private:
30 const std::vector<int> *values_;
31};
32
33void GenerateRandomKeys(std::size_t num_keys, std::size_t length,
34 std::vector<std::string> *keys) {
35 std::vector<char> key(length);
36 keys->resize(num_keys);
37 for (std::size_t key_id = 0; key_id < num_keys; ++key_id) {
38 for (std::size_t i = 0; i < length; ++i) {
39 key[i] = 'A' + (std::rand() % ('Z' - 'A' + 1));
40 }
41 (*keys)[key_id].assign(&key[0], length);
42 }
43
44 // Sorts keys, and then removes repeated keys.
45 std::sort(keys->begin(), keys->end());
46 std::vector<std::string>::iterator unique_keys_end =
47 std::unique(keys->begin(), keys->end());
48 keys->erase(unique_keys_end, keys->end());
49}
50
51void GenerateRandomValues(std::size_t num_values, std::vector<int> *values) {
52 values->resize(num_values);
53 for (std::size_t i = 0; i < num_values; ++i) {
54 (*values)[i] = std::rand() % MAX_VALUE;
55 }
56}
57
58bool BuildDictionary(const std::vector<std::string> &keys,
59 const std::vector<int> &values, dawgdic::Dictionary *dic,
60 dawgdic::RankedGuide *guide) {
61 dawgdic::DawgBuilder builder;
62 for (std::size_t i = 0; i < keys.size(); ++i) {
63 if (!builder.Insert(keys[i].c_str(), static_cast<dawgdic::ValueType>(i))) {
64 std::cerr << "error: failed to insert key: "
65 << keys[i] << std::endl;
66 return false;
67 }
68 }
69
70 dawgdic::Dawg dawg;
71 if (!builder.Finish(&dawg)) {
72 std::cerr << "error: failed to finish building Dawg" << std::endl;
73 return false;
74 }
75
76 if (!dawgdic::DictionaryBuilder::Build(dawg, dic)) {
77 std::cerr << "error: failed to build Dictionary" << std::endl;
78 return false;
79 }
80
81 if (!dawgdic::RankedGuideBuilder::Build(dawg, *dic, guide,
82 Comparer(values))) {
83 std::cerr << "error: failed to build RankedGuide" << std::endl;
84 return false;
85 }
86
87 return true;
88}
89
90bool TestDictionary(const dawgdic::Dictionary &dic,
91 const std::vector<std::string> &keys) {
92 for (std::size_t i = 0; i < keys.size(); ++i) {
93 dawgdic::ValueType value;
94 if (!dic.Find(keys[i].c_str(), &value)) {
95 std::cerr << "error: failed to find key: " << keys[i] << std::endl;
96 return false;
97 } else if (value != static_cast<dawgdic::ValueType>(i)) {
98 std::cerr << "error: wrong value: "
99 << value << '/' << i << std::endl;
100 return false;
101 }
102 }
103 return true;
104}
105
106bool TestCompleter(const dawgdic::Dictionary &dic,
107 const dawgdic::RankedGuide &guide,
108 const std::vector<std::string> &keys,
109 const std::vector<int> &values) {
110 dawgdic::RankedCompleterBase<Comparer> completer(dic, guide,
111 Comparer(values));
112
113 for (char first_label = 'A'; first_label <= 'Z'; ++first_label) {
114 dawgdic::BaseType index = dic.root();
115 if (!dic.Follow(first_label, &index)) {
116 continue;
117 }
118
119 int prev_value = MAX_VALUE;
120 completer.Start(index, &first_label, 1);
121 while (completer.Next()) {
122 int value = values[completer.value()];
123 if (value > prev_value) {
124 std::cerr << "error: invalid value order: "
125 << value << " -> " << prev_value << std::endl;
126 return false;
127 }
128 prev_value = value;
129
130// std::cout << completer.key() << ": " << value << std::endl;
131 }
132 }
133
134 return true;
135}
136
137} // namespace
138
139int main() {
140 // Initializes random number generator's seed.
141 std::srand(std::time(NULL));
142
143 std::vector<std::string> keys;
144 GenerateRandomKeys(NUM_KEYS, KEY_LENGTH, &keys);
145 std::cerr << "no. unique keys: " << keys.size() << std::endl;
146
147 std::vector<int> values;
148 GenerateRandomValues(keys.size(), &values);
149
150// for (std::size_t i = 0; i < keys.size(); ++i)
151// std::cout << i << ": " << keys[i] << ": " << values[i] << std::endl;
152
153 dawgdic::Dictionary dic;
154 dawgdic::RankedGuide guide;
155 if (!BuildDictionary(keys, values, &dic, &guide)) {
156 return 2;
157 }
158
159 if (!TestDictionary(dic, keys)) {
160 return 3;
161 }
162
163 if (!TestCompleter(dic, guide, keys, values)) {
164 return 4;
165 }
166
167 return 0;
168}
169