00001 #ifndef DataFormats_Common_SortedCollection_h
00002 #define DataFormats_Common_SortedCollection_h
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
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
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
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
00071
00072 };
00073
00074
00075 template <typename T, typename SORT>
00076 class SortedCollection {
00077 public:
00078 typedef T value_type;
00079 typedef SORT key_compare;
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
00089
00090
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
00099
00100
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
00116
00117
00118 reference operator[](size_type i);
00119 const_reference operator[](size_type i) const;
00120
00121
00122
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
00138
00139
00140
00141
00142 void sort();
00143
00144
00145
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
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
00265
00266
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
00281
00282
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
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
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
00402
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415
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
00426
00427
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
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
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