// See www.openfst.org for extensive documentation on this weighted
// finite-state transducer library.
//
// FST Class for memory-efficient representation of common types of
// FSTs: linear automata, acceptors, unweighted FSTs, ...

#ifndef FST_COMPACT_FST_H_
#define FST_COMPACT_FST_H_

#include <climits>
#include <iterator>
#include <memory>
#include <tuple>
#include <utility>
#include <vector>

#include <fst/log.h>

#include <fst/cache.h>
#include <fst/expanded-fst.h>
#include <fst/fst-decl.h>  // For optional argument declarations
#include <fst/mapped-file.h>
#include <fst/matcher.h>
#include <fst/test-properties.h>
#include <fst/util.h>


namespace fst {

struct CompactFstOptions : public CacheOptions {
  // The default caching behaviour is to do no caching. Most compactors are
  // cheap and therefore we save memory by not doing caching.
  CompactFstOptions() : CacheOptions(true, 0) {}

  explicit CompactFstOptions(const CacheOptions &opts) : CacheOptions(opts) {}
};

// New upcoming (Fst) Compactor interface - currently used internally
// by CompactFstImpl.
//
// class Compactor {
//  public:
//   // Constructor from the Fst to be compacted.
//   Compactor(const Fst<Arc> &fst, ...);
//   // Copy constructor
//   Compactor(const Compactor &compactor, bool safe = false)
//   // Default constructor (optional, see comment below).
//   Compactor();
//
//   // Returns the start state, number of states, and total number of arcs
//   // of the compacted Fst
//   StateId Start() const;
//   StateId NumStates() const;
//   size_t NumArcs() const;
//
//   // Accessor class for state attributes.
//   class State {
//    public:
//     State();  // Required, corresponds to kNoStateId.
//     State(const Compactor *c, StateId);  // Accessor for StateId 's'.
//     StateId GetStateId() const;
//     Weight Final() const;
//     size_t NumArcs() const;
//     Arc GetArc(size_t i) const;
//   };
//
//   // Modifies 'state' accessor to provide access to state id 's'.
//   void SetState(StateId s, State *state);
//   // Tests whether 'fst' can be compacted by this compactor.
//   bool IsCompatible(const Fst<A> &fst) const;
//   // Return the properties that are always true for an fst
//   // compacted using this compactor
//   uint64 Properties() const;
//   // Return a string identifying the type of compactor.
//   static const string &Type();
//   // Return true if an error has occured.
//   bool Error() const;
//   // Writes a compactor to a file.
//   bool Write(std::ostream &strm, const FstWriteOptions &opts) const;
//   // Reads a compactor from a file.
//   static Compactor*Read(std::istream &strm, const FstReadOptions &opts,
//                         const FstHeader &hdr);
// };
//

// Old (Arc) Compactor Interface:
//
// The ArcCompactor class determines how arcs and final weights are compacted
// and expanded.
//
// Final weights are treated as transitions to the superfinal state, i.e.,
// ilabel = olabel = kNoLabel and nextstate = kNoStateId.
//
// There are two types of compactors:
//
// * Fixed out-degree compactors: 'compactor.Size()' returns a positive integer
//   's'. An FST can be compacted by this compactor only if each state has
//   exactly 's' outgoing transitions (counting a non-Zero() final weight as a
//   transition). A typical example is a compactor for string FSTs, i.e.,
//   's == 1'.
//
// * Variable out-degree compactors: 'compactor.Size() == -1'. There are no
//   out-degree restrictions for these compactors.
//
// Interface:
//
// class ArcCompactor {
//  public:
//   // Element is the type of the compacted transitions.
//   using Element = ...
//
//   // Returns the compacted representation of a transition 'arc'
//   // at a state 's'.
//   Element Compact(StateId s, const Arc &arc);
//
//   // Returns the transition at state 's' represented by the compacted
//   // transition 'e'.
//   Arc Expand(StateId s, const Element &e) const;
//
//   // Returns -1 for variable out-degree compactors, and the mandatory
//   // out-degree otherwise.
//   ssize_t Size() const;
//
//   // Tests whether an FST can be compacted by this compactor.
//   bool Compatible(const Fst<A> &fst) const;
//
//   // Returns the properties that are always true for an FST compacted using
//   // this compactor
//   uint64 Properties() const;
//
//   // Returns a string identifying the type of compactor.
//   static const string &Type();
//
//   // Writes a compactor to a file.
//   bool Write(std::ostream &strm) const;
//
//   // Reads a compactor from a file.
//   static ArcCompactor *Read(std::istream &strm);
//
//   // Default constructor (optional, see comment below).
//   ArcCompactor();
// };
//
// The default constructor is only required for FST_REGISTER to work (i.e.,
// enabling Convert() and the command-line utilities to work with this new
// compactor). However, a default constructor always needs to be specified for
// this code to compile, but one can have it simply raise an error when called,
// like so:
//
// Compactor::Compactor() {
//   FSTERROR() << "Compactor: No default constructor";
// }

// Default implementation data for CompactFst, which can shared between
// otherwise independent copies.
//
// The implementation contains two arrays: 'states_' and 'compacts_'.
//
// For fixed out-degree compactors, the 'states_' array is unallocated. The
// 'compacts_' contains the compacted transitions. Its size is 'ncompacts_'.
// The outgoing transitions at a given state are stored consecutively. For a
// given state 's', its 'compactor.Size()' outgoing transitions (including
// superfinal transition when 's' is final), are stored in position
// ['s*compactor.Size()', '(s+1)*compactor.Size()').
//
// For variable out-degree compactors, the states_ array has size
// 'nstates_ + 1' and contains pointers to positions into 'compacts_'. For a
// given state 's', the compacted transitions of 's' are stored in positions
// ['states_[s]', 'states_[s + 1]') in 'compacts_'. By convention,
// 'states_[nstates_] == ncompacts_'.
//
// In both cases, the superfinal transitions (when 's' is final, i.e.,
// 'Final(s) != Weight::Zero()') are stored first.
//
// The unsigned type U is used to represent indices into the compacts_ array.
template <class Element, class Unsigned>
class DefaultCompactStore {
 public:
  DefaultCompactStore()
      : states_(nullptr),
        compacts_(nullptr),
        nstates_(0),
        ncompacts_(0),
        narcs_(0),
        start_(kNoStateId),
        error_(false) {}

  template <class Arc, class Compactor>
  DefaultCompactStore(const Fst<Arc> &fst, const Compactor &compactor);

  template <class Iterator, class Compactor>
  DefaultCompactStore(const Iterator &begin, const Iterator &end,
                      const Compactor &compactor);

  ~DefaultCompactStore() {
    if (!states_region_) delete[] states_;
    if (!compacts_region_) delete[] compacts_;
  }

  template <class Compactor>
  static DefaultCompactStore<Element, Unsigned> *Read(
      std::istream &strm, const FstReadOptions &opts, const FstHeader &hdr,
      const Compactor &compactor);

