Home | History | Annotate | Download | only in fst 
      1 // project.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 project an Fst on to its domain or range.
     20 
     21 #ifndef FST_LIB_PROJECT_H__
     22 #define FST_LIB_PROJECT_H__
     23 
     24 #include <fst/arc-map.h>
     25 #include <fst/mutable-fst.h>
     26 
     27 
     28 namespace fst {
     29 
     30 // This specifies whether to project on input or output.
     31 enum ProjectType { PROJECT_INPUT = 1, PROJECT_OUTPUT = 2 };
     32 
     33 
     34 // Mapper to implement projection per arc.
     35 template <class A> class ProjectMapper {
     36  public:
     37   explicit ProjectMapper(ProjectType project_type)
     38       : project_type_(project_type) {}
     39 
     40   A operator()(const A &arc) {
     41     typename A::Label label = project_type_ == PROJECT_INPUT
     42                               ? arc.ilabel : arc.olabel;
     43     return A(label, label, arc.weight, arc.nextstate);
     44   }
     45 
     46   MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
     47 
     48   MapSymbolsAction InputSymbolsAction() const {
     49     return project_type_ == PROJECT_INPUT ? MAP_COPY_SYMBOLS :
     50         MAP_CLEAR_SYMBOLS;
     51   }
     52 
     53   MapSymbolsAction OutputSymbolsAction() const {
     54     return project_type_ == PROJECT_OUTPUT ? MAP_COPY_SYMBOLS :
     55         MAP_CLEAR_SYMBOLS;
     56   }
     57 
     58   uint64 Properties(uint64 props) {
     59     return ProjectProperties(props, project_type_ == PROJECT_INPUT);
     60   }
     61 
     62 
     63  private:
     64   ProjectType project_type_;
     65 };
     66 
     67 
     68 // Projects an FST onto its domain or range by either copying each arcs'
     69 // input label to the output label or vice versa. This version modifies
     70 // its input.
     71 //
     72 // Complexity:
     73 // - Time: O(V + E)
     74 // - Space: O(1)
     75 // where V = # of states and E = # of arcs.
     76 template<class Arc> inline
     77 void Project(MutableFst<Arc> *fst, ProjectType project_type) {
     78   ArcMap(fst, ProjectMapper<Arc>(project_type));
     79   if (project_type == PROJECT_INPUT)
     80     fst->SetOutputSymbols(fst->InputSymbols());
     81   if (project_type == PROJECT_OUTPUT)
     82     fst->SetInputSymbols(fst->OutputSymbols());
     83 }
     84 
     85 
     86 // Projects an FST onto its domain or range by either copying each arc's
     87 // input label to the output label or vice versa. This version is a delayed
     88 // Fst.
     89 //
     90 // Complexity:
     91 // - Time: O(v + e)
     92 // - Space: O(1)
     93 // where v = # of states visited, e = # of arcs visited. Constant
     94 // time and to visit an input state or arc is assumed and exclusive
     95 // of caching.
     96 template <class A>
     97 class ProjectFst : public ArcMapFst<A, A, ProjectMapper<A> > {
     98  public:
     99   typedef A Arc;
    100   typedef ProjectMapper<A> C;
    101   typedef ArcMapFstImpl< A, A, ProjectMapper<A> > Impl;
    102   using ImplToFst<Impl>::GetImpl;
    103 
    104   ProjectFst(const Fst<A> &fst, ProjectType project_type)
    105       : ArcMapFst<A, A, C>(fst, C(project_type)) {
    106     if (project_type == PROJECT_INPUT)
    107       GetImpl()->SetOutputSymbols(fst.InputSymbols());
    108     if (project_type == PROJECT_OUTPUT)
    109       GetImpl()->SetInputSymbols(fst.OutputSymbols());
    110   }
    111 
    112   // See Fst<>::Copy() for doc.
    113   ProjectFst(const ProjectFst<A> &fst, bool safe = false)
    114       : ArcMapFst<A, A, C>(fst, safe) {}
    115 
    116   // Get a copy of this ProjectFst. See Fst<>::Copy() for further doc.
    117   virtual ProjectFst<A> *Copy(bool safe = false) const {
    118     return new ProjectFst(*this, safe);
    119   }
    120 };
    121 
    122 
    123 // Specialization for ProjectFst.
    124 template <class A>
    125 class StateIterator< ProjectFst<A> >
    126     : public StateIterator< ArcMapFst<A, A, ProjectMapper<A> > > {
    127  public:
    128   explicit StateIterator(const ProjectFst<A> &fst)
    129       : StateIterator< ArcMapFst<A, A, ProjectMapper<A> > >(fst) {}
    130 };
    131 
    132 
    133 // Specialization for ProjectFst.
    134 template <class A>
    135 class ArcIterator< ProjectFst<A> >
    136     : public ArcIterator< ArcMapFst<A, A, ProjectMapper<A> > > {
    137  public:
    138   ArcIterator(const ProjectFst<A> &fst, typename A::StateId s)
    139       : ArcIterator< ArcMapFst<A, A, ProjectMapper<A> > >(fst, s) {}
    140 };
    141 
    142 
    143 // Useful alias when using StdArc.
    144 typedef ProjectFst<StdArc> StdProjectFst;
    145 
    146 }  // namespace fst
    147 
    148 #endif  // FST_LIB_PROJECT_H__
    149