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     DetSetVector& operator=(DetSetVector const& other);
0127
0128     ///  Insert the given DetSet.
0129     // What should happen if there is already a DetSet with this
0130     // DetId? Right now, it is up to the user *not* to do this. If you
0131     // are unsure whether or not your DetId is already in the
0132     // DetSetVector, then use 'find_or_insert(id)' instead.
0133     void insert(detset const& s);
0134
0135     /// Find the DetSet with the given DetId, and return a reference
0136     /// to it. If there is none, create one with the right DetId, and
0137     /// an empty vector, and return a reference to the new one.
0138     reference find_or_insert(det_id_type id);
0139
0140     /// Return true if we contain no DetSets.
0141     bool empty() const;
0142
0143     /// Return the number of contained DetSets
0144     size_type size() const;
0145
0146     // reserve...
0147     void reserve(size_t s) { _sets.reserve(s); }
0148
0149     // Do we need a short-hand method to return the number of T
0150     // instances? If so, do we optimize for size (calculate on the
0151     // fly) or speed (keep a current cache)?
0152
0153     /// Return an iterator to the DetSet with the given id, or end()
0154     /// if there is no such DetSet.
0155     iterator find(det_id_type id);
0156     const_iterator find(det_id_type id) const;
0157
0158     /// Return a reference to the DetSet with the given detector
0159     /// ID. If there is no such DetSet, we throw an edm::Exception.
0160     /// **DO NOT MODIFY THE id DATA MEMBER OF THE REFERENCED DetSet!**
0161     reference operator[](det_id_type i);
0162     const_reference operator[](det_id_type i) const;
0163
0164     /// Return an iterator to the first DetSet.
0165     iterator begin();
0166     const_iterator begin() const;
0167
0168     /// Return the off-the-end iterator.
0169     iterator end();
0170     const_iterator end() const;
0171
0172     /// Push all the id for each DetSet stored in this DetSetVector
0173     /// into the given vector 'result'.
0174     void getIds(std::vector<det_id_type>& result) const;
0175
0176     /// This function will be called by the edm::Event after the
0177     /// DetSetVector has been inserted into the Event.
0178     void post_insert();
0179
0180     void fillView(ProductID const& id, std::vector<void const*>& pointers, FillViewHelperVector& helpers) const;
0181
0182     //Used by ROOT storage
0183     CMS_CLASS_VERSION(10)
0184
0185   private:
0186     collection_type _sets;
0187     edm::BoolCache _alreadySorted;
0188
0189     /// Sort the DetSet in order of increasing DetId.
0190     void _sort();
0191   };
0192
0193   template <class T>
0194   inline DetSetVector<T>::DetSetVector() : _sets() {}
0195
0196   template <class T>
0197   inline DetSetVector<T>::DetSetVector(std::vector<DetSet<T> >& input, bool alreadySorted)
0198       : _sets(), _alreadySorted(alreadySorted) {
0199     _sets.swap(input);
0200     if (!alreadySorted)
0201       _sort();
0202   }
0203
0204   template <class T>
0205   inline void DetSetVector<T>::swap(DetSetVector<T>& other) {
0206     _sets.swap(other._sets);
0207     bool tmp = _alreadySorted;
0208     _alreadySorted = other._alreadySorted;
0209     other._alreadySorted = tmp;
0210   }
0211
0212   template <class T>
0213   inline DetSetVector<T>& DetSetVector<T>::operator=(DetSetVector<T> const& other) {
0214     DetSetVector<T> temp(other);
0215     swap(temp);
0216     return *this;
0217   }
0218
0219   template <class T>
0220   inline void DetSetVector<T>::insert(detset const& t) {
0221     _alreadySorted = false;  // we don't know if the DetSet we're adding is already sorted
0222     // Implementation provided by the Performance Task Force.
0223     _sets.insert(std::lower_bound(_sets.begin(), _sets.end(), t), t);
0224 #if 0
0225     // It seems we have to sort on each insertion, because we may
0226     // perform lookups during construction.
0227     _sets.push_back(t);
0228
0229     _sort();
0230 #endif
0231   }
0232
0233   template <class T>
0234   inline typename DetSetVector<T>::reference DetSetVector<T>::find_or_insert(det_id_type id) {
0235     // NOTE: we don't have to clear _alreadySorted: the new DS is empty,
0236     //       and gets inserted in the correct place
0237     std::pair<iterator, iterator> p = std::equal_range(_sets.begin(), _sets.end(), id);
0238
0239     // If the range isn't empty, we already have the right thing;
0240     // return a reference to it...
0241     if (p.first != p.second)
0242       return *p.first;
0243
0244       // Insert the right thing, in the right place, and return a
0245       // reference to the newly inserted thing.
0246 #if defined(__GXX_EXPERIMENTAL_CXX0X__)
0247     return *(_sets.emplace(p.first, id));
0248 #else
0249     return *(_sets.insert(p.first, detset(id)));
0250 #endif
0251   }
0252
0253   template <class T>
0254   inline bool DetSetVector<T>::empty() const {
0255     return _sets.empty();
0256   }
0257
0258   template <class T>
0259   inline typename DetSetVector<T>::size_type DetSetVector<T>::size() const {
0260     return _sets.size();
0261   }
0262
0263   template <class T>
0264   inline typename DetSetVector<T>::iterator DetSetVector<T>::find(det_id_type id) {
0265     _alreadySorted = false;  // it's non const
0266     std::pair<iterator, iterator> p = std::equal_range(_sets.begin(), _sets.end(), id);
0267     if (p.first == p.second)
0268       return _sets.end();
0269
0270 // The range indicated by [p.first, p.second) should be exactly of
0271 // length 1. It seems likely we don't want to take the time hit of
0272 // checking this, but here is the appropriate test... We can turn
0273 // it on if we need the debugging aid.
0274 #if 0
0275     assert(std::distance(p.first, p.second) == 1);
0276 #endif
0277
0278     return p.first;
0279   }
0280
0281   template <class T>
0282   inline typename DetSetVector<T>::const_iterator DetSetVector<T>::find(det_id_type id) const {
0283     std::pair<const_iterator, const_iterator> p = std::equal_range(_sets.begin(), _sets.end(), id);
0284     if (p.first == p.second)
0285       return _sets.end();
0286     // The range indicated by [p.first, p.second) should be exactly of
0287     // length 1.
0288     assert(std::distance(p.first, p.second) == 1);
0289     return p.first;
0290   }
0291
0292   template <class T>
0293   inline typename DetSetVector<T>::reference DetSetVector<T>::operator[](det_id_type i) {
0294     _alreadySorted = false;  // it's non const
0295     // Find the right DetSet, and return a reference to it.  Throw if
0296     // there is none.
0297     iterator it = this->find(i);
0298     if (it == this->end())
0299       detail::_throw_range(i);
0300     return *it;
0301   }
0302
0303   template <class T>
0304   inline typename DetSetVector<T>::const_reference DetSetVector<T>::operator[](det_id_type i) const {
0305     // Find the right DetSet, and return a reference to it.  Throw if
0306     // there is none.
0307     const_iterator it = this->find(i);
0308     if (it == this->end())
0309       detail::_throw_range(i);
0310     return *it;
0311   }
0312
0313   template <class T>
0314   inline typename DetSetVector<T>::iterator DetSetVector<T>::begin() {
0315     _alreadySorted = false;  // it's non const
0316     return _sets.begin();
0317   }
0318
0319   template <class T>
0320   inline typename DetSetVector<T>::const_iterator DetSetVector<T>::begin() const {
0321     return _sets.begin();
0322   }
0323
0324   template <class T>
0325   inline typename DetSetVector<T>::iterator DetSetVector<T>::end() {
0326     _alreadySorted = false;  // it's non const
0327     return _sets.end();
0328   }
0329
0330   template <class T>
0331   inline typename DetSetVector<T>::const_iterator DetSetVector<T>::end() const {
0332     return _sets.end();
0333   }
0334
0335   template <class T>
0336   inline void DetSetVector<T>::getIds(std::vector<det_id_type>& result) const {
0337     std::transform(
0338         this->begin(), this->end(), std::back_inserter(result), std::bind(&DetSet<T>::id, std::placeholders::_1));
0339   }
0340
0341   template <class T>
0342   inline void DetSetVector<T>::post_insert() {
0343     _sets.shrink_to_fit();
0344     if (_alreadySorted)
0345       return;
0346     typename collection_type::iterator i = _sets.begin();
0347     typename collection_type::iterator e = _sets.end();
0348     // For each DetSet...
0349     for (; i != e; ++i) {
0350       i->data.shrink_to_fit();
0351       // sort the Detset pointed to by
0352       std::sort(i->data.begin(), i->data.end());
0353     }
0354   }
0355
0356   template <class T>
0357   inline void DetSetVector<T>::_sort() {
0358     std::sort(_sets.begin(), _sets.end());
0359   }
0360
0361   template <class T>
0362   void DetSetVector<T>::fillView(ProductID const& id,
0363                                  std::vector<void const*>& pointers,
0364                                  FillViewHelperVector& helpers) const {
0365     detail::reallyFillView(*this, id, pointers, helpers);
0366   }
0367
0368   //----------------------------------------------------------------------
0369   //
0370   // Free function template to support creation of Views.
0371
0372   template <class T>
0373   inline void fillView(DetSetVector<T> const& obj,
0374                        ProductID const& id,
0375                        std::vector<void const*>& pointers,
0376                        FillViewHelperVector& helpers) {
0377     obj.fillView(id, pointers, helpers);
0378   }
0379
0380   template <class T>
0381   struct has_fillView<edm::DetSetVector<T> > {
0382     static bool const value = true;
0383   };
0384
0385   // Free swap function
0386   template <class T>
0387   inline void swap(DetSetVector<T>& a, DetSetVector<T>& b) {
0388     a.swap(b);
0389   }
0390
0391 }  // namespace edm
0392
0393 //specialize behavior of edm::Ref to get access to the 'Det'
0394 namespace edm {
0395
0396   namespace refhelper {
0397     template <typename T>
0398     class FindForDetSetVector {
0399     public:
0400       using first_argument_type = const DetSetVector<T>&;
0401       using second_argument_type = std::pair<det_id_type, typename DetSet<T>::collection_type::size_type>;
0402       using result_type = const T*;
0403
0404       result_type operator()(first_argument_type iContainer, second_argument_type iIndex) {
0405         return &(*(iContainer.find(iIndex.first)->data.begin() + iIndex.second));
0406       }
0407     };
0408
0409     template <typename T>
0410     struct FindTrait<DetSetVector<T>, T> {
0411       typedef FindForDetSetVector<T> value;
0412     };
0413   }  // namespace refhelper
0414
0415   //helper function to make it easier to create a edm::Ref
0416
0417   template <class HandleT>
0418   inline Ref<typename HandleT::element_type, typename HandleT::element_type::value_type::value_type> makeRefTo(
0419       const HandleT& iHandle, det_id_type iDetID, typename HandleT::element_type::value_type::const_iterator itIter) {
0420     typedef typename HandleT::element_type Vec;
0421     typename Vec::value_type::collection_type::size_type index = 0;
0422     typename Vec::const_iterator itFound = iHandle->find(iDetID);
0423     if (itFound == iHandle->end()) {
0424       Exception::throwThis(errors::InvalidReference,
0425                            "an edm::Ref to an edm::DetSetVector was given a DetId, ",
0426                            iDetID,
0427                            ", that is not in the DetSetVector");
0428     }
0429     index += (itIter - itFound->data.begin());
0430     if (index >= itFound->data.size()) {
0431       Exception::throwThis(errors::InvalidReference,
0432                            "an edm::Ref to a edm::DetSetVector is being made with an interator that is not part of the "
0433                            "edm::DetSet itself");
0434     }
0435     return Ref<typename HandleT::element_type, typename HandleT::element_type::value_type::value_type>(
0436         iHandle, std::make_pair(iDetID, index));
0437   }
0438
0439   template <class HandleT>
0440   inline Ref<typename HandleT::element_type, typename HandleT::element_type::value_type::value_type>
0441   makeRefToDetSetVector(const HandleT& iHandle,
0442                         det_id_type iDetID,
0443                         typename HandleT::element_type::value_type::iterator itIter) {
0444     typedef typename HandleT::element_type Vec;
0445     typename Vec::detset::const_iterator itIter2 = itIter;
0446     return makeRefTo(iHandle, iDetID, itIter2);
0447   }
0448 }  // namespace edm
0449 #endif