  bool Write(std::ostream &strm, const FstWriteOptions &opts) const;

  Unsigned States(ssize_t i) const { return states_[i]; }

  const Element &Compacts(size_t i) const { return compacts_[i]; }

  size_t NumStates() const { return nstates_; }

  size_t NumCompacts() const { return ncompacts_; }

  size_t NumArcs() const { return narcs_; }

  ssize_t Start() const { return start_; }

  bool Error() const { return error_; }

  // Returns a string identifying the type of data storage container.
  static const string &Type();

 private:
  std::unique_ptr<MappedFile> states_region_;
  std::unique_ptr<MappedFile> compacts_region_;
  Unsigned *states_;
  Element *compacts_;
  size_t nstates_;
  size_t ncompacts_;
  size_t narcs_;
  ssize_t start_;
  bool error_;
};

template <class Element, class Unsigned>
template <class Arc, class Compactor>
DefaultCompactStore<Element, Unsigned>::DefaultCompactStore(
    const Fst<Arc> &fst, const Compactor &compactor)
    : states_(nullptr),
      compacts_(nullptr),
      nstates_(0),
      ncompacts_(0),
      narcs_(0),
      start_(kNoStateId),
      error_(false) {
  using StateId = typename Arc::StateId;
  using Weight = typename Arc::Weight;
  start_ = fst.Start();
  // Counts # of states and arcs.
  StateId nfinals = 0;
  for (StateIterator<Fst<Arc>> siter(fst); !siter.Done(); siter.Next()) {
    ++nstates_;
    const auto s = siter.Value();
    for (ArcIterator<Fst<Arc>> aiter(fst, s); !aiter.Done(); aiter.Next()) {
      ++narcs_;
    }
    if (fst.Final(s) != Weight::Zero()) ++nfinals;
  }
  if (compactor.Size() == -1) {
    states_ = new Unsigned[nstates_ + 1];
    ncompacts_ = narcs_ + nfinals;
    compacts_ = new Element[ncompacts_];
    states_[nstates_] = ncompacts_;
  } else {
    states_ = nullptr;
    ncompacts_ = nstates_ * compactor.Size();
    if ((narcs_ + nfinals) != ncompacts_) {
      FSTERROR() << "DefaultCompactStore: Compactor incompatible with FST";
      error_ = true;
      return;
    }
    compacts_ = new Element[ncompacts_];
  }
  size_t pos = 0;
  size_t fpos = 0;
  for (size_t s = 0; s < nstates_; ++s) {
    fpos = pos;
    if (compactor.Size() == -1) states_[s] = pos;
    if (fst.Final(s) != Weight::Zero()) {
      compacts_[pos++] = compactor.Compact(
          s, Arc(kNoLabel, kNoLabel, fst.Final(s), kNoStateId));
    }
    for (ArcIterator<Fst<Arc>> aiter(fst, s); !aiter.Done(); aiter.Next()) {
      compacts_[pos++] = compactor.Compact(s, aiter.Value());
    }
    if ((compactor.Size() != -1) && ((pos - fpos) != compactor.Size())) {
      FSTERROR() << "DefaultCompactStore: Compactor incompatible with FST";
      error_ = true;
      return;
    }
  }
  if (pos != ncompacts_) {
    FSTERROR() << "DefaultCompactStore: Compactor incompatible with FST";
    error_ = true;
    return;
  }
}

template <class Element, class Unsigned>
template <class Iterator, class Compactor>
DefaultCompactStore<Element, Unsigned>::DefaultCompactStore(
    const Iterator &begin, const Iterator &end, const Compactor &compactor)
    : states_(nullptr),
      compacts_(nullptr),
      nstates_(0),
      ncompacts_(0),
      narcs_(0),
      start_(kNoStateId),
      error_(false) {
  using Arc = typename Compactor::Arc;
  using Weight = typename Arc::Weight;
  if (compactor.Size() != -1) {
    ncompacts_ = std::distance(begin, end);
    if (compactor.Size() == 1) {
      // For strings, allows implicit final weight. Empty input is the empty
      // string.
      if (ncompacts_ == 0) {
        ++ncompacts_;
      } else {
        const auto arc =
            compactor.Expand(ncompacts_ - 1, *(begin + (ncompacts_ - 1)));
        if (arc.ilabel != kNoLabel) ++ncompacts_;
      }
    }
    if (ncompacts_ % compactor.Size()) {
      FSTERROR() << "DefaultCompactStore: Size of input container incompatible"
                 << " with compactor";
      error_ = true;
      return;
    }
    if (ncompacts_ == 0) return;
    start_ = 0;
    nstates_ = ncompacts_ / compactor.Size();
    compacts_ = new Element[ncompacts_];
    size_t i = 0;
    Iterator it = begin;
    for (; it != end; ++it, ++i) {
      compacts_[i] = *it;
      if (compactor.Expand(i, *it).ilabel != kNoLabel) ++narcs_;
    }
    if (i < ncompacts_) {
      compacts_[i] = compactor.Compact(
          i, Arc(kNoLabel, kNoLabel, Weight::One(), kNoStateId));
    }
  } else {
    if (std::distance(begin, end) == 0) return;
    // Count # of states, arcs and compacts.
    auto it = begin;
    for (size_t i = 0; it != end; ++it, ++i) {
      const auto arc = compactor.Expand(i, *it);
      if (arc.ilabel != kNoLabel) {
        ++narcs_;
        ++ncompacts_;
      } else {
        ++nstates_;
        if (arc.weight != Weight::Zero()) ++ncompacts_;
      }
    }
    start_ = 0;
    compacts_ = new Element[ncompacts_];
    states_ = new Unsigned[nstates_ + 1];
    states_[nstates_] = ncompacts_;
    size_t i = 0;
    size_t s = 0;
    for (it = begin; it != end; ++it) {
      const auto arc = compactor.Expand(i, *it);
      if (arc.ilabel != kNoLabel) {
        compacts_[i++] = *it;
      } else {
        states_[s++] = i;
        if (arc.weight != Weight::Zero()) compacts_[i++] = *it;
      }
    }
    if ((s != nstates_) || (i != ncompacts_)) {
      FSTERROR() << "DefaultCompactStore: Ill-formed input container";
      error_ = true;
      return;
    }
  }
}

template <class Element, class Unsigned>
template <class Compactor>
DefaultCompactStore<Element, Unsigned>
    *DefaultCompactStore<Element, Unsigned>::Read(std::istream &strm,
                                                  const FstReadOptions &opts,
                                                  const FstHeader &hdr,
                                                  const Compactor &compactor) {
  std::unique_ptr<DefaultCompactStore<Element, Unsigned>> data(
      new DefaultCompactStore<Element, Unsigned>());
  data->start_ = hdr.Start();
  data->nstates_ = hdr.NumStates();
  data->narcs_ = hdr.NumArcs();
  if (compactor.Size() == -1) {
    if ((hdr.GetFlags() & FstHeader::IS_ALIGNED) && !AlignInput(strm)) {
      LOG(ERROR) << "DefaultCompactStore::Read: Alignment failed: "
                 << opts.source;
      return nullptr;
    }
    auto b = (data->nstates_ + 1) * sizeof(Unsigned);
    data->states_region_.reset(MappedFile::Map(
        &strm, opts.mode == FstReadOptions::MAP, opts.source, b));
    if (!strm || !data->states_region_) {
      LOG(ERROR) << "DefaultCompactStore::Read: Read failed: " << opts.source;
      return nullptr;
    }
    data->states_ =
        static_cast<Unsigned *>(data->states_region_->mutable_data());
  } else {
    data->states_ = nullptr;
  }
  data->ncompacts_ = compactor.Size() == -1 ? data->states_[data->nstates_]
                                            : data->nstates_ * compactor.Size();
  if ((hdr.GetFlags() & FstHeader::IS_ALIGNED) && !AlignInput(strm)) {
    LOG(ERROR) << "DefaultCompactStore::Read: Alignment failed: "
               << opts.source;
    return nullptr;
  }
  size_t b = data->ncompacts_ * sizeof(Element);
  data->compacts_region_.reset(
      MappedFile::Map(&strm, opts.mode == FstReadOptions::MAP, opts.source, b));
  if (!strm || !data->compacts_region_) {
    LOG(ERROR) << "DefaultCompactStore::Read: Read failed: " << opts.source;
    return nullptr;
  }
  data->compacts_ =
      static_cast<Element *>(data->compacts_region_->mutable_data());
  return data.release();
}

template <class Element, class Unsigned>
bool DefaultCompactStore<Element, Unsigned>::Write(
    std::ostream &strm, const FstWriteOptions &opts) const {
  if (states_) {
    if (opts.align && !AlignOutput(strm)) {
      LOG(ERROR) << "DefaultCompactStore::Write: Alignment failed: "
                 << opts.source;
      return false;
    }
    strm.write(reinterpret_cast<char *>(states_),
               (nstates_ + 1) * sizeof(Unsigned));
  }
  if (opts.align && !AlignOutput(strm)) {
    LOG(ERROR) << "DefaultCompactStore::Write: Alignment failed: "
               << opts.source;
    return false;
  }
  strm.write(reinterpret_cast<char *>(compacts_), ncompacts_ * sizeof(Element));
  strm.flush();
  if (!strm) {
    LOG(ERROR) << "DefaultCompactStore::Write: Write failed: " << opts.source;
    return false;
  }
  return true;
}

template <class Element, class Unsigned>
const string &DefaultCompactStore<Element, Unsigned>::Type() {
  static const string *const type = new string("compact");
  return *type;
}

template <class C, class U, class S> class DefaultCompactState;

// Wraps an arc compactor and a compact store as a new Fst compactor.
template <class C, class U,
          class S = DefaultCompactStore<typename C::Element, U>>
class DefaultCompactor {
 public:
  using ArcCompactor = C;
  using Unsigned = U;
  using CompactStore = S;
  using Element = typename C::Element;
  using Arc = typename C::Arc;
  using StateId = typename Arc::StateId;
  using Weight = typename Arc::Weight;
  using State = DefaultCompactState<C, U, S>;
  friend State;

