14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// complement.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// Class to complement an Fst. 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_COMPLEMENT_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_COMPLEMENT_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/fst.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 Projecttemplate <class A> class ComplementFst; 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Implementation of delayed ComplementFst. The algorithm used 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// completes the (deterministic) FSA and then exchanges final and 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// non-final states. Completion, i.e. ensuring that all labels can be 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// read from every state, is accomplished by using RHO labels, which 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// match all labels that are otherwise not found leaving a state. The 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// first state in the output is reserved to be a new state that is the 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// destination of all RHO labels. Each remaining output state s 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// corresponds to input state s - 1. The first arc in the output at 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// these states is the rho label, the remaining arcs correspond to the 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// input arcs. 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class A> 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ComplementFstImpl : public FstImpl<A> { 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetType; 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetProperties; 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::Properties; 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetInputSymbols; 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetOutputSymbols; 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class StateIterator< ComplementFst<A> >; 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class ArcIterator< ComplementFst<A> >; 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Label Label; 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit ComplementFstImpl(const Fst<A> &fst) : fst_(fst.Copy()) { 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetType("complement"); 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props = fst.Properties(kILabelSorted, false); 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetProperties(ComplementProperties(props), kCopyProperties); 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetInputSymbols(fst.InputSymbols()); 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetOutputSymbols(fst.OutputSymbols()); 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ~ComplementFstImpl() { delete fst_; } 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Start() const { 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId start = fst_->Start(); 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (start != kNoStateId) 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return start + 1; 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return 0; 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Exchange final and non-final states; make rho destination state final. 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight Final(StateId s) const { 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s == 0 || fst_->Final(s - 1) == Weight::Zero()) 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return Weight::One(); 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return Weight::Zero(); 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumArcs(StateId s) const { 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s == 0) 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return 1; 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return fst_->NumArcs(s - 1) + 1; 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumInputEpsilons(StateId s) const { 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return s == 0 ? 0 : fst_->NumInputEpsilons(s - 1); 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumOutputEpsilons(StateId s) const { 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return s == 0 ? 0 : fst_->NumOutputEpsilons(s - 1); 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> *fst_; 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(ComplementFstImpl); 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complements an automaton; this is a library-internal operation 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// that introduces the rho label. This version is a delayed Fst. 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ComplementFst : public Fst<A> { 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class StateIterator< ComplementFst<A> >; 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class ArcIterator< ComplementFst<A> >; 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Label Label; 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit ComplementFst(const Fst<A> &fst) 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : impl_(new ComplementFstImpl<A>(fst)) { 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props = kUnweighted | kNoEpsilons | kIDeterministic | kAcceptor; 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (fst.Properties(props, true) != props) 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "ComplementFst: argument not an unweighted" 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << " epsilon-free deterministic acceptor"; 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComplementFst(const ComplementFst<A> &fst) : impl_(fst.impl_) { 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->IncrRefCount(); 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ~ComplementFst() { if (!impl_->DecrRefCount()) { delete impl_; }} 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Start() const { return impl_->Start(); } 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual Weight Final(StateId s) const { return impl_->Final(s); } 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual uint64 Properties(uint64 mask, bool test) const { 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (test) { 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 known, test = TestProperties(*this, mask, &known); 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->SetProperties(test, known); 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return test & mask; 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->Properties(mask); 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const string& Type() const { return impl_->Type(); } 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ComplementFst<A> *Copy() const { 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return new ComplementFst<A>(*this); 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const SymbolTable* InputSymbols() const { 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->InputSymbols(); 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const SymbolTable* OutputSymbols() const { 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->OutputSymbols(); 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumArcs(StateId s) const { return impl_->NumArcs(s); } 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumInputEpsilons(StateId s) const { 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->NumInputEpsilons(s); 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumOutputEpsilons(StateId s) const { 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->NumOutputEpsilons(s); 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual inline void InitStateIterator(StateIteratorData<A> *data) const; 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual inline void InitArcIterator(StateId s, 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIteratorData<A> *data) const; 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComplementFstImpl<A> *impl_; 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void operator=(const ComplementFst<A> &fst); // disallow 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for ComplementFst. 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StateIterator< ComplementFst<A> > : public StateIteratorBase<A> { 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Label Label; 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit StateIterator(const ComplementFst<A> &fst) 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : siter_(*fst.impl_->fst_), s_(0) { 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual bool Done() const { return s_ > 0 && siter_.Done(); } 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Value() const { return s_; } 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Next() { 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s_ != 0) 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project siter_.Next(); 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++s_; 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Reset() { 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project siter_.Reset(); 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project s_ = 0; 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateIterator< Fst<A> > siter_; 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s_; 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(StateIterator); 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for ComplementFst. 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcIterator< ComplementFst<A> > : public ArcIteratorBase<A> { 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Label Label; 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator(const ComplementFst<A> &fst, StateId s) 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : aiter_(0), s_(s), pos_(0) { 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s_ != 0) 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter_ = new ArcIterator< Fst<A> >(*fst.impl_->fst_, s - 1); 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ~ArcIterator() { delete aiter_; } 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual bool Done() const { 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s_ != 0) 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return pos_ > 0 && aiter_->Done(); 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return pos_ > 0; 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Adds the rho label to the rho destination state. 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const A& Value() const { 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (pos_ == 0) { 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_.ilabel = arc_.olabel = kRhoLabel; 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_.weight = Weight::One(); 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_.nextstate = 0; 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_ = aiter_->Value(); 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++arc_.nextstate; 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return arc_; 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Next() { 2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s_ != 0 && pos_ > 0) 2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter_->Next(); 2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++pos_; 2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Reset() { 2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s_ != 0) 2544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter_->Reset(); 2554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pos_ = 0; 2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Seek(size_t a) { 2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s_ != 0) { 2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (a == 0) { 2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter_->Reset(); 2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter_->Seek(a - 1); 2634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pos_ = a; 2664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 2694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator< Fst<A> > *aiter_; 2704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s_; 2714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t pos_; 2724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project mutable A arc_; 2734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(ArcIterator); 2744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 2754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> inline void 2784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectComplementFst<A>::InitStateIterator(StateIteratorData<A> *data) const { 2794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data->base = new StateIterator< ComplementFst<A> >(*this); 2804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> inline void 2834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectComplementFst<A>::InitArcIterator(StateId s, ArcIteratorData<A> *data) const { 2844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data->base = new ArcIterator< ComplementFst<A> >(*this, s); 2854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Useful alias when using StdArc. 2894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef ComplementFst<StdArc> StdComplementFst; 2904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 2924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_COMPLEMENT_H__ 294