20 #ifndef FST_EXTENSIONS_MPDT_MPDT_H_ 21 #define FST_EXTENSIONS_MPDT_MPDT_H_ 23 #include <sys/types.h> 40 #include <unordered_map> 53 template <
typename StackId,
typename Level, Level nlevels>
60 template <
typename Level>
65 template <
typename Level>
68 KeyPair(Level level,
size_t id) : level_(level), underlying_id_(id) {}
71 return level_ == rhs.level_ && underlying_id_ == rhs.underlying_id_;
77 size_t underlying_id_;
80 template <
typename Level>
83 return std::hash<Level>()(keypair.level_) ^
84 (std::hash<size_t>()(keypair.underlying_id_) << 1);
88 template <
typename StackId,
typename Level, Level nlevels = 2,
96 MPdtStack(
const std::vector<std::pair<Label, Label>> &parens,
97 const std::vector<Level> &assignments);
102 : error_(other.error_),
103 min_paren_(other.min_paren_),
104 max_paren_(other.max_paren_),
105 paren_levels_(other.paren_levels_),
106 parens_(other.parens_),
107 paren_map_(other.paren_map_),
108 paren_id_map_(other.paren_id_map_),
109 config_to_stack_id_map_(other.config_to_stack_id_map_),
110 stack_id_to_config_map_(other.stack_id_to_config_map_),
111 next_stack_id_(other.next_stack_id_),
112 stacks_(other.stacks_) {}
123 StackId Find(StackId stack_id,
Label label);
130 ssize_t
Top(StackId stack_id)
const {
131 if (stack_id == -1)
return -1;
132 const auto config = InternalStackIds(stack_id);
134 StackId underlying_id = -1;
135 for (; level < nlevels; ++level) {
136 if (!Empty(config, level)) {
137 underlying_id = stacks_[level]->Top(config[level]);
141 if (underlying_id == -1)
return -1;
142 const auto it = paren_id_map_.find(
KeyPair<Level>(level, underlying_id));
143 if (it == paren_id_map_.end())
return -1;
148 const auto it = paren_map_.find(label);
149 return it != paren_map_.end() ? it->second : -1;
159 const auto it = config_to_stack_id_map_.find(config);
161 if (it == config_to_stack_id_map_.end()) {
162 result = next_stack_id_++;
163 config_to_stack_id_map_.insert(
164 std::pair<Config, StackId>(config, result));
165 stack_id_to_config_map_[result] = config;
174 auto it = stack_id_to_config_map_.find(stack_id);
175 if (it == stack_id_to_config_map_.end()) {
176 it = stack_id_to_config_map_.find(-1);
182 return config[level] <= 0;
186 for (Level level = 0; level < nlevels; ++level) {
187 if (!Empty(config, level))
return false;
197 std::unordered_map<Label, Label> paren_levels_;
198 std::vector<std::pair<Label, Label>> parens_;
199 std::unordered_map<Label, size_t> paren_map_;
205 std::unordered_map<StackId, Config> stack_id_to_config_map_;
206 StackId next_stack_id_;
208 std::array<std::optional<PdtStack<StackId, Label>>, nlevels> stacks_;
211 template <
typename StackId,
typename Level, Level nlevels, MPdtType restrict>
213 const std::vector<std::pair<Level, Level>> &parens,
214 const std::vector<Level> &assignments)
221 if (parens.size() != assignments.size()) {
222 FSTERROR() <<
"MPdtStack: Parens of different size from assignments";
226 std::array<std::vector<std::pair<Label, Label>>, nlevels> vectors;
227 for (Level i = 0; i < assignments.size(); ++i) {
230 const auto level = assignments[i] - 1;
231 if (level < 0 || level >= nlevels) {
232 FSTERROR() <<
"MPdtStack: Specified level " << level <<
" out of bounds";
236 const auto &pair = parens[i];
237 vectors[level].push_back(pair);
238 paren_levels_[pair.first] = level;
239 paren_levels_[pair.second] = level;
240 paren_map_[pair.first] = i;
241 paren_map_[pair.second] = i;
243 paren_id_map_[key] = i;
244 if (min_paren_ ==
kNoLabel || pair.first < min_paren_) {
245 min_paren_ = pair.first;
247 if (pair.second < min_paren_) min_paren_ = pair.second;
248 if (max_paren_ ==
kNoLabel || pair.first > max_paren_) {
249 max_paren_ = pair.first;
251 if (pair.second > max_paren_) max_paren_ = pair.second;
256 for (Level level = 0; level < nlevels; ++level) {
257 stacks_[level].emplace(vectors[level]);
261 config_to_stack_id_map_[neg_one] = -1;
262 config_to_stack_id_map_[zero] = 0;
263 stack_id_to_config_map_[-1] = neg_one;
264 stack_id_to_config_map_[0] = zero;
267 template <
typename StackId,
typename Level, Level nlevels, MPdtType restrict>
271 if (min_paren_ ==
kNoLabel || label < min_paren_ || label > max_paren_) {
274 const auto it = paren_map_.find(label);
276 if (it == paren_map_.end())
return stack_id;
277 ssize_t paren_id = it->second;
281 const auto level = paren_levels_.find(label)->second;
287 if (label == parens_[paren_id].first) {
289 for (Level upper_level = 0; upper_level < level; ++upper_level) {
290 if (!
Empty(config, upper_level))
return -1;
299 for (Level lower_level = 0; lower_level < level; ++lower_level) {
300 if (!
Empty(config, lower_level))
return -1;
303 const auto nid = stacks_[level]->Find(config[level], label);
311 nconfig[level] = nid;
319 #endif // FST_EXTENSIONS_MPDT_MPDT_H_ MPdtStack & operator=(const MPdtStack &other)
size_t operator()(const KeyPair< Level > &keypair) const
MPdtStack(const MPdtStack &other)
std::array< StackId, nlevels > StackConfig
ssize_t Top(StackId stack_id) const
const Config InternalStackIds(StackId stack_id) const
std::map< Config, StackId > ConfigToStackId
StackId ExternalStackId(const Config &config)
bool Empty(const Config &config, Level level) const
bool operator==(const KeyPair &rhs) const
KeyPair(Level level, size_t id)
ssize_t ParenId(Label label) const
bool AllEmpty(const Config &config)
StackConfig< StackId, Label, 2 > Config
StackId Find(StackId stack_id, Label label)