1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// string-weight.h 2f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 3f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Licensed under the Apache License, Version 2.0 (the "License"); 4f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// you may not use this file except in compliance with the License. 5f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// You may obtain a copy of the License at 6f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 7f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// http://www.apache.org/licenses/LICENSE-2.0 8f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 9f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Unless required by applicable law or agreed to in writing, software 10f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// distributed under the License is distributed on an "AS IS" BASIS, 11f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// See the License for the specific language governing permissions and 13f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// limitations under the License. 14f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 15f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Copyright 2005-2010 Google, Inc. 16f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Author: riley@google.com (Michael Riley) 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// String weight set and associated semiring operation definitions. 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_LIB_STRING_WEIGHT_H__ 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_LIB_STRING_WEIGHT_H__ 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <list> 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <string> 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/product-weight.h> 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/weight.h> 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst int kStringInfinity = -1; // Label for the infinite string 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst int kStringBad = -2; // Label for a non-string 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst char kStringSeparator = '_'; // Label separator in strings 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Determines whether to use left or right string semiring. Includes 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// restricted versions that signal an error if proper prefixes 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// (suffixes) would otherwise be returned by Plus, useful with various 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// algorithms that require functional transducer input with the 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// string semirings. 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonenum StringType { STRING_LEFT = 0, STRING_RIGHT = 1 , 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson STRING_LEFT_RESTRICT = 2, STRING_RIGHT_RESTRICT }; 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define REVERSE_STRING_TYPE(S) \ 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ((S) == STRING_LEFT ? STRING_RIGHT : \ 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ((S) == STRING_RIGHT ? STRING_LEFT : \ 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ((S) == STRING_LEFT_RESTRICT ? STRING_RIGHT_RESTRICT : \ 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson STRING_LEFT_RESTRICT))) 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S = STRING_LEFT> 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass StringWeight; 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S = STRING_LEFT> 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass StringWeightIterator; 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S = STRING_LEFT> 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass StringWeightReverseIterator; 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonbool operator==(const StringWeight<L, S> &, const StringWeight<L, S> &); 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// String semiring: (longest_common_prefix/suffix, ., Infinity, Epsilon) 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass StringWeight { 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef L Label; 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef StringWeight<L, REVERSE_STRING_TYPE(S)> ReverseWeight; 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson friend class StringWeightIterator<L, S>; 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson friend class StringWeightReverseIterator<L, S>; 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson friend bool operator==<>(const StringWeight<L, S> &, 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StringWeight<L, S> &); 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeight() { Init(); } 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson template <typename Iter> 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeight(const Iter &begin, const Iter &end) { 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Init(); 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (Iter iter = begin; iter != end; ++iter) 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PushBack(*iter); 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson explicit StringWeight(L l) { Init(); PushBack(l); } 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const StringWeight<L, S> &Zero() { 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const StringWeight<L, S> zero(kStringInfinity); 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return zero; 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const StringWeight<L, S> &One() { 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const StringWeight<L, S> one; 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return one; 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const StringWeight<L, S> &NoWeight() { 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const StringWeight<L, S> no_weight(kStringBad); 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return no_weight; 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const string &Type() { 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const string type = 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson S == STRING_LEFT ? "string" : 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (S == STRING_RIGHT ? "right_string" : 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (S == STRING_LEFT_RESTRICT ? "restricted_string" : 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson "right_restricted_string")); 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return type; 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Member() const; 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson istream &Read(istream &strm); 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ostream &Write(ostream &strm) const; 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t Hash() const; 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeight<L, S> Quantize(float delta = kDelta) const { 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return *this; 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ReverseWeight Reverse() const; 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static uint64 Properties() { 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return (S == STRING_LEFT || S == STRING_LEFT_RESTRICT ? 126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson kLeftSemiring : kRightSemiring) | kIdempotent; 127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // NB: This needs to be uncommented only if default fails for this impl. 130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // StringWeight<L, S> &operator=(const StringWeight<L, S> &w); 131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // These operations combined with the StringWeightIterator and 133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // StringWeightReverseIterator provide the access and mutation of 134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // the string internal elements. 135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Common initializer among constructors. 137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Init() { first_ = 0; } 138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Clear existing StringWeight. 140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Clear() { first_ = 0; rest_.clear(); } 141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t Size() const { return first_ ? rest_.size() + 1 : 0; } 143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void PushFront(L l) { 145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (first_) 146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rest_.push_front(first_); 147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson first_ = l; 148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void PushBack(L l) { 151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!first_) 152f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson first_ = l; 153f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else 154f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rest_.push_back(l); 155f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 156f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 157f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 158f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson L first_; // first label in string (0 if empty) 159f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson list<L> rest_; // remaining labels in string 160f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 161f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 162f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 163f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Traverses string in forward direction. 164f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 165f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass StringWeightIterator { 166f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 167f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson explicit StringWeightIterator(const StringWeight<L, S>& w) 168f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : first_(w.first_), rest_(w.rest_), init_(true), 169f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson iter_(rest_.begin()) {} 170f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 171f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Done() const { 172f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (init_) return first_ == 0; 173f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else return iter_ == rest_.end(); 174f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 175f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 176f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const L& Value() const { return init_ ? first_ : *iter_; } 177f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 178f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Next() { 179f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (init_) init_ = false; 180f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else ++iter_; 181f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 182f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 183f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Reset() { 184f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson init_ = true; 185f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson iter_ = rest_.begin(); 186f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 187f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 188f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 189f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const L &first_; 190f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const list<L> &rest_; 191f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool init_; // in the initialized state? 192f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename list<L>::const_iterator iter_; 193f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 194f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DISALLOW_COPY_AND_ASSIGN(StringWeightIterator); 195f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 196f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 197f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 198f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Traverses string in backward direction. 199f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 200f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass StringWeightReverseIterator { 201f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 202f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson explicit StringWeightReverseIterator(const StringWeight<L, S>& w) 203f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : first_(w.first_), rest_(w.rest_), fin_(first_ == 0), 204f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson iter_(rest_.rbegin()) {} 205f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 206f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Done() const { return fin_; } 207f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 208f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const L& Value() const { return iter_ == rest_.rend() ? first_ : *iter_; } 209f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 210f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Next() { 211f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (iter_ == rest_.rend()) fin_ = true; 212f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else ++iter_; 213f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 214f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 215f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Reset() { 216f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fin_ = false; 217f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson iter_ = rest_.rbegin(); 218f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 219f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 220f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 221f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const L &first_; 222f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const list<L> &rest_; 223f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool fin_; // in the final state? 224f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename list<L>::const_reverse_iterator iter_; 225f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 226f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DISALLOW_COPY_AND_ASSIGN(StringWeightReverseIterator); 227f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 228f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 229f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 230f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// StringWeight member functions follow that require 231f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// StringWeightIterator or StringWeightReverseIterator. 232f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 233f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 234f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline istream &StringWeight<L, S>::Read(istream &strm) { 235f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Clear(); 236f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int32 size; 237f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ReadType(strm, &size); 238f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (int i = 0; i < size; ++i) { 239f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson L label; 240f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ReadType(strm, &label); 241f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PushBack(label); 242f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 243f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return strm; 244f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 245f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 246f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 247f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline ostream &StringWeight<L, S>::Write(ostream &strm) const { 248f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int32 size = Size(); 249f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson WriteType(strm, size); 250f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StringWeightIterator<L, S> iter(*this); !iter.Done(); iter.Next()) { 251f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson L label = iter.Value(); 252f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson WriteType(strm, label); 253f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 254f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return strm; 255f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 256f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 257f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 258f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline bool StringWeight<L, S>::Member() const { 259f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (Size() != 1) 260f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return true; 261f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeightIterator<L, S> iter(*this); 262f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return iter.Value() != kStringBad; 263f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 264f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 265f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 266f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline typename StringWeight<L, S>::ReverseWeight 267f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonStringWeight<L, S>::Reverse() const { 268f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ReverseWeight rw; 269f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StringWeightIterator<L, S> iter(*this); !iter.Done(); iter.Next()) 270f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rw.PushFront(iter.Value()); 271f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return rw; 272f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 273f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 274f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 275f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline size_t StringWeight<L, S>::Hash() const { 276f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t h = 0; 277f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StringWeightIterator<L, S> iter(*this); !iter.Done(); iter.Next()) 278f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson h ^= h<<1 ^ iter.Value(); 279f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return h; 280f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 281f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 282f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// NB: This needs to be uncommented only if default fails for this the impl. 283f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 284f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// template <typename L, StringType S> 285f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// inline StringWeight<L, S> 286f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// &StringWeight<L, S>::operator=(const StringWeight<L, S> &w) { 287f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// if (this != &w) { 288f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Clear(); 289f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// for (StringWeightIterator<L, S> iter(w); !iter.Done(); iter.Next()) 290f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// PushBack(iter.Value()); 291f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// } 292f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// return *this; 293f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// } 294f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 295f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 296f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline bool operator==(const StringWeight<L, S> &w1, 297f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StringWeight<L, S> &w2) { 298f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (w1.Size() != w2.Size()) 299f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return false; 300f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 301f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeightIterator<L, S> iter1(w1); 302f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeightIterator<L, S> iter2(w2); 303f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 304f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (; !iter1.Done() ; iter1.Next(), iter2.Next()) 305f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (iter1.Value() != iter2.Value()) 306f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return false; 307f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 308f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return true; 309f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 310f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 311f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 312f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline bool operator!=(const StringWeight<L, S> &w1, 313f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StringWeight<L, S> &w2) { 314f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return !(w1 == w2); 315f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 316f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 317f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 318f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline bool ApproxEqual(const StringWeight<L, S> &w1, 319f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StringWeight<L, S> &w2, 320f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson float delta = kDelta) { 321f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w1 == w2; 322f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 323f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 324f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 325f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline ostream &operator<<(ostream &strm, const StringWeight<L, S> &w) { 326f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeightIterator<L, S> iter(w); 327f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (iter.Done()) 328f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return strm << "Epsilon"; 329f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if (iter.Value() == kStringInfinity) 330f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return strm << "Infinity"; 331f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if (iter.Value() == kStringBad) 332f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return strm << "BadString"; 333f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else 334f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t i = 0; !iter.Done(); ++i, iter.Next()) { 335f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (i > 0) 336f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson strm << kStringSeparator; 337f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson strm << iter.Value(); 338f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 339f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return strm; 340f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 341f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 342f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 343f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline istream &operator>>(istream &strm, StringWeight<L, S> &w) { 344f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson string s; 345f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson strm >> s; 346f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (s == "Infinity") { 347f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson w = StringWeight<L, S>::Zero(); 348f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else if (s == "Epsilon") { 349f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson w = StringWeight<L, S>::One(); 350f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 351f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson w.Clear(); 352f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson char *p = 0; 353f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (const char *cs = s.c_str(); !p || *p != '\0'; cs = p + 1) { 354f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int l = strtoll(cs, &p, 10); 355f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (p == cs || (*p != 0 && *p != kStringSeparator)) { 356f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson strm.clear(std::ios::badbit); 357f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson break; 358f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 359f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson w.PushBack(l); 360f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 361f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 362f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return strm; 363f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 364f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 365f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 366f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Default is for the restricted left and right semirings. String 367f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// equality is required (for non-Zero() input. This restriction 368f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// is used in e.g. Determinize to ensure functional input. 369f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> inline StringWeight<L, S> 370f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonPlus(const StringWeight<L, S> &w1, 371f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StringWeight<L, S> &w2) { 372f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!w1.Member() || !w2.Member()) 373f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, S>::NoWeight(); 374f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (w1 == StringWeight<L, S>::Zero()) 375f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w2; 376f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (w2 == StringWeight<L, S>::Zero()) 377f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w1; 378f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 379f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (w1 != w2) { 380f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "StringWeight::Plus: unequal arguments " 381f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << "(non-functional FST?)" 382f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << " w1 = " << w1 383f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << " w2 = " << w2; 384f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, S>::NoWeight(); 385f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 386f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 387f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w1; 388f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 389f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 390f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 391f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Longest common prefix for left string semiring. 392f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L> inline StringWeight<L, STRING_LEFT> 393f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonPlus(const StringWeight<L, STRING_LEFT> &w1, 394f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StringWeight<L, STRING_LEFT> &w2) { 395f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!w1.Member() || !w2.Member()) 396f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, STRING_LEFT>::NoWeight(); 397f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (w1 == StringWeight<L, STRING_LEFT>::Zero()) 398f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w2; 399f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (w2 == StringWeight<L, STRING_LEFT>::Zero()) 400f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w1; 401f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 402f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeight<L, STRING_LEFT> sum; 403f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeightIterator<L, STRING_LEFT> iter1(w1); 404f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeightIterator<L, STRING_LEFT> iter2(w2); 405f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (; !iter1.Done() && !iter2.Done() && iter1.Value() == iter2.Value(); 406f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson iter1.Next(), iter2.Next()) 407f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sum.PushBack(iter1.Value()); 408f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return sum; 409f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 410f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 411f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 412f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Longest common suffix for right string semiring. 413f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L> inline StringWeight<L, STRING_RIGHT> 414f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonPlus(const StringWeight<L, STRING_RIGHT> &w1, 415f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StringWeight<L, STRING_RIGHT> &w2) { 416f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!w1.Member() || !w2.Member()) 417f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, STRING_RIGHT>::NoWeight(); 418f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (w1 == StringWeight<L, STRING_RIGHT>::Zero()) 419f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w2; 420f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (w2 == StringWeight<L, STRING_RIGHT>::Zero()) 421f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w1; 422f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 423f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeight<L, STRING_RIGHT> sum; 424f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeightReverseIterator<L, STRING_RIGHT> iter1(w1); 425f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeightReverseIterator<L, STRING_RIGHT> iter2(w2); 426f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (; !iter1.Done() && !iter2.Done() && iter1.Value() == iter2.Value(); 427f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson iter1.Next(), iter2.Next()) 428f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sum.PushFront(iter1.Value()); 429f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return sum; 430f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 431f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 432f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 433f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> 434f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline StringWeight<L, S> Times(const StringWeight<L, S> &w1, 435f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StringWeight<L, S> &w2) { 436f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!w1.Member() || !w2.Member()) 437f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, S>::NoWeight(); 438f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (w1 == StringWeight<L, S>::Zero() || w2 == StringWeight<L, S>::Zero()) 439f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, S>::Zero(); 440f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 441f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeight<L, S> prod(w1); 442f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StringWeightIterator<L, S> iter(w2); !iter.Done(); iter.Next()) 443f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson prod.PushBack(iter.Value()); 444f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 445f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return prod; 446f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 447f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 448f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 449f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Default is for left division in the left string and the 450f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// left restricted string semirings. 451f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L, StringType S> inline StringWeight<L, S> 452f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonDivide(const StringWeight<L, S> &w1, 453f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StringWeight<L, S> &w2, 454f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DivideType typ) { 455f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 456f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (typ != DIVIDE_LEFT) { 457f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "StringWeight::Divide: only left division is defined " 458f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << "for the " << StringWeight<L, S>::Type() << " semiring"; 459f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, S>::NoWeight(); 460f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 461f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 462f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!w1.Member() || !w2.Member()) 463f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, S>::NoWeight(); 464f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 465f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (w2 == StringWeight<L, S>::Zero()) 466f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, S>(kStringBad); 467f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if (w1 == StringWeight<L, S>::Zero()) 468f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, S>::Zero(); 469f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 470f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeight<L, S> div; 471f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeightIterator<L, S> iter(w1); 472f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (int i = 0; !iter.Done(); iter.Next(), ++i) { 473f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (i >= w2.Size()) 474f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson div.PushBack(iter.Value()); 475f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 476f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return div; 477f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 478f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 479f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 480f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Right division in the right string semiring. 481f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L> inline StringWeight<L, STRING_RIGHT> 482f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonDivide(const StringWeight<L, STRING_RIGHT> &w1, 483f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StringWeight<L, STRING_RIGHT> &w2, 484f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DivideType typ) { 485f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 486f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (typ != DIVIDE_RIGHT) { 487f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "StringWeight::Divide: only right division is defined " 488f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << "for the right string semiring"; 489f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, STRING_RIGHT>::NoWeight(); 490f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 491f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 492f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!w1.Member() || !w2.Member()) 493f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, STRING_RIGHT>::NoWeight(); 494f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 495f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (w2 == StringWeight<L, STRING_RIGHT>::Zero()) 496f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, STRING_RIGHT>(kStringBad); 497f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if (w1 == StringWeight<L, STRING_RIGHT>::Zero()) 498f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, STRING_RIGHT>::Zero(); 499f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 500f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeight<L, STRING_RIGHT> div; 501f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeightReverseIterator<L, STRING_RIGHT> iter(w1); 502f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (int i = 0; !iter.Done(); iter.Next(), ++i) { 503f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (i >= w2.Size()) 504f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson div.PushFront(iter.Value()); 505f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 506f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return div; 507f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 508f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 509f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 510f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Right division in the right restricted string semiring. 511f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename L> inline StringWeight<L, STRING_RIGHT_RESTRICT> 512f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonDivide(const StringWeight<L, STRING_RIGHT_RESTRICT> &w1, 513f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StringWeight<L, STRING_RIGHT_RESTRICT> &w2, 514f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DivideType typ) { 515f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 516f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (typ != DIVIDE_RIGHT) { 517f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "StringWeight::Divide: only right division is defined " 518f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << "for the right restricted string semiring"; 519f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, STRING_RIGHT_RESTRICT>::NoWeight(); 520f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 521f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 522f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!w1.Member() || !w2.Member()) 523f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, STRING_RIGHT_RESTRICT>::NoWeight(); 524f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 525f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (w2 == StringWeight<L, STRING_RIGHT_RESTRICT>::Zero()) 526f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, STRING_RIGHT_RESTRICT>(kStringBad); 527f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if (w1 == StringWeight<L, STRING_RIGHT_RESTRICT>::Zero()) 528f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return StringWeight<L, STRING_RIGHT_RESTRICT>::Zero(); 529f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 530f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeight<L, STRING_RIGHT_RESTRICT> div; 531f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeightReverseIterator<L, STRING_RIGHT_RESTRICT> iter(w1); 532f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (int i = 0; !iter.Done(); iter.Next(), ++i) { 533f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (i >= w2.Size()) 534f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson div.PushFront(iter.Value()); 535f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 536f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return div; 537f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 538f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 539f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 540f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Product of string weight and an arbitray weight. 541f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class L, class W, StringType S = STRING_LEFT> 542f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonstruct GallicWeight : public ProductWeight<StringWeight<L, S>, W> { 543f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef GallicWeight<L, typename W::ReverseWeight, REVERSE_STRING_TYPE(S)> 544f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ReverseWeight; 545f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 546f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson GallicWeight() {} 547f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 548f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson GallicWeight(StringWeight<L, S> w1, W w2) 549f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ProductWeight<StringWeight<L, S>, W>(w1, w2) {} 550f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 551f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson explicit GallicWeight(const string &s, int *nread = 0) 552f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ProductWeight<StringWeight<L, S>, W>(s, nread) {} 553f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 554f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson GallicWeight(const ProductWeight<StringWeight<L, S>, W> &w) 555f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ProductWeight<StringWeight<L, S>, W>(w) {} 556f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 557f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 558f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 559f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 560f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // FST_LIB_STRING_WEIGHT_H__ 561