  DefaultCompactor()
      : arc_compactor_(nullptr), compact_store_(nullptr) {}

  // Constructs from Fst.
  DefaultCompactor(const Fst<Arc> &fst,
                   std::shared_ptr<ArcCompactor> arc_compactor)
      : arc_compactor_(std::move(arc_compactor)),
        compact_store_(std::make_shared<S>(fst, *arc_compactor_)) {}

  DefaultCompactor(const Fst<Arc> &fst,
                   std::shared_ptr<DefaultCompactor<C, U, S>> compactor)
      : arc_compactor_(compactor->arc_compactor_),
        compact_store_(compactor->compact_store_ == nullptr ?
                       std::make_shared<S>(fst, *arc_compactor_) :
                       compactor->compact_store_) {}

  // Constructs from CompactStore.
  DefaultCompactor(std::shared_ptr<ArcCompactor> arc_compactor,
                   std::shared_ptr<CompactStore> compact_store)
      : arc_compactor_(std::move(arc_compactor)),
        compact_store_(std::move(compact_store)) {}

  // Constructs from set of compact elements (when arc_compactor.Size() != -1).
  template <class Iterator>
  DefaultCompactor(const Iterator &b, const Iterator &e,
                   std::shared_ptr<C> arc_compactor)
      : arc_compactor_(std::move(arc_compactor)),
        compact_store_(std::make_shared<S>(b, e, *arc_compactor_)) {}

  // Copy constructor.
  DefaultCompactor(const DefaultCompactor<C, U, S> &compactor)
      : arc_compactor_(std::make_shared<C>(*compactor.GetArcCompactor())),
        compact_store_(compactor.SharedCompactStore()) {}

  template <class OtherC>
  explicit DefaultCompactor(const DefaultCompactor<OtherC, U, S> &compactor)
      : arc_compactor_(std::make_shared<C>(*compactor.GetArcCompactor())),
        compact_store_(compactor.SharedCompactStore()) {}

  StateId Start() const { return compact_store_->Start(); }
  StateId NumStates() const { return compact_store_->NumStates(); }
  size_t NumArcs() const { return compact_store_->NumArcs(); }

  void SetState(StateId s, State *state) const {
    if (state->GetStateId() != s) state->Set(this, s);
  }

  static DefaultCompactor<C, U, S> *Read(std::istream &strm,
                                         const FstReadOptions &opts,
                                         const FstHeader &hdr) {
    std::shared_ptr<C> arc_compactor(C::Read(strm));
    if (arc_compactor == nullptr) return nullptr;
    std::shared_ptr<S> compact_store(S::Read(strm, opts, hdr, *arc_compactor));
    if (compact_store == nullptr) return nullptr;
    return new DefaultCompactor<C, U, S>(arc_compactor, compact_store);
  }

  bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
    return arc_compactor_->Write(strm) && compact_store_->Write(strm, opts);
  }

  uint64 Properties() const { return arc_compactor_->Properties(); }

  bool IsCompatible(const Fst<Arc> &fst) const {
    return arc_compactor_->Compatible(fst);
  }

  bool Error() const { return compact_store_->Error(); }

  bool HasFixedOutdegree() const { return arc_compactor_->Size() != -1; }

  static const string &Type() {
    static const string *const type = [] {
      string type = "compact";
      if (sizeof(U) != sizeof(uint32)) type += std::to_string(8 * sizeof(U));
      type += "_";
      type += C::Type();
      if (CompactStore::Type() != "compact") {
        type += "_";
        type += CompactStore::Type();
      }
      return new string(type);
    }();
    return *type;
  }

  const ArcCompactor *GetArcCompactor() const { return arc_compactor_.get(); }
  CompactStore *GetCompactStore() const { return compact_store_.get(); }

  std::shared_ptr<ArcCompactor> SharedArcCompactor() const {
    return arc_compactor_;
  }

