// compact-fst.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: allauzen@google.com (Cyril Allauzen)
//
// \file
// FST Class for memory-efficient representation of common types of
// FSTs: linear automata, acceptors, unweighted FSTs, ...
#ifndef FST_LIB_COMPACT_FST_H__
#define FST_LIB_COMPACT_FST_H__
#include <iterator>
#include <utility>
using std::pair; using std::make_pair;
#include <vector>
using std::vector;
#include <fst/cache.h>
#include <fst/expanded-fst.h>
#include <fst/fst-decl.h> // For optional argument declarations
#include <fst/mapped-file.h>
#include <fst/matcher.h>
#include <fst/test-properties.h>
#include <fst/util.h>
namespace fst {
struct CompactFstOptions : public CacheOptions {
// CompactFst default caching behaviour is to do no caching. Most
// compactors are cheap and therefore we save memory by not doing
// caching.
CompactFstOptions() : CacheOptions(true, 0) {}
CompactFstOptions(const CacheOptions &opts) : CacheOptions(opts) {}
};
// Compactor Interface - class determinies how arcs and final weights
// are compacted and expanded.
//
// Final weights are treated as transitions to the superfinal state,
// i.e. ilabel = olabel = kNoLabel and nextstate = kNoStateId.
//
// There are two types of compactors:
//
// * Fixed out-degree compactors: 'compactor.Size()' returns a
// positive integer 's'. An FST can be compacted by this compactor
// only if each state has exactly 's' outgoing transitions (counting a
// non-Zero() final weight as a transition). A typical example is a
// compactor for string FSTs, i.e. 's == 1'.
//
// * Variable out-degree compactors: 'compactor.Size() == -1'. There
// are no out-degree restrictions for these compactors.
//
//
// class Compactor {
// public:
// // Element is the type of the compacted transitions.
// typedef ... Element;
// // Return the compacted representation of a transition 'arc'
// // at a state 's'.
// Element Compact(StateId s, const Arc &arc);
// // Return the transition at state 's' represented by the compacted
// // transition 'e'.
// Arc Expand(StateId s, const Element &e);
// // Return -1 for variable out-degree compactors, and the mandatory
// // out-degree otherwise.
// ssize_t Size();
// // Test whether 'fst' can be compacted by this compactor.
// bool Compatible(const Fst<A> &fst);
// // Return the properties that are always true for an fst
// // compacted using this compactor
// uint64 Properties();
// // Return a string identifying the type of compactor.
// static const string &Type();
// // Write a compactor to a file.
// bool Write(ostream &strm);
// // Read a compactor from a file.
// static Compactor *Read(istream &strm);
// // Default constructor (optional, see comment below).
// Compactor();
// };
//
// The default constructor is only required for FST_REGISTER to work
// (i.e. enabling Convert() and the command-line utilities to work
// with this new compactor). However, a default constructor always
// needs to be specify for this code to compile, but one can have it
// simply raised an error when called:
//
// Compactor::Compactor() {
// FSTERROR() << "Compactor: no default constructor";
// }
// Implementation data for Compact Fst, which can shared between otherwise
// independent copies.
//
// The implementation contains two arrays: 'states_' and 'compacts_'.
//
// For fixed out-degree compactors, the 'states_' array is unallocated.
// The 'compacts_' contains the compacted transitions. Its size is
// 'ncompacts_'. The outgoing transitions at a given state are s