FST  openfst-1.7.2
OpenFst Library
collection.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // Class to store a collection of ordered (multi-)sets with elements of type T.
5 
6 #ifndef FST_EXTENSIONS_PDT_COLLECTION_H_
7 #define FST_EXTENSIONS_PDT_COLLECTION_H_
8 
9 #include <functional>
10 #include <vector>
11 
12 #include <fst/log.h>
13 #include <fst/bi-table.h>
14 
15 namespace fst {
16 
17 // Stores a collection of non-empty, ordered (multi-)sets with elements of type
18 // T. A default constructor, operator==, and an STL-style hash functor must be
19 // defined on the elements. Provides signed integer ID (of type I) for each
20 // unique set. The IDs are allocated starting from 0 in order.
21 template <class I, class T>
22 class Collection {
23  public:
24  struct Node { // Trie node.
25  I node_id; // Root is kNoNodeId;
27 
28  Node() : node_id(kNoNodeId), element(T()) {}
29 
30  Node(I i, const T &t) : node_id(i), element(t) {}
31 
32  bool operator==(const Node &n) const {
33  return n.node_id == node_id && n.element == element;
34  }
35  };
36 
37  struct NodeHash {
38  size_t operator()(const Node &n) const {
39  static constexpr auto kPrime = 7853;
40  return n.node_id + hash_(n.element) * kPrime;
41  }
42  };
43 
45 
46  class SetIterator {
47  public:
48  SetIterator(I id, Node node, NodeTable *node_table)
49  : id_(id), node_(node), node_table_(node_table) {}
50 
51  bool Done() const { return id_ == kNoNodeId; }
52 
53  const T &Element() const { return node_.element; }
54 
55  void Next() {
56  id_ = node_.node_id;
57  if (id_ != kNoNodeId) node_ = node_table_->FindEntry(id_);
58  }
59 
60  private:
61  I id_; // Iterator set node ID.
62  Node node_; // Iterator set node.
63  NodeTable *node_table_;
64  };
65 
67 
68  // Looks up integer ID from ordered multi-se, and if it doesn't exist and
69  // insert is true, then adds it. Otherwise returns -1.
70  I FindId(const std::vector<T> &set, bool insert = true) {
71  I node_id = kNoNodeId;
72  for (ssize_t i = set.size() - 1; i >= 0; --i) {
73  Node node(node_id, set[i]);
74  node_id = node_table_.FindId(node, insert);
75  if (node_id == -1) break;
76  }
77  return node_id;
78  }
79 
80  // Finds ordered (multi-)set given integer ID. Returns set iterator to
81  // traverse result.
82  SetIterator FindSet(I id) {
83  if (id < 0 || id >= node_table_.Size()) {
84  return SetIterator(kNoNodeId, Node(kNoNodeId, T()), &node_table_);
85  } else {
86  return SetIterator(id, node_table_.FindEntry(id), &node_table_);
87  }
88  }
89 
90  I Size() const { return node_table_.Size(); }
91 
92  private:
93  static constexpr I kNoNodeId = -1;
94  static const std::hash<T> hash_;
95 
96  NodeTable node_table_;
97 };
98 
99 template <class I, class T>
100 constexpr I Collection<I, T>::kNoNodeId;
101 
102 template <class I, class T>
103 const std::hash<T> Collection<I, T>::hash_ = {};
104 
105 } // namespace fst
106 
107 #endif // FST_EXTENSIONS_PDT_COLLECTION_H_
I FindId(const std::vector< T > &set, bool insert=true)
Definition: collection.h:70
size_t operator()(const Node &n) const
Definition: collection.h:38
SetIterator(I id, Node node, NodeTable *node_table)
Definition: collection.h:48
SetIterator FindSet(I id)
Definition: collection.h:82
I Size() const
Definition: collection.h:90
Node(I i, const T &t)
Definition: collection.h:30
const T & Element() const
Definition: collection.h:53
bool operator==(const Node &n) const
Definition: collection.h:32