// arc-map.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
// Class to map over/transform arcs e.g., change semirings or
// implement project/invert. Consider using when operation does
// not change the number of arcs (except possibly superfinal arcs).
#ifndef FST_LIB_ARC_MAP_H__
#define FST_LIB_ARC_MAP_H__
#include <tr1/unordered_map>
using std::tr1::unordered_map;
using std::tr1::unordered_multimap;
#include <string>
#include <utility>
using std::pair; using std::make_pair;
#include <fst/cache.h>
#include <fst/mutable-fst.h>
namespace fst {
// This determines how final weights are mapped.
enum MapFinalAction {
// A final weight is mapped into a final weight. An error
// is raised if this is not possible.
MAP_NO_SUPERFINAL,
// A final weight is mapped to an arc to the superfinal state
// when the result cannot be represented as a final weight.
// The superfinal state will be added only if it is needed.
MAP_ALLOW_SUPERFINAL,
// A final weight is mapped to an arc to the superfinal state
// unless the result can be represented as a final weight of weight
// Zero(). The superfinal state is always added (if the input is
// not the empty Fst).
MAP_REQUIRE_SUPERFINAL
};
// This determines how symbol tables are mapped.
enum MapSymbolsAction {
// Symbols should be cleared in the result by the map.
MAP_CLEAR_SYMBOLS,
// Symbols should be copied from the input FST by the map.
MAP_COPY_SYMBOLS,
// Symbols should not be modified in the result by the map itself.
// (They may set by the mapper).
MAP_NOOP_SYMBOLS
};
// ArcMapper Interface - class determinies how arcs and final weights
// are mapped. Useful for implementing operations that do not change
// the number of arcs (expect possibly superfinal arcs).
//
// class ArcMapper {
// public:
// typedef A FromArc;
// typedef B ToArc;
//
// // Maps an arc type A to arc type B.
// B operator()(const A &arc);
// // Specifies final action the mapper requires (see above).
// // The mapper will be passed final weights as arcs of the
// // form A(0, 0, weight, kNoStateId).
// MapFinalAction FinalAction() const;
// // Specifies input symbol table action the mapper requires (see above).
// MapSymbolsAction InputSymbolsAction() const;
// // Specifies output symbol table action the mapper requires (see above).
// MapSymbolsAction OutputSymbolsAction() const;
// // This specifies the known properties of an Fst mapped by this
// // mapper. It takes as argument the input Fst's known properties.
// uint64 Properties(uint64 props) const;
// };
//
// The ArcMap functions and classes below will use the FinalAction()
// method of the mapper to determine how to treat final weights,
// e.g. whether to add a superfinal state. They will use the Properties()
// method to set the result Fst properties.
//
// We include a various map versions below. One dimension of
// variation is whether the mapping mutates its input, writes to a
// new result Fst, or is an on-the-fly Fst. Another dimension is how
// we pass the mapper. We allow passing the mapper by pointer
// for cases that we need to change the state of the user's mapper.
// This is the case with the encode mapper, which is reused during
// decoding. We also include map versions that pass the mapper
// by value or const reference when this suffices.
// Maps an arc type A using a mapper function object C, passed
// by pointer. This version modifies its Fst input.
template<class A, class C>
void ArcMap(MutableFst<A> *fst, C* mapper) {
typedef typename A::StateId StateId;
typedef typename A::Weight Weight;
if (mapper->InputSymbolsAction() == MAP_CLEAR_SYMBOLS)
fst->SetInputSymbols(0);
if (mapper->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS)
fst->SetOutputSymbols(0);
if (fst->Start() == kNoStateId)
return;
uint64 props = fst->Properties(kFstProperties, false);
MapFinalAction final_action = mapper->FinalAction();
StateId superfinal = kNoStateId;
if (final_action == MAP_REQUIRE_SUPERFINAL) {
superfinal = fst->AddState();
fst->SetFinal(superfinal, Weight::One());
}
for (StateId s = 0; s < fst->NumStates(); ++s) {
for (MutableArcIterator< MutableFst<A> > aiter(fst, s);
!aiter.Done(); aiter.Next()) {
const A &arc = aiter.Value();
aiter.SetValue((*mapper)(arc));
}
switch (final_action) {
case MAP_NO_SUPERFINAL:
default: {
A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId));
if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
FSTERROR() << "ArcMap: non-zero arc labels for superfinal arc";
fst->SetProperties(kError, kError);
}
fst->SetFinal(s, final_arc.weight);
break;
}
case MAP_ALLOW_SUPERFINAL: {
if (s != superfinal) {
A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId));
if (final_arc.ilabel != 0 || final_arc.olabel != 0)