string-weight.h revision 4a68b3365c8c50aa93505e99ead2565ab73dcdb0
14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// string-weight.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// String weight set and associated semiring operation definitions. 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_STRING_WEIGHT_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_STRING_WEIGHT_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <list> 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/product-weight.h" 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/weight.h" 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectconst int kStringInfinity = -1; // Label for the infinite string 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectconst int kStringBad = -2; // Label for a non-string 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectconst char kStringSeparator = '_'; // Label separator in strings 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Determines whether to use left or right string semiring. Includes 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// restricted versions that signal an error if proper prefixes 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// (suffixes) would otherwise be returned by Plus, useful with various 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// algorithms that require functional transducer input with the 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// string semirings. 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectenum StringType { STRING_LEFT = 0, STRING_RIGHT = 1 , 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project STRING_LEFT_RESTRICT = 2, STRING_RIGHT_RESTRICT }; 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define REVERSE_STRING_TYPE(S) \ 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ((S) == STRING_LEFT ? STRING_RIGHT : \ 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ((S) == STRING_RIGHT ? STRING_LEFT : \ 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ((S) == STRING_LEFT_RESTRICT ? STRING_RIGHT_RESTRICT : \ 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project STRING_LEFT_RESTRICT))) 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S = STRING_LEFT> 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StringWeight; 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S = STRING_LEFT> 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StringWeightIterator; 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S = STRING_LEFT> 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StringWeightReverseIterator; 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectbool operator==(const StringWeight<L, S> &, const StringWeight<L, S> &); 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// String semiring: (longest_common_prefix/suffix, ., Infinity, Epsilon) 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StringWeight { 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef L Label; 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef StringWeight<L, REVERSE_STRING_TYPE(S)> ReverseWeight; 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class StringWeightIterator<L, S>; 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class StringWeightReverseIterator<L, S>; 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend bool operator==<>(const StringWeight<L, S> &, 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StringWeight<L, S> &); 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeight() { Init(); } 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project template <typename Iter> 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeight(const Iter &begin, const Iter &end) { 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Init(); 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (Iter iter = begin; iter != end; ++iter) 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PushBack(*iter); 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit StringWeight(L l) { Init(); PushBack(l); } 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const StringWeight<L, S> &Zero() { 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const StringWeight<L, S> zero(kStringInfinity); 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return zero; 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const StringWeight<L, S> &One() { 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const StringWeight<L, S> one; 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return one; 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const string &Type() { 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const string type = 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project S == STRING_LEFT ? "string" : 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (S == STRING_RIGHT ? "right_string" : 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (S == STRING_LEFT_RESTRICT ? "restricted_string" : 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project "right_restricted_string")); 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return type; 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Member() const; 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project istream &Read(istream &strm); 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ostream &Write(ostream &strm) const; 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ssize_t Hash() const; 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeight<L, S> Quantize(float delta = kDelta) const { 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return *this; 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ReverseWeight Reverse() const; 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static uint64 Properties() { 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return (S == STRING_LEFT || S == STRING_LEFT_RESTRICT ? 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kLeftSemiring : kRightSemiring) | kIdempotent; 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // NB: This needs to be uncommented only if default fails for this impl. 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // StringWeight<L, S> &operator=(const StringWeight<L, S> &w); 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // These operations combined with the StringWeightIterator and 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // StringWeightReverseIterator provide the access and mutation of 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // the string internal elements. 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Common initializer among constructors. 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Init() { first_ = 0; } 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Clear existing StringWeight. 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Clear() { first_ = 0; rest_.clear(); } 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label Size() const { return first_ ? rest_.size() + 1 : 0; } 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void PushFront(L l) { 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (first_) 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rest_.push_front(first_); 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project first_ = l; 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void PushBack(L l) { 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!first_) 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project first_ = l; 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rest_.push_back(l); 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project L first_; // first label in string (0 if empty) 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project list<L> rest_; // remaining labels in string 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Traverses string in forward direction. 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StringWeightIterator { 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit StringWeightIterator(const StringWeight<L, S>& w) 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : first_(w.first_), rest_(w.rest_), init_(true), 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project iter_(rest_.begin()) {} 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Done() const { 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (init_) return first_ == 0; 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else return iter_ == rest_.end(); 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const L& Value() const { return init_ ? first_ : *iter_; } 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Next() { 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (init_) init_ = false; 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else ++iter_; 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Reset() { 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project init_ = true; 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project iter_ = rest_.begin(); 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const L &first_; 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const list<L> &rest_; 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool init_; // in the initialized state? 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typename list<L>::const_iterator iter_; 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(StringWeightIterator); 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Traverses string in forward direction. 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StringWeightReverseIterator { 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit StringWeightReverseIterator(const StringWeight<L, S>& w) 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : first_(w.first_), rest_(w.rest_), fin_(first_ == 0), 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project iter_(rest_.rbegin()) {} 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Done() const { return fin_; } 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const L& Value() const { return iter_ == rest_.rend() ? first_ : *iter_; } 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Next() { 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (iter_ == rest_.rend()) fin_ = true; 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else ++iter_; 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Reset() { 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fin_ = false; 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project iter_ = rest_.rbegin(); 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const L &first_; 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const list<L> &rest_; 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool fin_; // in the final state? 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typename list<L>::const_reverse_iterator iter_; 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(StringWeightReverseIterator); 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// StringWeight member functions follow that require 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// StringWeightIterator or StringWeightReverseIterator. 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectinline istream &StringWeight<L, S>::Read(istream &strm) { 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Clear(); 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int32 size = 0; 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ReadType(strm, &size); 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (int i = 0; i < size; ++i) { 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project L label; 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ReadType(strm, &label); 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PushBack(label); 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return strm; 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectinline ostream &StringWeight<L, S>::Write(ostream &strm) const { 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int32 size = Size(); 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project WriteType(strm, size); 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StringWeightIterator<L, S> iter(*this); !iter.Done(); iter.Next()) { 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project L label = iter.Value(); 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project WriteType(strm, label); 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return strm; 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectinline bool StringWeight<L, S>::Member() const { 2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (Size() != 1) 2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeightIterator<L, S> iter(*this); 2544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return iter.Value() != kStringBad; 2554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectinline typename StringWeight<L, S>::ReverseWeight 2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectStringWeight<L, S>::Reverse() const { 2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ReverseWeight rw; 2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StringWeightIterator<L, S> iter(*this); !iter.Done(); iter.Next()) 2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rw.PushFront(iter.Value()); 2634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return rw; 2644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 2674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectinline ssize_t StringWeight<L, S>::Hash() const { 2684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t h = 0; 2694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StringWeightIterator<L, S> iter(*this); !iter.Done(); iter.Next()) 2704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project h ^= h<<1 ^ iter.Value(); 2714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return static_cast<ssize_t>(h); 2724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// NB: This needs to be uncommented only if default fails for this the impl. 2754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 2764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// template <typename L, StringType S> 2774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// inline StringWeight<L, S> 2784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// &StringWeight<L, S>::operator=(const StringWeight<L, S> &w) { 2794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// if (this != &w) { 2804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Clear(); 2814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// for (StringWeightIterator<L, S> iter(w); !iter.Done(); iter.Next()) 2824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// PushBack(iter.Value()); 2834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// } 2844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// return *this; 2854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// } 2864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 2884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectinline bool operator==(const StringWeight<L, S> &w1, 2894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StringWeight<L, S> &w2) { 2904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (w1.Size() != w2.Size()) 2914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 2924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeightIterator<L, S> iter1(w1); 2944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeightIterator<L, S> iter2(w2); 2954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (; !iter1.Done() ; iter1.Next(), iter2.Next()) 2974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (iter1.Value() != iter2.Value()) 2984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 2994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 3014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 3024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 3044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectinline bool operator!=(const StringWeight<L, S> &w1, 3054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StringWeight<L, S> &w2) { 3064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return !(w1 == w2); 3074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 3084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 3104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectinline bool ApproxEqual(const StringWeight<L, S> &w1, 3114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StringWeight<L, S> &w2, 3124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project float delta = kDelta) { 3134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return w1 == w2; 3144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 3154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 3174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectinline ostream &operator<<(ostream &strm, const StringWeight<L, S> &w) { 3184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeightIterator<L, S> iter(w); 3194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (iter.Done()) 3204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return strm << "Epsilon"; 3214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (iter.Value() == kStringInfinity) 3224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return strm << "Infinity"; 3234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (iter.Value() == kStringBad) 3244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return strm << "BadString"; 3254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 3264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t i = 0; !iter.Done(); ++i, iter.Next()) { 3274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (i > 0) 3284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project strm << kStringSeparator; 3294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project strm << iter.Value(); 3304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return strm; 3324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 3334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 3354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectinline istream &operator>>(istream &strm, StringWeight<L, S> &w) { 3364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project string s; 3374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project strm >> s; 3384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s == "Infinity") { 3394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project w = StringWeight<L, S>::Zero(); 3404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (s == "Epsilon") { 3414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project w = StringWeight<L, S>::One(); 3424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 3434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project w.Clear(); 3444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project char *p = 0; 3454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (const char *cs = s.c_str(); !p || *p != '\0'; cs = p + 1) { 3464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int l = strtoll(cs, &p, 10); 3474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (p == cs || *p != 0 && *p != kStringSeparator) { 3484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project strm.clear(std::ios::badbit); 3494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 3504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project w.PushBack(l); 3524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return strm; 3554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 3564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Default is for the restricted left and right semirings. String 3594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// equality is required (for non-Zero() input. This restriction 3604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// is used in e.g. Determinize to ensure functional input. 3614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> inline StringWeight<L, S> 3624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectPlus(const StringWeight<L, S> &w1, 3634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StringWeight<L, S> &w2) { 3644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (w1 == StringWeight<L, S>::Zero()) 3654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return w2; 3664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (w2 == StringWeight<L, S>::Zero()) 3674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return w1; 3684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (w1 != w2) 3704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "StringWeight::Plus: unequal arguments " 3714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << "(non-functional FST?)"; 3724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return w1; 3744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 3754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Longest common prefix for left string semiring. 3784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L> inline StringWeight<L, STRING_LEFT> 3794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectPlus(const StringWeight<L, STRING_LEFT> &w1, 3804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StringWeight<L, STRING_LEFT> &w2) { 3814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (w1 == StringWeight<L, STRING_LEFT>::Zero()) 3824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return w2; 3834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (w2 == StringWeight<L, STRING_LEFT>::Zero()) 3844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return w1; 3854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeight<L, STRING_LEFT> sum; 3874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeightIterator<L, STRING_LEFT> iter1(w1); 3884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeightIterator<L, STRING_LEFT> iter2(w2); 3894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (; !iter1.Done() && !iter2.Done() && iter1.Value() == iter2.Value(); 3904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project iter1.Next(), iter2.Next()) 3914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sum.PushBack(iter1.Value()); 3924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return sum; 3934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 3944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Longest common suffix for right string semiring. 3974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L> inline StringWeight<L, STRING_RIGHT> 3984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectPlus(const StringWeight<L, STRING_RIGHT> &w1, 3994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StringWeight<L, STRING_RIGHT> &w2) { 4004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (w1 == StringWeight<L, STRING_RIGHT>::Zero()) 4014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return w2; 4024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (w2 == StringWeight<L, STRING_RIGHT>::Zero()) 4034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return w1; 4044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeight<L, STRING_RIGHT> sum; 4064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeightReverseIterator<L, STRING_RIGHT> iter1(w1); 4074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeightReverseIterator<L, STRING_RIGHT> iter2(w2); 4084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (; !iter1.Done() && !iter2.Done() && iter1.Value() == iter2.Value(); 4094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project iter1.Next(), iter2.Next()) 4104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sum.PushFront(iter1.Value()); 4114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return sum; 4124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 4134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 4164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectinline StringWeight<L, S> Times(const StringWeight<L, S> &w1, 4174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StringWeight<L, S> &w2) { 4184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (w1 == StringWeight<L, S>::Zero() || w2 == StringWeight<L, S>::Zero()) 4194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return StringWeight<L, S>::Zero(); 4204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeight<L, S> prod(w1); 4224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StringWeightIterator<L, S> iter(w2); !iter.Done(); iter.Next()) 4234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project prod.PushBack(iter.Value()); 4244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return prod; 4264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 4274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Default is for left division in the left string and the 4304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// left restricted string semirings. 4314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> inline StringWeight<L, S> 4324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectDivide(const StringWeight<L, S> &w1, 4334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StringWeight<L, S> &w2, 4344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DivideType typ) { 4354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (typ != DIVIDE_LEFT) 4374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "StringWeight::Divide: only left division is defined " 4384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << "for the " << StringWeight<L, S>::Type() << " semiring"; 4394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (w2 == StringWeight<L, S>::Zero()) 4414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return StringWeight<L, S>(kStringBad); 4424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (w1 == StringWeight<L, S>::Zero()) 4434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return StringWeight<L, S>::Zero(); 4444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeight<L, S> div; 4464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeightIterator<L, S> iter(w1); 4474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (int i = 0; !iter.Done(); iter.Next(), ++i) { 4484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (i >= w2.Size()) 4494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project div.PushBack(iter.Value()); 4504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return div; 4524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 4534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Right division in the right string semiring. 4564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L> inline StringWeight<L, STRING_RIGHT> 4574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectDivide(const StringWeight<L, STRING_RIGHT> &w1, 4584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StringWeight<L, STRING_RIGHT> &w2, 4594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DivideType typ) { 4604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (typ != DIVIDE_RIGHT) 4624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "StringWeight::Divide: only right division is defined " 4634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << "for the right string semiring"; 4644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (w2 == StringWeight<L, STRING_RIGHT>::Zero()) 4664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return StringWeight<L, STRING_RIGHT>(kStringBad); 4674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (w1 == StringWeight<L, STRING_RIGHT>::Zero()) 4684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return StringWeight<L, STRING_RIGHT>::Zero(); 4694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeight<L, STRING_RIGHT> div; 4714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeightReverseIterator<L, STRING_RIGHT> iter(w1); 4724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (int i = 0; !iter.Done(); iter.Next(), ++i) { 4734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (i >= w2.Size()) 4744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project div.PushFront(iter.Value()); 4754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return div; 4774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 4784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Right division in the right restricted string semiring. 4814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L> inline StringWeight<L, STRING_RIGHT_RESTRICT> 4824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectDivide(const StringWeight<L, STRING_RIGHT_RESTRICT> &w1, 4834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StringWeight<L, STRING_RIGHT_RESTRICT> &w2, 4844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DivideType typ) { 4854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (typ != DIVIDE_RIGHT) 4874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "StringWeight::Divide: only right division is defined " 4884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << "for the right restricted string semiring"; 4894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (w2 == StringWeight<L, STRING_RIGHT_RESTRICT>::Zero()) 4914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return StringWeight<L, STRING_RIGHT_RESTRICT>(kStringBad); 4924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (w1 == StringWeight<L, STRING_RIGHT_RESTRICT>::Zero()) 4934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return StringWeight<L, STRING_RIGHT_RESTRICT>::Zero(); 4944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeight<L, STRING_RIGHT_RESTRICT> div; 4964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeightReverseIterator<L, STRING_RIGHT_RESTRICT> iter(w1); 4974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (int i = 0; !iter.Done(); iter.Next(), ++i) { 4984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (i >= w2.Size()) 4994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project div.PushFront(iter.Value()); 5004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return div; 5024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 5034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Product of string weight and an arbitray weight. 5064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class L, class W, StringType S = STRING_LEFT> 5074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct GallicWeight : public ProductWeight<StringWeight<L, S>, W> { 5084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef GallicWeight<L, typename W::ReverseWeight, REVERSE_STRING_TYPE(S)> 5094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ReverseWeight; 5104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project GallicWeight() {} 5124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project GallicWeight(StringWeight<L, S> w1, W w2) 5144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ProductWeight<StringWeight<L, S>, W>(w1, w2) {} 5154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit GallicWeight(const string &s, int *nread = 0) 5174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ProductWeight<StringWeight<L, S>, W>(s, nread) {} 5184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project GallicWeight(const ProductWeight<StringWeight<L, S>, W> &w) 5204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ProductWeight<StringWeight<L, S>, W>(w) {} 5214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 5224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst; 5244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_STRING_WEIGHT_H__ 526