1 #ifndef __SPARSE_SET_H__
2 #define __SPARSE_SET_H__
3 // U indicates whether to use FAST_FSET.
4 #include <cassert>
5 #include <cstdlib>
6 
7 template<int U = 0>
8 class SparseSet {
9 public:
SparseSet(void)10    SparseSet(void) : dom(0), sparse(NULL), dense(NULL), members( 0 )
11    {
12 
13    }
14 
SparseSet(unsigned int size)15    SparseSet(unsigned int size) : dom(size),
16       sparse((unsigned int*) malloc(size*sizeof(unsigned int))),
17       dense((unsigned int*) malloc(size*sizeof(unsigned int))),
18       members( 0 )
19    {
20       if( U&1 )
21       {
22          assert( members == 0 );
23          for( unsigned int i = 0; i < dom; i++ )
24          {
25              sparse[i] = i;
26              dense[i] = i;
27          }
28       }
29    }
30 
~SparseSet()31    ~SparseSet() {
32       if( sparse )
33          free(sparse);
34       if( dense )
35          free(dense);
36    }
37 
elem(unsigned int value)38    bool elem(unsigned int value) const {
39       if( U&1 )
40       {
41          return (sparse[value] < members);
42       } else {
43          unsigned int a = sparse[value];
44 
45          if( a < members && dense[a] == value )
46             return true;
47          return false;
48       }
49    }
50 
elemLim(unsigned int lim,unsigned int el)51    bool elemLim(unsigned int lim, unsigned int el)
52    {
53       return (sparse[el] < lim) && elem(el);
54    }
55 
insert(unsigned int value)56    virtual bool insert(unsigned int value)
57    {
58       if( U&1 )
59       {
60          unsigned int old_dense = sparse[value];
61          unsigned int lost_val = dense[members];
62 
63          sparse[value] = members;
64          dense[members] = value;
65 
66          sparse[lost_val] = old_dense;
67          dense[old_dense] = lost_val;
68       } else {
69         assert( !elem(value) );
70 
71         sparse[value] = members;
72         dense[members] = value;
73       }
74       members++;
75 
76       return true;
77    }
78 
clear(void)79    void clear(void) {
80       members = 0;
81    }
82 
pos(unsigned int val)83    unsigned int pos(unsigned int val) const
84    {
85       assert( elem(val) );
86       return sparse[val];
87    }
88 
89    unsigned int operator [] (unsigned int index) {
90       assert(index < members);
91       return dense[index];
92    }
93 
growTo(unsigned int sz)94    void growTo(unsigned int sz)
95    {
96       if( sz > dom )
97       {
98          sparse = (unsigned int*) realloc(sparse,sizeof(unsigned int)*sz);
99          dense = (unsigned int*) realloc(dense,sizeof(unsigned int)*sz);
100 
101          if( U&1 )
102          {
103             assert( members == 0 );
104             for(; dom < sz; dom++ )
105             {
106                 sparse[dom] = dom;
107                 dense[dom] = dom;
108             }
109          }
110       }
111    }
112 
size(void)113    unsigned int size(void) {
114       return members;
115    }
116 
domain(void)117    unsigned int domain(void) {
118       return dom;
119    }
120 
121 protected:
122    unsigned int dom;
123    unsigned int* sparse;
124    unsigned int* dense;
125    unsigned int members;
126 };
127 
128 class TrailedSet : public SparseSet<0> {
129 public:
TrailedSet(int sz)130    TrailedSet(int sz) : SparseSet<0>( sz )
131    {
132 
133    }
134 
insert(int value)135    bool insert(int value)
136    {
137        // Assumes not FFSET.
138       assert( !elem(value) );
139 
140       sparse[value] = members;
141       dense[members] = value;
142 
143       trailChange(members,members+1);
144 
145       return true;
146    }
147 };
148 
149 // Variant of a trailed sparse set which
150 // only trails at the end of a series of operations.
151 class DeferredSet : public SparseSet<0> {
152 public:
DeferredSet(int sz)153   DeferredSet(int sz) : SparseSet<0>( sz )
154   {
155 
156   }
157 
158   // Ensure members is given the correct value.
refresh(void)159   inline void refresh(void)
160   {
161     members = stored;
162   }
163 
commit(void)164   inline void commit(void)
165   {
166     if(stored != members)
167       trailChange(stored, members);
168   }
169 protected:
170   unsigned int stored;
171 };
172 #endif
173