14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// arcsort.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Functions and classes to sort arcs in an FST. 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_ARCSORT_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_ARCSORT_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <algorithm> 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/cache.h" 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/test-properties.h" 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Sorts the arcs in an FST according to function object 'comp' of 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// type Compare. This version modifies its input. Comparison function 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// objects IlabelCompare and OlabelCompare are provived by the 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// library. In general, Compare must meet the requirements for an STL 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// sort comparision function object. It must also have a member 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Properties(uint64) that specifies the known properties of the 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// sorted FST; it takes as argument the input FST's known properties 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// before the sort. 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: O(V + D log D) 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(D) 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where V = # of states and D = maximum out-degree. 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc, class Compare> 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid ArcSort(MutableFst<Arc> *fst, Compare comp) { 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props = fst->Properties(kFstProperties, false); 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Arc> arcs; 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateIterator< MutableFst<Arc> > siter(*fst); 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !siter.Done(); 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project siter.Next()) { 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = siter.Value(); 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arcs.clear(); 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator< MutableFst<Arc> > aiter(*fst, s); 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !aiter.Done(); 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter.Next()) 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arcs.push_back(aiter.Value()); 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sort(arcs.begin(), arcs.end(), comp); 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->DeleteArcs(s); 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t a = 0; a < arcs.size(); ++a) 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->AddArc(s, arcs[a]); 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->SetProperties(comp.Properties(props), kFstProperties); 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef CacheOptions ArcSortFstOptions; 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Implementation of delayed ArcSortFst. 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class A, class C> 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcSortFstImpl : public CacheImpl<A> { 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetType; 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetProperties; 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::Properties; 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetInputSymbols; 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetOutputSymbols; 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::InputSymbols; 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::OutputSymbols; 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using VectorFstBaseImpl<typename CacheImpl<A>::State>::NumStates; 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheImpl<A>::HasArcs; 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheImpl<A>::HasFinal; 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheImpl<A>::HasStart; 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcSortFstImpl(const Fst<A> &fst, const C &comp, 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const ArcSortFstOptions &opts) 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheImpl<A>(opts), fst_(fst.Copy()), comp_(comp) { 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetType("arcsort"); 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props = fst_->Properties(kCopyProperties, false); 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetProperties(comp_.Properties(props)); 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetInputSymbols(fst.InputSymbols()); 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetOutputSymbols(fst.OutputSymbols()); 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcSortFstImpl(const ArcSortFstImpl& impl) 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : fst_(impl.fst_->Copy()), comp_(impl.comp_) { 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetType("arcsort"); 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetProperties(impl.Properties(), kCopyProperties); 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetInputSymbols(impl.InputSymbols()); 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetOutputSymbols(impl.OutputSymbols()); 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ~ArcSortFstImpl() { delete fst_; } 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Start() { 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasStart()) 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetStart(fst_->Start()); 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::Start(); 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight Final(StateId s) { 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasFinal(s)) 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetFinal(s, fst_->Final(s)); 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::Final(s); 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumArcs(StateId s) { 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumArcs(s); 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumInputEpsilons(StateId s) { 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumInputEpsilons(s); 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumOutputEpsilons(StateId s) { 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumOutputEpsilons(s); 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void InitStateIterator(StateIteratorData<A> *data) const { 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst_->InitStateIterator(data); 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void InitArcIterator(StateId s, ArcIteratorData<A> *data) { 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheImpl<A>::InitArcIterator(s, data); 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Expand(StateId s) { 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator< Fst<A> > aiter(*fst_, s); !aiter.Done(); aiter.Next()) 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddArc(s, aiter.Value()); 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetArcs(s); 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s < NumStates()) { // ensure state exists 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<A> &carcs = GetState(s)->arcs; 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sort(carcs.begin(), carcs.end(), comp_); 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> *fst_; 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project C comp_; 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void operator=(const ArcSortFstImpl<A, C> &impl); // Disallow 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Sorts the arcs in an FST according to function object 'comp' of 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// type Compare. This version is a delayed Fst. Comparsion function 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// objects IlabelCompare and OlabelCompare are provided by the 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// library. In general, Compare must meet the requirements for an STL 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// comparision function object (e.g. as used for STL sort). It must 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// also have a member Properties(uint64) that specifies the known 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// properties of the sorted FST; it takes as argument the input FST's 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// known properties. 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: O(v + d log d) 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(v + d) 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where v = # of states visited, d = maximum out-degree of states 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// visited. Constant time and space to visit an input state is assumed 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// and exclusive of caching. 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A, class C> 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcSortFst : public Fst<A> { 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class CacheArcIterator< ArcSortFst<A, C> >; 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class ArcIterator< ArcSortFst<A, C> >; 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef C Compare; 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef CacheState<A> State; 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcSortFst(const Fst<A> &fst, const C &comp) 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : impl_(new ArcSortFstImpl<A, C>(fst, comp, ArcSortFstOptions())) {} 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcSortFst(const Fst<A> &fst, const C &comp, const ArcSortFstOptions &opts) 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : impl_(new ArcSortFstImpl<A, C>(fst, comp, opts)) {} 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcSortFst(const ArcSortFst<A, C> &fst) : 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_(new ArcSortFstImpl<A, C>(*(fst.impl_))) {} 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ~ArcSortFst() { if (!impl_->DecrRefCount()) delete impl_; } 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Start() const { return impl_->Start(); } 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual Weight Final(StateId s) const { return impl_->Final(s); } 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumArcs(StateId s) const { return impl_->NumArcs(s); } 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumInputEpsilons(StateId s) const { 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->NumInputEpsilons(s); 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumOutputEpsilons(StateId s) const { 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->NumOutputEpsilons(s); 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual uint64 Properties(uint64 mask, bool test) const { 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (test) { 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 known, test = TestProperties(*this, mask, &known); 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->SetProperties(test, known); 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return test & mask; 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->Properties(mask); 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const string& Type() const { return impl_->Type(); } 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ArcSortFst<A, C> *Copy() const { 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return new ArcSortFst<A, C>(*this); 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const SymbolTable* InputSymbols() const { 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->InputSymbols(); 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const SymbolTable* OutputSymbols() const { 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->OutputSymbols(); 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void InitStateIterator(StateIteratorData<A> *data) const { 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->InitStateIterator(data); 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const { 2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->InitArcIterator(s, data); 2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 2544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcSortFstImpl<A, C> *impl_; 2554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void operator=(const ArcSortFst<A, C> &fst); // Disallow 2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for ArcSortFst. 2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A, class C> 2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcIterator< ArcSortFst<A, C> > 2634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public CacheArcIterator< ArcSortFst<A, C> > { 2644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 2664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator(const ArcSortFst<A, C> &fst, StateId s) 2684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheArcIterator< ArcSortFst<A, C> >(fst, s) { 2694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!fst.impl_->HasArcs(s)) 2704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst.impl_->Expand(s); 2714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 2744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(ArcIterator); 2754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 2764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Compare class for comparing input labels of arcs. 2794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class A> class ILabelCompare { 2804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool operator() (A arc1, A arc2) const { 2824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return arc1.ilabel < arc2.ilabel; 2834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 Properties(uint64 props) const { 28673018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers return (props & kArcSortProperties) | kILabelSorted; 2874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 2894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Compare class for comparing output labels of arcs. 2924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class A> class OLabelCompare { 2934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool operator() (const A &arc1, const A &arc2) const { 2954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return arc1.olabel < arc2.olabel; 2964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 Properties(uint64 props) const { 29973018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers return (props & kArcSortProperties) | kOLabelSorted; 3004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 3024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Useful aliases when using StdArc. 3054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class C> class StdArcSortFst : public ArcSortFst<StdArc, C> { 3064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 3074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef StdArc Arc; 3084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef C Compare; 3094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 3104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef ILabelCompare<StdArc> StdILabelCompare; 3124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef OLabelCompare<StdArc> StdOLabelCompare; 3144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 3164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_ARCSORT_H__ 318