src/include/fst/bi-table.h - platform/external/openfst - Git at Google

 // bi-table.h

 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.
 //
 // Copyright 2005-2010 Google, Inc.
 // Author: riley@google.com (Michael Riley)
 //
 // \file
 // Classes for representing a bijective mapping between an arbitrary entry
 // of type T and a signed integral ID.

 #ifndef FST_LIB_BI_TABLE_H__
 #define FST_LIB_BI_TABLE_H__

 #include <deque>
 #include <vector>
 using std::vector;

 namespace fst {

 // BI TABLES - these determine a bijective mapping between an
 // arbitrary entry of type T and an signed integral ID of type I. The IDs are
 // allocated starting from 0 in order.
 //
 // template <class I, class T>
 // class BiTable {
 //  public:
 //
 //   // Required constructors.
 //   BiTable();
 //
 //   // Lookup integer ID from entry. If it doesn't exist, then add it.
 //   I FindId(const T &entry);
 //   // Lookup entry from integer ID.
 //   const T &FindEntry(I) const;
 //   // # of stored entries.
 //   I Size() const;
 // };

 // An implementation using a hash map for the entry to ID mapping.
 // The  entry T must have == defined and the default constructor
 // must produce an entry that will never be seen. H is the hash function.
 template <class I, class T, class H>
 class HashBiTable {
  public:

   HashBiTable() {
     T empty_entry;
   }

   I FindId(const T &entry) {
     I &id_ref = entry2id_[entry];
     if (id_ref == 0) {  // T not found; store and assign it a new ID.
       id2entry_.push_back(entry);
       id_ref = id2entry_.size();
     }
     return id_ref - 1;  // NB: id_ref = ID + 1
   }

   const T &FindEntry(I s) const {
     return id2entry_[s];
   }

   I Size() const { return id2entry_.size(); }

  private:
   unordered_map<T, I, H> entry2id_;
   vector<T> id2entry_;

   DISALLOW_COPY_AND_ASSIGN(HashBiTable);
 };


 // An implementation using a hash set for the entry to ID
 // mapping.  The hash set holds 'keys' which are either the ID
 // or kCurrentKey.  These keys can be mapped to entrys either by
 // looking up in the entry vector or, if kCurrentKey, in current_entry_
 // member. The hash and key equality functions map to entries first.
 // The  entry T must have == defined and the default constructor
 // must produce a entry that will never be seen. H is the hash
 // function.
 template <class I, class T, class H>
 class CompactHashBiTable {
  public:
   friend class HashFunc;
   friend class HashEqual;

   CompactHashBiTable()
       : hash_func_(*this),
         hash_equal_(*this),
         keys_(0, hash_func_, hash_equal_) {
   }

   // Reserves space for table_size elements.
   explicit CompactHashBiTable(size_t table_size)
       : hash_func_(*this),
         hash_equal_(*this),
         keys_(table_size, hash_func_, hash_equal_) {
     id2entry_.reserve(table_size);
   }

   I FindId(const T &entry) {
     current_entry_ = &entry;
     typename KeyHashSet::const_iterator it = keys_.find(kCurrentKey);
     if (it == keys_.end()) {
       I key = id2entry_.size();
       id2entry_.push_back(entry);
       keys_.insert(key);
       return key;
     } else {
       return *it;
     }
   }

   const T &FindEntry(I s) const { return id2entry_[s]; }
   I Size() const { return id2entry_.size(); }

  private:
   static const I kEmptyKey;    // -1
   static const I kCurrentKey;  // -2

   class HashFunc {
    public:
     HashFunc(const CompactHashBiTable &ht) : ht_(&ht) {}

     size_t operator()(I k) const { return hf(ht_->Key2T(k)); }
    private:
     const CompactHashBiTable *ht_;
     H hf;
   };

   class HashEqual {
    public:
     HashEqual(const CompactHashBiTable &ht) : ht_(&ht) {}

     bool operator()(I k1, I k2) const {
       return ht_->Key2T(k1) == ht_->Key2T(k2);
     }
    private:
     const CompactHashBiTable *ht_;
   };

   typedef unordered_set<I, HashFunc, HashEqual> KeyHashSet;

   const T &Key2T(I k) const {
     if (k == kEmptyKey)
       return empty_entry_;
     else if (k == kCurrentKey)
       return *current_entry_;
     else
       return id2entry_[k];
   }

   HashFunc hash_func_;
   HashEqual hash_equal_;
   KeyHashSet keys_;
   vector<T> id2entry_;
   const T empty_entry_;
   const T *current_entry_;

   DISALLOW_COPY_AND_ASSIGN(CompactHashBiTable);
 };

 template <class I, class T, class H>
 const I CompactHashBiTable<I, T, H>::kEmptyKey = -1;

 template <class I, class T, class H>
 const I CompactHashBiTable<I, T, H>::kCurrentKey = -2;


 // An implementation using a vector for the entry to ID mapping.
 // It is passed a function object FP that should fingerprint entries
 // uniquely to an integer that can used as a vector index. Normally,
 // VectorBiTable constructs the FP object.  The user can instead
 // pass in this object; in that case, VectorBiTable takes its
 // ownership.
 template <class I, class T, class FP>
 class VectorBiTable {
  public:
   explicit VectorBiTable(FP *fp = 0) : fp_(fp ? fp : new FP()) {}

   ~VectorBiTable() { delete fp_; }

   I FindId(const T &entry) {
     ssize_t fp = (*fp_)(entry);
     if (fp >= fp2id_.size())
       fp2id_.resize(fp + 1);
     I &id_ref = fp2id_[fp];
     if (id_ref == 0) {  // T not found; store and assign it a new ID.
       id2entry_.push_back(entry);
       id_ref = id2entry_.size();
     }
     return id_ref - 1;  // NB: id_ref = ID + 1
   }

   const T &FindEntry(I s) const { return id2entry_[s]; }

   I Size() const { return id2entry_.size(); }

   const FP &Fingerprint() const { return *fp_; }

  private:
   FP *fp_;
   vector<I> fp2id_;
   vector<T> id2entry_;

   DISALLOW_COPY_AND_ASSIGN(VectorBiTable);
 };


 // An implementation using a vector and a compact hash table. The
 // selecting functor S returns true for entries to be hashed in the
 // vector.  The fingerprinting functor FP returns a unique fingerprint
 // for each entry to be hashed in the vector (these need to be
 // suitable for indexing in a vector).  The hash functor H is used when
 // hashing entry into the compact hash table.
 template <class I, class T, class S, class FP, class H>
 class VectorHashBiTable {
  public:
   friend class HashFunc;
   friend class HashEqual;

   VectorHashBiTable(S *s, FP *fp, H *h,
                        size_t vector_size = 0,
                        size_t entry_size = 0)
       : selector_(s),
         fp_(fp),
         h_(h),
         hash_func_(*this),
         hash_equal_(*this),
         keys_(0, hash_func_, hash_equal_) {
     if (vector_size)
       fp2id_.reserve(vector_size);
     if (entry_size)
       id2entry_.reserve(entry_size);
   }

   ~VectorHashBiTable() {
     delete selector_;
     delete fp_;
     delete h_;
   }

   I FindId(const T &entry) {
     if ((*selector_)(entry)) {  // Use the vector if 'selector_(entry) == true'
       uint64 fp = (*fp_)(entry);
       if (fp2id_.size() <= fp)
         fp2id_.resize(fp + 1, 0);
       if (fp2id_[fp] == 0) {
         id2entry_.push_back(entry);
         fp2id_[fp] = id2entry_.size();
       }
       return fp2id_[fp] - 1;  // NB: assoc_value = ID + 1
     } else {  // Use the hash table otherwise.
       current_entry_ = &entry;
       typename KeyHashSet::const_iterator it = keys_.find(kCurrentKey);
       if (it == keys_.end()) {
         I key = id2entry_.size();
         id2entry_.push_back(entry);
         keys_.insert(key);
         return key;
       } else {
         return *it;
       }
     }
   }

   const T &FindEntry(I s) const {
     return id2entry_[s];
   }

   I Size() const { return id2entry_.size(); }

   const S &Selector() const { return *selector_; }

   const FP &Fingerprint() const { return *fp_; }

   const H &Hash() const { return *h_; }

  private:
   static const I kEmptyKey;
   static const I kCurrentKey;

   class HashFunc {
    public:
     HashFunc(const VectorHashBiTable &ht) : ht_(&ht) {}

     size_t operator()(I k) const { return (*(ht_->h_))(ht_->Key2Entry(k)); }
    private:
     const VectorHashBiTable *ht_;
   };

   class HashEqual {
    public:
     HashEqual(const VectorHashBiTable &ht) : ht_(&ht) {}

     bool operator()(I k1, I k2) const {
       return ht_->Key2Entry(k1) == ht_->Key2Entry(k2);
     }
    private:
     const VectorHashBiTable *ht_;
   };

   typedef unordered_set<I, HashFunc, HashEqual> KeyHashSet;

   const T &Key2Entry(I k) const {
     if (k == kEmptyKey)
       return empty_entry_;
     else if (k == kCurrentKey)
       return *current_entry_;
     else
       return id2entry_[k];
   }


   S *selector_;  // Returns true if entry hashed into vector
   FP *fp_;       // Fingerprint used when hashing entry into vector
   H *h_;         // Hash function used when hashing entry into hash_set

   vector<T> id2entry_;  // Maps state IDs to entry
   vector<I> fp2id_;        // Maps entry fingerprints to IDs

   // Compact implementation of the hash table mapping entrys to
   // state IDs using the hash function 'h_'
   HashFunc hash_func_;
   HashEqual hash_equal_;
   KeyHashSet keys_;
   const T empty_entry_;
   const T *current_entry_;

   DISALLOW_COPY_AND_ASSIGN(VectorHashBiTable);
 };

 template <class I, class T, class S, class FP, class H>
 const I VectorHashBiTable<I, T, S, FP, H>::kEmptyKey = -1;

 template <class I, class T, class S, class FP, class H>
 const I VectorHashBiTable<I, T, S, FP, H>::kCurrentKey = -2;


 // An implementation using a hash map for the entry to ID
 // mapping. This version permits erasing of s.  The  entry T
 // must have == defined and its default constructor must produce a
 // entry that will never be seen. F is the hash function.
 template <class I, class T, class F>
 class ErasableBiTable {
  public:
   ErasableBiTable() : first_(0) {}

   I FindId(const T &entry) {
     I &id_ref = entry2id_[entry];
     if (id_ref == 0) {  // T not found; store and assign it a new ID.
       id2entry_.push_back(entry);
       id_ref = id2entry_.size() + first_;
     }
     return id_ref - 1;  // NB: id_ref = ID + 1
   }

   const T &FindEntry(I s) const { return id2entry_[s - first_]; }

   I Size() const { return id2entry_.size(); }

   void Erase(I s) {
     T &entry = id2entry_[s - first_];
     typename unordered_map<T, I, F>::iterator it =
         entry2id_.find(entry);
     entry2id_.erase(it);
     id2entry_[s - first_] = empty_entry_;
     while (!id2entry_.empty() && id2entry_.front() == empty_entry_) {
       id2entry_.pop_front();
       ++first_;
     }
   }

  private:
   unordered_map<T, I, F> entry2id_;
   deque<T> id2entry_;
   const T empty_entry_;
   I first_;        // I of first element in the deque;

   DISALLOW_COPY_AND_ASSIGN(ErasableBiTable);
 };

 }  // namespace fst

 #endif  // FST_LIB_BI_TABLE_H__
	// bi-table.h

	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.
	//
	// Copyright 2005-2010 Google, Inc.
	// Author: riley@google.com (Michael Riley)
	//
	// \file
	// Classes for representing a bijective mapping between an arbitrary entry
	// of type T and a signed integral ID.

	#ifndef FST_LIB_BI_TABLE_H__
	#define FST_LIB_BI_TABLE_H__

	#include <deque>
	#include <vector>
	using std::vector;

	namespace fst {

	// BI TABLES - these determine a bijective mapping between an
	// arbitrary entry of type T and an signed integral ID of type I. The IDs are
	// allocated starting from 0 in order.
	//
	// template <class I, class T>
	// class BiTable {
	// public:
	//
	// // Required constructors.
	// BiTable();
	//
	// // Lookup integer ID from entry. If it doesn't exist, then add it.
	// I FindId(const T &entry);
	// // Lookup entry from integer ID.
	// const T &FindEntry(I) const;
	// // # of stored entries.
	// I Size() const;
	// };

	// An implementation using a hash map for the entry to ID mapping.
	// The entry T must have == defined and the default constructor
	// must produce an entry that will never be seen. H is the hash function.
	template <class I, class T, class H>
	class HashBiTable {
	public:

	HashBiTable() {
	T empty_entry;
	}

	I FindId(const T &entry) {
	I &id_ref = entry2id_[entry];
	if (id_ref == 0) { // T not found; store and assign it a new ID.
	id2entry_.push_back(entry);
	id_ref = id2entry_.size();
	}
	return id_ref - 1; // NB: id_ref = ID + 1
	}

	const T &FindEntry(I s) const {
	return id2entry_[s];
	}

	I Size() const { return id2entry_.size(); }

	private:
	unordered_map<T, I, H> entry2id_;
	vector<T> id2entry_;

	DISALLOW_COPY_AND_ASSIGN(HashBiTable);
	};


	// An implementation using a hash set for the entry to ID
	// mapping. The hash set holds 'keys' which are either the ID
	// or kCurrentKey. These keys can be mapped to entrys either by
	// looking up in the entry vector or, if kCurrentKey, in current_entry_
	// member. The hash and key equality functions map to entries first.
	// The entry T must have == defined and the default constructor
	// must produce a entry that will never be seen. H is the hash
	// function.
	template <class I, class T, class H>
	class CompactHashBiTable {
	public:
	friend class HashFunc;
	friend class HashEqual;

	CompactHashBiTable()
	: hash_func_(*this),
	hash_equal_(*this),
	keys_(0, hash_func_, hash_equal_) {
	}

	// Reserves space for table_size elements.
	explicit CompactHashBiTable(size_t table_size)
	: hash_func_(*this),
	hash_equal_(*this),
	keys_(table_size, hash_func_, hash_equal_) {
	id2entry_.reserve(table_size);
	}

	I FindId(const T &entry) {
	current_entry_ = &entry;
	typename KeyHashSet::const_iterator it = keys_.find(kCurrentKey);
	if (it == keys_.end()) {
	I key = id2entry_.size();
	id2entry_.push_back(entry);
	keys_.insert(key);
	return key;
	} else {
	return *it;
	}
	}

	const T &FindEntry(I s) const { return id2entry_[s]; }
	I Size() const { return id2entry_.size(); }

	private:
	static const I kEmptyKey; // -1
	static const I kCurrentKey; // -2

	class HashFunc {
	public:
	HashFunc(const CompactHashBiTable &ht) : ht_(&ht) {}

	size_t operator()(I k) const { return hf(ht_->Key2T(k)); }
	private:
	const CompactHashBiTable *ht_;
	H hf;
	};

	class HashEqual {
	public:
	HashEqual(const CompactHashBiTable &ht) : ht_(&ht) {}

	bool operator()(I k1, I k2) const {
	return ht_->Key2T(k1) == ht_->Key2T(k2);
	}
	private:
	const CompactHashBiTable *ht_;
	};

	typedef unordered_set<I, HashFunc, HashEqual> KeyHashSet;

	const T &Key2T(I k) const {
	if (k == kEmptyKey)
	return empty_entry_;
	else if (k == kCurrentKey)
	return *current_entry_;
	else
	return id2entry_[k];
	}

	HashFunc hash_func_;
	HashEqual hash_equal_;
	KeyHashSet keys_;
	vector<T> id2entry_;
	const T empty_entry_;
	const T *current_entry_;

	DISALLOW_COPY_AND_ASSIGN(CompactHashBiTable);
	};

	template <class I, class T, class H>
	const I CompactHashBiTable<I, T, H>::kEmptyKey = -1;

	template <class I, class T, class H>
	const I CompactHashBiTable<I, T, H>::kCurrentKey = -2;


	// An implementation using a vector for the entry to ID mapping.
	// It is passed a function object FP that should fingerprint entries
	// uniquely to an integer that can used as a vector index. Normally,
	// VectorBiTable constructs the FP object. The user can instead
	// pass in this object; in that case, VectorBiTable takes its
	// ownership.
	template <class I, class T, class FP>
	class VectorBiTable {
	public:
	explicit VectorBiTable(FP *fp = 0) : fp_(fp ? fp : new FP()) {}

	~VectorBiTable() { delete fp_; }

	I FindId(const T &entry) {
	ssize_t fp = (*fp_)(entry);
	if (fp >= fp2id_.size())
	fp2id_.resize(fp + 1);
	I &id_ref = fp2id_[fp];
	if (id_ref == 0) { // T not found; store and assign it a new ID.
	id2entry_.push_back(entry);
	id_ref = id2entry_.size();
	}
	return id_ref - 1; // NB: id_ref = ID + 1
	}

	const T &FindEntry(I s) const { return id2entry_[s]; }

	I Size() const { return id2entry_.size(); }

	const FP &Fingerprint() const { return *fp_; }

	private:
	FP *fp_;
	vector<I> fp2id_;
	vector<T> id2entry_;

	DISALLOW_COPY_AND_ASSIGN(VectorBiTable);
	};


	// An implementation using a vector and a compact hash table. The
	// selecting functor S returns true for entries to be hashed in the
	// vector. The fingerprinting functor FP returns a unique fingerprint
	// for each entry to be hashed in the vector (these need to be
	// suitable for indexing in a vector). The hash functor H is used when
	// hashing entry into the compact hash table.
	template <class I, class T, class S, class FP, class H>
	class VectorHashBiTable {
	public:
	friend class HashFunc;
	friend class HashEqual;

	VectorHashBiTable(S s, FP fp, H *h,
	size_t vector_size = 0,
	size_t entry_size = 0)
	: selector_(s),
	fp_(fp),
	h_(h),
	hash_func_(*this),
	hash_equal_(*this),
	keys_(0, hash_func_, hash_equal_) {
	if (vector_size)
	fp2id_.reserve(vector_size);
	if (entry_size)
	id2entry_.reserve(entry_size);
	}

	~VectorHashBiTable() {
	delete selector_;
	delete fp_;
	delete h_;
	}

	I FindId(const T &entry) {
	if ((*selector_)(entry)) { // Use the vector if 'selector_(entry) == true'
	uint64 fp = (*fp_)(entry);
	if (fp2id_.size() <= fp)
	fp2id_.resize(fp + 1, 0);
	if (fp2id_[fp] == 0) {
	id2entry_.push_back(entry);
	fp2id_[fp] = id2entry_.size();
	}
	return fp2id_[fp] - 1; // NB: assoc_value = ID + 1
	} else { // Use the hash table otherwise.
	current_entry_ = &entry;
	typename KeyHashSet::const_iterator it = keys_.find(kCurrentKey);
	if (it == keys_.end()) {
	I key = id2entry_.size();
	id2entry_.push_back(entry);
	keys_.insert(key);
	return key;
	} else {
	return *it;
	}
	}
	}

	const T &FindEntry(I s) const {
	return id2entry_[s];
	}

	I Size() const { return id2entry_.size(); }

	const S &Selector() const { return *selector_; }

	const FP &Fingerprint() const { return *fp_; }

	const H &Hash() const { return *h_; }

	private:
	static const I kEmptyKey;
	static const I kCurrentKey;

	class HashFunc {
	public:
	HashFunc(const VectorHashBiTable &ht) : ht_(&ht) {}

	size_t operator()(I k) const { return (*(ht_->h_))(ht_->Key2Entry(k)); }
	private:
	const VectorHashBiTable *ht_;
	};

	class HashEqual {
	public:
	HashEqual(const VectorHashBiTable &ht) : ht_(&ht) {}

	bool operator()(I k1, I k2) const {
	return ht_->Key2Entry(k1) == ht_->Key2Entry(k2);
	}
	private:
	const VectorHashBiTable *ht_;
	};

	typedef unordered_set<I, HashFunc, HashEqual> KeyHashSet;

	const T &Key2Entry(I k) const {
	if (k == kEmptyKey)
	return empty_entry_;
	else if (k == kCurrentKey)
	return *current_entry_;
	else
	return id2entry_[k];
	}


	S *selector_; // Returns true if entry hashed into vector
	FP *fp_; // Fingerprint used when hashing entry into vector
	H *h_; // Hash function used when hashing entry into hash_set

	vector<T> id2entry_; // Maps state IDs to entry
	vector<I> fp2id_; // Maps entry fingerprints to IDs

	// Compact implementation of the hash table mapping entrys to
	// state IDs using the hash function 'h_'
	HashFunc hash_func_;
	HashEqual hash_equal_;
	KeyHashSet keys_;
	const T empty_entry_;
	const T *current_entry_;

	DISALLOW_COPY_AND_ASSIGN(VectorHashBiTable);
	};

	template <class I, class T, class S, class FP, class H>
	const I VectorHashBiTable<I, T, S, FP, H>::kEmptyKey = -1;

	template <class I, class T, class S, class FP, class H>
	const I VectorHashBiTable<I, T, S, FP, H>::kCurrentKey = -2;


	// An implementation using a hash map for the entry to ID
	// mapping. This version permits erasing of s. The entry T
	// must have == defined and its default constructor must produce a
	// entry that will never be seen. F is the hash function.
	template <class I, class T, class F>
	class ErasableBiTable {
	public:
	ErasableBiTable() : first_(0) {}

	I FindId(const T &entry) {
	I &id_ref = entry2id_[entry];
	if (id_ref == 0) { // T not found; store and assign it a new ID.
	id2entry_.push_back(entry);
	id_ref = id2entry_.size() + first_;
	}
	return id_ref - 1; // NB: id_ref = ID + 1
	}

	const T &FindEntry(I s) const { return id2entry_[s - first_]; }

	I Size() const { return id2entry_.size(); }

	void Erase(I s) {
	T &entry = id2entry_[s - first_];
	typename unordered_map<T, I, F>::iterator it =
	entry2id_.find(entry);
	entry2id_.erase(it);
	id2entry_[s - first_] = empty_entry_;
	while (!id2entry_.empty() && id2entry_.front() == empty_entry_) {
	id2entry_.pop_front();
	++first_;
	}
	}

	private:
	unordered_map<T, I, F> entry2id_;
	deque<T> id2entry_;
	const T empty_entry_;
	I first_; // I of first element in the deque;

	DISALLOW_COPY_AND_ASSIGN(ErasableBiTable);
	};

	} // namespace fst

	#endif // FST_LIB_BI_TABLE_H__