Branch data     Line data    Source code

       1                 :            : // $Id: IntSet.h 80 2004-07-14 20:15:50Z jason $
       2                 :            : 
       3                 :            : // A simple but fast data structure for sets of integers.
       4                 :            : // Only supported operations are insert, remove and membership test.
       5                 :            : //
       6                 :            : // It's implemented via a bitmap so the memory usage increases linearly
       7                 :            : // with max(set).
       8                 :            : 
       9                 :            : #ifndef intset_h
      10                 :            : #define intset_h
      11                 :            : 
      12                 :            : #include <string.h>
      13                 :            : 
      14                 :            : class IntSet {
      15                 :            : public:
      16                 :            :         // n is a hint for the value of the largest integer.
      17                 :            :         IntSet(unsigned int n = 1);
      18                 :            :         ~IntSet();
      19                 :            : 
      20                 :            :         void Insert(unsigned int i);
      21                 :            :         void Remove(unsigned int i);
      22                 :            :         bool Contains(unsigned int i) const;
      23                 :            : 
      24                 :            :         void Clear();
      25                 :            : 
      26                 :            : private:
      27                 :            :         void Expand(unsigned int i);
      28                 :            : 
      29                 :            :         unsigned int size;
      30                 :            :         unsigned char* set;
      31                 :            :         };
      32                 :            : 
      33                 :            : 
      34                 :            : #define bzero(p, size) memset(p, 0, size)
      35                 :            : 
      36                 :         24 : inline IntSet::IntSet(unsigned int n)
      37                 :            :         {
      38                 :         24 :         size = n / 8 + 1;
      39                 :         24 :         set = new unsigned char[size];
      40                 :         24 :         bzero(set, size);
      41                 :         24 :         }
      42                 :            : 
      43                 :          2 : inline IntSet::~IntSet()
      44                 :            :         {
      45         [ +  - ]:          2 :         delete [] set;
      46                 :          2 :         }
      47                 :            : 
      48                 :      35933 : inline void IntSet::Insert(unsigned int i)
      49                 :            :         {
      50         [ +  + ]:      35933 :         if ( i / 8 >= size )
      51                 :        885 :                 Expand(i);
      52                 :            : 
      53                 :      35933 :         set[i / 8] |= (1 << (i % 8));
      54                 :      35933 :         }
      55                 :            : 
      56                 :            : inline void IntSet::Remove(unsigned int i)
      57                 :            :         {
      58                 :            :         if ( i / 8 >= size )
      59                 :            :                 Expand(i);
      60                 :            :         else
      61                 :            :                 set[i / 8] &= ~(1 << (i % 8));
      62                 :            :         }
      63                 :            : 
      64                 :      36209 : inline bool IntSet::Contains(unsigned int i) const
      65                 :            :         {
      66         [ +  + ]:      36209 :         return i / 8 < size ? set[i / 8] & (1 << (i % 8)) : false;
      67                 :            :         }
      68                 :            : 
      69                 :       1082 : inline void IntSet::Clear()
      70                 :            :         {
      71                 :       1082 :         bzero(set, size);
      72                 :       1082 :         }
      73                 :            : 
      74                 :            : #endif