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
|