1 // collection.h 2 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // Copyright 2005-2010 Google, Inc. 16 // Author: riley (at) google.com (Michael Riley) 17 // 18 // \file 19 // Class to store a collection of ordered (multi-)sets with elements of type T. 20 21 #ifndef FST_EXTENSIONS_PDT_COLLECTION_H__ 22 #define FST_EXTENSIONS_PDT_COLLECTION_H__ 23 24 #include <algorithm> 25 #include <vector> 26 using std::vector; 27 28 #include <fst/bi-table.h> 29 30 namespace fst { 31 32 // Stores a collection of non-empty, ordered (multi-)sets with elements 33 // of type T. A default constructor, equality ==, and an STL-style 34 // hash class must be defined on the elements. Provides signed integer 35 // ID (of type I) of each unique set. The IDs are allocated starting 36 // from 0 in order. 37 template <class I, class T> 38 class Collection { 39 public: 40 struct Node { // Trie node 41 I node_id; // Root is kNoNodeId; 42 T element; 43 44 Node() : node_id(kNoNodeId), element(T()) {} 45 Node(I i, const T &t) : node_id(i), element(t) {} 46 47 bool operator==(const Node& n) const { 48 return n.node_id == node_id && n.element == element; 49 } 50 }; 51 52 struct NodeHash { 53 size_t operator()(const Node &n) const { 54 return n.node_id + hash_(n.element) * kPrime; 55 } 56 }; 57 58 typedef CompactHashBiTable<I, Node, NodeHash> NodeTable; 59 60 class SetIterator { 61 public: 62 SetIterator(I id, Node node, NodeTable *node_table) 63 :id_(id), node_(node), node_table_(node_table) {} 64 65 bool Done() const { return id_ == kNoNodeId; } 66 67 const T &Element() const { return node_.element; } 68 69 void Next() { 70 id_ = node_.node_id; 71 if (id_ != kNoNodeId) 72 node_ = node_table_->FindEntry(id_); 73 } 74 75 private: 76 I id_; // Iterator set node id 77 Node node_; // Iterator set node 78 NodeTable *node_table_; 79 }; 80 81 Collection() {} 82 83 // Lookups integer ID from ordered multi-set. If it doesn't exist 84 // and 'insert' is true, then adds it. Otherwise returns -1. 85 I FindId(const vector<T> &set, bool insert = true) { 86 I node_id = kNoNodeId; 87 for (ssize_t i = set.size() - 1; i >= 0; --i) { 88 Node node(node_id, set[i]); 89 node_id = node_table_.FindId(node, insert); 90 if (node_id == -1) break; 91 } 92 return node_id; 93 } 94 95 // Finds ordered (multi-)set given integer ID. Returns set iterator 96 // to traverse result. 97 SetIterator FindSet(I id) { 98 if (id < 0 || id >= node_table_.Size()) { 99 return SetIterator(kNoNodeId, Node(kNoNodeId, T()), &node_table_); 100 } else { 101 return SetIterator(id, node_table_.FindEntry(id), &node_table_); 102 } 103 } 104 105 I Size() const { return node_table_.Size(); } 106 107 private: 108 static const I kNoNodeId; 109 static const size_t kPrime; 110 static std::tr1::hash<T> hash_; 111 112 NodeTable node_table_; 113 114 DISALLOW_COPY_AND_ASSIGN(Collection); 115 }; 116 117 template<class I, class T> const I Collection<I, T>::kNoNodeId = -1; 118 119 template <class I, class T> const size_t Collection<I, T>::kPrime = 7853; 120 121 template <class I, class T> std::tr1::hash<T> Collection<I, T>::hash_; 122 123 } // namespace fst 124 125 #endif // FST_EXTENSIONS_PDT_COLLECTION_H__ 126
