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