// matcher.h
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright 2005-2010 Google, Inc.
// Author: riley@google.com (Michael Riley)
//
// \file
// Classes to allow matching labels leaving FST states.
#ifndef FST_LIB_MATCHER_H__
#define FST_LIB_MATCHER_H__
#include <algorithm>
#include <set>
#include <fst/mutable-fst.h> // for all internal FST accessors
namespace fst {
// MATCHERS - these can find and iterate through requested labels at
// FST states. In the simplest form, these are just some associative
// map or search keyed on labels. More generally, they may
// implement matching special labels that represent sets of labels
// such as 'sigma' (all), 'rho' (rest), or 'phi' (fail).
// The Matcher interface is:
//
// template <class F>
// class Matcher {
// public:
// typedef F FST;
// typedef F::Arc Arc;
// typedef typename Arc::StateId StateId;
// typedef typename Arc::Label Label;
// typedef typename Arc::Weight Weight;
//
// // Required constructors.
// Matcher(const F &fst, MatchType type);
// // If safe=true, the copy is thread-safe. See Fst<>::Copy()
// // for further doc.
// Matcher(const Matcher &matcher, bool safe = false);
//
// // If safe=true, the copy is thread-safe. See Fst<>::Copy()
// // for further doc.
// Matcher<F> *Copy(bool safe = false) const;
//
// // Returns the match type that can be provided (depending on
// // compatibility of the input FST). It is either
// // the requested match type, MATCH_NONE, or MATCH_UNKNOWN.
// // If 'test' is false, a constant time test is performed, but
// // MATCH_UNKNOWN may be returned. If 'test' is true,
// // a definite answer is returned, but may involve more costly
// // computation (e.g., visiting the Fst).
// MatchType Type(bool test) const;
// // Specifies the current state.
// void SetState(StateId s);
//
// // This finds matches to a label at the current state.
// // Returns true if a match found. kNoLabel matches any
// // 'non-consuming' transitions, e.g., epsilon transitions,
// // which do not require a matching symbol.
// bool Find(Label label);
// // These iterate through any matches found:
// bool Done() const; // No more matches.
// const A& Value() const; // Current arc (when !Done)
// void Next(); // Advance to next arc (when !Done)
// // Initially and after SetState() the iterator methods
// // have undefined behavior until Find() is called.
//
// // Return matcher FST.
// const F& GetFst() const;
// // This specifies the known Fst properties as viewed from this
// // matcher. It takes as argument the input Fst's known properties.
// uint64 Properties(uint64 props) const;
// };
//
// MATCHER FLAGS (see also kLookAheadFlags in lookahead-matcher.h)
//
// Matcher prefers being used as the matching side in composition.
const uint32 kPreferMatch = 0x00000001;
// Matcher needs to be used as the matching side in composition.
const uint32 kRequireMatch = 0x00000002;
// Flags used for basic matchers (see also lookahead.h).
const uint32 kMatcherFlags = kPreferMatch | kRequireMatch;
// Matcher interface, templated on the Arc definition; used
// for matcher specializations that are returned by the
// InitMatcher Fst method.
template <class A>
class MatcherBase {
public:
typedef A Arc;
typedef typename A::StateId StateId;
typedef typename A::Label Label;
typedef typename A::Weight Weight;
virtual ~MatcherBase() {}
virtual MatcherBase<A> *Copy(bool safe = false) const = 0;
virtual MatchType Type(bool test) const = 0;
void SetState(StateId s) { SetState_(s); }
bool Find(Label label) { return Find_(label); }
bool Done() const { return Done_(); }
const A& Value() const { return Value_(); }
void Next() { Next_(); }
virtual const Fst<A> &GetFst() const = 0;
virtual uint64 Properties(uint64 props) const = 0;
virtual uint32 Flags() const { return 0; }
private:
virtual void SetState_(StateId s) = 0;
virtual bool Find_(Label label) = 0;
virtual bool Done_() const = 0;
virtual const A& Value_() const = 0;
virtual void Next_() = 0;
};
// A matcher that expects sorted labels on the side to be matched.
// If match_type == MATCH_INPUT, epsilons match the implicit self loop
// Arc(kNoLabel, 0, Weight::One(), current_state) as well as any
// actual epsilon transitions. If match_type == MATCH_OUTPUT, then
// Arc(0, kNoLabel, Weight::One(), current_state) is instead matched.
template <class F>
class SortedMatcher : public MatcherBase<typename F::Arc> {
public:
typedef F FST;
typedef typename F::Arc Arc;
typedef typename Arc::StateId StateId;
typedef typename Arc::Label