CMS 3D CMS Logo

/data/doxygen/doxygen-1.7.3/gen/CMSSW_4_2_8/src/DataFormats/Common/interface/SortedCollection.h

Go to the documentation of this file.
00001 #ifndef DataFormats_Common_SortedCollection_h
00002 #define DataFormats_Common_SortedCollection_h
00003 
00004 /*----------------------------------------------------------------------
00005 
00006 SortedCollection: A collection of homogeneous objects that can be used
00007 for an EDProduct. SortedCollection is *not* designed for use as a base
00008 class (it has no virtual functions).
00009 
00010 SortedCollection is in some ways similar to a sequence
00011 (e.g. std::vector and std::list), and in other ways is similar to an
00012 associative collection (e.g. std::map and std::set). SortedCollection
00013 provides keyed access (via operator[]() and find()) to its contained
00014 values. In normal usage, the values contained in a SortedCollection
00015 are sorted according to the order imposed by the ordering of the keys.
00016 
00017 CAVEATS:
00018 
00019 1. The user must make sure that two VALUES with the same KEY are not
00020 never inserted into the sequence. The SortedCollection does not
00021 prevent this, nor does it detect this. However, 'find' will be
00022 unreliable if such duplicate entries are made.
00023 
00024 **************** Much more is needed here! ****************
00025 
00026 ----------------------------------------------------------------------*/
00027 
00028 #include "DataFormats/Common/interface/CMS_CLASS_VERSION.h"
00029 #include "DataFormats/Common/interface/EDProduct.h"
00030 #include "DataFormats/Common/interface/fillPtrVector.h"
00031 #include "DataFormats/Common/interface/FillView.h"
00032 #include "DataFormats/Common/interface/Ref.h"
00033 #include "DataFormats/Common/interface/traits.h"
00034 #include "DataFormats/Provenance/interface/ProductID.h"
00035 #include "FWCore/Utilities/interface/EDMException.h"
00036 
00037 #include <algorithm>
00038 #include <typeinfo>
00039 #include <vector>
00040 
00041 namespace edm {
00042 
00043   //------------------------------------------------------------
00044   // Forward declarations
00045   //
00046 
00047   template <typename T> struct StrictWeakOrdering;
00048   template <typename T, typename SORT = StrictWeakOrdering<T> >
00049     class SortedCollection;
00050 
00051   template <typename T, typename SORT>
00052   struct has_fillView<edm::SortedCollection<T, SORT> > {
00053     static bool const value = true;
00054   };
00055 
00056   template <typename T, typename SORT>
00057   struct has_setPtr<edm::SortedCollection<T, SORT> > {
00058     static bool const value = true;
00059   };
00060 
00061   template <typename T>
00062   struct StrictWeakOrdering {
00063     typedef typename T::key_type key_type;
00064 
00065     // Each of the following comparisons are needed (at least with GCC's library).
00066     bool operator()(key_type a, T const& b) const { return a < b.id(); }
00067     bool operator()(T const& a, key_type b) const { return a.id() < b; }
00068     bool operator()(T const& a, T const& b) const { return a.id() < b.id(); }
00069 
00070     // This final comparison is not needed (at least with GCC's library).
00071     // bool operator()(key_type a, key_type b) const { return a < b; }
00072   };
00073 
00074 
00075   template <typename T, typename SORT>
00076   class SortedCollection {
00077   public:
00078     typedef T    value_type;    // the values we contain
00079     typedef SORT key_compare;   // function object for sorting
00080 
00081     typedef typename std::vector<T>::const_iterator  const_iterator;
00082     typedef typename std::vector<T>::iterator        iterator;
00083     typedef typename std::vector<T>::const_reference const_reference;
00084     typedef typename std::vector<T>::reference       reference;
00085 
00086     typedef typename std::vector<T>::size_type      size_type;
00087 
00088     // This needs to be turned into a template parameter, perhaps with
00089     // a default --- if there is a way to slip in the default without
00090     // growing any dependence on the code supplying the key!
00091     typedef typename key_compare::key_type key_type;
00092 
00093     SortedCollection();
00094     explicit SortedCollection(size_type n);
00095     explicit SortedCollection(std::vector<T> const& vec);
00096     SortedCollection(SortedCollection const& h);
00097 
00098     // Add the following when needed
00099     //template <typename InputIterator>
00100     //SortedCollection(InputIterator b, InputIterator e);
00101 
00102     void push_back(T const& t);
00103 
00104     void swap(SortedCollection& other);
00105 
00106     void swap_contents(std::vector<T>& other);
00107 
00108     SortedCollection& operator=(SortedCollection const& rhs);
00109 
00110     bool empty() const;
00111     size_type size() const;
00112     size_type capacity() const;
00113     void reserve(size_type n);
00114 
00115     // Return a reference to the i'th item in the collection.
00116     // Note that the argument is an *integer*, not an object of
00117     //   type key_type
00118     reference       operator[](size_type i);
00119     const_reference operator[](size_type i) const;
00120 
00121     // Find the item with key matching k. If no such item is found,
00122     // return end();
00123     iterator       find(key_type k);
00124     const_iterator find(key_type k) const;
00125 
00126     const_iterator begin() const;
00127     const_iterator end() const;
00128 
00129     iterator begin();
00130     iterator end();
00131 
00132     const_reference front() const;
00133     reference       front();
00134     const_reference back() const;
00135     reference       back();
00136 
00137     // Sort the elements of the vector, in the order determined by the
00138     // keys. Note that the Event will make sure to call this function
00139     // after the SortedCollection has been put into the Event, so
00140     // there is no need to call it in user code (unless one needs the
00141     // collection sorted *before* it is inserted into the Event).
00142     void sort();
00143 
00144     // This function will be called by the edm::Event after the
00145     // SortedCollection has been inserted into the Event.
00146     void post_insert();
00147 
00148     void fillView(ProductID const& id,
00149                   std::vector<void const*>& pointers,
00150                   helper_vector& helpers) const;
00151 
00152     void setPtr(std::type_info const& toType,
00153                 unsigned long index,
00154                 void const*& ptr) const;
00155 
00156     void fillPtrVector(std::type_info const& toType,
00157                        std::vector<unsigned long> const& indices,
00158                        std::vector<void const*>& ptrs) const;
00159 
00160     //Used by ROOT storage
00161     CMS_CLASS_VERSION(10)
00162 
00163   private:
00164 
00165     typedef std::vector<T> collection_type;
00166     typedef typename collection_type::const_iterator const_inner_iterator;
00167     typedef typename collection_type::iterator       inner_iterator;
00168 
00169     collection_type   obj;
00170   };
00171 
00172   template <typename T, typename SORT>
00173   inline
00174   SortedCollection<T, SORT>::SortedCollection() : obj() {}
00175 
00176   template <typename T, typename SORT>
00177   inline
00178   SortedCollection<T, SORT>::SortedCollection(size_type n) : obj(n) {}
00179 
00180   template <typename T, typename SORT>
00181   inline
00182   SortedCollection<T, SORT>::SortedCollection(std::vector<T> const& vec) : obj(vec) {}
00183 
00184   template <typename T, typename SORT>
00185   inline
00186   SortedCollection<T, SORT>::SortedCollection(SortedCollection<T, SORT> const& h) : obj(h.obj) {}
00187 
00188   template <typename T, typename SORT>
00189   inline
00190   void
00191   SortedCollection<T, SORT>::push_back(T const& t) {
00192     obj.push_back(t);
00193   }
00194 
00195   template <typename T, typename SORT>
00196   inline
00197   void
00198   SortedCollection<T, SORT>::swap(SortedCollection<T, SORT>& other) {
00199     obj.swap(other.obj);
00200   }
00201 
00202   template <typename T, typename SORT>
00203   inline
00204   void
00205   SortedCollection<T, SORT>::swap_contents(std::vector<T>& other) {
00206     obj.swap(other);
00207   }
00208 
00209   template <typename T, typename SORT>
00210   inline
00211   SortedCollection<T, SORT>&
00212   SortedCollection<T, SORT>::operator=(SortedCollection<T, SORT> const& rhs) {
00213     SortedCollection<T, SORT> temp(rhs);
00214     this->swap(temp);
00215     return *this;
00216   }
00217 
00218   template <typename T, typename SORT>
00219   inline
00220   bool
00221   SortedCollection<T, SORT>::empty() const {
00222     return obj.empty();
00223   }
00224 
00225   template <typename T, typename SORT>
00226   inline
00227   typename SortedCollection<T, SORT>::size_type
00228   SortedCollection<T, SORT>::size() const {
00229     return obj.size();
00230   }
00231 
00232   template <typename T, typename SORT>
00233   inline
00234   typename SortedCollection<T, SORT>::size_type
00235   SortedCollection<T, SORT>::capacity() const {
00236     return obj.capacity();
00237   }
00238 
00239   template <typename T, typename SORT>
00240   inline
00241   void
00242   SortedCollection<T, SORT>::reserve(typename SortedCollection<T, SORT>::size_type n) {
00243     obj.reserve(n);
00244   }
00245 
00246   template <typename T, typename SORT>
00247   inline
00248   typename SortedCollection<T, SORT>::reference
00249   SortedCollection<T, SORT>::operator[](size_type i) {
00250     return obj[i];
00251   }
00252 
00253   template <typename T, typename SORT>
00254   inline
00255   typename SortedCollection<T, SORT>::const_reference
00256   SortedCollection<T, SORT>::operator[](size_type i) const {
00257     return obj[i];
00258   }
00259 
00260   template <typename T, typename SORT>
00261   inline
00262   typename SortedCollection<T, SORT>::iterator
00263   SortedCollection<T, SORT>::find(key_type key) {
00264     // This fails if the SortedCollection has not been sorted. It is
00265     // up to the user (with the help of the Event) to make sure this
00266     // has been done.
00267     key_compare comp;
00268     inner_iterator last = obj.end();
00269     inner_iterator loc = std::lower_bound(obj.begin(),
00270                                           last,
00271                                           key,
00272                                           comp);
00273     return loc == last || comp(key, *loc) ? last : loc;
00274   }
00275 
00276   template <typename T, typename SORT>
00277   inline
00278   typename SortedCollection<T, SORT>::const_iterator
00279   SortedCollection<T, SORT>::find(key_type key) const {
00280     // This fails if the SortedCollection has not been sorted. It is
00281     // up to the user (with the help of the Event) to make sure this
00282     // has been done.
00283     key_compare  comp;
00284     const_inner_iterator last = obj.end();
00285     const_inner_iterator loc = std::lower_bound(obj.begin(),
00286                                                 last,
00287                                                 key,
00288                                                 comp);
00289     return loc == last || comp(key, *loc) ? last : loc;
00290   }
00291 
00292   template <typename T, typename SORT>
00293   inline
00294   typename SortedCollection<T, SORT>::const_iterator
00295   SortedCollection<T, SORT>::begin() const {
00296     return obj.begin();
00297   }
00298 
00299   template <typename T, typename SORT>
00300   inline
00301   typename SortedCollection<T, SORT>::const_iterator
00302   SortedCollection<T, SORT>::end() const {
00303     return obj.end();
00304   }
00305 
00306   template <typename T, typename SORT>
00307   inline
00308   typename SortedCollection<T, SORT>::iterator
00309   SortedCollection<T, SORT>::begin() {
00310     return obj.begin();
00311   }
00312 
00313   template <typename T, typename SORT>
00314   inline
00315   typename SortedCollection<T, SORT>::iterator
00316   SortedCollection<T, SORT>::end() {
00317     return obj.end();
00318   }
00319 
00320   template <typename T, typename SORT>
00321   inline
00322   typename SortedCollection<T, SORT>::const_reference
00323   SortedCollection<T, SORT>::front() const {
00324     return obj.front();
00325   }
00326 
00327   template <typename T, typename SORT>
00328   inline
00329   typename SortedCollection<T, SORT>::reference
00330   SortedCollection<T, SORT>::front() {
00331     return obj.front();
00332   }
00333 
00334   template <typename T, typename SORT>
00335   inline
00336   typename SortedCollection<T, SORT>::const_reference
00337   SortedCollection<T, SORT>::back() const {
00338     return obj.back();
00339   }
00340 
00341   template <typename T, typename SORT>
00342   inline
00343   typename SortedCollection<T, SORT>::reference
00344   SortedCollection<T, SORT>::back() {
00345     return obj.back();
00346   }
00347 
00348   template <typename T, typename SORT>
00349   inline
00350   void
00351   SortedCollection<T, SORT>::sort() {
00352     key_compare  comp;
00353     std::sort(obj.begin(), obj.end(), comp);
00354   }
00355 
00356   template <typename T, typename SORT>
00357   inline
00358   void
00359   SortedCollection<T, SORT>::post_insert() {
00360     // After insertion, we make sure our contents are sorted.
00361     sort();
00362   }
00363 
00364   template <typename T, typename SORT>
00365   inline
00366   void
00367   SortedCollection<T, SORT>::fillView(ProductID const& id,
00368                                      std::vector<void const*>& pointers,
00369                                      helper_vector& helpers) const {
00370     detail::reallyFillView(*this, id, pointers, helpers);
00371   }
00372 
00373   template <typename T, typename SORT>
00374   inline
00375   void
00376   SortedCollection<T, SORT>::setPtr(std::type_info const& toType,
00377                                    unsigned long index,
00378                                    void const*& ptr) const {
00379     detail::reallySetPtr(*this, toType, index, ptr);
00380   }
00381 
00382   template <typename T, typename SORT>
00383   inline
00384   void
00385   SortedCollection<T, SORT>::fillPtrVector(std::type_info const& toType,
00386                                           std::vector<unsigned long> const& indices,
00387                                           std::vector<void const*>& ptrs) const {
00388     detail::reallyfillPtrVector(*this, toType, indices, ptrs);
00389   }
00390 
00391   // Free swap function
00392   template <typename T, typename SORT>
00393   inline
00394   void
00395   swap(SortedCollection<T, SORT>& a, SortedCollection<T, SORT>& b) {
00396     a.swap(b);
00397   }
00398 
00399   //----------------------------------------------------------------------
00400   //
00401   // Free function templates to support comparisons.
00402 
00403   // The two function templates below are not written as a single
00404   // function template in order to avoid inadvertent matches with
00405   // inappropriate template arguments. Template template parameters
00406   // were avoided to stay away from generic programming problems
00407   // sometimes encountered in the presence of such parameters.  If
00408   // support for comparison between SortedCollections and other sorts
00409   // of collections is needed, it can be added.
00410 
00411   // comparison with vector tests to see whether the entries in the
00412   // SortedCollection are the same as the entries in the vector, *and
00413   // in the same order.
00414   // operator==(T const& a, T const& b) is used to compare the elements in
00415   // the collections.
00416 
00417   template <typename T, typename SORT, typename ALLOC>
00418   inline
00419   bool
00420   operator==(SortedCollection<T, SORT> const& c,
00421              std::vector<T, ALLOC>     const& v) {
00422     return c.size() == v.size() && std::equal(v.begin(), v.end(), c.begin());
00423   }
00424 
00425   // comparison of two SortedCollections is done by comparing the
00426   // collected elements, in order for equality.
00427   // operator==(T const& a, T const& b) is used to compare the elements.
00428 
00429   template <typename T, typename SORT>
00430   inline
00431   bool
00432   operator==(SortedCollection<T, SORT> const& a,
00433              SortedCollection<T, SORT> const& b) {
00434     return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
00435   }
00436 
00437   //----------------------------------------------------------------------
00438   //
00439   // Free function template to support creation of Views.
00440 
00441   template <typename T, typename SORT>
00442   inline
00443   void
00444   fillView(SortedCollection<T, SORT> const& obj,
00445            ProductID const& id,
00446            std::vector<void const*>& pointers,
00447            helper_vector& helpers) {
00448     obj.fillView(id, pointers, helpers);
00449   }
00450 
00451   // Free function templates to support the use of edm::Ptr.
00452   template <typename T, typename SORT>
00453   inline
00454   void
00455   setPtr(SortedCollection<T, SORT> const& obj,
00456          std::type_info const& toType,
00457          unsigned long index,
00458          void const*& ptr) {
00459     obj.setPtr(toType, index, ptr);
00460   }
00461 
00462   template <typename T, typename SORT>
00463   inline
00464   void
00465   fillPtrVector(SortedCollection<T, SORT> const& obj,
00466                 std::type_info const& toType,
00467                 std::vector<unsigned long> const& indices,
00468                 std::vector<void const*>& ptrs) {
00469     obj.fillPtrVector(toType, indices, ptrs);
00470   }
00471 }
00472 
00473 #endif