1// intersect.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// Class to compute the intersection of two FSAs
18
19#ifndef FST_LIB_INTERSECT_H__
20#define FST_LIB_INTERSECT_H__
21
22#include "fst/lib/compose.h"
23
24namespace fst {
25
26template <uint64 T = 0>
27struct IntersectFstOptions : public ComposeFstOptions<T> { };
28
29
30// Computes the intersection (Hadamard product) of two FSAs. This
31// version is a delayed Fst.  Only strings that are in both automata
32// are retained in the result.
33//
34// The two arguments must be acceptors. One of the arguments must be
35// label-sorted.
36//
37// Complexity: same as ComposeFst.
38//
39// Caveats:  same as ComposeFst.
40template <class A>
41class IntersectFst : public ComposeFst<A> {
42 public:
43  using ComposeFst<A>::Impl;
44
45  typedef A Arc;
46  typedef typename A::Weight Weight;
47  typedef typename A::StateId StateId;
48
49  IntersectFst(const Fst<A> &fst1, const Fst<A> &fst2)
50      : ComposeFst<A>(fst1, fst2) {
51    if (!fst1.Properties(kAcceptor, true) || !fst2.Properties(kAcceptor, true))
52      LOG(FATAL) << "IntersectFst: arguments not both acceptors";
53    uint64 props1 = fst1.Properties(kFstProperties, false);
54    uint64 props2 = fst2.Properties(kFstProperties, false);
55    Impl()->SetProperties(IntersectProperties(props1, props2),
56                          kCopyProperties);
57  }
58
59  template <uint64 T>
60  IntersectFst(const Fst<A> &fst1, const Fst<A> &fst2,
61               const IntersectFstOptions<T> &opts)
62      : ComposeFst<A>(fst1, fst2, ComposeFstOptions<T>(opts)) {
63    if (!fst1.Properties(kAcceptor, true) || !fst2.Properties(kAcceptor, true))
64      LOG(FATAL) << "IntersectFst: arguments not both acceptors";
65    uint64 props1 = fst1.Properties(kFstProperties, false);
66    uint64 props2 = fst2.Properties(kFstProperties, false);
67    Impl()->SetProperties(IntersectProperties(props1, props2),
68                          kCopyProperties);
69  }
70
71  IntersectFst(const IntersectFst<A> &fst) : ComposeFst<A>(fst) {}
72
73  virtual IntersectFst<A> *Copy() const {
74    return new IntersectFst<A>(*this);
75  }
76};
77
78
79// Specialization for IntersectFst.
80template <class A>
81class StateIterator< IntersectFst<A> >
82    : public StateIterator< ComposeFst<A> > {
83 public:
84  explicit StateIterator(const IntersectFst<A> &fst)
85      : StateIterator< ComposeFst<A> >(fst) {}
86};
87
88
89// Specialization for IntersectFst.
90template <class A>
91class ArcIterator< IntersectFst<A> >
92    : public ArcIterator< ComposeFst<A> > {
93 public:
94  typedef typename A::StateId StateId;
95
96  ArcIterator(const IntersectFst<A> &fst, StateId s)
97      : ArcIterator< ComposeFst<A> >(fst, s) {}
98};
99
100// Useful alias when using StdArc.
101typedef IntersectFst<StdArc> StdIntersectFst;
102
103
104typedef ComposeOptions IntersectOptions;
105
106
107// Computes the intersection (Hadamard product) of two FSAs. This
108// version writes the intersection to an output MurableFst. Only
109// strings that are in both automata are retained in the result.
110//
111// The two arguments must be acceptors. One of the arguments must be
112// label-sorted.
113//
114// Complexity: same as Compose.
115//
116// Caveats:  same as Compose.
117template<class Arc>
118void Intersect(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
119             MutableFst<Arc> *ofst,
120             const IntersectOptions &opts = IntersectOptions()) {
121  IntersectFstOptions<> nopts;
122  nopts.gc_limit = 0;  // Cache only the last state for fastest copy.
123  *ofst = IntersectFst<Arc>(ifst1, ifst2, nopts);
124  if (opts.connect)
125    Connect(ofst);
126}
127
128}  // namespace fst
129
130#endif  // FST_LIB_INTERSECT_H__
131