1 | #ifndef DAWGDIC_RANKED_GUIDE_BUILDER_H |
2 | #define DAWGDIC_RANKED_GUIDE_BUILDER_H |
3 | |
4 | #include "dawg.h" |
5 | #include "dictionary.h" |
6 | #include "ranked-guide.h" |
7 | #include "ranked-guide-link.h" |
8 | |
9 | #include <algorithm> |
10 | #include <functional> |
11 | #include <vector> |
12 | |
13 | namespace dawgdic { |
14 | |
15 | class RankedGuideBuilder { |
16 | public: |
17 | // Builds a dictionary for completing keys. |
18 | static bool Build(const Dawg &dawg, const Dictionary &dic, |
19 | RankedGuide *guide) { |
20 | return Build(dawg, dic, guide, std::less<ValueType>()); |
21 | } |
22 | |
23 | // Builds a dictionary for completing keys. |
24 | template <typename VALUE_COMPARER_TYPE> |
25 | static bool Build(const Dawg &dawg, const Dictionary &dic, |
26 | RankedGuide *guide, VALUE_COMPARER_TYPE value_comparer) { |
27 | RankedGuideBuilder builder(dawg, dic, guide); |
28 | return builder.BuildRankedGuide(value_comparer); |
29 | } |
30 | |
31 | private: |
32 | const Dawg &dawg_; |
33 | const Dictionary &dic_; |
34 | RankedGuide *guide_; |
35 | |
36 | std::vector<RankedGuideUnit> units_; |
37 | std::vector<RankedGuideLink> links_; |
38 | std::vector<UCharType> is_fixed_table_; |
39 | |
40 | // Disallows copies. |
41 | RankedGuideBuilder(const RankedGuideBuilder &); |
42 | RankedGuideBuilder &operator=(const RankedGuideBuilder &); |
43 | |
44 | RankedGuideBuilder(const Dawg &dawg, const Dictionary &dic, |
45 | RankedGuide *guide) |
46 | : dawg_(dawg), dic_(dic), guide_(guide), |
47 | units_(), links_(), is_fixed_table_() {} |
48 | |
49 | template <typename VALUE_COMPARER_TYPE> |
50 | bool BuildRankedGuide(VALUE_COMPARER_TYPE value_comparer) { |
51 | // Initializes units and flags. |
52 | units_.resize(dic_.size()); |
53 | is_fixed_table_.resize(dic_.size() / 8, '\0'); |
54 | |
55 | if (dawg_.size() <= 1) { |
56 | return true; |
57 | } |
58 | |
59 | ValueType max_value = -1; |
60 | if (!BuildRankedGuide(dawg_.root(), dic_.root(), |
61 | &max_value, value_comparer)) { |
62 | return false; |
63 | } |
64 | |
65 | guide_->SwapUnitsBuf(&units_); |
66 | return true; |
67 | } |
68 | |
69 | // Builds a guide recursively. |
70 | template <typename VALUE_COMPARER_TYPE> |
71 | bool BuildRankedGuide(BaseType dawg_index, BaseType dic_index, |
72 | ValueType *max_value, |
73 | VALUE_COMPARER_TYPE value_comparer) { |
74 | if (is_fixed(dic_index)) { |
75 | return FindMaxValue(dic_index, max_value); |
76 | } |
77 | set_is_fixed(dic_index); |
78 | |
79 | SizeType initial_num_links = links_.size(); |
80 | |
81 | // Enumerates links to the next states. |
82 | if (!EnumerateLinks(dawg_index, dic_index, value_comparer)) { |
83 | return false; |
84 | } |
85 | |
86 | std::stable_sort(links_.begin() + initial_num_links, links_.end(), |
87 | RankedGuideLink::MakeComparer(value_comparer)); |
88 | |
89 | // Reflects links into units. |
90 | if (!TurnLinksToUnits(dic_index, initial_num_links)) { |
91 | return false; |
92 | } |
93 | |
94 | *max_value = links_[initial_num_links].value(); |
95 | links_.resize(initial_num_links); |
96 | |
97 | return true; |
98 | } |
99 | |
100 | // Finds the maximum value by using fixed units. |
101 | bool FindMaxValue(BaseType dic_index, ValueType *max_value) const { |
102 | while (units_[dic_index].child() != '\0') { |
103 | UCharType child_label = units_[dic_index].child(); |
104 | if (!dic_.Follow(child_label, &dic_index)) { |
105 | return false; |
106 | } |
107 | } |
108 | if (!dic_.has_value(dic_index)) { |
109 | return false; |
110 | } |
111 | *max_value = dic_.value(dic_index); |
112 | return true; |
113 | } |
114 | |
115 | // Enumerates links to the next states. |
116 | template <typename VALUE_COMPARER_TYPE> |
117 | bool EnumerateLinks(BaseType dawg_index, BaseType dic_index, |
118 | VALUE_COMPARER_TYPE value_comparer) { |
119 | for (BaseType dawg_child_index = dawg_.child(dawg_index); |
120 | dawg_child_index != 0; |
121 | dawg_child_index = dawg_.sibling(dawg_child_index)) { |
122 | ValueType value = -1; |
123 | UCharType child_label = dawg_.label(dawg_child_index); |
124 | if (child_label == '\0') { |
125 | if (!dic_.has_value(dic_index)) { |
126 | return false; |
127 | } |
128 | value = dic_.value(dic_index); |
129 | } else { |
130 | BaseType dic_child_index = dic_index; |
131 | if (!dic_.Follow(child_label, &dic_child_index)) { |
132 | return false; |
133 | } |
134 | |
135 | if (!BuildRankedGuide(dawg_child_index, dic_child_index, |
136 | &value, value_comparer)) { |
137 | return false; |
138 | } |
139 | } |
140 | links_.push_back(RankedGuideLink(child_label, value)); |
141 | } |
142 | |
143 | return true; |
144 | } |
145 | |
146 | // Modifies units. |
147 | bool TurnLinksToUnits(BaseType dic_index, SizeType links_begin) { |
148 | // The first child. |
149 | UCharType first_label = links_[links_begin].label(); |
150 | units_[dic_index].set_child(first_label); |
151 | BaseType dic_child_index = FollowWithoutCheck(dic_index, first_label); |
152 | |
153 | // Other children. |
154 | for (SizeType i = links_begin + 1; i < links_.size(); ++i) { |
155 | UCharType sibling_label = links_[i].label(); |
156 | |
157 | BaseType dic_sibling_index = |
158 | FollowWithoutCheck(dic_index, sibling_label); |
159 | units_[dic_child_index].set_sibling(sibling_label); |
160 | dic_child_index = dic_sibling_index; |
161 | } |
162 | |
163 | return true; |
164 | } |
165 | |
166 | // Follows a transition without any check. |
167 | BaseType FollowWithoutCheck(BaseType index, UCharType label) const { |
168 | return index ^ dic_.units()[index].offset() ^ label; |
169 | } |
170 | |
171 | void set_is_fixed(BaseType index) { |
172 | is_fixed_table_[index / 8] |= 1 << (index % 8); |
173 | } |
174 | |
175 | bool is_fixed(BaseType index) const { |
176 | return (is_fixed_table_[index / 8] & (1 << (index % 8))) != 0; |
177 | } |
178 | }; |
179 | |
180 | } // namespace dawgdic |
181 | |
182 | #endif // DAWGDIC_RANKED_GUIDE_BUILDER_H |
183 | |