include/fst/arc-map.h

// arc-map.h

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright 2005-2010 Google, Inc.
// Author: riley@google.com (Michael Riley)
//
// \file
// Class to map over/transform arcs e.g., change semirings or
// implement project/invert. Consider using when operation does
// not change the number of arcs (except possibly superfinal arcs).

#ifndef FST_LIB_ARC_MAP_H__
#define FST_LIB_ARC_MAP_H__

#include <tr1/unordered_map>
using std::tr1::unordered_map;
using std::tr1::unordered_multimap;
#include <string>
#include <utility>
using std::pair; using std::make_pair;

#include <fst/cache.h>
#include <fst/mutable-fst.h>


namespace fst {

// This determines how final weights are mapped.
enum MapFinalAction {
  // A final weight is mapped into a final weight. An error
  // is raised if this is not possible.
  MAP_NO_SUPERFINAL,

  // A final weight is mapped to an arc to the superfinal state
  // when the result cannot be represented as a final weight.
  // The superfinal state will be added only if it is needed.
  MAP_ALLOW_SUPERFINAL,

  // A final weight is mapped to an arc to the superfinal state
  // unless the result can be represented as a final weight of weight
  // Zero(). The superfinal state is always added (if the input is
  // not the empty Fst).
  MAP_REQUIRE_SUPERFINAL
};

// This determines how symbol tables are mapped.
enum MapSymbolsAction {
  // Symbols should be cleared in the result by the map.
  MAP_CLEAR_SYMBOLS,

  // Symbols should be copied from the input FST by the map.
  MAP_COPY_SYMBOLS,

  // Symbols should not be modified in the result by the map itself.
  // (They may set by the mapper).
  MAP_NOOP_SYMBOLS
};

// ArcMapper Interface - class determinies how arcs and final weights
// are mapped. Useful for implementing operations that do not change
// the number of arcs (expect possibly superfinal arcs).
//
// class ArcMapper {
//  public:
//   typedef A FromArc;
//   typedef B ToArc;
//
//   // Maps an arc type A to arc type B.
//   B operator()(const A &arc);
//   // Specifies final action the mapper requires (see above).
//   // The mapper will be passed final weights as arcs of the
//   // form A(0, 0, weight, kNoStateId).
//   MapFinalAction FinalAction() const;
//   // Specifies input symbol table action the mapper requires (see above).
//   MapSymbolsAction InputSymbolsAction() const;
//   // Specifies output symbol table action the mapper requires (see above).
//   MapSymbolsAction OutputSymbolsAction() const;
//   // This specifies the known properties of an Fst mapped by this
//   // mapper. It takes as argument the input Fst's known properties.
//   uint64 Properties(uint64 props) const;
// };
//
// The ArcMap functions and classes below will use the FinalAction()
// method of the mapper to determine how to treat final weights,
// e.g. whether to add a superfinal state. They will use the Properties()
// method to set the result Fst properties.
//
// We include a various map versions below. One dimension of
// variation is whether the mapping mutates its input, writes to a
// new result Fst, or is an on-the-fly Fst. Another dimension is how
// we pass the mapper. We allow passing the mapper by pointer
// for cases that we need to change the state of the user's mapper.
// This is the case with the encode mapper, which is reused during
// decoding. We also include map versions that pass the mapper
// by value or const reference when this suffices.


// Maps an arc type A using a mapper function object C, passed
// by pointer.  This version modifies its Fst input.
template<class A, class C>
void ArcMap(MutableFst<A> *fst, C* mapper) {
  typedef typename A::StateId StateId;
  typedef typename A::Weight Weight;

  if (mapper->InputSymbolsAction() == MAP_CLEAR_SYMBOLS)
    fst->SetInputSymbols(0);

  if (mapper->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS)
    fst->SetOutputSymbols(0);

  if (fst->Start() == kNoStateId)
    return;

  uint64 props = fst->Properties(kFstProperties, false);

  MapFinalAction final_action = mapper->FinalAction();
  StateId superfinal = kNoStateId;
  if (final_action == MAP_REQUIRE_SUPERFINAL) {
    superfinal = fst->AddState();
    fst->SetFinal(superfinal, Weight::One());
  }

  for (StateId s = 0; s < fst->NumStates(); ++s) {
    for (MutableArcIterator< MutableFst<A> > aiter(fst, s);
         !aiter.Done(); aiter.Next()) {
      const A &arc = aiter.Value();
      aiter.SetValue((*mapper)(arc));
    }

    switch (final_action) {
      case MAP_NO_SUPERFINAL:
      default: {
        A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId));
        if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
          FSTERROR() << "ArcMap: non-zero arc labels for superfinal arc";
          fst->SetProperties(kError, kError);
        }

        fst->SetFinal(s, final_arc.weight);
        break;
      }
      case MAP_ALLOW_SUPERFINAL: {
        if (s != superfinal) {
          A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId));
          if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
            // Add a superfinal state if not already done.
            if (superfinal == kNoStateId) {
              superfinal = fst->AddState();
              fst->SetFinal(superfinal, Weight::One());
            }
            final_arc.nextstate = superfinal;
            fst->AddArc(s, final_arc);
            fst->SetFinal(s, Weight::Zero());
          } else {
            fst->SetFinal(s, final_arc.weight);
          }
        }
        break;
      }
      case MAP_REQUIRE_SUPERFINAL: {
        if (s != superfinal) {
          A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId));
          if (final_arc.ilabel != 0 || final_arc.olabel != 0 ||
              final_arc.weight != Weight::Zero())
            fst->AddArc(s, A(final_arc.ilabel, final_arc.olabel,
                             final_arc.weight, superfinal));
            fst->SetFinal(s, Weight::Zero());
        }
        break;
      }
    }
  }
  fst->SetProperties(mapper->Properties(props), kFstProperties);
}


