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 | |
14 | namespace { |
15 | |
16 | static const std::size_t NUM_KEYS = 1 << 16; |
17 | static const std::size_t KEY_LENGTH = 6; |
18 | static const int MAX_VALUE = 100; |
19 | |
20 | class 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 | |
33 | void 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 | |
51 | void 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 | |
58 | bool 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 | |
90 | bool 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 | |
106 | bool 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 | |
139 | int 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 | |