14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// compose.h
24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License");
44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License.
54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at
64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//      http://www.apache.org/licenses/LICENSE-2.0
84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software
104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS,
114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and
134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License.
144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file
174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Class to compute the composition of two FSTs
184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_COMPOSE_H__
204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_COMPOSE_H__
214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <algorithm>
234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
2473018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers#include <unordered_map>
254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/cache.h"
274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/test-properties.h"
284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst {
304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Enumeration of uint64 bits used to represent the user-defined
324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// properties of FST composition (in the template parameter to
334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// ComposeFstOptions<T>). The bits stand for extensions of generic FST
344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// composition. ComposeFstOptions<> (all the bits unset) is the "plain"
354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// compose without any extra extensions.
364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectenum ComposeTypes {
374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // RHO: flags dealing with a special "rest" symbol in the FSTs.
384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // NB: at most one of the bits COMPOSE_FST1_RHO, COMPOSE_FST2_RHO
394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // may be set.
404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_FST1_RHO    = 1ULL<<0,  // "Rest" symbol on the output side of fst1.
414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_FST2_RHO    = 1ULL<<1,  // "Rest" symbol on the input side of fst2.
424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_FST1_PHI    = 1ULL<<2,  // "Failure" symbol on the output
434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                                  // side of fst1.
444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_FST2_PHI    = 1ULL<<3,  // "Failure" symbol on the input side
454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                                  // of fst2.
464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_FST1_SIGMA  = 1ULL<<4,  // "Any" symbol on the output side of
474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                                  // fst1.
484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_FST2_SIGMA  = 1ULL<<5,  // "Any" symbol on the input side of
494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                                  // fst2.
504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Optimization related bits.
514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_GENERIC     = 1ULL<<32,  // Disables optimizations, applies
524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                                   // the generic version of the
534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                                   // composition algorithm. This flag
544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                                   // is used for internal testing
554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                                   // only.
564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // -----------------------------------------------------------------
584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Auxiliary enum values denoting specific combinations of
594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // bits. Internal use only.
604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_RHO         = COMPOSE_FST1_RHO | COMPOSE_FST2_RHO,
614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_PHI         = COMPOSE_FST1_PHI | COMPOSE_FST2_PHI,
624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_SIGMA       = COMPOSE_FST1_SIGMA | COMPOSE_FST2_SIGMA,
634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_SPECIAL_SYMBOLS = COMPOSE_RHO | COMPOSE_PHI | COMPOSE_SIGMA,
644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // -----------------------------------------------------------------
664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // The following bits, denoting specific optimizations, are
674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // typically set *internally* by the composition algorithm.
684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_FST1_STRING = 1ULL<<33,  // fst1 is a string
694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_FST2_STRING = 1ULL<<34,  // fst2 is a string
704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_FST1_DET    = 1ULL<<35,  // fst1 is deterministic
714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_FST2_DET    = 1ULL<<36,  // fst2 is deterministic
724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  COMPOSE_INTERNAL_MASK    = 0xffffffff00000000ULL
734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project};
744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <uint64 T = 0ULL>
774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct ComposeFstOptions : public CacheOptions {
784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  explicit ComposeFstOptions(const CacheOptions &opts) : CacheOptions(opts) {}
794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  ComposeFstOptions() { }
804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project};
814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Abstract base for the implementation of delayed ComposeFst. The
844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// concrete specializations are templated on the (uint64-valued)
854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// properties of the FSTs being composed.
864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A>
874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ComposeFstImplBase : public CacheImpl<A> {
884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public:
894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  using FstImpl<A>::SetType;
904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  using FstImpl<A>::SetProperties;
914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  using FstImpl<A>::Properties;
924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  using FstImpl<A>::SetInputSymbols;
934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  using FstImpl<A>::SetOutputSymbols;
944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  using CacheBaseImpl< CacheState<A> >::HasStart;
964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  using CacheBaseImpl< CacheState<A> >::HasFinal;
974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  using CacheBaseImpl< CacheState<A> >::HasArcs;
984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef typename A::Label Label;
1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef typename A::Weight Weight;
1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef typename A::StateId StateId;
1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef CacheState<A> State;
1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  ComposeFstImplBase(const Fst<A> &fst1,
1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                     const Fst<A> &fst2,
1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                     const CacheOptions &opts)
1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      :CacheImpl<A>(opts), fst1_(fst1.Copy()), fst2_(fst2.Copy()) {
1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    SetType("compose");
1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    uint64 props1 = fst1.Properties(kFstProperties, false);
1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    uint64 props2 = fst2.Properties(kFstProperties, false);
1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    SetProperties(ComposeProperties(props1, props2), kCopyProperties);
1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (!CompatSymbols(fst2.InputSymbols(), fst1.OutputSymbols()))
1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      LOG(FATAL) << "ComposeFst: output symbol table of 1st argument "
1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                 << "does not match input symbol table of 2nd argument";
1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    SetInputSymbols(fst1.InputSymbols());
1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    SetOutputSymbols(fst2.OutputSymbols());
1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual ~ComposeFstImplBase() {
1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    delete fst1_;
1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    delete fst2_;
1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  StateId Start() {
1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (!HasStart()) {
1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      StateId start = ComputeStart();
1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      if (start != kNoStateId) {
130ea4ad6085a8661b5513c394316108c0ef26f3e7bAl Sutton        this->SetStart(start);
1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      }
1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return CacheImpl<A>::Start();
1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  Weight Final(StateId s) {
1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (!HasFinal(s)) {
1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      Weight final = ComputeFinal(s);
139ea4ad6085a8661b5513c394316108c0ef26f3e7bAl Sutton      this->SetFinal(s, final);
1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return CacheImpl<A>::Final(s);
1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual void Expand(StateId s) = 0;
1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  size_t NumArcs(StateId s) {
1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (!HasArcs(s))
1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      Expand(s);
1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return CacheImpl<A>::NumArcs(s);
1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  size_t NumInputEpsilons(StateId s) {
1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (!HasArcs(s))
1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      Expand(s);
1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return CacheImpl<A>::NumInputEpsilons(s);
1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  size_t NumOutputEpsilons(StateId s) {
1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (!HasArcs(s))
1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      Expand(s);
1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return CacheImpl<A>::NumOutputEpsilons(s);
1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  void InitArcIterator(StateId s, ArcIteratorData<A> *data) {
1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (!HasArcs(s))
1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      Expand(s);
1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    CacheImpl<A>::InitArcIterator(s, data);
1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Access to flags encoding compose options/optimizations etc.  (for
1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // debugging).
1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual uint64 ComposeFlags() const = 0;
1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project protected:
1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual StateId ComputeStart() = 0;
1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual Weight ComputeFinal(StateId s) = 0;
1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  const Fst<A> *fst1_;            // first input Fst
1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  const Fst<A> *fst2_;            // second input Fst
1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project};
1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The following class encapsulates implementation-dependent details
1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// of state tuple lookup, i.e. a bijective mapping from triples of two
1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// FST states and an epsilon filter state to the corresponding state
1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// IDs of the fst resulting from composition. The mapping must
1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// implement the [] operator in the style of STL associative
1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// containers (map, hash_map), i.e. table[x] must return a reference
1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// to the value associated with x. If x is an unassigned tuple, the
1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// operator must automatically associate x with value 0.
1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// NB: "table[x] == 0" for unassigned tuples x is required by the
1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// following off-by-one device used in the implementation of
1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// ComposeFstImpl. The value stored in the table is equal to tuple ID
1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// plus one, i.e. it is always a strictly positive number. Therefore,
1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// table[x] is equal to 0 if and only if x is an unassigned tuple (in
1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// which the algorithm assigns a new ID to x, and sets table[x] -
1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// stored in a reference - to "new ID + 1"). This form of lookup is
1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// more efficient than calling "find(x)" and "insert(make_pair(x, new
2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// ID))" if x is an unassigned tuple.
2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The generic implementation is a wrapper around a hash_map.
2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A, uint64 T>
2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ComposeStateTable {
2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public:
2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef typename A::StateId StateId;
2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  struct StateTuple {
2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateTuple() {}
2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateTuple(StateId s1, StateId s2, int f)
2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        : state_id1(s1), state_id2(s2), filt(f) {}
2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateId state_id1;  // state Id on fst1
2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateId state_id2;  // state Id on fst2
2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    int filt;           // epsilon filter state
2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  };
2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  ComposeStateTable() {
2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateTuple empty_tuple(kNoStateId, kNoStateId, 0);
2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // NB: if 'tuple' is not in 'table_', the pair (tuple, StateId()) is
2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // inserted into 'table_' (standard STL container semantics). Since
2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // StateId is a built-in type, the explicit default constructor call
2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // StateId() returns 0.
2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  StateId &operator[](const StateTuple &tuple) {
2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return table_[tuple];
2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private:
2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Comparison object for hashing StateTuple(s).
2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  class StateTupleEqual {
2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project   public:
2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    bool operator()(const StateTuple& x, const StateTuple& y) const {
2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      return x.state_id1 == y.state_id1 &&
2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project             x.state_id2 == y.state_id2 &&
2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project             x.filt == y.filt;
2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  };
2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  static const int kPrime0 = 7853;
2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  static const int kPrime1 = 7867;
2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Hash function for StateTuple to Fst states.
2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  class StateTupleKey {
2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project   public:
2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    size_t operator()(const StateTuple& x) const {
2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      return static_cast<size_t>(x.state_id1 +
2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                                 x.state_id2 * kPrime0 +
2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                                 x.filt * kPrime1);
2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  };
2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Lookup table mapping state tuples to state IDs.
25473018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers  typedef std::unordered_map<StateTuple, StateId, StateTupleKey,
25573018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers                             StateTupleEqual> StateTable;
2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Actual table data.
2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  StateTable table_;
2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  DISALLOW_EVIL_CONSTRUCTORS(ComposeStateTable);
2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project};
2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
2634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// State tuple lookup table for the composition of a string FST with a
2644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// deterministic FST.  The class maps state tuples to their unique IDs
2654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// (i.e. states of the ComposeFst). Main optimization: due to the
2664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1-to-1 correspondence between the states of the input string FST
2674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// and those of the resulting (string) FST, a state tuple (s1, s2) is
2684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// simply mapped to StateId s1. Hence, we use an STL vector as a
2694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// lookup table. Template argument Fst1IsString specifies which FST is
2704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// a string (this determines whether or not we index the lookup table
2714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// by the first or by the second state).
2724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A, bool Fst1IsString>
2734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StringDetComposeStateTable {
2744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public:
2754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef typename A::StateId StateId;
2764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
2774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  struct StateTuple {
2784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    typedef typename A::StateId StateId;
2794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateTuple() {}
2804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateTuple(StateId s1, StateId s2, int /* f */)
2814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        : state_id1(s1), state_id2(s2) {}
2824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateId state_id1;  // state Id on fst1
2834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateId state_id2;  // state Id on fst2
2844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    static const int filt = 0;  // 'fake' epsilon filter - only needed
2854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                                // for API compatibility
2864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  };
2874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
2884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  StringDetComposeStateTable() {}
2894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
2904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Subscript operator. Behaves in a way similar to its map/hash_map
2914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // counterpart, i.e. returns a reference to the value associated
2924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // with 'tuple', inserting a 0 value if 'tuple' is unassigned.
2934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  StateId &operator[](const StateTuple &tuple) {
2944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateId index = Fst1IsString ? tuple.state_id1 : tuple.state_id2;
2954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (index >= (StateId)data_.size()) {
2964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      // NB: all values in [old_size; index] are initialized to 0.
2974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      data_.resize(index + 1);
2984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
2994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return data_[index];
3004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
3014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
3024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private:
3034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  vector<StateId> data_;
3044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
3054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  DISALLOW_EVIL_CONSTRUCTORS(StringDetComposeStateTable);
3064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project};
3074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
3084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
3094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specializations of ComposeStateTable for the string/det case.
3104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Both inherit from StringDetComposeStateTable.
3114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A>
3124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ComposeStateTable<A, COMPOSE_FST1_STRING | COMPOSE_FST2_DET>
3134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    : public StringDetComposeStateTable<A, true> { };
3144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
3154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A>
3164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ComposeStateTable<A, COMPOSE_FST2_STRING | COMPOSE_FST1_DET>
3174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    : public StringDetComposeStateTable<A, false> { };
3184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
3194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
3204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Parameterized implementation of FST composition for a pair of FSTs
3214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// matching the property bit vector T. If possible,
3224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// instantiation-specific switches in the code are based on the values
3234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// of the bits in T, which are known at compile time, so unused code
3244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// should be optimized away by the compiler.
3254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A, uint64 T>
3264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ComposeFstImpl : public ComposeFstImplBase<A> {
3274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef typename A::StateId StateId;
3284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef typename A::Label   Label;
3294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef typename A::Weight  Weight;
3304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  using FstImpl<A>::SetType;
3314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  using FstImpl<A>::SetProperties;
3324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
3334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  enum FindType { FIND_INPUT  = 1,          // find input label on fst2
3344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                  FIND_OUTPUT = 2,          // find output label on fst1
3354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                  FIND_BOTH   = 3 };        // find choice state dependent
3364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
3374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef ComposeStateTable<A, T & COMPOSE_INTERNAL_MASK> StateTupleTable;
3384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef typename StateTupleTable::StateTuple StateTuple;
3394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
3404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public:
3414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  ComposeFstImpl(const Fst<A> &fst1,
3424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                 const Fst<A> &fst2,
3434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                 const CacheOptions &opts)
3444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      :ComposeFstImplBase<A>(fst1, fst2, opts) {
3454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
3464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    bool osorted = fst1.Properties(kOLabelSorted, false);
3474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    bool isorted = fst2.Properties(kILabelSorted, false);
3484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
3494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    switch (T & COMPOSE_SPECIAL_SYMBOLS) {
3504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      case COMPOSE_FST1_RHO:
3514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      case COMPOSE_FST1_PHI:
3524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      case COMPOSE_FST1_SIGMA:
3534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        if (!osorted || FLAGS_fst_verify_properties)
3544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          osorted = fst1.Properties(kOLabelSorted, true);
3554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        if (!osorted)
3564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          LOG(FATAL) << "ComposeFst: 1st argument not output label "
3574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                     << "sorted (special symbols present)";
3584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        break;
3594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      case COMPOSE_FST2_RHO:
3604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      case COMPOSE_FST2_PHI:
3614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      case COMPOSE_FST2_SIGMA:
3624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        if (!isorted || FLAGS_fst_verify_properties)
3634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          isorted = fst2.Properties(kILabelSorted, true);
3644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        if (!isorted)
3654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          LOG(FATAL) << "ComposeFst: 2nd argument not input label "
3664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                     << "sorted (special symbols present)";
3674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        break;
3684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      case 0:
36973018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers        if ((!isorted && !osorted) || FLAGS_fst_verify_properties) {
3704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          osorted = fst1.Properties(kOLabelSorted, true);
3714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          if (!osorted)
3724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project            isorted = fst2.Properties(kILabelSorted, true);
3734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        }
3744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        break;
3754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      default:
3764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        LOG(FATAL)
3774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          << "ComposeFst: More than one special symbol used in composition";
3784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
3794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
3804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (isorted && (T & COMPOSE_FST2_SIGMA)) {
3814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      find_type_ = FIND_INPUT;
3824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    } else if (osorted && (T & COMPOSE_FST1_SIGMA)) {
3834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      find_type_ = FIND_OUTPUT;
3844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    } else if (isorted && (T & COMPOSE_FST2_PHI)) {
3854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      find_type_ = FIND_INPUT;
3864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    } else if (osorted && (T & COMPOSE_FST1_PHI)) {
3874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      find_type_ = FIND_OUTPUT;
3884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    } else if (isorted && (T & COMPOSE_FST2_RHO)) {
3894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      find_type_ = FIND_INPUT;
3904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    } else if (osorted && (T & COMPOSE_FST1_RHO)) {
3914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      find_type_ = FIND_OUTPUT;
3924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    } else if (isorted && (T & COMPOSE_FST1_STRING)) {
3934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      find_type_ = FIND_INPUT;
3944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    } else if(osorted && (T & COMPOSE_FST2_STRING)) {
3954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      find_type_ = FIND_OUTPUT;
3964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    } else if (isorted && osorted) {
3974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      find_type_ = FIND_BOTH;
3984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    } else if (isorted) {
3994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      find_type_ = FIND_INPUT;
4004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    } else if (osorted) {
4014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      find_type_ = FIND_OUTPUT;
4024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    } else {
4034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      LOG(FATAL) << "ComposeFst: 1st argument not output label sorted "
4044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                 << "and 2nd argument is not input label sorted";
4054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
4064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
4074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
4084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Finds/creates an Fst state given a StateTuple.  Only creates a new
4094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // state if StateTuple is not found in the state hash.
4104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  //
4114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // The method exploits the following device: all pairs stored in the
4124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // associative container state_tuple_table_ are of the form (tuple,
4134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // id(tuple) + 1), i.e. state_tuple_table_[tuple] > 0 if tuple has
4144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // been stored previously. For unassigned tuples, the call to
4154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // state_tuple_table_[tuple] creates a new pair (tuple, 0). As a
4164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // result, state_tuple_table_[tuple] == 0 iff tuple is new.
4174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  StateId FindState(const StateTuple& tuple) {
4184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateId &assoc_value = state_tuple_table_[tuple];
4194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (assoc_value == 0) {  // tuple wasn't present in lookup table:
4204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                             // assign it a new ID.
4214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      state_tuples_.push_back(tuple);
4224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      assoc_value = state_tuples_.size();
4234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
4244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return assoc_value - 1;  // NB: assoc_value = ID + 1
4254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
4264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
4274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Generates arc for composition state s from matched input Fst arcs.
4284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  void AddArc(StateId s, const A &arca, const A &arcb, int f,
4294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              bool find_input) {
4304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    A arc;
4314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (find_input) {
4324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      arc.ilabel = arcb.ilabel;
4334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      arc.olabel = arca.olabel;
4344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      arc.weight = Times(arcb.weight, arca.weight);
4354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      StateTuple tuple(arcb.nextstate, arca.nextstate, f);
4364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      arc.nextstate = FindState(tuple);
4374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    } else {
4384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      arc.ilabel = arca.ilabel;
4394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      arc.olabel = arcb.olabel;
4404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      arc.weight = Times(arca.weight, arcb.weight);
4414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      StateTuple tuple(arca.nextstate, arcb.nextstate, f);
4424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      arc.nextstate = FindState(tuple);
4434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
4444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    CacheImpl<A>::AddArc(s, arc);
4454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
4464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
4474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Arranges it so that the first arg to OrderedExpand is the Fst
4484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // that will be passed to FindLabel.
4494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  void Expand(StateId s) {
4504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateTuple &tuple = state_tuples_[s];
4514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateId s1 = tuple.state_id1;
4524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateId s2 = tuple.state_id2;
4534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    int f = tuple.filt;
4544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (find_type_ == FIND_INPUT)
4554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      OrderedExpand(s, ComposeFstImplBase<A>::fst2_, s2,
4564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                    ComposeFstImplBase<A>::fst1_, s1, f, true);
4574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    else
4584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      OrderedExpand(s, ComposeFstImplBase<A>::fst1_, s1,
4594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                    ComposeFstImplBase<A>::fst2_, s2, f, false);
4604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
4614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
4624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Access to flags encoding compose options/optimizations etc.  (for
4634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // debugging).
4644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual uint64 ComposeFlags() const { return T; }
4654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
4664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private:
4674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // This does that actual matching of labels in the composition. The
4684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // arguments are ordered so FindLabel is called with state SA of
4694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // FSTA for each arc leaving state SB of FSTB. The FIND_INPUT arg
4704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // determines whether the input or output label of arcs at SB is
4714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // the one to match on.
4724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  void OrderedExpand(StateId s, const Fst<A> *fsta, StateId sa,
4734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                     const Fst<A> *fstb, StateId sb, int f, bool find_input) {
4744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
4754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    size_t numarcsa = fsta->NumArcs(sa);
4764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    size_t numepsa = find_input ? fsta->NumInputEpsilons(sa) :
4774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                     fsta->NumOutputEpsilons(sa);
4784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    bool finala = fsta->Final(sa) != Weight::Zero();
4794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    ArcIterator< Fst<A> > aitera(*fsta, sa);
4804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    // First handle special epsilons and sigmas on FSTA
4814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    for (; !aitera.Done(); aitera.Next()) {
4824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      const A &arca = aitera.Value();
4834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      Label match_labela = find_input ? arca.ilabel : arca.olabel;
4844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      if (match_labela > 0) {
4854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        break;
4864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      }
4874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      if ((T & COMPOSE_SIGMA) != 0 &&  match_labela == kSigmaLabel) {
4884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        // Found a sigma? Match it against all (non-special) symbols
4894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        // on side b.
4904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        for (ArcIterator< Fst<A> > aiterb(*fstb, sb);
4914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project             !aiterb.Done();
4924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project             aiterb.Next()) {
4934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          const A &arcb = aiterb.Value();
4944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          Label labelb = find_input ? arcb.olabel : arcb.ilabel;
4954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          if (labelb <= 0) continue;
4964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          AddArc(s, arca, arcb, 0, find_input);
4974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        }
4984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      } else if (f == 0 && match_labela == 0) {
4994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        A earcb(0, 0, Weight::One(), sb);
5004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        AddArc(s, arca, earcb, 0, find_input);  // move forward on epsilon
5014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      }
5024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
5034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    // Next handle non-epsilon matches, rho labels, and epsilons on FSTB
5044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    for (ArcIterator< Fst<A> > aiterb(*fstb, sb);
5054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project         !aiterb.Done();
5064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project         aiterb.Next()) {
5074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      const A &arcb = aiterb.Value();
5084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      Label match_labelb = find_input ? arcb.olabel : arcb.ilabel;
5094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      if (match_labelb) {  // Consider non-epsilon match
5104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        if (FindLabel(&aitera, numarcsa, match_labelb, find_input)) {
5114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          for (; !aitera.Done(); aitera.Next()) {
5124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project            const A &arca = aitera.Value();
5134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project            Label match_labela = find_input ? arca.ilabel : arca.olabel;
5144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project            if (match_labela != match_labelb)
5154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              break;
5164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project            AddArc(s, arca, arcb, 0, find_input);  // move forward on match
5174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          }
5184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        } else if ((T & COMPOSE_SPECIAL_SYMBOLS) != 0) {
5194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          // If there is no transition labelled 'match_labelb' in
5204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          // fsta, try matching 'match_labelb' against special symbols
5214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          // (Phi, Rho,...).
5224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          for (aitera.Reset(); !aitera.Done(); aitera.Next()) {
5234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project            A arca = aitera.Value();
5244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project            Label labela = find_input ? arca.ilabel : arca.olabel;
5254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project            if (labela >= 0) {
5264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              break;
5274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project            } else if (((T & COMPOSE_PHI) != 0) && (labela == kPhiLabel)) {
5284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              // Case 1: if a failure transition exists, follow its
5294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              // transitive closure until a) a transition labelled
5304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              // 'match_labelb' is found, or b) the initial state of
5314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              // fsta is reached.
5324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
5334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              StateId sf = sa;  // Start of current failure transition.
5344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              while (labela == kPhiLabel && sf != arca.nextstate) {
5354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                sf = arca.nextstate;
5364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
5374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                size_t numarcsf = fsta->NumArcs(sf);
5384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                ArcIterator< Fst<A> > aiterf(*fsta, sf);
5394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                if (FindLabel(&aiterf, numarcsf, match_labelb, find_input)) {
5404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                  // Sub-case 1a: there exists a transition starting
5414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                  // in sf and consuming symbol 'match_labelb'.
5424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                  AddArc(s, aiterf.Value(), arcb, 0, find_input);
5434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                  break;
5444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                } else {
5454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                  // No transition labelled 'match_labelb' found: try
5464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                  // next failure transition (starting at 'sf').
5474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                  for (aiterf.Reset(); !aiterf.Done(); aiterf.Next()) {
5484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                    arca = aiterf.Value();
5494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                    labela = find_input ? arca.ilabel : arca.olabel;
5504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                    if (labela >= kPhiLabel) break;
5514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                  }
5524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                }
5534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              }
5544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              if (labela == kPhiLabel && sf == arca.nextstate) {
5554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                // Sub-case 1b: failure transitions lead to start
5564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                // state without finding a matching
5574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                // transition. Therefore, we generate a loop in start
5584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                // state of fsta.
5594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                A loop(match_labelb, match_labelb, Weight::One(), sf);
5604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                AddArc(s, loop, arcb, 0, find_input);
5614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              }
5624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project            } else if (((T & COMPOSE_RHO) != 0) && (labela == kRhoLabel)) {
5634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              // Case 2: 'match_labelb' can be matched against a
5644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              // "rest" (rho) label in fsta.
5654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              if (find_input) {
5664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                arca.ilabel = match_labelb;
5674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                if (arca.olabel == kRhoLabel)
5684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                  arca.olabel = match_labelb;
5694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              } else {
5704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                arca.olabel = match_labelb;
5714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                if (arca.ilabel == kRhoLabel)
5724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                  arca.ilabel = match_labelb;
5734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              }
5744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project              AddArc(s, arca, arcb, 0, find_input);  // move fwd on match
5754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project            }
5764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          }
5774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        }
5784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      } else if (numepsa != numarcsa || finala) {  // Handle FSTB epsilon
5794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        A earca(0, 0, Weight::One(), sa);
5804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        AddArc(s, earca, arcb, numepsa > 0, find_input);  // move on epsilon
5814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      }
5824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
583ea4ad6085a8661b5513c394316108c0ef26f3e7bAl Sutton    this->SetArcs(s);
5844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project   }
5854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
5864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
5874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Finds matches to MATCH_LABEL in arcs given by AITER
5884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // using FIND_INPUT to determine whether to look on input or output.
5894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  bool FindLabel(ArcIterator< Fst<A> > *aiter, size_t numarcs,
5904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                 Label match_label, bool find_input) {
5914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    // binary search for match
5924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    size_t low = 0;
5934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    size_t high = numarcs;
5944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    while (low < high) {
5954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      size_t mid = (low + high) / 2;
5964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      aiter->Seek(mid);
5974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      Label label = find_input ?
5984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                    aiter->Value().ilabel : aiter->Value().olabel;
5994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      if (label > match_label) {
6004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        high = mid;
6014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      } else if (label < match_label) {
6024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        low = mid + 1;
6034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      } else {
6044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        // find first matching label (when non-determinism)
6054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        for (size_t i = mid; i > low; --i) {
6064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          aiter->Seek(i - 1);
6074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          label = find_input ? aiter->Value().ilabel : aiter->Value().olabel;
6084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          if (label != match_label) {
6094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project            aiter->Seek(i);
6104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project            return true;
6114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          }
6124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        }
6134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        return true;
6144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      }
6154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
6164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return false;
6174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
6184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
6194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  StateId ComputeStart() {
6204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateId s1 = ComposeFstImplBase<A>::fst1_->Start();
6214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateId s2 = ComposeFstImplBase<A>::fst2_->Start();
6224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (s1 == kNoStateId || s2 == kNoStateId)
6234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      return kNoStateId;
6244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateTuple tuple(s1, s2, 0);
6254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return FindState(tuple);
6264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
6274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
6284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  Weight ComputeFinal(StateId s) {
6294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    StateTuple &tuple = state_tuples_[s];
6304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    Weight final = Times(ComposeFstImplBase<A>::fst1_->Final(tuple.state_id1),
6314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                         ComposeFstImplBase<A>::fst2_->Final(tuple.state_id2));
6324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return final;
6334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
6344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
6354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
6364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  FindType find_type_;            // find label on which side?
6374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
6384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Maps from StateId to StateTuple.
6394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  vector<StateTuple> state_tuples_;
6404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
6414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Maps from StateTuple to StateId.
6424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  StateTupleTable state_tuple_table_;
6434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
6444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  DISALLOW_EVIL_CONSTRUCTORS(ComposeFstImpl);
6454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project};
6464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
6474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
6484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes the composition of two transducers. This version is a
6494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// delayed Fst. If FST1 transduces string x to y with weight a and FST2
6504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// transduces y to z with weight b, then their composition transduces
6514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// string x to z with weight Times(x, z).
6524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
6534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The output labels of the first transducer or the input labels of
6544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the second transducer must be sorted.  The weights need to form a
6554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// commutative semiring (valid for TropicalWeight and LogWeight).
6564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
6574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity:
6584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Assuming the first FST is unsorted and the second is sorted:
6594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: O(v1 v2 d1 (log d2 + m2)),
6604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(v1 v2)
6614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where vi = # of states visited, di = maximum out-degree, and mi the
6624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// maximum multiplicity of the states visited for the ith
6634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// FST. Constant time and space to visit an input state or arc is
6644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// assumed and exclusive of caching.
6654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
6664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Caveats:
6674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - ComposeFst does not trim its output (since it is a delayed operation).
6684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - The efficiency of composition can be strongly affected by several factors:
6694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//   - the choice of which tnansducer is sorted - prefer sorting the FST
6704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//     that has the greater average out-degree.
6714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//   - the amount of non-determinism
6724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//   - the presence and location of epsilon transitions - avoid epsilon
6734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//     transitions on the output side of the first transducer or
6744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//     the input side of the second transducer or prefer placing
6754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//     them later in a path since they delay matching and can
6764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//     introduce non-coaccessible states and transitions.
6774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A>
6784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ComposeFst : public Fst<A> {
6794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public:
6804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  friend class ArcIterator< ComposeFst<A> >;
6814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  friend class CacheStateIterator< ComposeFst<A> >;
6824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  friend class CacheArcIterator< ComposeFst<A> >;
6834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
6844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef A Arc;
6854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef typename A::Weight Weight;
6864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef typename A::StateId StateId;
6874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef CacheState<A> State;
6884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
6894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  ComposeFst(const Fst<A> &fst1, const Fst<A> &fst2)
6904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      : impl_(Init(fst1, fst2, ComposeFstOptions<>())) { }
6914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
6924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  template <uint64 T>
6934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  ComposeFst(const Fst<A> &fst1,
6944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project             const Fst<A> &fst2,
6954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project             const ComposeFstOptions<T> &opts)
6964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      : impl_(Init(fst1, fst2, opts)) { }
6974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
6984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  ComposeFst(const ComposeFst<A> &fst) : Fst<A>(fst), impl_(fst.impl_) {
6994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    impl_->IncrRefCount();
7004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
7014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual ~ComposeFst() { if (!impl_->DecrRefCount()) delete impl_;  }
7034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual StateId Start() const { return impl_->Start(); }
7054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual Weight Final(StateId s) const { return impl_->Final(s); }
7074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual size_t NumArcs(StateId s) const { return impl_->NumArcs(s); }
7094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual size_t NumInputEpsilons(StateId s) const {
7114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return impl_->NumInputEpsilons(s);
7124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
7134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual size_t NumOutputEpsilons(StateId s) const {
7154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return impl_->NumOutputEpsilons(s);
7164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
7174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual uint64 Properties(uint64 mask, bool test) const {
7194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (test) {
7204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      uint64 known, test = TestProperties(*this, mask, &known);
7214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      impl_->SetProperties(test, known);
7224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      return test & mask;
7234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    } else {
7244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      return impl_->Properties(mask);
7254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
7264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
7274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual const string& Type() const { return impl_->Type(); }
7294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual ComposeFst<A> *Copy() const {
7314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return new ComposeFst<A>(*this);
7324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
7334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual const SymbolTable* InputSymbols() const {
7354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return impl_->InputSymbols();
7364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
7374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual const SymbolTable* OutputSymbols() const {
7394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return impl_->OutputSymbols();
7404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
7414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual inline void InitStateIterator(StateIteratorData<A> *data) const;
7434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const {
7454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    impl_->InitArcIterator(s, data);
7464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
7474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Access to flags encoding compose options/optimizations etc.  (for
7494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // debugging).
7504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  uint64 ComposeFlags() const { return impl_->ComposeFlags(); }
7514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project protected:
7534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  ComposeFstImplBase<A> *Impl() { return impl_; }
7544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private:
7564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  ComposeFstImplBase<A> *impl_;
7574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Auxiliary method encapsulating the creation of a ComposeFst
7594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // implementation that is appropriate for the properties of fst1 and
7604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // fst2.
7614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  template <uint64 T>
7624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  static ComposeFstImplBase<A> *Init(
7634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      const Fst<A> &fst1,
7644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      const Fst<A> &fst2,
7654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      const ComposeFstOptions<T> &opts) {
7664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    // Filter for sort properties (forces a property check).
7684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    uint64 sort_props_mask = kILabelSorted | kOLabelSorted;
7694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    // Filter for optimization-related properties (does not force a
7704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    // property-check).
7714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    uint64 opt_props_mask =
7724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      kString | kIDeterministic | kODeterministic | kNoIEpsilons |
7734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      kNoOEpsilons;
7744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    uint64 props1 = fst1.Properties(sort_props_mask, true);
7764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    uint64 props2 = fst2.Properties(sort_props_mask, true);
7774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    props1 |= fst1.Properties(opt_props_mask, false);
7794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    props2 |= fst2.Properties(opt_props_mask, false);
7804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (!(Weight::Properties() & kCommutative)) {
7824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      props1 |= fst1.Properties(kUnweighted, true);
7834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      props2 |= fst2.Properties(kUnweighted, true);
7844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      if (!(props1 & kUnweighted) && !(props2 & kUnweighted))
7854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        LOG(FATAL) << "ComposeFst: Weight needs to be a commutative semiring: "
7864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project                   << Weight::Type();
7874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
7884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    // Case 1: flag COMPOSE_GENERIC disables optimizations.
7904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (T & COMPOSE_GENERIC) {
7914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      return new ComposeFstImpl<A, T>(fst1, fst2, opts);
7924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
7934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    const uint64 kStringDetOptProps =
7954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      kIDeterministic | kILabelSorted | kNoIEpsilons;
7964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    const uint64 kDetStringOptProps =
7974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      kODeterministic | kOLabelSorted | kNoOEpsilons;
7984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
7994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    // Case 2: fst1 is a string, fst2 is deterministic and epsilon-free.
8004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if ((props1 & kString) &&
8014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        !(T & (COMPOSE_FST1_RHO | COMPOSE_FST1_PHI | COMPOSE_FST1_SIGMA)) &&
8024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        ((props2 & kStringDetOptProps) == kStringDetOptProps)) {
8034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      return new ComposeFstImpl<A, T | COMPOSE_FST1_STRING | COMPOSE_FST2_DET>(
8044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          fst1, fst2, opts);
8054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
8064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    // Case 3: fst1 is deterministic and epsilon-free, fst2 is string.
8074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if ((props2 & kString) &&
8084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        !(T & (COMPOSE_FST1_RHO | COMPOSE_FST1_PHI | COMPOSE_FST1_SIGMA)) &&
8094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        ((props1 & kDetStringOptProps) == kDetStringOptProps)) {
8104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      return new ComposeFstImpl<A, T | COMPOSE_FST2_STRING | COMPOSE_FST1_DET>(
8114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project          fst1, fst2, opts);
8124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
8134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    // Default case: no optimizations.
8154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return new ComposeFstImpl<A, T>(fst1, fst2, opts);
8164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
8174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  void operator=(const ComposeFst<A> &fst);  // disallow
8194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project};
8204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for ComposeFst.
8234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class A>
8244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StateIterator< ComposeFst<A> >
8254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    : public CacheStateIterator< ComposeFst<A> > {
8264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public:
8274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  explicit StateIterator(const ComposeFst<A> &fst)
8284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      : CacheStateIterator< ComposeFst<A> >(fst) {}
8294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project};
8304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for ComposeFst.
8334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A>
8344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcIterator< ComposeFst<A> >
8354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    : public CacheArcIterator< ComposeFst<A> > {
8364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public:
8374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  typedef typename A::StateId StateId;
8384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  ArcIterator(const ComposeFst<A> &fst, StateId s)
8404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      : CacheArcIterator< ComposeFst<A> >(fst, s) {
8414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (!fst.impl_->HasArcs(s))
8424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      fst.impl_->Expand(s);
8434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
8444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private:
8464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  DISALLOW_EVIL_CONSTRUCTORS(ArcIterator);
8474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project};
8484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> inline
8504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid ComposeFst<A>::InitStateIterator(StateIteratorData<A> *data) const {
8514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  data->base = new StateIterator< ComposeFst<A> >(*this);
8524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}
8534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Useful alias when using StdArc.
8554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef ComposeFst<StdArc> StdComposeFst;
8564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct ComposeOptions {
8594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  bool connect;  // Connect output
8604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  ComposeOptions(bool c) : connect(c) {}
8624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  ComposeOptions() : connect(true) { }
8634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project};
8644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
8664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes the composition of two transducers. This version writes
8674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the composed FST into a MurableFst. If FST1 transduces string x to
8684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// y with weight a and FST2 transduces y to z with weight b, then
8694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// their composition transduces string x to z with weight
8704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Times(x, z).
8714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
8724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The output labels of the first transducer or the input labels of
8734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the second transducer must be sorted.  The weights need to form a
8744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// commutative semiring (valid for TropicalWeight and LogWeight).
8754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
8764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity:
8774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Assuming the first FST is unsorted and the second is sorted:
8784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: O(V1 V2 D1 (log D2 + M2)),
8794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(V1 V2 D1 M2)
8804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where Vi = # of states, Di = maximum out-degree, and Mi is
8814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the maximum multiplicity for the ith FST.
8824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
8834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Caveats:
8844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Compose trims its output.
8854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - The efficiency of composition can be strongly affected by several factors:
8864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//   - the choice of which tnansducer is sorted - prefer sorting the FST
8874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//     that has the greater average out-degree.
8884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//   - the amount of non-determinism
8894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//   - the presence and location of epsilon transitions - avoid epsilon
8904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//     transitions on the output side of the first transducer or
8914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//     the input side of the second transducer or prefer placing
8924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//     them later in a path since they delay matching and can
8934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//     introduce non-coaccessible states and transitions.
8944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc>
8954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Compose(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
8964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project             MutableFst<Arc> *ofst,
8974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project             const ComposeOptions &opts = ComposeOptions()) {
8984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  ComposeFstOptions<> nopts;
8994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  nopts.gc_limit = 0;  // Cache only the last state for fastest copy.
9004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  *ofst = ComposeFst<Arc>(ifst1, ifst2, nopts);
9014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  if (opts.connect)
9024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    Connect(ofst);
9034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}
9044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
9054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}  // namespace fst
9064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
9074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif  // FST_LIB_COMPOSE_H__
908