  std::shared_ptr<CompactStore> SharedCompactStore() const {
    return compact_store_;
  }

  // TODO(allauzen): remove dependencies on this method and make private.
  Arc ComputeArc(StateId s, Unsigned i, uint32 f) const {
    return arc_compactor_->Expand(s, compact_store_->Compacts(i), f);
  }

 private:
  std::pair<Unsigned, Unsigned> CompactsRange(StateId s) const {
    std::pair<size_t, size_t> range;
    if (HasFixedOutdegree()) {
      range.first = s * arc_compactor_->Size();
      range.second = arc_compactor_->Size();
    } else {
      range.first = compact_store_->States(s);
      range.second = compact_store_->States(s + 1) - range.first;
    }
    return range;
  }

 private:
  std::shared_ptr<ArcCompactor> arc_compactor_;
  std::shared_ptr<CompactStore> compact_store_;
};

// Default implementation of state attributes accessor class for
// DefaultCompactor. Use of efficient specialization strongly encouraged.
template <class C, class U, class S>
class DefaultCompactState {
 public:
  using Arc = typename C::Arc;
  using StateId = typename Arc::StateId;
  using Weight = typename Arc::Weight;

  DefaultCompactState() = default;

  DefaultCompactState(const DefaultCompactor<C, U, S> *compactor, StateId s)
      : compactor_(compactor),
        s_(s),
        range_(compactor->CompactsRange(s)),
        has_final_(
            range_.second != 0 &&
            compactor->ComputeArc(s, range_.first,
                                 kArcILabelValue).ilabel == kNoLabel) {
    if (has_final_) {
      ++range_.first;
      --range_.second;
    }
  }

  void Set(const DefaultCompactor<C, U, S> *compactor, StateId s) {
    compactor_ = compactor;
    s_ = s;
    range_ = compactor->CompactsRange(s);
    if (range_.second != 0 &&
        compactor->ComputeArc(s, range_.first, kArcILabelValue).ilabel
        == kNoLabel) {
      has_final_ = true;
      ++range_.first;
      --range_.second;
    } else {
      has_final_ = false;
    }
  }

  StateId GetStateId() const { return s_; }

  Weight Final() const {
    if (!has_final_) return Weight::Zero();
    return compactor_->ComputeArc(s_, range_.first - 1, kArcWeightValue).weight;
  }

  size_t NumArcs() const { return range_.second; }

  Arc GetArc(size_t i, uint32 f) const {
    return compactor_->ComputeArc(s_, range_.first + i, f);
  }

 private:
  const DefaultCompactor<C, U, S> *compactor_ = nullptr;  // borrowed ref.
  StateId s_ = kNoStateId;
  std::pair<U, U> range_ = {0, 0};
  bool has_final_ = false;
};

// Specialization for DefaultCompactStore.
template <class C, class U>
class DefaultCompactState<C, U, DefaultCompactStore<typename C::Element, U>> {
 public:
  using Arc = typename C::Arc;
  using StateId = typename Arc::StateId;
  using Weight = typename Arc::Weight;
  using CompactStore = DefaultCompactStore<typename C::Element, U>;

  DefaultCompactState() = default;

  DefaultCompactState(
      const DefaultCompactor<C, U, CompactStore> *compactor, StateId s)
      : arc_compactor_(compactor->GetArcCompactor()), s_(s) {
    Init(compactor);
  }

  void Set(const DefaultCompactor<C, U, CompactStore> *compactor, StateId s) {
    arc_compactor_ = compactor->GetArcCompactor();
    s_ = s;
    has_final_ = false;
    Init(compactor);
  }

  StateId GetStateId() const { return s_; }

  Weight Final() const {
    if (!has_final_) return Weight::Zero();
    return arc_compactor_->Expand(s_, *(compacts_ - 1), kArcWeightValue).weight;
  }

  size_t NumArcs() const { return num_arcs_; }

  Arc GetArc(size_t i, uint32 f) const {
    return arc_compactor_->Expand(s_, compacts_[i], f);
  }

 private:
  void Init(const DefaultCompactor<C, U, CompactStore> *compactor) {
    const auto *store = compactor->GetCompactStore();
    U offset;
    if (!compactor->HasFixedOutdegree()) {  // Variable out-degree compactor.
      offset = store->States(s_);
      num_arcs_ = store->States(s_ + 1) - offset;
    } else {  // Fixed out-degree compactor.
      offset = s_ * arc_compactor_->Size();
      num_arcs_ = arc_compactor_->Size();
    }
    if (num_arcs_ > 0) {
      compacts_ = &(store->Compacts(offset));
      if (arc_compactor_->Expand(s_, *compacts_, kArcILabelValue).ilabel
          == kNoStateId) {
        ++compacts_;
        --num_arcs_;
        has_final_ = true;
      }
    }
  }

 private:
  const C *arc_compactor_ = nullptr;               // Borrowed reference.
  const typename C::Element *compacts_ = nullptr;  // Borrowed reference.
  StateId s_ = kNoStateId;
  U num_arcs_ = 0;
  bool has_final_ = false;
};

template <class Arc, class ArcCompactor, class Unsigned, class CompactStore,
          class CacheStore>
class CompactFst;

template <class F, class G>
void Cast(const F &, G *);

