Common/interface/SortedCollection.h

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