// fstext/determinize-lattice-test.cc
  
  // 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.
  
  #include "fstext/determinize-lattice.h"
  #include "fstext/lattice-utils.h"
  #include "fstext/fst-test-utils.h"
  #include "base/kaldi-math.h"
  
  namespace fst {
  
  void TestLatticeStringRepository() {
    typedef int32 IntType;
  
    LatticeStringRepository<IntType> sr;
    typedef LatticeStringRepository<IntType>::Entry Entry;
  
    for(int i = 0; i < 100; i++) {
      int len = kaldi::Rand() % 5;
      vector<IntType> str(len), str2(kaldi::Rand() % 4);
      const Entry *e = NULL;
      for(int i = 0; i < len; i++) {
        str[i] = kaldi::Rand() % 5;
        e = sr.Successor(e, str[i]);
      }
      sr.ConvertToVector(e, &str2);
      assert(str == str2);
  
      int len2 = kaldi::Rand() % 5;
      str2.resize(len2);
      const Entry *f = sr.EmptyString(); // NULL
      for(int i = 0; i < len2; i++) {
        str2[i] = kaldi::Rand() % 5;
        f = sr.Successor(f, str2[i]);
      }
      vector<IntType> prefix, prefix2(kaldi::Rand() % 10),
          prefix3;
      for(int i = 0; i < len && i < len2; i++) {
        if (str[i] == str2[i]) prefix.push_back(str[i]);
        else break;
      }
      const Entry *g = sr.CommonPrefix(e, f);
      sr.ConvertToVector(g, &prefix2);
      sr.ConvertToVector(e, &prefix3);
      sr.ReduceToCommonPrefix(f, &prefix3);
      assert(prefix == prefix2);
      assert(prefix == prefix3);
      assert(sr.IsPrefixOf(g, e));
      assert(sr.IsPrefixOf(g, f));
      if (str.size() > prefix.size())
        assert(!sr.IsPrefixOf(e, g));
    }
  }
  
  
  // test that determinization proceeds correctly on general
  // FSTs (not guaranteed determinzable, but we use the
  // max-states option to stop it getting out of control).
  template<class Arc> void TestDeterminizeLattice() {
    typedef typename Arc::Weight Weight;
    typedef int32 Int;
    typedef ArcTpl<CompactLatticeWeightTpl<Weight, Int> > CompactArc;
  
    for(int i = 0; i < 100; i++) {
      RandFstOptions opts;
      opts.n_states = 4;
      opts.n_arcs = 10;
      opts.n_final = 2;
      opts.allow_empty = false;
      opts.weight_multiplier = 0.5; // impt for the randomly generated weights
      // to be exactly representable in float,
      // or this test fails because numerical differences can cause symmetry in
      // weights to be broken, which causes the wrong path to be chosen as far
      // as the string part is concerned.
  
      VectorFst<Arc> *fst = RandFst<Arc>();
      std::cout << "FST before lattice-determinizing is:
  ";
      {
        FstPrinter<Arc> fstprinter(*fst, NULL, NULL, NULL, false, true, "\t");
        fstprinter.Print(&std::cout, "standard output");
      }
      VectorFst<Arc> det_fst;
      try {
        DeterminizeLatticeOptions lat_opts;
        lat_opts.max_mem = 100;
  
        if (!DeterminizeLattice<TropicalWeight, int32>(*fst, &det_fst, lat_opts, NULL))
          throw std::runtime_error("could not determinize");
        std::cout << "FST after lattice-determinizing is:
  ";
        {
          FstPrinter<Arc> fstprinter(det_fst, NULL, NULL, NULL, false, true, "\t");
          fstprinter.Print(&std::cout, "standard output");
        }
        assert(det_fst.Properties(kIDeterministic, true) & kIDeterministic);
        // OK, now determinize it a different way and check equivalence.
        // [note: it's not normal determinization, it's taking the best path
        // for any input-symbol sequence....
        VectorFst<CompactArc> compact_fst, compact_det_fst;
        ConvertLattice<Weight, Int>(*fst, &compact_fst, false);
        std::cout << "Compact FST is:
  ";
        {
          FstPrinter<CompactArc> fstprinter(compact_fst, NULL, NULL, NULL, false, true, "\t");
          fstprinter.Print(&std::cout, "standard output");
        }
        if (kaldi::Rand() % 2 == 1)
          ConvertLattice<Weight, Int>(det_fst, &compact_det_fst, false);
        else
          if (!DeterminizeLattice<TropicalWeight, int32>(*fst, &compact_det_fst, lat_opts, NULL))
            throw std::runtime_error("could not determinize");
  
        std::cout << "Compact version of determinized FST is:
  ";
        {
          FstPrinter<CompactArc> fstprinter(compact_det_fst, NULL, NULL, NULL, false, true, "\t");
          fstprinter.Print(&std::cout, "standard output");
        }
  
        assert(RandEquivalent(compact_det_fst, compact_fst, 5/*paths*/, 0.01/*delta*/, kaldi::Rand()/*seed*/, 100/*path length, max*/));
      } catch (...) {
        std::cout << "Failed to lattice-determinize this FST (probably not determinizable)
  ";
      }
      delete fst;
    }
  }
  
  // test that determinization proceeds correctly on acyclic FSTs
  // (guaranteed determinizable in this sense).
  template<class Arc> void TestDeterminizeLattice2() {
    RandFstOptions opts;
    opts.acyclic = true;
    for(int i = 0; i < 100; i++) {
      VectorFst<Arc> *fst = RandFst<Arc>(opts);
      std::cout << "FST before lattice-determinizing is:
  ";
      {
        FstPrinter<Arc> fstprinter(*fst, NULL, NULL, NULL, false, true, "\t");
        fstprinter.Print(&std::cout, "standard output");
      }
      VectorFst<Arc> ofst;
      DeterminizeLattice<TropicalWeight, int32>(*fst, &ofst);
      std::cout << "FST after lattice-determinizing is:
  ";
      {
        FstPrinter<Arc> fstprinter(ofst, NULL, NULL, NULL, false, true, "\t");
        fstprinter.Print(&std::cout, "standard output");
      }
      delete fst;
    }
  }
  
  
  } // end namespace fst
  
  int main() {
    using namespace fst;
    TestLatticeStringRepository();
    TestDeterminizeLattice<StdArc>();
    TestDeterminizeLattice2<StdArc>();
    std::cout << "Tests succeeded
  ";
  }