collection.h revision 3da1eb108d36da35333b2d655202791af854996b 
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>
26using std::vector;
27
28#include <fst/bi-table.h>
29
30namespace 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.
37template <class I, class T>
38class 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
117template<class I, class T> const I Collection<I, T>::kNoNodeId = -1;
118
119template <class I, class T> const size_t Collection<I, T>::kPrime = 7853;
120
121template <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