Common/interface/RangeMap.h

0001 #ifndef DataFormats_Common_RangeMap_h
0002 #define DataFormats_Common_RangeMap_h
0003 /* \class edm::RangeMap
0004  *
0005  * Generic container storing objects arranged according
0006  * to a specified identifier.
0007  *
0008  * The data content can be fetched either via
0009  * an iterator, or specifying user-defined identifier
0010  * match criteria.
0011  *
0012  * The template parameters are:
0013  * - ID: identifier type
0014  * - C : underlying collection used to
0015  * - P : policy to perform object cloning
0016  *
0017  * \author Tommaso Boccali, Luca Lista INFN
0018  *
0019  *
0020  */
0021 #include <map>
0022 #include <vector>
0023 #include <functional>
0024 #include "DataFormats/Common/interface/CMS_CLASS_VERSION.h"
0025 #include "FWCore/Utilities/interface/Exception.h"
0026 #include "DataFormats/Common/interface/traits.h"
0027 #include "DataFormats/Common/interface/CloneTrait.h"
0028
0029 namespace edm {
0030
0031   template <typename ID, typename C, typename P = typename clonehelper::CloneTrait<C>::type>
0032   class RangeMap {
0033   public:
0034     /// contained object type
0035     typedef typename C::value_type value_type;
0036     /// collection size type
0037     typedef typename C::size_type size_type;
0038     /// reference type
0039     typedef typename C::reference reference;
0040     /// pointer type
0041     typedef typename C::pointer pointer;
0042     /// constant access iterator type
0043     typedef typename C::const_iterator const_iterator;
0044     /// index range
0045     //use unsigned int rather than C::size_type in order to avoid porting problems
0046     typedef std::pair<unsigned int, unsigned int> pairType;
0047     /// map of identifier to index range
0048     typedef std::map<ID, pairType> mapType;
0049     /// iterator range
0050     typedef std::pair<const_iterator, const_iterator> range;
0051
0052   private:
0053     /// comparator helper class
0054     template <typename CMP>
0055     struct comp {
0056       comp(const CMP c) : cmp(c) {}
0057       bool operator()(ID id, const typename mapType::value_type& p) { return cmp(id, p.first); }
0058       bool operator()(const typename mapType::value_type& p, ID id) { return cmp(p.first, id); }
0059
0060     private:
0061       CMP cmp;
0062     };
0063
0064   public:
0065     /// default constructor
0066     RangeMap() {}
0067     /// get range of objects matching a specified identifier with a specified comparator.
0068     /// <b>WARNING</b>: the comparator has to be written
0069     /// in such a way that the std::equal_range
0070     /// function returns a meaningful range.
0071     /// Not properly written comparators may return
0072     /// an unpredictable range. It is recommended
0073     /// to use only comparators provided with CMSSW release.
0074     template <typename CMP>
0075     range get(ID id, CMP comparator) const {
0076       std::pair<typename mapType::const_iterator, typename mapType::const_iterator> r =
0077           std::equal_range(map_.begin(), map_.end(), id, comp<CMP>(comparator));
0078       const_iterator begin, end;
0079       if ((r.first) == map_.end()) {
0080         begin = end = collection_.end();
0081         return std::make_pair(begin, end);
0082       } else {
0083         begin = collection_.begin() + (r.first)->second.first;
0084       }
0085       if ((r.second) == map_.end()) {
0086         end = collection_.end();
0087       } else {
0088         end = collection_.begin() + (r.second)->second.first;
0089       }
0090       return std::make_pair(begin, end);
0091     }
0092     /// get range of objects matching a specified identifier with a specified comparator.
0093     template <typename CMP>
0094     range get(std::pair<ID, CMP> p) const {
0095       return get(p.first, p.second);
0096     }
0097     /// get a range of objects with specified identifier
0098     range get(ID id) const {
0099       const_iterator begin, end;
0100       typename mapType::const_iterator i = map_.find(id);
0101       if (i != map_.end()) {
0102         begin = collection_.begin() + i->second.first;
0103         end = collection_.begin() + i->second.second;
0104       } else {
0105         begin = end = collection_.end();
0106       }
0107       return std::make_pair(begin, end);
0108     }
0109     /// insert an object range with specified identifier
0110     template <typename CI>
0111     void put(ID id, CI begin, CI end) {
0112       typename mapType::const_iterator i = map_.find(id);
0113       if (i != map_.end()) {
0114         throw Exception(errors::LogicError, "trying to insert duplicate entry");
0115       }
0116       assert(i == map_.end());
0117       pairType& p = map_[id];
0118       p.first = collection_.size();
0119       for (CI ii = begin; ii != end; ++ii)
0120         collection_.push_back(P::clone(*ii));
0121       p.second = collection_.size();
0122     }
0123     /// return number of contained object
0124     size_t size() const { return collection_.size(); }
0125     /// first collection iterator
0126     typename C::const_iterator begin() const { return collection_.begin(); }
0127     /// last collection iterator
0128     typename C::const_iterator end() const { return collection_.end(); }
0129     /// identifier iterator
0130     struct id_iterator {
0131       typedef ID value_type;
0132       typedef ID* pointer;
0133       typedef ID& reference;
0134       typedef ptrdiff_t difference_type;
0135       typedef typename mapType::const_iterator::iterator_category iterator_category;
0136       typedef typename mapType::const_iterator const_iterator;
0137       id_iterator() {}
0138       id_iterator(const_iterator o) : i(o) {}
0139       id_iterator& operator++() {
0140         ++i;
0141         return *this;
0142       }
0143       id_iterator operator++(int) {
0144         id_iterator ci = *this;
0145         ++i;
0146         return ci;
0147       }
0148       id_iterator& operator--() {
0149         --i;
0150         return *this;
0151       }
0152       id_iterator operator--(int) {
0153         id_iterator ci = *this;
0154         --i;
0155         return ci;
0156       }
0157       bool operator==(const id_iterator& ci) const { return i == ci.i; }
0158       bool operator!=(const id_iterator& ci) const { return i != ci.i; }
0159       const ID operator*() const { return i->first; }
0160
0161     private:
0162       const_iterator i;
0163     };
0164     /// perfor post insert action
0165     void post_insert() {
0166       // sorts the container via ID
0167       C tmp;
0168       for (typename mapType::iterator it = map_.begin(), itEnd = map_.end(); it != itEnd; it++) {
0169         range r = get((*it).first);
0170         //do cast to acknowledge that we may be going from a larger type to a smaller type but we are OK
0171         unsigned int begIt = static_cast<unsigned int>(tmp.size());
0172         for (const_iterator i = r.first; i != r.second; ++i)
0173           tmp.push_back(P::clone(*i));
0174         unsigned int endIt = static_cast<unsigned int>(tmp.size());
0175         it->second = pairType(begIt, endIt);
0176       }
0177       collection_ = tmp;
0178     }
0179     /// first identifier iterator
0180     id_iterator id_begin() const { return id_iterator(map_.begin()); }
0181     /// last identifier iterator
0182     id_iterator id_end() const { return id_iterator(map_.end()); }
0183     /// number of contained identifiers
0184     size_t id_size() const { return map_.size(); }
0185     /// indentifier vector
0186     std::vector<ID> ids() const {
0187       std::vector<ID> temp(id_size());
0188       std::copy(id_begin(), id_end(), temp.begin());
0189       return temp;
0190     }
0191     /// direct access to an object in the collection
0192     reference operator[](size_type i) { return collection_[i]; }
0193
0194     /// swap member function
0195     void swap(RangeMap<ID, C, P>& other);
0196
0197     //Used by ROOT storage
0198     CMS_CLASS_VERSION(10)
0199
0200   private:
0201     /// stored collection
0202     C collection_;
0203     /// identifier map
0204     mapType map_;
0205   };
0206
0207   template <typename ID, typename C, typename P>
0208   inline void RangeMap<ID, C, P>::swap(RangeMap<ID, C, P>& other) {
0209     collection_.swap(other.collection_);
0210     map_.swap(other.map_);
0211   }
0212
0213   // free swap function
0214   template <typename ID, typename C, typename P>
0215   inline void swap(RangeMap<ID, C, P>& a, RangeMap<ID, C, P>& b) {
0216     a.swap(b);
0217   }
0218
0219 }  // namespace edm
0220
0221 #endif