1// arcsort.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// Functions and classes to sort arcs in an FST.
20
21#ifndef FST_LIB_ARCSORT_H__
22#define FST_LIB_ARCSORT_H__
23
24#include <algorithm>
25#include <string>
26#include <vector>
27using std::vector;
28
29#include <fst/cache.h>
30#include <fst/state-map.h>
31#include <fst/test-properties.h>
32
33
34namespace fst {
35
36template <class Arc, class Compare>
37class ArcSortMapper {
38 public:
39  typedef Arc FromArc;
40  typedef Arc ToArc;
41
42  typedef typename Arc::StateId StateId;
43  typedef typename Arc::Weight Weight;
44
45  ArcSortMapper(const Fst<Arc> &fst, const Compare &comp)
46      : fst_(fst), comp_(comp), i_(0) {}
47
48  // Allows updating Fst argument; pass only if changed.
49  ArcSortMapper(const ArcSortMapper<Arc, Compare> &mapper,
50                const Fst<Arc> *fst = 0)
51      : fst_(fst ? *fst : mapper.fst_), comp_(mapper.comp_), i_(0) {}
52
53  StateId Start() { return fst_.Start(); }
54  Weight Final(StateId s) const { return fst_.Final(s); }
55
56  void SetState(StateId s) {
57    i_ = 0;
58    arcs_.clear();
59    arcs_.reserve(fst_.NumArcs(s));
60    for (ArcIterator< Fst<Arc> > aiter(fst_, s); !aiter.Done(); aiter.Next())
61      arcs_.push_back(aiter.Value());
62    sort(arcs_.begin(), arcs_.end(), comp_);
63  }
64
65  bool Done() const { return i_ >= arcs_.size(); }
66  const Arc &Value() const { return arcs_[i_]; }
67  void Next() { ++i_; }
68
69  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
70  MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
71  uint64 Properties(uint64 props) const { return comp_.Properties(props); }
72
73 private:
74  const Fst<Arc> &fst_;
75  const Compare &comp_;
76  vector<Arc> arcs_;
77  ssize_t i_;               // current arc position
78
79  void operator=(const ArcSortMapper<Arc, Compare> &);  // disallow
80};
81
82
83// Sorts the arcs in an FST according to function object 'comp' of
84// type Compare. This version modifies its input.  Comparison function
85// objects ILabelCompare and OLabelCompare are provived by the
86// library. In general, Compare must meet the requirements for an STL
87// sort comparision function object. It must also have a member
88// Properties(uint64) that specifies the known properties of the
89// sorted FST; it takes as argument the input FST's known properties
90// before the sort.
91//
92// Complexity:
93// - Time: O(V D log D)
94// - Space: O(D)
95// where V = # of states and D = maximum out-degree.
96template<class Arc, class Compare>
97void ArcSort(MutableFst<Arc> *fst, Compare comp) {
98  ArcSortMapper<Arc, Compare> mapper(*fst, comp);
99  StateMap(fst, mapper);
100}
101
102typedef CacheOptions ArcSortFstOptions;
103
104// Sorts the arcs in an FST according to function object 'comp' of
105// type Compare. This version is a delayed Fst.  Comparsion function
106// objects ILabelCompare and OLabelCompare are provided by the
107// library. In general, Compare must meet the requirements for an STL
108// comparision function object (e.g. as used for STL sort). It must
109// also have a member Properties(uint64) that specifies the known
110// properties of the sorted FST; it takes as argument the input FST's
111// known properties.
112//
113// Complexity:
114// - Time: O(v d log d)
115// - Space: O(d)
116// where v = # of states visited, d = maximum out-degree of states
117// visited. Constant time and space to visit an input state is assumed
118// and exclusive of caching.
119template <class A, class C>
120class ArcSortFst : public StateMapFst<A, A, ArcSortMapper<A, C> > {
121  using StateMapFst<A, A, ArcSortMapper<A, C> >::GetImpl;
122 public:
123  typedef A Arc;
124  typedef typename Arc::StateId StateId;
125  typedef ArcSortMapper<A, C> M;
126
127  ArcSortFst(const Fst<A> &fst, const C &comp)
128      : StateMapFst<A, A, M>(fst, ArcSortMapper<A, C>(fst, comp)) {}
129
130  ArcSortFst(const Fst<A> &fst, const C &comp, const ArcSortFstOptions &opts)
131      : StateMapFst<A, A, M>(fst, ArcSortMapper<A, C>(fst, comp), opts) {}
132
133  // See Fst<>::Copy() for doc.
134  ArcSortFst(const ArcSortFst<A, C> &fst, bool safe = false)
135      : StateMapFst<A, A, M>(fst, safe) {}
136
137  // Get a copy of this ArcSortFst. See Fst<>::Copy() for further doc.
138  virtual ArcSortFst<A, C> *Copy(bool safe = false) const {
139    return new ArcSortFst(*this, safe);
140  }
141
142  virtual size_t NumArcs(StateId s) const {
143    return GetImpl()->GetFst().NumArcs(s);
144  }
145
146  virtual size_t NumInputEpsilons(StateId s) const {
147    return GetImpl()->GetFst().NumInputEpsilons(s);
148  }
149
150  virtual size_t NumOutputEpsilons(StateId s) const {
151    return GetImpl()->GetFst().NumOutputEpsilons(s);
152  }
153};
154
155
156// Specialization for ArcSortFst.
157template <class A, class C>
158class StateIterator< ArcSortFst<A, C> >
159    : public StateIterator< StateMapFst<A, A,  ArcSortMapper<A, C> > > {
160 public:
161  explicit StateIterator(const ArcSortFst<A, C> &fst)
162      : StateIterator< StateMapFst<A, A,  ArcSortMapper<A, C> > >(fst) {}
163};
164
165
166// Specialization for ArcSortFst.
167template <class A, class C>
168class ArcIterator< ArcSortFst<A, C> >
169    : public ArcIterator< StateMapFst<A, A,  ArcSortMapper<A, C> > > {
170 public:
171  ArcIterator(const ArcSortFst<A, C> &fst, typename A::StateId s)
172      : ArcIterator< StateMapFst<A, A,  ArcSortMapper<A, C> > >(fst, s) {}
173};
174
175
176// Compare class for comparing input labels of arcs.
177template<class A> class ILabelCompare {
178 public:
179  bool operator() (A arc1, A arc2) const {
180    return arc1.ilabel < arc2.ilabel;
181  }
182
183  uint64 Properties(uint64 props) const {
184    return (props & kArcSortProperties) | kILabelSorted |
185        (props & kAcceptor ? kOLabelSorted : 0);
186  }
187};
188
189
190// Compare class for comparing output labels of arcs.
191template<class A> class OLabelCompare {
192 public:
193  bool operator() (const A &arc1, const A &arc2) const {
194    return arc1.olabel < arc2.olabel;
195  }
196
197  uint64 Properties(uint64 props) const {
198    return (props & kArcSortProperties) | kOLabelSorted |
199        (props & kAcceptor ? kILabelSorted : 0);
200  }
201};
202
203
204// Useful aliases when using StdArc.
205template<class C> class StdArcSortFst : public ArcSortFst<StdArc, C> {
206 public:
207  typedef StdArc Arc;
208  typedef C Compare;
209};
210
211typedef ILabelCompare<StdArc> StdILabelCompare;
212
213typedef OLabelCompare<StdArc> StdOLabelCompare;
214
215}  // namespace fst
216
217#endif  // FST_LIB_ARCSORT_H__
218