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