1// closure.h
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15//
16// \file
17// Functions and classes to compute the concatenative closure of an Fst.
18
19#ifndef FST_LIB_CLOSURE_H__
20#define FST_LIB_CLOSURE_H__
21
22#include "fst/lib/mutable-fst.h"
23#include "fst/lib/rational.h"
24
25namespace fst {
26
27// Computes the concatenative closure. This version modifies its
28// MutableFst input. If FST transduces string x to y with weight a,
29// then the closure transduces x to y with weight a, xx to yy with
30// weight Times(a, a), xxx to yyy with with Times(Times(a, a), a),
31// etc. If closure_type == CLOSURE_STAR, then the empty string is
32// transduced to itself with weight Weight::One() as well.
33//
34// Complexity:
35// - Time: O(V)
36// - Space: O(V)
37// where V = # of states.
38template<class Arc>
39void Closure(MutableFst<Arc> *fst, ClosureType closure_type) {
40  typedef typename Arc::StateId StateId;
41  typedef typename Arc::Label Label;
42  typedef typename Arc::Weight Weight;
43
44  uint64 props = fst->Properties(kFstProperties, false);
45  StateId start = fst->Start();
46  for (StateIterator< MutableFst<Arc> > siter(*fst);
47       !siter.Done();
48       siter.Next()) {
49    StateId s = siter.Value();
50    Weight final = fst->Final(s);
51    if (final != Weight::Zero())
52      fst->AddArc(s, Arc(0, 0, final, start));
53  }
54  if (closure_type == CLOSURE_STAR) {
55    StateId nstart = fst->AddState();
56    fst->SetStart(nstart);
57    fst->SetFinal(nstart, Weight::One());
58    if (start != kNoLabel)
59      fst->AddArc(nstart, Arc(0, 0, Weight::One(), start));
60  }
61  fst->SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR),
62                     kFstProperties);
63}
64
65// Computes the concatenative closure. This version modifies its
66// RationalFst input.
67template<class Arc>
68void Closure(RationalFst<Arc> *fst, ClosureType closure_type) {
69  fst->Impl()->AddClosure(closure_type);
70}
71
72
73struct ClosureFstOptions : RationalFstOptions {
74  ClosureType type;
75
76  ClosureFstOptions(const RationalFstOptions &opts, ClosureType t)
77      : RationalFstOptions(opts), type(t) {}
78  explicit ClosureFstOptions(ClosureType t) : type(t) {}
79  ClosureFstOptions() : type(CLOSURE_STAR) {}
80};
81
82
83// Computes the concatenative closure. This version is a delayed
84// Fst. If FST transduces string x to y with weight a, then the
85// closure transduces x to y with weight a, xx to yy with weight
86// Times(a, a), xxx to yyy with weight Times(Times(a, a), a), etc. If
87// closure_type == CLOSURE_STAR, then The empty string is transduced
88// to itself with weight Weight::One() as well.
89//
90// Complexity:
91// - Time: O(v)
92// - Space: O(v)
93// where v = # of states visited. Constant time and space to visit an
94// input state or arc is assumed and exclusive of caching.
95template <class A>
96class ClosureFst : public RationalFst<A> {
97 public:
98  using RationalFst<A>::Impl;
99
100  typedef A Arc;
101
102  ClosureFst(const Fst<A> &fst, ClosureType closure_type) {
103    Impl()->InitClosure(fst, closure_type);
104  }
105
106  ClosureFst(const Fst<A> &fst, const ClosureFstOptions &opts)
107      : RationalFst<A>(opts) {
108    Impl()->InitClosure(fst, opts.type);
109  }
110
111  ClosureFst(const ClosureFst<A> &fst) : RationalFst<A>(fst) {}
112
113  virtual ClosureFst<A> *Copy() const { return new ClosureFst<A>(*this); }
114};
115
116
117// Specialization for ClosureFst.
118template <class A>
119class StateIterator< ClosureFst<A> > : public StateIterator< RationalFst<A> > {
120 public:
121  explicit StateIterator(const ClosureFst<A> &fst)
122      : StateIterator< RationalFst<A> >(fst) {}
123};
124
125
126// Specialization for ClosureFst.
127template <class A>
128class ArcIterator< ClosureFst<A> > : public ArcIterator< RationalFst<A> > {
129 public:
130  typedef typename A::StateId StateId;
131
132  ArcIterator(const ClosureFst<A> &fst, StateId s)
133      : ArcIterator< RationalFst<A> >(fst, s) {}
134};
135
136
137// Useful alias when using StdArc.
138typedef ClosureFst<StdArc> StdClosureFst;
139
140}  // namespace fst
141
142#endif  // FST_LIB_CLOSURE_H__
143