blob: 72c01cb307998a764112977e8f6c597c37830db8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#pragma once
#ifndef NUMBEREDSET_H_
#define NUMBEREDSET_H_
#include "Exception.h"
#include <boost/unordered_map.hpp>
#include <limits>
#include <sstream>
#include <vector>
namespace moses {
// Stores a set of elements of type T, each of which is allocated an integral
// ID of type IdType. IDs are contiguous starting at 0. Elements cannot be
// removed.
template<typename T, typename IdType=size_t>
class NumberedSet {
private:
typedef boost::unordered_map<T, IdType> ElementToIdMap;
typedef std::vector<const T *> IdToElementMap;
public:
typedef typename IdToElementMap::const_iterator const_iterator;
NumberedSet() {}
const_iterator begin() const { return m_idToElement.begin(); }
const_iterator end() const { return m_idToElement.end(); }
// Static value
static IdType nullID() { return std::numeric_limits<IdType>::max(); }
bool empty() const { return m_idToElement.empty(); }
size_t size() const { return m_idToElement.size(); }
IdType lookup(const T &) const;
const T &lookup(IdType) const;
// Insert the given object and return its ID.
IdType insert(const T &);
private:
ElementToIdMap m_elementToId;
IdToElementMap m_idToElement;
};
template<typename T, typename IdType>
IdType NumberedSet<T, IdType>::lookup(const T &s) const {
typename ElementToIdMap::const_iterator p = m_elementToId.find(s);
return (p == m_elementToId.end()) ? nullID() : p->second;
}
template<typename T, typename IdType>
const T &NumberedSet<T, IdType>::lookup(IdType id) const {
if (id < 0 || id >= m_idToElement.size()) {
std::ostringstream msg;
msg << "Value not found: " << id;
throw Exception(msg.str());
}
return *(m_idToElement[id]);
}
template<typename T, typename IdType>
IdType NumberedSet<T, IdType>::insert(const T &x) {
std::pair<T, IdType> value(x, m_idToElement.size());
std::pair<typename ElementToIdMap::iterator, bool> result =
m_elementToId.insert(value);
if (result.second) {
// x is a new element.
m_idToElement.push_back(&result.first->first);
}
return result.first->second;
}
} // namespace moses
#endif
|
