Common/interface/MapOfVectors.h

0001 #ifndef DataFormats_Common_MapOfVectors_h
0002 #define DataFormats_Common_MapOfVectors_h
0003
0004 #include "FWCore/Utilities/interface/thread_safety_macros.h"
0005 #include <vector>
0006 #include <map>
0007
0008 #include <boost/range/iterator_range.hpp>
0009 #include <boost/iterator/iterator_facade.hpp>
0010
0011 class TestMapOfVectors;
0012
0013 namespace edm {
0014
0015   /* a linearized read-only map-of vectors
0016    NOTE: The iterator for MapOfVectors an not safely be used across threads, even if only const methods are called.
0017    */
0018   template <typename K, typename T>
0019   class MapOfVectors {
0020   public:
0021     typedef MapOfVectors<K, T> self;
0022     typedef std::map<K, std::vector<T> > TheMap;
0023
0024     typedef unsigned int size_type;
0025
0026     typedef std::vector<K> Keys;
0027     typedef std::vector<size_type> Offsets;
0028     typedef std::vector<T> Data;
0029
0030     typedef typename Keys::const_iterator key_iterator;
0031     typedef Offsets::const_iterator offset_iterator;
0032     typedef typename Data::const_iterator data_iterator;
0033
0034     typedef boost::iterator_range<data_iterator> range;
0035
0036     typedef std::pair<K, range> Pair;
0037
0038     class Iter : public boost::iterator_facade<Iter, Pair const, boost::forward_traversal_tag> {
0039     public:
0040       typedef Iter self;
0041       Iter() {}
0042
0043       explicit Iter(key_iterator k, offset_iterator o, std::vector<T> const& d) : key(k), off(o), data(d.begin()) {}
0044
0045     private:
0046       friend class boost::iterator_core_access;
0047
0048       void increment() {
0049         ++key;
0050         ++off;
0051       }
0052
0053       bool equal(self const& other) const { return this->key == other.key; }
0054
0055       Pair const& dereference() const {
0056         // FIXME can be optimized...
0057         cache.first = *key;
0058         cache.second = range(data + (*off), data + (*(off + 1)));
0059         return cache;
0060       }
0061
0062       key_iterator key;
0063       offset_iterator off;
0064       data_iterator data;
0065       //This class is not intended to be used across threads
0066       CMS_SA_ALLOW mutable Pair cache;
0067     };
0068
0069     typedef Iter const_iterator;
0070
0071     range emptyRange() const { return range(m_data.end(), m_data.end()); }
0072
0073     MapOfVectors() : m_offsets(1, 0) {}
0074
0075     MapOfVectors(TheMap const& it) {
0076       m_keys.reserve(it.size());
0077       m_offsets.reserve(it.size() + 1);
0078       m_offsets.push_back(0);
0079       size_type tot = 0;
0080       for (typename TheMap::const_iterator p = it.begin(); p != it.end(); ++p)
0081         tot += (*p).second.size();
0082       m_data.reserve(tot);
0083       for (typename TheMap::const_iterator p = it.begin(); p != it.end(); ++p)
0084         loadNext((*p).first, (*p).second);
0085     }
0086
0087     void loadNext(K const& k, std::vector<T> const& v) {
0088       m_keys.push_back(k);
0089       m_data.resize(m_offsets.back() + v.size());
0090       std::copy(v.begin(), v.end(), m_data.begin() + m_offsets.back());
0091       m_offsets.push_back(m_data.size());
0092     }
0093
0094     size_type size() const { return m_keys.size(); }
0095
0096     bool empty() const { return m_keys.empty(); }
0097
0098     key_iterator findKey(K const& k) const {
0099       std::pair<key_iterator, key_iterator> p = std::equal_range(m_keys.begin(), m_keys.end(), k);
0100       return (p.first != p.second) ? p.first : m_keys.end();
0101     }
0102
0103     size_type offset(K const& k) const {
0104       key_iterator p = findKey(k);
0105       if (p == m_keys.end())
0106         return m_data.size();
0107       return m_offsets[p - m_keys.begin()];
0108     }
0109
0110     range find(K const& k) const {
0111       key_iterator p = findKey(k);
0112       if (p == m_keys.end())
0113         return emptyRange();
0114       size_type loc = p - m_keys.begin();
0115       data_iterator b = m_data.begin() + m_offsets[loc];
0116       data_iterator e = m_data.begin() + m_offsets[loc + 1];
0117       return range(b, e);
0118     }
0119
0120     ///The iterator returned can not safely be used across threads
0121     const_iterator begin() const { return const_iterator(m_keys.begin(), m_offsets.begin(), m_data); }
0122
0123     const_iterator end() const { return const_iterator(m_keys.end(), m_offsets.begin() + m_keys.size(), m_data); }
0124
0125     void swap(MapOfVectors& other) {
0126       m_keys.swap(other.m_keys);
0127       m_offsets.swap(other.m_offsets);
0128       m_data.swap(other.m_data);
0129     }
0130
0131   private:
0132     //for testing
0133     friend class ::TestMapOfVectors;
0134
0135     std::vector<K> m_keys;
0136     std::vector<size_type> m_offsets;
0137     std::vector<T> m_data;
0138   };
0139
0140   // Free swap function
0141   template <typename K, typename T>
0142   inline void swap(MapOfVectors<K, T>& lhs, MapOfVectors<K, T>& rhs) {
0143     lhs.swap(rhs);
0144   }
0145
0146 }  // namespace edm
0147
0148 #endif  // DatFormats_Common_MapOfVectors_h