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@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 
NodeNode44     Node() : node_id(kNoNodeId), element(T()) {}
NodeNode45     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 {
operatorNodeHash53     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:
SetIterator(I id,Node node,NodeTable * node_table)62     SetIterator(I id, Node node, NodeTable *node_table)
63         :id_(id), node_(node), node_table_(node_table) {}
64 
Done()65     bool Done() const { return id_ == kNoNodeId; }
66 
Element()67     const T &Element() const { return node_.element; }
68 
Next()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 
Collection()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.
FindSet(I id)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 
Size()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