Sandia Home Sandia Home
Main Page | Publications | Downloads | Configuration | Running the Code | Solver Parameters | FAQ | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

setoper.c

Go to the documentation of this file.
00001 
00043 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00044 
00045 /* setoper.c:
00046  * A set operation library 
00047  * created by Komei Fukuda, Nov.14, 1993
00048  * modified on December 5, 1994 
00049    (set_card function replaced with a better code by David Bremner) 
00050  * last modified on June 1, 2000 
00051    (set_fwrite_compl(), set_groundsize added.  set_compl fixed.)
00052  */
00053  
00054 #include "setoper.h"
00055 
00056 #include <limits.h>
00057 #define SETBITS (sizeof(long) * CHAR_BIT)
00058 /* (Number of chars in a long) * (number of bits in a char) */
00059 
00060 /* Definitions for optimized set_card function 
00061    by David Bremner bremner@cs.mcgill.ca  
00062 */
00063 
00064 /* Caution!!!
00065    Bremner's technique depends on the assumption that CHAR_BIT == 8.
00066 */
00067 
00068 #define LUTBLOCKS(set) (((set[0]-1)/SETBITS+1)*(sizeof(long)/sizeof(set_card_lut_t)))
00069 
00070 static unsigned char set_card_lut[]={
00071 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
00072 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
00073 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
00074 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
00075 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
00076 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
00077 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
00078 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};
00079 /* End of Definitions for optimized set_card */
00080 
00081 unsigned long set_blocks(long len)
00082 {
00083         long blocks=1L;
00084         
00085         if (len>0) blocks=((long)len-1)/SETBITS+2;
00086         return blocks;
00087 }
00088 
00089 void set_initialize(set_type *setp, long length)
00090 /* Make a set with a given bit lengths  */
00091 {
00092         long i,forlim1,len;
00093         
00094     if (length<=0) len=1;else len=length; 
00095      /* if negative length is requested, it generates the shortest length */
00096 
00097         forlim1=set_blocks(len);
00098         *setp=(unsigned long *) calloc(forlim1, sizeof i);
00099         (*setp)[0]=(unsigned long) len;  /* size of the ground set */
00100         for (i=1; i<forlim1; i++)
00101                 (*setp)[i]=0U;
00102 }
00103 
00104 void set_free(set_type set)
00105 /* Free the space created with the set pointer set*/
00106 {
00107     free(set);
00108 }
00109 
00110 void set_emptyset(set_type set)
00111 /* Set set to be the emptyset  */
00112 {
00113         long i,forlim;
00114         
00115         forlim=set_blocks(set[0])-1;
00116         for (i=1; i<=forlim; i++)
00117                 set[i]=0U;
00118 }
00119 
00120 void set_copy(set_type setcopy,set_type set)
00121 /* Copy the set set[] to setcopy[] with setcopy[] length */
00122 {
00123         long i,forlim;
00124 
00125         forlim=set_blocks(setcopy[0])-1;
00126         for (i=1; i<=forlim; i++)
00127                 setcopy[i]=set[i];
00128 }
00129 
00130 void set_addelem(set_type set, long elem)
00131 /* add elem only if it is within the set[] range */
00132 {
00133         long i,j;
00134         unsigned long change;
00135         unsigned long one=1U;
00136         
00137         if (elem<=set[0])    
00138         {
00139                 i=(elem-1)/SETBITS+1;
00140                 j=(elem-1)%SETBITS;
00141                 change= one << j;  /* put 1 in jth position */
00142                 set[i]=set[i] | change;
00143         }
00144 }
00145 
00146 void set_delelem(set_type set, long elem)
00147 /* delete elem only if it is within the set[] range */
00148 {
00149         long  i,j;
00150         unsigned long change;
00151         unsigned long one=1U;    
00152         
00153         if (elem<=set[0])
00154         {
00155                 i=(elem-1)/SETBITS+1;
00156                 j=(elem-1)%SETBITS;
00157                 change=one << j;  /* put 1 in jth position */
00158                 set[i]=(set[i] | change) ^ change;
00159         }
00160 }
00161 
00162 void set_int(set_type set,set_type set1,set_type set2)
00163 /* Set intersection, assuming set1 and set2 have the same length as set */
00164 {
00165         long  i,forlim;
00166         
00167         forlim=set_blocks(set[0])-1;
00168         for (i=1;i<=forlim;i++)
00169                 set[i]=(set1[i] & set2[i]);
00170 }
00171 
00172 void set_uni(set_type set,set_type set1,set_type set2)
00173 /* Set union,assuming set1 and set2 have the same length as set */
00174 {
00175         long  i,forlim;
00176 
00177         forlim=set_blocks(set[0])-1;    
00178         for (i=1;i<=forlim;i++)
00179                 set[i]=set1[i] | set2[i];
00180 }
00181 
00182 void set_diff(set_type set,set_type set1,set_type set2)
00183 /* Set difference se1/set2, assuming set1 and set2 have the same length as set */
00184 {
00185         long  i,forlim;
00186 
00187         forlim=set_blocks(set[0])-1;    
00188         for (i=1;i<=forlim;i++)
00189                 set[i]=set1[i] & (~set2[i]);
00190 }
00191 
00192 void set_compl(set_type set,set_type set1)
00193 /* set[] will be set to the complement of set1[] */
00194 {
00195         long  i,j,l,forlim;
00196         unsigned long change;
00197         unsigned long one=1U;    
00198 
00199         forlim=set_blocks(set[0])-1;    
00200         for (i=1;i<=forlim;i++)
00201                 set[i]= ~set1[i];
00202 
00203 /* the following is necessary to remove 1's in the unused bits.
00204    Bremner's trick counts these bits as well.  (000601KF)
00205 */
00206         l=(set[0]-1)%SETBITS; /* the position of the last elem in the last block */
00207         for (j=l+1; j<=SETBITS-1; j++){
00208                 change=one << j;
00209                 set[forlim]=(set[forlim] | change) ^ change;
00210         }
00211 }
00212 
00213 int set_subset(set_type set1,set_type set2)
00214 /* Set containment check, set1 <= set2 */
00215 {
00216         int  yes=1;
00217         long i,forlim;
00218         
00219         forlim=set_blocks(set2[0])-1;
00220         for (i=1;i<=forlim && yes;i++)
00221                 if ((set1[i] | set2[i])!=set2[i])
00222                         yes=0;
00223         return yes;
00224 }
00225 
00226 int set_member(long elem, set_type set)
00227 /* Set membership check, elem in set */
00228 {
00229         int  yes=0;
00230         long  i,j;
00231         unsigned long testset;
00232         unsigned long one=1U;    
00233         
00234         if (elem<=set[0])
00235         {
00236                 i=(elem-1)/SETBITS+1;
00237                 j=(elem-1)%SETBITS;
00238                 testset=set[i] | (one<<j);   /* add elem to set[i] */
00239                 if (testset==set[i])
00240                         yes=1;
00241         }
00242         return yes;
00243 }
00244 
00245 /*set cardinality, modified by David Bremner bremner@cs.mcgill.ca
00246    to optimize for speed.*/
00247 long set_card(set_type set)
00248 {
00249   unsigned long block;
00250   long car=0;
00251   set_card_lut_t *p;
00252   
00253   p=(set_card_lut_t *)&set[1];
00254   for (block=0; block< LUTBLOCKS(set);block++) {
00255     car+=set_card_lut[p[block]];
00256   }
00257   return car;
00258 }
00259 
00260 /* old safe cardinality code
00261 long set_card(set_type set)
00262 {
00263         long elem,car=0;
00264         
00265         for (elem=1; elem<=set[0]; elem++) {
00266                 if (set_member(elem,set)) car++;
00267     }
00268         return car;
00269 }
00270 */
00271 
00272 long set_groundsize(set_type set)
00273 {
00274         return set[0];
00275 }
00276 
00277 void set_write(set_type set)
00278 {
00279         long elem;
00280         
00281         for (elem=1;elem<=set[0];elem++)
00282         {
00283                 if (set_member(elem,set))
00284                         printf("%ld ",elem);
00285         }
00286         printf("\n");
00287 }
00288 
00289 void set_fwrite(FILE *f,set_type set)
00290 {
00291         long elem;
00292         
00293         for (elem=1;elem<=set[0];elem++)
00294         {
00295                 if (set_member(elem,set))
00296                         fprintf(f,"%ld ",elem);
00297         }
00298         fprintf(f,"\n");
00299 }
00300 
00301 void set_fwrite_compl(FILE *f,set_type set)
00302 {
00303         long elem;
00304         
00305         for (elem=1;elem<=set[0];elem++)
00306         {
00307                 if (!set_member(elem,set))
00308                         fprintf(f,"%ld ",elem);
00309         }
00310         fprintf(f,"\n");
00311 }
00312 
00313 void set_binwrite(set_type set)
00314 {
00315         int i,j;
00316         long forlim;
00317         unsigned long e1,e2;
00318         
00319         printf("max element = %ld,\n",set[0]);
00320         forlim=set_blocks(set[0])-1;
00321         for (i=forlim;i>=1;i--)
00322         {
00323                 e1=e2=set[i];
00324                 for (j=SETBITS-1;j>=0;j--)
00325                 {
00326                         e1=(e1>>j);
00327                         printf("%1ld",e1);
00328                         e1=e2-(e1<<j);
00329                         e2=e1;
00330                 }
00331                 printf(" ");
00332         }
00333         printf("\n");
00334 }
00335 
00336 
00337 void set_fbinwrite(FILE *f,set_type set)
00338 {
00339         int i,j;
00340         long forlim;
00341         long e1,e2;
00342         
00343         printf("max element = %ld,\n",set[0]);
00344         forlim=set_blocks(set[0])-1;
00345         for (i=forlim;i>=1;i--)
00346         {
00347                 e1=e2=set[i];
00348                 for (j=SETBITS-1;j>=0;j--)
00349                 {
00350                         e1=(e1>>j);
00351                         fprintf(f,"%1ld",e1);
00352                         e1=e2-(e1<<j);
00353                         e2=e1;
00354                 }
00355                 fprintf(f," ");
00356         }
00357         fprintf(f,"\n");
00358 }
00359 
00360 /* End of the library:  setoper.c  */
00361 
00362 #endif

 

© Sandia Corporation | Site Contact | Privacy and Security

Generated on Fri Feb 16 10:33:35 2007 for APPSPACK 5.0.1 by doxygen 1.3.9.1 written by Dimitri van Heesch, © 1997-2002