// See www.openfst.org for extensive documentation on this weighted
  // finite-state transducer library.
  //
  // An FST implementation that allows non-destructive edit operations on an
  // existing FST.
  //
  // The EditFst class enables non-destructive edit operations on a wrapped
  // ExpandedFst. The implementation uses copy-on-write semantics at the node
  // level: if a user has an underlying fst on which he or she wants to perform a
  // relatively small number of edits (read: mutations), then this implementation
  // will copy the edited node to an internal MutableFst and perform any edits in
  // situ on that copied node. This class supports all the methods of MutableFst
  // except for DeleteStates(const std::vector<StateId> &); thus, new nodes may
  // also be
  // added, and one may add transitions from existing nodes of the wrapped fst to
  // new nodes.
  //
  // N.B.: The documentation for Fst::Copy(true) says that its behavior is
  // undefined if invoked on an fst that has already been accessed.  This class
  // requires that the Fst implementation it wraps provides consistent, reliable
  // behavior when its Copy(true) method is invoked, where consistent means
  // the graph structure, graph properties and state numbering and do not change.
  // VectorFst and CompactFst, for example, are both well-behaved in this regard.
  
  #ifndef FST_EDIT_FST_H_
  #define FST_EDIT_FST_H_
  
  #include <string>
  #include <unordered_map>
  #include <vector>
  
  #include <fst/log.h>
  
  #include <fst/cache.h>
  
  
  namespace fst {
  namespace internal {
  
  // The EditFstData class is a container for all mutable data for EditFstImpl;
  // also, this class provides most of the actual implementation of what EditFst
  // does (that is, most of EditFstImpl's methods delegate to methods in this, the
  // EditFstData class).  Instances of this class are reference-counted and can be
  // shared between otherwise independent EditFstImpl instances. This scheme
  // allows EditFstImpl to implement the thread-safe, copy-on-write semantics
  // required by Fst::Copy(true).
  //
  // template parameters:
  //   A the type of arc to use
  //   WrappedFstT the type of fst wrapped by the EditFst instance that
  //     this EditFstData instance is backing
  //   MutableFstT the type of mutable fst to use internally for edited states;
  //     crucially, MutableFstT::Copy(false) *must* yield an fst that is
  //     thread-safe for reading (VectorFst, for example, has this property)
  template <typename Arc, typename WrappedFstT = ExpandedFst<Arc>,
            typename MutableFstT = VectorFst<Arc>>
  class EditFstData {
   public:
    using StateId = typename Arc::StateId;
    using Weight = typename Arc::Weight;
  
    EditFstData() : num_new_states_(0) {}
  
    EditFstData(const EditFstData &other)
        : edits_(other.edits_),
          external_to_internal_ids_(other.external_to_internal_ids_),
          edited_final_weights_(other.edited_final_weights_),
          num_new_states_(other.num_new_states_) {}
  
    ~EditFstData() {}
  
    static EditFstData<Arc, WrappedFstT, MutableFstT> *Read(
        std::istream &strm, const FstReadOptions &opts);
  
    bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
      // Serialize all private data members of this class.
      FstWriteOptions edits_opts(opts);
      edits_opts.write_header = true;  // Force writing contained header.
      edits_.Write(strm, edits_opts);
      WriteType(strm, external_to_internal_ids_);
      WriteType(strm, edited_final_weights_);
      WriteType(strm, num_new_states_);
      if (!strm) {
        LOG(ERROR) << "EditFstData::Write: Write failed: " << opts.source;
        return false;
      }
      return true;
    }
  
    StateId NumNewStates() const { return num_new_states_; }
  
    // accessor methods for the fst holding edited states
    StateId EditedStart() const { return edits_.Start(); }
  
    Weight Final(StateId s, const WrappedFstT *wrapped) const {
      auto final_weight_it = GetFinalWeightIterator(s);
      if (final_weight_it == NotInFinalWeightMap()) {
        auto it = GetEditedIdMapIterator(s);
        return it == NotInEditedMap() ? wrapped->Final(s)
                                      : edits_.Final(it->second);
      } else {
        return final_weight_it->second;
      }
    }
  
    size_t NumArcs(StateId s, const WrappedFstT *wrapped) const {
      auto it = GetEditedIdMapIterator(s);
      return it == NotInEditedMap() ? wrapped->NumArcs(s)
                                    : edits_.NumArcs(it->second);
    }
  
    size_t NumInputEpsilons(StateId s, const WrappedFstT *wrapped) const {
      auto it = GetEditedIdMapIterator(s);
      return it == NotInEditedMap() ? wrapped->NumInputEpsilons(s)
                                    : edits_.NumInputEpsilons(it->second);
    }
  
    size_t NumOutputEpsilons(StateId s, const WrappedFstT *wrapped) const {
      auto it = GetEditedIdMapIterator(s);
      return it == NotInEditedMap() ? wrapped->NumOutputEpsilons(s)
                                    : edits_.NumOutputEpsilons(it->second);
    }
  
    void SetEditedProperties(uint64 props, uint64 mask) {
      edits_.SetProperties(props, mask);
    }
  
    // Non-const MutableFst operations.
  
    // Sets the start state for this FST.
    void SetStart(StateId s) { edits_.SetStart(s); }
  
    // Sets the final state for this FST.
    Weight SetFinal(StateId s, Weight w, const WrappedFstT *wrapped) {
      Weight old_weight = Final(s, wrapped);
      auto it = GetEditedIdMapIterator(s);
      // If we haven't already edited state s, don't add it to edited_ (which can
      // be expensive if s has many transitions); just use the
      // edited_final_weights_ map.
      if (it == NotInEditedMap()) {
        edited_final_weights_[s] = w;
      } else {
        edits_.SetFinal(GetEditableInternalId(s, wrapped), w);
      }
      return old_weight;
    }
  
    // Adds a new state to this FST, initially with no arcs.
    StateId AddState(StateId curr_num_states) {
      StateId internal_state_id = edits_.AddState();
      StateId external_state_id = curr_num_states;
      external_to_internal_ids_[external_state_id] = internal_state_id;
      num_new_states_++;
      return external_state_id;
    }
  
    // Adds the specified arc to the specified state of this FST.
    const Arc *AddArc(StateId s, const Arc &arc, const WrappedFstT *wrapped) {
      const auto internal_id = GetEditableInternalId(s, wrapped);
      const auto num_arcs = edits_.NumArcs(internal_id);
      ArcIterator<MutableFstT> arc_it(edits_, internal_id);
      const Arc *prev_arc = nullptr;
      if (num_arcs > 0) {
        // grab the final arc associated with this state in edits_
        arc_it.Seek(num_arcs - 1);
        prev_arc = &(arc_it.Value());
      }
      edits_.AddArc(internal_id, arc);
      return prev_arc;
    }
  
    void DeleteStates() {
      edits_.DeleteStates();
      num_new_states_ = 0;
      external_to_internal_ids_.clear();
      edited_final_weights_.clear();
    }
  
    // Removes all but the first n outgoing arcs of the specified state.
    void DeleteArcs(StateId s, size_t n, const WrappedFstT *wrapped) {
      edits_.DeleteArcs(GetEditableInternalId(s, wrapped), n);
    }
  
    // Removes all outgoing arcs from the specified state.
    void DeleteArcs(StateId s, const WrappedFstT *wrapped) {
      edits_.DeleteArcs(GetEditableInternalId(s, wrapped));
    }
  
    // End methods for non-const MutableFst operations.
  
    // Provides information for the generic arc iterator.
    void InitArcIterator(StateId s, ArcIteratorData<Arc> *data,
                         const WrappedFstT *wrapped) const {
      auto id_map_it = GetEditedIdMapIterator(s);
      if (id_map_it == NotInEditedMap()) {
        VLOG(3) << "EditFstData::InitArcIterator: iterating on state " << s
                << " of original fst";
        wrapped->InitArcIterator(s, data);
      } else {
        VLOG(2) << "EditFstData::InitArcIterator: iterating on edited state " << s
                << " (internal state id: " << id_map_it->second << ")";
        edits_.InitArcIterator(id_map_it->second, data);
      }
    }
  
    // Provides information for the generic mutable arc iterator.
    void InitMutableArcIterator(StateId s, MutableArcIteratorData<Arc> *data,
                                const WrappedFstT *wrapped) {
      data->base = new MutableArcIterator<MutableFstT>(
          &edits_, GetEditableInternalId(s, wrapped));
    }
  
    // Prints out the map from external to internal state id's (for debugging
    // purposes).
    void PrintMap() {
      for (auto map_it = external_to_internal_ids_.begin();
           map_it != NotInEditedMap(); ++map_it) {
        LOG(INFO) << "(external,internal)=(" << map_it->first << ","
                  << map_it->second << ")";
      }
    }
  
   private:
    // Returns the iterator of the map from external to internal state id's
    // of edits_ for the specified external state id.
    typename std::unordered_map<StateId, StateId>::const_iterator
        GetEditedIdMapIterator(StateId s) const {
      return external_to_internal_ids_.find(s);
    }
  
    typename std::unordered_map<StateId, StateId>::const_iterator
        NotInEditedMap() const {
      return external_to_internal_ids_.end();
    }
  
    typename std::unordered_map<StateId, Weight>::const_iterator
        GetFinalWeightIterator(StateId s) const {
      return edited_final_weights_.find(s);
    }
  
    typename std::unordered_map<StateId, Weight>::const_iterator
        NotInFinalWeightMap() const {
      return edited_final_weights_.end();
    }
  
    // Returns the internal state ID of the specified external ID if the state has
    // already been made editable, or else copies the state from wrapped_ to
    // edits_ and returns the state id of the newly editable state in edits_.
    StateId GetEditableInternalId(StateId s, const WrappedFstT *wrapped) {
      auto id_map_it = GetEditedIdMapIterator(s);
      if (id_map_it == NotInEditedMap()) {
        StateId new_internal_id = edits_.AddState();
        VLOG(2) << "EditFstData::GetEditableInternalId: editing state " << s
                << " of original fst; new internal state id:" << new_internal_id;
        external_to_internal_ids_[s] = new_internal_id;
        for (ArcIterator<Fst<Arc>> arc_iterator(*wrapped, s);
             !arc_iterator.Done(); arc_iterator.Next()) {
          edits_.AddArc(new_internal_id, arc_iterator.Value());
        }
        // Copies the final weight.
        auto final_weight_it = GetFinalWeightIterator(s);
        if (final_weight_it == NotInFinalWeightMap()) {
          edits_.SetFinal(new_internal_id, wrapped->Final(s));
        } else {
          edits_.SetFinal(new_internal_id, final_weight_it->second);
          edited_final_weights_.erase(s);
        }
        return new_internal_id;
      } else {
        return id_map_it->second;
      }
    }
  
    // A mutable FST (by default, a VectorFst) to contain new states, and/or
    // copies of states from a wrapped ExpandedFst that have been modified in
    // some way.
    MutableFstT edits_;
    // A mapping from external state IDs to the internal IDs of states that
    // appear in edits_.
    std::unordered_map<StateId, StateId> external_to_internal_ids_;
    // A mapping from external state IDs to final state weights assigned to
    // those states.  The states in this map are *only* those whose final weight
    // has been modified; if any other part of the state has been modified,
    // the entire state is copied to edits_, and all modifications reside there.
    std::unordered_map<StateId, Weight> edited_final_weights_;
    // The number of new states added to this mutable fst impl, which is <= the
    // number of states in edits_ (since edits_ contains both edited *and* new
    // states).
    StateId num_new_states_;
  };
  
  // EditFstData method implementations: just the Read method.
  template <typename A, typename WrappedFstT, typename MutableFstT>
  EditFstData<A, WrappedFstT, MutableFstT> *
  EditFstData<A, WrappedFstT, MutableFstT>::Read(std::istream &strm,
                                                 const FstReadOptions &opts) {
    auto *data = new EditFstData<A, WrappedFstT, MutableFstT>();
    // next read in MutabelFstT machine that stores edits
    FstReadOptions edits_opts(opts);
    // Contained header was written out, so read it in.
    edits_opts.header = nullptr;
  
    // Because our internal representation of edited states is a solid object
    // of type MutableFstT (defaults to VectorFst<A>) and not a pointer,
    // and because the static Read method allocates a new object on the heap,
    // we need to call Read, check if there was a failure, use
    // MutableFstT::operator= to assign the object (not the pointer) to the
    // edits_ data member (which will increase the ref count by 1 on the impl)
    // and, finally, delete the heap-allocated object.
    std::unique_ptr<MutableFstT> edits(MutableFstT::Read(strm, edits_opts));
    if (!edits) return nullptr;
    data->edits_ = *edits;
    edits.reset();
    // Finally, reads in rest of private data members.
    ReadType(strm, &data->external_to_internal_ids_);
    ReadType(strm, &data->edited_final_weights_);
    ReadType(strm, &data->num_new_states_);
    if (!strm) {
      LOG(ERROR) << "EditFst::Read: read failed: " << opts.source;
      return nullptr;
    }
    return data;
  }
  
  // This class enables non-destructive edit operations on a wrapped ExpandedFst.
  // The implementation uses copy-on-write semantics at the node level: if a user
  // has an underlying fst on which he or she wants to perform a relatively small
  // number of edits (read: mutations), then this implementation will copy the
  // edited node to an internal MutableFst and perform any edits in situ on that
  // copied node. This class supports all the methods of MutableFst except for
  // DeleteStates(const std::vector<StateId> &); thus, new nodes may also be
  // added, and
  // one may add transitions from existing nodes of the wrapped fst to new nodes.
  //
  // template parameters:
  //   A the type of arc to use
  //   WrappedFstT the type of fst wrapped by the EditFst instance that
  //     this EditFstImpl instance is backing
  //   MutableFstT the type of mutable fst to use internally for edited states;
  //     crucially, MutableFstT::Copy(false) *must* yield an fst that is
  //     thread-safe for reading (VectorFst, for example, has this property)
  template <typename A, typename WrappedFstT = ExpandedFst<A>,
            typename MutableFstT = VectorFst<A>>
  class EditFstImpl : public FstImpl<A> {
   public:
    using Arc = A;
    using StateId = typename Arc::StateId;
    using Weight = typename Arc::Weight;
  
    using FstImpl<Arc>::SetProperties;
    using FstImpl<Arc>::SetInputSymbols;
    using FstImpl<Arc>::SetOutputSymbols;
    using FstImpl<Arc>::WriteHeader;
  
    // Constructs an editable FST implementation with no states. Effectively, this
    // initially-empty fst will in every way mimic the behavior of a
    // VectorFst---more precisely, a VectorFstImpl instance---but with slightly
    // slower performance (by a constant factor), due to the fact that
    // this class maintains a mapping between external state id's and
    // their internal equivalents.
    EditFstImpl() : wrapped_(new MutableFstT()) {
      FstImpl<Arc>::SetType("edit");
      InheritPropertiesFromWrapped();
      data_ = std::make_shared<EditFstData<Arc, WrappedFstT, MutableFstT>>();
    }
  
    // Wraps the specified ExpandedFst. This constructor requires that the
    // specified Fst is an ExpandedFst instance. This requirement is only enforced
    // at runtime. (See below for the reason.)
    //
    // This library uses the pointer-to-implementation or "PIMPL" design pattern.
    // In particular, to make it convenient to bind an implementation class to its
    // interface, there are a pair of template "binder" classes, one for immutable
    // and one for mutable fst's (ImplToFst and ImplToMutableFst, respectively).
    // As it happens, the API for the ImplToMutableFst<I,F> class requires that
    // the implementation class--the template parameter "I"--have a constructor
    // taking a const Fst<A> reference.  Accordingly, the constructor here must
    // perform a static_cast to the WrappedFstT type required by EditFst and
    // therefore EditFstImpl.
    explicit EditFstImpl(const Fst<Arc> &wrapped)
        : wrapped_(static_cast<WrappedFstT *>(wrapped.Copy())) {
      FstImpl<Arc>::SetType("edit");
      data_ = std::make_shared<EditFstData<Arc, WrappedFstT, MutableFstT>>();
      // have edits_ inherit all properties from wrapped_
      data_->SetEditedProperties(wrapped_->Properties(kFstProperties, false),
                                 kFstProperties);
      InheritPropertiesFromWrapped();
    }
  
    // A copy constructor for this implementation class, used to implement
    // the Copy() method of the Fst interface.
    EditFstImpl(const EditFstImpl &impl)
        : FstImpl<Arc>(),
          wrapped_(static_cast<WrappedFstT *>(impl.wrapped_->Copy(true))),
          data_(impl.data_) {
      SetProperties(impl.Properties());
    }
  
    // const Fst/ExpandedFst operations, declared in the Fst and ExpandedFst
    // interfaces
    StateId Start() const {
      const auto edited_start = data_->EditedStart();
      return edited_start == kNoStateId ? wrapped_->Start() : edited_start;
    }
  
    Weight Final(StateId s) const { return data_->Final(s, wrapped_.get()); }
  
    size_t NumArcs(StateId s) const { return data_->NumArcs(s, wrapped_.get()); }
  
    size_t NumInputEpsilons(StateId s) const {
      return data_->NumInputEpsilons(s, wrapped_.get());
    }
  
    size_t NumOutputEpsilons(StateId s) const {
      return data_->NumOutputEpsilons(s, wrapped_.get());
    }
  
    StateId NumStates() const {
      return wrapped_->NumStates() + data_->NumNewStates();
    }
  
    static EditFstImpl<Arc, WrappedFstT, MutableFstT> *Read(
        std::istream &strm, const FstReadOptions &opts);
  
    bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
      FstHeader hdr;
      hdr.SetStart(Start());
      hdr.SetNumStates(NumStates());
      FstWriteOptions header_opts(opts);
      // Allows the contained FST to hold any symbols.
      header_opts.write_isymbols = false;
      header_opts.write_osymbols = false;
      WriteHeader(strm, header_opts, kFileVersion, &hdr);
      // First, serializes the wrapped FST to stream.
      FstWriteOptions wrapped_opts(opts);
      // Forcse writing the contained header.
      wrapped_opts.write_header = true;
      wrapped_->Write(strm, wrapped_opts);
      data_->Write(strm, opts);
      strm.flush();
      if (!strm) {
        LOG(ERROR) << "EditFst::Write: Write failed: " << opts.source;
        return false;
      }
      return true;
    }
  
    // Sets the start state for this FST.
    void SetStart(StateId s) {
      MutateCheck();
      data_->SetStart(s);
      SetProperties(SetStartProperties(FstImpl<Arc>::Properties()));
    }
  
    // Sets the final state for this fst.
    void SetFinal(StateId s, Weight weight) {
      MutateCheck();
      Weight old_weight = data_->SetFinal(s, weight, wrapped_.get());
      SetProperties(
          SetFinalProperties(FstImpl<Arc>::Properties(), old_weight, weight));
    }
  
    // Adds a new state to this fst, initially with no arcs.
    StateId AddState() {
      MutateCheck();
      SetProperties(AddStateProperties(FstImpl<Arc>::Properties()));
      return data_->AddState(NumStates());
    }
  
    // Adds the specified arc to the specified state of this fst.
    void AddArc(StateId s, const Arc &arc) {
      MutateCheck();
      const auto *prev_arc = data_->AddArc(s, arc, wrapped_.get());
      SetProperties(
          AddArcProperties(FstImpl<Arc>::Properties(), s, arc, prev_arc));
    }
  
    void DeleteStates(const std::vector<StateId> &dstates) {
      FSTERROR() << ": EditFstImpl::DeleteStates(const std::vector<StateId>&): "
                 << " not implemented";
      SetProperties(kError, kError);
    }
  
    // Deletes all states in this fst.
    void DeleteStates();
  
    // Removes all but the first n outgoing arcs of the specified state.
    void DeleteArcs(StateId s, size_t n) {
      MutateCheck();
      data_->DeleteArcs(s, n, wrapped_.get());
      SetProperties(DeleteArcsProperties(FstImpl<Arc>::Properties()));
    }
  
    // Removes all outgoing arcs from the specified state.
    void DeleteArcs(StateId s) {
      MutateCheck();
      data_->DeleteArcs(s, wrapped_.get());
      SetProperties(DeleteArcsProperties(FstImpl<Arc>::Properties()));
    }
  
    void ReserveStates(StateId s) {}
  
    void ReserveArcs(StateId s, size_t n) {}
  
    // Ends non-const MutableFst operations.
  
    // Provides information for the generic state iterator.
    void InitStateIterator(StateIteratorData<Arc> *data) const {
      data->base = nullptr;
      data->nstates = NumStates();
    }
  
    // Provides information for the generic arc iterator.
    void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const {
      data_->InitArcIterator(s, data, wrapped_.get());
    }
  
    // Provides information for the generic mutable arc iterator.
    void InitMutableArcIterator(StateId s, MutableArcIteratorData<Arc> *data) {
      MutateCheck();
      data_->InitMutableArcIterator(s, data, wrapped_.get());
    }
  
   private:
    // Properties always true of this FST class.
    static constexpr uint64 kStaticProperties = kExpanded | kMutable;
    // Current file format version.
    static constexpr int kFileVersion = 2;
    // Minimum file format version supported
    static constexpr int kMinFileVersion = 2;
  
    // Causes this FST to inherit all the properties from its wrapped FST, except
    // for the two properties that always apply to EditFst instances: kExpanded
    // and kMutable.
    void InheritPropertiesFromWrapped() {
      SetProperties(wrapped_->Properties(kCopyProperties, false) |
                    kStaticProperties);
      SetInputSymbols(wrapped_->InputSymbols());
      SetOutputSymbols(wrapped_->OutputSymbols());
    }
  
    // This method ensures that any operations that alter the mutable data
    // portion of this EditFstImpl cause the data_ member to be copied when its
    // reference count is greater than 1.  Note that this method is distinct from
    // MutableFst::Mutate, which gets invoked whenever one of the basic mutation
    // methods defined in MutableFst is invoked, such as SetInputSymbols.
    // The MutateCheck here in EditFstImpl is invoked whenever one of the
    // mutating methods specifically related to the types of edits provided
    // by EditFst is performed, such as changing an arc of an existing state
    // of the wrapped fst via a MutableArcIterator, or adding a new state via
    // AddState().
    void MutateCheck() {
      if (!data_.unique()) {
        data_ =
            std::make_shared<EditFstData<Arc, WrappedFstT, MutableFstT>>(*data_);
      }
    }
  
    // The FST that this FST wraps. The purpose of this class is to enable
    // non-destructive edits on this wrapped FST.
    std::unique_ptr<const WrappedFstT> wrapped_;
    // The mutable data for this EditFst instance, with delegates for all the
    // methods that can mutate data.
    std::shared_ptr<EditFstData<Arc, WrappedFstT, MutableFstT>> data_;
  };
  
  template <typename Arc, typename WrappedFstT, typename MutableFstT>
  constexpr uint64 EditFstImpl<Arc, WrappedFstT, MutableFstT>::kStaticProperties;
  
  template <typename Arc, typename WrappedFstT, typename MutableFstT>
  constexpr int EditFstImpl<Arc, WrappedFstT, MutableFstT>::kFileVersion;
  
  template <typename Arc, typename WrappedFstT, typename MutableFstT>
  constexpr int EditFstImpl<Arc, WrappedFstT, MutableFstT>::kMinFileVersion;
  
  template <typename Arc, typename WrappedFstT, typename MutableFstT>
  inline void EditFstImpl<Arc, WrappedFstT, MutableFstT>::DeleteStates() {
    data_->DeleteStates();
    // we are deleting all states, so just forget about pointer to wrapped_
    // and do what default constructor does: set wrapped_ to a new VectorFst
    wrapped_.reset(new MutableFstT());
    const auto new_props =
        DeleteAllStatesProperties(FstImpl<Arc>::Properties(), kStaticProperties);
    FstImpl<Arc>::SetProperties(new_props);
  }
  
  template <typename Arc, typename WrappedFstT, typename MutableFstT>
  EditFstImpl<Arc, WrappedFstT, MutableFstT> *
  EditFstImpl<Arc, WrappedFstT, MutableFstT>::Read(std::istream &strm,
                                                   const FstReadOptions &opts) {
    auto *impl = new EditFstImpl();
    FstHeader hdr;
    if (!impl->ReadHeader(strm, opts, kMinFileVersion, &hdr)) return nullptr;
    impl->SetStart(hdr.Start());
    // Reads in wrapped FST.
    FstReadOptions wrapped_opts(opts);
    // Contained header was written out, so reads it in too.
    wrapped_opts.header = nullptr;
    std::unique_ptr<Fst<Arc>> wrapped_fst(Fst<Arc>::Read(strm, wrapped_opts));
    if (!wrapped_fst) return nullptr;
    impl->wrapped_.reset(static_cast<WrappedFstT *>(wrapped_fst.release()));
    impl->data_ = std::shared_ptr<EditFstData<Arc, WrappedFstT, MutableFstT>>(
        EditFstData<Arc, WrappedFstT, MutableFstT>::Read(strm, opts));
    if (!impl->data_) return nullptr;
    return impl;
  }
  
  }  // namespace internal
  
  // Concrete, editable FST.  This class attaches interface to implementation.
  template <typename A, typename WrappedFstT = ExpandedFst<A>,
            typename MutableFstT = VectorFst<A>>
  class EditFst : public ImplToMutableFst<
                      internal::EditFstImpl<A, WrappedFstT, MutableFstT>> {
   public:
    using Arc = A;
    using StateId = typename Arc::StateId;
  
    using Impl = internal::EditFstImpl<Arc, WrappedFstT, MutableFstT>;
  
    friend class MutableArcIterator<EditFst<Arc, WrappedFstT, MutableFstT>>;
  
    EditFst() : ImplToMutableFst<Impl>(std::make_shared<Impl>()) {}
  
    explicit EditFst(const Fst<Arc> &fst)
        : ImplToMutableFst<Impl>(std::make_shared<Impl>(fst)) {}
  
    explicit EditFst(const WrappedFstT &fst)
        : ImplToMutableFst<Impl>(std::make_shared<Impl>(fst)) {}
  
    // See Fst<>::Copy() for doc.
    EditFst(const EditFst<Arc, WrappedFstT, MutableFstT> &fst, bool safe = false)
        : ImplToMutableFst<Impl>(fst, safe) {}
  
    ~EditFst() override {}
  
    // Gets a copy of this EditFst. See Fst<>::Copy() for further doc.
    EditFst<Arc, WrappedFstT, MutableFstT> *Copy(
        bool safe = false) const override {
      return new EditFst<Arc, WrappedFstT, MutableFstT>(*this, safe);
    }
  
    EditFst<Arc, WrappedFstT, MutableFstT> &operator=(
        const EditFst<Arc, WrappedFstT, MutableFstT> &fst) {
      SetImpl(fst.GetSharedImpl());
      return *this;
    }
  
    EditFst<Arc, WrappedFstT, MutableFstT> &operator=(
        const Fst<Arc> &fst) override {
      SetImpl(std::make_shared<Impl>(fst));
      return *this;
    }
  
    // Reads an EditFst from an input stream, returning nullptr on error.
    static EditFst<Arc, WrappedFstT, MutableFstT> *Read(
        std::istream &strm, const FstReadOptions &opts) {
      auto *impl = Impl::Read(strm, opts);
      return impl ? new EditFst<Arc>(std::shared_ptr<Impl>(impl)) : nullptr;
    }
  
    // Reads an EditFst from a file, returning nullptr on error. If the filename
    // argument is an empty string, it reads from standard input.
    static EditFst<Arc, WrappedFstT, MutableFstT> *Read(const string &filename) {
      auto *impl = ImplToExpandedFst<Impl, MutableFst<Arc>>::Read(filename);
      return impl ? new EditFst<Arc, WrappedFstT, MutableFstT>(
                        std::shared_ptr<Impl>(impl))
                  : nullptr;
    }
  
    bool Write(std::ostream &strm, const FstWriteOptions &opts) const override {
      return GetImpl()->Write(strm, opts);
    }
  
    bool Write(const string &filename) const override {
      return Fst<Arc>::WriteFile(filename);
    }
  
    void InitStateIterator(StateIteratorData<Arc> *data) const override {
      GetImpl()->InitStateIterator(data);
    }
  
    void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const override {
      GetImpl()->InitArcIterator(s, data);
    }
  
    void InitMutableArcIterator(StateId s,
                                MutableArcIteratorData<A> *data) override {
      GetMutableImpl()->InitMutableArcIterator(s, data);
    }
  
   private:
    explicit EditFst(std::shared_ptr<Impl> impl) : ImplToMutableFst<Impl>(impl) {}
  
    using ImplToFst<Impl, MutableFst<Arc>>::GetImpl;
    using ImplToFst<Impl, MutableFst<Arc>>::GetMutableImpl;
    using ImplToFst<Impl, MutableFst<Arc>>::SetImpl;
  };
  
  }  // namespace fst
  
  #endif  // FST_EDIT_FST_H_