Home | History | Annotate | Download | only in lib 
      1 // invert.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 //
     16 // \file
     17 // Functions and classes to invert an Fst.
     18 
     19 #ifndef FST_LIB_INVERT_H__
     20 #define FST_LIB_INVERT_H__
     21 
     22 #include "fst/lib/map.h"
     23 #include "fst/lib/mutable-fst.h"
     24 
     25 namespace fst {
     26 
     27 // Mapper to implement inversion of an arc.
     28 template <class A> struct InvertMapper {
     29   InvertMapper() {}
     30 
     31   A operator()(const A &arc) {
     32     return A(arc.olabel, arc.ilabel, arc.weight, arc.nextstate);
     33   }
     34 
     35   uint64 Properties(uint64 props) { return InvertProperties(props); }
     36 
     37   MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
     38 };
     39 
     40 
     41 // Inverts the transduction corresponding to an FST by exchanging the
     42 // FST's input and output labels. This version modifies its input.
     43 //
     44 // Complexity:
     45 // - Time: O(V + E)
     46 // - Space: O(1)
     47 // where V = # of states and E = # of arcs.
     48 template<class Arc> inline
     49 void Invert(MutableFst<Arc> *fst) { Map(fst, InvertMapper<Arc>()); }
     50 
     51 
     52 // Inverts the transduction corresponding to an FST by exchanging the
     53 // FST's input and output labels.  This version is a delayed Fst.
     54 //
     55 // Complexity:
     56 // - Time: O(v + e)
     57 // - Space: O(1)
     58 // where v = # of states visited, e = # of arcs visited. Constant
     59 // time and to visit an input state or arc is assumed and exclusive
     60 // of caching.
     61 template <class A>
     62 class InvertFst : public MapFst<A, A, InvertMapper<A> > {
     63  public:
     64   typedef A Arc;
     65   typedef InvertMapper<A> C;
     66 
     67   explicit InvertFst(const Fst<A> &fst) : MapFst<A, A, C>(fst, C()) {}
     68 
     69   InvertFst(const InvertFst<A> &fst) : MapFst<A, A, C>(fst) {}
     70 
     71   virtual InvertFst<A> *Copy() const { return new InvertFst(*this); }
     72 };
     73 
     74 
     75 // Specialization for InvertFst.
     76 template <class A>
     77 class StateIterator< InvertFst<A> >
     78     : public StateIterator< MapFst<A, A, InvertMapper<A> > > {
     79  public:
     80   explicit StateIterator(const InvertFst<A> &fst)
     81       : StateIterator< MapFst<A, A, InvertMapper<A> > >(fst) {}
     82 };
     83 
     84 
     85 // Specialization for InvertFst.
     86 template <class A>
     87 class ArcIterator< InvertFst<A> >
     88     : public ArcIterator< MapFst<A, A, InvertMapper<A> > > {
     89  public:
     90   ArcIterator(const InvertFst<A> &fst, typename A::StateId s)
     91       : ArcIterator< MapFst<A, A, InvertMapper<A> > >(fst, s) {}
     92 };
     93 
     94 
     95 // Useful alias when using StdArc.
     96 typedef InvertFst<StdArc> StdInvertFst;
     97 
     98 }  // namespace fst
     99 
    100 #endif  // FST_LIB_INVERT_H__
    101