// fstext/pre-determinize-inl.h

// Copyright 2009-2011  Microsoft Corporation

// See ../../COPYING for clarification regarding multiple authors
//
// 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
//
// THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
// WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
// MERCHANTABLITY OR NON-INFRINGEMENT.
// See the Apache 2 License for the specific language governing permissions and
// limitations under the License.

#ifndef KALDI_FSTEXT_PRE_DETERMINIZE_INL_H_
#define KALDI_FSTEXT_PRE_DETERMINIZE_INL_H_


/* Do not include this file directly.  It is an implementation file included by PreDeterminize.h */

/*
  Predeterminization

    This is a function that makes an FST compactly determinizable by inserting symbols on the input
  side as necessary for disambiguation.  Note that we do not treat epsilon as a real symbol
  when measuring determinizability in this sense.   The extra symbols are added to the vocabulary,
  on the input side; these are of the form (prefix)1, (prefix)2, and so on without limit, where
  (prefix) is some prefix the user provides, e.g. '#' (the function checks that this will not
  lead to conflicts with symbols already in the FST).  The function tells us how many such
  symbols it created.

   Note that there is a paper "Generalized optimization algorithm for speech recognition
   transducers" by Allauzen and Mohri, that deals with a similar issue, but this is a very
   different algorithm that only aims to ensure determinizability, but not *compact*
   determinizability.

   Our algorithm is slightly heuristic, and probably not optimal, but does ensure that the
   output is compactly determinizable, possibly at the expense of inserting unnecessary
   symbols.  We considered more sophisticated algorithms, but these were extremely
   complicated and would give the same output for the kinds of inputs that we envisage.

   Suppose the input FST is T.  We want to ensure that in det(T), if we consider the
   states of det(T) as weighted subsets of states of T, each state of T only appears once
   in any given subset.  This ensures that det(T) is no larger than T in an appropriate
   sense.  The way we do this is as follows.  We identify all states in T that have
   multiple input transitions (counting "being an initial state" as an input transition).
   Let's call these "problematic" states.  For a problematic state p we stipulate that it
   can never appear in any state of det(T) unless that state equals (p, \bar{1}) [i.e. p,
   unweighted].  In order to ensure this, we insert input symbols on the transitions to these
   problematic states (this may necessitate adding extra states).
      We also stipulate that the path through det(T) should always be sufficient to tell us
   the path through T (and we insert extra symbols sufficient to make this so).  This is to
   simplify the algorithm, so that we don't have to consider the output symbols or weights
   when predeterminizing.

   The algorithm is as follows.

    (A) Definitions

      (i)  Define a *problematic state* as a state that either has multiple input transitions,
           or is an initial state and has at least one input transition.

     (ii)  For an arc a, define:
            i[a] = input symbol on a
            o[a] = output symbol on a
            n[a] = dest-state of a
            p[a] = origin-state of a

           For a state q, define
            E[q] = set of transitions leaving q.
           For a set of states Q, define
            E[Q] = set of transitions leaving some q in Q

    (iii)  For a state s, define Closure(s) as the union of state s, and all states t
           that are reachable via sequences of arcs a such that i[a]=epsilon and n[a] is
           not problematic.

           For a set of states S, define Closure(S) as the union of the closures of
           states s in S.

    (B) Inputs and outputs.

     (i) Inputs and preconditions.  Input is an FST, which should have a symbol table compiled into
         it, and a prefix (e.g. #) for symbols to be added.  We check that the input FST is trim,
         and that it does not have any symbols that appear on its arcs, that are equal to the prefix
         followed by digits.

    (ii) Outputs: The algorithm modifies the FST that is given to it, and returns the number of
         the highest numbered "extra symbol" inserted.  The extra symbols are numbered #1, #2 and
         so on without limit (as integers).  They are inserted into the symbol table in a sequential
         way by calling AvailableKey()
         for each in turn (this is stipulated in case we need to keep other symbol tables in sync).

     (C) Sub-algorithm: Closure(S).  This requires the array p(s), defined below, which is true
         if s is problematic.  This also requires, for efficiency, that the arcs be sorted on input
         label.
            Input: a set of states S.  [plus, the fst and the array p].
            Output: a set of states T.
            Algorithm:
                set T <-- S, Q <-- S.
                while Q is nonempty:
                  pop a state s from Q.
                  for each transition a from state s with epsilon on the input label [we can
                    find these efficiently using the sorting on arcs]:
                      If p(n[a]) is false and n[a] is not in T:
                         Insert n[a] into T.
                         Add n[a] to Q.
                return T.


     (D) Main algorithm.


       (i) (a) Check preconditions (FST is trim)
           (b) Make sure there is just one final state (insert epsilon transitions as necessary).
           (c) Sort arcs on input label (so epsilon arcs are at the start of arc lists).


      (ii) Work out the set of problematic states by constructing a boolean array indexed by
           states, i.e.
             p(s)
           which is true if the state is problematic.  We can do this by constructing an array
           t(s) to store the number of transitions into each state [adding one for the initial state],
           and then setting p(s) = true if t(s) > 1.

           Also create a boolean array d(s), defined for states, and set d(s) = false.
           This array is purely for sanity-checking that we are processing each state exactly once.

     (iii) Set up an array of integers m(a), indexed by arcs (how exactly we store these is
           implementation-dependent, but this will probably be a hash from (state, arc-index) to
           integers.  m(a) will store the extra symbol, if any, to be added to that arc (or -1
           if no such symbol; we can also simply have the arc not present in the hash).  The
           initial value of m(a) is -1 (if array), or undefined (if hash).

      (iv) Initialize a set of sets-of-states S, and a queue of pairs Q, as follows.
            The pairs in Q are a pair of (set-of-states, integer), where the integer
            is the number of "special symbols" already used up for that state.

            Note that we use a special indexing for the sets in both S and Q, rather than
            using std::set.  We use a sorted vector of StateId's.  And in S, we index them
            by the lowest-numbered state-id.  Because each state is supposed to only ever
            be a member of one set, if there is an attempt to add another, different set
            with the same lowest-numbered state-id, we detect an error.

            Let I be the single initial state (OpenFST only supports one).
            We set:
              S = { Closure(I) }
              Push (Closure(I), 0)  onto Q.
            Then for each state s such that p(s) = true, and s is not an initial state:
              S <-- S u { Closure(s) }
              Push (Closure(s), 0)  onto Q.

       (v) While Q is nonempty:

          (a) Pop pair (A, n) from Q (queue discipline is arbitrary).

          (b) For each state s in A, check that d(s) is false, and set d(s) to true.
              This is for sanity checking only.

          (c)
             Let S_\eps be the set of epsilon-transitions from members of A to problematic
             states (i.e. S_\eps = \{ a \in E[A]: i[a]=\epsilon, p(n[a]) = true \}).

             Next, we will define, for each t \neq \epsilon, S_t as the set of
               transitions from some state s in S with t as the input label, i.e.:
               S_t = \{ a \in E[A]: i[a] = t \}
               We further define T_t and U_t as the subsets of S where the destination
                 state is problematic and non-problematic respectively, i.e:
               T_t = \{ a \in E[A]: i[a] = t, p(n[a]) = true \}
               U_t = \{ a \in E[A]: i[a] = t, p(n[a]) = false \}

             The easiest way to obtain these sets is probably to have a hash indexed by
               t that maps to a list of pairs (state, arc-offset) that stores S_t.
               From this we can work out the sizes of T_t and U_t on the fly.

         (d)
             for each transition a in S_\eps:
                m(a) <-- n # Will put symbol n on this transition.
                n <-- n+1  # Note, same n as in pair (A, n)

         (e)
             next,
             for each t\neq epsilon s.t. S_t is nonempty,

                if |S_t| > 1 #if-statement is because if |S_t|=|T_t|=1, no need for prefix.
                   k = 0
                   for each transition a in T_t:
                     set m(a) to k.
                     set k = k+1

                if |U_t| > 0
                   Let V_t be the set of destination-states of arcs in U_t.
                   if Closure(V_t) is not in S:
                     insert Closure(V_t) into S, and add the pair (Closure(V_t), k) to Q.

       (vi) Check that for each state in the FST, d(s) = true.

      (vii) Let n = max_a m(a).  This is the highest-numbered extra symbol (extra symbols
            start from zero, in this numbering which doesn't correspond to the symbol-table
            numbering).  Here we add n+1 extra symbols to the symbol table and store
            the mappings from 0, 1, ... n to the symbol-id.

     (viii) Set up a hash h from (state, int) to (state-id) such that
             t = h(s, k)
            will be the state-id of a newly-created state that has a transition to state s
            with input-label #k.

      (ix) For each arc a such that m(a) != 0:
             If i[a] = epsilon (the input label is epsilon):
                Change i[a] to #m(a). [i.e. prefix then digit m(a)]
             Otherwise:
                If t = h(n[a], m(a)) is not defined [where n[a] is the dest-state]:
                  create a new state t with a transition to n[a], with input-label #m(a) and
                  no output-label or weight.  Set h(n[a], m(a)) = t.
                Change n[a] to h(n[a], m(a)).


*/
namespace fst {

namespace pre_determinize_helpers {

// make it inline to avoid having to put it in a .cc file which most functions here
// could not go in.
inline bool HasBannedPrefixPlusDigits(SymbolTable *symTable, std::string prefix, std::string *bad_sym) {
  // returns true if the symbol table contains any string consisting of this
  // (possibly empty) prefix followed by a nonempty sequence of digits (0 to 9).
  // requires symTable to be non-NULL.
  // if bad_sym != NULL, puts the first bad symbol it finds in *bad_sym.
  assert(symTable != NULL);
  const char *prefix_ptr = prefix.c_str();
  size_t prefix_len = strlen(prefix_ptr);  // allowed to be zero but not encouraged.
  for (SymbolTableIterator siter(*symTable); !siter.Done(); siter.Next()) {
    const char *sym = siter.Symbol().c_str();
    if (!strncmp(prefix_ptr, sym, prefix_len)) {  // has prefix.
      if (isdigit(sym[prefix_len])) {  // we don't allow prefix followed by a digit, as a symbol.
        // Has at least one digit.
        size_t pos;
        for (pos = prefix_len;sym[pos] != '\0'; pos++)
          if (!isdigit(sym[pos])) break;
        if (sym[pos] == '\0') {  // All remaining characters were digits.
          if (bad_sym != NULL) *bad_sym = (std::string) sym;
          return true;
        }
      } // else OK because prefix was followed by '\0' or a non-digit.
    }
  }
  return false;  // doesn't have banned symbol.
}

template<class T> void CopySetToVector(const std::set<T> s, vector<T> *v) {
  // adds members of s to v, in sorted order from lowest to highest
  // (because the set was in sorted order).
  assert(v != NULL);
  v->resize(s.size());
  typename std::set<T>::const_iterator siter = s.begin();
  typename vector<T>::iterator viter = v->begin();
  for (;  siter != s.end(); ++siter, ++viter) {
    assert(viter != v->end());
    *viter = *siter;
  }
}

// Warning.  This function calls 'new'.
template<class T>
vector<T>* InsertMember(const vector<T> m, vector<vector<T>*> *S) {
  assert(m.size() > 0);
  T idx = m[0];
  assert(idx>=(T)0 && idx < (T)S->size());
  if ( (*S)[idx] != NULL) {
    assert( *((*S)[idx]) == m );
    // The vectors should be the same.  Otherwise this is a bug in the algorithm.
    // It could either be a programming error or a deeper conceptual bug.
    return NULL;  // nothing was inserted.
  } else {
    vector<T> *ret = (*S)[idx] = new vector<T>(m);  // New copy of m.
    return ret;  // was inserted.
  }
}


// See definition of Closure(S) in item A(iii) in the comment above. it's the set of states
// that are reachable from S via sequences of arcs a such that i[a]=epsilon and n[a] is
// not problematic.  We assume that the fst is sorted on input label (so epsilon arcs first)
// The algorithm is described in section (C) above.  We use the same variable for S and T.
template<class Arc> void Closure(MutableFst<Arc> *fst, std::set<typename Arc::StateId> *S,
                                 const vector<bool> &pVec) {
  typedef typename Arc::StateId StateId;
  vector<StateId> Q;
  CopySetToVector(*S, &Q);
  while (Q.size() != 0) {
    StateId s = Q.back();
    Q.pop_back();
    for (ArcIterator<MutableFst<Arc> > aiter(*fst, s); ! aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (arc.ilabel != 0) break;  // Break from the loop: due to sorting there will be no
      // more transitions with epsilons as input labels.
      if (!pVec[arc.nextstate]) {  // Next state is not problematic -> we can use this transition.
        pair< typename std::set<StateId>::iterator, bool > p = S->insert(arc.nextstate);
        if (p.second) {  // True means: was inserted into S (wasn't already there).
          Q.push_back(arc.nextstate);
        }
      }
    }
  }
} // end function Closure.

} // end namespace pre_determinize_helpers.


template<class Arc, class Int>
void PreDeterminize(MutableFst<Arc> *fst,
                    typename Arc::Label first_new_sym,
                    vector<Int> *symsOut) {
  typedef typename Arc::Label Label;
  typedef typename Arc::StateId StateId;
  typedef size_t ArcId;  // Our own typedef, not standard OpenFst.  Use size_t
  // for compatibility with argument of ArcIterator::Seek().
  typedef typename Arc::Weight Weight;
  assert(first_new_sym > 0);
  assert(fst != NULL);
  if (fst->Start() == kNoStateId) return;  // for empty FST, nothing to do.
  assert(symsOut != NULL && symsOut->size() == 0);  // we will output the symbols we add into this.

  {  // (D)(i)(a): check is trim (i.e. connected, in OpenFST parlance).
    KALDI_VLOG(2) <<  "PreDeterminize: Checking FST properties";
    uint64 props = fst->Properties(kAccessible|kCoAccessible, true);  // true-> computes properties if unknown at time when called.
    if (props != (kAccessible|kCoAccessible)) {  // All states are not both accessible and co-accessible...
      KALDI_ERR << "PreDeterminize: FST is not trim";
    }
  }

  {  // (D)(i)(b): make single final state.
    KALDI_VLOG(2) <<  "PreDeterminize: creating single final state";
    CreateSuperFinal(fst);
  }

  {  // (D)(i)(c): sort arcs on input.
    KALDI_VLOG(2) <<  "PreDeterminize: sorting arcs on input";
    ILabelCompare<Arc> icomp;
    ArcSort(fst, icomp);
  }

  StateId n_states = 0, max_state = 0;  // Compute n_states, max_state = highest-numbered state.
  {  // compute nStates, maxStates.
    for (StateIterator<MutableFst<Arc> > iter(*fst); ! iter.Done(); iter.Next()) {
      StateId state = iter.Value();
      assert(state>=0);
      n_states++;
      if (state > max_state) max_state = state;
    }
    KALDI_VLOG(2) <<  "PreDeterminize: n_states = "<<(n_states)<<", max_state ="<<(max_state);
  }

  vector<bool> p_vec(max_state+1, false);  // compute this next.
  {  // D(ii): computing the array p. ["problematic states, i.e. states with >1 input transition,
    // counting being the initial state as an input transition"].
    vector<bool> seen_vec(max_state+1, false);  // rather than counting incoming transitions we just have a bool that says we saw at least one.

    seen_vec[fst->Start()] = true;
    for (StateIterator<MutableFst<Arc> > siter(*fst); ! siter.Done(); siter.Next()) {
      for (ArcIterator<MutableFst<Arc> > aiter(*fst, siter.Value()); ! aiter.Done(); aiter.Next()) {
        const Arc &arc = aiter.Value();
        assert(arc.nextstate>=0&&arc.nextstate<max_state+1);
        if (seen_vec[arc.nextstate])
          p_vec[arc.nextstate] = true;  // now have >1 transition in, so problematic.
        else
          seen_vec[arc.nextstate] = true;
      }
    }
  }
  // D(iii): set up m(a)
  std::map<pair<StateId, ArcId>, size_t> m_map;
  // This is the array m, indexed by arcs.  It maps to the index of the symbol we add.


  // WARNING: we should be sure to clean up this memory before exiting.  Do not return
  // or throw an exception from this function, later than this point, without cleaning up!
  // Note that the vectors are shared between Q and S (they "belong to" S.
  vector<vector<StateId>* > S(max_state+1, (vector<StateId>*)(void*)0);
  vector<pair<vector<StateId>*, size_t> > Q;

  // D(iv): initialize S and Q.
  {
    vector<StateId> all_seed_states;  // all "problematic" states, plus initial state (if not problematic).
    if (!p_vec[fst->Start()])
      all_seed_states.push_back(fst->Start());
    for (StateId s = 0;s<=max_state; s++)
      if (p_vec[s]) all_seed_states.push_back(s);

    for (size_t idx = 0;idx < all_seed_states.size(); idx++) {
      StateId s = all_seed_states[idx];
      std::set<StateId> closure_s;
      closure_s.insert(s);  // insert "seed" state.
      pre_determinize_helpers::Closure(fst, &closure_s, p_vec);  // follow epsilons to non-problematic states.
      // Closure in this case whis will usually not add anything, for typical topologies in speech
      vector<StateId> closure_s_vec;
      pre_determinize_helpers::CopySetToVector(closure_s, &closure_s_vec);
      KALDI_ASSERT(closure_s_vec.size() != 0);
      vector<StateId> *ptr = pre_determinize_helpers::InsertMember(closure_s_vec, &S);
      KALDI_ASSERT(ptr != NULL);  // Or conceptual bug or programming error.
      Q.push_back(pair<vector<StateId>*, size_t>(ptr, 0));
    }
  }

  vector<bool> d_vec(max_state+1, false);  // "done vector".  Purely for debugging.


  size_t num_extra_det_states = 0;

  // (D)(v)
  while (Q.size() != 0) {

    // (D)(v)(a)
    pair<vector<StateId>*, size_t> cur_pair(Q.back());
    Q.pop_back();
    const vector<StateId> &A(*cur_pair.first);
    size_t n =cur_pair.second;  // next special symbol to add.

    // (D)(v)(b)
    for (size_t idx = 0;idx < A.size(); idx++) {
      assert(d_vec[A[idx]] == false && "This state has been seen before.  Algorithm error.");
      d_vec[A[idx]] = true;
    }

    // From here is (D)(v)(c).  We work out S_\eps and S_t (for t\neq eps)
    // simultaneously at first.
    map<Label, set<pair<pair<StateId, ArcId>, StateId> > > arc_hash;
    // arc_hash is a hash with info of all arcs from states in the set A to
    // non-problematic states.
    // It is a map from ilabel to pair(pair(start-state, arc-offset), end-state).
    // Here, arc-offset reflects the order in which we accessed the arc using the
    // ArcIterator (zero for the first arc).


    {  // This block sets up arc_hash
      for (size_t idx = 0;idx < A.size(); idx++) {
        StateId s = A[idx];
        assert(s>=0 && s<=max_state);
        ArcId arc_id = 0;
        for (ArcIterator<MutableFst<Arc> > aiter(*fst, s); ! aiter.Done(); aiter.Next(), ++arc_id) {
          const Arc &arc = aiter.Value();

          pair<pair<StateId, ArcId>, StateId>
              this_pair(pair<StateId, ArcId>(s, arc_id), arc.nextstate);
          bool inserted = (arc_hash[arc.ilabel].insert(this_pair)).second;
          assert(inserted);  // Otherwise we had a duplicate.
        }
      }
    }

    // (D)(v)(d)
    if (arc_hash.count(0) == 1) {  // We have epsilon transitions out.
      set<pair<pair<StateId, ArcId>, StateId> >  &eps_set = arc_hash[0];
      typedef typename set<pair<pair<StateId, ArcId>, StateId> >::iterator set_iter_t;
      for (set_iter_t siter = eps_set.begin(); siter != eps_set.end(); ++siter) {
        const pair<pair<StateId, ArcId>, StateId>  &this_pr = *siter;
        if (p_vec[this_pr.second]) {  // Eps-transition to problematic state.
          assert(m_map.count(this_pr.first) == 0);
          m_map[this_pr.first] = n;
          n++;
        }
      }
    }

    // (D)(v)(e)
    {
      typedef typename map<Label, set<pair<pair<StateId, ArcId>, StateId> > >::iterator map_iter_t;
      typedef typename set<pair<pair<StateId, ArcId>, StateId> >::iterator set_iter_t2;
      for (map_iter_t miter = arc_hash.begin(); miter != arc_hash.end(); ++miter) {
        Label t = miter->first;
        set<pair<pair<StateId, ArcId>, StateId> >  &S_t = miter->second;
        if (t != 0) {  // For t != epsilon,
          set<StateId> V_t;  // set of destination non-problem states.  Will create this set now.

          // exists_noproblem is true iff |U_t| > 0.
          size_t k = 0;

          // First loop "for each transition a in T_t" (i.e. transitions to problematic states)
          // The if-statement if (|S_t|>1) is pushed inside the loop, as the loop also computes
          // the set V_t.
          for (set_iter_t2 siter = S_t.begin(); siter != S_t.end(); ++siter) {
            const pair<pair<StateId, ArcId>, StateId>  &this_pr = *siter;
            if (p_vec[this_pr.second]) {  // only consider problematic states (just set T_t)
              if (S_t.size() > 1) {  // This is where we pushed the if-statement in.
                assert(m_map.count(this_pr.first) == 0);
                m_map[this_pr.first] = k;
                k++;
                num_extra_det_states++;
              }
            } else {  // Create the set V_t.
              V_t.insert(this_pr.second);
            }
          }
          if (V_t.size() != 0) {
            pre_determinize_helpers::Closure(fst, &V_t, p_vec);  // follow epsilons to non-problematic states.
            vector<StateId> closure_V_t_vec;
            pre_determinize_helpers::CopySetToVector(V_t, &closure_V_t_vec);
            vector<StateId> *ptr = pre_determinize_helpers::InsertMember(closure_V_t_vec, &S);
            if (ptr != NULL) {  // was inserted.
              Q.push_back(pair<vector<StateId>*, size_t>(ptr, k));
            }
          }
        }
      }
    }
  } // end while (Q.size() != 0)


  {  // (D)(vi): Check that for each state in the FST, d(s) = true.
    for (StateIterator<MutableFst<Arc> > siter(*fst); ! siter.Done(); siter.Next()) {
      StateId val = siter.Value();
      assert(d_vec[val] == true);
    }
  }

  {  // (D)(vii): compute symbol-table ID's.
    // sets up symsOut array.
    int64 n = -1;
    for (typename map<pair<StateId, ArcId>, size_t>::iterator m_iter = m_map.begin();
        m_iter != m_map.end();
        ++m_iter) {
      n = std::max(n, (int64) m_iter->second);  // m_iter->second is of type size_t.
    }
    // At this point n is the highest symbol-id (type size_t) of symbols we must add.
    n++;  // This is now the number of symbols we must add.
    for (size_t i = 0;static_cast<int64>(i)<n;i++) symsOut->push_back(first_new_sym + i);
  }

  // (D)(viii): set up hash.
  map<pair<StateId, size_t>, StateId> h_map;

  {  // D(ix): add extra symbols!  This is where the work gets done.

    // Core part of this is below, search for (*)
    size_t n_states_added = 0;

    for (typename map<pair<StateId, ArcId>, size_t>::iterator m_iter = m_map.begin();
        m_iter != m_map.end();
        ++m_iter) {
      StateId state = m_iter->first.first;
      ArcId arcpos = m_iter->first.second;
      size_t m_a = m_iter->second;

      MutableArcIterator<MutableFst<Arc> > aiter(fst, state);
      aiter.Seek(arcpos);
      Arc arc = aiter.Value();

      // (*) core part here.
      if (arc.ilabel == 0)
        arc.ilabel = (*symsOut)[m_a];
      else {
        pair<StateId, size_t> pr(arc.nextstate, m_a);
        if (!h_map.count(pr)) {
          n_states_added++;
          StateId newstate = fst->AddState();
          assert(newstate>=0);
          Arc new_arc( (*symsOut)[m_a], (Label)0, Weight::One(), arc.nextstate);
          fst->AddArc(newstate, new_arc);
          h_map[pr] = newstate;
        }
        arc.nextstate = h_map[pr];
      }
      aiter.SetValue(arc);
    }

    KALDI_VLOG(2) <<  "Added " <<(n_states_added)<<" new states and added/changed "<<(m_map.size())<<" arcs";

  }
  // Now free up memory.
  for (size_t i = 0;i < S.size();i++)
    delete S[i];
} // end function PreDeterminize


template<class Label> void CreateNewSymbols(SymbolTable *input_sym_table, int nSym,
                                            std::string prefix, vector<Label> *symsOut) {
  // Creates nSym new symbols named (prefix)0, (prefix)1 and so on.
  // Crashes if it cannot create them because one or more of them were in the symbol
  // table already.
  assert(symsOut && symsOut->size() == 0);
  for (int i = 0;i < nSym;i++) {
    std::stringstream ss; ss << prefix << i;
    std::string str = ss.str();
    if (input_sym_table->Find(str) != -1) {  // should not be present.
    }
    assert(symsOut);
    symsOut->push_back( (Label) input_sym_table->AddSymbol(str));
  }
}


// see pre-determinize.h for documentation.
template<class Arc> void AddSelfLoops(MutableFst<Arc> *fst, vector<typename Arc::Label> &isyms,
                                      vector<typename Arc::Label> &osyms) {
  assert(fst != NULL);
  assert(isyms.size() == osyms.size());
  typedef typename Arc::Label Label;
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;
  size_t n = isyms.size();
  if (n == 0) return;  // Nothing to do.

  // {
  // the following declarations and statements are for quick detection of these
  // symbols, which is purely for debugging/checking purposes.
  Label  isyms_min = *std::min_element(isyms.begin(), isyms.end()),
         isyms_max = *std::max_element(isyms.begin(), isyms.end()),
         osyms_min = *std::min_element(osyms.begin(), osyms.end()),
         osyms_max = *std::max_element(osyms.begin(), osyms.end());
  std::set<Label> isyms_set, osyms_set;
  for (size_t i = 0;i < isyms.size();i++) {
    assert(isyms[i] > 0 && osyms[i] > 0);  // should not have epsilon or invalid symbols.
    isyms_set.insert(isyms[i]);
    osyms_set.insert(osyms[i]);
  }
  assert(isyms_set.size() == n && osyms_set.size() == n);
  // } end block.

  for (StateIterator<MutableFst<Arc> > siter(*fst); ! siter.Done(); siter.Next()) {
    StateId state = siter.Value();
    bool this_state_needs_self_loops = (fst->Final(state) != Weight::Zero());
    for (ArcIterator<MutableFst<Arc> > aiter(*fst, state); ! aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      // If one of the following asserts fails, it means that the input FST already had the symbols
      // we are inserting.  This is contrary to the preconditions of this algorithm.
      assert(!(arc.ilabel>=isyms_min && arc.ilabel<=isyms_max && isyms_set.count(arc.ilabel) != 0));
      assert(!(arc.olabel>=osyms_min && arc.olabel<=osyms_max && osyms_set.count(arc.olabel) != 0));
      if (arc.olabel != 0) // Has non-epsilon output label -> need self loops.
        this_state_needs_self_loops = true;
    }
    if (this_state_needs_self_loops) {
      for (size_t i = 0;i < n;i++) {
        Arc arc;
        arc.ilabel = isyms[i];
        arc.olabel = osyms[i];
        arc.weight = Weight::One();
        arc.nextstate = state;
        fst->AddArc(state, arc);
      }
    }
  }
}

template<class Arc>
int64 DeleteISymbols(MutableFst<Arc> *fst, vector<typename Arc::Label> isyms) {

  // We could do this using the Mapper concept, but this is much easier to understand.

  typedef typename Arc::Label Label;
  typedef typename Arc::StateId StateId;

  int64 num_deleted = 0;

  if (isyms.size() == 0) return 0;
  Label  isyms_min = *std::min_element(isyms.begin(), isyms.end()),
         isyms_max = *std::max_element(isyms.begin(), isyms.end());
  bool isyms_consecutive = (isyms_max+1-isyms_min == static_cast<Label>(isyms.size()));
  std::set<Label> isyms_set;
  if (!isyms_consecutive)
    for (size_t i = 0;i < isyms.size();i++)
      isyms_set.insert(isyms[i]);

  for (StateIterator<MutableFst<Arc> > siter(*fst); ! siter.Done(); siter.Next()) {
    StateId state = siter.Value();
    for (MutableArcIterator<MutableFst<Arc> > aiter(fst, state); ! aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (arc.ilabel >= isyms_min && arc.ilabel <= isyms_max) {
        if (isyms_consecutive || isyms_set.count(arc.ilabel) != 0) {
          num_deleted++;
          Arc mod_arc (arc);
          mod_arc.ilabel = 0;  // change label to epsilon.
          aiter.SetValue(mod_arc);
        }
      }
    }
  }
  return num_deleted;
}

template<class Arc>
typename Arc::StateId CreateSuperFinal(MutableFst<Arc> *fst) {
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;
  assert(fst != NULL);
  StateId num_states = fst->NumStates();
  StateId num_final = 0;
  vector<StateId> final_states;
  for (StateId s = 0; s < num_states; s++) {
    if (fst->Final(s) != Weight::Zero()) {
      num_final++;
      final_states.push_back(s);
    }
  }
  if (final_states.size() == 1) {
    if (fst->Final(final_states[0]) == Weight::One()) {
      ArcIterator<MutableFst<Arc> > iter(*fst, final_states[0]);
      if (iter.Done()) {
        // We already have a final state w/ no transitions out and unit weight.
        // So we're done.
        return final_states[0];
      }
    }
  }

  StateId final_state = fst->AddState();
  fst->SetFinal(final_state, Weight::One());
  for (size_t idx = 0;idx < final_states.size(); idx++) {
    StateId s = final_states[idx];
    Weight weight = fst->Final(s);
    fst->SetFinal(s, Weight::Zero());
    Arc arc;
    arc.ilabel = 0;
    arc.olabel = 0;
    arc.nextstate = final_state;
    arc.weight = weight;
    fst->AddArc(s, arc);
  }
  return final_state;
}


}  // namespace fst

#endif  // KALDI_FSTEXT_PRE_DETERMINIZE_INL_H_