haskell-igraph-0.8.5: igraph/include/cliquer/set.h
/*
* This file contains the set handling routines.
*
* Copyright (C) 2002 Sampo Niskanen, Patric Östergård.
* Licensed under the GNU GPL, read the file LICENSE for details.
*/
#ifndef CLIQUER_SET_H
#define CLIQUER_SET_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include "misc.h"
/*
* Sets are arrays of setelement's (typically unsigned long int's) with
* representative bits for each value they can contain. The values
* are numbered 0,...,n-1.
*/
/*** Variable types and constants. ***/
/*
* If setelement hasn't been declared:
* - use "unsigned long int" as setelement
* - try to deduce size from ULONG_MAX
*/
#ifndef ELEMENTSIZE
typedef unsigned long int setelement;
# if (ULONG_MAX == 65535)
# define ELEMENTSIZE 16
# elif (ULONG_MAX == 4294967295)
# define ELEMENTSIZE 32
# else
# define ELEMENTSIZE 64
# endif
#endif /* !ELEMENTSIZE */
typedef setelement * set_t;
/*** Counting amount of 1 bits in a setelement ***/
/* Array for amount of 1 bits in a byte. */
static int set_bit_count[256] = {
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 };
/* The following macros assume that all higher bits are 0.
* They may in some cases be useful also on with other ELEMENTSIZE's,
* so we define them all. */
#define SET_ELEMENT_BIT_COUNT_8(a) (set_bit_count[(a)])
#define SET_ELEMENT_BIT_COUNT_16(a) (set_bit_count[(a)>>8] + \
set_bit_count[(a)&0xFF])
#define SET_ELEMENT_BIT_COUNT_32(a) (set_bit_count[(a)>>24] + \
set_bit_count[((a)>>16)&0xFF] + \
set_bit_count[((a)>>8)&0xFF] + \
set_bit_count[(a)&0xFF])
#define SET_ELEMENT_BIT_COUNT_64(a) (set_bit_count[(a)>>56] + \
set_bit_count[((a)>>48)&0xFF] + \
set_bit_count[((a)>>40)&0xFF] + \
set_bit_count[((a)>>32)&0xFF] + \
set_bit_count[((a)>>24)&0xFF] + \
set_bit_count[((a)>>16)&0xFF] + \
set_bit_count[((a)>>8)&0xFF] + \
set_bit_count[(a)&0xFF])
#if (ELEMENTSIZE==64)
# define SET_ELEMENT_BIT_COUNT(a) SET_ELEMENT_BIT_COUNT_64(a)
# define FULL_ELEMENT ((setelement)0xFFFFFFFFFFFFFFFF)
#elif (ELEMENTSIZE==32)
# define SET_ELEMENT_BIT_COUNT(a) SET_ELEMENT_BIT_COUNT_32(a)
# define FULL_ELEMENT ((setelement)0xFFFFFFFF)
#elif (ELEMENTSIZE==16)
# define SET_ELEMENT_BIT_COUNT(a) SET_ELEMENT_BIT_COUNT_16(a)
# define FULL_ELEMENT ((setelement)0xFFFF)
#else
# error "SET_ELEMENT_BIT_COUNT(a) not defined for current ELEMENTSIZE"
#endif
/*** Macros and functions ***/
/*
* Gives a value with bit x (counting from lsb up) set.
*
* Making this as a table might speed up things on some machines
* (though on most modern machines it's faster to shift instead of
* using memory). Making it a macro makes it easy to change.
*/
#define SET_BIT_MASK(x) ((setelement)1<<(x))
/* Set element handling macros */
#define SET_ELEMENT_INTERSECT(a,b) ((a)&(b))
#define SET_ELEMENT_UNION(a,b) ((a)|(b))
#define SET_ELEMENT_DIFFERENCE(a,b) ((a)&(~(b)))
#define SET_ELEMENT_CONTAINS(e,v) ((e)&SET_BIT_MASK(v))
/* Set handling macros */
#define SET_ADD_ELEMENT(s,a) \
((s)[(a)/ELEMENTSIZE] |= SET_BIT_MASK((a)%ELEMENTSIZE))
#define SET_DEL_ELEMENT(s,a) \
((s)[(a)/ELEMENTSIZE] &= ~SET_BIT_MASK((a)%ELEMENTSIZE))
#define SET_CONTAINS_FAST(s,a) (SET_ELEMENT_CONTAINS((s)[(a)/ELEMENTSIZE], \
(a)%ELEMENTSIZE))
#define SET_CONTAINS(s,a) (((a)<SET_MAX_SIZE(s))?SET_CONTAINS_FAST(s,a):FALSE)
/* Sets can hold values between 0,...,SET_MAX_SIZE(s)-1 */
#define SET_MAX_SIZE(s) ((s)[-1])
/* Sets consist of an array of SET_ARRAY_LENGTH(s) setelements */
#define SET_ARRAY_LENGTH(s) (((s)[-1]+ELEMENTSIZE-1)/ELEMENTSIZE)
/*
* set_new()
*
* Create a new set that can hold values in the range 0,...,size-1.
*/
UNUSED_FUNCTION
static set_t set_new(int size) {
int n;
set_t s;
ASSERT(size>0);
n=(size/ELEMENTSIZE+1)+1;
s=calloc(n,sizeof(setelement));
s[0]=size;
return &(s[1]);
}
/*
* set_free()
*
* Free the memory associated with set s.
*/
UNUSED_FUNCTION INLINE
static void set_free(set_t s) {
ASSERT(s!=NULL);
free(&(s[-1]));
}
/*
* set_resize()
*
* Resizes set s to given size. If the size is less than SET_MAX_SIZE(s),
* the last elements are dropped.
*
* Returns a pointer to the new set.
*/
UNUSED_FUNCTION INLINE
static set_t set_resize(set_t s, int size) {
int n;
ASSERT(size>0);
n=(size/ELEMENTSIZE+1);
s=((setelement *)realloc(s-1,(n+1)*sizeof(setelement)))+1;
if (n>SET_ARRAY_LENGTH(s))
memset(s+SET_ARRAY_LENGTH(s),0,
(n-SET_ARRAY_LENGTH(s))*sizeof(setelement));
if (size < SET_MAX_SIZE(s))
s[(size-1)/ELEMENTSIZE] &= (FULL_ELEMENT >>
(ELEMENTSIZE-size%ELEMENTSIZE));
s[-1]=size;
return s;
}
/*
* set_size()
*
* Returns the number of elements in set s.
*/
UNUSED_FUNCTION INLINE
static int set_size(set_t s) {
int count=0;
setelement *c;
for (c=s; c < s+SET_ARRAY_LENGTH(s); c++)
count+=SET_ELEMENT_BIT_COUNT(*c);
return count;
}
/*
* set_duplicate()
*
* Returns a newly allocated duplicate of set s.
*/
UNUSED_FUNCTION INLINE
static set_t set_duplicate(set_t s) {
set_t new;
new=set_new(SET_MAX_SIZE(s));
memcpy(new,s,SET_ARRAY_LENGTH(s)*sizeof(setelement));
return new;
}
/*
* set_copy()
*
* Copies set src to dest. If dest is NULL, is equal to set_duplicate.
* If dest smaller than src, it is freed and a new set of the same size as
* src is returned.
*/
UNUSED_FUNCTION INLINE
static set_t set_copy(set_t dest,set_t src) {
if (dest==NULL)
return set_duplicate(src);
if (SET_MAX_SIZE(dest)<SET_MAX_SIZE(src)) {
set_free(dest);
return set_duplicate(src);
}
memcpy(dest,src,SET_ARRAY_LENGTH(src)*sizeof(setelement));
memset(dest+SET_ARRAY_LENGTH(src),0,((SET_ARRAY_LENGTH(dest) -
SET_ARRAY_LENGTH(src)) *
sizeof(setelement)));
return dest;
}
/*
* set_empty()
*
* Removes all elements from the set s.
*/
UNUSED_FUNCTION INLINE
static void set_empty(set_t s) {
memset(s,0,SET_ARRAY_LENGTH(s)*sizeof(setelement));
return;
}
/*
* set_intersection()
*
* Store the intersection of sets a and b into res. If res is NULL,
* a new set is created and the result is written to it. If res is
* smaller than the larger one of a and b, it is freed and a new set
* is created and the result is returned.
*
* Returns either res or a new set that has been allocated in its stead.
*
* Note: res may not be a or b.
*/
UNUSED_FUNCTION INLINE
static set_t set_intersection(set_t res,set_t a,set_t b) {
int i,max;
if (res==NULL) {
res = set_new(MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b)));
} else if (SET_MAX_SIZE(res) < MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b))) {
set_free(res);
res = set_new(MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b)));
} else {
set_empty(res);
}
max=MIN(SET_ARRAY_LENGTH(a),SET_ARRAY_LENGTH(b));
for (i=0; i<max; i++) {
res[i]=SET_ELEMENT_INTERSECT(a[i],b[i]);
}
return res;
}
/*
* set_union()
*
* Store the union of sets a and b into res. If res is NULL, a new set
* is created and the result is written to it. If res is smaller than
* the larger one of a and b, it is freed and a new set is created and
* the result is returned.
*
* Returns either res or a new set that has been allocated in its stead.
*
* Note: res may not be a or b.
*/
UNUSED_FUNCTION INLINE
static set_t set_union(set_t res,set_t a,set_t b) {
int i,max;
if (res==NULL) {
res = set_new(MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b)));
} else if (SET_MAX_SIZE(res) < MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b))) {
set_free(res);
res = set_new(MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b)));
} else {
set_empty(res);
}
max=MAX(SET_ARRAY_LENGTH(a),SET_ARRAY_LENGTH(b));
for (i=0; i<max; i++) {
res[i]=SET_ELEMENT_UNION(a[i],b[i]);
}
return res;
}
/*
* set_return_next()
*
* Returns the smallest value in set s which is greater than n, or -1 if
* such a value does not exist.
*
* Can be used to iterate through all values of s:
*
* int i=-1;
* while ((i=set_return_next(s,i))>=0) {
* // i is in set s
* }
*/
UNUSED_FUNCTION INLINE
static int set_return_next(set_t s, int n) {
if (n<0)
n=0;
else
n++;
if (n >= SET_MAX_SIZE(s))
return -1;
while (n%ELEMENTSIZE) {
if (SET_CONTAINS(s,n))
return n;
n++;
if (n >= SET_MAX_SIZE(s))
return -1;
}
while (s[n/ELEMENTSIZE]==0) {
n+=ELEMENTSIZE;
if (n >= SET_MAX_SIZE(s))
return -1;
}
while (!SET_CONTAINS(s,n)) {
n++;
if (n >= SET_MAX_SIZE(s))
return -1;
}
return n;
}
/*
* set_print()
*
* Prints the size and contents of set s to stdout.
* Mainly useful for debugging purposes and trivial output.
*/
/*
UNUSED_FUNCTION
static void set_print(set_t s) {
int i;
printf("size=%d(max %d)",set_size(s),(int)SET_MAX_SIZE(s));
for (i=0; i<SET_MAX_SIZE(s); i++)
if (SET_CONTAINS(s,i))
printf(" %d",i);
printf("\n");
return;
}
*/
#endif /* !CLIQUER_SET_H */