63 //------------------------------operator=--------------------------------------

    64 Set &VectorSet::operator = (const Set &set)

    65 {

    66   if( &set == this ) return *this;

    67   FREE_FAST(data);

    68   // The cast is a virtual function that checks that "set" is a VectorSet.

    69   slamin(*(set.asVectorSet()));

    70   return *this;

    71 }

    72 

    73 //------------------------------slamin-----------------------------------------

    74 // Initialize one set with another.  No regard is made to the existing Set.

    75 void VectorSet::slamin(const VectorSet& s)

    76 {

    77   size = s.size;                // Use new size

    78   data = (uint32_t*)s._set_arena->Amalloc(size*sizeof(uint32_t)); // Make array of required size

    79   memcpy( data, s.data, size*sizeof(uint32_t) ); // Fill the array

    80 }

    81 

    82 //------------------------------grow-------------------------------------------

    94 //------------------------------operator<<=------------------------------------

   107 //------------------------------operator>>=------------------------------------

   108 // Delete a member from an existing Set.

   109 Set &VectorSet::operator >>= (uint elem)

   110 {

   111   uint word = elem >> 5;          // Get the longword offset

   112   if( word >= size )              // Beyond the last?

   113     return *this;                 // Then it's clear & return clear

   114   uint32_t mask = 1L << (elem & 31);     // Get bit mask

   115   data[word] &= ~mask;            // Clear bit

   116   return *this;

   117 }

   118 

   119 //------------------------------operator&=-------------------------------------

   120 // Intersect one set into another.

   121 VectorSet &VectorSet::operator &= (const VectorSet &s)

   122 {

   123   // NOTE: The intersection is never any larger than the smallest set.

   124   if( s.size < size ) size = s.size; // Get smaller size

   125   uint32_t *u1 = data;          // Pointer to the destination data

   126   uint32_t *u2 = s.data;        // Pointer to the source data

   127   for( uint i=0; i<size; i++)   // For data in set

   128     *u1++ &= *u2++;             // Copy and AND longwords

   129   return *this;                 // Return set

   130 }

   131 

   132 //------------------------------operator&=-------------------------------------

   133 Set &VectorSet::operator &= (const Set &set)

   134 {

   135   // The cast is a virtual function that checks that "set" is a VectorSet.

   136   return (*this) &= *(set.asVectorSet());

   137 }

   138 

   139 //------------------------------operator|=-------------------------------------

   140 // Union one set into another.

   141 VectorSet &VectorSet::operator |= (const VectorSet &s)

   142 {

   143   // This many words must be unioned

   144   uint cnt = ((size<s.size)?size:s.size);

   145   uint32_t *u1 = data;          // Pointer to the destination data

   146   uint32_t *u2 = s.data;        // Pointer to the source data

   147   for( uint i=0; i<cnt; i++)    // Copy and OR the two sets

   148     *u1++ |= *u2++;

   149   if( size < s.size ) {         // Is set 2 larger than set 1?

   150     // Extend result by larger set

   151     grow(s.size*sizeof(uint32_t)*8);

   152     memcpy(&data[cnt], u2, (s.size - cnt)*sizeof(uint32_t));

   153   }

   154   return *this;                 // Return result set

   155 }

   156 

   157 //------------------------------operator|=-------------------------------------

   158 Set &VectorSet::operator |= (const Set &set)

   159 {

   160   // The cast is a virtual function that checks that "set" is a VectorSet.

   161   return (*this) |= *(set.asVectorSet());

   162 }

   163 

   164 //------------------------------operator-=-------------------------------------

   165 // Difference one set from another.

   166 VectorSet &VectorSet::operator -= (const VectorSet &s)

   167 {

   168   // This many words must be unioned

   169   uint cnt = ((size<s.size)?size:s.size);

   170   uint32_t *u1 = data;          // Pointer to the destination data

   171   uint32_t *u2 = s.data;        // Pointer to the source data

   172   for( uint i=0; i<cnt; i++ )   // For data in set

   173     *u1++ &= ~(*u2++);          // A <-- A & ~B  with longwords

   174   return *this;                 // Return new set

   175 }

   176 

   177 //------------------------------operator-=-------------------------------------

   178 Set &VectorSet::operator -= (const Set &set)

   179 {

   180   // The cast is a virtual function that checks that "set" is a VectorSet.

   181   return (*this) -= *(set.asVectorSet());

   182 }

   183 

   184 //------------------------------compare----------------------------------------

   185 // Compute 2 booleans: bits in A not B, bits in B not A.

   186 // Return X0 --  A is not a subset of B

   187 //        X1 --  A is a subset of B

   188 //        0X --  B is not a subset of A

   189 //        1X --  B is a subset of A

   190 int VectorSet::compare (const VectorSet &s) const

   191 {

   192   uint32_t *u1 = data;          // Pointer to the destination data

   193   uint32_t *u2 = s.data;        // Pointer to the source data

   194   uint32_t AnotB = 0, BnotA = 0;

   195   // This many words must be unioned

   196   uint cnt = ((size<s.size)?size:s.size);

   197 

   198   // Get bits for both sets

   199   uint i;                       // Exit value of loop

   200   for( i=0; i<cnt; i++ ) {      // For data in BOTH sets

   201     uint32_t A = *u1++;         // Data from one guy

   202     uint32_t B = *u2++;         // Data from other guy

   203     AnotB |= (A & ~B);          // Compute bits in A not B

   204     BnotA |= (B & ~A);          // Compute bits in B not A

   205   }

   206 

   207   // Get bits from bigger set

   208   if( size < s.size ) {

   209     for( ; i<s.size; i++ )      // For data in larger set

   210       BnotA |= *u2++;           // These bits are in B not A

   211   } else {

   212     for( ; i<size; i++ )        // For data in larger set

   213       AnotB |= *u1++;           // These bits are in A not B

   214   }

   215 

   216   // Set & return boolean flags

   217   return ((!BnotA)<<1) + (!AnotB);

   218 }

   219 

   220 //------------------------------operator==-------------------------------------

   221 // Test for set equality

   222 int VectorSet::operator == (const VectorSet &s) const

   223 {

   224   return compare(s) == 3;       // TRUE if A and B are mutual subsets

   225 }

   226 

   227 //------------------------------operator==-------------------------------------

   228 int VectorSet::operator == (const Set &set) const

   229 {

   230   // The cast is a virtual function that checks that "set" is a VectorSet.

   231   return (*this) == *(set.asVectorSet());

   232 }

   233 

   234 //------------------------------disjoint---------------------------------------

   235 // Check for sets being disjoint.

   236 int VectorSet::disjoint(const Set &set) const

   237 {

   238   // The cast is a virtual function that checks that "set" is a VectorSet.

   239   const VectorSet &s = *(set.asVectorSet());

   240 

   241   // NOTE: The intersection is never any larger than the smallest set.

   242   uint small_size = ((size<s.size)?size:s.size);

   243   uint32_t *u1 = data;               // Pointer to the destination data

   244   uint32_t *u2 = s.data;             // Pointer to the source data

   245   for( uint i=0; i<small_size; i++)  // For data in set

   246     if( *u1++ & *u2++ )              // If any elements in common

   247       return 0;                      // Then not disjoint

   248   return 1;                          // Else disjoint

   249 }

   250 

   251 //------------------------------operator<--------------------------------------

   252 // Test for strict subset

   253 int VectorSet::operator < (const VectorSet &s) const

   254 {

   255   return compare(s) == 1;       // A subset B, B not subset A

   256 }

   257 

   258 //------------------------------operator<--------------------------------------

   259 int VectorSet::operator < (const Set &set) const

   260 {

   261   // The cast is a virtual function that checks that "set" is a VectorSet.

   262   return (*this) < *(set.asVectorSet());

   263 }

   264 

   265 //------------------------------operator<=-------------------------------------

   266 // Test for subset

   267 int VectorSet::operator <= (const VectorSet &s) const

   268 {

   269   return compare(s) & 1;        // A subset B

   270 }

   271 

   272 //------------------------------operator<=-------------------------------------

   273 int VectorSet::operator <= (const Set &set) const

   274 {

   275   // The cast is a virtual function that checks that "set" is a VectorSet.

   276   return (*this) <= *(set.asVectorSet());

   277 }

   278 

   279 //------------------------------operator[]-------------------------------------

   280 // Test for membership.  A Zero/Non-Zero value is returned!

   281 int VectorSet::operator[](uint elem) const

   282 {

   283   uint word = elem >> 5;              // Get the longword offset

   284   if( word >= size )                  // Beyond the last?

   285     return 0;                         // Then it's clear

   286   uint32_t mask = 1L << (elem & 31);  // Get bit mask

   287   return ((data[word] & mask))!=0;    // Return the sense of the bit

   288 }

   289 

   290 //------------------------------Clear------------------------------------------

   328 

   329 //------------------------------iterate----------------------------------------

   330 // Used by Set::print().

   331 class VSetI_ : public SetI_ {

   332   VectorSetI vsi;

   333 public:

   334   VSetI_( const VectorSet *vset, uint &elem ) : vsi(vset) { elem = vsi.elem; }

   335 

   336   uint next(void) { ++vsi; return vsi.elem; }

   337   int  test(void) { return vsi.test(); }

   338 };

   339 

   340 SetI_ *VectorSet::iterate(uint &elem) const {

   341   return new(ResourceObj::C_HEAP, mtInternal) VSetI_(this, elem);

   342 }

   343 

   344 //=============================================================================

   345 //------------------------------next-------------------------------------------

   346 // Find and return the next element of a vector set, or return garbage and

   347 // make "VectorSetI::test()" fail.

   348 uint VectorSetI::next(void)

   349 {

   350   j++;                          // Next element in word

   351   mask = (mask & max_jint) << 1;// Next bit in word

   352   do {                          // Do While still have words

   353     while( mask ) {             // While have bits in word

   354       if( s->data[i] & mask ) { // If found a bit

   355         return (i<<5)+j;        // Return the bit address

   356       }

   357       j++;                      // Skip to next bit

   358       mask = (mask & max_jint) << 1;

   359     }

   360     j = 0;                      // No more bits in word; setup for next word

   361     mask = 1;

   362     for( i++; (i<s->size) && (!s->data[i]); i++ ); // Skip to non-zero word

   363   } while( i<s->size );

   364   return max_juint;             // No element, iterated them all

   365 }