namespace internal {

// Implementation class for CompactFst, which contains parametrizeable
// Fst data storage (DefaultCompactStore by default) and Fst cache.
template <class Arc, class C, class CacheStore = DefaultCacheStore<Arc>>
class CompactFstImpl
    : public CacheBaseImpl<typename CacheStore::State, CacheStore> {
 public:
  using Weight = typename Arc::Weight;
  using StateId = typename Arc::StateId;
  using Compactor = C;

  using FstImpl<Arc>::SetType;
  using FstImpl<Arc>::SetProperties;
  using FstImpl<Arc>::Properties;
  using FstImpl<Arc>::SetInputSymbols;
  using FstImpl<Arc>::SetOutputSymbols;
  using FstImpl<Arc>::WriteHeader;

  using ImplBase = CacheBaseImpl<typename CacheStore::State, CacheStore>;
  using ImplBase::PushArc;
  using ImplBase::HasArcs;
  using ImplBase::HasFinal;
  using ImplBase::HasStart;
  using ImplBase::SetArcs;
  using ImplBase::SetFinal;
  using ImplBase::SetStart;

  CompactFstImpl()
      : ImplBase(CompactFstOptions()),
        compactor_() {
    SetType(Compactor::Type());
    SetProperties(kNullProperties | kStaticProperties);
  }

  CompactFstImpl(const Fst<Arc> &fst, std::shared_ptr<Compactor> compactor,
                 const CompactFstOptions &opts)
      : ImplBase(opts),
        compactor_(std::make_shared<Compactor>(fst, compactor)) {
    SetType(Compactor::Type());
    SetInputSymbols(fst.InputSymbols());
    SetOutputSymbols(fst.OutputSymbols());
    if (compactor_->Error()) SetProperties(kError, kError);
    uint64 copy_properties = fst.Properties(kMutable, false) ?
        fst.Properties(kCopyProperties, true):
        CheckProperties(fst,
                        kCopyProperties & ~kWeightedCycles & ~kUnweightedCycles,
                        kCopyProperties);
    if ((copy_properties & kError) || !compactor_->IsCompatible(fst)) {
      FSTERROR() << "CompactFstImpl: Input Fst incompatible with compactor";
      SetProperties(kError, kError);
      return;
    }
    SetProperties(copy_properties | kStaticProperties);
  }

  CompactFstImpl(std::shared_ptr<Compactor> compactor,
                 const CompactFstOptions &opts)
      : ImplBase(opts),
        compactor_(compactor) {
    SetType(Compactor::Type());
    SetProperties(kStaticProperties | compactor_->Properties());
    if (compactor_->Error()) SetProperties(kError, kError);
  }

  CompactFstImpl(const CompactFstImpl<Arc, Compactor, CacheStore> &impl)
      : ImplBase(impl),
        compactor_(impl.compactor_ == nullptr ?
                   std::make_shared<Compactor>() :
                   std::make_shared<Compactor>(*impl.compactor_)) {
    SetType(impl.Type());
    SetProperties(impl.Properties());
    SetInputSymbols(impl.InputSymbols());
    SetOutputSymbols(impl.OutputSymbols());
  }

  // Allows to change the cache store from OtherI to I.
  template <class OtherCacheStore>
  CompactFstImpl(const CompactFstImpl<Arc, Compactor, OtherCacheStore> &impl)
      : ImplBase(CacheOptions(impl.GetCacheGc(), impl.GetCacheLimit())),
        compactor_(impl.compactor_ == nullptr ?
                   std::make_shared<Compactor>() :
                   std::make_shared<Compactor>(*impl.compactor_)) {
    SetType(impl.Type());
    SetProperties(impl.Properties());
    SetInputSymbols(impl.InputSymbols());
    SetOutputSymbols(impl.OutputSymbols());
  }

  StateId Start() {
    if (!HasStart()) SetStart(compactor_->Start());
    return ImplBase::Start();
  }

  Weight Final(StateId s) {
    if (HasFinal(s)) return ImplBase::Final(s);
    compactor_->SetState(s, &state_);
    return state_.Final();
  }

  StateId NumStates() const {
    if (Properties(kError)) return 0;
    return compactor_->NumStates();
  }

  size_t NumArcs(StateId s) {
    if (HasArcs(s)) return ImplBase::NumArcs(s);
    compactor_->SetState(s, &state_);
    return state_.NumArcs();
  }

  size_t NumInputEpsilons(StateId s) {
    if (!HasArcs(s) && !Properties(kILabelSorted)) Expand(s);
    if (HasArcs(s)) return ImplBase::NumInputEpsilons(s);
    return CountEpsilons(s, false);
  }

  size_t NumOutputEpsilons(StateId s) {
    if (!HasArcs(s) && !Properties(kOLabelSorted)) Expand(s);
    if (HasArcs(s)) return ImplBase::NumOutputEpsilons(s);
    return CountEpsilons(s, true);
  }

  size_t CountEpsilons(StateId s, bool output_epsilons) {
    compactor_->SetState(s, &state_);
    const uint32 f = output_epsilons ? kArcOLabelValue : kArcILabelValue;
    size_t num_eps = 0;
    for (size_t i = 0; i < state_.NumArcs(); ++i) {
      const auto& arc = state_.GetArc(i, f);
      const auto label = output_epsilons ? arc.olabel : arc.ilabel;
      if (label == 0)
        ++num_eps;
      else if (label > 0)
        break;
    }
    return num_eps;
  }

  static CompactFstImpl<Arc, Compactor, CacheStore> *Read(
      std::istream &strm, const FstReadOptions &opts) {
    std::unique_ptr<CompactFstImpl<Arc, Compactor, CacheStore>> impl(
      new CompactFstImpl<Arc, Compactor, CacheStore>());
    FstHeader hdr;
    if (!impl->ReadHeader(strm, opts, kMinFileVersion, &hdr)) {
      return nullptr;
    }
    // Ensures compatibility.
    if (hdr.Version() == kAlignedFileVersion) {
      hdr.SetFlags(hdr.GetFlags() | FstHeader::IS_ALIGNED);
    }
    impl->compactor_ = std::shared_ptr<Compactor>(
        Compactor::Read(strm, opts, hdr));
    if (!impl->compactor_) {
      return nullptr;
    }
    return impl.release();
  }

  bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
    FstHeader hdr;
    hdr.SetStart(compactor_->Start());
    hdr.SetNumStates(compactor_->NumStates());
    hdr.SetNumArcs(compactor_->NumArcs());
    // Ensures compatibility.
    const auto file_version = opts.align ? kAlignedFileVersion : kFileVersion;
    WriteHeader(strm, opts, file_version, &hdr);
    return compactor_->Write(strm, opts);
  }

  // Provides information needed for generic state iterator.
  void InitStateIterator(StateIteratorData<Arc> *data) const {
    data->base = nullptr;
    data->nstates = compactor_->NumStates();
  }

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

  void Expand(StateId s) {
    compactor_->SetState(s, &state_);
    for (size_t i = 0; i < state_.NumArcs(); ++i)
      PushArc(s, state_.GetArc(i, kArcValueFlags));
    SetArcs(s);
    if (!HasFinal(s)) SetFinal(s, state_.Final());
  }

  const Compactor *GetCompactor() const { return compactor_.get(); }
  std::shared_ptr<Compactor> SharedCompactor() const { return compactor_; }
  void SetCompactor(std::shared_ptr<Compactor> compactor) {
    // TODO(allauzen): is this correct? is this needed?
    // TODO(allauzen): consider removing and forcing this through direct calls
    // to compactor.
    compactor_ = compactor;
  }

  // Properties always true of this FST class.
  static constexpr uint64 kStaticProperties = kExpanded;

 protected:
  template <class OtherArc, class OtherCompactor, class OtherCacheStore>
  explicit CompactFstImpl(
    const CompactFstImpl<OtherArc, OtherCompactor, OtherCacheStore> &impl)
    : compactor_(std::make_shared<Compactor>(*impl.GetCompactor())) {
    SetType(impl.Type());
    SetProperties(impl.Properties());
    SetInputSymbols(impl.InputSymbols());
    SetOutputSymbols(impl.OutputSymbols());
  }

 private:
  // Allows access during write.
  template <class AnyArc, class ArcCompactor, class Unsigned,
            class CompactStore, class AnyCacheStore>
  friend class ::fst::CompactFst;  // allow access during write.

  // Current unaligned file format version.
  static constexpr int kFileVersion = 2;
  // Current aligned file format version.
  static constexpr int kAlignedFileVersion = 1;
  // Minimum file format version supported.
  static constexpr int kMinFileVersion = 1;

  std::shared_ptr<Compactor> compactor_;
  typename Compactor::State state_;
};

