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