6 #ifndef FST_EXTENSIONS_PDT_PDT_H_ 7 #define FST_EXTENSIONS_PDT_PDT_H_ 11 #include <unordered_map> 23 template <
typename StackId,
typename Label>
36 StackNode(StackId p,
size_t i) : parent_id(p), paren_id(i) {}
39 explicit PdtStack(
const std::vector<std::pair<Label, Label>> &parens)
41 for (
size_t i = 0; i < parens.size(); ++i) {
42 const auto &pair = parens[i];
43 paren_map_[pair.first] = i;
44 paren_map_[pair.second] = i;
45 if (min_paren_ ==
kNoLabel || pair.first < min_paren_) {
46 min_paren_ = pair.first;
48 if (pair.second < min_paren_) min_paren_ = pair.second;
49 if (max_paren_ ==
kNoLabel || pair.first > max_paren_) {
50 max_paren_ = pair.first;
52 if (pair.second > max_paren_) max_paren_ = pair.second;
63 StackId
Find(StackId stack_id, Label label) {
64 if (min_paren_ ==
kNoLabel || label < min_paren_ || label > max_paren_) {
67 const auto it = paren_map_.find(label);
69 if (it == paren_map_.end())
return stack_id;
72 if (label == parens_[
paren_id].first) {
73 auto &child_id = child_map_[std::make_pair(stack_id, label)];
75 child_id = nodes_.size();
80 const auto &node = nodes_[stack_id];
82 if (
paren_id == node.paren_id)
return node.parent_id;
89 StackId
Pop(StackId stack_id)
const {
return nodes_[stack_id].parent_id; }
92 ssize_t
Top(StackId stack_id)
const {
return nodes_[stack_id].paren_id; }
95 const auto it = paren_map_.find(label);
96 if (it == paren_map_.end())
return -1;
102 size_t operator()(
const std::pair<StackId, Label> &pair)
const {
103 static constexpr
size_t prime = 7853;
104 return static_cast<size_t>(pair.first) +
105 static_cast<size_t>(pair.second) * prime;
109 std::vector<std::pair<Label, Label>> parens_;
110 std::vector<StackNode> nodes_;
111 std::unordered_map<Label, size_t> paren_map_;
113 std::unordered_map<std::pair<StackId, Label>, StackId, ChildHash> child_map_;
119 template <
typename S,
typename K>
128 : state_id(state_id), stack_id(stack_id) {}
132 template <
typename S,
typename K>
135 if (&x == &y)
return true;
144 static constexpr
auto prime = 7853;
145 return tuple.state_id + tuple.stack_id * prime;
150 template <
class StateId,
class StackId>
152 PdtStateTuple<StateId, StackId>,
153 PdtStateHash<PdtStateTuple<StateId, StackId>>> {
165 #endif // FST_EXTENSIONS_PDT_PDT_H_
PdtStateTuple(StateId state_id=kNoStateId, StackId stack_id=-1)
StackNode(StackId p, size_t i)
bool operator==(const PdtStateTuple< S, K > &x, const PdtStateTuple< S, K > &y)
PdtStateTable(const PdtStateTable &other)
StackId Pop(StackId stack_id) const
ssize_t ParenId(Label label) const
typename Arc::StateId StateId
StackId Find(StackId stack_id, Label label)
ssize_t Top(StackId stack_id) const
typename Arc::StateId StackId
size_t operator()(const T &tuple) const
PdtStack(const std::vector< std::pair< Label, Label >> &parens)