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
26namespace 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).
32template <class Arc>
33void 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