template <class Arc, class Compactor, class CacheStore>
constexpr uint64 CompactFstImpl<Arc, Compactor, CacheStore>::kStaticProperties;

template <class Arc, class Compactor, class CacheStore>
constexpr int CompactFstImpl<Arc, Compactor, CacheStore>::kFileVersion;

template <class Arc, class Compactor, class CacheStore>
constexpr int CompactFstImpl<Arc, Compactor, CacheStore>::kAlignedFileVersion;

template <class Arc, class Compactor, class CacheStore>
constexpr int CompactFstImpl<Arc, Compactor, CacheStore>::kMinFileVersion;

}  // namespace internal

// This class attaches interface to implementation and handles reference
// counting, delegating most methods to ImplToExpandedFst. The Unsigned type
// is used to represent indices into the compact arc array. (Template
// argument defaults are declared in fst-decl.h.)
template <class A, class ArcCompactor, class Unsigned, class CompactStore,
          class CacheStore>
class CompactFst
    : public ImplToExpandedFst<internal::CompactFstImpl<
          A,
          DefaultCompactor<ArcCompactor, Unsigned, CompactStore>,
          CacheStore>> {
 public:
  template <class F, class G>
  void friend Cast(const F &, G *);

  using Arc = A;
  using StateId = typename A::StateId;
  using Compactor = DefaultCompactor<ArcCompactor, Unsigned, CompactStore>;
  using Impl = internal::CompactFstImpl<A, Compactor, CacheStore>;
  using Store = CacheStore;  // for CacheArcIterator

  friend class StateIterator<
      CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore>>;
  friend class ArcIterator<
      CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore>>;

  CompactFst() : ImplToExpandedFst<Impl>(std::make_shared<Impl>()) {}

  // If data is not nullptr, it is assumed to be already initialized.
  explicit CompactFst(
      const Fst<A> &fst,
      const ArcCompactor &compactor = ArcCompactor(),
      const CompactFstOptions &opts = CompactFstOptions(),
      std::shared_ptr<CompactStore> data = std::shared_ptr<CompactStore>())
      : ImplToExpandedFst<Impl>(
            std::make_shared<Impl>(
                fst,
                std::make_shared<Compactor>(
                    std::make_shared<ArcCompactor>(compactor), data),
                opts)) {}

  // If data is not nullptr, it is assumed to be already initialized.
  CompactFst(
      const Fst<Arc> &fst,
      std::shared_ptr<ArcCompactor> compactor,
      const CompactFstOptions &opts = CompactFstOptions(),
      std::shared_ptr<CompactStore> data = std::shared_ptr<CompactStore>())
      : ImplToExpandedFst<Impl>(
            std::make_shared<Impl>(fst,
                                   std::make_shared<Compactor>(compactor, data),
                                   opts)) {}

  // The following 2 constructors take as input two iterators delimiting a set
  // of (already) compacted transitions, starting with the transitions out of
  // the initial state. The format of the input differs for fixed out-degree
  // and variable out-degree compactors.
  //
  // - For fixed out-degree compactors, the final weight (encoded as a
  // compacted transition) needs to be given only for final states. All strings
  // (compactor of size 1) will be assume to be terminated by a final state
  // even when the final state is not implicitely given.
  //
  // - For variable out-degree compactors, the final weight (encoded as a
  // compacted transition) needs to be given for all states and must appeared
  // first in the list (for state s, final weight of s, followed by outgoing
  // transitons in s).
  //
  // These 2 constructors allows the direct construction of a CompactFst
  // without first creating a more memory-hungry regular FST. This is useful
  // when memory usage is severely constrained.
  template <class Iterator>
  explicit CompactFst(const Iterator &begin, const Iterator &end,
                      const ArcCompactor &compactor = ArcCompactor(),
                      const CompactFstOptions &opts = CompactFstOptions())
      : ImplToExpandedFst<Impl>(
            std::make_shared<Impl>(
                std::make_shared<Compactor>(
                    begin, end, std::make_shared<ArcCompactor>(compactor)),
                opts)) {}

  template <class Iterator>
  CompactFst(const Iterator &begin, const Iterator &end,
             std::shared_ptr<ArcCompactor> compactor,
             const CompactFstOptions &opts = CompactFstOptions())
      : ImplToExpandedFst<Impl>(
            std::make_shared<Impl>(
                std::make_shared<Compactor>(begin, end, compactor), opts)) {}

  // See Fst<>::Copy() for doc.
  CompactFst(
      const CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore>
      &fst,
      bool safe = false)
      : ImplToExpandedFst<Impl>(fst, safe) {}

  // Get a copy of this CompactFst. See Fst<>::Copy() for further doc.
  CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore> *Copy(
      bool safe = false) const override {
    return new CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore>(
        *this, safe);
  }

  // Read a CompactFst from an input stream; return nullptr on error
  static CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore> *Read(
      std::istream &strm, const FstReadOptions &opts) {
    auto *impl = Impl::Read(strm, opts);
    return impl ? new CompactFst<A, ArcCompactor, Unsigned, CompactStore,
                                 CacheStore>(std::shared_ptr<Impl>(impl))
                : nullptr;
  }

  // Read a CompactFst from a file; return nullptr on error
  // Empty filename reads from standard input
  static CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore> *Read(
      const string &filename) {
    auto *impl = ImplToExpandedFst<Impl>::Read(filename);
    return impl ? new CompactFst<A, ArcCompactor, Unsigned, CompactStore,
                                 CacheStore>(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);
  }

  template <class FST>
  static bool WriteFst(const FST &fst, const ArcCompactor &compactor,
                       std::ostream &strm, const FstWriteOptions &opts);

  void InitStateIterator(StateIteratorData<Arc> *data) const override {
    GetImpl()->InitStateIterator(data);
  }

  void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const override {
    GetMutableImpl()->InitArcIterator(s, data);
  }

  MatcherBase<Arc> *InitMatcher(MatchType match_type) const override {
    return new SortedMatcher<
        CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore>>(
        *this, match_type);
  }

  template <class Iterator>
  void SetCompactElements(const Iterator &b, const Iterator &e) {
    GetMutableImpl()->SetCompactor(std::make_shared<Compactor>(
        b, e, std::make_shared<ArcCompactor>()));
  }

 private:
  using ImplToFst<Impl, ExpandedFst<Arc>>::GetImpl;
  using ImplToFst<Impl, ExpandedFst<Arc>>::GetMutableImpl;

  explicit CompactFst(std::shared_ptr<Impl> impl)
      : ImplToExpandedFst<Impl>(impl) {}

  // Use overloading to extract the type of the argument.
  static Impl *GetImplIfCompactFst(
      const CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore>
          &compact_fst) {
    return compact_fst.GetImpl();
  }

  // This does not give privileged treatment to subclasses of CompactFst.
  template <typename NonCompactFst>
  static Impl *GetImplIfCompactFst(const NonCompactFst &fst) {
    return nullptr;
  }

  CompactFst &operator=(const CompactFst &fst) = delete;
};

