Line data    Source code

       1             : #ifndef INTSET_H
       2             : #define INTSET_H
       3             : 
       4             : #include <algorithm>
       5             : #include <bitset>
       6             : #include <functional>
       7             : #include <type_traits>
       8             : #include <unordered_set>
       9             : 
      10             : #include "wd2_allocator.h"
      11             : 
      12             : namespace wikidiff2 {
      13             : 
      14             : // The UnsignedSet template class represents a set of unsigned integers.
      15             : // Internally, it uses a fixed-size bitset to store small values and falls
      16             : // back to an std::unordered_set for values that exceed the bitset size.
      17             : // The default bitset size of 512 bytes can hold values in the range [0, 4096).
      18             : template <class T = unsigned int, size_t BitSetSize = 4096>
      19             : class UnsignedSet {
      20             :     static_assert(std::is_unsigned<T>::value,
      21             :         "IntSet<> only works with unsigned integer types.");
      22             : 
      23             :  public:
      24         698 :     UnsignedSet()
      25         698 :         : bitset_(), set_() {}
      26             : 
      27         421 :     void clear() noexcept {
      28         421 :         bitset_.reset();
      29         421 :         set_.clear();
      30         421 :     }
      31             : 
      32       42940 :     void erase(const T& t) {
      33       42940 :         if (t < bitset_.size()) {
      34       42940 :             bitset_.reset(t);
      35             :         } else {
      36           0 :             set_.erase(t);
      37             :         }
      38       42940 :     }
      39             : 
      40       45504 :     void insert(const T& t) {
      41       45504 :         if (t < bitset_.size()) {
      42       45504 :             bitset_.set(t);
      43             :         } else {
      44           0 :             set_.emplace(t);
      45             :         }
      46       45504 :     }
      47             : 
      48       29495 :     bool contains(const T& t) const {
      49       29495 :         if (t < bitset_.size()) {
      50       29495 :             return bitset_.test(t);
      51             :         }
      52           0 :         return set_.find(t) != set_.end();
      53             :     }
      54             : 
      55             :  private:
      56             :     std::bitset<BitSetSize> bitset_;
      57             :     std::unordered_set<T, std::hash<T>, std::equal_to<T>, WD2_ALLOCATOR<T> > set_;
      58             : };
      59             : 
      60             : using IntSet = UnsignedSet<>;
      61             : 
      62             : } // namespace wikidiff2
      63             : 
      64             : #endif  // INTSET_H