MultiAssociation.h

Go to the documentation of this file.

#ifndef DataFormats_Common_MultiAssociation_h
#define DataFormats_Common_MultiAssociation_h
/* \class MultiAssociation
 *
 * \author Giovanni Petrucciani, SNS Pisa and CERN PH-CMG
 * 
 * One-to-Many variant of edm::Association<C> / edm::ValueMap<T>, 
 *
 * Given a key, it will return a range of iterators within a collection (fast access), or collection by value (slow access mode)
 *
 * The range of iterators is handled through boost::sub_range, so it should feel like a collection:
 *   1) it has a '::const_iterator', a 'begin()' and an 'end()'
 *   2) it has a 'size()' and an 'empty()'
 *   3) it has a 'front()', 'back()'
 *   4) it works as an array  (i.e. you can use range[index] to pick an element)
 *   5) if your MultiAssociation is not const, you can modify the values associated to each key
 *      (but you can't push_back new values for a given key)
 * ( details at http://www.boost.org/doc/libs/1_37_0/libs/range/doc/utility_class.html#sub_range )
 *
 * 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>...
 * The collection must be compatible with sub_range and support a few other features. Usually you need:
 *  - that it has a default constructor
 *  - that it has a const_iterator, and "begin() const" returns such const_iterator. 
 *  - that it has an iterator, and "begin()" returns such iterator (note: it doesn't have to be writable, it can be const as well) 
 *  - that it has a swap method
 *  - that 'begin() + offset' is legal (and fast, otherwise this thing is will be awfully slow)
 *  - that you can push_back on a C the * of a C::const_iterator. Namely this should be legal
 *    <code>
 *       C::const_iterator it = ..something..
 *       C someOtherC = ...
 *       someOtherC.push_back(*it);
 *    </code>
 *
 * It can be filled through a FastFiller or a LazyFiller. 
 * FastFiller is probably faster, but has many constraints:
 * - you must fill only one product id at time
 * - you must fill items in strict key order
 * - there is no way to abort a filling operation
 * Try LazyFiller first, unless you're doing some sort of batch task that satisfies the FastFiller requirements
 *
 * It stores:
 *  - for each collection of keys: a product id and an offset  
 *  - for each key (even those not mapped to any value): one offset
 *  - for each value: one value
 * With respect to ValueMap / Association, there is one extra int32 for each key (but we don't store null values)
 *
 * Its backbone is given by edm::helper::IndexRangeAssociation, that maps keys to ranges, and is not templated.
 *
 */

#include <vector>
#include <map>
#include <memory>
#include <boost/utility.hpp>
#include <boost/range.hpp>
#include "DataFormats/Common/interface/CMS_CLASS_VERSION.h"
#include "DataFormats/Provenance/interface/ProductID.h"
#include "FWCore/Utilities/interface/GCC11Compatibility.h"

namespace edm {
  namespace helper {

      class IndexRangeAssociation {
          public:
              typedef std::pair<unsigned int, unsigned int> range;
            
              IndexRangeAssociation() : isFilling_(false) {}

              template<typename RefKey>
              range operator[](const RefKey &r) const {  
                  return get(r.id(), r.key()); 
              }
              
              range get(const edm::ProductID & id, unsigned int t) const ;

              bool  contains(ProductID id) const ;

              unsigned int size() const { return ref_offsets_.empty() ? 0 : ref_offsets_.size() - 1; }
            
              bool empty() const { return ref_offsets_.empty(); }

              class FastFiller : boost::noncopyable {
                  public:
                      FastFiller(IndexRangeAssociation &assoc, ProductID id, unsigned int size) ;

                      ~FastFiller() ;

                      template<typename RefKey> 
                      void insert(const RefKey &r, unsigned int startingOffset, unsigned int size) {
                         insert(r.id(), r.key(), startingOffset, size);
                      }

