// 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: dbikel@google.com (Dan Bikel)
//
// An \ref Fst implementation that allows non-destructive edit operations on an
// existing fst.
#ifndef FST_LIB_EDIT_FST_H_
#define FST_LIB_EDIT_FST_H_
#include <vector>
using std::vector;
#include <fst/cache.h>
#include <tr1/unordered_map>
using std::tr1::unordered_map;
using std::tr1::unordered_multimap;
namespace fst {
// The EditFst class enables non-destructive edit operations on a wrapped
// ExpandedFst. The implementation uses copy-on-write semantics at the node
// level: if a user has an underlying fst on which he or she wants to perform a
// relatively small number of edits (read: mutations), then this implementation
// will copy the edited node to an internal MutableFst and perform any edits in
// situ on that copied node. This class supports all the methods of MutableFst
// except for DeleteStates(const vector<StateId> &); thus, new nodes may also be
// added, and one may add transitions from existing nodes of the wrapped fst to
// new nodes.
//
// N.B.: The documentation for Fst::Copy(true) says that its behavior is
// undefined if invoked on an fst that has already been accessed. This class
// requires that the Fst implementation it wraps provides consistent, reliable
// behavior when its Copy(true) method is invoked, where consistent means
// the graph structure, graph properties and state numbering and do not change.
// VectorFst and CompactFst, for example, are both well-behaved in this regard.
// The EditFstData class is a container for all mutable data for EditFstImpl;
// also, this class provides most of the actual implementation of what EditFst
// does (that is, most of EditFstImpl's methods delegate to methods in this, the
// EditFstData class). Instances of this class are reference-counted and can be
// shared between otherwise independent EditFstImpl instances. This scheme
// allows EditFstImpl to implement the thread-safe, copy-on-write semantics
// required by Fst::Copy(true).
//
// template parameters:
// A the type of arc to use
// WrappedFstT the type of fst wrapped by the EditFst instance that
// this EditFstData instance is backing
// MutableFstT the type of mutable fst to use internally for edited states;
// crucially, MutableFstT::Copy(false) *must* yield an fst that is
// thread-safe for reading (VectorFst, for example, has this property)
template <typename A,
typename WrappedFstT = ExpandedFst<A>,
typename MutableFstT = VectorFst<A> >
class EditFstData {
public:
typedef A Arc;
typedef typename A::Weight Weight;
typedef typename A::StateId StateId;
typedef typename unordered_map<StateId, StateId>::const_iterator
IdMapIterator;
typedef typename unordered_map<StateId, Weight>::const_iterator
FinalWeightIterator;
EditFstData() : num_new_states_(0) {
SetEmptyAndDeleteKeysForInternalMaps();
}
EditFstData(const EditFstData &other) :
edits_(other.edits_),
external_to_internal_ids_(other.external_to_internal_ids_),
edited_final_weights_(other.edited_final_weights_),
num_new_states_(other.num_new_states_) {
}
~EditFstData() {
}
static EditFstData<A, WrappedFstT, MutableFstT> *Read(istream &strm,
const FstReadOptions &opts);
bool Write(ostream &strm, const FstWriteOptions &opts) const {
// Serialize all private data members of this class.
FstWriteOptions edits_opts(opts);
edits_opts.write_header = true; // Force writing contained header.
edits_.Write(strm, edits_opts);
WriteType(strm, external_to_internal_ids_);
WriteType(strm, edited_final_weights_);
WriteType(strm, num_new_states_);
if (!strm) {
LOG(ERROR) << "EditFstData::Write: write failed: " << opts.source;
return false;
}
return true;
}
int RefCount() const { return ref_count_.count(); }
int IncrRefCount() { return ref_count_.Incr(); }
int DecrRefCount() { return ref_count_.Decr(); }
StateId NumNewStates() const {
return num_new_states_;
}
// accessor methods for the fst holding edited states
StateId EditedStart() const {
return edits_.Start();
}
Weight Final(StateId s, const WrappedFstT *wrapped) const {
FinalWeightIterator final_weight_it = GetFinalWeightIterator(s);
if (final_weight_it == NotInFinalWeightMap()) {
IdMapIterator it = GetEditedIdMapIterator(s);
return it == NotInEditedMap() ?
wrapped->Final(s) : edits_.Final(it->second);
}
else {
return final_weight_it->second;
}
}
size_t NumArcs(StateId s, const WrappedFstT *wrapped) const {
IdMapIterator it = GetEditedIdMapIterator(s);
return it == NotInEditedMap() ?
wrapped->NumArcs(s) : edits_.NumArcs(it->second);
}
size_t NumInputEpsilons(StateId s, const WrappedFstT *wrapped) const {
IdMapIterator it = GetEditedIdMapIterator(s);
return it == NotInEditedMap() ?
wrapped->NumInputEpsilons(s) :
edits_.NumInputEpsilons(it->second);
}
size_t NumOutputEpsilons(StateId s, const WrappedFstT *wrapped) const {
IdMapIterator it = GetEditedIdMapIterator(s);
return it == NotInEditedMap() ?
wrapped->NumOutputEpsilons(s) :
edits_.NumOutputEpsilons(it->second);
}
void SetEditedProperties(uint64 props, uint64 mask) {
edits_.SetProperties(props, mask);
}
// non-const MutableFst operations
// Sets the start state for this fst.
void SetStart(StateId s) {
edits_.SetStart(s);
}
// Sets the final state for this fst.
Weight SetFinal(StateId s, Weight w, const WrappedFstT *wrapped) {
Weight old_weight = Final(s, wrapped);
IdMapIterator it = GetEditedIdMapIterator(s);
// if we haven't already edited state s, don't add it to edited_ (which can
// be expensive if s has many transitions); just use the
// edited_final_weights_ map
if (it == NotInEditedMap()) {
edited_final_weights_[s] = w;
}
else {
edits_.SetFinal(GetEditableInternalId(s, wrapped), w);
}
return old_weight;
}
// Adds a new state to this fst, initially with no arcs.
StateId AddState(StateId curr_num_states) {
StateId internal_state_id = edits_.AddState();
StateId external_state_id = curr_num_states;
external_to_internal_ids_[external_state_id] = internal_state_id;
num_new_states_++;
return external_state_id;
}
// Adds the specified arc to the specified state of this fst.
const A *AddArc(StateId s, const Arc