Common/interface/DetSetVector.h

0001 #ifndef DataFormats_Common_DetSetVector_h
0002 #define DataFormats_Common_DetSetVector_h
0003
0004 /*----------------------------------------------------------------------
0005
0006 DetSetVector: A collection of homogeneous objects that can be used for
0007 an EDProduct. DetSetVector is *not* designed for use as a base class
0008 (it has no virtual functions).
0009
0010 DetSetVector<T> contains a vector<DetSet<T> >, sorted on DetId, and
0011 provides fast (O(log n)) lookups, but only O(n) insertion.
0012
0013 It provides an interface such that EdmRef2 can directly reference, and
0014 provide access to, individual T objects.
0015
0016 The collection appears to the user as if it were a sequence of
0017 DetSet<T>; e.g., operator[] returns a DetSet<T>&. However, the
0018 argument to operator[] specifies the (DetId) identifier of the vector
0019 to be returned, *not* the ordinal number of the T to be returned.
0020
0021               ------------------
0022    It is critical that users DO NOT MODIFY the id data member of a
0023    DetSet object in a DetSetVector.
0024               ------------------
0025
0026 Since CMSSW 2_0_0_pre4, it is possible to skip the automatic sorting
0027 when creating a DetSetVector<T> from an already sorted vector<DetSet<T>>.
0028 If the DSV is not modified afterwards, it will no longer be sorted when
0029 it is inserted in the event.
0030 ONE NOTE OF CAUTION: it is not sufficient to to say that the vector is
0031 sorted already.  In addition the sorting must have been done with the same
0032 criteria and obey the rules of "strict weak ordering" as will be used to
0033 find things in the collection.  Not insuring this leads to undefined
0034 behavior (usually a core dump).
0035
0036 ----------------------------------------------------------------------*/
0037
0038 #include <algorithm>
0039 #include <iterator>
0040 #include <vector>
0041
0042 #include <type_traits>
0043 #include "boost/concept_check.hpp"
0044
0045 #include "DataFormats/Common/interface/CMS_CLASS_VERSION.h"
0046 #include "DataFormats/Common/interface/DetSet.h"
0047 #include "DataFormats/Common/interface/FillView.h"
0048 #include "DataFormats/Common/interface/Ref.h"
0049 #include "DataFormats/Common/interface/traits.h"
0050
0051 #include "FWCore/Utilities/interface/EDMException.h"
0052
0053 #include "DataFormats/Common/interface/BoolCache.h"
0054
0055 namespace edm {
0056   class ProductID;
0057
0058   //------------------------------------------------------------
0059   // Forward declarations
0060   template <class T>
0061   class DetSetVector;
0062
0063   //------------------------------------------------------------
0064   // Helper function, to regularize throwing of exceptions.
0065   //------------------------------------------------------------
0066
0067   namespace detail {
0068     // Throw an edm::Exception with an appropriate message
0069     inline void _throw_range(det_id_type i) {
0070       Exception::throwThis(
0071           errors::InvalidReference, "DetSetVector::operator[] called with index not in collection;\nindex value: ", i);
0072     }
0073   }  // namespace detail
0074
0075   //------------------------------------------------------------
0076   //
0077
0078   // If DetSetVector<T> is instantiated with a class T which inherits
0079   // from DoNotSortUponInsertion, the resulting class inherits from
0080   // DoNotSortUponInsertion. In the normal case, DetSetVector<T>
0081   // inherits from Other.  (This is necessary to assure that
0082   // DetSetVector<T> is not sorted upon insertion into the Event when
0083   // T is defined to inherit from DoNotSortUponInsertion).
0084
0085   template <class T>
0086   class DetSetVector : public std::conditional_t<std::is_base_of<edm::DoNotSortUponInsertion, T>::value,
0087                                                  edm::DoNotSortUponInsertion,
0088                                                  Other> {
0089     /// DetSetVector requires that T objects can be compared with
0090     /// operator<.
0091     BOOST_CLASS_REQUIRE(T, boost, LessThanComparableConcept);
0092
0093   public:
0094     typedef DetSet<T> detset;
0095     typedef detset value_type;
0096     typedef std::vector<detset> collection_type;
0097
0098     typedef detset& reference;
0099     typedef detset const& const_reference;
0100
0101     typedef typename collection_type::iterator iterator;
0102     typedef typename collection_type::const_iterator const_iterator;
0103     typedef typename collection_type::size_type size_type;
0104
0105     /// Compiler-generated copy c'tor, d'tor and
0106     /// assignment are correct.
0107
0108     /// Create an empty DetSetVector
0109     DetSetVector();
0110
0111     /// Create a DetSetVector by copying swapping in the given vector,
0112     /// and then sorting the contents.
0113     /// N.B.: Swapping in the vector *destructively modifies the input*.
0114     /// Using swap here allows us to avoid copying the data.
0115     /// N.B. 2: if you set alreadySorted to true, data *must* be sorted,
0116     /// (the vector<DetSet<T>> must be ordered by detid, and each DetSet
0117     /// must be ordered according to the natural "strict weak ordering" of Ts.
0118     /// You *must not* modify the contents after this DSV after creation,
0119     /// or you might get an undefined behavior / a core dump.
0120     /// (there are some checks to assure alreadySorted is resetted if you try
0121     /// to modify the DSV, but you should not count on them)
0122     explicit DetSetVector(std::vector<DetSet<T> >& input, bool alreadySorted = false);
0123
0124     void swap(DetSetVector& other);
0125
0126     ///  Insert the given DetSet.
0127     // What should happen if there is already a DetSet with this
0128     // DetId? Right now, it is up to the user *not* to do this. If you
0129     // are unsure whether or not your DetId is already in the
0130     // DetSetVector, then use 'find_or_insert(id)' instead.
0131     void insert(detset const& s);
0132
0133     /// Find the DetSet with the given DetId, and return a reference
0134     /// to it. If there is none, create one with the right DetId, and
0135     /// an empty vector, and return a reference to the new one.
0136     reference find_or_insert(det_id_type id);
0137
0138     /// Return true if we contain no DetSets.
0139     bool empty() const;
0140
0141     /// Return the number of contained DetSets
0142     size_type size() const;
0143
0144     // reserve...
0145     void reserve(size_t s) { _sets.reserve(s); }
0146
0147     // Do we need a short-hand method to return the number of T
0148     // instances? If so, do we optimize for size (calculate on the
0149     // fly) or speed (keep a current cache)?
0150
0151     /// Return an iterator to the DetSet with the given id, or end()
0152     /// if there is no such DetSet.
0153     iterator find(det_id_type id);
0154     const_iterator find(det_id_type id) const;
0155
0156     /// Return a reference to the DetSet with the given detector
0157     /// ID. If there is no such DetSet, we throw an edm::Exception.
0158     /// **DO NOT MODIFY THE id DATA MEMBER OF THE REFERENCED DetSet!**
0159     reference operator[](det_id_type i);
0160     const_reference operator[](det_id_type i) const;
0161
0162     /// Return an iterator to the first DetSet.
0163     iterator begin();
0164     const_iterator begin() const;
0165
0166     /// Return the off-the-end iterator.
0167     iterator end();
0168     const_iterator end() const;
0169
0170     /// Push all the id for each DetSet stored in this DetSetVector
0171     /// into the given vector 'result'.
0172     void getIds(std::vector<det_id_type>& result) const;
0173
0174     /// This function will be called by the edm::Event after the
0175     /// DetSetVector has been inserted into the Event.
0176     void post_insert();
0177
0178     void fillView(ProductID const& id, std::vector<void const*>& pointers, FillViewHelperVector& helpers) const;
0179
0180     //Used by ROOT storage
0181     CMS_CLASS_VERSION(10)
0182
0183   private:
0184     collection_type _sets;
0185     edm::BoolCache _alreadySorted;
0186
0187     /// Sort the DetSet in order of increasing DetId.
0188     void _sort();
0189   };
0190
0191   template <class T>
0192   inline DetSetVector<T>::DetSetVector() : _sets() {}
0193
0194   template <class T>
0195   inline DetSetVector<T>::DetSetVector(std::vector<DetSet<T> >& input, bool alreadySorted)
0196       : _sets(), _alreadySorted(alreadySorted) {
0197     _sets.swap(input);
0198     if (!alreadySorted)
0199       _sort();
0200   }
0201
0202   template <class T>
0203   inline void DetSetVector<T>::swap(DetSetVector<T>& other) {
0204     _sets.swap(other._sets);
0205     bool tmp = _alreadySorted;
0206     _alreadySorted = other._alreadySorted;
0207     other._alreadySorted = tmp;
0208   }
0209
0210   template <class T>
0211   inline void DetSetVector<T>::insert(detset const& t) {
0212     _alreadySorted = false;  // we don't know if the DetSet we're adding is already sorted
0213     // Implementation provided by the Performance Task Force.
0214     _sets.insert(std::lower_bound(_sets.begin(), _sets.end(), t), t);
0215 #if 0
0216     // It seems we have to sort on each insertion, because we may
0217     // perform lookups during construction.
0218     _sets.push_back(t);
0219
0220     _sort();
0221 #endif
0222   }
0223
0224   template <class T>
0225   inline typename DetSetVector<T>::reference DetSetVector<T>::find_or_insert(det_id_type id) {
0226     // NOTE: we don't have to clear _alreadySorted: the new DS is empty,
0227     //       and gets inserted in the correct place
0228     std::pair<iterator, iterator> p = std::equal_range(_sets.begin(), _sets.end(), id);
0229
0230     // If the range isn't empty, we already have the right thing;
0231     // return a reference to it...
0232     if (p.first != p.second)
0233       return *p.first;
0234
0235       // Insert the right thing, in the right place, and return a
0236       // reference to the newly inserted thing.
0237 #if defined(__GXX_EXPERIMENTAL_CXX0X__)
0238     return *(_sets.emplace(p.first, id));
0239 #else
0240     return *(_sets.insert(p.first, detset(id)));
0241 #endif
0242   }
0243
0244   template <class T>
0245   inline bool DetSetVector<T>::empty() const {
0246     return _sets.empty();
0247   }
0248
0249   template <class T>
0250   inline typename DetSetVector<T>::size_type DetSetVector<T>::size() const {
0251     return _sets.size();
0252   }
0253
0254   template <class T>
0255   inline typename DetSetVector<T>::iterator DetSetVector<T>::find(det_id_type id) {
0256     _alreadySorted = false;  // it's non const
0257     std::pair<iterator, iterator> p = std::equal_range(_sets.begin(), _sets.end(), id);
0258     if (p.first == p.second)
0259       return _sets.end();
0260
0261 // The range indicated by [p.first, p.second) should be exactly of
0262 // length 1. It seems likely we don't want to take the time hit of
0263 // checking this, but here is the appropriate test... We can turn
0264 // it on if we need the debugging aid.
0265 #if 0
0266     assert(std::distance(p.first, p.second) == 1);
0267 #endif
0268
0269     return p.first;
0270   }
0271
0272   template <class T>
0273   inline typename DetSetVector<T>::const_iterator DetSetVector<T>::find(det_id_type id) const {
0274     std::pair<const_iterator, const_iterator> p = std::equal_range(_sets.begin(), _sets.end(), id);
0275     if (p.first == p.second)
0276       return _sets.end();
0277     // The range indicated by [p.first, p.second) should be exactly of
0278     // length 1.
0279     assert(std::distance(p.first, p.second) == 1);
0280     return p.first;
0281   }
0282
0283   template <class T>
0284   inline typename DetSetVector<T>::reference DetSetVector<T>::operator[](det_id_type i) {
0285     _alreadySorted = false;  // it's non const
0286     // Find the right DetSet, and return a reference to it.  Throw if
0287     // there is none.
0288     iterator it = this->find(i);
0289     if (it == this->end())
0290       detail::_throw_range(i);
0291     return *it;
0292   }
0293
0294   template <class T>
0295   inline typename DetSetVector<T>::const_reference DetSetVector<T>::operator[](det_id_type i) const {
0296     // Find the right DetSet, and return a reference to it.  Throw if
0297     // there is none.
0298     const_iterator it = this->find(i);
0299     if (it == this->end())
0300       detail::_throw_range(i);
0301     return *it;
0302   }
0303
0304   template <class T>
0305   inline typename DetSetVector<T>::iterator DetSetVector<T>::begin() {
0306     _alreadySorted = false;  // it's non const
0307     return _sets.begin();
0308   }
0309
0310   template <class T>
0311   inline typename DetSetVector<T>::const_iterator DetSetVector<T>::begin() const {
0312     return _sets.begin();
0313   }
0314
0315   template <class T>
0316   inline typename DetSetVector<T>::iterator DetSetVector<T>::end() {
0317     _alreadySorted = false;  // it's non const
0318     return _sets.end();
0319   }
0320
0321   template <class T>
0322   inline typename DetSetVector<T>::const_iterator DetSetVector<T>::end() const {
0323     return _sets.end();
0324   }
0325
0326   template <class T>
0327   inline void DetSetVector<T>::getIds(std::vector<det_id_type>& result) const {
0328     std::transform(
0329         this->begin(), this->end(), std::back_inserter(result), std::bind(&DetSet<T>::id, std::placeholders::_1));
0330   }
0331
0332   template <class T>
0333   inline void DetSetVector<T>::post_insert() {
0334     _sets.shrink_to_fit();
0335     if (_alreadySorted)
0336       return;
0337     typename collection_type::iterator i = _sets.begin();
0338     typename collection_type::iterator e = _sets.end();
0339     // For each DetSet...
0340     for (; i != e; ++i) {
0341       i->data.shrink_to_fit();
0342       // sort the Detset pointed to by
0343       std::sort(i->data.begin(), i->data.end());
0344     }
0345   }
0346
0347   template <class T>
0348   inline void DetSetVector<T>::_sort() {
0349     std::sort(_sets.begin(), _sets.end());
0350   }
0351
0352   template <class T>
0353   void DetSetVector<T>::fillView(ProductID const& id,
0354                                  std::vector<void const*>& pointers,
0355                                  FillViewHelperVector& helpers) const {
0356     detail::reallyFillView(*this, id, pointers, helpers);
0357   }
0358
0359   //----------------------------------------------------------------------
0360   //
0361   // Free function template to support creation of Views.
0362
0363   template <class T>
0364   inline void fillView(DetSetVector<T> const& obj,
0365                        ProductID const& id,
0366                        std::vector<void const*>& pointers,
0367                        FillViewHelperVector& helpers) {
0368     obj.fillView(id, pointers, helpers);
0369   }
0370
0371   template <class T>
0372   struct has_fillView<edm::DetSetVector<T> > {
0373     static bool const value = true;
0374   };
0375
0376   // Free swap function
0377   template <class T>
0378   inline void swap(DetSetVector<T>& a, DetSetVector<T>& b) {
0379     a.swap(b);
0380   }
0381
0382 }  // namespace edm
0383
0384 //specialize behavior of edm::Ref to get access to the 'Det'
0385 namespace edm {
0386
0387   namespace refhelper {
0388     template <typename T>
0389     class FindForDetSetVector {
0390     public:
0391       using first_argument_type = const DetSetVector<T>&;
0392       using second_argument_type = std::pair<det_id_type, typename DetSet<T>::collection_type::size_type>;
0393       using result_type = const T*;
0394
0395       result_type operator()(first_argument_type iContainer, second_argument_type iIndex) {
0396         return &(*(iContainer.find(iIndex.first)->data.begin() + iIndex.second));
0397       }
0398     };
0399
0400     template <typename T>
0401     struct FindTrait<DetSetVector<T>, T> {
0402       typedef FindForDetSetVector<T> value;
0403     };
0404   }  // namespace refhelper
0405
0406   //helper function to make it easier to create a edm::Ref
0407
0408   template <class HandleT>
0409   inline Ref<typename HandleT::element_type, typename HandleT::element_type::value_type::value_type> makeRefTo(
0410       const HandleT& iHandle, det_id_type iDetID, typename HandleT::element_type::value_type::const_iterator itIter) {
0411     typedef typename HandleT::element_type Vec;
0412     typename Vec::value_type::collection_type::size_type index = 0;
0413     typename Vec::const_iterator itFound = iHandle->find(iDetID);
0414     if (itFound == iHandle->end()) {
0415       Exception::throwThis(errors::InvalidReference,
0416                            "an edm::Ref to an edm::DetSetVector was given a DetId, ",
0417                            iDetID,
0418                            ", that is not in the DetSetVector");
0419     }
0420     index += (itIter - itFound->data.begin());
0421     if (index >= itFound->data.size()) {
0422       Exception::throwThis(errors::InvalidReference,
0423                            "an edm::Ref to a edm::DetSetVector is being made with an interator that is not part of the "
0424                            "edm::DetSet itself");
0425     }
0426     return Ref<typename HandleT::element_type, typename HandleT::element_type::value_type::value_type>(
0427         iHandle, std::make_pair(iDetID, index));
0428   }
0429
0430   template <class HandleT>
0431   inline Ref<typename HandleT::element_type, typename HandleT::element_type::value_type::value_type>
0432   makeRefToDetSetVector(const HandleT& iHandle,
0433                         det_id_type iDetID,
0434                         typename HandleT::element_type::value_type::iterator itIter) {
0435     typedef typename HandleT::element_type Vec;
0436     typename Vec::detset::const_iterator itIter2 = itIter;
0437     return makeRefTo(iHandle, iDetID, itIter2);
0438   }
0439 }  // namespace edm
0440 #endif