Home | History | Annotate | Download | only in fst 
      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 (at) 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>
     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