1 // statesort.h
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 // Copyright 2005-2010 Google, Inc.
16 // Author: riley@google.com (Michael Riley)
17 //
18 // \file
19 // Function to sort states of an Fst.
20
21 #ifndef FST_LIB_STATESORT_H__
22 #define FST_LIB_STATESORT_H__
23
24 #include <vector>
25 using std::vector;
26 #include <algorithm>
27
28 #include <fst/mutable-fst.h>
29
30
31 namespace fst {
32
33 // Sorts the input states of an FST, modifying it. ORDER[i] gives the
34 // the state Id after sorting that corresponds to state Id i before
35 // sorting. ORDER must be a permutation of FST's states ID sequence:
36 // (0, 1, 2, ..., fst->NumStates() - 1).
37 template <class Arc>
StateSort(MutableFst<Arc> * fst,const vector<typename Arc::StateId> & order)38 void StateSort(MutableFst<Arc> *fst,
39 const vector<typename Arc::StateId> &order) {
40 typedef typename Arc::StateId StateId;
41 typedef typename Arc::Weight Weight;
42
43 if (order.size() != fst->NumStates()) {
44 FSTERROR() << "StateSort: bad order vector size: " << order.size();
45 fst->SetProperties(kError, kError);
46 return;
47 }
48
49 if (fst->Start() == kNoStateId)
50 return;
51
52 uint64 props = fst->Properties(kStateSortProperties, false);
53
54 vector<bool> done(order.size(), false);
55 vector<Arc> arcsa, arcsb;
56 vector<Arc> *arcs1 = &arcsa, *arcs2 = &arcsb;
57
58 fst->SetStart(order[fst->Start()]);
59
60 for (StateIterator< MutableFst<Arc> > siter(*fst);
61 !siter.Done();
62 siter.Next()) {
63 StateId s1 = siter.Value(), s2;
64 if (done[s1])
65 continue;
66 Weight final1 = fst->Final(s1), final2 = Weight::Zero();
67 arcs1->clear();
68 for (ArcIterator< MutableFst<Arc> > aiter(*fst, s1);
69 !aiter.Done();
70 aiter.Next())
71 arcs1->push_back(aiter.Value());
72 for (; !done[s1]; s1 = s2, final1 = final2, swap(arcs1, arcs2)) {
73 s2 = order[s1];
74 if (!done[s2]) {
75 final2 = fst->Final(s2);
76 arcs2->clear();
77 for (ArcIterator< MutableFst<Arc> > aiter(*fst, s2);
78 !aiter.Done();
79 aiter.Next())
80 arcs2->push_back(aiter.Value());
81 }
82 fst->SetFinal(s2, final1);
83 fst->DeleteArcs(s2);
84 for (size_t i = 0; i < arcs1->size(); ++i) {
85 Arc arc = (*arcs1)[i];
86 arc.nextstate = order[arc.nextstate];
87 fst->AddArc(s2, arc);
88 }
89 done[s1] = true;
90 }
91 }
92 fst->SetProperties(props, kFstProperties);
93 }
94
95 } // namespace fst
96
97 #endif // FST_LIB_STATESORT_H__
98