CMS 3D CMS Logo

/data/refman/pasoursint/CMSSW_5_3_3/src/DataFormats/Common/interface/DetSetVector.h

Go to the documentation of this file.
00001 #ifndef DataFormats_Common_DetSetVector_h
00002 #define DataFormats_Common_DetSetVector_h
00003 
00004 /*----------------------------------------------------------------------
00005 
00006 DetSetVector: A collection of homogeneous objects that can be used for
00007 an EDProduct. DetSetVector is *not* designed for use as a base class
00008 (it has no virtual functions).
00009 
00010 DetSetVector<T> contains a vector<DetSet<T> >, sorted on DetId, and
00011 provides fast (O(log n)) lookups, but only O(n) insertion.
00012 
00013 It provides an interface such that EdmRef2 can directly reference, and
00014 provide access to, individual T objects.
00015 
00016 The collection appears to the user as if it were a sequence of
00017 DetSet<T>; e.g., operator[] returns a DetSet<T>&. However, the
00018 argument to operator[] specifies the (DetId) identifier of the vector
00019 to be returned, *not* the ordinal number of the T to be returned.
00020 
00021                           ------------------
00022    It is critical that users DO NOT MODIFY the id data member of a
00023    DetSet object in a DetSetVector.
00024                           ------------------
00025 
00026 Since CMSSW 2_0_0_pre4, it is possible to skip the automatic sorting
00027 when creating a DetSetVector<T> from an already sorted vector<DetSet<T>>.
00028 If the DSV is not modified afterwards, it will no longer be sorted when
00029 it is inserted in the event.
00030 ONE NOTE OF CAUTION: it is not sufficient to to say that the vector is 
00031 sorted already.  In addition the sorting must have been done with the same
00032 criteria and obey the rules of "strict weak ordering" as will be used to
00033 find things in the collection.  Not insuring this leads to undefined
00034 behavior (usually a core dump).
00035 
00036 ----------------------------------------------------------------------*/
00037 
00038 #include <algorithm>
00039 #include <iterator>
00040 #include <vector>
00041 
00042 #include "boost/concept_check.hpp"
00043 #include "boost/mpl/if.hpp"
00044 #include "boost/bind.hpp"
00045 
00046 
00047 #include "DataFormats/Common/interface/CMS_CLASS_VERSION.h"
00048 #include "DataFormats/Common/interface/DetSet.h"
00049 #include "DataFormats/Common/interface/FillView.h"
00050 #include "DataFormats/Common/interface/Ref.h"
00051 #include "DataFormats/Common/interface/traits.h"
00052 
00053 #include "FWCore/Utilities/interface/EDMException.h"
00054 
00055 #include "DataFormats/Common/interface/BoolCache.h"
00056 
00057 namespace edm {
00058   class ProductID;
00059 
00060   //------------------------------------------------------------
00061   // Forward declarations
00062   template <class T> class DetSetVector;
00063 
00064   //------------------------------------------------------------
00065   // Helper function, to regularize throwing of exceptions.
00066   //------------------------------------------------------------
00067 
00068   namespace detail {
00069     // Throw an edm::Exception with an appropriate message
00070     inline
00071     void _throw_range(det_id_type i) {
00072       Exception::throwThis(errors::InvalidReference,
00073         "DetSetVector::operator[] called with index not in collection;\nindex value: ", i);
00074     }
00075   }
00076 
00077   //------------------------------------------------------------
00078   //
00079 
00080   // If DetSetVector<T> is instantiated with a class T which inherits
00081   // from DoNotSortUponInsertion, the resulting class inherits from
00082   // DoNotSortUponInsertion. In the normal case, DetSetVector<T>
00083   // inherits from Other.  (This is necessary to assure that
00084   // DetSetVector<T> is not sorted upon insertion into the Event when
00085   // T is defined to inherit from DoNotSortUponInsertion).
00086 
00087   template <class T>
00088   class DetSetVector : 
00089     public boost::mpl::if_c<boost::is_base_of<edm::DoNotSortUponInsertion, T>::value,
00090                             edm::DoNotSortUponInsertion,
00091                             Other>::type
00092   {
00095     BOOST_CLASS_REQUIRE(T, boost, LessThanComparableConcept);
00096   public:
00097 
00098     typedef DetSet<T>           detset;
00099     typedef detset              value_type;
00100     typedef std::vector<detset> collection_type;
00101 
00102     typedef detset&        reference;
00103     typedef detset const&  const_reference;
00104 
00105     typedef typename collection_type::iterator       iterator;
00106     typedef typename collection_type::const_iterator const_iterator;
00107     typedef typename collection_type::size_type      size_type;
00108 
00111 
00113     DetSetVector();
00114 
00126     explicit DetSetVector(std::vector<DetSet<T> > & input, bool alreadySorted=false);
00127 
00128 
00129     void swap(DetSetVector& other);
00130 
00131     DetSetVector& operator= (DetSetVector const& other);
00132 
00134     // What should happen if there is already a DetSet with this
00135     // DetId? Right now, it is up to the user *not* to do this. If you
00136     // are unsure whether or not your DetId is already in the
00137     // DetSetVector, then use 'find_or_insert(id)' instead.
00138     void insert(detset const& s);
00139 
00143     reference find_or_insert(det_id_type id);
00144 
00146     bool empty() const;
00147 
00149     size_type size() const;
00150 
00151     // Do we need a short-hand method to return the number of T
00152     // instances? If so, do we optimize for size (calculate on the
00153     // fly) or speed (keep a current cache)?
00154 
00157     iterator       find(det_id_type id);
00158     const_iterator find(det_id_type id) const;
00159 
00163     reference       operator[](det_id_type  i);
00164     const_reference operator[](det_id_type i) const;
00165 
00167     iterator       begin();
00168     const_iterator begin() const;
00169 
00171     iterator       end();
00172     const_iterator end() const;
00173 
00176     void getIds(std::vector<det_id_type> & result) const;
00177 
00180     void post_insert();
00181 
00182     void fillView(ProductID const& id,
00183                   std::vector<void const*>& pointers,
00184                   helper_vector& helpers) const;
00185 
00186     //Used by ROOT storage
00187     CMS_CLASS_VERSION(10)
00188 
00189   private:
00190     collection_type   _sets;
00191     edm::BoolCache    _alreadySorted; 
00192 
00194     void _sort();
00195 
00196   };
00197 
00198   template <class T>
00199   inline
00200   DetSetVector<T>::DetSetVector() :
00201     _sets()
00202   { }
00203 
00204   template <class T>
00205   inline
00206   DetSetVector<T>::DetSetVector(std::vector<DetSet<T> > & input, bool alreadySorted) :
00207     _sets(), _alreadySorted(alreadySorted)
00208   {
00209     _sets.swap(input);
00210     if (!alreadySorted) _sort();
00211   }
00212 
00213   template <class T>
00214   inline
00215   void
00216   DetSetVector<T>::swap(DetSetVector<T>& other) {
00217     _sets.swap(other._sets);
00218     bool tmp = _alreadySorted; _alreadySorted = other._alreadySorted; other._alreadySorted = tmp;
00219   }
00220 
00221   template <class T>
00222   inline
00223   DetSetVector<T>&
00224   DetSetVector<T>::operator= (DetSetVector<T> const& other)
00225   {
00226     DetSetVector<T> temp(other);
00227     swap(temp);
00228     return *this;
00229   }
00230 
00231   template <class T>
00232   inline
00233   void
00234   DetSetVector<T>::insert(detset const& t) {
00235     _alreadySorted = false; // we don't know if the DetSet we're adding is already sorted
00236     // Implementation provided by the Performance Task Force.
00237     _sets.insert(std::lower_bound(_sets.begin(),
00238                                   _sets.end(),
00239                                   t),
00240                  t);
00241 #if 0
00242     // It seems we have to sort on each insertion, because we may
00243     // perform lookups during construction.
00244     _sets.push_back(t);
00245 
00246     _sort();
00247 #endif
00248   }
00249 
00250   template <class T>
00251   inline
00252   typename DetSetVector<T>::reference
00253   DetSetVector<T>::find_or_insert(det_id_type id) {
00254     // NOTE: we don't have to clear _alreadySorted: the new DS is empty, 
00255     //       and gets inserted in the correct place
00256     std::pair<iterator,iterator> p =
00257       std::equal_range(_sets.begin(), _sets.end(), id);
00258 
00259     // If the range isn't empty, we already have the right thing;
00260     // return a reference to it...
00261     if (p.first != p.second) return *p.first;
00262 
00263     // Insert the right thing, in the right place, and return a
00264     // reference to the newly inserted thing.
00265     return *(_sets.insert(p.first, detset(id)));
00266   }
00267 
00268   template <class T>
00269   inline
00270   bool
00271   DetSetVector<T>::empty() const {
00272     return _sets.empty();
00273   }
00274 
00275   template <class T>
00276   inline
00277   typename DetSetVector<T>::size_type
00278   DetSetVector<T>::size() const {
00279     return _sets.size();
00280   }
00281 
00282   template <class T>
00283   inline
00284   typename DetSetVector<T>::iterator
00285   DetSetVector<T>::find(det_id_type id) {
00286     _alreadySorted = false; // it's non const 
00287     std::pair<iterator,iterator> p =
00288       std::equal_range(_sets.begin(), _sets.end(), id);
00289     if (p.first == p.second) return _sets.end();
00290 
00291     // The range indicated by [p.first, p.second) should be exactly of
00292     // length 1. It seems likely we don't want to take the time hit of
00293     // checking this, but here is the appropriate test... We can turn
00294     // it on if we need the debugging aid.
00295     #if 0
00296     assert(std::distance(p.first, p.second) == 1);
00297     #endif
00298 
00299     return p.first;
00300   }
00301 
00302   template <class T>
00303   inline
00304   typename DetSetVector<T>::const_iterator
00305   DetSetVector<T>::find(det_id_type id) const {
00306     std::pair<const_iterator,const_iterator> p =
00307       std::equal_range(_sets.begin(), _sets.end(), id);
00308     if (p.first == p.second) return _sets.end();
00309     // The range indicated by [p.first, p.second) should be exactly of
00310     // length 1.
00311     assert(std::distance(p.first, p.second) == 1);
00312     return p.first;
00313   }
00314 
00315   template <class T>
00316   inline
00317   typename DetSetVector<T>::reference
00318   DetSetVector<T>::operator[](det_id_type i) {
00319     _alreadySorted = false; // it's non const 
00320     // Find the right DetSet, and return a reference to it.  Throw if
00321     // there is none.
00322     iterator it = this->find(i);
00323     if (it == this->end()) detail::_throw_range(i);
00324     return *it;
00325   }
00326 
00327   template <class T>
00328   inline
00329   typename DetSetVector<T>::const_reference
00330   DetSetVector<T>::operator[](det_id_type i) const {
00331     // Find the right DetSet, and return a reference to it.  Throw if
00332     // there is none.
00333     const_iterator it = this->find(i);
00334     if (it == this->end()) detail::_throw_range(i);
00335     return *it;
00336   }
00337 
00338   template <class T>
00339   inline
00340   typename DetSetVector<T>::iterator
00341   DetSetVector<T>::begin() {
00342     _alreadySorted = false; // it's non const 
00343     return _sets.begin();
00344   }
00345 
00346   template <class T>
00347   inline
00348   typename DetSetVector<T>::const_iterator
00349   DetSetVector<T>::begin() const {
00350     return _sets.begin();
00351   }
00352 
00353   template <class T>
00354   inline
00355   typename DetSetVector<T>::iterator
00356   DetSetVector<T>::end() {
00357     _alreadySorted = false; // it's non const 
00358     return _sets.end();
00359   }
00360 
00361   template <class T>
00362   inline
00363   typename DetSetVector<T>::const_iterator
00364   DetSetVector<T>::end() const {
00365     return _sets.end();
00366   }
00367 
00368 
00369   template <class T>
00370   inline
00371   void
00372   DetSetVector<T>::getIds(std::vector<det_id_type> & result) const
00373   {
00374     std::transform(this->begin(), this->end(),
00375                    std::back_inserter(result),
00376                    boost::bind(&DetSet<T>::id,_1));
00377   }
00378 
00379   template <class T>
00380   inline
00381   void
00382   DetSetVector<T>::post_insert() {
00383     if (_alreadySorted) return; 
00384     typename collection_type::iterator i = _sets.begin();
00385     typename collection_type::iterator e = _sets.end();
00386     // For each DetSet...
00387     for (; i != e; ++i) {
00388       // sort the Detset pointed to by
00389       std::sort(i->data.begin(), i->data.end());
00390     }
00391   }
00392 
00393   template <class T>
00394   inline
00395   void
00396   DetSetVector<T>::_sort() {
00397     std::sort(_sets.begin(), _sets.end());
00398   }
00399 
00400   template<class T>
00401   void DetSetVector<T>::fillView(ProductID const& id,
00402                                  std::vector<void const*>& pointers,
00403                                  helper_vector& helpers) const
00404   {
00405     detail::reallyFillView(*this, id, pointers, helpers);
00406   }
00407 
00408   //----------------------------------------------------------------------
00409   //
00410   // Free function template to support creation of Views.
00411 
00412   template <class T>
00413   inline
00414   void
00415   fillView(DetSetVector<T> const& obj,
00416            ProductID const& id,
00417            std::vector<void const*>& pointers,
00418            helper_vector& helpers)
00419   {
00420     obj.fillView(id, pointers, helpers);
00421   }
00422 
00423   template <class T>
00424   struct has_fillView<edm::DetSetVector<T> >
00425   {
00426     static bool const value = true;
00427   };
00428 
00429 
00430   // Free swap function
00431   template <class T>
00432   inline
00433   void
00434   swap(DetSetVector<T>& a, DetSetVector<T>& b) 
00435   {
00436     a.swap(b);
00437   }
00438 
00439 }
00440 
00441 
00442 //specialize behavior of edm::Ref to get access to the 'Det'
00443 namespace edm {
00444 
00445   namespace refhelper {
00446     template<typename T>
00447     class FindForDetSetVector : public std::binary_function<const DetSetVector<T>&, std::pair<det_id_type, typename DetSet<T>::collection_type::size_type>, const T*> {
00448     public:
00449       typedef FindForDetSetVector<T> self;
00450       typename self::result_type operator()(typename self::first_argument_type iContainer, typename self::second_argument_type iIndex) {
00451         return &(*(iContainer.find(iIndex.first)->data.begin()+iIndex.second));
00452       }
00453     };
00454 
00455     template<typename T>
00456       struct FindTrait<DetSetVector<T>,T> {
00457         typedef FindForDetSetVector<T> value;
00458       };
00459   }
00460 
00461    //helper function to make it easier to create a edm::Ref
00462 
00463   template<class HandleT>
00464   Ref<typename HandleT::element_type, typename HandleT::element_type::value_type::value_type>
00465   makeRefTo(const HandleT& iHandle,
00466              det_id_type iDetID,
00467              typename HandleT::element_type::value_type::const_iterator itIter) {
00468     typedef typename HandleT::element_type Vec;
00469     typename Vec::value_type::collection_type::size_type index=0;
00470     typename Vec::const_iterator itFound = iHandle->find(iDetID);
00471     if(itFound == iHandle->end()) {
00472       Exception::throwThis(errors::InvalidReference,
00473         "an edm::Ref to an edm::DetSetVector was given a DetId, ", iDetID, ", that is not in the DetSetVector");
00474     }
00475     index += (itIter- itFound->data.begin());
00476     if(index >= itFound->data.size()) {
00477       Exception::throwThis(errors::InvalidReference,
00478         "an edm::Ref to a edm::DetSetVector is being made with an interator that is not part of the edm::DetSet itself");
00479     }
00480     return Ref<typename HandleT::element_type,
00481                typename HandleT::element_type::value_type::value_type>
00482               (iHandle,std::make_pair(iDetID,index));
00483   }
00484 
00485   template<class HandleT>
00486   Ref<typename HandleT::element_type, typename HandleT::element_type::value_type::value_type>
00487   makeRefToDetSetVector(const HandleT& iHandle,
00488              det_id_type iDetID,
00489              typename HandleT::element_type::value_type::iterator itIter) {
00490     typedef typename HandleT::element_type Vec;
00491     typename Vec::detset::const_iterator itIter2 = itIter;
00492     return makeRefTo(iHandle,iDetID,itIter2);
00493   }
00494 }
00495 #endif