// Writes FST in Compact format, with a possible pass over the machine before
// writing to compute the number of states and arcs.
template <class A, class ArcCompactor, class Unsigned, class CompactStore,
          class CacheStore>
template <class FST>
bool CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore>::WriteFst(
    const FST &fst, const ArcCompactor &compactor, std::ostream &strm,
    const FstWriteOptions &opts) {
  using Arc = A;
  using Weight = typename A::Weight;
  using Element = typename ArcCompactor::Element;
  const auto file_version =
      opts.align ? Impl::kAlignedFileVersion : Impl::kFileVersion;
  size_t num_arcs = -1;
  size_t num_states = -1;
  auto first_pass_compactor = compactor;
  if (auto *impl = GetImplIfCompactFst(fst)) {
    num_arcs = impl->GetCompactor()->GetCompactStore()->NumArcs();
    num_states = impl->GetCompactor()->GetCompactStore()->NumStates();
    first_pass_compactor = *impl->GetCompactor()->GetArcCompactor();
  } else {
    // A first pass is needed to compute the state of the compactor, which
    // is saved ahead of the rest of the data structures. This unfortunately
    // means forcing a complete double compaction when writing in this format.
    // TODO(allauzen): eliminate mutable state from compactors.
    num_arcs = 0;
    num_states = 0;
    for (StateIterator<FST> siter(fst); !siter.Done(); siter.Next()) {
      const auto s = siter.Value();
      ++num_states;
      if (fst.Final(s) != Weight::Zero()) {
        first_pass_compactor.Compact(
            s, Arc(kNoLabel, kNoLabel, fst.Final(s), kNoStateId));
      }
      for (ArcIterator<FST> aiter(fst, s); !aiter.Done(); aiter.Next()) {
        ++num_arcs;
        first_pass_compactor.Compact(s, aiter.Value());
      }
    }
  }
  FstHeader hdr;
  hdr.SetStart(fst.Start());
  hdr.SetNumStates(num_states);
  hdr.SetNumArcs(num_arcs);
  string type = "compact";
  if (sizeof(Unsigned) != sizeof(uint32)) {
    type += std::to_string(CHAR_BIT * sizeof(Unsigned));
  }
  type += "_";
  type += ArcCompactor::Type();
  if (CompactStore::Type() != "compact") {
    type += "_";
    type += CompactStore::Type();
  }
  const auto copy_properties = fst.Properties(kCopyProperties, true);
  if ((copy_properties & kError) || !compactor.Compatible(fst)) {
    FSTERROR() << "Fst incompatible with compactor";
    return false;
  }
  uint64 properties = copy_properties | Impl::kStaticProperties;
  internal::FstImpl<Arc>::WriteFstHeader(fst, strm, opts, file_version, type,
                                         properties, &hdr);
  first_pass_compactor.Write(strm);
  if (first_pass_compactor.Size() == -1) {
    if (opts.align && !AlignOutput(strm)) {
      LOG(ERROR) << "CompactFst::Write: Alignment failed: " << opts.source;
      return false;
    }
    Unsigned compacts = 0;
    for (StateIterator<FST> siter(fst); !siter.Done(); siter.Next()) {
      const auto s = siter.Value();
      strm.write(reinterpret_cast<const char *>(&compacts), sizeof(compacts));
      if (fst.Final(s) != Weight::Zero()) {
        ++compacts;
      }
      compacts += fst.NumArcs(s);
    }
    strm.write(reinterpret_cast<const char *>(&compacts), sizeof(compacts));
  }
  if (opts.align && !AlignOutput(strm)) {
    LOG(ERROR) << "Could not align file during write after writing states";
  }
  const auto &second_pass_compactor = compactor;
  Element element;
  for (StateIterator<FST> siter(fst); !siter.Done(); siter.Next()) {
    const auto s = siter.Value();
    if (fst.Final(s) != Weight::Zero()) {
      element = second_pass_compactor.Compact(
          s, A(kNoLabel, kNoLabel, fst.Final(s), kNoStateId));
      strm.write(reinterpret_cast<const char *>(&element), sizeof(element));
    }
    for (ArcIterator<FST> aiter(fst, s); !aiter.Done(); aiter.Next()) {
      element = second_pass_compactor.Compact(s, aiter.Value());
      strm.write(reinterpret_cast<const char *>(&element), sizeof(element));
    }
  }
  strm.flush();
  if (!strm) {
    LOG(ERROR) << "CompactFst write failed: " << opts.source;
    return false;
  }
  return true;
}

// Specialization for CompactFst; see generic version in fst.h for sample
// usage (but use the CompactFst type!). This version should inline.
template <class Arc, class ArcCompactor, class Unsigned, class CompactStore,
          class CacheStore>
class StateIterator<
    CompactFst<Arc, ArcCompactor, Unsigned, CompactStore, CacheStore>> {
 public:
  using StateId = typename Arc::StateId;

  explicit StateIterator(
      const CompactFst<Arc, ArcCompactor, Unsigned, CompactStore,
                       CacheStore> &fst)
      : nstates_(fst.GetImpl()->NumStates()), s_(0) {}

  bool Done() const { return s_ >= nstates_; }

  StateId Value() const { return s_; }

  void Next() { ++s_; }

  void Reset() { s_ = 0; }

 private:
  StateId nstates_;
  StateId s_;
};

// Specialization for CompactFst. Never caches,
// always iterates over the underlying compact elements.
template <class Arc, class ArcCompactor, class Unsigned,
          class CompactStore, class CacheStore>
class ArcIterator<CompactFst<
    Arc, ArcCompactor, Unsigned, CompactStore, CacheStore>> {
 public:
  using StateId = typename Arc::StateId;
  using Element = typename ArcCompactor::Element;
  using Compactor = DefaultCompactor<ArcCompactor, Unsigned, CompactStore>;
  using State = typename Compactor::State;

  ArcIterator(const CompactFst<Arc, ArcCompactor, Unsigned, CompactStore,
                               CacheStore> &fst,
              StateId s)
      : state_(fst.GetImpl()->GetCompactor(), s),
        pos_(0),
        flags_(kArcValueFlags) {}

  bool Done() const { return pos_ >= state_.NumArcs(); }

  const Arc &Value() const {
    arc_ = state_.GetArc(pos_, flags_);
    return arc_;
  }

  void Next() { ++pos_; }

  size_t Position() const { return pos_; }

  void Reset() { pos_ = 0; }

  void Seek(size_t pos) { pos_ = pos; }

  uint32 Flags() const { return flags_; }

  void SetFlags(uint32 f, uint32 m) {
    flags_ &= ~m;
    flags_ |= (f & kArcValueFlags);
  }

 private:
  State state_;
  size_t pos_;
  mutable Arc arc_;
  uint32 flags_;
};

// ArcCompactor for unweighted string FSTs.
template <class A>
class StringCompactor {
 public:
  using Arc = A;
  using Label = typename Arc::Label;
  using StateId = typename Arc::StateId;
  using Weight = typename Arc::Weight;