// Maps an arc type A using a mapper function object C, passed
// by value.  This version modifies its Fst input.
template<class A, class C>
void ArcMap(MutableFst<A> *fst, C mapper) {
  ArcMap(fst, &mapper);
}


// Maps an arc type A to an arc type B using mapper function
// object C, passed by pointer. This version writes the mapped
// input Fst to an output MutableFst.
template<class A, class B, class C>
void ArcMap(const Fst<A> &ifst, MutableFst<B> *ofst, C* mapper) {
  typedef typename A::StateId StateId;
  typedef typename A::Weight Weight;

  ofst->DeleteStates();

  if (mapper->InputSymbolsAction() == MAP_COPY_SYMBOLS)
    ofst->SetInputSymbols(ifst.InputSymbols());
  else if (mapper->InputSymbolsAction() == MAP_CLEAR_SYMBOLS)
    ofst->SetInputSymbols(0);

  if (mapper->OutputSymbolsAction() == MAP_COPY_SYMBOLS)
    ofst->SetOutputSymbols(ifst.OutputSymbols());
  else if (mapper->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS)
    ofst->SetOutputSymbols(0);

  uint64 iprops = ifst.Properties(kCopyProperties, false);

  if (ifst.Start() == kNoStateId) {
    if (iprops & kError) ofst->SetProperties(kError, kError);
    return;
  }

  MapFinalAction final_action = mapper->FinalAction();
  if (ifst.Properties(kExpanded, false)) {
    ofst->ReserveStates(CountStates(ifst) +
                        final_action == MAP_NO_SUPERFINAL ? 0 : 1);
  }

  // Add all states.
  for (StateIterator< Fst<A> > siter(ifst); !siter.Done(); siter.Next())
    ofst->AddState();

  StateId superfinal = kNoStateId;
  if (final_action == MAP_REQUIRE_SUPERFINAL) {
    superfinal = ofst->AddState();
    ofst->SetFinal(superfinal, B::Weight::One());
  }
  for (StateIterator< Fst<A> > siter(ifst); !siter.Done(); siter.Next()) {
    StateId s = siter.Value();
    if (s == ifst.Start())
      ofst->SetStart(s);

    ofst->ReserveArcs(s, ifst.NumArcs(s));
    for (ArcIterator< Fst<A> > aiter(ifst, s); !aiter.Done(); aiter.Next())
      ofst->AddArc(s, (*mapper)(aiter.Value()));

    switch (final_action) {
      case MAP_NO_SUPERFINAL:
      default: {
        B final_arc = (*mapper)(A(0, 0, ifst.Final(s), kNoStateId));
        if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
          FSTERROR() << "ArcMap: non-zero arc labels for superfinal arc";
          ofst->SetProperties(kError, kError);
        }
        ofst->SetFinal(s, final_arc.weight);
        break;
      }
      case MAP_ALLOW_SUPERFINAL: {
        B final_arc = (*mapper)(A(0, 0, ifst.Final(s), kNoStateId));
        if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
            // Add a superfinal state if not already done.
          if (superfinal == kNoStateId) {
            superfinal = ofst->AddState();
            ofst->SetFinal(superfinal, B::Weight::One());
          }
          final_arc.nextstate = superfinal;
          ofst->AddArc(s, final_arc);
          ofst->SetFinal(s, B::Weight::Zero());
        } else {
          ofst->SetFinal(s, final_arc.weight);
        }
        break;
      }
      case MAP_REQUIRE_SUPERFINAL: {
        B final_arc = (*mapper)(A(0, 0, ifst.Final(s), kNoStateId));
        if (final_arc.ilabel != 0 || final_arc.olabel != 0 ||
            final_arc.weight != B::Weight::Zero())
          ofst->AddArc(s, B(final_arc.ilabel, final_arc.olabel,
                            final_arc.weight, superfinal));
        ofst->SetFinal(s, B::Weight::Zero());
        break;
      }
    }
  }
  uint64 oprops = ofst->Properties(kFstProperties, false);
  ofst->SetProperties(mapper->Properties(iprops) | oprops, kFstProperties);
}

