Common/interface/MultiAssociation.h

0001 #ifndef DataFormats_Common_MultiAssociation_h
0002 #define DataFormats_Common_MultiAssociation_h
0003 /* \class MultiAssociation
0004  *
0005  * \author Giovanni Petrucciani, SNS Pisa and CERN PH-CMG
0006  *
0007  * One-to-Many variant of edm::Association<C> / edm::ValueMap<T>,
0008  *
0009  * Given a key, it will return a range of iterators within a collection (fast access), or collection by value (slow access mode)
0010  *
0011  * The range of iterators is handled through boost::sub_range, so it should feel like a collection:
0012  *   1) it has a '::const_iterator', a 'begin()' and an 'end()'
0013  *   2) it has a 'size()' and an 'empty()'
0014  *   3) it has a 'front()', 'back()'
0015  *   4) it works as an array  (i.e. you can use range[index] to pick an element)
0016  *   5) if your MultiAssociation is not const, you can modify the values associated to each key
0017  *      (but you can't push_back new values for a given key)
0018  * ( details at http://www.boost.org/doc/libs/1_37_0/libs/range/doc/utility_class.html#sub_range )
0019  *
0020  * The collection can be a RefVector<C> (to work a la edm::Association<C>), a std::vector<T> (to work a la ValueMap<T>), a PtrVector<T>...
0021  * The collection must be compatible with sub_range and support a few other features. Usually you need:
0022  *  - that it has a default constructor
0023  *  - that it has a const_iterator, and "begin() const" returns such const_iterator.
0024  *  - that it has an iterator, and "begin()" returns such iterator (note: it doesn't have to be writable, it can be const as well)
0025  *  - that it has a swap method
0026  *  - that 'begin() + offset' is legal (and fast, otherwise this thing is will be awfully slow)
0027  *  - that you can push_back on a C the * of a C::const_iterator. Namely this should be legal
0028  *    <code>
0029  *       C::const_iterator it = ..something..
0030  *       C someOtherC = ...
0031  *       someOtherC.push_back(*it);
0032  *    </code>
0033  *
0034  * It can be filled through a FastFiller or a LazyFiller.
0035  * FastFiller is probably faster, but has many constraints:
0036  * - you must fill only one product id at time
0037  * - you must fill items in strict key order
0038  * - there is no way to abort a filling operation
0039  * Try LazyFiller first, unless you're doing some sort of batch task that satisfies the FastFiller requirements
0040  *
0041  * It stores:
0042  *  - for each collection of keys: a product id and an offset
0043  *  - for each key (even those not mapped to any value): one offset
0044  *  - for each value: one value
0045  * With respect to ValueMap / Association, there is one extra int32 for each key (but we don't store null values)
0046  *
0047  * Its backbone is given by edm::helper::IndexRangeAssociation, that maps keys to ranges, and is not templated.
0048  *
0049  */
0050
0051 #include <vector>
0052 #include <map>
0053 #include <memory>
0054 #include <boost/range.hpp>
0055 #include "DataFormats/Common/interface/CMS_CLASS_VERSION.h"
0056 #include "DataFormats/Provenance/interface/ProductID.h"
0057
0058 namespace edm {
0059   namespace helper {
0060     /// Base class to map to items one a range within a target collection.
0061     /// All items in a target collection must be mapped to one and only one key.
0062     /// The target collection will normally be a RefVector (also PtrVector and std::vector could work)
0063     /// To be used by MultiAssociation. Any other usage beyond MultiAssociation is not supported.
0064     /** This class holds:
0065            - ref_offsets_: A non decreasing list of offsets in the target collection, with one item for each key *plus one end item*.
0066                            A range is given by a consecutive pair of offsets.
0067                            While filling the map, some items can be '-1', but not the last one.
0068            - id_offsets_ : A list of pairs, mapping a product id to its associated range in ref_offsets_
0069           This class can be filled through a FastFiller, that requires to fill keys and offsets in strictly increasing order, and without gaps.
0070           Only one FastFiller can exist at time, and each FastFiller fills only for a given key collection. */
0071     class IndexRangeAssociation {
0072     public:
0073       typedef std::pair<unsigned int, unsigned int> range;
0074
0075       IndexRangeAssociation() : isFilling_(false) {}
0076
0077       /// Get a range of indices for this key. RefKey can be edm::Ref, edm::Ptr, edm::RefToBase
0078       /// And end value of -1 means 'until the end of the other collection, AFAICT'
0079       template <typename RefKey>
0080       range operator[](const RefKey &r) const {
0081         return get(r.id(), r.key());
0082       }
0083
0084       /// Get a range of indices for this product id and key (non-template version)
0085       /// And end value of -1 means 'until the end of the other collection, AFAICT'
0086       range get(const edm::ProductID &id, unsigned int t) const;
0087
0088       /// True if this IndexRangeAssociation has info for this product id
0089       bool contains(ProductID id) const;
0090
0091       /// Size of this collection (number of keys)
0092       unsigned int size() const { return ref_offsets_.empty() ? 0 : ref_offsets_.size() - 1; }
0093
0094       /// True if it's empty (no keys)
0095       bool empty() const { return ref_offsets_.empty(); }
0096
0097       /// FastFiller for the IndexRangeAssociation:
0098       /// It requires to fill items in strict key order.
0099       /// You can have a single FastFiller for a given map at time
0100       /// You can't access the map for this collection while filling it
0101       class FastFiller {
0102       public:
0103         FastFiller(const FastFiller &) = delete;
0104         FastFiller &operator=(const FastFiller &) = delete;
0105
0106         /// Make a filler for a collection with a given product id and size
0107         FastFiller(IndexRangeAssociation &assoc, ProductID id, unsigned int size);
0108
0109         /// When the FastFiller goes out of scope, it unlocks the map so you can make a new one
0110         ~FastFiller();
0111
0112         /// Sets the starting offset for this key.
0113         template <typename RefKey>
0114         void insert(const RefKey &r, unsigned int startingOffset, unsigned int size) {
0115           insert(r.id(), r.key(), startingOffset, size);
0116         }
0117
0118         /// Sets the starting offset for this key (non-templated variant)
0119         void insert(edm::ProductID id, unsigned int key, unsigned int startingOffset, unsigned int size);
0120
0121       private:
0122         IndexRangeAssociation &assoc_;
0123         const ProductID id_;
0124         unsigned int start_, end_;  // indices into assoc_.ref_offsets_ (end_ points to the end marker, so it's valid)
0125         /// last key used to fill (to check that the new key must be strictly greater than lastKey_)
0126         int lastKey_;
0127       };  // FastFiller
0128       friend class FastFiller;
0129
0130       void swap(IndexRangeAssociation &other);
0131
0132       static void throwUnexpectedProductID(ProductID found, ProductID expected, const char *where);
0133
0134     private:
0135       typedef std::pair<edm::ProductID, unsigned int> id_off_pair;
0136       typedef std::vector<id_off_pair> id_offset_vector;  // sorted by product id
0137       typedef std::vector<int> offset_vector;
0138       id_offset_vector id_offsets_;
0139       offset_vector ref_offsets_;
0140
0141       bool isFilling_;  // transient, to check no two fillers exist at the same time
0142       struct IDComparator {
0143         bool operator()(const id_off_pair &p, const edm::ProductID &id) const { return p.first < id; }
0144       };  // IDComparator
0145     };
0146
0147     // Free swap function
0148     inline void swap(IndexRangeAssociation &lhs, IndexRangeAssociation &rhs) { lhs.swap(rhs); }
0149
0150   }  // namespace helper
0151
0152   template <typename C>
0153   class MultiAssociation {
0154   public:
0155     typedef C Collection;
0156     typedef boost::sub_range<const Collection> const_range;
0157     typedef boost::sub_range<Collection> range;
0158
0159     MultiAssociation() {}
0160
0161     /// Get a range of values for this key (fast)
0162     template <typename RefKey>
0163     const_range operator[](const RefKey &r) const {
0164       return get(r.id(), r.key());
0165     }
0166     // ---- and the non-const sister
0167     /// Get a range of values for this key (fast)
0168     template <typename RefKey>
0169     range operator[](const RefKey &r) {
0170       return get(r.id(), r.key());
0171     }
0172
0173     /// Get a copy of the values for this key (slow!)
0174     template <typename RefKey>
0175     Collection getValues(const RefKey &r) const {
0176       return getValues(r.id(), r.key());
0177     }
0178
0179     /// True if there are keys from this product id
0180     bool contains(const edm::ProductID &id) const { return indices_.contains(id); }
0181
0182     /// Get a range of values for this product id and index (fast)
0183     const_range get(const edm::ProductID &id, unsigned int t) const;
0184     // ---- and the non-const sister
0185     /// Get a range of values for this product id and index (fast)
0186     range get(const edm::ProductID &id, unsigned int t);
0187
0188     /// Get a copy of the values for this product id and index (slow!)
0189     Collection getValues(const edm::ProductID &id, unsigned int t) const;
0190
0191     void swap(MultiAssociation &other) {
0192       indices_.swap(other.indices_);
0193       data_.swap(other.data_);
0194     }
0195
0196     /// Returns the number of values
0197     unsigned int dataSize() const { return data_.size(); }
0198
0199     /// Returns the number of keys
0200     unsigned int size() const { return indices_.size(); }
0201
0202     /// Returns true if there are no keys
0203     bool empty() const { return indices_.empty(); }
0204
0205     /// FastFiller for the MultiAssociation.
0206     /// It is fast, but it requires to fill items in strict key order.
0207     /// You can have a single FastFiller for a given map at time
0208     /// You can't access the map for this collection while filling it
0209     class FastFiller {
0210     public:
0211       template <typename HandleType>
0212       FastFiller(MultiAssociation &assoc, const HandleType &handle)
0213           : assoc_(assoc), indexFiller_(new IndexFiller(assoc_.indices_, handle.id(), handle->size())) {}
0214
0215       FastFiller(MultiAssociation &assoc, edm::ProductID id, unsigned int size)
0216           : assoc_(assoc), indexFiller_(new IndexFiller(assoc_.indices_, id, size)) {}
0217
0218       ~FastFiller() {}
0219
0220       /// Sets the Collection values associated to this key, making copies of those in refs
0221       template <typename KeyRef>
0222       void setValues(const KeyRef &k, const Collection &refs) {
0223         setValues(k.id(), k.key(), refs);
0224       }
0225
0226       /// Sets the Collection values associated to this key, making copies of those in refs
0227       void setValues(const edm::ProductID &id, unsigned int key, const Collection &refs);
0228
0229     private:
0230       MultiAssociation &assoc_;
0231       typedef edm::helper::IndexRangeAssociation::FastFiller IndexFiller;
0232       std::shared_ptr<IndexFiller> indexFiller_;
0233
0234     };  // FastFiller
0235     friend class FastFiller;
0236
0237     template <typename HandleType>
0238     FastFiller fastFiller(const HandleType &handle) {
0239       return FastFiller(*this, handle);
0240     }
0241
0242     /// LazyFiller for the MultiAssociation.
0243     /// It is slower than FastFiller, as it keeps a copy of the input before filling it (unless you use swapValues)
0244     /// Anyway it has no constraints on the order of the keys, or the number of fillers
0245     /// It can also be copied around by value without cloning its keys (e.g to put it into a std::vector)
0246     /// If you set fillOnExit to 'true', it will fill the MultiAssociation automatically when going out of scope
0247     class LazyFiller {
0248     public:
0249       template <typename HandleType>
0250       LazyFiller(MultiAssociation &assoc, const HandleType &handle, bool fillOnExit = false)
0251           : assoc_(assoc),
0252             id_(handle.id()),
0253             size_(handle->size()),
0254             tempValues_(new TempValues()),
0255             fillOnExit_(fillOnExit) {}
0256       ~LazyFiller() noexcept(false) {
0257         if (fillOnExit_)
0258           fill();
0259       }
0260
0261       /// Does the real filling. Until this is called, the map is not modified at all.
0262       /// Calling this twice won't have any effect (but you can't modify a LazyFiller
0263       /// after calling 'fill()')
0264       /// Implementation note: inside, it just makes a FastFiller and uses it.
0265       void fill() noexcept(false);
0266
0267       /// If set to true, the LazyFiller wil call 'fill()' when it goes out of scope
0268       void setFillOnExit(bool fillOnExit) { fillOnExit_ = fillOnExit; }
0269
0270       /// Sets the Collection values associated to this key, making copies of those in refs
0271       template <typename KeyRef>
0272       void setValues(const KeyRef &k, const Collection &refs);
0273
0274       /// Swaps the Collection values associated to this key with the ones in 'ref'
0275       /// This is expected to be faster than 'setValues'.
0276       template <typename KeyRef>
0277       void swapValues(const KeyRef &k, Collection &refs);
0278
0279     private:
0280       typedef std::map<unsigned int, Collection> TempValues;
0281       MultiAssociation &assoc_;
0282       ProductID id_;
0283       unsigned int size_;
0284       std::shared_ptr<TempValues> tempValues_;
0285       bool fillOnExit_;
0286     };  // LazyFiller
0287     friend class LazyFiller;
0288
0289     template <typename HandleType>
0290     LazyFiller lazyFiller(const HandleType &h, bool fillOnExit = false) {
0291       return LazyFiller(*this, h, fillOnExit);
0292     }
0293
0294     //Used by ROOT storage
0295     CMS_CLASS_VERSION(10)
0296
0297   private:
0298     typedef helper::IndexRangeAssociation Indices;
0299     Indices indices_;
0300     Collection data_;
0301
0302   };  // class
0303
0304   // Free swap function
0305   template <typename C>
0306   inline void swap(MultiAssociation<C> &lhs, MultiAssociation<C> &rhs) {
0307     lhs.swap(rhs);
0308   }
0309
0310   //============= IMPLEMENTATION OF THE METHODS =============
0311   template <typename C>
0312   typename MultiAssociation<C>::const_range MultiAssociation<C>::get(const edm::ProductID &id, unsigned int key) const {
0313     Indices::range idxrange = indices_.get(id, key);
0314     return const_range(data_.begin() + idxrange.first, data_.begin() + idxrange.second);
0315   }
0316
0317   template <typename C>
0318   typename MultiAssociation<C>::range MultiAssociation<C>::get(const edm::ProductID &id, unsigned int key) {
0319     Indices::range idxrange = indices_.get(id, key);
0320     return range(data_.begin() + idxrange.first, data_.begin() + idxrange.second);
0321   }
0322
0323   template <typename C>
0324   typename MultiAssociation<C>::Collection MultiAssociation<C>::getValues(const edm::ProductID &id,
0325                                                                           unsigned int key) const {
0326     Collection ret;
0327     const_range values = get(id, key);
0328     for (typename const_range::const_iterator it = values.begin(), ed = values.end(); it != ed; ++it) {
0329       ret.push_back(*it);
0330     }
0331     return ret;
0332   }
0333
0334   template <typename C>
0335   void MultiAssociation<C>::FastFiller::setValues(const edm::ProductID &id, unsigned int key, const Collection &vals) {
0336     indexFiller_->insert(id, key, assoc_.data_.size(), vals.size());
0337     for (typename Collection::const_iterator it = vals.begin(), ed = vals.end(); it != ed; ++it) {
0338       assoc_.data_.push_back(*it);
0339     }
0340   }
0341
0342   template <typename C>
0343   template <typename KeyRef>
0344   void MultiAssociation<C>::LazyFiller::setValues(const KeyRef &k, const Collection &vals) {
0345     if (k.id() != id_)
0346       Indices::throwUnexpectedProductID(k.id(), id_, "LazyFiller::insert");
0347     (*tempValues_)[k.key()] = vals;
0348   }
0349
0350   template <typename C>
0351   template <typename KeyRef>
0352   void MultiAssociation<C>::LazyFiller::swapValues(const KeyRef &k, Collection &vals) {
0353     if (k.id() != id_)
0354       Indices::throwUnexpectedProductID(k.id(), id_, "LazyFiller::insert");
0355     vals.swap((*tempValues_)[k.key()]);
0356   }
0357
0358   template <typename C>
0359   void MultiAssociation<C>::LazyFiller::fill() {
0360     if (id_ != ProductID()) {  // protection against double filling
0361       typename MultiAssociation<C>::FastFiller filler(assoc_, id_, size_);
0362       for (typename TempValues::const_iterator it = tempValues_->begin(), ed = tempValues_->end(); it != ed; ++it) {
0363         filler.setValues(id_, it->first, it->second);
0364       }
0365       id_ = ProductID();  // protection against double filling
0366     }
0367   }
0368
0369 }  // namespace edm
0370
0371 #endif