99 |
99 |
100 //------------------------------operator<<=------------------------------------ |
100 //------------------------------operator<<=------------------------------------ |
101 // Insert a member into an existing Set. |
101 // Insert a member into an existing Set. |
102 Set &VectorSet::operator <<= (uint elem) |
102 Set &VectorSet::operator <<= (uint elem) |
103 { |
103 { |
104 register uint word = elem >> 5; // Get the longword offset |
104 uint word = elem >> 5; // Get the longword offset |
105 register uint32_t mask = 1L << (elem & 31); // Get bit mask |
105 uint32_t mask = 1L << (elem & 31); // Get bit mask |
106 |
106 |
107 if( word >= size ) // Need to grow set? |
107 if( word >= size ) // Need to grow set? |
108 grow(elem+1); // Then grow it |
108 grow(elem+1); // Then grow it |
109 data[word] |= mask; // Set new bit |
109 data[word] |= mask; // Set new bit |
110 return *this; |
110 return *this; |
112 |
112 |
113 //------------------------------operator>>=------------------------------------ |
113 //------------------------------operator>>=------------------------------------ |
114 // Delete a member from an existing Set. |
114 // Delete a member from an existing Set. |
115 Set &VectorSet::operator >>= (uint elem) |
115 Set &VectorSet::operator >>= (uint elem) |
116 { |
116 { |
117 register uint word = elem >> 5; // Get the longword offset |
117 uint word = elem >> 5; // Get the longword offset |
118 if( word >= size ) // Beyond the last? |
118 if( word >= size ) // Beyond the last? |
119 return *this; // Then it's clear & return clear |
119 return *this; // Then it's clear & return clear |
120 register uint32_t mask = 1L << (elem & 31); // Get bit mask |
120 uint32_t mask = 1L << (elem & 31); // Get bit mask |
121 data[word] &= ~mask; // Clear bit |
121 data[word] &= ~mask; // Clear bit |
122 return *this; |
122 return *this; |
123 } |
123 } |
124 |
124 |
125 //------------------------------operator&=------------------------------------- |
125 //------------------------------operator&=------------------------------------- |
126 // Intersect one set into another. |
126 // Intersect one set into another. |
127 VectorSet &VectorSet::operator &= (const VectorSet &s) |
127 VectorSet &VectorSet::operator &= (const VectorSet &s) |
128 { |
128 { |
129 // NOTE: The intersection is never any larger than the smallest set. |
129 // NOTE: The intersection is never any larger than the smallest set. |
130 if( s.size < size ) size = s.size; // Get smaller size |
130 if( s.size < size ) size = s.size; // Get smaller size |
131 register uint32_t *u1 = data; // Pointer to the destination data |
131 uint32_t *u1 = data; // Pointer to the destination data |
132 register uint32_t *u2 = s.data; // Pointer to the source data |
132 uint32_t *u2 = s.data; // Pointer to the source data |
133 for( uint i=0; i<size; i++) // For data in set |
133 for( uint i=0; i<size; i++) // For data in set |
134 *u1++ &= *u2++; // Copy and AND longwords |
134 *u1++ &= *u2++; // Copy and AND longwords |
135 return *this; // Return set |
135 return *this; // Return set |
136 } |
136 } |
137 |
137 |
145 //------------------------------operator|=------------------------------------- |
145 //------------------------------operator|=------------------------------------- |
146 // Union one set into another. |
146 // Union one set into another. |
147 VectorSet &VectorSet::operator |= (const VectorSet &s) |
147 VectorSet &VectorSet::operator |= (const VectorSet &s) |
148 { |
148 { |
149 // This many words must be unioned |
149 // This many words must be unioned |
150 register uint cnt = ((size<s.size)?size:s.size); |
150 uint cnt = ((size<s.size)?size:s.size); |
151 register uint32_t *u1 = data; // Pointer to the destination data |
151 uint32_t *u1 = data; // Pointer to the destination data |
152 register uint32_t *u2 = s.data; // Pointer to the source data |
152 uint32_t *u2 = s.data; // Pointer to the source data |
153 for( uint i=0; i<cnt; i++) // Copy and OR the two sets |
153 for( uint i=0; i<cnt; i++) // Copy and OR the two sets |
154 *u1++ |= *u2++; |
154 *u1++ |= *u2++; |
155 if( size < s.size ) { // Is set 2 larger than set 1? |
155 if( size < s.size ) { // Is set 2 larger than set 1? |
156 // Extend result by larger set |
156 // Extend result by larger set |
157 grow(s.size*sizeof(uint32_t)*8); |
157 grow(s.size*sizeof(uint32_t)*8); |
170 //------------------------------operator-=------------------------------------- |
170 //------------------------------operator-=------------------------------------- |
171 // Difference one set from another. |
171 // Difference one set from another. |
172 VectorSet &VectorSet::operator -= (const VectorSet &s) |
172 VectorSet &VectorSet::operator -= (const VectorSet &s) |
173 { |
173 { |
174 // This many words must be unioned |
174 // This many words must be unioned |
175 register uint cnt = ((size<s.size)?size:s.size); |
175 uint cnt = ((size<s.size)?size:s.size); |
176 register uint32_t *u1 = data; // Pointer to the destination data |
176 uint32_t *u1 = data; // Pointer to the destination data |
177 register uint32_t *u2 = s.data; // Pointer to the source data |
177 uint32_t *u2 = s.data; // Pointer to the source data |
178 for( uint i=0; i<cnt; i++ ) // For data in set |
178 for( uint i=0; i<cnt; i++ ) // For data in set |
179 *u1++ &= ~(*u2++); // A <-- A & ~B with longwords |
179 *u1++ &= ~(*u2++); // A <-- A & ~B with longwords |
180 return *this; // Return new set |
180 return *this; // Return new set |
181 } |
181 } |
182 |
182 |
193 // X1 -- A is a subset of B |
193 // X1 -- A is a subset of B |
194 // 0X -- B is not a subset of A |
194 // 0X -- B is not a subset of A |
195 // 1X -- B is a subset of A |
195 // 1X -- B is a subset of A |
196 int VectorSet::compare (const VectorSet &s) const |
196 int VectorSet::compare (const VectorSet &s) const |
197 { |
197 { |
198 register uint32_t *u1 = data; // Pointer to the destination data |
198 uint32_t *u1 = data; // Pointer to the destination data |
199 register uint32_t *u2 = s.data; // Pointer to the source data |
199 uint32_t *u2 = s.data; // Pointer to the source data |
200 register uint32_t AnotB = 0, BnotA = 0; |
200 uint32_t AnotB = 0, BnotA = 0; |
201 // This many words must be unioned |
201 // This many words must be unioned |
202 register uint cnt = ((size<s.size)?size:s.size); |
202 uint cnt = ((size<s.size)?size:s.size); |
203 |
203 |
204 // Get bits for both sets |
204 // Get bits for both sets |
205 uint i; // Exit value of loop |
205 uint i; // Exit value of loop |
206 for( i=0; i<cnt; i++ ) { // For data in BOTH sets |
206 for( i=0; i<cnt; i++ ) { // For data in BOTH sets |
207 register uint32_t A = *u1++; // Data from one guy |
207 uint32_t A = *u1++; // Data from one guy |
208 register uint32_t B = *u2++; // Data from other guy |
208 uint32_t B = *u2++; // Data from other guy |
209 AnotB |= (A & ~B); // Compute bits in A not B |
209 AnotB |= (A & ~B); // Compute bits in A not B |
210 BnotA |= (B & ~A); // Compute bits in B not A |
210 BnotA |= (B & ~A); // Compute bits in B not A |
211 } |
211 } |
212 |
212 |
213 // Get bits from bigger set |
213 // Get bits from bigger set |
243 { |
243 { |
244 // The cast is a virtual function that checks that "set" is a VectorSet. |
244 // The cast is a virtual function that checks that "set" is a VectorSet. |
245 const VectorSet &s = *(set.asVectorSet()); |
245 const VectorSet &s = *(set.asVectorSet()); |
246 |
246 |
247 // NOTE: The intersection is never any larger than the smallest set. |
247 // NOTE: The intersection is never any larger than the smallest set. |
248 register uint small_size = ((size<s.size)?size:s.size); |
248 uint small_size = ((size<s.size)?size:s.size); |
249 register uint32_t *u1 = data; // Pointer to the destination data |
249 uint32_t *u1 = data; // Pointer to the destination data |
250 register uint32_t *u2 = s.data; // Pointer to the source data |
250 uint32_t *u2 = s.data; // Pointer to the source data |
251 for( uint i=0; i<small_size; i++) // For data in set |
251 for( uint i=0; i<small_size; i++) // For data in set |
252 if( *u1++ & *u2++ ) // If any elements in common |
252 if( *u1++ & *u2++ ) // If any elements in common |
253 return 0; // Then not disjoint |
253 return 0; // Then not disjoint |
254 return 1; // Else disjoint |
254 return 1; // Else disjoint |
255 } |
255 } |
284 |
284 |
285 //------------------------------operator[]------------------------------------- |
285 //------------------------------operator[]------------------------------------- |
286 // Test for membership. A Zero/Non-Zero value is returned! |
286 // Test for membership. A Zero/Non-Zero value is returned! |
287 int VectorSet::operator[](uint elem) const |
287 int VectorSet::operator[](uint elem) const |
288 { |
288 { |
289 register uint word = elem >> 5; // Get the longword offset |
289 uint word = elem >> 5; // Get the longword offset |
290 if( word >= size ) // Beyond the last? |
290 if( word >= size ) // Beyond the last? |
291 return 0; // Then it's clear |
291 return 0; // Then it's clear |
292 register uint32_t mask = 1L << (elem & 31); // Get bit mask |
292 uint32_t mask = 1L << (elem & 31); // Get bit mask |
293 return ((data[word] & mask))!=0; // Return the sense of the bit |
293 return ((data[word] & mask))!=0; // Return the sense of the bit |
294 } |
294 } |
295 |
295 |
296 //------------------------------getelem---------------------------------------- |
296 //------------------------------getelem---------------------------------------- |
297 // Get any element from the set. |
297 // Get any element from the set. |
298 uint VectorSet::getelem(void) const |
298 uint VectorSet::getelem(void) const |