// Maps an arc type A to an arc type B using mapper function
// object C, passed by value. This version writes the mapped input
// Fst to an output MutableFst.
template<class A, class B, class C>
void ArcMap(const Fst<A> &ifst, MutableFst<B> *ofst, C mapper) {
  ArcMap(ifst, ofst, &mapper);
}


struct ArcMapFstOptions : public CacheOptions {
  // ArcMapFst default caching behaviour is to do no caching. Most
  // mappers are cheap and therefore we save memory by not doing
  // caching.
  ArcMapFstOptions() : CacheOptions(true, 0) {}
  ArcMapFstOptions(const CacheOptions& opts) : CacheOptions(opts) {}
};


template <class A, class B, class C> class ArcMapFst;

// Implementation of delayed ArcMapFst.
template <class A, class B, class C>
class ArcMapFstImpl : public CacheImpl<B> {
 public:
  using FstImpl<B>::SetType;
  using FstImpl<B>::SetProperties;
  using FstImpl<B>::SetInputSymbols;
  using FstImpl<B>::SetOutputSymbols;

  using CacheImpl<B>::PushArc;
  using CacheImpl<B>::HasArcs;
  using CacheImpl<B>::HasFinal;
  using CacheImpl<B>::HasStart;
  using CacheImpl<B>::SetArcs;
  using CacheImpl<B>::SetFinal;
  using CacheImpl<B>::SetStart;

  friend class StateIterator< ArcMapFst<A, B, C> >;

  typedef B Arc;
  typedef typename B::Weight Weight;
  typedef typename B::StateId StateId;

  ArcMapFstImpl(const Fst<A> &fst, const C &mapper,
                 const ArcMapFstOptions& opts)
      : CacheImpl<B>(opts),
        fst_(fst.Copy()),
        mapper_(new C(mapper)),
        own_mapper_(true),
        superfinal_(kNoStateId),
        nstates_(0) {
    Init();
  }

  ArcMapFstImpl(const Fst<A> &fst, C *mapper,
                 const ArcMapFstOptions& opts)
      : CacheImpl<B>(opts),
        fst_(fst.Copy()),
        mapper_(mapper),
        own_mapper_(false),
        superfinal_(kNoStateId),
        nstates_(0) {
    Init();
  }

  ArcMapFstImpl(const ArcMapFstImpl<A, B, C> &impl)
      : CacheImpl<B>(impl),
        fst_(impl.fst_->Copy(true)),
        mapper_(new C(*impl.mapper_)),
        own_mapper_(true),
        superfinal_(kNoStateId),
        nstates_(0) {
    Init();
  }

  ~ArcMapFstImpl() {
    delete fst_;
    if (own_mapper_) delete mapper_;
  }

  StateId Start() {
    if (!HasStart())
      SetStart(FindOState(fst_->Start()));
    return CacheImpl<B>::Start();
  }

