1#ifndef DAWGDIC_GUIDE_BUILDER_H
2#define DAWGDIC_GUIDE_BUILDER_H
3
4#include "guide.h"
5#include "dawg.h"
6#include "dictionary.h"
7
8#include <vector>
9
10namespace dawgdic {
11
12class GuideBuilder {
13 public:
14 // Builds a dictionary for completing keys.
15 static bool Build(const Dawg &dawg, const Dictionary &dic, Guide *guide) {
16 GuideBuilder builder(dawg, dic, guide);
17 return builder.BuildGuide();
18 }
19
20 private:
21 const Dawg &dawg_;
22 const Dictionary &dic_;
23 Guide *guide_;
24
25 std::vector<GuideUnit> units_;
26 std::vector<UCharType> is_fixed_table_;
27
28 // Disallows copies.
29 GuideBuilder(const GuideBuilder &);
30 GuideBuilder &operator=(const GuideBuilder &);
31
32 GuideBuilder(const Dawg &dawg, const Dictionary &dic, Guide *guide)
33 : dawg_(dawg), dic_(dic), guide_(guide), units_(), is_fixed_table_() {}
34
35 bool BuildGuide() {
36 // Initializes units and flags.
37 units_.resize(dic_.size());
38 is_fixed_table_.resize(dic_.size() / 8, '\0');
39
40 if (dawg_.size() <= 1) {
41 return true;
42 }
43
44 if (!BuildGuide(dawg_.root(), dic_.root())) {
45 return false;
46 }
47
48 guide_->SwapUnitsBuf(&units_);
49 return true;
50 }
51
52 // Builds a guide recursively.
53 bool BuildGuide(BaseType dawg_index, BaseType dic_index) {
54 if (is_fixed(dic_index)) {
55 return true;
56 }
57 set_is_fixed(dic_index);
58
59 // Finds the first non-terminal child.
60 BaseType dawg_child_index = dawg_.child(dawg_index);
61 if (dawg_.label(dawg_child_index) == '\0') {
62 dawg_child_index = dawg_.sibling(dawg_child_index);
63 if (dawg_child_index == 0) {
64 return true;
65 }
66 }
67 units_[dic_index].set_child(dawg_.label(dawg_child_index));
68
69 do {
70 UCharType child_label = dawg_.label(dawg_child_index);
71 BaseType dic_child_index = dic_index;
72 if (!dic_.Follow(child_label, &dic_child_index)) {
73 return false;
74 }
75
76 if (!BuildGuide(dawg_child_index, dic_child_index)) {
77 return false;
78 }
79
80 BaseType dawg_sibling_index = dawg_.sibling(dawg_child_index);
81 UCharType sibling_label = dawg_.label(dawg_sibling_index);
82 if (dawg_sibling_index != 0) {
83 units_[dic_child_index].set_sibling(sibling_label);
84 }
85
86 dawg_child_index = dawg_sibling_index;
87 } while (dawg_child_index != 0);
88
89 return true;
90 }
91
92 void set_is_fixed(BaseType index) {
93 is_fixed_table_[index / 8] |= 1 << (index % 8);
94 }
95
96 bool is_fixed(BaseType index) const {
97 return (is_fixed_table_[index / 8] & (1 << (index % 8))) != 0;
98 }
99};
100
101} // namespace dawgdic
102
103#endif // DAWGDIC_GUIDE_BUILDER_H
104