arcsort.h revision f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2
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 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. 143template <class A, class C> 144class 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. 153template <class A, class C> 154class 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. 163template<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. 177template<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. 191template<class C> class StdArcSortFst : public ArcSortFst<StdArc, C> { 192 public: 193 typedef StdArc Arc; 194 typedef C Compare; 195}; 196 197typedef ILabelCompare<StdArc> StdILabelCompare; 198 199typedef OLabelCompare<StdArc> StdOLabelCompare; 200 201} // namespace fst 202 203#endif // FST_LIB_ARCSORT_H__ 204