  Weight Final(StateId s) {
    if (!HasFinal(s)) {
      switch (final_action_) {
        case MAP_NO_SUPERFINAL:
        default: {
          B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
                                        kNoStateId));
          if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
            FSTERROR() << "ArcMapFst: non-zero arc labels for superfinal arc";
            SetProperties(kError, kError);
          }
          SetFinal(s, final_arc.weight);
          break;
        }
        case MAP_ALLOW_SUPERFINAL: {
          if (s == superfinal_) {
            SetFinal(s, Weight::One());
          } else {
            B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
                                          kNoStateId));
            if (final_arc.ilabel == 0 && final_arc.olabel == 0)
              SetFinal(s, final_arc.weight);
            else
              SetFinal(s, Weight::Zero());
          }
          break;
        }
        case MAP_REQUIRE_SUPERFINAL: {
          SetFinal(s, s == superfinal_ ? Weight::One() : Weight::Zero());
          break;
        }
      }
    }
    return CacheImpl<B>::Final(s);
  }

  size_t NumArcs(StateId s) {
    if (!HasArcs(s))
      Expand(s);
    return CacheImpl<B>::NumArcs(s);
  }

  size_t NumInputEpsilons(StateId s) {
    if (!HasArcs(s))
      Expand(s);
    return CacheImpl<B>::NumInputEpsilons(s);
  }

  size_t NumOutputEpsilons(StateId s) {
    if (!HasArcs(s))
      Expand(s);
    return CacheImpl<B>::NumOutputEpsilons(s);
  }

  uint64 Properties() const { return Properties(kFstProperties); }

  // Set error if found; return FST impl properties.
  uint64 Properties(uint64 mask) const {
    if ((mask & kError) && (fst_->Properties(kError, false) ||
                            (mapper_->Properties(0) & kError)))
      SetProperties(kError, kError);
    return FstImpl<Arc>::Properties(mask);
  }

  void InitArcIterator(StateId s, ArcIteratorData<B> *data) {
    if (!HasArcs(s))
      Expand(s);
    CacheImpl<B>::InitArcIterator(s, data);
  }

  void Expand(StateId s) {
    // Add exiting arcs.
    if (s == superfinal_) { SetArcs(s); return; }

    for (ArcIterator< Fst<A> > aiter(*fst_, FindIState(s));
         !aiter.Done(); aiter.Next()) {
      A aarc(aiter.Value());
      aarc.nextstate = FindOState(aarc.nextstate);
      const B& barc = (*mapper_)(aarc);
      PushArc(s, barc);
    }

    // Check for superfinal arcs.
    if (!HasFinal(s) || Final(s) == Weight::Zero())
      switch (final_action_) {
        case MAP_NO_SUPERFINAL:
        default:
          break;
        case MAP_ALLOW_SUPERFINAL: {
          B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
                                        kNoStateId));
          if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
            if (superfinal_ == kNoStateId)
              superfinal_ = nstates_++;
            final_arc.nextstate = superfinal_;
            PushArc(s, final_arc);
          }
          break;
        }
      case MAP_REQUIRE_SUPERFINAL: {
        B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
                                      kNoStateId));
        if (final_arc.ilabel != 0 || final_arc.olabel != 0 ||
            final_arc.weight != B::Weight::Zero())
          PushArc(s, B(final_arc.ilabel, final_arc.olabel,
                      final_arc.weight, superfinal_));
        break;
      }
    }
    SetArcs(s);
  }

 private:
  void Init() {
    SetType("map");

    if (mapper_->InputSymbolsAction() == MAP_COPY_SYMBOLS)
      SetInputSymbols(fst_->InputSymbols());
    else if (mapper_->InputSymbolsAction() == MAP_CLEAR_SYMBOLS)
      SetInputSymbols(0);

    if (mapper_->OutputSymbolsAction() == MAP_COPY_SYMBOLS)
      SetOutputSymbols(fst_->OutputSymbols());
    else if (mapper_->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS)
      SetOutputSymbols(0);

    if (fst_->Start() == kNoStateId) {
      final_action_ = MAP_NO_SUPERFINAL;
      SetProperties(kNullProperties);
    } else {
      final_action_ = mapper_->FinalAction();
      uint64 props = fst_->Properties(kCopyProperties, false);
      SetProperties(mapper_->Properties(props));
      if (final_action_ == MAP_REQUIRE_SUPERFINAL)
        superfinal_ = 0;
    }
  }

  // Maps from output state to input state.
  StateId FindIState(StateId s) {
    if (superfinal_ == kNoStateId || s < superfinal_)
      return s;
    else
      return s - 1;
  }

  // Maps from input state to output state.
  StateId FindOState(StateId is) {
    StateId os;
    if (superfinal_ == kNoStateId || is < superfinal_)
      os = is;
    else
      os = is + 1;

    if (os >= nstates_)
      nstates_ = os + 1;

    return os;
  }


  const Fst<A> *fst_;
  C*   mapper_;
  bool own_mapper_;
  MapFinalAction final_action_;

  StateId superfinal_;
  StateId nstates_;

  void operator=(const ArcMapFstImpl<A, B, C> &);  // disallow
};


