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> 25using std::vector; 26#include <algorithm> 27 28#include <fst/mutable-fst.h> 29 30 31namespace 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). 37template <class Arc> 38void 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