third_party/cddlib/lib-src/setoper.c - RealtimeRoboticsGroup/test - Gitiles

 /* setoper.c:
  * A set operation library
  * created by Komei Fukuda, Nov.14, 1993
  * modified on December 5, 1994
    (set_card function replaced with a better code by David Bremner)
  * last modified on June 1, 2000
    (set_fwrite_compl(), set_groundsize added.  set_compl fixed.)
  */

 #include "setoper.h"

 #include <limits.h>
 #define SETBITS (sizeof(long) * CHAR_BIT)
 /* (Number of chars in a long) * (number of bits in a char) */

 /* Definitions for optimized set_card function
    by David Bremner bremner@cs.mcgill.ca
 */

 /* Caution!!!
    Bremner's technique depends on the assumption that CHAR_BIT == 8.
 */

 #define LUTBLOCKS(set) (((set[0]-1)/SETBITS+1)*(sizeof(long)/sizeof(set_card_lut_t)))

 static unsigned char set_card_lut[]={
 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,
 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,
 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,
 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,
 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,
 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,
 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,
 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};
 /* End of Definitions for optimized set_card */

 unsigned long set_blocks(long len)
 {
 	long blocks=1L;

 	if (len>0) blocks=((long)len-1)/SETBITS+2;
 	return blocks;
 }

 void set_initialize(set_type *setp, long length)
 /* Make a set with a given bit lengths  */
 {
 	long i,forlim1,len;

     if (length<=0) len=1;else len=length;
      /* if negative length is requested, it generates the shortest length */

 	forlim1=set_blocks(len);
 	*setp=(unsigned long *) calloc(forlim1, sizeof i);
 	(*setp)[0]=(unsigned long) len;  /* size of the ground set */
 	for (i=1; i<forlim1; i++)
 		(*setp)[i]=0U;
 }

 void set_free(set_type set)
 /* Free the space created with the set pointer set*/
 {
     free(set);
 }

 void set_emptyset(set_type set)
 /* Set set to be the emptyset  */
 {
 	long i,forlim;

 	forlim=set_blocks(set[0])-1;
 	for (i=1; i<=forlim; i++)
 		set[i]=0U;
 }

 void set_copy(set_type setcopy,set_type set)
 /* Copy the set set[] to setcopy[] with setcopy[] length */
 {
 	long i,forlim;

 	forlim=set_blocks(setcopy[0])-1;
 	for (i=1; i<=forlim; i++)
 		setcopy[i]=set[i];
 }

 void set_addelem(set_type set, long elem)
 /* add elem only if it is within the set[] range */
 {
 	long i,j;
 	unsigned long change;
 	unsigned long one=1U;

 	if (elem<=set[0])
 	{
 		i=(elem-1)/SETBITS+1;
 		j=(elem-1)%SETBITS;
 		change= one << j;  /* put 1 in jth position */
 		set[i]=set[i] | change;
 	}
 }

 void set_delelem(set_type set, long elem)
 /* delete elem only if it is within the set[] range */
 {
 	long  i,j;
 	unsigned long change;
 	unsigned long one=1U;

 	if (elem<=set[0])
 	{
 		i=(elem-1)/SETBITS+1;
 		j=(elem-1)%SETBITS;
 		change=one << j;  /* put 1 in jth position */
 		set[i]=(set[i] | change) ^ change;
 	}
 }

 void set_int(set_type set,set_type set1,set_type set2)
 /* Set intersection, assuming set1 and set2 have the same length as set */
 {
 	long  i,forlim;

 	forlim=set_blocks(set[0])-1;
 	for (i=1;i<=forlim;i++)
 		set[i]=(set1[i] & set2[i]);
 }

 void set_uni(set_type set,set_type set1,set_type set2)
 /* Set union,assuming set1 and set2 have the same length as set */
 {
 	long  i,forlim;

 	forlim=set_blocks(set[0])-1;
 	for (i=1;i<=forlim;i++)
 		set[i]=set1[i] | set2[i];
 }

 void set_diff(set_type set,set_type set1,set_type set2)
 /* Set difference se1/set2, assuming set1 and set2 have the same length as set */
 {
 	long  i,forlim;

 	forlim=set_blocks(set[0])-1;
 	for (i=1;i<=forlim;i++)
 		set[i]=set1[i] & (~set2[i]);
 }

 void set_compl(set_type set,set_type set1)
 /* set[] will be set to the complement of set1[] */
 {
 	long  i,j,l,forlim;
 	unsigned long change;
 	unsigned long one=1U;

 	forlim=set_blocks(set[0])-1;
 	for (i=1;i<=forlim;i++)
 		set[i]= ~set1[i];

 /* the following is necessary to remove 1's in the unused bits.
    Bremner's trick counts these bits as well.  (000601KF)
 */
 	l=(set[0]-1)%SETBITS; /* the position of the last elem in the last block */
     	for (j=l+1; j<=SETBITS-1; j++){
 		change=one << j;
 		set[forlim]=(set[forlim] | change) ^ change;
     	}
 }

 int set_subset(set_type set1,set_type set2)
 /* Set containment check, set1 <= set2 */
 {
 	int  yes=1;
 	long i,forlim;

 	forlim=set_blocks(set2[0])-1;
 	for (i=1;i<=forlim && yes;i++)
 		if ((set1[i] | set2[i])!=set2[i])
 			yes=0;
 	return yes;
 }

 int set_member(long elem, set_type set)
 /* Set membership check, elem in set */
 {
 	int  yes=0;
 	long  i,j;
 	unsigned long testset;
 	unsigned long one=1U;

 	if (elem<=set[0])
 	{
 		i=(elem-1)/SETBITS+1;
 		j=(elem-1)%SETBITS;
 		testset=set[i] | (one<<j);   /* add elem to set[i] */
 		if (testset==set[i])
 			yes=1;
 	}
 	return yes;
 }

 /*set cardinality, modified by David Bremner bremner@cs.mcgill.ca
    to optimize for speed.*/
 long set_card(set_type set)
 {
   unsigned long block;
   long car=0;
   set_card_lut_t *p;

   p=(set_card_lut_t *)&set[1];
   for (block=0; block< LUTBLOCKS(set);block++) {
     car+=set_card_lut[p[block]];
   }
   return car;
 }

 /* old safe cardinality code
 long set_card(set_type set)
 {
 	long elem,car=0;

 	for (elem=1; elem<=set[0]; elem++) {
 		if (set_member(elem,set)) car++;
     }
 	return car;
 }
 */

 long set_groundsize(set_type set)
 {
 	return set[0];
 }

 void set_write(set_type set)
 {
 	long elem;

 	for (elem=1;elem<=set[0];elem++)
 	{
 		if (set_member(elem,set))
 			printf("%ld ",elem);
 	}
 	printf("\n");
 }

 void set_fwrite(FILE *f,set_type set)
 {
 	long elem;

 	for (elem=1;elem<=set[0];elem++)
 	{
 		if (set_member(elem,set))
 			fprintf(f,"%ld ",elem);
 	}
 	fprintf(f,"\n");
 }

 void set_fwrite_compl(FILE *f,set_type set)
 {
 	long elem;

 	for (elem=1;elem<=set[0];elem++)
 	{
 		if (!set_member(elem,set))
 			fprintf(f,"%ld ",elem);
 	}
 	fprintf(f,"\n");
 }

 void set_binwrite(set_type set)
 {
 	int i,j;
 	long forlim;
 	unsigned long e1,e2;

 	printf("max element = %ld,\n",set[0]);
 	forlim=set_blocks(set[0])-1;
 	for (i=forlim;i>=1;i--)
 	{
 		e1=e2=set[i];
 		for (j=SETBITS-1;j>=0;j--)
 		{
 			e1=(e1>>j);
 			printf("%1ld",e1);
 			e1=e2-(e1<<j);
 			e2=e1;
 		}
 		printf(" ");
 	}
 	printf("\n");
 }


 void set_fbinwrite(FILE *f,set_type set)
 {
 	int i,j;
 	long forlim;
 	long e1,e2;

 	printf("max element = %ld,\n",set[0]);
 	forlim=set_blocks(set[0])-1;
 	for (i=forlim;i>=1;i--)
 	{
 		e1=e2=set[i];
 		for (j=SETBITS-1;j>=0;j--)
 		{
 			e1=(e1>>j);
 			fprintf(f,"%1ld",e1);
 			e1=e2-(e1<<j);
 			e2=e1;
 		}
 		fprintf(f," ");
 	}
 	fprintf(f,"\n");
 }

 /* End of the library:  setoper.c  */
	/* setoper.c:
	* A set operation library
	* created by Komei Fukuda, Nov.14, 1993
	* modified on December 5, 1994
	(set_card function replaced with a better code by David Bremner)
	* last modified on June 1, 2000
	(set_fwrite_compl(), set_groundsize added. set_compl fixed.)
	*/

	#include "setoper.h"

	#include <limits.h>
	#define SETBITS (sizeof(long) * CHAR_BIT)
	/* (Number of chars in a long) * (number of bits in a char) */

	/* Definitions for optimized set_card function
	by David Bremner bremner@cs.mcgill.ca
	*/

	/* Caution!!!
	Bremner's technique depends on the assumption that CHAR_BIT == 8.
	*/

	#define LUTBLOCKS(set) (((set[0]-1)/SETBITS+1)*(sizeof(long)/sizeof(set_card_lut_t)))

	static unsigned char set_card_lut[]={
	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,
	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,
	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,
	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,
	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,
	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,
	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,
	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};
	/* End of Definitions for optimized set_card */

	unsigned long set_blocks(long len)
	{
	long blocks=1L;

	if (len>0) blocks=((long)len-1)/SETBITS+2;
	return blocks;
	}

	void set_initialize(set_type *setp, long length)
	/* Make a set with a given bit lengths */
	{
	long i,forlim1,len;

	if (length<=0) len=1;else len=length;
	/* if negative length is requested, it generates the shortest length */

	forlim1=set_blocks(len);
	setp=(unsigned long ) calloc(forlim1, sizeof i);
	(setp)[0]=(unsigned long) len; / size of the ground set */
	for (i=1; i<forlim1; i++)
	(*setp)[i]=0U;
	}

	void set_free(set_type set)
	/* Free the space created with the set pointer set*/
	{
	free(set);
	}

	void set_emptyset(set_type set)
	/* Set set to be the emptyset */
	{
	long i,forlim;

	forlim=set_blocks(set[0])-1;
	for (i=1; i<=forlim; i++)
	set[i]=0U;
	}

	void set_copy(set_type setcopy,set_type set)
	/* Copy the set set[] to setcopy[] with setcopy[] length */
	{
	long i,forlim;

	forlim=set_blocks(setcopy[0])-1;
	for (i=1; i<=forlim; i++)
	setcopy[i]=set[i];
	}

	void set_addelem(set_type set, long elem)
	/* add elem only if it is within the set[] range */
	{
	long i,j;
	unsigned long change;
	unsigned long one=1U;

	if (elem<=set[0])
	{
	i=(elem-1)/SETBITS+1;
	j=(elem-1)%SETBITS;
	change= one << j; /* put 1 in jth position */
	set[i]=set[i] \| change;
	}
	}

	void set_delelem(set_type set, long elem)
	/* delete elem only if it is within the set[] range */
	{
	long i,j;
	unsigned long change;
	unsigned long one=1U;

	if (elem<=set[0])
	{
	i=(elem-1)/SETBITS+1;
	j=(elem-1)%SETBITS;
	change=one << j; /* put 1 in jth position */
	set[i]=(set[i] \| change) ^ change;
	}
	}

	void set_int(set_type set,set_type set1,set_type set2)
	/* Set intersection, assuming set1 and set2 have the same length as set */
	{
	long i,forlim;

	forlim=set_blocks(set[0])-1;
	for (i=1;i<=forlim;i++)
	set[i]=(set1[i] & set2[i]);
	}

	void set_uni(set_type set,set_type set1,set_type set2)
	/* Set union,assuming set1 and set2 have the same length as set */
	{
	long i,forlim;

	forlim=set_blocks(set[0])-1;
	for (i=1;i<=forlim;i++)
	set[i]=set1[i] \| set2[i];
	}

	void set_diff(set_type set,set_type set1,set_type set2)
	/* Set difference se1/set2, assuming set1 and set2 have the same length as set */
	{
	long i,forlim;

	forlim=set_blocks(set[0])-1;
	for (i=1;i<=forlim;i++)
	set[i]=set1[i] & (~set2[i]);
	}

	void set_compl(set_type set,set_type set1)
	/* set[] will be set to the complement of set1[] */
	{
	long i,j,l,forlim;
	unsigned long change;
	unsigned long one=1U;

	forlim=set_blocks(set[0])-1;
	for (i=1;i<=forlim;i++)
	set[i]= ~set1[i];

	/* the following is necessary to remove 1's in the unused bits.
	Bremner's trick counts these bits as well. (000601KF)
	*/
	l=(set[0]-1)%SETBITS; /* the position of the last elem in the last block */
	for (j=l+1; j<=SETBITS-1; j++){
	change=one << j;
	set[forlim]=(set[forlim] \| change) ^ change;
	}
	}

	int set_subset(set_type set1,set_type set2)
	/* Set containment check, set1 <= set2 */
	{
	int yes=1;
	long i,forlim;

	forlim=set_blocks(set2[0])-1;
	for (i=1;i<=forlim && yes;i++)
	if ((set1[i] \| set2[i])!=set2[i])
	yes=0;
	return yes;
	}

	int set_member(long elem, set_type set)
	/* Set membership check, elem in set */
	{
	int yes=0;
	long i,j;
	unsigned long testset;
	unsigned long one=1U;

	if (elem<=set[0])
	{
	i=(elem-1)/SETBITS+1;
	j=(elem-1)%SETBITS;
	testset=set[i] \| (one<<j); /* add elem to set[i] */
	if (testset==set[i])
	yes=1;
	}
	return yes;
	}

	/*set cardinality, modified by David Bremner bremner@cs.mcgill.ca
	to optimize for speed.*/
	long set_card(set_type set)
	{
	unsigned long block;
	long car=0;
	set_card_lut_t *p;

	p=(set_card_lut_t *)&set[1];
	for (block=0; block< LUTBLOCKS(set);block++) {
	car+=set_card_lut[p[block]];
	}
	return car;
	}

	/* old safe cardinality code
	long set_card(set_type set)
	{
	long elem,car=0;

	for (elem=1; elem<=set[0]; elem++) {
	if (set_member(elem,set)) car++;
	}
	return car;
	}
	*/

	long set_groundsize(set_type set)
	{
	return set[0];
	}

	void set_write(set_type set)
	{
	long elem;

	for (elem=1;elem<=set[0];elem++)
	{
	if (set_member(elem,set))
	printf("%ld ",elem);
	}
	printf("\n");
	}

	void set_fwrite(FILE *f,set_type set)
	{
	long elem;

	for (elem=1;elem<=set[0];elem++)
	{
	if (set_member(elem,set))
	fprintf(f,"%ld ",elem);
	}
	fprintf(f,"\n");
	}

	void set_fwrite_compl(FILE *f,set_type set)
	{
	long elem;

	for (elem=1;elem<=set[0];elem++)
	{
	if (!set_member(elem,set))
	fprintf(f,"%ld ",elem);
	}
	fprintf(f,"\n");
	}

	void set_binwrite(set_type set)
	{
	int i,j;
	long forlim;
	unsigned long e1,e2;

	printf("max element = %ld,\n",set[0]);
	forlim=set_blocks(set[0])-1;
	for (i=forlim;i>=1;i--)
	{
	e1=e2=set[i];
	for (j=SETBITS-1;j>=0;j--)
	{
	e1=(e1>>j);
	printf("%1ld",e1);
	e1=e2-(e1<<j);
	e2=e1;
	}
	printf(" ");
	}
	printf("\n");
	}


	void set_fbinwrite(FILE *f,set_type set)
	{
	int i,j;
	long forlim;
	long e1,e2;

	printf("max element = %ld,\n",set[0]);
	forlim=set_blocks(set[0])-1;
	for (i=forlim;i>=1;i--)
	{
	e1=e2=set[i];
	for (j=SETBITS-1;j>=0;j--)
	{
	e1=(e1>>j);
	fprintf(f,"%1ld",e1);
	e1=e2-(e1<<j);
	e2=e1;
	}
	fprintf(f," ");
	}
	fprintf(f,"\n");
	}

	/* End of the library: setoper.c */