// sparse-tuple-weight.h
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright 2005-2010 Google, Inc.
// Author: krr@google.com (Kasturi Rangan Raghavan)
// Inspiration: allauzen@google.com (Cyril Allauzen)
// \file
// Sparse version of tuple-weight, based on tuple-weight.h
// Internally stores sparse key, value pairs in linked list
// Default value elemnt is the assumed value of unset keys
// Internal singleton implementation that stores first key,
// value pair as a initialized member variable to avoide
// unnecessary allocation on heap.
// Use SparseTupleWeightIterator to iterate through the key,value pairs
// Note: this does NOT iterate through the default value.
//
// Sparse tuple weight set operation definitions.
#ifndef FST_LIB_SPARSE_TUPLE_WEIGHT_H__
#define FST_LIB_SPARSE_TUPLE_WEIGHT_H__
#include<string>
#include<list>
#include<stack>
#include<tr1/unordered_map>
using std::tr1::unordered_map;
using std::tr1::unordered_multimap;
#include <fst/weight.h>
DECLARE_string(fst_weight_parentheses);
DECLARE_string(fst_weight_separator);
namespace fst {
template <class W, class K> class SparseTupleWeight;
template<class W, class K>
class SparseTupleWeightIterator;
template <class W, class K>
istream &operator>>(istream &strm, SparseTupleWeight<W, K> &w);
// Arbitrary dimension tuple weight, stored as a sorted linked-list
// W is any weight class,
// K is the key value type. kNoKey(-1) is reserved for internal use
template <class W, class K = int>
class SparseTupleWeight {
public:
typedef pair<K, W> Pair;
typedef SparseTupleWeight<typename W::ReverseWeight, K> ReverseWeight;
const static K kNoKey = -1;
SparseTupleWeight() {
Init();
}
template <class Iterator>
SparseTupleWeight(Iterator begin, Iterator end) {
Init();
// Assumes input iterator is sorted
for (Iterator it = begin; it != end; ++it)
Push(*it);
}
SparseTupleWeight(const K& key, const W &w) {
Init();
Push(key, w);
}
SparseTupleWeight(const W &w) {
Init(w);
}
SparseTupleWeight(const SparseTupleWeight<W, K> &w) {
Init(w.DefaultValue());
SetDefaultValue(w.DefaultValue());
for (SparseTupleWeightIterator<W, K> it(w); !it.Done(); it.Next()) {
Push(it.Value());
}
}
static const SparseTupleWeight<W, K> &Zero() {
static SparseTupleWeight<W, K> zero;
return zero;
}
static const SparseTupleWeight<W, K> &One() {
static SparseTupleWeight<W, K> one(W::One());
return one;
}
static const SparseTupleWeight<W, K> &NoWeight() {
static SparseTupleWeight<W, K> no_weight(W::NoWeight());
return no_weight;
}
istream &Read(istream &strm) {
ReadType(strm, &default_);
ReadType(strm, &first_);
return ReadType(strm, &rest_);
}
ostream &Write(ostream &strm) const {
WriteType(strm, default_);
WriteType(strm, first_);
return WriteType(strm, rest_);
}
SparseTupleWeight<W, K> &operator=(const SparseTupleWeight<W, K> &w) {
if (this == &w) return *this; // check for w = w
Init(w.DefaultValue());
for (SparseTupleWeightIterator<W, K> it(w); !it.Done(); it.Next()) {
Push(it.Value());
}
return *this;
}
bool Member() const {
if (!DefaultValue().Member()) return false;
for (SparseTupleWeightIterator<W, K> it(*this); !it.Done(); it.Next()) {
if (!it.Value().second.Member()) return false;
}
return true;
}
// Assumes H() function exists for the hash of the key value
size_t Hash() const {
uint64 h = 0;
std::tr1::hash<K> H;
for (SparseTupleWeightIterator<W, K> it(*this); !it.Done(); it.Next()) {
h = 5 * h + H(it.Value().first);
h = 13 * h + it.Value().second.Hash();
}
return size_t(h);
}
SparseTupleWeight<W, K> Quantize(float delta = kDelta) const {
SparseTupleWeight<W, K> w;
for (SparseTupleWeightIterator<W, K> it(*this); !it.Done(); it.Next()) {
w.Push(it.Value().first, it.Value().second.Quantize(delta));
}
return w;
}
ReverseWeight Reverse() const {
SparseTupleWeight<W, K> w;
for (SparseTupleWeightIterator<W, K> it(*this); !it.Done(); it.Next()) {
w.Push(it.Value().first, it.Value().second.Reverse());
}
return w;
}
// Common initializer among constructors.
void Init() {
Init(W::Zero());
}
void Init(const W& default_value) {
first_.first = kNoKey;
/* initialized to the reserved key value */
default_ = default_value;
rest_.clear();
}
size_t Size() const {
if (first_.first == kNoKey)
return 0;
else
return rest_.size() + 1;
}
inline void Push(const K &k, const W &w, bool default_value_check = true) {
Push(make_pair(k, w), default_value_check);
}
inline void Push(const Pair &p, bool default_value_check = true) {
if (default_value_check && p.second == default_) return;
if (first_.first == kNoKey) {
first_ = p;
}