// Maps an arc type A to an arc type B using Mapper function object
// C. This version is a delayed Fst.
template <class A, class B, class C>
class ArcMapFst : public ImplToFst< ArcMapFstImpl<A, B, C> > {
 public:
  friend class ArcIterator< ArcMapFst<A, B, C> >;
  friend class StateIterator< ArcMapFst<A, B, C> >;

  typedef B Arc;
  typedef typename B::Weight Weight;
  typedef typename B::StateId StateId;
  typedef CacheState<B> State;
  typedef ArcMapFstImpl<A, B, C> Impl;

  ArcMapFst(const Fst<A> &fst, const C &mapper, const ArcMapFstOptions& opts)
      : ImplToFst<Impl>(new Impl(fst, mapper, opts)) {}

  ArcMapFst(const Fst<A> &fst, C* mapper, const ArcMapFstOptions& opts)
      : ImplToFst<Impl>(new Impl(fst, mapper, opts)) {}

  ArcMapFst(const Fst<A> &fst, const C &mapper)
      : ImplToFst<Impl>(new Impl(fst, mapper, ArcMapFstOptions())) {}

  ArcMapFst(const Fst<A> &fst, C* mapper)
      : ImplToFst<Impl>(new Impl(fst, mapper, ArcMapFstOptions())) {}

  // See Fst<>::Copy() for doc.
  ArcMapFst(const ArcMapFst<A, B, C> &fst, bool safe = false)
    : ImplToFst<Impl>(fst, safe) {}

  // Get a copy of this ArcMapFst. See Fst<>::Copy() for further doc.
  virtual ArcMapFst<A, B, C> *Copy(bool safe = false) const {
    return new ArcMapFst<A, B, C>(*this, safe);
  }

  virtual inline void InitStateIterator(StateIteratorData<B> *data) const;

  virtual void InitArcIterator(StateId s, ArcIteratorData<B> *data) const {
    GetImpl()->InitArcIterator(s, data);
  }

 private:
  // Makes visible to friends.
  Impl *GetImpl() const { return ImplToFst<Impl>::GetImpl(); }

  void operator=(const ArcMapFst<A, B, C> &fst);  // disallow
};


// Specialization for ArcMapFst.
template<class A, class B, class C>
class StateIterator< ArcMapFst<A, B, C> > : public StateIteratorBase<B> {
 public:
  typedef typename B::StateId StateId;

  explicit StateIterator(const ArcMapFst<A, B, C> &fst)
      : impl_(fst.GetImpl()), siter_(*impl_->fst_), s_(0),
        superfinal_(impl_->final_action_ == MAP_REQUIRE_SUPERFINAL)
  { CheckSuperfinal(); }

  bool Done() const { return siter_.Done() && !superfinal_; }

  StateId Value() const { return s_; }

  void Next() {
    ++s_;
    if (!siter_.Done()) {
      siter_.Next();
      CheckSuperfinal();
    }
    else if (superfinal_)
      superfinal_ = false;
  }

  void Reset() {
    s_ = 0;
    siter_.Reset();
    superfinal_ = impl_->final_action_ == MAP_REQUIRE_SUPERFINAL;
    CheckSuperfinal();
  }

 private:
  // This allows base-class virtual access to non-virtual derived-
  // class members of the same name. It makes the derived class more
  // efficient to use but unsafe to further derive.
  bool Done_() const { return Done(); }
  StateId Value_() const { return Value(); }
  void Next_() { Next(); }
  void Reset_() { Reset(); }

  void CheckSuperfinal() {
    if (impl_->final_action_ != MAP_ALLOW_SUPERFINAL || superfinal_)
      return;
    if (!siter_.Done()) {
      B final_arc = (*impl_->mapper_)(A(0, 0, impl_->fst_->Final(s_),
                                           kNoStateId));
      if (final_arc.ilabel != 0 || final_arc.olabel != 0)
        superfinal_ = true;
    }
  }

  const ArcMapFstImpl<A, B, C> *impl_;
  StateIterator< Fst<A> > siter_;
  StateId s_;
  bool superfinal_;    // true if there is a superfinal state and not done

  DISALLOW_COPY_AND_ASSIGN(StateIterator);
};


// Specialization for ArcMapFst.
template <class A, class B, class C>
class ArcIterator< ArcMapFst<A, B, C> >
    : public CacheArcIterator< ArcMapFst<A, B, C> > {
 public:
  typedef typename A::StateId StateId;

  ArcIterator(const ArcMapFst<A, B, C> &fst, StateId s)
      : CacheArcIterator< ArcMapFst<A, B, C> >(fst.GetImpl(), s) {
    if (!fst.GetImpl()->HasArcs(s))
      fst.GetImpl()->Expand(s);
  }

 private:
  DISALLOW_COPY_AND_ASSIGN(ArcIterator);
};

