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     ValueMap& operator=(ValueMap const& rhs) {
0124       ValueMap temp(rhs);
0125       this->swap(temp);
0126       return *this;
0127     }
0128
0129     template <typename RefKey>
0130     const_reference_type operator[](const RefKey& r) const {
0131       return get(r.id(), r.key());
0132     }
0133     // raw index of a given (id,key) pair
0134     size_t rawIndexOf(ProductID id, size_t idx) const {
0135       typename id_offset_vector::const_iterator f = getIdOffset(id);
0136       if (f == ids_.end())
0137         throwNotExisting();
0138       offset off = f->second;
0139       size_t j = off + idx;
0140       if (j >= values_.size())
0141         throwIndexBound();
0142       return j;
0143     }
0144     const_reference_type get(ProductID id, size_t idx) const { return values_[rawIndexOf(id, idx)]; }
0145     template <typename RefKey>
0146     reference_type operator[](const RefKey& r) {
0147       return get(r.id(), r.key());
0148     }
0149     reference_type get(ProductID id, size_t idx) { return values_[rawIndexOf(id, idx)]; }
0150
0151     ValueMap<T>& operator+=(const ValueMap<T>& o) {
0152       add(o);
0153       return *this;
0154     }
0155     bool contains(ProductID id) const { return getIdOffset(id) != ids_.end(); }
0156     size_t size() const { return values_.size(); }
0157     size_t idSize() const { return ids_.size(); }
0158     bool empty() const { return values_.empty(); }
0159     void clear() {
0160       values_.clear();
0161       ids_.clear();
0162     }
0163     void shrink_to_fit() {
0164       ids_.shrink_to_fit();
0165       values_.shrink_to_fit();
0166     }
0167
0168     typedef helper::Filler<ValueMap<T> > Filler;
0169
0170     struct const_iterator {
0171       typedef ptrdiff_t difference_type;
0172       const_iterator() : values_(nullptr) {}
0173       ProductID id() const { return i_->first; }
0174       typename container::const_iterator begin() const { return values_->begin() + i_->second; }
0175       typename container::const_iterator end() const {
0176         if (i_ == end_)
0177           return values_->end();
0178         id_offset_vector::const_iterator end = i_;
0179         ++end;
0180         if (end == end_)
0181           return values_->end();
0182         return values_->begin() + end->second;
0183       }
0184       size_t size() const { return end() - begin(); }
0185       const T& operator[](size_t i) { return *(begin() + i); }
0186       const_iterator& operator++() {
0187         ++i_;
0188         return *this;
0189       }
0190       const_iterator operator++(int) {
0191         const_iterator ci = *this;
0192         ++i_;
0193         return ci;
0194       }
0195       const_iterator& operator--() {
0196         --i_;
0197         return *this;
0198       }
0199       const_iterator operator--(int) {
0200         const_iterator ci = *this;
0201         --i_;
0202         return ci;
0203       }
0204       difference_type operator-(const const_iterator& o) const { return i_ - o.i_; }
0205       const_iterator operator+(difference_type n) const { return const_iterator(i_ + n, end_, values_); }
0206       const_iterator operator-(difference_type n) const { return const_iterator(i_ - n, end_, values_); }
0207       bool operator<(const const_iterator& o) const { return i_ < o.i_; }
0208       bool operator==(const const_iterator& ci) const { return i_ == ci.i_; }
0209       bool operator!=(const const_iterator& ci) const { return i_ != ci.i_; }
0210       const_iterator& operator+=(difference_type d) {
0211         i_ += d;
0212         return *this;
0213       }
0214       const_iterator& operator-=(difference_type d) {
0215         i_ -= d;
0216         return *this;
0217       }
0218
0219     private:
0220       const_iterator(const id_offset_vector::const_iterator& i_,
0221                      const id_offset_vector::const_iterator& end,
0222                      const container* values)
0223           : values_(values), i_(i_), end_(end) {}
0224       const container* values_;
0225       id_offset_vector::const_iterator i_, end_;
0226       friend class ValueMap<T>;
0227     };
0228
0229     const_iterator begin() const { return const_iterator(ids_.begin(), ids_.end(), &values_); }
0230     const_iterator end() const { return const_iterator(ids_.end(), ids_.end(), &values_); }
0231
0232     /// meant to be used in AssociativeIterator, not by the ordinary user
0233     const id_offset_vector& ids() const { return ids_; }
0234     /// meant to be used in AssociativeIterator, not by the ordinary user
0235     const_reference_type get(size_t idx) const { return values_[idx]; }
0236
0237     //Used by ROOT storage
0238     CMS_CLASS_VERSION(10)
0239
0240   protected:
0241     container values_;
0242     id_offset_vector ids_;
0243
0244     typename id_offset_vector::const_iterator getIdOffset(ProductID id) const {
0245       typename id_offset_vector::const_iterator i = std::lower_bound(ids_.begin(), ids_.end(), id, IDComparator());
0246       if (i == ids_.end())
0247         return i;
0248       return i->first == id ? i : ids_.end();
0249     }
0250
0251     void throwIndexBound() const {
0252       Exception::throwThis(errors::InvalidReference, "ValueMap: index out of upper boundary\n");
0253     }
0254
0255   private:
0256     struct IDComparator {
0257       bool operator()(const std::pair<ProductID, offset>& p, const ProductID& id) { return p.first < id; }
0258     };
0259     void throwNotExisting() const {
0260       Exception::throwThis(errors::InvalidReference, "ValueMap: no associated value for given product and index\n");
0261     }
0262
0263     void add(const ValueMap<T>& o) {
0264       Filler filler(*this);
0265       filler.add(o);
0266       filler.fill();
0267     }
0268
0269     friend class helper::Filler<ValueMap<T> >;
0270   };
0271
0272   template <typename T>
0273   inline ValueMap<T> operator+(const ValueMap<T>& a1, const ValueMap<T>& a2) {
0274     ValueMap<T> a = a1;
0275     a += a2;
0276     return a;
0277   }
0278
0279   // Free swap function
0280   template <typename T>
0281   inline void swap(ValueMap<T>& lhs, ValueMap<T>& rhs) {
0282     lhs.swap(rhs);
0283   }
0284
0285 }  // namespace edm
0286 #endif