// string-weight.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
// String weight set and associated semiring operation definitions.
#ifndef FST_LIB_STRING_WEIGHT_H__
#define FST_LIB_STRING_WEIGHT_H__
#include <list>
#include <string>
#include <fst/product-weight.h>
#include <fst/weight.h>
namespace fst {
const int kStringInfinity = -1; // Label for the infinite string
const int kStringBad = -2; // Label for a non-string
const char kStringSeparator = '_'; // Label separator in strings
// Determines whether to use left or right string semiring. Includes
// restricted versions that signal an error if proper prefixes
// (suffixes) would otherwise be returned by Plus, useful with various
// algorithms that require functional transducer input with the
// string semirings.
enum StringType { STRING_LEFT = 0, STRING_RIGHT = 1 ,
STRING_LEFT_RESTRICT = 2, STRING_RIGHT_RESTRICT };
#define REVERSE_STRING_TYPE(S) \
((S) == STRING_LEFT ? STRING_RIGHT : \
((S) == STRING_RIGHT ? STRING_LEFT : \
((S) == STRING_LEFT_RESTRICT ? STRING_RIGHT_RESTRICT : \
STRING_LEFT_RESTRICT)))
template <typename L, StringType S = STRING_LEFT>
class StringWeight;
template <typename L, StringType S = STRING_LEFT>
class StringWeightIterator;
template <typename L, StringType S = STRING_LEFT>
class StringWeightReverseIterator;
template <typename L, StringType S>
bool operator==(const StringWeight<L, S> &, const StringWeight<L, S> &);
// String semiring: (longest_common_prefix/suffix, ., Infinity, Epsilon)
template <typename L, StringType S>
class StringWeight {
public:
typedef L Label;
typedef StringWeight<L, REVERSE_STRING_TYPE(S)> ReverseWeight;
friend class StringWeightIterator<L, S>;
friend class StringWeightReverseIterator<L, S>;
friend bool operator==<>(const StringWeight<L, S> &,
const StringWeight<L, S> &);
StringWeight() { Init(); }
template <typename Iter>
StringWeight(const Iter &begin, const Iter &end) {
Init();
for (Iter iter = begin; iter != end; ++iter)
PushBack(*iter);
}
explicit StringWeight(L l) { Init(); PushBack(l); }
static const StringWeight<L, S> &Zero() {
static const StringWeight<L, S> zero(kStringInfinity);
return zero;
}
static const StringWeight<L, S> &One() {
static const StringWeight<L, S> one;
return one;
}
static const StringWeight<L, S> &NoWeight() {
static const StringWeight<L, S> no_weight(kStringBad);
return no_weight;
}
static const string &Type() {
static const string type =
S == STRING_LEFT ? "string" :
(S == STRING_RIGHT ? "right_string" :
(S == STRING_LEFT_RESTRICT ? "restricted_string" :
"right_restricted_string"));
return type;
}
bool Member() const;
istream &Read(istream &strm);
ostream &Write(ostream &strm) const;
size_t Hash() const;
StringWeight<L, S> Quantize(float delta = kDelta) const {
return *this;
}
ReverseWeight Reverse() const;
static uint64 Properties() {
return (S == STRING_LEFT || S == STRING_LEFT_RESTRICT ?
kLeftSemiring : kRightSemiring) | kIdempotent;
}
// NB: This needs to be uncommented only if default fails for this impl.
// StringWeight<L, S> &operator=(const StringWeight<L, S> &w);
// These operations combined with the StringWeightIterator and
// StringWeightReverseIterator provide the access and mutation of
// the string internal elements.
// Common initializer among constructors.
void Init() { first_ = 0; }
// Clear existing StringWeight.
void Clear() { first_ = 0; rest_.clear(); }
size_t Size() const { return first_ ? rest_.size() + 1 : 0; }
void PushFront(L l) {
if (first_)
rest_.push_front(first_);
first_ = l;
}
void PushBack(L l) {
if (!first_)
first_ = l;
else
rest_.push_back(l);
}
private:
L first_; // first label in string (0 if empty)
list<L> rest_; // remaining labels in string
};
// Traverses string in forward direction.
template <typename L, StringType S>
class StringWeightIterator {
public:
explicit StringWeightIterator(const StringWeight<L, S>& w)
: first_(w.first_), rest_(w.rest_), init_(true),
iter_(rest_.begin()) {}
bool Done() const {
if (init_) return first_ == 0;
else return iter_ == rest_.end();
}
const L& Value() const { return init_ ? first_ : *iter_; }
void Next() {
if (init_) init_ = false;
else ++iter_;
}
void Reset() {
init_ = true;
iter_ = rest_.begin();
}
private:
const L &first_;
const list<L> &rest_;
bool init_; // in the initialized state?
typename list<L>::const_iterator iter_;
DISALLOW_COPY_AND_ASSIGN(StringWeightIterator);
};
// Traverses string in backward direction.
template <typename L, StringType S>
class StringWeightReverseIterator {
public:
explicit StringWeightReverseIterator(const StringWeight<L, S>& w)
: first_(w.first_), rest_(w.rest_), fin_(first_ == 0),
iter_(rest_.rbegin()) {}
bool Done() const { return fin_; }
const L& Value() const { return iter_ == rest_.rend() ? first_ : *iter_; }
void Next() {
if (iter_ == rest_.rend()) fin_ = true;
else ++iter_;
}
void Reset() {
fin_ = false;
iter_ = rest_.rbegin();
}
private:
const L &first_;
const list<L> &rest_;
bool fin_; // in the final state?
typename list<L>::const_reverse_iterator iter_;
DISALLOW_COPY_AND_ASSIGN(StringWeightReverseIterator);
};
// StringWeight member functions follow that require
// StringWeightIterator or StringWeightReverseIterator.
template <typename L, StringType S>
inline istream &StringWeight<