Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2021-02-14 12:52:57

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