1 files changed, 155 insertions, 0 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/closure.h b/kaldi_io/src/tools/openfst/include/fst/closure.h
new file mode 100644
index 0000000..541562b
--- /dev/null
+++ b/kaldi_io/src/tools/openfst/include/fst/closure.h
@@ -0,0 +1,155 @@
+// closure.h
+
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Copyright 2005-2010 Google, Inc.
+// Author: riley@google.com (Michael Riley)
+//
+// \file
+// Functions and classes to compute the concatenative closure of an Fst.
+
+#ifndef FST_LIB_CLOSURE_H__
+#define FST_LIB_CLOSURE_H__
+
+#include <vector>
+using std::vector;
+#include <algorithm>
+
+#include <fst/mutable-fst.h>
+#include <fst/rational.h>
+
+
+namespace fst {
+
+// Computes the concatenative closure. This version modifies its
+// MutableFst input. If FST transduces string x to y with weight a,
+// then the closure transduces x to y with weight a, xx to yy with
+// weight Times(a, a), xxx to yyy with with Times(Times(a, a), a),
+// etc. If closure_type == CLOSURE_STAR, then the empty string is
+// transduced to itself with weight Weight::One() as well.
+//
+// Complexity:
+// - Time: O(V)
+// - Space: O(V)
+// where V = # of states.
+template<class Arc>
+void Closure(MutableFst<Arc> *fst, ClosureType closure_type) {
+  typedef typename Arc::StateId StateId;
+  typedef typename Arc::Label Label;
+  typedef typename Arc::Weight Weight;
+
+  uint64 props = fst->Properties(kFstProperties, false);
+  StateId start = fst->Start();
+  for (StateIterator< MutableFst<Arc> > siter(*fst);
+       !siter.Done();
+       siter.Next()) {
+    StateId s = siter.Value();
+    Weight final = fst->Final(s);
+    if (final != Weight::Zero())
+      fst->AddArc(s, Arc(0, 0, final, start));
+  }
+  if (closure_type == CLOSURE_STAR) {
+    fst->ReserveStates(fst->NumStates() + 1);
+    StateId nstart = fst->AddState();
+    fst->SetStart(nstart);
+    fst->SetFinal(nstart, Weight::One());
+    if (start != kNoLabel)
+      fst->AddArc(nstart, Arc(0, 0, Weight::One(), start));
+  }
+  fst->SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR),
+                     kFstProperties);
+}
+
+// Computes the concatenative closure. This version modifies its
+// RationalFst input.
+template<class Arc>
+void Closure(RationalFst<Arc> *fst, ClosureType closure_type) {
+  fst->GetImpl()->AddClosure(closure_type);
+}
+
+
+struct ClosureFstOptions : RationalFstOptions {
+  ClosureType type;
+
+  ClosureFstOptions(const RationalFstOptions &opts, ClosureType t)
+      : RationalFstOptions(opts), type(t) {}
+  explicit ClosureFstOptions(ClosureType t) : type(t) {}
+  ClosureFstOptions() : type(CLOSURE_STAR) {}
+};
+
+
+// Computes the concatenative closure. This version is a delayed
+// Fst. If FST transduces string x to y with weight a, then the
+// closure transduces x to y with weight a, xx to yy with weight
+// Times(a, a), xxx to yyy with weight Times(Times(a, a), a), etc. If
+// closure_type == CLOSURE_STAR, then The empty string is transduced
+// to itself with weight Weight::One() as well.
+//
+// Complexity:
+// - Time: O(v)
+// - Space: O(v)
+// where v = # of states visited. Constant time and space to visit an
+// input state or arc is assumed and exclusive of caching.
+template <class A>
+class ClosureFst : public RationalFst<A> {
+ public:
+  using ImplToFst< RationalFstImpl<A> >::GetImpl;
+
+  typedef A Arc;
+
+  ClosureFst(const Fst<A> &fst, ClosureType closure_type) {
+    GetImpl()->InitClosure(fst, closure_type);
+  }
+
+  ClosureFst(const Fst<A> &fst, const ClosureFstOptions &opts)
+      : RationalFst<A>(opts) {
+    GetImpl()->InitClosure(fst, opts.type);
+  }
+
+  // See Fst<>::Copy() for doc.
+  ClosureFst(const ClosureFst<A> &fst, bool safe = false)
+      : RationalFst<A>(fst, safe) {}
+
+  // Get a copy of this ClosureFst. See Fst<>::Copy() for further doc.
+  virtual ClosureFst<A> *Copy(bool safe = false) const {
+    return new ClosureFst<A>(*this, safe);
+  }
+};
+
+
+// Specialization for ClosureFst.
+template <class A>
+class StateIterator< ClosureFst<A> > : public StateIterator< RationalFst<A> > {
+ public:
+  explicit StateIterator(const ClosureFst<A> &fst)
+      : StateIterator< RationalFst<A> >(fst) {}
+};
+
+
+// Specialization for ClosureFst.
+template <class A>
+class ArcIterator< ClosureFst<A> > : public ArcIterator< RationalFst<A> > {
+ public:
+  typedef typename A::StateId StateId;
+
+  ArcIterator(const ClosureFst<A> &fst, StateId s)
+      : ArcIterator< RationalFst<A> >(fst, s) {}
+};
+
+
+// Useful alias when using StdArc.
+typedef ClosureFst<StdArc> StdClosureFst;
+
+}  // namespace fst
+
+#endif  // FST_LIB_CLOSURE_H__