                      void insert(edm::ProductID id, unsigned int key, unsigned int startingOffset, unsigned int size) ;
                  private:
                      IndexRangeAssociation & assoc_;
                      const ProductID         id_;
                      unsigned int start_, end_; // indices into assoc_.ref_offsets_ (end_ points to the end marker, so it's valid)
                      int lastKey_; 
              }; // FastFiller
              friend class FastFiller;

              void swap(IndexRangeAssociation &other) ;

              static void throwUnexpectedProductID(ProductID found, ProductID expected, const char *where) ;
          private:
              typedef std::pair<edm::ProductID,unsigned int> id_off_pair;
              typedef std::vector<id_off_pair> id_offset_vector; // sorted by product id
              typedef std::vector<int> offset_vector; 
              id_offset_vector id_offsets_;  
              offset_vector    ref_offsets_; 

              bool isFilling_; // transient, to check no two fillers exist at the same time
              struct IDComparator { 
                bool operator()(const id_off_pair &p, const edm::ProductID &id) const {  return p.first < id; }
              }; // IDComparator

              
    };

    // Free swap function
    inline void swap(IndexRangeAssociation& lhs, IndexRangeAssociation& rhs) { lhs.swap(rhs); }

  } // Helper Namespace
 
  template<typename C>
  class MultiAssociation {
  public:
    typedef C Collection;
    typedef boost::sub_range<const Collection> const_range;
    typedef boost::sub_range<Collection>       range;

    MultiAssociation() {}

    template<typename RefKey> 
    const_range operator[](const RefKey &r) const { 
        return get(r.id(), r.key()); 
    }
    // ---- and the non-const sister
    template<typename RefKey> 
    range operator[](const RefKey &r) { 
        return get(r.id(), r.key()); 
    }

    template<typename RefKey> 
    Collection getValues(const RefKey &r) const { 
        return getValues(r.id(), r.key()); 
    }

    bool contains(const edm::ProductID &id) const { return indices_.contains(id); }

    const_range get(const edm::ProductID &id, unsigned int t) const ;
    // ---- and the non-const sister
    range get(const edm::ProductID &id, unsigned int t) ;

    Collection getValues(const edm::ProductID &id, unsigned int t) const ;
    
    void swap(MultiAssociation &other) {
        indices_.swap(other.indices_);
        data_.swap(other.data_);
    }

    unsigned int dataSize()    const { return data_.size();    }

    unsigned int size() const { return indices_.size(); }

    bool empty() const { return indices_.empty(); }

    class FastFiller {
        public:
            template<typename HandleType>
            FastFiller(MultiAssociation &assoc, const HandleType &handle) : 
                assoc_(assoc), indexFiller_(new IndexFiller(assoc_.indices_, handle.id(), handle->size())) {}

            FastFiller(MultiAssociation &assoc, edm::ProductID id, unsigned int size) : 
                assoc_(assoc), indexFiller_(new IndexFiller(assoc_.indices_, id, size)) {}

            ~FastFiller() {}
        
            template<typename KeyRef>
            void setValues(const KeyRef &k, const Collection &refs) { setValues(k.id(), k.key(), refs); }

            void setValues(const edm::ProductID &id, unsigned int key, const Collection &refs);
        private:
            MultiAssociation &  assoc_;
            typedef edm::helper::IndexRangeAssociation::FastFiller IndexFiller;
            std::shared_ptr<IndexFiller> indexFiller_;

    }; // FastFiller
    friend class FastFiller;

    template<typename HandleType>
    FastFiller fastFiller(const HandleType &handle) { return FastFiller(*this, handle); }

    class LazyFiller {
        public:
            template<typename HandleType>
            LazyFiller(MultiAssociation &assoc, const HandleType &handle, bool fillOnExit=false) :
                assoc_(assoc), 
                id_(handle.id()), size_(handle->size()), 
                tempValues_(new TempValues()), fillOnExit_(fillOnExit) {}
            ~LazyFiller() noexcept(false) { if (fillOnExit_) fill(); } 

