Home | History | Annotate | Download | only in lib 
      1 // map.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 // Class to map over/transform arcs e.g., change semirings or
     18 // implement project/invert.
     19 
     20 #ifndef FST_LIB_MAP_H__
     21 #define FST_LIB_MAP_H__
     22 
     23 #include "fst/lib/cache.h"
     24 #include "fst/lib/mutable-fst.h"
     25 
     26 namespace fst {
     27 
     28 // This determines how final weights are mapped.
     29 enum MapFinalAction {
     30 
     31   // A final weight is mapped into a final weight. An error
     32   // is raised if this is not possible.
     33   MAP_NO_SUPERFINAL,
     34 
     35   // A final weight is mapped to an arc to the superfinal state
     36   // when the result cannot be represented as a final weight.
     37   // The superfinal state will be added only if it is needed.
     38   MAP_ALLOW_SUPERFINAL,
     39 
     40   // A final weight is mapped to an arc to the superfinal state
     41   // unless the result can be represented as a final weight of weight
     42   // Zero(). The superfinal state is always added (if the input is
     43   // not the empty Fst).
     44   MAP_REQUIRE_SUPERFINAL
     45 };
     46 
     47 // Mapper Interface - class determinies how arcs and final weights
     48 // are mapped.
     49 //
     50 // class Mapper {
     51 //  public:
     52 //   // Maps an arc type A to arc type B.
     53 //   B operator()(const A &arc);
     54 //   // Specifies final action the mapper requires (see above).
     55 //   // The mapper will be passed final weights as arcs of the
     56 //   // form A(0, 0, weight, kNoStateId).
     57 //   MapFinalAction FinalAction() const;
     58 //   // This specifies the known properties of an Fst mapped by this
     59 //   // mapper. It takes as argument the input Fst's known properties.
     60 //   uint64 Properties(uint64 props) const;
     61 // }
     62 //
     63 // The Map functions and classes below will use the FinalAction()
     64 // method of the mapper to determine how to treat final weights,
     65 // e.g. whether to add a superfinal state. They will use the Properties()
     66 // method to set the result Fst properties.
     67 //
     68 // We include a various map versions below. One dimension of
     69 // variation is whether the mapping mutates its input, writes to a
     70 // new result Fst, or is an on-the-fly Fst. Another dimension is how
     71 // we pass the mapper. We allow passing the mapper by pointer
     72 // for cases that we need to change the state of the user's mapper.
     73 // This is the case with the encode mapper, which is reused during
     74 // decoding. We also include map versions that pass the mapper
     75 // by value or const reference when this suffices.
     76 
     77 
     78 // Maps an arc type A using a mapper function object C, passed
     79 // by pointer.  This version modifies its Fst input.
     80 template<class A, class C>
     81 void Map(MutableFst<A> *fst, C* mapper) {
     82   typedef typename A::StateId StateId;
     83   typedef typename A::Weight Weight;
     84 
     85   if (fst->Start() == kNoStateId)
     86     return;
     87 
     88   uint64 props = fst->Properties(kFstProperties, false);
     89 
     90   MapFinalAction final_action = mapper->FinalAction();
     91   StateId superfinal = kNoStateId;
     92   if (final_action == MAP_REQUIRE_SUPERFINAL) {
     93     superfinal = fst->AddState();
     94     fst->SetFinal(superfinal, Weight::One());
     95   }
     96 
     97   for (StateId s = 0; s < fst->NumStates(); ++s) {
     98     for (MutableArcIterator< MutableFst<A> > aiter(fst, s);
     99          !aiter.Done(); aiter.Next()) {
    100       const A &arc = aiter.Value();
    101       aiter.SetValue((*mapper)(arc));
    102     }
    103 
    104     switch (final_action) {
    105       case MAP_NO_SUPERFINAL:
    106       default: {
    107         A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId));
    108         CHECK(final_arc.ilabel == 0 && final_arc.olabel == 0);
    109         fst->SetFinal(s, final_arc.weight);
    110         break;
    111       }
    112       case MAP_ALLOW_SUPERFINAL: {
    113         if (s != superfinal) {
    114           A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId));
    115           if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
    116             // Add a superfinal state if not already done.
    117             if (superfinal == kNoStateId) {
    118               superfinal = fst->AddState();
    119               fst->SetFinal(superfinal, Weight::One());
    120             }
    121             final_arc.nextstate = superfinal;
    122             fst->AddArc(s, final_arc);
    123             fst->SetFinal(s, Weight::Zero());
    124           } else {
    125             fst->SetFinal(s, final_arc.weight);
    126           }
    127           break;
    128         }
    129       }
    130       case MAP_REQUIRE_SUPERFINAL: {
    131         if (s != superfinal) {
    132           A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId));
    133           if (final_arc.ilabel != 0 || final_arc.olabel != 0 ||
    134               final_arc.weight != Weight::Zero())
    135             fst->AddArc(s, A(final_arc.ilabel, final_arc.olabel,
    136                              final_arc.weight, superfinal));
    137             fst->SetFinal(s, Weight::Zero());
    138         }
    139         break;
    140       }
    141     }
    142   }
    143   fst->SetProperties(mapper->Properties(props), kFstProperties);
    144 }
    145 
    146 // Maps an arc type A using a mapper function object C, passed
    147 // by value.  This version modifies its Fst input.
    148 template<class A, class C>
    149 void Map(MutableFst<A> *fst, C mapper) {
    150   Map(fst, &mapper);
    151 }
    152 
    153 
    154 // Maps an arc type A to an arc type B using mapper function
    155 // object C, passed by pointer. This version writes the mapped
    156 // input Fst to an output MutableFst.
    157 template<class A, class B, class C>
    158 void Map(const Fst<A> &ifst, MutableFst<B> *ofst, C* mapper) {
    159   typedef typename A::StateId StateId;
    160   typedef typename A::Weight Weight;
    161 
    162   ofst->DeleteStates();
    163   ofst->SetInputSymbols(ifst.InputSymbols());
    164   ofst->SetOutputSymbols(ifst.OutputSymbols());
    165 
    166   if (ifst.Start() == kNoStateId)
    167     return;
    168 
    169   // Add all states.
    170   for (StateIterator< Fst<A> > siter(ifst); !siter.Done(); siter.Next())
    171     ofst->AddState();
    172 
    173   MapFinalAction final_action = mapper->FinalAction();
    174   StateId superfinal = kNoStateId;
    175   if (final_action == MAP_REQUIRE_SUPERFINAL) {
    176     superfinal = ofst->AddState();
    177     ofst->SetFinal(superfinal, B::Weight::One());
    178   }
    179   for (StateIterator< Fst<A> > siter(ifst); !siter.Done(); siter.Next()) {
    180     StateId s = siter.Value();
    181     if (s == ifst.Start())
    182       ofst->SetStart(s);
    183 
    184     for (ArcIterator< Fst<A> > aiter(ifst, s); !aiter.Done(); aiter.Next())
    185       ofst->AddArc(s, (*mapper)(aiter.Value()));
    186 
    187     switch (final_action) {
    188       case MAP_NO_SUPERFINAL:
    189       default: {
    190         B final_arc = (*mapper)(A(0, 0, ifst.Final(s), kNoStateId));
    191         CHECK(final_arc.ilabel == 0 && final_arc.olabel == 0);
    192         ofst->SetFinal(s, final_arc.weight);
    193         break;
    194       }
    195       case MAP_ALLOW_SUPERFINAL: {
    196         B final_arc = (*mapper)(A(0, 0, ifst.Final(s), kNoStateId));
    197         if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
    198             // Add a superfinal state if not already done.
    199           if (superfinal == kNoStateId) {
    200             superfinal = ofst->AddState();
    201             ofst->SetFinal(superfinal, B::Weight::One());
    202           }
    203           final_arc.nextstate = superfinal;
    204           ofst->AddArc(s, final_arc);
    205           ofst->SetFinal(s, B::Weight::Zero());
    206         } else {
    207           ofst->SetFinal(s, final_arc.weight);
    208         }
    209         break;
    210       }
    211       case MAP_REQUIRE_SUPERFINAL: {
    212         B final_arc = (*mapper)(A(0, 0, ifst.Final(s), kNoStateId));
    213         if (final_arc.ilabel != 0 || final_arc.olabel != 0 ||
    214             final_arc.weight != B::Weight::Zero())
    215           ofst->AddArc(s, B(final_arc.ilabel, final_arc.olabel,
    216                             final_arc.weight, superfinal));
    217         ofst->SetFinal(s, B::Weight::Zero());
    218         break;
    219       }
    220     }
    221   }
    222   uint64 iprops = ifst.Properties(kCopyProperties, false);
    223   uint64 oprops = ofst->Properties(kFstProperties, false);
    224   ofst->SetProperties(mapper->Properties(iprops) | oprops, kFstProperties);
    225 }
    226 
    227 // Maps an arc type A to an arc type B using mapper function
    228 // object C, passed by value. This version writes the mapped input
    229 // Fst to an output MutableFst.
    230 template<class A, class B, class C>
    231 void Map(const Fst<A> &ifst, MutableFst<B> *ofst, C mapper) {
    232   Map(ifst, ofst, &mapper);
    233 }
    234 
    235 
    236 struct MapFstOptions : public CacheOptions {
    237   // MapFst default caching behaviour is to do no caching. Most
    238   // mappers are cheap and therefore we save memory by not doing
    239   // caching.
    240   MapFstOptions() : CacheOptions(true, 0) {}
    241   MapFstOptions(const CacheOptions& opts) : CacheOptions(opts) {}
    242 };
    243 
    244 
    245 template <class A, class B, class C> class MapFst;
    246 
    247 // Implementation of delayed MapFst.
    248 template <class A, class B, class C>
    249 class MapFstImpl : public CacheImpl<B> {
    250  public:
    251   using FstImpl<B>::SetType;
    252   using FstImpl<B>::SetProperties;
    253   using FstImpl<B>::Properties;
    254   using FstImpl<B>::SetInputSymbols;
    255   using FstImpl<B>::SetOutputSymbols;
    256 
    257   using VectorFstBaseImpl<typename CacheImpl<B>::State>::NumStates;
    258 
    259   using CacheImpl<B>::HasArcs;
    260   using CacheImpl<B>::HasFinal;
    261   using CacheImpl<B>::HasStart;
    262 
    263   friend class StateIterator< MapFst<A, B, C> >;
    264 
    265   typedef B Arc;
    266   typedef typename B::Weight Weight;
    267   typedef typename B::StateId StateId;
    268 
    269   MapFstImpl(const Fst<A> &fst, const C &mapper,
    270                  const MapFstOptions& opts)
    271       : CacheImpl<B>(opts), fst_(fst.Copy()),
    272         mapper_(new C(mapper)),
    273         own_mapper_(true),
    274         superfinal_(kNoStateId),
    275         nstates_(0) {
    276     Init();
    277   }
    278 
    279   MapFstImpl(const Fst<A> &fst, C *mapper,
    280                  const MapFstOptions& opts)
    281       : CacheImpl<B>(opts), fst_(fst.Copy()),
    282         mapper_(mapper),
    283         own_mapper_(false),
    284         superfinal_(kNoStateId),
    285         nstates_(0) {
    286     Init();
    287   }
    288 
    289 
    290   ~MapFstImpl() {
    291     delete fst_;
    292     if (own_mapper_) delete mapper_;
    293   }
    294 
    295   StateId Start() {
    296     if (!HasStart())
    297       SetStart(FindOState(fst_->Start()));
    298     return CacheImpl<B>::Start();
    299   }
    300 
    301   Weight Final(StateId s) {
    302     if (!HasFinal(s)) {
    303       switch (final_action_) {
    304         case MAP_NO_SUPERFINAL:
    305         default: {
    306           B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
    307                                         kNoStateId));
    308           CHECK(final_arc.ilabel == 0 && final_arc.olabel == 0);
    309           SetFinal(s, final_arc.weight);
    310           break;
    311         }
    312         case MAP_ALLOW_SUPERFINAL: {
    313           if (s == superfinal_) {
    314             SetFinal(s, Weight::One());
    315           } else {
    316             B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
    317                                           kNoStateId));
    318             if (final_arc.ilabel == 0 && final_arc.olabel == 0)
    319               SetFinal(s, final_arc.weight);
    320             else
    321               SetFinal(s, Weight::Zero());
    322           }
    323           break;
    324         }
    325         case MAP_REQUIRE_SUPERFINAL: {
    326           SetFinal(s, s == superfinal_ ? Weight::One() : Weight::Zero());
    327           break;
    328         }
    329       }
    330     }
    331     return CacheImpl<B>::Final(s);
    332   }
    333 
    334   size_t NumArcs(StateId s) {
    335     if (!HasArcs(s))
    336       Expand(s);
    337     return CacheImpl<B>::NumArcs(s);
    338   }
    339 
    340   size_t NumInputEpsilons(StateId s) {
    341     if (!HasArcs(s))
    342       Expand(s);
    343     return CacheImpl<B>::NumInputEpsilons(s);
    344   }
    345 
    346   size_t NumOutputEpsilons(StateId s) {
    347     if (!HasArcs(s))
    348       Expand(s);
    349     return CacheImpl<B>::NumOutputEpsilons(s);
    350   }
    351 
    352   void InitArcIterator(StateId s, ArcIteratorData<B> *data) {
    353     if (!HasArcs(s))
    354       Expand(s);
    355     CacheImpl<B>::InitArcIterator(s, data);
    356   }
    357 
    358   void Expand(StateId s) {
    359     // Add exiting arcs.
    360     if (s == superfinal_) { SetArcs(s); return; }
    361 
    362     for (ArcIterator< Fst<A> > aiter(*fst_, FindIState(s));
    363          !aiter.Done(); aiter.Next()) {
    364       A aarc(aiter.Value());
    365       aarc.nextstate = FindOState(aarc.nextstate);
    366       const B& barc = (*mapper_)(aarc);
    367       AddArc(s, barc);
    368     }
    369 
    370     // Check for superfinal arcs.
    371     if (!HasFinal(s) || Final(s) == Weight::Zero())
    372       switch (final_action_) {
    373         case MAP_NO_SUPERFINAL:
    374         default:
    375           break;
    376         case MAP_ALLOW_SUPERFINAL: {
    377           B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
    378                                         kNoStateId));
    379           if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
    380             if (superfinal_ == kNoStateId)
    381               superfinal_ = nstates_++;
    382             final_arc.nextstate = superfinal_;
    383             AddArc(s, final_arc);
    384           }
    385           break;
    386         }
    387       case MAP_REQUIRE_SUPERFINAL: {
    388         B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
    389                                       kNoStateId));
    390         if (final_arc.ilabel != 0 || final_arc.olabel != 0 ||
    391             final_arc.weight != B::Weight::Zero())
    392           AddArc(s, B(final_arc.ilabel, final_arc.olabel,
    393                       final_arc.weight, superfinal_));
    394         break;
    395       }
    396     }
    397     SetArcs(s);
    398   }
    399 
    400  private:
    401   void Init() {
    402     SetType("map");
    403     SetInputSymbols(fst_->InputSymbols());
    404     SetOutputSymbols(fst_->OutputSymbols());
    405     if (fst_->Start() == kNoStateId) {
    406       final_action_ = MAP_NO_SUPERFINAL;
    407       SetProperties(kNullProperties);
    408     } else {
    409       final_action_ = mapper_->FinalAction();
    410       uint64 props = fst_->Properties(kCopyProperties, false);
    411       SetProperties(mapper_->Properties(props));
    412       if (final_action_ == MAP_REQUIRE_SUPERFINAL)
    413         superfinal_ = 0;
    414     }
    415   }
    416 
    417   // Maps from output state to input state.
    418   StateId FindIState(StateId s) {
    419     if (superfinal_ == kNoStateId || s < superfinal_)
    420       return s;
    421     else
    422       return s - 1;
    423   }
    424 
    425   // Maps from input state to output state.
    426   StateId FindOState(StateId is) {
    427     StateId os;
    428     if (superfinal_ == kNoStateId || is < superfinal_)
    429       os = is;
    430     else
    431       os = is + 1;
    432 
    433     if (os >= nstates_)
    434       nstates_ = os + 1;
    435 
    436     return os;
    437   }
    438 
    439 
    440   const Fst<A> *fst_;
    441   C*   mapper_;
    442   bool own_mapper_;
    443   MapFinalAction final_action_;
    444 
    445   StateId superfinal_;
    446   StateId nstates_;
    447 };
    448 
    449 
    450 // Maps an arc type A to an arc type B using Mapper function object
    451 // C. This version is a delayed Fst.
    452 template <class A, class B, class C>
    453 class MapFst : public Fst<B> {
    454  public:
    455   friend class ArcIterator< MapFst<A, B, C> >;
    456   friend class StateIterator< MapFst<A, B, C> >;
    457   friend class CacheArcIterator< MapFst<A, B, C> >;
    458 
    459   typedef B Arc;
    460   typedef typename B::Weight Weight;
    461   typedef typename B::StateId StateId;
    462   typedef CacheState<B> State;
    463 
    464   MapFst(const Fst<A> &fst, const C &mapper,
    465              const MapFstOptions& opts)
    466       : impl_(new MapFstImpl<A, B, C>(fst, mapper, opts)) {}
    467 
    468   MapFst(const Fst<A> &fst, C* mapper,
    469              const MapFstOptions& opts)
    470       : impl_(new MapFstImpl<A, B, C>(fst, mapper, opts)) {}
    471 
    472   MapFst(const Fst<A> &fst, const C &mapper)
    473       : impl_(new MapFstImpl<A, B, C>(fst, mapper,
    474                                           MapFstOptions())) {}
    475 
    476   MapFst(const Fst<A> &fst, C* mapper)
    477       : impl_(new MapFstImpl<A, B, C>(fst, mapper,
    478                                           MapFstOptions())) {}
    479 
    480   MapFst(const MapFst<A, B, C> &fst) : Fst<B>(fst), impl_(fst.impl_) {
    481     impl_->IncrRefCount();
    482   }
    483 
    484   virtual ~MapFst() { if (!impl_->DecrRefCount()) delete impl_;  }
    485 
    486   virtual StateId Start() const { return impl_->Start(); }
    487 
    488   virtual Weight Final(StateId s) const { return impl_->Final(s); }
    489 
    490   StateId NumStates() const { return impl_->NumStates(); }
    491 
    492   size_t NumArcs(StateId s) const { return impl_->NumArcs(s); }
    493 
    494   size_t NumInputEpsilons(StateId s) const {
    495     return impl_->NumInputEpsilons(s);
    496   }
    497 
    498   size_t NumOutputEpsilons(StateId s) const {
    499     return impl_->NumOutputEpsilons(s);
    500   }
    501 
    502   virtual uint64 Properties(uint64 mask, bool test) const {
    503     if (test) {
    504       uint64 known, test = TestProperties(*this, mask, &known);
    505       impl_->SetProperties(test, known);
    506       return test & mask;
    507     } else {
    508       return impl_->Properties(mask);
    509     }
    510   }
    511 
    512   virtual const string& Type() const { return impl_->Type(); }
    513 
    514   virtual MapFst<A, B, C> *Copy() const {
    515     return new MapFst<A, B, C>(*this);
    516   }
    517 
    518   virtual const SymbolTable* InputSymbols() const {
    519     return impl_->InputSymbols();
    520   }
    521 
    522   virtual const SymbolTable* OutputSymbols() const {
    523     return impl_->OutputSymbols();
    524   }
    525 
    526  virtual inline void InitStateIterator(StateIteratorData<B> *data) const;
    527 
    528   virtual void InitArcIterator(StateId s, ArcIteratorData<B> *data) const {
    529     impl_->InitArcIterator(s, data);
    530   }
    531 
    532  private:
    533   MapFstImpl<A, B, C> *impl_;
    534 
    535   void operator=(const MapFst<A, B, C> &fst);  // disallow
    536 };
    537 
    538 
    539 // Specialization for MapFst.
    540 template<class A, class B, class C>
    541 class StateIterator< MapFst<A, B, C> > : public StateIteratorBase<B> {
    542  public:
    543   typedef typename B::StateId StateId;
    544 
    545   explicit StateIterator(const MapFst<A, B, C> &fst)
    546       : impl_(fst.impl_), siter_(*impl_->fst_), s_(0),
    547         superfinal_(impl_->final_action_ == MAP_REQUIRE_SUPERFINAL)
    548   { CheckSuperfinal(); }
    549 
    550   bool Done() const { return siter_.Done() && !superfinal_; }
    551 
    552   StateId Value() const { return s_; }
    553 
    554   void Next() {
    555     ++s_;
    556     if (!siter_.Done()) {
    557       siter_.Next();
    558       CheckSuperfinal();
    559     }
    560     else if (superfinal_)
    561       superfinal_ = false;
    562   }
    563 
    564   void Reset() {
    565     s_ = 0;
    566     siter_.Reset();
    567     superfinal_ = impl_->final_action_ == MAP_REQUIRE_SUPERFINAL;
    568     CheckSuperfinal();
    569   }
    570 
    571  private:
    572   void CheckSuperfinal() {
    573     if (impl_->final_action_ != MAP_ALLOW_SUPERFINAL || superfinal_)
    574       return;
    575     if (!siter_.Done()) {
    576       B final_arc = (*impl_->mapper_)(A(0, 0, impl_->fst_->Final(s_),
    577                                            kNoStateId));
    578       if (final_arc.ilabel != 0 || final_arc.olabel != 0)
    579         superfinal_ = true;
    580     }
    581   }
    582 
    583   const MapFstImpl<A, B, C> *impl_;
    584   StateIterator< Fst<A> > siter_;
    585   StateId s_;
    586   bool superfinal_;    // true if there is a superfinal state and not done
    587 
    588   DISALLOW_EVIL_CONSTRUCTORS(StateIterator);
    589 };
    590 
    591 // Specialization for MapFst.
    592 template <class A, class B, class C>
    593 class ArcIterator< MapFst<A, B, C> >
    594     : public CacheArcIterator< MapFst<A, B, C> > {
    595  public:
    596   typedef typename A::StateId StateId;
    597 
    598   ArcIterator(const MapFst<A, B, C> &fst, StateId s)
    599       : CacheArcIterator< MapFst<A, B, C> >(fst, s) {
    600     if (!fst.impl_->HasArcs(s))
    601       fst.impl_->Expand(s);
    602   }
    603 
    604  private:
    605   DISALLOW_EVIL_CONSTRUCTORS(ArcIterator);
    606 };
    607 
    608 template <class A, class B, class C> inline
    609 void MapFst<A, B, C>::InitStateIterator(StateIteratorData<B> *data)
    610     const {
    611   data->base = new StateIterator< MapFst<A, B, C> >(*this);
    612 }
    613 
    614 
    615 //
    616 // Utility Mappers
    617 //
    618 
    619 // Mapper that returns its input.
    620 template <class A>
    621 struct IdentityMapper {
    622   typedef A FromArc;
    623   typedef A ToArc;
    624 
    625   A operator()(const A &arc) const { return arc; }
    626 
    627   MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
    628 
    629   uint64 Properties(uint64 props) const { return props; }
    630 };
    631 
    632 
    633 // Mapper that returns its input with final states redirected to
    634 // a single super-final state.
    635 template <class A>
    636 struct SuperFinalMapper {
    637   typedef A FromArc;
    638   typedef A ToArc;
    639 
    640   A operator()(const A &arc) const { return arc; }
    641 
    642   MapFinalAction FinalAction() const { return MAP_REQUIRE_SUPERFINAL; }
    643 
    644   uint64 Properties(uint64 props) const {
    645     return props & kAddSuperFinalProperties;
    646   }
    647 };
    648 
    649 
    650 // Mapper from StdArc to LogArc.
    651 struct StdToLogMapper {
    652   typedef StdArc FromArc;
    653   typedef LogArc ToArc;
    654 
    655   LogArc operator()(const StdArc &arc) const {
    656     return LogArc(arc.ilabel, arc.olabel, arc.weight.Value(), arc.nextstate);
    657   }
    658 
    659   MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
    660 
    661   uint64 Properties(uint64 props) const { return props; }
    662 };
    663 
    664 
    665 // Mapper from LogArc to StdArc.
    666 struct LogToStdMapper {
    667   typedef LogArc FromArc;
    668   typedef StdArc ToArc;
    669 
    670   StdArc operator()(const LogArc &arc) const {
    671     return StdArc(arc.ilabel, arc.olabel, arc.weight.Value(), arc.nextstate);
    672   }
    673 
    674   MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
    675 
    676   uint64 Properties(uint64 props) const { return props; }
    677 };
    678 
    679 
    680 // Mapper from A to GallicArc<A>.
    681 template <class A, StringType S = STRING_LEFT>
    682 struct ToGallicMapper {
    683   typedef A FromArc;
    684   typedef GallicArc<A, S> ToArc;
    685 
    686   typedef StringWeight<typename A::Label, S> SW;
    687   typedef typename A::Weight AW;
    688   typedef typename GallicArc<A, S>::Weight GW;
    689 
    690   ToArc operator()(const A &arc) const {
    691     // 'Super-final' arc.
    692     if (arc.nextstate == kNoStateId && arc.weight != AW::Zero())
    693       return ToArc(0, 0, GW(SW::One(), arc.weight), kNoStateId);
    694     // 'Super-non-final' arc.
    695     else if (arc.nextstate == kNoStateId)
    696       return ToArc(0, 0, GW(SW::Zero(), arc.weight), kNoStateId);
    697     // Epsilon label.
    698     else if (arc.olabel == 0)
    699       return ToArc(arc.ilabel, arc.ilabel,
    700                    GW(SW::One(), arc.weight), arc.nextstate);
    701     // Regular label.
    702     else
    703       return ToArc(arc.ilabel, arc.ilabel,
    704                    GW(SW(arc.olabel), arc.weight), arc.nextstate);
    705   }
    706 
    707   MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
    708 
    709   uint64 Properties(uint64 props) const {
    710     return ProjectProperties(props, true) & kWeightInvariantProperties;
    711   }
    712 };
    713 
    714 
    715 // Mapper from GallicArc<A> to A.
    716 template <class A, StringType S = STRING_LEFT>
    717 struct FromGallicMapper {
    718   typedef GallicArc<A, S> FromArc;
    719   typedef A ToArc;
    720 
    721   typedef typename A::Label Label;
    722   typedef StringWeight<Label, S> SW;
    723   typedef typename A::Weight AW;
    724   typedef typename GallicArc<A, S>::Weight GW;
    725 
    726   A operator()(const FromArc &arc) const {
    727     // 'Super-non-final' arc.
    728     if (arc.nextstate == kNoStateId && arc.weight == GW::Zero())
    729       return A(arc.ilabel, 0, AW::Zero(), kNoStateId);
    730 
    731     SW w1 = arc.weight.Value1();
    732     AW w2 = arc.weight.Value2();
    733     StringWeightIterator<Label, S> iter1(w1);
    734 
    735     Label l = w1.Size() == 1 ? iter1.Value() : 0;
    736 
    737     CHECK(l != kStringInfinity);
    738     CHECK(l != kStringBad);
    739     CHECK(arc.ilabel == arc.olabel);
    740     CHECK(w1.Size() <= 1);
    741 
    742     return A(arc.ilabel, l, w2, arc.nextstate);
    743   }
    744 
    745   MapFinalAction FinalAction() const { return MAP_ALLOW_SUPERFINAL; }
    746 
    747   uint64 Properties(uint64 props) const {
    748     return props & kOLabelInvariantProperties &
    749       kWeightInvariantProperties & kAddSuperFinalProperties;
    750   }
    751 };
    752 
    753 
    754 // Mapper from GallicArc<A> to A.
    755 template <class A, StringType S = STRING_LEFT>
    756 struct GallicToNewSymbolsMapper {
    757   typedef GallicArc<A, S> FromArc;
    758   typedef A ToArc;
    759 
    760   typedef typename A::StateId StateId;
    761   typedef typename A::Label Label;
    762   typedef StringWeight<Label, S> SW;
    763   typedef typename A::Weight AW;
    764   typedef typename GallicArc<A, S>::Weight GW;
    765 
    766   GallicToNewSymbolsMapper(MutableFst<ToArc> *fst)
    767       : fst_(fst), lmax_(0), osymbols_(fst->OutputSymbols()), isymbols_(0) {
    768     fst_->DeleteStates();
    769     state_ = fst_->AddState();
    770     fst_->SetStart(state_);
    771     fst_->SetFinal(state_, AW::One());
    772     if (osymbols_) {
    773       string name = osymbols_->Name() + "_from_gallic";
    774       isymbols_ = new SymbolTable(name);
    775       isymbols_->AddSymbol(osymbols_->Find((int64) 0), 0);
    776    }
    777     fst_->SetInputSymbols(isymbols_);
    778   }
    779 
    780   A operator()(const FromArc &arc) {
    781     // 'Super-non-final' arc.
    782     if (arc.nextstate == kNoStateId && arc.weight == GW::Zero())
    783       return A(arc.ilabel, 0, AW::Zero(), kNoStateId);
    784 
    785     SW w1 = arc.weight.Value1();
    786     AW w2 = arc.weight.Value2();
    787     Label l;
    788 
    789     if (w1.Size() == 0) {
    790       l = 0;
    791     } else {
    792       typename Map::iterator miter = map_.find(w1);
    793       if (miter != map_.end()) {
    794         l = (*miter).second;
    795       } else {
    796         l = ++lmax_;
    797         map_.insert(pair<const SW, Label>(w1, l));
    798         StringWeightIterator<Label, S> iter1(w1);
    799         StateId n;
    800         string s;
    801         for(ssize_t i = 0, p = state_;
    802             i < w1.Size();
    803             ++i, iter1.Next(), p = n) {
    804           n = i == w1.Size() - 1 ? state_ : fst_->AddState();
    805           fst_->AddArc(p, ToArc(i ? 0 : l, iter1.Value(), AW::One(), n));
    806           if (isymbols_) {
    807             if (i) s = s + "_";
    808             s = s + osymbols_->Find(iter1.Value());
    809           }
    810         }
    811         if (isymbols_)
    812           isymbols_->AddSymbol(s, l);
    813       }
    814     }
    815 
    816     CHECK(l != kStringInfinity);
    817     CHECK(l != kStringBad);
    818     CHECK(arc.ilabel == arc.olabel);
    819 
    820     return A(arc.ilabel, l, w2, arc.nextstate);
    821   }
    822 
    823   MapFinalAction FinalAction() const { return MAP_ALLOW_SUPERFINAL; }
    824 
    825   uint64 Properties(uint64 props) const {
    826     return props & kOLabelInvariantProperties &
    827       kWeightInvariantProperties & kAddSuperFinalProperties;
    828   }
    829 
    830  private:
    831   class StringKey {
    832    public:
    833     size_t operator()(const SW &x) const {
    834       return x.Hash();
    835     }
    836   };
    837 
    838   typedef hash_map<SW, Label, StringKey> Map;
    839 
    840   MutableFst<ToArc> *fst_;
    841   Map map_;
    842   Label lmax_;
    843   StateId state_;
    844   SymbolTable *osymbols_, *isymbols_;
    845 };
    846 
    847 
    848 // Mapper to add a constant to all weights.
    849 template <class A>
    850 struct PlusMapper {
    851   typedef typename A::Weight Weight;
    852 
    853   explicit PlusMapper(Weight w) : weight_(w) {}
    854 
    855   A operator()(const A &arc) const {
    856     if (arc.weight == Weight::Zero())
    857       return arc;
    858     Weight w = Plus(arc.weight, weight_);
    859     return A(arc.ilabel, arc.olabel, w, arc.nextstate);
    860   }
    861 
    862   MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
    863 
    864   uint64 Properties(uint64 props) const {
    865     return props & kWeightInvariantProperties;
    866   }
    867 
    868   Weight weight_;
    869 };
    870 
    871 
    872 // Mapper to (right) multiply a constant to all weights.
    873 template <class A>
    874 struct TimesMapper {
    875   typedef typename A::Weight Weight;
    876 
    877   explicit TimesMapper(Weight w) : weight_(w) {}
    878 
    879   A operator()(const A &arc) const {
    880     if (arc.weight == Weight::Zero())
    881       return arc;
    882     Weight w = Times(arc.weight, weight_);
    883     return A(arc.ilabel, arc.olabel, w, arc.nextstate);
    884   }
    885 
    886   MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
    887 
    888   uint64 Properties(uint64 props) const {
    889     return props & kWeightInvariantProperties;
    890   }
    891 
    892   Weight weight_;
    893 };
    894 
    895 
    896 // Mapper to map all non-Zero() weights to One().
    897 template <class A, class B = A>
    898 struct RmWeightMapper {
    899   typedef A FromArc;
    900   typedef B ToArc;
    901   typedef typename FromArc::Weight FromWeight;
    902   typedef typename ToArc::Weight ToWeight;
    903 
    904   B operator()(const A &arc) const {
    905     ToWeight w = arc.weight != FromWeight::Zero() ?
    906                    ToWeight::One() : ToWeight::Zero();
    907     return B(arc.ilabel, arc.olabel, w, arc.nextstate);
    908   }
    909 
    910   MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
    911 
    912   uint64 Properties(uint64 props) const {
    913     return props & kWeightInvariantProperties | kUnweighted;
    914   }
    915 };
    916 
    917 
    918 // Mapper to quantize all weights.
    919 template <class A, class B = A>
    920 struct QuantizeMapper {
    921   typedef A FromArc;
    922   typedef B ToArc;
    923   typedef typename FromArc::Weight FromWeight;
    924   typedef typename ToArc::Weight ToWeight;
    925 
    926   QuantizeMapper() : delta_(kDelta) {}
    927 
    928   explicit QuantizeMapper(float d) : delta_(d) {}
    929 
    930   B operator()(const A &arc) const {
    931     ToWeight w = arc.weight.Quantize(delta_);
    932     return B(arc.ilabel, arc.olabel, w, arc.nextstate);
    933   }
    934 
    935   MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
    936 
    937   uint64 Properties(uint64 props) const {
    938     return props & kWeightInvariantProperties;
    939   }
    940 
    941   float delta_;
    942 };
    943 
    944 
    945 // Mapper from A to B under the assumption:
    946 //    B::Weight = A::Weight::ReverseWeight
    947 //    B::Label == A::Label
    948 //    B::StateId == A::StateId
    949 // The weight is reversed, while the label and nextstate preserved
    950 // in the mapping.
    951 template <class A, class B>
    952 struct ReverseWeightMapper {
    953   typedef A FromArc;
    954   typedef B ToArc;
    955 
    956   B operator()(const A &arc) const {
    957     return B(arc.ilabel, arc.olabel, arc.weight.Reverse(), arc.nextstate);
    958   }
    959 
    960   MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
    961 
    962   uint64 Properties(uint64 props) const { return props; }
    963 };
    964 
    965 }  // namespace fst
    966 
    967 #endif  // FST_LIB_MAP_H__
    968