Utilities/interface/IndexSet.h

0001 #ifndef FWCore_Utilities_IndexSet_h
0002 #define FWCore_Utilities_IndexSet_h
0003
0004 #include <vector>
0005
0006 namespace edm {
0007   /**
0008    * A simple class representing a set of indices to another container
0009    * for fast insert and search.
0010    *
0011    * This class can be useful if one needs to record the indices of
0012    * objects that form a subset of a container (e.g. passing some
0013    * selection), and then repeatedly check if an object of a given
0014    * index belongs to that subset. As the elements are assumed to be
0015    * indices, the set can be implemented as a vector<bool> such that
0016    * each possible element corresponds an index in the vector. Then
0017    * the insert and search are (almost) array access operations.
0018    *
0019    * From the set opreations, only insertion, search, and clear are
0020    * supported for now. More can be added if needed.
0021    */
0022   class IndexSet {
0023   public:
0024     /// Construct empty set
0025     IndexSet() : numTrueElements_(0) {}
0026
0027     /// Check if the set is empty
0028     bool empty() const { return numTrueElements_ == 0; }
0029
0030     /// Number of elements in the set
0031     unsigned int size() const { return numTrueElements_; }
0032
0033     /// Reserve memory for the set
0034     void reserve(unsigned int size) {
0035       if (size >= content_.size()) {
0036         content_.resize(size, false);
0037       }
0038     }
0039
0040     /// Clear the set
0041     void clear() {
0042       std::fill(begin(content_), end(content_), false);
0043       numTrueElements_ = 0;
0044     }
0045
0046     /// Insert an element (=index) to the set
0047     void insert(unsigned int index) {
0048       reserve(index + 1);
0049       numTrueElements_ += !content_[index];  // count increases if value was false
0050       content_[index] = true;
0051     }
0052
0053     /// Check if an element (=index) is in the set
0054     bool has(unsigned int index) const { return index < content_.size() && content_[index]; }
0055
0056   private:
0057     std::vector<bool>
0058         content_;  /// Each possible element of the set corresponds an index in this vector. The value of an element tells if that index exists in the set (true) or not (false).
0059     unsigned int numTrueElements_;  /// Count of true elements is equivalent of "size()" of std::set
0060   };
0061 }  // namespace edm
0062
0063 #endif