            void fill() noexcept(false);

            void setFillOnExit(bool fillOnExit) { fillOnExit_ = fillOnExit; }

            template<typename KeyRef>
            void setValues(const KeyRef &k, const Collection &refs) ;

            template<typename KeyRef>
            void swapValues(const KeyRef &k, Collection &refs) ;
        private:
            typedef std::map<unsigned int, Collection> TempValues;
            MultiAssociation & assoc_;
            ProductID id_; 
            unsigned int size_;
            std::shared_ptr<TempValues> tempValues_;
            bool fillOnExit_;
    }; // LazyFiller
    friend class LazyFiller;

    template<typename HandleType>
    LazyFiller lazyFiller(const HandleType &h, bool fillOnExit=false) { return LazyFiller(*this, h, fillOnExit); }

    //Used by ROOT storage
    CMS_CLASS_VERSION(10)

  private:
    typedef helper::IndexRangeAssociation Indices;
    Indices    indices_;
    Collection data_;

}; // class

  // Free swap function
  template <typename C>
  inline void swap(MultiAssociation<C>& lhs, MultiAssociation<C>& rhs) { lhs.swap(rhs); }

  //============= IMPLEMENTATION OF THE METHODS =============
  template<typename C>
  typename MultiAssociation<C>::const_range
  MultiAssociation<C>::get(const edm::ProductID & id, unsigned int key) const {
    Indices::range idxrange = indices_.get(id,key);
    return const_range(data_.begin()+idxrange.first, data_.begin()+idxrange.second);
  }

  template<typename C>
  typename MultiAssociation<C>::range
  MultiAssociation<C>::get(const edm::ProductID & id, unsigned int key) {
    Indices::range idxrange = indices_.get(id,key);
    return range(data_.begin()+idxrange.first, data_.begin()+idxrange.second);
  }


  template<typename C>
  typename MultiAssociation<C>::Collection
  MultiAssociation<C>::getValues(const edm::ProductID & id, unsigned int key) const {
     Collection ret;
     const_range values = get(id,key);
     for (typename const_range::const_iterator it = values.begin(), ed = values.end(); it != ed; ++it) {
        ret.push_back(*it);
     }
     return ret;
  }

  template<typename C>
  void MultiAssociation<C>::FastFiller::setValues(const edm::ProductID & id, unsigned int key, const Collection &vals) {
     indexFiller_->insert(id, key, assoc_.data_.size(), vals.size());
     for (typename Collection::const_iterator it = vals.begin(), ed = vals.end(); it != ed; ++it) {
        assoc_.data_.push_back(*it);
     }
  } 
  
  template<typename C>
  template<typename KeyRef>
  void MultiAssociation<C>::LazyFiller::setValues(const KeyRef &k, const Collection &vals) {
     if (k.id() != id_) Indices::throwUnexpectedProductID(k.id(),id_,"LazyFiller::insert");  
     (*tempValues_)[k.key()] = vals;
  }

  template<typename C>
  template<typename KeyRef>
  void MultiAssociation<C>::LazyFiller::swapValues(const KeyRef &k, Collection &vals) {
     if (k.id() != id_) Indices::throwUnexpectedProductID(k.id(),id_,"LazyFiller::insert");  
     vals.swap((*tempValues_)[k.key()]);
  }


  template<typename C>
  void MultiAssociation<C>::LazyFiller::fill() {
     if (id_ != ProductID()) { // protection against double filling
        typename MultiAssociation<C>::FastFiller filler(assoc_, id_, size_);
        for (typename TempValues::const_iterator it = tempValues_->begin(), ed = tempValues_->end(); it != ed; ++it) {
           filler.setValues(id_, it->first, it->second);                
        }
        id_ = ProductID();     // protection against double filling
     }
  }

 
} // namespace

#endif