IntSet.ccGo to the documentation of this file.00001
00002
00003
00004
00005 #include "ClassNames.h"
00006 #include "define.h"
00007
00008 #ifdef POLARIS_GNU_PRAGMAS
00009 #pragma implementation
00010 #endif
00011
00012 #include "IntSet.h"
00013
00014 #include "macros.h"
00015 #include "p-assert.h"
00016
00017
00018
00019 IntSet::IntSet(unsigned int max_int GIV(31))
00020 {
00021 #ifdef CLASS_INSTANCE_REGISTRY
00022 register_instance(INT_SET, sizeof(IntSet), this);
00023 #endif
00024
00025 _max_size = _INTSET_WORD(max_int) + 1;
00026 _data = new unsigned int[_max_size];
00027
00028 for (unsigned i = 0; i<_max_size; i++)
00029 _data[i] = 0;
00030 }
00031
00032
00033
00034 IntSet::IntSet(const IntSet & other)
00035 {
00036 #ifdef CLASS_INSTANCE_REGISTRY
00037 register_instance(INT_SET, sizeof(IntSet), this);
00038 #endif
00039
00040 _max_size = other._max_size;
00041 _data = new unsigned int[_max_size];
00042
00043 for (unsigned i = 0; i<_max_size; i++)
00044 _data[i] = other._data[i];
00045 }
00046
00047
00048
00049 void
00050 IntSet::clear()
00051 {
00052 for (unsigned i = 0; i<_max_size; i++)
00053 _data[i] = 0;
00054 }
00055
00056
00057
00058 IntSet &
00059 IntSet::operator = (const IntSet & other)
00060 {
00061 if (this != &other) {
00062 if (_max_size != other._max_size) {
00063 _max_size = other._max_size;
00064 delete[] _data;
00065 _data = new unsigned int[_max_size];
00066 }
00067
00068 for (unsigned i = 0; i<_max_size; i++)
00069 _data[i] = other._data[i];
00070 }
00071
00072 return *this;
00073 }
00074
00075
00076
00077 int
00078 IntSet::operator == (const IntSet & other) const
00079 {
00080 unsigned i;
00081 if (_max_size <= other._max_size) {
00082 for (i = 0; i<_max_size; ++i) {
00083 if (_data[i] != other._data[i])
00084 return 0;
00085 }
00086 for (i = _max_size; i < other._max_size; ++i) {
00087 if (!other._data[i])
00088 return 0;
00089 }
00090 }
00091 else {
00092 for (i = 0; i<other._max_size; ++i)
00093 if (_data[i] != other._data[i])
00094 return 0;
00095
00096 for (i = other._max_size; i<_max_size; ++i)
00097 if (_data[i])
00098 return 0;
00099 }
00100
00101 return 1;
00102 }
00103
00104
00105
00106 int
00107 IntSet::operator <= (const IntSet & other) const
00108 {
00109 unsigned i;
00110 if (_max_size <= other._max_size) {
00111 for (i = 0; i<_max_size; i++) {
00112 if (_data[i] & ~other._data[i])
00113 return 0;
00114 }
00115 }
00116 else {
00117 for (i = 0; i<other._max_size; i++)
00118 if (_data[i] & ~other._data[i])
00119 return 0;
00120
00121 for (i = other._max_size; i<_max_size; i++)
00122 if (_data[i])
00123 return 0;
00124 }
00125 return 1;
00126 }
00127
00128
00129
00130 int
00131 IntSet::intersects_with(const IntSet & other) const
00132 {
00133 int min_size = (_max_size <= other._max_size) ? _max_size
00134 : other._max_size;
00135 for (unsigned i = 0; i<min_size; i++)
00136 if (_data[i] & other._data[i])
00137 return 1;
00138
00139 return 0;
00140 }
00141
00142
00143
00144 IntSet &
00145 IntSet::operator += (const IntSet & other)
00146 {
00147 if (_max_size<other._max_size)
00148 _resize(other._max_size);
00149
00150 for (unsigned i = 0; i<other._max_size; i++)
00151 _data[i] |= other._data[i];
00152
00153 return *this;
00154 }
00155
00156
00157
00158 IntSet &
00159 IntSet::operator &= (const IntSet & other)
00160 {
00161 unsigned i;
00162 if (_max_size <= other._max_size) {
00163 for (i = 0; i<_max_size; i++)
00164 _data[i] &= other._data[i];
00165 }
00166 else {
00167 for (i = 0; i<other._max_size; i++)
00168 _data[i] &= other._data[i];
00169
00170 for (i = other._max_size; i<_max_size; i++)
00171 _data[i] = 0;
00172 }
00173
00174 return *this;
00175 }
00176
00177
00178
00179 IntSet &
00180 IntSet::operator -= (const IntSet & other)
00181 {
00182 int min_size = (_max_size <= other._max_size) ? _max_size
00183 : other._max_size;
00184
00185 for (unsigned i = 0; i<min_size; i++)
00186 _data[i] &= ~other._data[i];
00187
00188 return *this;
00189 }
00190
00191
00192
00193 IntSet &
00194 IntSet::negate_in_place()
00195 {
00196 for (unsigned i = 0; i<_max_size; i++)
00197 _data[i] = ~_data[i];
00198
00199 return *this;
00200 }
00201
00202
00203
00204 void
00205 IntSet::_resize(unsigned new_size)
00206 {
00207 unsigned int old_max_size = _max_size;
00208 unsigned int *old_data = _data;
00209 unsigned i;
00210
00211 _max_size = new_size;
00212
00213 if (old_max_size == _max_size)
00214 return;
00215
00216 _data = new unsigned int[_max_size];
00217
00218 if (_max_size>old_max_size) {
00219 for (i = 0; i<old_max_size; i++)
00220 _data[i] = old_data[i];
00221
00222 for (i = old_max_size; i<_max_size; i++)
00223 _data[i] = 0;
00224 }
00225 else {
00226 for (i = 0; i<_max_size; i++)
00227 _data[i] = old_data[i];
00228 }
00229
00230 delete[] old_data;
00231 }
00232
00233
00234
00235 int
00236 IntSet::first() const
00237 {
00238 unsigned word = 0;
00239
00240 while (word<_max_size && !_data[word])
00241 ++word;
00242
00243 if (word >= _max_size)
00244 return -1;
00245
00246 unsigned mask = 0;
00247
00248 while (mask<_INTSET_WORD_BITS && !(_data[word] & (1 << mask)))
00249 ++mask;
00250
00251 p_assert(mask < _INTSET_WORD_BITS, "Internal error.");
00252
00253 return word * _INTSET_WORD_BITS + mask;
00254 }
00255
00256
00257
00258 int
00259 IntSet::last() const
00260 {
00261 unsigned word = _max_size - 1;
00262
00263 while (word >= 0 && !_data[word])
00264 --word;
00265
00266 if (word < 0)
00267 return -1;
00268
00269 int mask = _INTSET_WORD_BITS - 1;
00270
00271 while (mask >= 0 && !(_data[word] & (1 << mask)))
00272 --mask;
00273
00274 p_assert(mask >= 0, "Internal error.");
00275
00276 return word * _INTSET_WORD_BITS + mask;
00277 }
00278
00279
00280
00281 int
00282 IntSet::next(unsigned int elem) const
00283 {
00284 unsigned word = _INTSET_WORD(elem);
00285 unsigned mask = elem % _INTSET_WORD_BITS;
00286
00287 ++mask;
00288
00289 while (mask<_INTSET_WORD_BITS && !(_data[word] & (1 << mask)))
00290 ++mask;
00291
00292 if (mask >= _INTSET_WORD_BITS) {
00293 ++word;
00294
00295 while (word<_max_size && !_data[word])
00296 ++word;
00297
00298 if (word >= _max_size)
00299 return -1;
00300
00301 mask = 0;
00302
00303 while (mask<_INTSET_WORD_BITS && !(_data[word] & (1 << mask)))
00304 ++mask;
00305
00306 p_assert(mask<_INTSET_WORD_BITS, "Internal error.");
00307 }
00308
00309 return word * _INTSET_WORD_BITS + mask;
00310 }
00311
00312
00313
00314 int
00315 IntSet::prev(unsigned int elem) const
00316 {
00317 unsigned word = _INTSET_WORD(elem);
00318 unsigned mask = elem % _INTSET_WORD_BITS;
00319
00320 --mask;
00321
00322 while (mask >= 0 && !(_data[word] & (1 << mask)))
00323 --mask;
00324
00325 if (mask < 0) {
00326 --word;
00327
00328 while (word >= 0 && !_data[word])
00329 --word;
00330
00331 if (word < 0)
00332 return -1;
00333
00334 mask = _INTSET_WORD_BITS - 1;
00335
00336 while (mask >= 0 && !(_data[word] & (1 << mask)))
00337 --mask;
00338
00339 p_assert(mask >= 0, "Internal error.");
00340 }
00341
00342 return word * _INTSET_WORD_BITS + mask;
00343 }
00344
00345 int
00346 IntSet::entries() const
00347 {
00348 int count = 0;
00349
00350 for (unsigned word = 0; word<_max_size; word++)
00351 if (_data[word])
00352 for (unsigned mask = 0; mask<_INTSET_WORD_BITS; mask++)
00353 if (_data[word] & (1 << mask))
00354 ++count;
00355
00356 return count;
00357 }
00358
00359
00360
00361 void
00362 IntSet::print(ostream & o) const
00363 {
00364 o << "{";
00365
00366 int elem = first();
00367
00368 if (elem != -1)
00369 o << elem;
00370
00371 while ((elem = next(elem)) != -1)
00372 o << ", " << elem;
00373
00374 o << "}";
00375 }
00376
00377
00378
00379 ostream &
00380 operator << (ostream & o, const IntSet & set)
00381 {
00382 set.print(o);
00383 return o;
00384 }
00385
00386
00387
00388 int
00389 IntSet::structures_OK() const
00390 {
00391 if (_data == 0) {
00392 cerr << "\n\nError: IntSet: "
00393 << "structures_OK() found a NULL _data field.\n";
00394 return 0;
00395 }
00396
00397 return 1;
00398 }
00399
00400
00401
00402 #ifdef INTSETTEST
00403
00404 #include "p-setjmp.h"
00405 #include "HeapStats.h"
00406
00407 main()
00408 {
00409 HeapStats::reset();
00410
00411 SETJUMP() {
00412 IntSet s1;
00413
00414 cout << "s1 should be {}\n";
00415 cout << "s1 is " << s1 << endl;
00416 cout << "s1 has " << s1.entries() << " entries\n\n";
00417
00418 s1.ins(1);
00419 s1.ins(3);
00420 s1.ins(7);
00421 s1.ins(35);
00422 s1.ins(151);
00423 cout << "s1 should be {1, 3, 7, 35, 151}\n";
00424 cout << "s1 is " << s1 << endl;
00425 cout << "s1 has " << s1.entries() << " entries\n\n";
00426
00427 s1.del(6);
00428 s1.del(7);
00429 s1.del(200);
00430 cout << "s1 should be {1, 3, 35, 151}\n";
00431 cout << "s1 is " << s1 << endl;
00432 cout << "s1 has " << s1.entries() << " entries\n\n";
00433
00434 cout << "s1[3] = " << s1[3] << endl;
00435 cout << "s1[7] = " << s1[7] << endl;
00436 cout << "s1[200] = " << s1[200] << endl << endl;
00437
00438 IntSet s2 = s1;
00439
00440 cout << s1 << " == " << s2 << " = " << (s1 == s2) << endl;
00441 cout << s1 << " != " << s2 << " = " << (s1 != s2) << endl;
00442 cout << s1 << " < " << s2 << " = " << (s1<s2) << endl;
00443 cout << s1 << " <= " << s2 << " = " << (s1 <= s2) << endl;
00444 cout << s1 << " > " << s2 << " = " << (s1>s2) << endl;
00445 cout << s1 << " >= " << s2 << " = " << (s1 >= s2) << endl << endl;
00446
00447 s2.del(3);
00448 cout << s1 << " == " << s2 << " = " << (s1 == s2) << endl;
00449 cout << s1 << " != " << s2 << " = " << (s1 != s2) << endl;
00450 cout << s1 << " < " << s2 << " = " << (s1<s2) << endl;
00451 cout << s1 << " <= " << s2 << " = " << (s1 <= s2) << endl;
00452 cout << s1 << " > " << s2 << " = " << (s1>s2) << endl;
00453 cout << s1 << " >= " << s2 << " = " << (s1 >= s2) << endl << endl;
00454
00455 IntSet s3;
00456
00457 s3.ins(1);
00458 s3.ins(10);
00459 s3.ins(35);
00460 cout << s1 << " == " << s3 << " = " << (s1 == s3) << endl;
00461 cout << s1 << " != " << s3 << " = " << (s1 != s3) << endl;
00462 cout << s1 << " < " << s3 << " = " << (s1<s3) << endl;
00463 cout << s1 << " <= " << s3 << " = " << (s1 <= s3) << endl;
00464 cout << s1 << " > " << s3 << " = " << (s1>s3) << endl;
00465 cout << s1 << " >= " << s3 << " = " << (s1 >= s3) << endl << endl;
00466
00467 cout << s1 << ".intersects_with(" << s3 << ") = "
00468 << s1.intersects_with(s3) << endl;
00469 IntSet s4;
00470
00471 s4.ins(10);
00472 s4.ins(34);
00473 s4.ins(36);
00474 cout << s1 << ".intersects_with(" << s4 << ") = "
00475 << s1.intersects_with(s4) << endl << endl;
00476
00477 cout << s1 << " + " << s3 << " = " << (s1 + s3) << endl;
00478 cout << s3 << " + " << s1 << " = " << (s3 + s1) << endl;
00479 cout << s1 << " & " << s3 << " = " << (s1 & s3) << endl;
00480 cout << s3 << " & " << s1 << " = " << (s3 & s1) << endl;
00481 cout << s1 << " - " << s3 << " = " << (s1 - s3) << endl;
00482 cout << s3 << " - " << s1 << " = " << (s3 - s1) << endl;
00483 cout << "~ " << s3 << " = " << ~s3 << endl << endl;
00484
00485 cout << s1 << ".clear() = ";
00486 s1.clear();
00487 cout << s1 << endl << endl;
00488 }
00489
00490 HeapStats::report();
00491 }
00492
00493 #endif
|