|
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
#ifndef DataFormats_Common_MapOfVectors_h
#define DataFormats_Common_MapOfVectors_h
#include "FWCore/Utilities/interface/thread_safety_macros.h"
#include <vector>
#include <map>
#include <boost/range/iterator_range.hpp>
#include <boost/iterator/iterator_facade.hpp>
class TestMapOfVectors;
namespace edm {
/* a linearized read-only map-of vectors
NOTE: The iterator for MapOfVectors an not safely be used across threads, even if only const methods are called.
*/
template <typename K, typename T>
class MapOfVectors {
public:
typedef MapOfVectors<K, T> self;
typedef std::map<K, std::vector<T> > TheMap;
typedef unsigned int size_type;
typedef std::vector<K> Keys;
typedef std::vector<size_type> Offsets;
typedef std::vector<T> Data;
typedef typename Keys::const_iterator key_iterator;
typedef Offsets::const_iterator offset_iterator;
typedef typename Data::const_iterator data_iterator;
typedef boost::iterator_range<data_iterator> range;
typedef std::pair<K, range> Pair;
class Iter : public boost::iterator_facade<Iter, Pair const, boost::forward_traversal_tag> {
public:
typedef Iter self;
Iter() {}
explicit Iter(key_iterator k, offset_iterator o, std::vector<T> const& d) : key(k), off(o), data(d.begin()) {}
private:
friend class boost::iterator_core_access;
void increment() {
++key;
++off;
}
bool equal(self const& other) const { return this->key == other.key; }
Pair const& dereference() const {
// FIXME can be optimized...
cache.first = *key;
cache.second = range(data + (*off), data + (*(off + 1)));
return cache;
}
key_iterator key;
offset_iterator off;
data_iterator data;
//This class is not intended to be used across threads
CMS_SA_ALLOW mutable Pair cache;
};
typedef Iter const_iterator;
range emptyRange() const { return range(m_data.end(), m_data.end()); }
MapOfVectors() : m_offsets(1, 0) {}
MapOfVectors(TheMap const& it) {
m_keys.reserve(it.size());
m_offsets.reserve(it.size() + 1);
m_offsets.push_back(0);
size_type tot = 0;
for (typename TheMap::const_iterator p = it.begin(); p != it.end(); ++p)
tot += (*p).second.size();
m_data.reserve(tot);
for (typename TheMap::const_iterator p = it.begin(); p != it.end(); ++p)
loadNext((*p).first, (*p).second);
}
void loadNext(K const& k, std::vector<T> const& v) {
m_keys.push_back(k);
m_data.resize(m_offsets.back() + v.size());
std::copy(v.begin(), v.end(), m_data.begin() + m_offsets.back());
m_offsets.push_back(m_data.size());
}
size_type size() const { return m_keys.size(); }
bool empty() const { return m_keys.empty(); }
key_iterator findKey(K const& k) const {
std::pair<key_iterator, key_iterator> p = std::equal_range(m_keys.begin(), m_keys.end(), k);
return (p.first != p.second) ? p.first : m_keys.end();
}
size_type offset(K const& k) const {
key_iterator p = findKey(k);
if (p == m_keys.end())
return m_data.size();
return m_offsets[p - m_keys.begin()];
}
range find(K const& k) const {
key_iterator p = findKey(k);
if (p == m_keys.end())
return emptyRange();
size_type loc = p - m_keys.begin();
data_iterator b = m_data.begin() + m_offsets[loc];
data_iterator e = m_data.begin() + m_offsets[loc + 1];
return range(b, e);
}
///The iterator returned can not safely be used across threads
const_iterator begin() const { return const_iterator(m_keys.begin(), m_offsets.begin(), m_data); }
const_iterator end() const { return const_iterator(m_keys.end(), m_offsets.begin() + m_keys.size(), m_data); }
void swap(MapOfVectors& other) {
m_keys.swap(other.m_keys);
m_offsets.swap(other.m_offsets);
m_data.swap(other.m_data);
}
private:
//for testing
friend class ::TestMapOfVectors;
std::vector<K> m_keys;
std::vector<size_type> m_offsets;
std::vector<T> m_data;
};
// Free swap function
template <typename K, typename T>
inline void swap(MapOfVectors<K, T>& lhs, MapOfVectors<K, T>& rhs) {
lhs.swap(rhs);
}
} // namespace edm
#endif // DatFormats_Common_MapOfVectors_h
|