template <class A, class B, class C> inline
void ArcMapFst<A, B, C>::InitStateIterator(StateIteratorData<B> *data)
    const {
  data->base = new StateIterator< ArcMapFst<A, B, C> >(*this);
}


//
// Utility Mappers
//

// Mapper that returns its input.
template <class A>
struct IdentityArcMapper {
  typedef A FromArc;
  typedef A ToArc;

  A operator()(const A &arc) const { return arc; }

  MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }

  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }

  MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}

  uint64 Properties(uint64 props) const { return props; }
};


// Mapper that returns its input with final states redirected to
// a single super-final state.
template <class A>
struct SuperFinalMapper {
  typedef A FromArc;
  typedef A ToArc;

  A operator()(const A &arc) const { return arc; }

  MapFinalAction FinalAction() const { return MAP_REQUIRE_SUPERFINAL; }

  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }

  MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}

  uint64 Properties(uint64 props) const {
    return props & kAddSuperFinalProperties;
  }
};


// Mapper that leaves labels and nextstate unchanged and constructs a new weight
// from the underlying value of the arc weight.  Requires that there is a
// WeightConvert class specialization that converts the weights.
template <class A, class B>
class WeightConvertMapper {
 public:
  typedef A FromArc;
  typedef B ToArc;
  typedef typename FromArc::Weight FromWeight;
  typedef typename ToArc::Weight ToWeight;

  ToArc operator()(const FromArc &arc) const {
    return ToArc(arc.ilabel, arc.olabel,
                 convert_weight_(arc.weight), arc.nextstate);
  }

  MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }

  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }

  MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}

  uint64 Properties(uint64 props) const { return props; }

 private:
  WeightConvert<FromWeight, ToWeight> convert_weight_;
};

// Non-precision-changing weight conversions.
// Consider using more efficient Cast (fst.h) instead.
typedef WeightConvertMapper<StdArc, LogArc> StdToLogMapper;
typedef WeightConvertMapper<LogArc, StdArc> LogToStdMapper;

// Precision-changing weight conversions.
typedef WeightConvertMapper<StdArc, Log64Arc> StdToLog64Mapper;
typedef WeightConvertMapper<LogArc, Log64Arc> LogToLog64Mapper;
typedef WeightConvertMapper<Log64Arc, StdArc> Log64ToStdMapper;
typedef WeightConvertMapper<Log64Arc, LogArc> Log64ToLogMapper;

// Mapper from A to GallicArc<A>.
template <class A, StringType S = STRING_LEFT>
struct ToGallicMapper {
  typedef A FromArc;
  typedef GallicArc<A, S> ToArc;

  typedef StringWeight<typename A::Label, S> SW;
  typedef typename A::Weight AW;
  typedef typename GallicArc<A, S>::Weight GW;

  ToArc operator()(const A &arc) const {
    // 'Super-final' arc.
    if (arc.nextstate == kNoStateId && arc.weight != AW::Zero())
      return ToArc(0, 0, GW(SW::One(), arc.weight), kNoStateId);
    // 'Super-non-final' arc.
    else if (arc.nextstate == kNoStateId)
      return ToArc(0, 0, GW(SW::Zero(), arc.weight), kNoStateId);
    // Epsilon label.
    else if (arc.olabel == 0)
      return ToArc(arc.ilabel, arc.ilabel,
                   GW(SW::One(), arc.weight), arc.nextstate);
    // Regular label.
    else
      return ToArc(arc.ilabel, arc.ilabel,
                   GW(SW(arc.olabel), arc.weight), arc.nextstate);
  }

  MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }

  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }

  MapSymbolsAction OutputSymbolsAction() const { return MAP_CLEAR_SYMBOLS;}

  uint64 Properties(uint64 props) const {
    return ProjectProperties(props, true) & kWeightInvariantProperties;
  }
};


// Mapper from GallicArc<A> to A.
template <class A, StringType S = STRING_LEFT>
struct FromGallicMapper {
  typedef GallicArc<A, S> FromArc;
  typedef A ToArc;

  typedef typename A::Label Label;
  typedef StringWeight<Label, S> SW;
  typedef typename A::Weight AW;
  typedef typename GallicArc<A, S>::Weight GW;

  FromGallicMapper(Label superfinal_label = 0)
      : superfinal_label_(superfinal_label), error_(false) {}

