map.h revision ea4ad6085a8661b5513c394316108c0ef26f3e7b 
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
26namespace fst {
27
28// This determines how final weights are mapped.
29enum 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.
80template<class A, class C>
81void 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.
148template<class A, class C>
149void 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.
157template<class A, class B, class C>
158void 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.
230template<class A, class B, class C>
231void Map(const Fst<A> &ifst, MutableFst<B> *ofst, C mapper) {
232  Map(ifst, ofst, &mapper);
233}
234
235
236struct 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
245template <class A, class B, class C> class MapFst;
246
247// Implementation of delayed MapFst.
248template <class A, class B, class C>
249class 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      this->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          this->SetFinal(s, final_arc.weight);
310          break;
311        }
312        case MAP_ALLOW_SUPERFINAL: {
313          if (s == superfinal_) {
314            this->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              this->SetFinal(s, final_arc.weight);
320            else
321              this->SetFinal(s, Weight::Zero());
322          }
323          break;
324        }
325        case MAP_REQUIRE_SUPERFINAL: {
326          this->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_) { this->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      this->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            this->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          this->AddArc(s, B(final_arc.ilabel, final_arc.olabel,
393                      final_arc.weight, superfinal_));
394        break;
395      }
396    }
397    this->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.
452template <class A, class B, class C>
453class 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.
540template<class A, class B, class C>
541class 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.
592template <class A, class B, class C>
593class 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
608template <class A, class B, class C> inline
609void 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.
620template <class A>
621struct 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.
635template <class A>
636struct 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.
651struct 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.
666struct 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>.
681template <class A, StringType S = STRING_LEFT>
682struct 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.
716template <class A, StringType S = STRING_LEFT>
717struct 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.
755template <class A, StringType S = STRING_LEFT>
756struct 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.
849template <class A>
850struct 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.
873template <class A>
874struct 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().
897template <class A, class B = A>
898struct 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.
919template <class A, class B = A>
920struct 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.
951template <class A, class B>
952struct 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