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 | |
10 | namespace dawgdic { |
11 | |
12 | class 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 | |