Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2023-09-19 00:11:42

0001 #ifndef DataFormats_Common_SortedCollection_h
0002 #define DataFormats_Common_SortedCollection_h
0003 
0004 /*----------------------------------------------------------------------
0005 
0006 SortedCollection: A collection of homogeneous objects that can be used
0007 for an EDProduct. SortedCollection is *not* designed for use as a base
0008 class (it has no virtual functions).
0009 
0010 SortedCollection is in some ways similar to a sequence
0011 (e.g. std::vector and std::list), and in other ways is similar to an
0012 associative collection (e.g. std::map and std::set). SortedCollection
0013 provides keyed access (via operator[]() and find()) to its contained
0014 values. In normal usage, the values contained in a SortedCollection
0015 are sorted according to the order imposed by the ordering of the keys.
0016 
0017 CAVEATS:
0018 
0019 1. The user must make sure that two VALUES with the same KEY are not
0020 never inserted into the sequence. The SortedCollection does not
0021 prevent this, nor does it detect this. However, 'find' will be
0022 unreliable if such duplicate entries are made.
0023 
0024 **************** Much more is needed here! ****************
0025 
0026 ----------------------------------------------------------------------*/
0027 
0028 #include "DataFormats/Common/interface/CMS_CLASS_VERSION.h"
0029 #include "DataFormats/Common/interface/fillPtrVector.h"
0030 #include "DataFormats/Common/interface/FillView.h"
0031 #include "DataFormats/Common/interface/setPtr.h"
0032 #include "DataFormats/Common/interface/traits.h"
0033 #include "DataFormats/Provenance/interface/ProductID.h"
0034 #include "FWCore/Utilities/interface/EDMException.h"
0035 
0036 #include <algorithm>
0037 #include <typeinfo>
0038 #include <vector>
0039 
0040 namespace edm {
0041 
0042   //------------------------------------------------------------
0043   // Forward declarations
0044   //
0045 
0046   template <typename T>
0047   struct StrictWeakOrdering;
0048   template <typename T, typename SORT = StrictWeakOrdering<T> >
0049   class SortedCollection;
0050 
0051   template <typename T, typename SORT>
0052   struct has_fillView<edm::SortedCollection<T, SORT> > {
0053     static bool const value = true;
0054   };
0055 
0056   template <typename T, typename SORT>
0057   struct has_setPtr<edm::SortedCollection<T, SORT> > {
0058     static bool const value = true;
0059   };
0060 
0061   template <typename T>
0062   struct StrictWeakOrdering {
0063     typedef typename T::key_type key_type;
0064 
0065     // Each of the following comparisons are needed (at least with GCC's library).
0066     bool operator()(key_type a, T const& b) const { return a < b.id(); }
0067     bool operator()(T const& a, key_type b) const { return a.id() < b; }
0068     bool operator()(T const& a, T const& b) const { return a.id() < b.id(); }
0069 
0070     // This final comparison is not needed (at least with GCC's library).
0071     // bool operator()(key_type a, key_type b) const { return a < b; }
0072   };
0073 
0074   template <typename T, typename SORT>
0075   class SortedCollection {
0076   public:
0077     typedef T value_type;      // the values we contain
0078     typedef SORT key_compare;  // function object for sorting
0079 
0080     typedef typename std::vector<T>::const_iterator const_iterator;
0081     typedef typename std::vector<T>::iterator iterator;
0082     typedef typename std::vector<T>::const_reference const_reference;
0083     typedef typename std::vector<T>::reference reference;
0084 
0085     typedef typename std::vector<T>::size_type size_type;
0086 
0087     // This needs to be turned into a template parameter, perhaps with
0088     // a default --- if there is a way to slip in the default without
0089     // growing any dependence on the code supplying the key!
0090     typedef typename key_compare::key_type key_type;
0091 
0092     SortedCollection();
0093     explicit SortedCollection(size_type n);
0094     explicit SortedCollection(std::vector<T> const& vec);
0095     SortedCollection(SortedCollection const& h);
0096 
0097     // Add the following when needed
0098     //template<typename InputIterator>
0099     //SortedCollection(InputIterator b, InputIterator e);
0100 
0101     void push_back(T const& t);
0102 #if defined(__GXX_EXPERIMENTAL_CXX0X__)
0103     void push_back(T&& t) { obj.push_back(t); }
0104 
0105     template <typename... Args>
0106     void emplace_back(Args&&... args) {
0107       obj.emplace_back(args...);
0108     }
0109 #endif
0110     void pop_back() { obj.pop_back(); }
0111 
0112     void swap(SortedCollection& other);
0113 
0114     void swap_contents(std::vector<T>& other);
0115 
0116     SortedCollection& operator=(SortedCollection const& rhs);
0117 
0118     bool empty() const;
0119     size_type size() const;
0120     size_type capacity() const;
0121     void reserve(size_type n);
0122 
0123     // Return a reference to the i'th item in the collection.
0124     // Note that the argument is an *integer*, not an object of
0125     //   type key_type
0126     reference operator[](size_type i);
0127     const_reference operator[](size_type i) const;
0128 
0129     // Find the item with key matching k. If no such item is found,
0130     // return end();
0131     iterator find(key_type k);
0132     const_iterator find(key_type k) const;
0133 
0134     const_iterator begin() const;
0135     const_iterator end() const;
0136 
0137     iterator begin();
0138     iterator end();
0139 
0140     const_reference front() const;
0141     reference front();
0142     const_reference back() const;
0143     reference back();
0144 
0145     // Sort the elements of the vector, in the order determined by the
0146     // keys. Note that the Event will make sure to call this function
0147     // after the SortedCollection has been put into the Event, so
0148     // there is no need to call it in user code (unless one needs the
0149     // collection sorted *before* it is inserted into the Event).
0150     void sort();
0151 
0152     // This function will be called by the edm::Event after the
0153     // SortedCollection has been inserted into the Event.
0154     void post_insert();
0155 
0156     void fillView(ProductID const& id, std::vector<void const*>& pointers, FillViewHelperVector& helpers) const;
0157 
0158     void setPtr(std::type_info const& toType, unsigned long index, void const*& ptr) const;
0159 
0160     void fillPtrVector(std::type_info const& toType,
0161                        std::vector<unsigned long> const& indices,
0162                        std::vector<void const*>& ptrs) const;
0163 
0164     //Used by ROOT storage
0165     CMS_CLASS_VERSION(10)
0166 
0167   private:
0168     typedef std::vector<T> collection_type;
0169     typedef typename collection_type::const_iterator const_inner_iterator;
0170     typedef typename collection_type::iterator inner_iterator;
0171 
0172     collection_type obj;
0173   };
0174 
0175   template <typename T, typename SORT>
0176   inline SortedCollection<T, SORT>::SortedCollection() : obj() {}
0177 
0178   template <typename T, typename SORT>
0179   inline SortedCollection<T, SORT>::SortedCollection(size_type n) : obj(n) {}
0180 
0181   template <typename T, typename SORT>
0182   inline SortedCollection<T, SORT>::SortedCollection(std::vector<T> const& vec) : obj(vec) {}
0183 
0184   template <typename T, typename SORT>
0185   inline SortedCollection<T, SORT>::SortedCollection(SortedCollection<T, SORT> const& h) : obj(h.obj) {}
0186 
0187   template <typename T, typename SORT>
0188   inline void SortedCollection<T, SORT>::push_back(T const& t) {
0189     obj.push_back(t);
0190   }
0191 
0192   template <typename T, typename SORT>
0193   inline void SortedCollection<T, SORT>::swap(SortedCollection<T, SORT>& other) {
0194     obj.swap(other.obj);
0195   }
0196 
0197   template <typename T, typename SORT>
0198   inline void SortedCollection<T, SORT>::swap_contents(std::vector<T>& other) {
0199     obj.swap(other);
0200   }
0201 
0202   template <typename T, typename SORT>
0203   inline SortedCollection<T, SORT>& SortedCollection<T, SORT>::operator=(SortedCollection<T, SORT> const& rhs) {
0204     SortedCollection<T, SORT> temp(rhs);
0205     this->swap(temp);
0206     return *this;
0207   }
0208 
0209   template <typename T, typename SORT>
0210   inline bool SortedCollection<T, SORT>::empty() const {
0211     return obj.empty();
0212   }
0213 
0214   template <typename T, typename SORT>
0215   inline typename SortedCollection<T, SORT>::size_type SortedCollection<T, SORT>::size() const {
0216     return obj.size();
0217   }
0218 
0219   template <typename T, typename SORT>
0220   inline typename SortedCollection<T, SORT>::size_type SortedCollection<T, SORT>::capacity() const {
0221     return obj.capacity();
0222   }
0223 
0224   template <typename T, typename SORT>
0225   inline void SortedCollection<T, SORT>::reserve(typename SortedCollection<T, SORT>::size_type n) {
0226     obj.reserve(n);
0227   }
0228 
0229   template <typename T, typename SORT>
0230   inline typename SortedCollection<T, SORT>::reference SortedCollection<T, SORT>::operator[](size_type i) {
0231     return obj[i];
0232   }
0233 
0234   template <typename T, typename SORT>
0235   inline typename SortedCollection<T, SORT>::const_reference SortedCollection<T, SORT>::operator[](size_type i) const {
0236     return obj[i];
0237   }
0238 
0239   template <typename T, typename SORT>
0240   inline typename SortedCollection<T, SORT>::iterator SortedCollection<T, SORT>::find(key_type key) {
0241     // This fails if the SortedCollection has not been sorted. It is
0242     // up to the user (with the help of the Event) to make sure this
0243     // has been done.
0244     key_compare comp;
0245     inner_iterator last = obj.end();
0246     inner_iterator loc = std::lower_bound(obj.begin(), last, key, comp);
0247     return loc == last || comp(key, *loc) ? last : loc;
0248   }
0249 
0250   template <typename T, typename SORT>
0251   inline typename SortedCollection<T, SORT>::const_iterator SortedCollection<T, SORT>::find(key_type key) const {
0252     // This fails if the SortedCollection has not been sorted. It is
0253     // up to the user (with the help of the Event) to make sure this
0254     // has been done.
0255     key_compare comp;
0256     const_inner_iterator last = obj.end();
0257     const_inner_iterator loc = std::lower_bound(obj.begin(), last, key, comp);
0258     return loc == last || comp(key, *loc) ? last : loc;
0259   }
0260 
0261   template <typename T, typename SORT>
0262   inline typename SortedCollection<T, SORT>::const_iterator SortedCollection<T, SORT>::begin() const {
0263     return obj.begin();
0264   }
0265 
0266   template <typename T, typename SORT>
0267   inline typename SortedCollection<T, SORT>::const_iterator SortedCollection<T, SORT>::end() const {
0268     return obj.end();
0269   }
0270 
0271   template <typename T, typename SORT>
0272   inline typename SortedCollection<T, SORT>::iterator SortedCollection<T, SORT>::begin() {
0273     return obj.begin();
0274   }
0275 
0276   template <typename T, typename SORT>
0277   inline typename SortedCollection<T, SORT>::iterator SortedCollection<T, SORT>::end() {
0278     return obj.end();
0279   }
0280 
0281   template <typename T, typename SORT>
0282   inline typename SortedCollection<T, SORT>::const_reference SortedCollection<T, SORT>::front() const {
0283     return obj.front();
0284   }
0285 
0286   template <typename T, typename SORT>
0287   inline typename SortedCollection<T, SORT>::reference SortedCollection<T, SORT>::front() {
0288     return obj.front();
0289   }
0290 
0291   template <typename T, typename SORT>
0292   inline typename SortedCollection<T, SORT>::const_reference SortedCollection<T, SORT>::back() const {
0293     return obj.back();
0294   }
0295 
0296   template <typename T, typename SORT>
0297   inline typename SortedCollection<T, SORT>::reference SortedCollection<T, SORT>::back() {
0298     return obj.back();
0299   }
0300 
0301   template <typename T, typename SORT>
0302   inline void SortedCollection<T, SORT>::sort() {
0303     key_compare comp;
0304     std::sort(obj.begin(), obj.end(), comp);
0305   }
0306 
0307   template <typename T, typename SORT>
0308   inline void SortedCollection<T, SORT>::post_insert() {
0309     // After insertion, we make sure our contents are sorted.
0310     sort();
0311   }
0312 
0313   template <typename T, typename SORT>
0314   inline void SortedCollection<T, SORT>::fillView(ProductID const& id,
0315                                                   std::vector<void const*>& pointers,
0316                                                   FillViewHelperVector& helpers) const {
0317     detail::reallyFillView(*this, id, pointers, helpers);
0318   }
0319 
0320   template <typename T, typename SORT>
0321   inline void SortedCollection<T, SORT>::setPtr(std::type_info const& toType,
0322                                                 unsigned long index,
0323                                                 void const*& ptr) const {
0324     detail::reallySetPtr(*this, toType, index, ptr);
0325   }
0326 
0327   template <typename T, typename SORT>
0328   inline void SortedCollection<T, SORT>::fillPtrVector(std::type_info const& toType,
0329                                                        std::vector<unsigned long> const& indices,
0330                                                        std::vector<void const*>& ptrs) const {
0331     detail::reallyfillPtrVector(*this, toType, indices, ptrs);
0332   }
0333 
0334   // Free swap function
0335   template <typename T, typename SORT>
0336   inline void swap(SortedCollection<T, SORT>& a, SortedCollection<T, SORT>& b) {
0337     a.swap(b);
0338   }
0339 
0340   //----------------------------------------------------------------------
0341   //
0342   // Free function templates to support comparisons.
0343 
0344   // The two function templates below are not written as a single
0345   // function template in order to avoid inadvertent matches with
0346   // inappropriate template arguments. Template template parameters
0347   // were avoided to stay away from generic programming problems
0348   // sometimes encountered in the presence of such parameters.  If
0349   // support for comparison between SortedCollections and other sorts
0350   // of collections is needed, it can be added.
0351 
0352   // comparison with vector tests to see whether the entries in the
0353   // SortedCollection are the same as the entries in the vector, *and
0354   // in the same order.
0355   // operator==(T const& a, T const& b) is used to compare the elements in
0356   // the collections.
0357 
0358   template <typename T, typename SORT, typename ALLOC>
0359   inline bool operator==(SortedCollection<T, SORT> const& c, std::vector<T, ALLOC> const& v) {
0360     return c.size() == v.size() && std::equal(v.begin(), v.end(), c.begin());
0361   }
0362 
0363   // comparison of two SortedCollections is done by comparing the
0364   // collected elements, in order for equality.
0365   // operator==(T const& a, T const& b) is used to compare the elements.
0366 
0367   template <typename T, typename SORT>
0368   inline bool operator==(SortedCollection<T, SORT> const& a, SortedCollection<T, SORT> const& b) {
0369     return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
0370   }
0371 
0372   //----------------------------------------------------------------------
0373   //
0374   // Free function template to support creation of Views.
0375 
0376   template <typename T, typename SORT>
0377   inline void fillView(SortedCollection<T, SORT> const& obj,
0378                        ProductID const& id,
0379                        std::vector<void const*>& pointers,
0380                        FillViewHelperVector& helpers) {
0381     obj.fillView(id, pointers, helpers);
0382   }
0383 
0384   // Free function templates to support the use of edm::Ptr.
0385   template <typename T, typename SORT>
0386   inline void setPtr(SortedCollection<T, SORT> const& obj,
0387                      std::type_info const& toType,
0388                      unsigned long index,
0389                      void const*& ptr) {
0390     obj.setPtr(toType, index, ptr);
0391   }
0392 
0393   template <typename T, typename SORT>
0394   inline void fillPtrVector(SortedCollection<T, SORT> const& obj,
0395                             std::type_info const& toType,
0396                             std::vector<unsigned long> const& indices,
0397                             std::vector<void const*>& ptrs) {
0398     obj.fillPtrVector(toType, indices, ptrs);
0399   }
0400 }  // namespace edm
0401 
0402 #endif