FST  openfst-1.7.2
OpenFst Library
arcsort.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // Functions and classes to sort arcs in an FST.
5 
6 #ifndef FST_ARCSORT_H_
7 #define FST_ARCSORT_H_
8 
9 #include <algorithm>
10 #include <string>
11 #include <vector>
12 
13 #include <fst/cache.h>
14 #include <fst/state-map.h>
15 #include <fst/test-properties.h>
16 
17 
18 namespace fst {
19 
20 template <class Arc, class Compare>
22  public:
23  using FromArc = Arc;
24  using ToArc = Arc;
25 
26  using StateId = typename Arc::StateId;
27  using Weight = typename Arc::Weight;
28 
29  constexpr ArcSortMapper(const Fst<Arc> &fst, const Compare &comp)
30  : fst_(fst), comp_(comp), i_(0) {}
31 
32  // Allows updating Fst argument; pass only if changed.
34  const Fst<Arc> *fst = nullptr)
35  : fst_(fst ? *fst : mapper.fst_), comp_(mapper.comp_), i_(0) {}
36 
37  StateId Start() { return fst_.Start(); }
38 
39  Weight Final(StateId s) const { return fst_.Final(s); }
40 
41  void SetState(StateId s) {
42  i_ = 0;
43  arcs_.clear();
44  arcs_.reserve(fst_.NumArcs(s));
45  for (ArcIterator<Fst<Arc>> aiter(fst_, s); !aiter.Done(); aiter.Next()) {
46  arcs_.push_back(aiter.Value());
47  }
48  std::sort(arcs_.begin(), arcs_.end(), comp_);
49  }
50 
51  bool Done() const { return i_ >= arcs_.size(); }
52 
53  const Arc &Value() const { return arcs_[i_]; }
54 
55  void Next() { ++i_; }
56 
58 
60 
61  uint64 Properties(uint64 props) const { return comp_.Properties(props); }
62 
63  private:
64  const Fst<Arc> &fst_;
65  const Compare &comp_;
66  std::vector<Arc> arcs_;
67  ssize_t i_; // current arc position
68 
69  ArcSortMapper &operator=(const ArcSortMapper &) = delete;
70 };
71 
72 // Sorts the arcs in an FST according to function object 'comp' of type Compare.
73 // This version modifies its input. Comparison function objects ILabelCompare
74 // and OLabelCompare are provided by the library. In general, Compare must meet
75 // the requirements for a comparison function object (e.g., similar to those
76 // used by std::sort). It must also have a member Properties(uint64) that
77 // specifies the known properties of the sorted FST; it takes as argument the
78 // input FST's known properties before the sort.
79 //
80 // Complexity:
81 //
82 // - Time: O(v d log d)
83 // - Space: O(d)
84 //
85 // where v = # of states and d = maximum out-degree.
86 template <class Arc, class Compare>
87 void ArcSort(MutableFst<Arc> *fst, Compare comp) {
88  ArcSortMapper<Arc, Compare> mapper(*fst, comp);
89  StateMap(fst, mapper);
90 }
91 
93 
94 // Sorts the arcs in an FST according to function object 'comp' of type Compare.
95 // This version is a delayed FST. Comparsion function objects ILabelCompare and
96 // OLabelCompare are provided by the library. In general, Compare must meet the
97 // requirements for a comparision function object (e.g., similar to those
98 // used by std::sort). It must also have a member Properties(uint64) that
99 // specifies the known properties of the sorted FST; it takes as argument the
100 // input FST's known properties.
101 //
102 // Complexity:
103 //
104 // - Time: O(v d log d)
105 // - Space: O(d)
106 //
107 // where v = # of states visited, d = maximum out-degree of states visited.
108 // Constant time and space to visit an input state is assumed and exclusive of
109 // caching.
110 template <class Arc, class Compare>
111 class ArcSortFst : public StateMapFst<Arc, Arc, ArcSortMapper<Arc, Compare>> {
113 
114  public:
115  using StateId = typename Arc::StateId;
117 
118  ArcSortFst(const Fst<Arc> &fst, const Compare &comp)
119  : StateMapFst<Arc, Arc, Mapper>(fst,
120  ArcSortMapper<Arc, Compare>(fst, comp)) {}
121 
122  ArcSortFst(const Fst<Arc> &fst, const Compare &comp,
123  const ArcSortFstOptions &opts)
124  : StateMapFst<Arc, Arc, Mapper>(fst, Mapper(fst, comp), opts) {}
125 
126  // See Fst<>::Copy() for doc.
127  ArcSortFst(const ArcSortFst<Arc, Compare> &fst, bool safe = false)
128  : StateMapFst<Arc, Arc, Mapper>(fst, safe) {}
129 
130  // Gets a copy of this ArcSortFst. See Fst<>::Copy() for further doc.
131  ArcSortFst<Arc, Compare> *Copy(bool safe = false) const override {
132  return new ArcSortFst(*this, safe);
133  }
134 
135  size_t NumArcs(StateId s) const override {
136  return GetImpl()->GetFst()->NumArcs(s);
137  }
138 
139  size_t NumInputEpsilons(StateId s) const override {
140  return GetImpl()->GetFst()->NumInputEpsilons(s);
141  }
142 
143  size_t NumOutputEpsilons(StateId s) const override {
144  return GetImpl()->GetFst()->NumOutputEpsilons(s);
145  }
146 };
147 
148 // Specialization for ArcSortFst.
149 template <class Arc, class Compare>
150 class StateIterator<ArcSortFst<Arc, Compare>>
151  : public StateIterator<StateMapFst<Arc, Arc, ArcSortMapper<Arc, Compare>>> {
152  public:
154  : StateIterator<StateMapFst<Arc, Arc, ArcSortMapper<Arc, Compare>>>(fst) {
155  }
156 };
157 
158 // Specialization for ArcSortFst.
159 template <class Arc, class Compare>
160 class ArcIterator<ArcSortFst<Arc, Compare>>
161  : public ArcIterator<StateMapFst<Arc, Arc, ArcSortMapper<Arc, Compare>>> {
162  public:
163  ArcIterator(const ArcSortFst<Arc, Compare> &fst, typename Arc::StateId s)
164  : ArcIterator<StateMapFst<Arc, Arc, ArcSortMapper<Arc, Compare>>>(fst,
165  s) {}
166 };
167 
168 // Compare class for comparing input labels of arcs.
169 template <class Arc>
171  public:
172  constexpr ILabelCompare() {}
173 
174  constexpr bool operator()(const Arc &arc1, const Arc &arc2) const {
175  return arc1.ilabel < arc2.ilabel;
176  }
177 
178  constexpr uint64 Properties(uint64 props) const {
179  return (props & kArcSortProperties) | kILabelSorted |
180  (props & kAcceptor ? kOLabelSorted : 0);
181  }
182 };
183 
184 // Compare class for comparing output labels of arcs.
185 template <class Arc>
187  public:
188  constexpr OLabelCompare() {}
189 
190  constexpr bool operator()(const Arc &arc1, const Arc &arc2) const {
191  return arc1.olabel < arc2.olabel;
192  }
193 
194  constexpr uint64 Properties(uint64 props) const {
195  return (props & kArcSortProperties) | kOLabelSorted |
196  (props & kAcceptor ? kILabelSorted : 0);
197  }
198 };
199 
200 // Useful aliases when using StdArc.
201 
202 template <class Compare>
204 
206 
208 
209 } // namespace fst
210 
211 #endif // FST_ARCSORT_H_
MapSymbolsAction
Definition: arc-map.h:39
ArcIterator(const ArcSortFst< Arc, Compare > &fst, typename Arc::StateId s)
Definition: arcsort.h:163
constexpr ILabelCompare()
Definition: arcsort.h:172
StateId Start()
Definition: arcsort.h:37
bool Done() const
Definition: arcsort.h:51
typename StateMapFst< Arc, Arc, ArcSortMapper< Arc, Compare > >::Arc Arc
Definition: fst.h:480
uint64_t uint64
Definition: types.h:32
typename Arc::StateId StateId
Definition: arcsort.h:26
virtual size_t NumArcs(StateId) const =0
constexpr OLabelCompare()
Definition: arcsort.h:188
const Arc & Value() const
Definition: arcsort.h:53
void SetState(StateId s)
Definition: arcsort.h:41
constexpr ArcSortMapper(const Fst< Arc > &fst, const Compare &comp)
Definition: arcsort.h:29
ArcSortFst(const ArcSortFst< Arc, Compare > &fst, bool safe=false)
Definition: arcsort.h:127
constexpr uint64 Properties(uint64 props) const
Definition: arcsort.h:194
size_t NumInputEpsilons(StateId s) const override
Definition: arcsort.h:139
constexpr uint64 kILabelSorted
Definition: properties.h:75
virtual Weight Final(StateId) const =0
MapSymbolsAction InputSymbolsAction() const
Definition: arcsort.h:57
typename StateMapFst< Arc, Arc, ArcSortMapper< Arc, Compare > >::Arc Arc
Definition: fst.h:374
StateIterator(const ArcSortFst< Arc, Compare > &fst)
Definition: arcsort.h:153
ArcSortMapper(const ArcSortMapper< Arc, Compare > &mapper, const Fst< Arc > *fst=nullptr)
Definition: arcsort.h:33
MapSymbolsAction OutputSymbolsAction() const
Definition: arcsort.h:59
constexpr uint64 kArcSortProperties
Definition: properties.h:226
uint64 Properties(uint64 props) const
Definition: arcsort.h:61
void ArcSort(MutableFst< Arc > *fst, Compare comp)
Definition: arcsort.h:87
ArcSortFst< Arc, Compare > * Copy(bool safe=false) const override
Definition: arcsort.h:131
constexpr uint64 kOLabelSorted
Definition: properties.h:80
virtual StateId Start() const =0
constexpr uint64 Properties(uint64 props) const
Definition: arcsort.h:178
typename Arc::Weight Weight
Definition: arcsort.h:27
constexpr uint64 kAcceptor
Definition: properties.h:45
void StateMap(MutableFst< A > *fst, C *mapper)
Definition: state-map.h:79
size_t NumArcs(StateId s) const override
Definition: arcsort.h:135
ArcSortFst(const Fst< Arc > &fst, const Compare &comp)
Definition: arcsort.h:118
ArcSortFst(const Fst< Arc > &fst, const Compare &comp, const ArcSortFstOptions &opts)
Definition: arcsort.h:122
constexpr bool operator()(const Arc &arc1, const Arc &arc2) const
Definition: arcsort.h:174
Weight Final(StateId s) const
Definition: arcsort.h:39
typename internal::StateMapFstImpl< Arc, Arc, ArcSortMapper< Arc, Compare > >::Arc Arc
Definition: fst.h:188
constexpr bool operator()(const Arc &arc1, const Arc &arc2) const
Definition: arcsort.h:190
typename Arc::StateId StateId
Definition: arcsort.h:115
size_t NumOutputEpsilons(StateId s) const override
Definition: arcsort.h:143