FST  openfst-1.8.3
OpenFst Library
statesort.h
Go to the documentation of this file.
1 // Copyright 2005-2024 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 // Function to sort states of an FST.
19 
20 #ifndef FST_STATESORT_H_
21 #define FST_STATESORT_H_
22 
23 #include <algorithm>
24 #include <utility>
25 #include <vector>
26 
27 #include <fst/log.h>
28 #include <fst/fst.h>
29 #include <fst/mutable-fst.h>
30 #include <fst/properties.h>
31 #include <fst/util.h>
32 
33 namespace fst {
34 
35 // Sorts the input states of an FST. order[i] gives the state ID after
36 // sorting that corresponds to the state ID i before sorting; it must
37 // therefore be a permutation of the input FST's states ID sequence.
38 template <class Arc>
40  const std::vector<typename Arc::StateId> &order) {
41  using StateId = typename Arc::StateId;
42  using Weight = typename Arc::Weight;
43  if (order.size() != fst->NumStates()) {
44  FSTERROR() << "StateSort: Bad order vector size: " << order.size();
46  return;
47  }
48  if (fst->Start() == kNoStateId) return;
49  const auto props = fst->Properties(kStateSortProperties, false);
50  std::vector<bool> done(order.size(), false);
51  std::vector<Arc> arcsa;
52  std::vector<Arc> arcsb;
53  fst->SetStart(order[fst->Start()]);
54  for (StateIterator<MutableFst<Arc>> siter(*fst); !siter.Done();
55  siter.Next()) {
56  auto s1 = siter.Value();
57  StateId s2;
58  if (done[s1]) continue;
59  auto final1 = fst->Final(s1);
60  auto final2 = Weight::Zero();
61  arcsa.clear();
62  for (ArcIterator<MutableFst<Arc>> aiter(*fst, s1); !aiter.Done();
63  aiter.Next()) {
64  arcsa.push_back(aiter.Value());
65  }
66  for (; !done[s1]; s1 = s2, final1 = final2, std::swap(arcsa, arcsb)) {
67  s2 = order[s1];
68  if (!done[s2]) {
69  final2 = fst->Final(s2);
70  arcsb.clear();
71  for (ArcIterator<MutableFst<Arc>> aiter(*fst, s2); !aiter.Done();
72  aiter.Next()) {
73  arcsb.push_back(aiter.Value());
74  }
75  }
76  fst->SetFinal(s2, final1);
77  fst->DeleteArcs(s2);
78  for (auto arc : arcsa) { // NOLINT(performance-for-range-copy)
79  arc.nextstate = order[arc.nextstate];
80  fst->AddArc(s2, arc);
81  }
82  done[s1] = true;
83  }
84  }
85  fst->SetProperties(props, kFstProperties);
86 }
87 
88 } // namespace fst
89 
90 #endif // FST_STATESORT_H_
constexpr uint64_t kStateSortProperties
Definition: properties.h:241
virtual uint64_t Properties(uint64_t mask, bool test) const =0
constexpr uint64_t kError
Definition: properties.h:52
virtual Weight Final(StateId) const =0
virtual void SetStart(StateId)=0
constexpr int kNoStateId
Definition: fst.h:196
#define FSTERROR()
Definition: util.h:56
virtual void SetProperties(uint64_t props, uint64_t mask)=0
virtual void DeleteArcs(StateId, size_t)=0
virtual StateId Start() const =0
constexpr uint64_t kFstProperties
Definition: properties.h:326
virtual void AddArc(StateId, const Arc &)=0
virtual void SetFinal(StateId s, Weight weight=Weight::One())=0
virtual StateId NumStates() const =0
bool StateSort(std::vector< IntervalSet< Label >> *interval_sets, const std::vector< StateId > &order)