  using Element = Label;

  Element Compact(StateId s, const Arc &arc) const { return arc.ilabel; }

  Arc Expand(StateId s, const Element &p, uint32 f = kArcValueFlags) const {
    return Arc(p, p, Weight::One(), p != kNoLabel ? s + 1 : kNoStateId);
  }

  constexpr ssize_t Size() const { return 1; }

  constexpr uint64 Properties() const {
    return kString | kAcceptor | kUnweighted;
  }

  bool Compatible(const Fst<Arc> &fst) const {
    const auto props = Properties();
    return fst.Properties(props, true) == props;
  }

  static const string &Type() {
    static const string *const type = new string("string");
    return *type;
  }

  bool Write(std::ostream &strm) const { return true; }

  static StringCompactor *Read(std::istream &strm) {
    return new StringCompactor;
  }
};

// ArcCompactor for weighted string FSTs.
template <class A>
class WeightedStringCompactor {
 public:
  using Arc = A;
  using Label = typename Arc::Label;
  using StateId = typename Arc::StateId;
  using Weight = typename Arc::Weight;

  using Element = std::pair<Label, Weight>;

  Element Compact(StateId s, const Arc &arc) const {
    return std::make_pair(arc.ilabel, arc.weight);
  }

  Arc Expand(StateId s, const Element &p, uint32 f = kArcValueFlags) const {
    return Arc(p.first, p.first, p.second,
               p.first != kNoLabel ? s + 1 : kNoStateId);
  }

  constexpr ssize_t Size() const { return 1; }

  constexpr uint64 Properties() const { return kString | kAcceptor; }

  bool Compatible(const Fst<Arc> &fst) const {
    const auto props = Properties();
    return fst.Properties(props, true) == props;
  }

  static const string &Type() {
    static const string *const type = new string("weighted_string");
    return *type;
  }

  bool Write(std::ostream &strm) const { return true; }

  static WeightedStringCompactor *Read(std::istream &strm) {
    return new WeightedStringCompactor;
  }
};

// ArcCompactor for unweighted acceptor FSTs.
template <class A>
class UnweightedAcceptorCompactor {
 public:
  using Arc = A;
  using Label = typename Arc::Label;
  using StateId = typename Arc::StateId;
  using Weight = typename Arc::Weight;

  using Element = std::pair<Label, StateId>;

  Element Compact(StateId s, const Arc &arc) const {
    return std::make_pair(arc.ilabel, arc.nextstate);
  }

  Arc Expand(StateId s, const Element &p, uint32 f = kArcValueFlags) const {
    return Arc(p.first, p.first, Weight::One(), p.second);
  }

  constexpr ssize_t Size() const { return -1; }

  constexpr uint64 Properties() const { return kAcceptor | kUnweighted; }

  bool Compatible(const Fst<Arc> &fst) const {
    const auto props = Properties();
    return fst.Properties(props, true) == props;
  }

  static const string &Type() {
    static const string *const type = new string("unweighted_acceptor");
    return *type;
  }

  bool Write(std::ostream &strm) const { return true; }

  static UnweightedAcceptorCompactor *Read(std::istream &istrm) {
    return new UnweightedAcceptorCompactor;
  }
};

// ArcCompactor for weighted acceptor FSTs.
template <class A>
class AcceptorCompactor {
 public:
  using Arc = A;
  using Label = typename Arc::Label;
  using StateId = typename Arc::StateId;
  using Weight = typename Arc::Weight;

  using Element = std::pair<std::pair<Label, Weight>, StateId>;

  Element Compact(StateId s, const Arc &arc) const {
    return std::make_pair(std::make_pair(arc.ilabel, arc.weight),
                          arc.nextstate);
  }

  Arc Expand(StateId s, const Element &p, uint32 f = kArcValueFlags) const {
    return Arc(p.first.first, p.first.first, p.first.second, p.second);
  }

  constexpr ssize_t Size() const { return -1; }

  constexpr uint64 Properties() const { return kAcceptor; }

  bool Compatible(const Fst<Arc> &fst) const {
    const auto props = Properties();
    return fst.Properties(props, true) == props;
  }

  static const string &Type() {
    static const string *const type = new string("acceptor");
    return *type;
  }

  bool Write(std::ostream &strm) const { return true; }

  static AcceptorCompactor *Read(std::istream &strm) {
    return new AcceptorCompactor;
  }
};

// ArcCompactor for unweighted FSTs.
template <class A>
class UnweightedCompactor {
 public:
  using Arc = A;
  using Label = typename Arc::Label;
  using StateId = typename Arc::StateId;
  using Weight = typename Arc::Weight;

  using Element = std::pair<std::pair<Label, Label>, StateId>;

  Element Compact(StateId s, const Arc &arc) const {
    return std::make_pair(std::make_pair(arc.ilabel, arc.olabel),
                          arc.nextstate);
  }

  Arc Expand(StateId s, const Element &p, uint32 f = kArcValueFlags) const {
    return Arc(p.first.first, p.first.second, Weight::One(), p.second);
  }

  constexpr ssize_t Size() const { return -1; }

  constexpr uint64 Properties() const { return kUnweighted; }

  bool Compatible(const Fst<Arc> &fst) const {
    const auto props = Properties();
    return fst.Properties(props, true) == props;
  }

  static const string &Type() {
    static const string *const type = new string("unweighted");
    return *type;
  }

  bool Write(std::ostream &strm) const { return true; }

  static UnweightedCompactor *Read(std::istream &strm) {
    return new UnweightedCompactor;
  }
};

template <class Arc, class Unsigned /* = uint32 */>
using CompactStringFst = CompactFst<Arc, StringCompactor<Arc>, Unsigned>;

template <class Arc, class Unsigned /* = uint32 */>
using CompactWeightedStringFst =
    CompactFst<Arc, WeightedStringCompactor<Arc>, Unsigned>;

template <class Arc, class Unsigned /* = uint32 */>
using CompactAcceptorFst = CompactFst<Arc, AcceptorCompactor<Arc>, Unsigned>;

template <class Arc, class Unsigned /* = uint32 */>
using CompactUnweightedFst =
    CompactFst<Arc, UnweightedCompactor<Arc>, Unsigned>;

template <class Arc, class Unsigned /* = uint32 */>
using CompactUnweightedAcceptorFst =
    CompactFst<Arc, UnweightedAcceptorCompactor<Arc>, Unsigned>;

using StdCompactStringFst = CompactStringFst<StdArc, uint32>;

using StdCompactWeightedStringFst = CompactWeightedStringFst<StdArc, uint32>;

using StdCompactAcceptorFst = CompactAcceptorFst<StdArc, uint32>;

using StdCompactUnweightedFst = CompactUnweightedFst<StdArc, uint32>;

using StdCompactUnweightedAcceptorFst =
    CompactUnweightedAcceptorFst<StdArc, uint32>;

}  // namespace fst

#endif  // FST_COMPACT_FST_H_