Common/interface/ValueMap.h

0001 #ifndef DataFormats_Common_ValueMap_h
0002 #define DataFormats_Common_ValueMap_h
0003 /* \class ValueMap<T>
0004  *
0005  * \author Luca Lista, INFN
0006  *
0007  *
0008  */
0009
0010 #include "DataFormats/Common/interface/CMS_CLASS_VERSION.h"
0011 #include "DataFormats/Provenance/interface/ProductID.h"
0012 #include "FWCore/Utilities/interface/EDMException.h"
0013 #include <vector>
0014 #include <map>
0015 #include <iterator>
0016 #include <algorithm>
0017 #include <cstddef>
0018
0019 namespace edm {
0020   namespace helper {
0021     template <typename Map>
0022     class Filler {
0023     private:
0024       typedef std::vector<size_t> index_vector;
0025       typedef std::vector<typename Map::value_type> value_vector;
0026       typedef std::map<ProductID, value_vector> value_map;
0027       typedef typename Map::offset offset;
0028       typedef typename Map::id_offset_vector id_offset_vector;
0029
0030     public:
0031       explicit Filler(Map& map) : map_(map), totSize_(0) { add(map); }
0032       void add(const Map& map) {
0033         if (map.empty())
0034           return;
0035         typename id_offset_vector::const_iterator j = map.ids_.begin();
0036         const typename id_offset_vector::const_iterator end = map.ids_.end();
0037         size_t i = 0;
0038         const size_t size = map.values_.size();
0039         // std::pair<ProductID, offset> id = *j;
0040         do {
0041           ProductID id = j->first;
0042           ++j;
0043           size_t max = (j == end ? size : j->second);
0044           typename value_map::iterator f = values_.find(id);
0045           if (f != values_.end())
0046             throwAdd();
0047           value_vector& values = values_.insert(std::make_pair(id, value_vector())).first->second;
0048           while (i != max)
0049             values.push_back(map.values_[i++]);
0050         } while (j != end);
0051       }
0052       template <typename H, typename I>
0053       void insert(const H& h, I begin, I end) {
0054         ProductID id = h.id();
0055         size_t size = h->size(), sizeIt = end - begin;
0056         if (sizeIt != size)
0057           throwFillSize();
0058         typename value_map::const_iterator f = values_.find(id);
0059         if (f != values_.end())
0060           throwFillID(id);
0061         value_vector& values = values_.insert(make_pair(id, value_vector(size))).first->second;
0062         std::copy(begin, end, values.begin());
0063         totSize_ += size;
0064       }
0065       void fill() {
0066         map_.clear();
0067         offset off = 0;
0068         map_.ids_.reserve(values_.size());
0069         map_.values_.reserve(totSize_);
0070         for (typename value_map::const_iterator i = values_.begin(); i != values_.end(); ++i) {
0071           ProductID id = i->first;
0072           map_.ids_.push_back(std::make_pair(id, off));
0073           const value_vector& values = i->second;
0074           for (typename value_vector::const_iterator j = values.begin(); j != values.end(); ++j) {
0075             map_.values_.push_back(*j);
0076             ++off;
0077           }
0078         }
0079         map_.shrink_to_fit();
0080       }
0081
0082     protected:
0083       Map& map_;
0084
0085     private:
0086       value_map values_;
0087       size_t totSize_;
0088
0089       void throwFillSize() const {
0090         Exception::throwThis(errors::InvalidReference,
0091                              "ValueMap::Filler: handle and reference "
0092                              "collections should the same size\n");
0093       }
0094       void throwFillID(ProductID id) const {
0095         Exception e(errors::InvalidReference);
0096         e << "index map has already been filled for id: " << id << "\n";
0097         e.raise();
0098       }
0099       void throwAdd() const {
0100         Exception::throwThis(errors::InvalidReference,
0101                              "ValueMap: trying to add entries for an already existing product\n");
0102       }
0103     };
0104   }  // namespace helper
0105
0106   template <typename T>
0107   class ValueMap {
0108   public:
0109     typedef T value_type;
0110     typedef std::vector<value_type> container;
0111     typedef unsigned int offset;
0112     typedef std::vector<std::pair<ProductID, offset> > id_offset_vector;
0113     typedef typename container::reference reference_type;
0114     typedef typename container::const_reference const_reference_type;
0115
0116     ValueMap() {}
0117
0118     void swap(ValueMap& other) {
0119       values_.swap(other.values_);
0120       ids_.swap(other.ids_);
0121     }
0122
0123     template <typename RefKey>
0124     const_reference_type operator[](const RefKey& r) const {
0125       return get(r.id(), r.key());
0126     }
0127     // raw index of a given (id,key) pair
0128     size_t rawIndexOf(ProductID id, size_t idx) const {
0129       typename id_offset_vector::const_iterator f = getIdOffset(id);
0130       if (f == ids_.end())
0131         throwNotExisting();
0132       offset off = f->second;
0133       size_t j = off + idx;
0134       if (j >= values_.size())
0135         throwIndexBound();
0136       return j;
0137     }
0138     const_reference_type get(ProductID id, size_t idx) const { return values_[rawIndexOf(id, idx)]; }
0139     template <typename RefKey>
0140     reference_type operator[](const RefKey& r) {
0141       return get(r.id(), r.key());
0142     }
0143     reference_type get(ProductID id, size_t idx) { return values_[rawIndexOf(id, idx)]; }
0144
0145     ValueMap<T>& operator+=(const ValueMap<T>& o) {
0146       add(o);
0147       return *this;
0148     }
0149     bool contains(ProductID id) const { return getIdOffset(id) != ids_.end(); }
0150     size_t size() const { return values_.size(); }
0151     size_t idSize() const { return ids_.size(); }
0152     bool empty() const { return values_.empty(); }
0153     void clear() {
0154       values_.clear();
0155       ids_.clear();
0156     }
0157     void shrink_to_fit() {
0158       ids_.shrink_to_fit();
0159       values_.shrink_to_fit();
0160     }
0161
0162     typedef helper::Filler<ValueMap<T> > Filler;
0163
0164     struct const_iterator {
0165       typedef ptrdiff_t difference_type;
0166       const_iterator() : values_(nullptr) {}
0167       ProductID id() const { return i_->first; }
0168       typename container::const_iterator begin() const { return values_->begin() + i_->second; }
0169       typename container::const_iterator end() const {
0170         if (i_ == end_)
0171           return values_->end();
0172         id_offset_vector::const_iterator end = i_;
0173         ++end;
0174         if (end == end_)
0175           return values_->end();
0176         return values_->begin() + end->second;
0177       }
0178       size_t size() const { return end() - begin(); }
0179       const T& operator[](size_t i) { return *(begin() + i); }
0180       const_iterator& operator++() {
0181         ++i_;
0182         return *this;
0183       }
0184       const_iterator operator++(int) {
0185         const_iterator ci = *this;
0186         ++i_;
0187         return ci;
0188       }
0189       const_iterator& operator--() {
0190         --i_;
0191         return *this;
0192       }
0193       const_iterator operator--(int) {
0194         const_iterator ci = *this;
0195         --i_;
0196         return ci;
0197       }
0198       difference_type operator-(const const_iterator& o) const { return i_ - o.i_; }
0199       const_iterator operator+(difference_type n) const { return const_iterator(i_ + n, end_, values_); }
0200       const_iterator operator-(difference_type n) const { return const_iterator(i_ - n, end_, values_); }
0201       bool operator<(const const_iterator& o) const { return i_ < o.i_; }
0202       bool operator==(const const_iterator& ci) const { return i_ == ci.i_; }
0203       bool operator!=(const const_iterator& ci) const { return i_ != ci.i_; }
0204       const_iterator& operator+=(difference_type d) {
0205         i_ += d;
0206         return *this;
0207       }
0208       const_iterator& operator-=(difference_type d) {
0209         i_ -= d;
0210         return *this;
0211       }
0212
0213     private:
0214       const_iterator(const id_offset_vector::const_iterator& i_,
0215                      const id_offset_vector::const_iterator& end,
0216                      const container* values)
0217           : values_(values), i_(i_), end_(end) {}
0218       const container* values_;
0219       id_offset_vector::const_iterator i_, end_;
0220       friend class ValueMap<T>;
0221     };
0222
0223     const_iterator begin() const { return const_iterator(ids_.begin(), ids_.end(), &values_); }
0224     const_iterator end() const { return const_iterator(ids_.end(), ids_.end(), &values_); }
0225
0226     /// meant to be used in AssociativeIterator, not by the ordinary user
0227     const id_offset_vector& ids() const { return ids_; }
0228     /// meant to be used in AssociativeIterator, not by the ordinary user
0229     const_reference_type get(size_t idx) const { return values_[idx]; }
0230
0231     //Used by ROOT storage
0232     CMS_CLASS_VERSION(10)
0233
0234   protected:
0235     container values_;
0236     id_offset_vector ids_;
0237
0238     typename id_offset_vector::const_iterator getIdOffset(ProductID id) const {
0239       typename id_offset_vector::const_iterator i = std::lower_bound(ids_.begin(), ids_.end(), id, IDComparator());
0240       if (i == ids_.end())
0241         return i;
0242       return i->first == id ? i : ids_.end();
0243     }
0244
0245     void throwIndexBound() const {
0246       Exception::throwThis(errors::InvalidReference, "ValueMap: index out of upper boundary\n");
0247     }
0248
0249   private:
0250     struct IDComparator {
0251       bool operator()(const std::pair<ProductID, offset>& p, const ProductID& id) { return p.first < id; }
0252     };
0253     void throwNotExisting() const {
0254       Exception::throwThis(errors::InvalidReference, "ValueMap: no associated value for given product and index\n");
0255     }
0256
0257     void add(const ValueMap<T>& o) {
0258       Filler filler(*this);
0259       filler.add(o);
0260       filler.fill();
0261     }
0262
0263     friend class helper::Filler<ValueMap<T> >;
0264   };
0265
0266   template <typename T>
0267   inline ValueMap<T> operator+(const ValueMap<T>& a1, const ValueMap<T>& a2) {
0268     ValueMap<T> a = a1;
0269     a += a2;
0270     return a;
0271   }
0272
0273   // Free swap function
0274   template <typename T>
0275   inline void swap(ValueMap<T>& lhs, ValueMap<T>& rhs) {
0276     lhs.swap(rhs);
0277   }
0278
0279 }  // namespace edm
0280 #endif