  A operator()(const FromArc &arc) const {
    // 'Super-non-final' arc.
    if (arc.nextstate == kNoStateId && arc.weight == GW::Zero())
      return A(arc.ilabel, 0, AW::Zero(), kNoStateId);

    SW w1 = arc.weight.Value1();
    AW w2 = arc.weight.Value2();
    StringWeightIterator<Label, S> iter1(w1);

    Label l = w1.Size() == 1 ? iter1.Value() : 0;

    if (l == kStringInfinity || l == kStringBad ||
        arc.ilabel != arc.olabel || w1.Size() > 1) {
      FSTERROR() << "FromGallicMapper: unrepesentable weight";
      error_ = true;
    }

    if (arc.ilabel == 0 && l != 0 && arc.nextstate == kNoStateId)
      return A(superfinal_label_, l, w2, arc.nextstate);
    else
      return A(arc.ilabel, l, w2, arc.nextstate);
  }

  MapFinalAction FinalAction() const { return MAP_ALLOW_SUPERFINAL; }

  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }

  MapSymbolsAction OutputSymbolsAction() const { return MAP_CLEAR_SYMBOLS;}

  uint64 Properties(uint64 inprops) const {
    uint64 outprops = inprops & kOLabelInvariantProperties &
        kWeightInvariantProperties & kAddSuperFinalProperties;
    if (error_)
      outprops |= kError;
    return outprops;
  }

 private:
  Label superfinal_label_;
  mutable bool error_;
};


// Mapper from GallicArc<A> to A.
template <class A, StringType S = STRING_LEFT>
struct GallicToNewSymbolsMapper {
  typedef GallicArc<A, S> FromArc;
  typedef A ToArc;

  typedef typename A::StateId StateId;
  typedef typename A::Label Label;
  typedef StringWeight<Label, S> SW;
  typedef typename A::Weight AW;
  typedef typename GallicArc<A, S>::Weight GW;

  GallicToNewSymbolsMapper(MutableFst<ToArc> *fst)
      : fst_(fst), lmax_(0), osymbols_(fst->OutputSymbols()),
        isymbols_(0), error_(false) {
    fst_->DeleteStates();
    state_ = fst_->AddState();
    fst_->SetStart(state_);
    fst_->SetFinal(state_, AW::One());
    if (osymbols_) {
      string name = osymbols_->Name() + "_from_gallic";
      fst_->SetInputSymbols(new SymbolTable(name));
      isymbols_ = fst_->MutableInputSymbols();
      isymbols_->AddSymbol(osymbols_->Find((int64) 0), 0);
    } else {
      fst_->SetInputSymbols(0);
    }
  }

  A operator()(const FromArc &arc) {
    // 'Super-non-final' arc.
    if (arc.nextstate == kNoStateId && arc.weight == GW::Zero())
      return A(arc.ilabel, 0, AW::Zero(), kNoStateId);

    SW w1 = arc.weight.Value1();
    AW w2 = arc.weight.Value2();
    Label l;

    if (w1.Size() == 0) {
      l = 0;
    } else {
      typename Map::iterator miter = map_.find(w1);
      if (miter != map_.end()) {
        l = (*miter).second;
      } else {
        l = ++lmax_;
        map_.insert(pair<const SW, Label>(w1, l));
        StringWeightIterator<Label, S> iter1(w1);
        StateId n;
        string s;
        for(size_t i = 0, p = state_;
            i < w1.Size();
            ++i, iter1.Next(), p = n) {
          n = i == w1.Size() - 1 ? state_ : fst_->AddState();
          fst_->AddArc(p, ToArc(i ? 0 : l, iter1.Value(), AW::One(), n));
          if (isymbols_) {
            if (i) s = s + "_";
            s = s + osymbols_->Find(iter1.Value());
          }
        }
        if (isymbols_)
          isymbols_->AddSymbol(s, l);
      }
    }

    if (l == kStringInfinity || l == kStringBad || arc.ilabel != arc.olabel) {
      FSTERROR() << "GallicToNewSymbolMapper: unrepesentable weight";
      error_ = true;
    }

    return A(arc.ilabel, l, w2, arc.nextstate);
  }

