00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051 #ifdef _KEEP_RCS_ID
00052 static const char source_file[] = __FILE__;
00053 #endif
00054
00055 #include "defs.h"
00056 #include "mempool.h"
00057 #include "errors.h"
00058 #include "bitset.h"
00059
00060
00061
00062
00063 static MEM_POOL bad_pool_struct;
00064 static MEM_POOL *bad_pool = &bad_pool_struct;
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079 static BS*
00080 bs_Malloc(
00081 size_t length,
00082 MEM_POOL *pool
00083 )
00084 {
00085 BS *new_set;
00086
00087 Is_True(pool != bad_pool,("Shouldn't be allocating."));
00088
00089 new_set = (BS *) TYPE_MEM_POOL_ALLOC_N(BS_WORD,pool,length + 1);
00090
00091 BS_word_count(new_set) = length;
00092 return new_set;
00093 }
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109 static BS*
00110 bs_Realloc(
00111 BS *set,
00112 size_t length,
00113 MEM_POOL *pool
00114 )
00115 {
00116 BS *new_set;
00117 BS_ELT i;
00118 BS_ELT old_length = BS_word_count(set);
00119 size_t new_length;
00120
00121 Is_True(pool != bad_pool,("Shouldn't be allocating."));
00122
00123 if (length <= old_length) return set;
00124
00125
00126 for (new_length = 2; new_length < length; new_length <<= 1);
00127 length = new_length;
00128
00129 new_set = (BS *)TYPE_MEM_POOL_REALLOC_N(BS_WORD, pool, set, old_length+1,
00130 length+1);
00131
00132 if (!MEM_POOL_Zeroed(pool))
00133 for ( i = old_length; i < length; ++i )
00134 BS_word(new_set,i) = bs_ZEROS;
00135
00136 BS_word_count(new_set) = length;
00137
00138 return new_set;
00139 }
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150 extern BS*
00151 BS_Create(
00152 BS_ELT size,
00153 MEM_POOL *pool
00154 )
00155 {
00156 Is_True(size >= 0,("BS_Create called with negative size."));
00157
00158 return bs_Malloc(bs_QBPW(size + (BITS_PER_BS_WORD - 1)),pool);
00159 }
00160
00161
00162
00163
00164
00165
00166
00167
00168
00169
00170 extern size_t
00171 BS_Size_Alloc_Size(
00172 BS_ELT size
00173 )
00174 {
00175 return (1 + bs_QBPW(size + (BITS_PER_BS_WORD - 1) )) * sizeof(BS_WORD);
00176 }
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187 extern size_t
00188 BS_Alloc_Size(
00189 BS *set
00190 )
00191 {
00192 return (BS_word_count(set) + 1) * sizeof(BS_WORD);
00193 }
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204 extern BS*
00205 BS_ClearD(
00206 BS *set
00207 )
00208 {
00209 BS_ELT i;
00210
00211 for ( i = 0; i < BS_word_count(set); ++i )
00212 BS_word(set,i) = bs_ZEROS;
00213
00214 return set;
00215 }
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226 extern BS*
00227 BS_Create_Empty(
00228 BS_ELT size,
00229 MEM_POOL *pool
00230 )
00231 {
00232 BS *set = BS_Create(size, pool);
00233 if (!MEM_POOL_Zeroed(pool))
00234 BS_ClearD(set);
00235 return set;
00236 }
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247 extern BS*
00248 BS_ResizeD(
00249 BS* set,
00250 BS_ELT new_size,
00251 MEM_POOL *pool
00252 )
00253 {
00254 BS_ELT new_words = bs_QBPW(new_size + (BITS_PER_BS_WORD - 1));
00255
00256 if ( new_words > BS_word_count(set) ) {
00257 set = bs_Realloc(set,new_words,pool);
00258 }
00259 return set;
00260 }
00261
00262 #ifndef MONGOOSE_BE
00263
00264
00265
00266
00267
00268
00269
00270
00271
00272 extern BS*
00273 BS_Range(
00274 BS_ELT low,
00275 BS_ELT high,
00276 MEM_POOL *pool
00277 )
00278 {
00279 return BS_RangeD(BS_Create(high + 1,pool),low,high,bad_pool);
00280 }
00281 #endif
00282
00283
00284
00285
00286
00287
00288
00289
00290
00291
00292 extern BS*
00293 BS_RangeD(
00294 BS* set,
00295 BS_ELT low,
00296 BS_ELT high,
00297 MEM_POOL *pool
00298 )
00299 {
00300 BS_ELT first_w, last_w, first_b, last_b;
00301 BS_ELT i;
00302
00303 Is_True(low >= 0,
00304 ("BS_RangeD called with negative low element."));
00305
00306 Is_True(high - low + 1 >= 0,
00307 ("BS_RangeD called with negative range size."));
00308
00309 if ( low > high )
00310 return BS_ClearD(set);
00311
00312 first_w = bs_QBPW(low);
00313 last_w = bs_QBPW(high);
00314 first_b = bs_QBPB(low);
00315 last_b = bs_QBPB(high);
00316
00317
00318
00319 if ( last_w >= BS_word_count(set) )
00320 set = bs_Realloc(set,last_w + 1,pool);
00321
00322 set = BS_ClearD(set);
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332 for ( i = first_w + 1; i < last_w; ++i )
00333 BS_word(set,i) = bs_ONES;
00334
00335
00336
00337
00338
00339 for ( i = first_b; i < bs_PBytesPW(first_w + 1) && i <= last_b; ++i )
00340 BS_byte(set,i) = (BS_BYTE)bs_ONES;
00341
00342
00343
00344
00345
00346 if (first_w != last_w)
00347 for ( i = bs_PBytesPW(last_w); i <= last_b; ++i )
00348 BS_byte(set,i) = (BS_BYTE)bs_ONES;
00349
00350
00351
00352
00353
00354 BS_byte(set,first_b) = bs_ONES << bs_RBPB(low);
00355 BS_byte(set,last_b) &=
00356 bs_ONES >> ((BITS_PER_BS_WORD - 1) - bs_RBPB(high));
00357
00358 return set;
00359 }
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370 extern BS*
00371 BS_Singleton(
00372 BS_ELT element,
00373 MEM_POOL *pool
00374 )
00375 {
00376 return BS_SingletonD(BS_Create(element + 1,pool),
00377 element,
00378 bad_pool);
00379 }
00380
00381
00382
00383
00384
00385
00386
00387
00388
00389
00390 extern BS*
00391 BS_SingletonD(
00392 BS *set,
00393 BS_ELT element,
00394 MEM_POOL *pool
00395 )
00396 {
00397 BS_ELT word;
00398
00399 Is_True(element >= 0,
00400 ("BS_SingletonD called with negative element."));
00401
00402 word = bs_QBPW(element);
00403
00404
00405
00406 if ( word >= BS_word_count(set) )
00407 set = bs_Realloc(set,word + 1,pool);
00408
00409 set = BS_ClearD(set);
00410 BS_byte(set,bs_QBPB(element)) = bs_ONE << bs_RBPB(element);
00411
00412 return set;
00413 }
00414
00415
00416
00417
00418
00419
00420
00421
00422
00423
00424 extern BS*
00425 BS_Universe(
00426 BS_ELT size,
00427 MEM_POOL *pool
00428 )
00429 {
00430 return BS_UniverseD(BS_Create(size,pool),size,bad_pool);
00431 }
00432
00433
00434
00435
00436
00437
00438
00439
00440
00441
00442 extern BS*
00443 BS_UniverseD(
00444 BS *set,
00445 BS_ELT size,
00446 MEM_POOL *pool
00447 )
00448 {
00449 return BS_RangeD(set,0,size - 1,bad_pool);
00450 }
00451
00452
00453
00454
00455
00456
00457
00458
00459
00460
00461 extern BS*
00462 BS_Copy(
00463 BS *set,
00464 MEM_POOL *pool
00465 )
00466 {
00467 size_t size;
00468 BS* newset;
00469 BS_ELT i;
00470
00471 size = BS_word_count(set);
00472 newset = bs_Malloc(size,pool);
00473
00474 for ( i = 0; i < size; ++i )
00475 BS_word(newset,i) = BS_word(set,i);
00476
00477 return newset;
00478 }
00479
00480
00481
00482
00483
00484
00485
00486
00487
00488
00489 extern BS*
00490 BS_CopyD(
00491 BS *set1,
00492 BS *set2,
00493 MEM_POOL *pool
00494 )
00495 {
00496 BS_ELT i;
00497 BS_ELT size1 = BS_word_count(set1);
00498 BS_ELT size2 = BS_word_count(set2);
00499
00500
00501
00502 if ( size1 < size2 )
00503 set1 = bs_Realloc(set1,size2,pool);
00504 else {
00505
00506
00507 for ( i = size2; i < size1; ++i )
00508 BS_word(set1,i) = bs_ZEROS;
00509 }
00510
00511
00512
00513 for ( i = 0; i < size2; ++i )
00514 BS_word(set1,i) = BS_word(set2,i);
00515
00516 return set1;
00517 }
00518
00519
00520
00521
00522 static const mUINT8 first_one [256] = {
00523 0,
00524 0,
00525 1,
00526 0,
00527 2,
00528 0,
00529 1,
00530 0,
00531 3,
00532 0,
00533 1,
00534 0,
00535 2,
00536 0,
00537 1,
00538 0,
00539 4,
00540 0,
00541 1,
00542 0,
00543 2,
00544 0,
00545 1,
00546 0,
00547 3,
00548 0,
00549 1,
00550 0,
00551 2,
00552 0,
00553 1,
00554 0,
00555 5,
00556 0,
00557 1,
00558 0,
00559 2,
00560 0,
00561 1,
00562 0,
00563 3,
00564 0,
00565 1,
00566 0,
00567 2,
00568 0,
00569 1,
00570 0,
00571 4,
00572 0,
00573 1,
00574 0,
00575 2,
00576 0,
00577 1,
00578 0,
00579 3,
00580 0,
00581 1,
00582 0,
00583 2,
00584 0,
00585 1,
00586 0,
00587 6,
00588 0,
00589 1,
00590 0,
00591 2,
00592 0,
00593 1,
00594 0,
00595 3,
00596 0,
00597 1,
00598 0,
00599 2,
00600 0,
00601 1,
00602 0,
00603 4,
00604 0,
00605 1,
00606 0,
00607 2,
00608 0,
00609 1,
00610 0,
00611 3,
00612 0,
00613 1,
00614 0,
00615 2,
00616 0,
00617 1,
00618 0,
00619 5,
00620 0,
00621 1,
00622 0,
00623 2,
00624 0,
00625 1,
00626 0,
00627 3,
00628 0,
00629 1,
00630 0,
00631 2,
00632 0,
00633 1,
00634 0,
00635 4,
00636 0,
00637 1,
00638 0,
00639 2,
00640 0,
00641 1,
00642 0,
00643 3,
00644 0,
00645 1,
00646 0,
00647 2,
00648 0,
00649 1,
00650 0,
00651 7,
00652 0,
00653 1,
00654 0,
00655 2,
00656 0,
00657 1,
00658 0,
00659 3,
00660 0,
00661 1,
00662 0,
00663 2,
00664 0,
00665 1,
00666 0,
00667 4,
00668 0,
00669 1,
00670 0,
00671 2,
00672 0,
00673 1,
00674 0,
00675 3,
00676 0,
00677 1,
00678 0,
00679 2,
00680 0,
00681 1,
00682 0,
00683 5,
00684 0,
00685 1,
00686 0,
00687 2,
00688 0,
00689 1,
00690 0,
00691 3,
00692 0,
00693 1,
00694 0,
00695 2,
00696 0,
00697 1,
00698 0,
00699 4,
00700 0,
00701 1,
00702 0,
00703 2,
00704 0,
00705 1,
00706 0,
00707 3,
00708 0,
00709 1,
00710 0,
00711 2,
00712 0,
00713 1,
00714 0,
00715 6,
00716 0,
00717 1,
00718 0,
00719 2,
00720 0,
00721 1,
00722 0,
00723 3,
00724 0,
00725 1,
00726 0,
00727 2,
00728 0,
00729 1,
00730 0,
00731 4,
00732 0,
00733 1,
00734 0,
00735 2,
00736 0,
00737 1,
00738 0,
00739 3,
00740 0,
00741 1,
00742 0,
00743 2,
00744 0,
00745 1,
00746 0,
00747 5,
00748 0,
00749 1,
00750 0,
00751 2,
00752 0,
00753 1,
00754 0,
00755 3,
00756 0,
00757 1,
00758 0,
00759 2,
00760 0,
00761 1,
00762 0,
00763 4,
00764 0,
00765 1,
00766 0,
00767 2,
00768 0,
00769 1,
00770 0,
00771 3,
00772 0,
00773 1,
00774 0,
00775 2,
00776 0,
00777 1,
00778 0,
00779 };
00780
00781
00782
00783
00784
00785
00786
00787
00788
00789
00790 extern BS_ELT
00791 BS_Choose(
00792 const BS* set
00793 )
00794 {
00795 BS_ELT i, j;
00796
00797 for ( i = 0; i < BS_word_count(set); ++i ) {
00798 if ( BS_word(set,i) != bs_ZEROS ) {
00799 BS_ELT first_byte = bs_PBytesPW(i);
00800
00801 for ( j = 0; j < BYTES_PER_BS_WORD; ++j ) {
00802 BS_BYTE byte = BS_byte(set,j + first_byte);
00803
00804 if ( byte != bs_ZEROS )
00805 return first_one[byte] + bs_PBPB(j + first_byte);
00806 }
00807
00808 Is_True(FALSE,("Word not zero, but no byte found"));
00809 }
00810 }
00811
00812 return BS_CHOOSE_FAILURE;
00813 }
00814
00815
00816
00817
00818
00819
00820
00821
00822
00823
00824 extern BS_ELT
00825 BS_Choose_Range(
00826 BS *set,
00827 BS_ELT low,
00828 BS_ELT high
00829 )
00830 {
00831 BS_BYTE byte;
00832 BS_ELT last_first_word_full_byte, i, j;
00833 BS_ELT first_word, last_word;
00834 BS_ELT first_byte, last_byte;
00835 BS_ELT last_elt_in_set;
00836
00837 Is_True(low >= 0,
00838 ("BS_Choose_Range called with negative low element."));
00839 Is_True(high - low >= -1,
00840 ("BS_Choose_Range called with negative range size."));
00841
00842
00843
00844 last_elt_in_set = bs_PBPW(BS_word_count(set)) - 1;
00845 if ( high > last_elt_in_set )
00846 high = last_elt_in_set;
00847
00848
00849
00850
00851 if ( low > high )
00852 return BS_CHOOSE_FAILURE;
00853
00854 first_byte = bs_QBPB(low);
00855 last_byte = bs_QBPB(high);
00856
00857
00858
00859
00860
00861
00862 byte = BS_byte(set,first_byte) & (bs_ONES << bs_RBPB(low));
00863 if ( first_byte == last_byte )
00864 byte &= bs_ONES >> ((BITS_PER_BS_WORD - 1) - bs_RBPB(high));
00865
00866 if ( byte != bs_ZEROS )
00867 return first_one[byte] + bs_PBPB(first_byte);
00868 else if (first_byte == last_byte)
00869 return BS_CHOOSE_FAILURE;
00870
00871
00872
00873
00874
00875 first_word = bs_QBPW(low);
00876 last_first_word_full_byte = (first_word + 1) * sizeof(BS_WORD) - 1;
00877
00878 if ( last_first_word_full_byte >= last_byte )
00879 last_first_word_full_byte = last_byte - 1;
00880
00881 for ( i = first_byte + 1; i <= last_first_word_full_byte; ++i ) {
00882 byte = BS_byte(set,i);
00883
00884 if ( byte != bs_ZEROS )
00885 return first_one[byte] + bs_PBPB(i);
00886 }
00887
00888
00889
00890
00891
00892
00893 last_word = bs_QBPW(high);
00894
00895 for ( i = first_word + 1; i < last_word; ++i ) {
00896 if ( BS_word(set,i) != bs_ZEROS ) {
00897
00898
00899 for ( j = 0; j < sizeof(BS_WORD); ++j ) {
00900 byte = BS_byte(set, j + i * BYTES_PER_BS_WORD);
00901
00902 if ( byte != 0 )
00903 return first_one[byte] + bs_PBPB(j) + bs_PBPW(i);
00904 }
00905 }
00906 }
00907
00908
00909
00910
00911
00912
00913
00914 for ( i *= sizeof(BS_WORD); i < last_byte; ++i ) {
00915 byte = BS_byte(set,i);
00916
00917 if ( byte != 0 )
00918 return first_one[byte] + 8 * i;
00919 }
00920
00921
00922
00923
00924 byte = BS_byte(set,last_byte)
00925 & (bs_ONES >> ((BITS_PER_BS_WORD - 1) - bs_RBPB(high)));
00926
00927 if ( byte != 0 )
00928 return first_one[byte] + bs_PBPB(last_byte);
00929
00930 return BS_CHOOSE_FAILURE;
00931 }
00932
00933
00934
00935
00936
00937
00938
00939
00940
00941
00942
00943 extern BS_ELT
00944 BS_Choose_Next(
00945 const BS* set,
00946 BS_ELT bound
00947 )
00948 {
00949 BS_ELT i, j, inx_first_byte, inx_first_byte_second_word, word_count;
00950 BS_BYTE byte;
00951
00952 ++bound;
00953
00954 if ( bound >= bs_PBPW(BS_word_count(set)) )
00955 return BS_CHOOSE_FAILURE;
00956
00957
00958
00959 inx_first_byte = bs_QBPB(bound);
00960 byte = BS_byte(set,inx_first_byte) & (bs_ONES << bs_RBPB(bound));
00961 if ( byte != bs_ZEROS )
00962 return first_one[byte] + bs_PBPB(inx_first_byte);
00963
00964
00965
00966 inx_first_byte_second_word = (bs_QBPW(bound) + 1) * sizeof(BS_WORD);
00967
00968 for ( i = inx_first_byte + 1; i < inx_first_byte_second_word; ++i ) {
00969 byte = BS_byte(set,i);
00970
00971 if ( byte != bs_ZEROS )
00972 return first_one[byte] + bs_PBPB(i);
00973 }
00974
00975
00976
00977 word_count = BS_word_count(set);
00978
00979 for ( i = bs_QBPW(bound) + 1; i < word_count; ++i ) {
00980 if ( BS_word(set,i) != bs_ZEROS ) {
00981 BS_ELT first_byte = bs_PBytesPW(i);
00982
00983
00984
00985 for ( j = 0; j < BYTES_PER_BS_WORD; ++j ) {
00986 BS_BYTE byte = BS_byte(set,j + first_byte);
00987
00988 if ( byte != bs_ZEROS )
00989 return first_one[byte] + bs_PBPB(j + first_byte);
00990 }
00991
00992 Is_True(FALSE,("Word not zero, but no byte found"));
00993 }
00994 }
00995
00996 return BS_CHOOSE_FAILURE;
00997 }
00998
00999
01000
01001
01002
01003
01004
01005
01006
01007
01008
01009 extern BS_ELT
01010 BS_Intersection_Choose(
01011 BS* set1,
01012 BS* set2
01013 )
01014 {
01015 BS_ELT i, j;
01016 BS_ELT last_word;
01017
01018 if ( BS_word_count(set1) < BS_word_count(set2) )
01019 last_word = BS_word_count(set1);
01020 else
01021 last_word = BS_word_count(set2);
01022
01023 for ( i = 0; i < last_word; ++i ) {
01024 if ( (BS_word(set1,i) & BS_word(set2,i)) != bs_ZEROS ) {
01025 BS_ELT first_byte = bs_PBytesPW(i);
01026
01027 for ( j = 0; j < BYTES_PER_BS_WORD; ++j ) {
01028 BS_BYTE byte = BS_byte(set1,j + first_byte)
01029 & BS_byte(set2,j + first_byte);
01030
01031 if ( byte != bs_ZEROS )
01032 return first_one[byte] + bs_PBPB(j + first_byte);
01033 }
01034
01035 Is_True(FALSE,("Word not zero, but no byte found"));
01036 }
01037 }
01038
01039 return BS_CHOOSE_FAILURE;
01040 }
01041
01042
01043
01044
01045
01046
01047
01048
01049
01050
01051
01052
01053 extern BS_ELT
01054 BS_Intersection_Choose_Next(
01055 BS* set1,
01056 BS* set2,
01057 BS_ELT bound
01058 )
01059 {
01060 BS_ELT i, j, inx_first_byte, inx_first_byte_second_word, word_count;
01061 BS_BYTE byte;
01062
01063 if ( BS_word_count(set1) < BS_word_count(set2) )
01064 word_count = BS_word_count(set1);
01065 else
01066 word_count = BS_word_count(set2);
01067
01068 ++bound;
01069
01070 if ( bound >= bs_PBPW(word_count) )
01071 return BS_CHOOSE_FAILURE;
01072
01073
01074
01075 inx_first_byte = bs_QBPB(bound);
01076 byte = BS_byte(set1,inx_first_byte)
01077 & BS_byte(set2,inx_first_byte)
01078 & (bs_ONES << bs_RBPB(bound));
01079 if ( byte != bs_ZEROS )
01080 return first_one[byte] + bs_PBPB(inx_first_byte);
01081
01082
01083
01084 inx_first_byte_second_word = (bs_QBPW(bound) + 1) * sizeof(BS_WORD);
01085
01086 for ( i = inx_first_byte + 1; i < inx_first_byte_second_word; ++i ) {
01087 byte = BS_byte(set1,i)
01088 & BS_byte(set2,i);
01089
01090 if ( byte != bs_ZEROS )
01091 return first_one[byte] + bs_PBPB(i);
01092 }
01093
01094
01095
01096 for ( i = bs_QBPW(bound) + 1; i < word_count; ++i ) {
01097 if ( (BS_word(set1,i) & BS_word(set2,i)) != bs_ZEROS ) {
01098 BS_ELT first_byte = bs_PBytesPW(i);
01099
01100
01101
01102 for ( j = 0; j < BYTES_PER_BS_WORD; ++j ) {
01103 BS_BYTE byte = BS_byte(set1,j + first_byte)
01104 & BS_byte(set2,j + first_byte);
01105
01106 if ( byte != bs_ZEROS )
01107 return first_one[byte] + bs_PBPB(j + first_byte);
01108 }
01109
01110 Is_True(FALSE,("Word not zero, but no byte found"));
01111 }
01112 }
01113
01114 return BS_CHOOSE_FAILURE;
01115 }
01116
01117
01118
01119
01120
01121
01122
01123
01124
01125
01126
01127
01128 extern BS*
01129 BS_Difference(
01130 BS *set1,
01131 BS *set2,
01132 MEM_POOL *pool
01133 )
01134 {
01135 BS *set;
01136 BS_ELT i;
01137 BS_ELT size1 = BS_word_count(set1);
01138 BS_ELT size2 = BS_word_count(set2);
01139 BS_ELT minsize = Min(size1,size2);
01140
01141 set = bs_Malloc(size1,pool);
01142
01143
01144
01145 for ( i = 0; i < minsize; ++i )
01146 BS_word(set,i) = BS_word(set1,i) & ~BS_word(set2,i);
01147
01148
01149
01150 for ( i = minsize; i < size1; ++i )
01151 BS_word(set,i) = BS_word(set1,i);
01152
01153 return set;
01154 }
01155
01156
01157
01158
01159
01160
01161
01162
01163
01164
01165 extern BS*
01166 BS_DifferenceD(
01167 BS* set1,
01168 BS* set2
01169 )
01170 {
01171 BS_ELT i;
01172 BS_ELT minsize = Min(BS_word_count(set1),BS_word_count(set2));
01173
01174 for ( i = 0; i < minsize; ++i )
01175 BS_word(set1,i) &= ~BS_word(set2,i);
01176
01177 return set1;
01178 }
01179
01180
01181
01182
01183
01184
01185
01186
01187
01188
01189 extern BS*
01190 BS_Difference1(
01191 BS *set,
01192 BS_ELT x,
01193 MEM_POOL *pool
01194 )
01195 {
01196 return BS_Difference1D(BS_Copy(set,pool),x);
01197 }
01198
01199
01200
01201
01202
01203
01204
01205
01206
01207
01208 extern BS*
01209 BS_Difference1D(
01210 BS *set,
01211 BS_ELT x
01212 )
01213 {
01214 Is_True(x >= 0,
01215 ("BS_Difference1D called with negative element."));
01216
01217 if ( bs_QBPW(x) < BS_word_count(set) )
01218 BS_byte(set,bs_QBPB(x)) &= ~(bs_ONE << bs_RBPB(x));
01219
01220 return set;
01221 }
01222
01223
01224
01225
01226
01227
01228
01229
01230
01231
01232 extern BS*
01233 BS_Intersection(
01234 BS *set1,
01235 BS *set2,
01236 MEM_POOL *pool
01237 )
01238 {
01239 BS_ELT i;
01240 BS_ELT size;
01241 BS *newset;
01242
01243 if ( BS_word_count(set1) < BS_word_count(set2) )
01244 size = BS_word_count(set1);
01245 else
01246 size = BS_word_count(set2);
01247
01248 newset = bs_Malloc(size,pool);
01249
01250 for ( i = 0; i < size; ++i )
01251 BS_word(newset,i) = BS_word(set1,i) & BS_word(set2,i);
01252
01253 return newset;
01254 }
01255
01256
01257
01258
01259
01260
01261
01262
01263
01264
01265 extern BS*
01266 BS_IntersectionD(
01267 BS* set1,
01268 BS* set2
01269 )
01270 {
01271 BS_ELT i;
01272 BS_ELT minsize;
01273
01274 minsize = MIN( BS_word_count(set1), BS_word_count(set2) );
01275
01276
01277
01278 for ( i = 0; i < minsize; ++i )
01279 BS_word(set1,i) &= BS_word(set2,i);
01280
01281
01282
01283 for ( i = i; i < BS_word_count(set1); ++i )
01284 BS_word(set1,i) = bs_ZEROS;
01285
01286 return set1;
01287 }
01288
01289
01290
01291
01292
01293
01294
01295
01296
01297
01298
01299 extern BS*
01300 BS_IntersectionR(
01301 BS* result,
01302 const BS* set1,
01303 const BS* set2
01304 )
01305 {
01306 BS_ELT i;
01307 BS_ELT minsize;
01308
01309 minsize = MIN( BS_word_count(set1), BS_word_count(set2) );
01310
01311
01312
01313 for ( i = 0; i < minsize; ++i )
01314 BS_word(result,i) = BS_word(set1,i) & BS_word(set2,i);
01315
01316
01317
01318 for ( i = i; i < BS_word_count(result); ++i )
01319 BS_word(result,i) = bs_ZEROS;
01320
01321 return result;
01322 }
01323
01324
01325
01326
01327 static unsigned const char bit_count[256] = {
01328 0,
01329 1,
01330 1,
01331 2,
01332 1,
01333 2,
01334 2,
01335 3,
01336 1,
01337 2,
01338 2,
01339 3,
01340 2,
01341 3,
01342 3,
01343 4,
01344 1,
01345 2,
01346 2,
01347 3,
01348 2,
01349 3,
01350 3,
01351 4,
01352 2,
01353 3,
01354 3,
01355 4,
01356 3,
01357 4,
01358 4,
01359 5,
01360 1,
01361 2,
01362 2,
01363 3,
01364 2,
01365 3,
01366 3,
01367 4,
01368 2,
01369 3,
01370 3,
01371 4,
01372 3,
01373 4,
01374 4,
01375 5,
01376 2,
01377 3,
01378 3,
01379 4,
01380 3,
01381 4,
01382 4,
01383 5,
01384 3,
01385 4,
01386 4,
01387 5,
01388 4,
01389 5,
01390 5,
01391 6,
01392 1,
01393 2,
01394 2,
01395 3,
01396 2,
01397 3,
01398 3,
01399 4,
01400 2,
01401 3,
01402 3,
01403 4,
01404 3,
01405 4,
01406 4,
01407 5,
01408 2,
01409 3,
01410 3,
01411 4,
01412 3,
01413 4,
01414 4,
01415 5,
01416 3,
01417 4,
01418 4,
01419 5,
01420 4,
01421 5,
01422 5,
01423 6,
01424 2,
01425 3,
01426 3,
01427 4,
01428 3,
01429 4,
01430 4,
01431 5,
01432 3,
01433 4,
01434 4,
01435 5,
01436 4,
01437 5,
01438 5,
01439 6,
01440 3,
01441 4,
01442 4,
01443 5,
01444 4,
01445 5,
01446 5,
01447 6,
01448 4,
01449 5,
01450 5,
01451 6,
01452 5,
01453 6,
01454 6,
01455 7,
01456 1,
01457 2,
01458 2,
01459 3,
01460 2,
01461 3,
01462 3,
01463 4,
01464 2,
01465 3,
01466 3,
01467 4,
01468 3,
01469 4,
01470 4,
01471 5,
01472 2,
01473 3,
01474 3,
01475 4,
01476 3,
01477 4,
01478 4,
01479 5,
01480 3,
01481 4,
01482 4,
01483 5,
01484 4,
01485 5,
01486 5,
01487 6,
01488 2,
01489 3,
01490 3,
01491 4,
01492 3,
01493 4,
01494 4,
01495 5,
01496 3,
01497 4,
01498 4,
01499 5,
01500 4,
01501 5,
01502 5,
01503 6,
01504 3,
01505 4,
01506 4,
01507 5,
01508 4,
01509 5,
01510 5,
01511 6,
01512 4,
01513 5,
01514 5,
01515 6,
01516 5,
01517 6,
01518 6,
01519 7,
01520 2,
01521 3,
01522 3,
01523 4,
01524 3,
01525 4,
01526 4,
01527 5,
01528 3,
01529 4,
01530 4,
01531 5,
01532 4,
01533 5,
01534 5,
01535 6,
01536 3,
01537 4,
01538 4,
01539 5,
01540 4,
01541 5,
01542 5,
01543 6,
01544 4,
01545 5,
01546 5,
01547 6,
01548 5,
01549 6,
01550 6,
01551 7,
01552 3,
01553 4,
01554 4,
01555 5,
01556 4,
01557 5,
01558 5,
01559 6,
01560 4,
01561 5,
01562 5,
01563 6,
01564 5,
01565 6,
01566 6,
01567 7,
01568 4,
01569 5,
01570 5,
01571 6,
01572 5,
01573 6,
01574 6,
01575 7,
01576 5,
01577 6,
01578 6,
01579 7,
01580 6,
01581 7,
01582 7,
01583 8
01584 };
01585
01586
01587
01588
01589
01590
01591
01592
01593
01594
01595 extern BS_ELT
01596 BS_Size(
01597 BS* set
01598 )
01599 {
01600
01601
01602
01603
01604 BS_ELT i;
01605 BS_ELT byte_count = BS_word_count(set) * sizeof(BS_WORD);
01606 size_t result = 0;
01607
01608 for ( i = 0; i < byte_count; ++i )
01609 result += bit_count[BS_byte(set,i)];
01610
01611 return result;
01612 }
01613
01614
01615
01616
01617
01618
01619
01620
01621
01622
01623 extern BS*
01624 BS_Union(
01625 BS *set1,
01626 BS *set2,
01627 MEM_POOL *pool
01628 )
01629 {
01630 BS *set;
01631 BS_ELT i;
01632 BS_ELT size1 = BS_word_count(set1);
01633 BS_ELT size2 = BS_word_count(set2);
01634
01635 if ( size1 < size2 ) {
01636
01637
01638 BS *tmps = set1;
01639 BS_ELT tmpe = size1;
01640
01641 set1 = set2;
01642 set2 = tmps;
01643 size1 = size2;
01644 size2 = tmpe;
01645 }
01646
01647 set = bs_Malloc(size1,pool);
01648 for ( i = 0; i < size2; ++i )
01649 BS_word(set,i) = BS_word(set1,i) | BS_word(set2,i);
01650 for ( i = size2; i < size1; ++i )
01651 BS_word(set,i) = BS_word(set1,i);
01652
01653 return set;
01654 }
01655
01656
01657
01658
01659
01660
01661
01662
01663
01664
01665 extern BS*
01666 BS_UnionD(
01667 BS *set1,
01668 BS *set2,
01669 MEM_POOL *pool
01670 )
01671 {
01672 BS_ELT i;
01673 BS_ELT size1 = BS_word_count(set1);
01674 BS_ELT size2 = BS_word_count(set2);
01675
01676 if ( size1 < size2 )
01677 set1 = bs_Realloc(set1,size2,pool);
01678
01679 for ( i = 0; i < size2; ++i )
01680 BS_word(set1,i) |= BS_word(set2,i);
01681
01682 return set1;
01683 }
01684
01685
01686
01687
01688
01689
01690
01691
01692
01693
01694 extern BS*
01695 BS_UnionR(
01696 BS *result,
01697 BS *set1,
01698 BS *set2,
01699 MEM_POOL *pool
01700 )
01701 {
01702 BS_ELT i;
01703 BS_ELT size1 = BS_word_count(set1);
01704 BS_ELT size2 = BS_word_count(set2);
01705 BS_ELT maxsize = MAX( size1, size2 );
01706 BS_ELT rsize = BS_word_count(result);
01707
01708 if ( rsize < maxsize )
01709 result = bs_Realloc(result,maxsize,pool);
01710
01711 for ( i = 0; i < maxsize; ++i )
01712 BS_word(result,i) = BS_word(set1,i) | BS_word(set2,i);
01713
01714 return result;
01715 }
01716
01717
01718
01719
01720
01721
01722
01723
01724
01725
01726 extern BS*
01727 BS_UnionD_Intersection(
01728 BS *set1,
01729 BS *set2,
01730 BS *set3,
01731 MEM_POOL *pool
01732 )
01733 {
01734 BS_ELT i;
01735 BS_ELT size1 = BS_word_count(set1);
01736 BS_ELT minsize = MIN( BS_word_count(set2), BS_word_count(set3) );
01737
01738 if ( size1 < minsize )
01739 set1 = bs_Realloc(set1,minsize,pool);
01740
01741 for ( i = 0; i < minsize; ++i )
01742 BS_word(set1,i) |= BS_word(set2,i) & BS_word(set3,i);
01743
01744 return set1;
01745 }
01746
01747
01748
01749
01750
01751
01752
01753
01754
01755
01756 extern BS*
01757 BS_Union1(
01758 BS *set,
01759 BS_ELT x,
01760 MEM_POOL *pool
01761 )
01762 {
01763 BS_ELT newsize;
01764 BS *newset;
01765
01766 if ( BS_word_count(set) > bs_QBPW(x) + 1 )
01767 newsize = bs_PBPW(BS_word_count(set));
01768 else
01769 newsize = x + 1;
01770
01771 newset = BS_Create_Empty(newsize,pool);
01772 newset = BS_CopyD(newset,set,bad_pool);
01773 return BS_Union1D(newset,x,bad_pool);
01774 }
01775
01776
01777
01778
01779
01780
01781
01782
01783
01784
01785 extern BS*
01786 BS_Union1D(
01787 BS *set,
01788 BS_ELT x,
01789 MEM_POOL *pool
01790 )
01791 {
01792 BS_ELT minsize = bs_QBPW(x) + 1;
01793
01794 Is_True(x >= 0,("BS_Union1D called with negative element."));
01795
01796 if ( minsize > BS_word_count(set) )
01797 set = bs_Realloc(set,minsize,pool);
01798
01799 BS_byte(set,bs_QBPB(x)) |= bs_ONE << bs_RBPB(x);
01800
01801 return set;
01802 }
01803
01804
01805
01806
01807
01808
01809
01810
01811
01812
01813 extern BS*
01814 BS_2_1_Minus_3_Or_R(
01815 BS *result,
01816 const BS *set1,
01817 const BS *set2,
01818 const BS *set3,
01819 MEM_POOL *pool
01820 )
01821 {
01822 BS_ELT i;
01823 BS_ELT rsize = BS_word_count(result);
01824 BS_ELT size3 = BS_word_count(set3);
01825
01826 Is_True( BS_word_count(set1) == size3,
01827 ("BS_2_1_Minus_3_Or_R: set1 size (%d) < set3 size (%d)",
01828 (BS_ELT)BS_word_count(set1), size3) );
01829 Is_True( BS_word_count(set2) == size3,
01830 ("BS_2_1_Minus_3_Or_R: set2 size (%d) < set3 size (%d)",
01831 (BS_ELT)BS_word_count(set2), size3) );
01832
01833 if ( rsize < size3 )
01834 result = bs_Realloc(result,size3,pool);
01835
01836 for ( i = 0; i < size3; ++i )
01837 BS_word(result,i) = (~BS_word(set1,i) & BS_word(set2,i)) |
01838 BS_word(set3,i);
01839
01840 return result;
01841 }
01842
01843 extern BS*
01844 BS_3_2_Minus_1_Or_D(
01845 BS *set1,
01846 const BS *set2,
01847 const BS *set3,
01848 MEM_POOL *pool
01849 )
01850 {
01851 BS_ELT i;
01852 BS_ELT size1 = BS_word_count(set1);
01853 BS_ELT size2 = BS_word_count(set2);
01854 BS_ELT size3 = BS_word_count(set3);
01855
01856 Is_True( size2 == size3,
01857 ("BS_3_2_Minus_1_Or_D: set2 size (%d) != set3 size (%d)",
01858 size2, size3) );
01859
01860 if ( size1 < size3 )
01861 set1 = bs_Realloc(set1,size3,pool);
01862
01863 for ( i = 0; i < size3; ++i )
01864 BS_word(set1,i) |= (~BS_word(set2,i) & BS_word(set3,i));
01865
01866 return set1;
01867 }
01868
01869
01870
01871
01872
01873
01874
01875
01876
01877
01878
01879 extern BS*
01880 BS_3_2_Minus_4_Or_1_Or_D(
01881 BS *set1,
01882 const BS *set2,
01883 const BS *set3,
01884 const BS *set4,
01885 MEM_POOL *pool )
01886 {
01887 BS_ELT i;
01888 BS_ELT size1 = BS_word_count(set1);
01889 BS_ELT size2 = BS_word_count(set2);
01890 BS_ELT size3 = BS_word_count(set3);
01891 BS_ELT size4 = BS_word_count(set4);
01892
01893 Is_True( size2 == size3 && size3 == size4,
01894 ("BS_3_2_Minus_4_Or_1_Or_D: sizes not equal %d, %d, %d",
01895 size2, size3, size4) );
01896
01897 if ( size1 < size2 )
01898 set1 = bs_Realloc(set1,size2,pool);
01899
01900 for ( i = 0; i < size2; ++i )
01901 BS_word(set1,i) |= (~BS_word(set2,i) & BS_word(set3,i)) |
01902 BS_word(set4,i);
01903
01904 return set1;
01905 }
01906
01907
01908
01909
01910
01911
01912
01913
01914
01915
01916
01917
01918 extern BS*
01919 BS_3_2_Minus_4_Or_5_Or_1_Or_D(
01920 BS *set1,
01921 const BS *set2,
01922 const BS *set3,
01923 const BS *set4,
01924 const BS *set5,
01925 MEM_POOL *pool )
01926 {
01927 BS_ELT i;
01928 BS_ELT size1 = BS_word_count(set1);
01929 BS_ELT size5 = BS_word_count(set5);
01930
01931 Is_True( BS_word_count(set2) == size5,
01932 ("BS_3_2_Minus_4_Or_5_Or_1_Or_D: set2 size (%d) != set5 size (%d)",
01933 (BS_ELT)BS_word_count(set2), size5) );
01934 Is_True( BS_word_count(set3) == size5,
01935 ("BS_3_2_Minus_4_Or_5_Or_1_Or_D: set3 size (%d) != set5 size (%d)",
01936 (BS_ELT)BS_word_count(set3), size5) );
01937 Is_True( BS_word_count(set4) == size5,
01938 ("BS_3_2_Minus_4_Or_5_Or_1_Or_D: set4 size (%d) != set5 size (%d)",
01939 (BS_ELT)BS_word_count(set4), size5) );
01940
01941 if ( size1 < size5 )
01942 set1 = bs_Realloc(set1,size5,pool);
01943
01944 for ( i = 0; i < size5; ++i )
01945 BS_word(set1,i) |= (~BS_word(set2,i) & BS_word(set3,i)) |
01946 BS_word(set4,i) | BS_word(set5,i);
01947
01948 return set1;
01949 }
01950
01951
01952
01953
01954
01955
01956
01957
01958
01959
01960
01961 extern BS*
01962 BS_2_1_Minus_3_Or_4_And_5_And_6_And_R(
01963 BS *result,
01964 const BS *set1,
01965 const BS *set2,
01966 const BS *set3,
01967 const BS *set4,
01968 const BS *set5,
01969 const BS *set6,
01970 MEM_POOL *pool
01971 )
01972 {
01973 BS_ELT i;
01974 BS_ELT rsize = BS_word_count(result);
01975 BS_ELT size3 = BS_word_count(set3);
01976
01977 Is_True( BS_word_count(set1) == size3,
01978 ("BS_2_1_Minus_3_Or_4_And_5_And_6_And_R: set1 size (%d) < set3 size (%d)",
01979 (BS_ELT)BS_word_count(set1), size3) );
01980 Is_True( BS_word_count(set2) == size3,
01981 ("BS_2_1_Minus_3_Or_4_And_5_And_6_And_R: set2 size (%d) < set3 size (%d)",
01982 (BS_ELT)BS_word_count(set2), size3) );
01983 Is_True( BS_word_count(set4) == size3,
01984 ("BS_2_1_Minus_3_Or_4_And_5_And_6_And_R: set4 size (%d) < set3 size (%d)",
01985 (BS_ELT)BS_word_count(set4), size3) );
01986 Is_True( BS_word_count(set5) == size3,
01987 ("BS_2_1_Minus_3_Or_4_And_5_And_6_And_R: set5 size (%d) < set3 size (%d)",
01988 (BS_ELT)BS_word_count(set4), size3) );
01989 Is_True( BS_word_count(set6) == size3,
01990 ("BS_2_1_Minus_3_Or_4_And_5_And_6_And_R: set6 size (%d) < set3 size (%d)",
01991 (BS_ELT)BS_word_count(set6), size3) );
01992
01993 if ( rsize < size3 )
01994 result = bs_Realloc(result,size3,pool);
01995
01996 for ( i = 0; i < size3; ++i )
01997 BS_word(result,i) = ((~BS_word(set1,i) & BS_word(set2,i)) |
01998 BS_word(set3,i)) &
01999 BS_word(set4,i) &
02000 BS_word(set5,i) &
02001 BS_word(set6,i);
02002
02003 return result;
02004 }
02005
02006
02007
02008
02009
02010
02011
02012
02013
02014
02015 extern BS*
02016 BS_2_1_Minus_3_Or_4_And_R(
02017 BS *result,
02018 const BS *set1,
02019 const BS *set2,
02020 const BS *set3,
02021 const BS *set4,
02022 MEM_POOL *pool
02023 )
02024 {
02025 BS_ELT i;
02026 BS_ELT rsize = BS_word_count(result);
02027 BS_ELT size3 = BS_word_count(set3);
02028
02029 Is_True( BS_word_count(set1) == size3,
02030 ("BS_2_1_Minus_3_Or_4_And_R: set1 size (%d) < set3 size (%d)",
02031 (BS_ELT)BS_word_count(set1), size3) );
02032 Is_True( BS_word_count(set2) == size3,
02033 ("BS_2_1_Minus_3_Or_4_And_R: set2 size (%d) < set3 size (%d)",
02034 (BS_ELT)BS_word_count(set2), size3) );
02035 Is_True( BS_word_count(set4) == size3,
02036 ("BS_2_1_Minus_3_Or_4_And_R: set4 size (%d) < set3 size (%d)",
02037 (BS_ELT)BS_word_count(set4), size3) );
02038
02039 if ( rsize < size3 )
02040 result = bs_Realloc(result,size3,pool);
02041
02042 for ( i = 0; i < size3; ++i )
02043 BS_word(result,i) = ((~BS_word(set1,i) & BS_word(set2,i)) |
02044 BS_word(set3,i)) &
02045 BS_word(set4,i);
02046
02047 return result;
02048 }
02049
02050
02051
02052
02053
02054
02055
02056
02057
02058
02059 extern BS*
02060 BS_1_Not_2_Or_3_Minus_4_And_R(
02061 BS *result,
02062 const BS *set1,
02063 const BS *set2,
02064 const BS *set3,
02065 const BS *set4,
02066 MEM_POOL *pool
02067 )
02068 {
02069 BS_ELT i;
02070 BS_ELT rsize = BS_word_count(result);
02071 BS_ELT size2 = BS_word_count(set2);
02072
02073 Is_True( BS_word_count(set1) == size2,
02074 ("BS_1_Not_2_Or_3_Minus_4_And_R: set1 size (%d) < set2 size (%d)",
02075 (BS_ELT)BS_word_count(set1), size2) );
02076 Is_True( BS_word_count(set3) == size2,
02077 ("BS_1_Not_2_Or_3_Minus_4_And_R: set3 size (%d) < set2 size (%d)",
02078 (BS_ELT)BS_word_count(set3), size2) );
02079 Is_True( BS_word_count(set4) == size2,
02080 ("BS_1_Not_2_Or_3_Minus_4_And_R: set4 size (%d) < set2 size (%d)",
02081 (BS_ELT)BS_word_count(set4), size2) );
02082
02083 if ( rsize < size2 )
02084 result = bs_Realloc(result,size2,pool);
02085
02086 for ( i = 0; i < size2; ++i )
02087 BS_word(result,i) = (~BS_word(set1,i) | BS_word(set2,i)) &
02088 (~BS_word(set3,i)) &
02089 BS_word(set4,i);
02090 return result;
02091 }
02092
02093
02094
02095
02096
02097
02098
02099
02100
02101
02102
02103 extern BS*
02104 BS_2_3_Or_1_Or_D(
02105 BS *set1,
02106 const BS *set2,
02107 const BS *set3,
02108 MEM_POOL *pool )
02109 {
02110 BS_ELT i;
02111 BS_ELT size1 = BS_word_count(set1);
02112 BS_ELT size2 = BS_word_count(set2);
02113 BS_ELT size3 = BS_word_count(set3);
02114
02115 Is_True( size2 == size3,
02116 ("BS_2_3_Or_1_Or_D: sizes not equal %d, %d",
02117 size2, size3) );
02118
02119 if ( size1 < size2 )
02120 set1 = bs_Realloc(set1,size2,pool);
02121
02122 for ( i = 0; i < size2; ++i )
02123 BS_word(set1,i) |= (BS_word(set2,i) | BS_word(set3,i));
02124
02125 return set1;
02126 }
02127
02128
02129
02130
02131
02132
02133
02134
02135
02136
02137 extern BS*
02138 BS_1_2_Or_3_And_R(
02139 BS *result,
02140 const BS *set1,
02141 const BS *set2,
02142 const BS *set3,
02143 MEM_POOL *pool
02144 )
02145 {
02146 BS_ELT i;
02147 BS_ELT rsize = BS_word_count(result);
02148 BS_ELT size1 = BS_word_count(set1);
02149
02150 Is_True( BS_word_count(set2) == size1,
02151 ("BS_1_2_Or_3_And_R: set2 size (%d) < set1 size (%d)",
02152 (BS_ELT)BS_word_count(set2), size1) );
02153 Is_True( BS_word_count(set3) == size1,
02154 ("BS_1_2_Or_3_And_R: set3 size (%d) < set1 size (%d)",
02155 (BS_ELT)BS_word_count(set3), size1) );
02156
02157 if ( rsize < size1 )
02158 result = bs_Realloc(result,size1,pool);
02159
02160 for ( i = 0; i < size1; ++i )
02161 BS_word(result,i) = (BS_word(set1,i) | BS_word(set2,i)) &
02162 BS_word(set3,i);
02163
02164 return result;
02165 }
02166
02167
02168
02169
02170
02171
02172
02173
02174
02175
02176 extern BS*
02177 BS_2_3_And_1_Or_D(
02178 BS *set1,
02179 const BS *set2,
02180 const BS *set3,
02181 MEM_POOL *pool
02182 )
02183 {
02184 BS_ELT i;
02185 BS_ELT size1 = BS_word_count(set1);
02186 BS_ELT size = MIN(BS_word_count(set2),BS_word_count(set3));
02187
02188 if ( size1 < size )
02189 set1 = bs_Realloc(set1,size,pool);
02190
02191 for ( i = 0; i < size; ++i )
02192 BS_word(set1,i) |= BS_word(set2,i) & BS_word(set3,i);
02193
02194 return set1;
02195 }
02196
02197
02198
02199
02200
02201
02202
02203
02204
02205
02206 extern BS*
02207 BS_3_Not_4_Or_2_And_1_Or_D(
02208 BS *set1,
02209 const BS *set2,
02210 const BS *set3,
02211 const BS *set4,
02212 MEM_POOL *pool
02213 )
02214 {
02215 BS_ELT i;
02216 BS_ELT size1 = BS_word_count(set1);
02217 BS_ELT size2 = BS_word_count(set2);
02218
02219 Is_True( BS_word_count(set3) == size2,
02220 ("BS_3_Not_4_Or_2_And_1_Or_D: set3 size (%d) < set2 size (%d)",
02221 (BS_ELT)BS_word_count(set3), size2) );
02222 Is_True( BS_word_count(set4) == size2,
02223 ("BS_3_Not_4_Or_2_And_1_Or_D: set4 size (%d) < set2 size (%d)",
02224 (BS_ELT)BS_word_count(set4), size2) );
02225
02226 if ( size1 < size2 )
02227 set1 = bs_Realloc(set1,size2,pool);
02228
02229 for ( i = 0; i < size2; ++i )
02230 BS_word(set1,i) |= BS_word(set2,i) &
02231 (~BS_word(set3,i) | BS_word(set4,i));
02232
02233 return set1;
02234 }
02235
02236
02237
02238
02239
02240
02241
02242
02243
02244
02245 extern BS*
02246 BS_4_3_Minus_2_Not_Or_1_And_D(
02247 BS *set1,
02248 const BS *set2,
02249 const BS *set3,
02250 const BS *set4,
02251 MEM_POOL *pool
02252 )
02253 {
02254 BS_ELT i;
02255 BS_ELT size1 = BS_word_count(set1);
02256 BS_ELT size2 = BS_word_count(set2);
02257
02258 Is_True( BS_word_count(set3) == size2,
02259 ("BS_4_3_Minus_2_Not_Or_1_And_D: set3 size (%d) < set2 size (%d)",
02260 (BS_ELT)BS_word_count(set3), size2) );
02261 Is_True( BS_word_count(set4) == size2,
02262 ("BS_4_3_Minus_2_Not_Or_1_And_D: set4 size (%d) < set2 size (%d)",
02263 (BS_ELT)BS_word_count(set4), size2) );
02264
02265 if ( size1 < size2 )
02266 set1 = bs_Realloc(set1,size2,pool);
02267
02268 for ( i = 0; i < size2; ++i )
02269 BS_word(set1,i) &= ~BS_word(set2,i) |
02270 (BS_word(set4,i) & ~BS_word(set3,i));
02271
02272 return set1;
02273 }
02274
02275
02276
02277
02278
02279
02280
02281
02282
02283
02284 extern BS*
02285 BS_2_3_Minus_1_Or_D(
02286 BS *set1,
02287 const BS *set2,
02288 const BS *set3,
02289 MEM_POOL *pool
02290 )
02291 {
02292 BS_ELT i;
02293 BS_ELT size1 = BS_word_count(set1);
02294 BS_ELT size2 = BS_word_count(set2);
02295 BS_ELT size3 = BS_word_count(set3);
02296
02297 Is_True( size2 == size3,
02298 ("BS_2_3_Minus_1_Or_D: sizes not equal %d, %d",
02299 size2, size3) );
02300
02301 if ( size1 < size2 )
02302 set1 = bs_Realloc(set1,size2,pool);
02303
02304 for ( i = 0; i < size2; ++i )
02305 BS_word(set1,i) |= BS_word(set2,i) & ~BS_word(set3,i);
02306
02307 return set1;
02308 }
02309
02310
02311
02312
02313
02314
02315
02316
02317
02318
02319 extern BS*
02320 BS_2_3_Minus_4_Minus_1_Or_D(
02321 BS *set1,
02322 const BS *set2,
02323 const BS *set3,
02324 const BS *set4,
02325 MEM_POOL *pool
02326 )
02327 {
02328 BS_ELT i;
02329 BS_ELT size1 = BS_word_count(set1);
02330 BS_ELT size2 = BS_word_count(set2);
02331 BS_ELT size3 = BS_word_count(set3);
02332 BS_ELT size4 = BS_word_count(set4);
02333
02334 Is_True( size2 == size3 && size3 == size4,
02335 ("BS_2_3_Minus_4_Minus_1_Or_D: sizes not equal %d, %d, %d",
02336 size2, size3, size4) );
02337
02338 if ( size1 < size2 )
02339 set1 = bs_Realloc(set1,size2,pool);
02340
02341 for ( i = 0; i < size2; ++i )
02342 BS_word(set1,i) |= BS_word(set2,i) & ~BS_word(set3,i)
02343 & ~BS_word(set4,i);
02344
02345 return set1;
02346 }
02347
02348
02349
02350
02351
02352
02353
02354
02355
02356
02357 extern BOOL
02358 BS_ContainsP(
02359 BS *set1,
02360 BS *set2
02361 )
02362 {
02363 BS_ELT minsize;
02364 BS_ELT i;
02365
02366 if ( BS_word_count(set1) < BS_word_count(set2) )
02367 minsize = BS_word_count(set1);
02368 else
02369 minsize = BS_word_count(set2);
02370
02371
02372
02373 for ( i = 0; i < minsize; ++i ) {
02374 if ( BS_word(set1,i) != (BS_word(set1,i) | BS_word(set2,i)) )
02375 return FALSE;
02376 }
02377
02378
02379
02380 for ( ; i < BS_word_count(set2); ++i ) {
02381 if ( BS_word(set2,i) != bs_ZEROS )
02382 return FALSE;
02383 }
02384
02385 return TRUE;
02386 }
02387
02388
02389
02390
02391
02392
02393
02394
02395
02396
02397 extern BOOL
02398 BS_EmptyP(
02399 BS *set
02400 )
02401 {
02402 BS_ELT i;
02403
02404 for ( i = 0; i < BS_word_count(set); ++i ) {
02405 if ( BS_word(set,i) != bs_ZEROS )
02406 return FALSE;
02407 }
02408
02409 return TRUE;
02410 }
02411
02412
02413
02414
02415
02416
02417
02418
02419
02420
02421 extern BOOL
02422 BS_EqualP(
02423 BS *set1,
02424 BS *set2
02425 )
02426 {
02427 BS_ELT i;
02428
02429
02430
02431 if ( BS_word_count(set1) > BS_word_count(set2) ) {
02432 BS *tmp = set1;
02433 set1 = set2;
02434 set2 = tmp;
02435 }
02436
02437 for ( i = 0; i < BS_word_count(set1); ++i ) {
02438 if ( BS_word(set1,i) != BS_word(set2,i) )
02439 return FALSE;
02440 }
02441
02442 for ( ; i < BS_word_count(set2); ++i ) {
02443 if ( BS_word(set2,i) != bs_ZEROS )
02444 return FALSE;
02445 }
02446
02447 return TRUE;
02448 }
02449
02450
02451
02452
02453
02454
02455
02456
02457
02458
02459 extern BOOL
02460 BS_IntersectsP(
02461 BS *set1,
02462 BS *set2
02463 )
02464 {
02465 BS_ELT minsize, i;
02466
02467 if ( BS_word_count(set1) < BS_word_count(set2) )
02468 minsize = BS_word_count(set1);
02469 else
02470 minsize = BS_word_count(set2);
02471
02472 for ( i = 0; i < minsize; ++i ) {
02473 if ( (BS_word(set1,i) & BS_word(set2,i)) != bs_ZEROS )
02474 return TRUE;
02475 }
02476
02477 return FALSE;
02478 }
02479
02480
02481
02482
02483
02484
02485
02486
02487
02488
02489 extern BOOL
02490 BS_MemberP(
02491 BS *set,
02492 BS_ELT x
02493 )
02494 {
02495 Is_True(x >= 0,("BS_Member called with negative element."));
02496
02497 if ( bs_QBPW(x) >= BS_word_count(set) )
02498 return FALSE;
02499 else
02500 return (BS_byte(set,bs_QBPB(x)) & (bs_ONE << bs_RBPB(x)))
02501 != bs_ZEROS;
02502 }
02503
02504
02505
02506
02507
02508
02509
02510
02511
02512
02513 extern BOOL
02514 BS_Intersection_MemberP(
02515 BS *set1,
02516 BS *set2,
02517 BS_ELT x
02518 )
02519 {
02520 Is_True(x >= 0,("BS_Member called with negative element."));
02521
02522 if ( bs_QBPW(x) >= BS_word_count(set1)
02523 || bs_QBPW(x) >= BS_word_count(set2)
02524 ) {
02525 return FALSE;
02526 }
02527 else {
02528 return ( BS_byte(set1,bs_QBPB(x))
02529 & BS_byte(set2,bs_QBPB(x))
02530 & (bs_ONE << bs_RBPB(x)))
02531 != bs_ZEROS;
02532 }
02533 }
02534
02535
02536
02537
02538
02539
02540
02541
02542
02543
02544
02545
02546
02547
02548
02549 static void
02550 PrintRange(
02551 FILE *f,
02552 BS_ELT low,
02553 BS_ELT high,
02554 BOOL *first
02555 )
02556 {
02557 if ( *first )
02558 *first = FALSE;
02559 else
02560 fprintf(f,",");
02561
02562 if ( low == high )
02563 fprintf(f,"%d",low);
02564 else
02565 fprintf(f,"%d-%d",low,high);
02566 }
02567
02568
02569
02570
02571
02572
02573
02574
02575
02576
02577 extern void
02578 BS_Print(
02579 BS *set,
02580 FILE *f
02581 )
02582 {
02583 BS_ELT range_first, last_elt, elt;
02584 BOOL first = TRUE;
02585
02586 if ( set == NULL ) {
02587 fprintf ( f, "<NULL>" );
02588 return;
02589 }
02590
02591 fprintf(f,"{");
02592
02593 elt = BS_Choose(set);
02594 if ( elt == BS_CHOOSE_FAILURE ) {
02595 fprintf(f,"}");
02596 return;
02597 }
02598 range_first = elt;
02599 last_elt = range_first;
02600
02601 while ( (elt = BS_Choose_Next(set,elt)) != BS_CHOOSE_FAILURE ) {
02602 if ( elt != last_elt + 1 ) {
02603
02604
02605
02606 PrintRange(f,range_first,last_elt,&first);
02607 range_first = elt;
02608 }
02609 last_elt = elt;
02610 }
02611
02612 PrintRange(f,range_first,last_elt,&first);
02613 fprintf(f,"}");
02614 }
02615
02616
02617
02618
02619
02620
02621
02622
02623
02624 extern void
02625 BS_Print_dbg(BS *set)
02626 {
02627 BS_Print(set, stderr);
02628 fprintf(stderr, "\n");
02629 }
02630
02631
02632
02633
02634
02635
02636
02637
02638
02639
02640
02641 extern BOOL
02642 FBS_MemberP_Validate(
02643 BS *set,
02644 BS_ELT x
02645 )
02646 {
02647 Is_True(x >= 0,("FBS_Member called with negative element."));
02648 Is_True( bs_QBPW(x) < BS_word_count(set), ("FBS_Member called with out of bound element."));
02649 return (BS_byte(set,bs_QBPB(x)) & (bs_ONE << bs_RBPB(x))) != bs_ZEROS;
02650 }
02651
02652
02653
02654
02655
02656
02657
02658
02659
02660
02661
02662 void
02663 FBS_Union1D_Validate(
02664 BS *set,
02665 BS_ELT x
02666 )
02667 {
02668 BS_ELT minsize = bs_QBPW(x) + 1;
02669 Is_True(x >= 0,("FBS_Union1D called with negative element."));
02670 Is_True( minsize <= BS_word_count(set), ("FBS_Union1D called with out of bound element."));
02671 BS_byte(set,bs_QBPB(x)) |= bs_ONE << bs_RBPB(x);
02672 }
02673
02674
02675