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