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 (at) 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> 27 using std::vector; 28 29 #include <fst/cache.h> 30 #include <fst/state-map.h> 31 #include <fst/test-properties.h> 32 33 34 namespace fst { 35 36 template <class Arc, class Compare> 37 class 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. 96 template<class Arc, class Compare> 97 void ArcSort(MutableFst<Arc> *fst, Compare comp) { 98 ArcSortMapper<Arc, Compare> mapper(*fst, comp); 99 StateMap(fst, mapper); 100 } 101 102 typedef 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. 119 template <class A, class C> 120 class ArcSortFst : public StateMapFst<A, A, ArcSortMapper<A, C> > { 121 public: 122 typedef A Arc; 123 typedef ArcSortMapper<A, C> M; 124 125 ArcSortFst(const Fst<A> &fst, const C &comp) 126 : StateMapFst<A, A, M>(fst, ArcSortMapper<A, C>(fst, comp)) {} 127 128 ArcSortFst(const Fst<A> &fst, const C &comp, const ArcSortFstOptions &opts) 129 : StateMapFst<A, A, M>(fst, ArcSortMapper<A, C>(fst, comp), opts) {} 130 131 // See Fst<>::Copy() for doc. 132 ArcSortFst(const ArcSortFst<A, C> &fst, bool safe = false) 133 : StateMapFst<A, A, M>(fst, safe) {} 134 135 // Get a copy of this ArcSortFst. See Fst<>::Copy() for further doc. 136 virtual ArcSortFst<A, C> *Copy(bool safe = false) const { 137 return new ArcSortFst(*this, safe); 138 } 139 }; 140 141 142 // Specialization for ArcSortFst. 143 template <class A, class C> 144 class StateIterator< ArcSortFst<A, C> > 145 : public StateIterator< StateMapFst<A, A, ArcSortMapper<A, C> > > { 146 public: 147 explicit StateIterator(const ArcSortFst<A, C> &fst) 148 : StateIterator< StateMapFst<A, A, ArcSortMapper<A, C> > >(fst) {} 149 }; 150 151 152 // Specialization for ArcSortFst. 153 template <class A, class C> 154 class ArcIterator< ArcSortFst<A, C> > 155 : public ArcIterator< StateMapFst<A, A, ArcSortMapper<A, C> > > { 156 public: 157 ArcIterator(const ArcSortFst<A, C> &fst, typename A::StateId s) 158 : ArcIterator< StateMapFst<A, A, ArcSortMapper<A, C> > >(fst, s) {} 159 }; 160 161 162 // Compare class for comparing input labels of arcs. 163 template<class A> class ILabelCompare { 164 public: 165 bool operator() (A arc1, A arc2) const { 166 return arc1.ilabel < arc2.ilabel; 167 } 168 169 uint64 Properties(uint64 props) const { 170 return (props & kArcSortProperties) | kILabelSorted | 171 (props & kAcceptor ? kOLabelSorted : 0); 172 } 173 }; 174 175 176 // Compare class for comparing output labels of arcs. 177 template<class A> class OLabelCompare { 178 public: 179 bool operator() (const A &arc1, const A &arc2) const { 180 return arc1.olabel < arc2.olabel; 181 } 182 183 uint64 Properties(uint64 props) const { 184 return (props & kArcSortProperties) | kOLabelSorted | 185 (props & kAcceptor ? kILabelSorted : 0); 186 } 187 }; 188 189 190 // Useful aliases when using StdArc. 191 template<class C> class StdArcSortFst : public ArcSortFst<StdArc, C> { 192 public: 193 typedef StdArc Arc; 194 typedef C Compare; 195 }; 196 197 typedef ILabelCompare<StdArc> StdILabelCompare; 198 199 typedef OLabelCompare<StdArc> StdOLabelCompare; 200 201 } // namespace fst 202 203 #endif // FST_LIB_ARCSORT_H__ 204