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