  MapFinalAction FinalAction() const { return MAP_ALLOW_SUPERFINAL; }

  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }

  MapSymbolsAction OutputSymbolsAction() const { return MAP_CLEAR_SYMBOLS; }

  uint64 Properties(uint64 inprops) const {
    uint64 outprops = inprops & kOLabelInvariantProperties &
        kWeightInvariantProperties & kAddSuperFinalProperties;
    if (error_)
      outprops |= kError;
    return outprops;
  }

 private:
  class StringKey {
   public:
    size_t operator()(const SW &x) const {
      return x.Hash();
    }
  };

  typedef unordered_map<SW, Label, StringKey> Map;

  MutableFst<ToArc> *fst_;
  Map map_;
  Label lmax_;
  StateId state_;
  const SymbolTable *osymbols_;
  SymbolTable *isymbols_;
  mutable bool error_;

  DISALLOW_COPY_AND_ASSIGN(GallicToNewSymbolsMapper);
};


// Mapper to add a constant to all weights.
template <class A>
struct PlusMapper {
  typedef A FromArc;
  typedef A ToArc;
  typedef typename A::Weight Weight;

  explicit PlusMapper(Weight w) : weight_(w) {}

  A operator()(const A &arc) const {
    if (arc.weight == Weight::Zero())
      return arc;
    Weight w = Plus(arc.weight, weight_);
    return A(arc.ilabel, arc.olabel, w, arc.nextstate);
  }

  MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }

  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }

  MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}

  uint64 Properties(uint64 props) const {
    return props & kWeightInvariantProperties;
  }

 private:


  Weight weight_;
};


// Mapper to (right) multiply a constant to all weights.
template <class A>
struct TimesMapper {
  typedef A FromArc;
  typedef A ToArc;
  typedef typename A::Weight Weight;

  explicit TimesMapper(Weight w) : weight_(w) {}

  A operator()(const A &arc) const {
    if (arc.weight == Weight::Zero())
      return arc;
    Weight w = Times(arc.weight, weight_);
    return A(arc.ilabel, arc.olabel, w, arc.nextstate);
  }

  MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }

  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }

  MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}

  uint64 Properties(uint64 props) const {
    return props & kWeightInvariantProperties;
  }

 private:
  Weight weight_;
};


// Mapper to reciprocate all non-Zero() weights.
template <class A>
struct InvertWeightMapper {
  typedef A FromArc;
  typedef A ToArc;
  typedef typename A::Weight Weight;

  A operator()(const A &arc) const {
    if (arc.weight == Weight::Zero())
      return arc;
    Weight w = Divide(Weight::One(), arc.weight);
    return A(arc.ilabel, arc.olabel, w, arc.nextstate);
  }

  MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }

  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }

  MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}

  uint64 Properties(uint64 props) const {
    return props & kWeightInvariantProperties;
  }
};


// Mapper to map all non-Zero() weights to One().
template <class A, class B = A>
struct RmWeightMapper {
  typedef A FromArc;
  typedef B ToArc;
  typedef typename FromArc::Weight FromWeight;
  typedef typename ToArc::Weight ToWeight;

  B operator()(const A &arc) const {
    ToWeight w = arc.weight != FromWeight::Zero() ?
                   ToWeight::One() : ToWeight::Zero();
    return B(arc.ilabel, arc.olabel, w, arc.nextstate);
  }

  MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }

  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }

  MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}

  uint64 Properties(uint64 props) const {
    return (props & kWeightInvariantProperties) | kUnweighted;
  }
};


// Mapper to quantize all weights.
template <class A, class B = A>
struct QuantizeMapper {
  typedef A FromArc;
  typedef B ToArc;
  typedef typename FromArc::Weight FromWeight;
  typedef typename ToArc::Weight ToWeight;

  QuantizeMapper() : delta_(kDelta) {}

  explicit QuantizeMapper(float d) : delta_(d) {}

  B operator()(const A &arc) const {
    ToWeight w = arc.weight.Quantize(delta_);
    return B(arc.ilabel, arc.olabel, w, arc.nextstate);
  }

  MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }

  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }

  MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}

  uint64 Properties(uint64 props) const {
    return props & kWeightInvariantProperties;
  }

 private:
  float delta_;
};


// Mapper from A to B under the assumption:
//    B::Weight = A::Weight::ReverseWeight
//    B::Label == A::Label
//    B::StateId == A::StateId
// The weight is reversed, while the label and nextstate preserved
// in the mapping.
template <class A, class B>
struct ReverseWeightMapper {
  typedef A FromArc;
  typedef B ToArc;

  B operator()(const A &arc) const {
    return B(arc.ilabel, arc.olabel, arc.weight.Reverse(), arc.nextstate);
  }

  MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }

  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }

  MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}

  uint64 Properties(uint64 props) const { return props; }
};

}  // namespace fst

#endif  // FST_LIB_ARC_MAP_H__