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