Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2023-11-02 03:10:56

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