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
13namespace dawgdic {
14
15class 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