This class uses bit representation to store many small sets. More...

#include <bitsets.h>

Public Member Functions
	BitSets (int_t _nsets, int_t _nelem)
	Constructor of a family of empty sets.
	BitSets (const BitSets &s)
	Copy constructor.
BitSets &	operator= (const BitSets &s)
	Assignment operator.
	~BitSets ()
	Destructor.
void	add (int_t n, int_t e)
	Adds an element to the given set.
void	remove (int_t n, int_t e)
	Removes an element from the given set.
bool	check (int_t n, int_t e) const
	Checks if an element belongs to the given set.
void	addset (int_t n, int_t m)
	Adds the entire set 'm' to the set 'n'.
int_t	get (int_t n, int_t start=0) const
	Retrieves an element >= 'start' in the given set.
Private Attributes
int_t	nsets
	The number of sets.
int_t	nelem
	The maximal number of elements in each set.
int_t	nbytes
	The number of bytes used for each set.
unsigned char *	bits
	The memory buffer for storing the bits.

Detailed Description

This class uses bit representation to store many small sets.

Each of the sets can contain integer numbers from 0 to the limit specified in the constructor. The number of sets must also be given in the constructor. A contiguous chunk of memory is used to store the bits that represent the sets. This class is not fool-proof, so use it carefully. Minimal interface, sorry.

Definition at line 58 of file bitsets.h.

Constructor & Destructor Documentation

chomp::homology::BitSets::BitSets	(	int_t	_nsets,
		int_t	_nelem
	)			`[inline]`

Constructor of a family of empty sets.

The number of the sets and the maximal number of elements in each set must be provided at initialization.

Definition at line 108 of file bitsets.h.

References bits, nbytes, and nsets.

                                                  :
        nsets (_nsets), nelem (_nelem), nbytes ((_nelem + 7) >> 3), bits (0)
{
        int_t size = nsets * nbytes;
        bits = new unsigned char [size];
        for (int_t i = 0; i < size; ++ i)
                bits [i] = 0;
        return;
} /* BitSets::BitSets */

chomp::homology::BitSets::BitSets ( const BitSets & s ) [inline]

Copy constructor.

Definition at line 118 of file bitsets.h.

References bits, nbytes, and nsets.

                                        :
        nsets (s. nsets), nelem (s. nelem), nbytes (s. nbytes), bits (0)
{
        int_t size = nsets * nbytes;
        bits = new unsigned char [size];
        for (int_t i = 0; i < size; ++ i)
                bits [i] = s. bits [i];
        return;
} /* BitSets::BitSets */

chomp::homology::BitSets::~BitSets ( ) [inline]

Destructor.

Definition at line 141 of file bitsets.h.

References bits.

{
        delete [] bits;
        return;
} /* BitSets::~BitSets */

Member Function Documentation

void chomp::homology::BitSets::add	(	int_t	n,
		int_t	e
	)			`[inline]`

Adds an element to the given set.

Definition at line 147 of file bitsets.h.

References bits, and nbytes.

{
//      sbug << "Add " << e << " to " << n << ".\n";
        unsigned char *buf = bits + n * nbytes;
        buf [e >> 3] |= (unsigned char) (0x01 << (e & 0x07));
        return;
} /* BitSets::add */

void chomp::homology::BitSets::addset	(	int_t	n,
		int_t	m
	)			`[inline]`

Adds the entire set 'm' to the set 'n'.

Definition at line 168 of file bitsets.h.

References bits, and nbytes.

{
        unsigned char *nbuf = bits + n * nbytes;
        unsigned char *mbuf = bits + m * nbytes;
        for (int_t i = 0; i < nbytes; ++ i)
                *(nbuf ++) |= *(mbuf ++);
        return;
} /* BitSets::addset */

bool chomp::homology::BitSets::check	(	int_t	n,
		int_t	e
	)			const `[inline]`

Checks if an element belongs to the given set.

Definition at line 162 of file bitsets.h.

References bits, and nbytes.

{
        unsigned char *buf = bits + n * nbytes;
        return !!(buf [e >> 3] & (0x01 << (e & 0x07)));
} /* BitSets::check */

int_t chomp::homology::BitSets::get	(	int_t	n,
		int_t	start = `0`
	)			const `[inline]`

Retrieves an element >= 'start' in the given set.

Returns -1 if none.

Definition at line 177 of file bitsets.h.

References bits, nbytes, and nelem.

{
        if (start >= nelem)
                return -1;
        unsigned char *buf = bits + n * nbytes;
        int_t offset = start >> 3;
        int bit = start & 0x07;
        if (buf [offset] & (0xFF << bit))
        {
                for (; bit < 8; ++ bit)
                {
                        if (buf [offset] & (0x01 << bit))
                                return (offset << 3) + bit;
                }
                throw "Wrong bit number in BitSets.";
        }
        for (++ offset; offset < nbytes; ++ offset)
        {
                if (!buf [offset])
                        continue;
                for (int bit = 0; bit < 8; ++ bit)
                {
                        if (buf [offset] & (0x01 << bit))
                                return (offset << 3) + bit;
                }
                throw "False bit in BitSets.";
        }
        return -1;
} /* BitSets::get */

BitSets & chomp::homology::BitSets::operator= ( const BitSets & s ) [inline]

Assignment operator.

Definition at line 128 of file bitsets.h.

References bits, nbytes, nelem, and nsets.

{
        delete [] bits;
        nsets = s. nsets;
        nelem = s. nelem;
        nbytes = s. nbytes;
        int_t size = nsets * nbytes;
        bits = new unsigned char [size];
        for (int_t i = 0; i < size; ++ i)
                bits [i] = s. bits [i];
        return *this;
} /* BitSets::operator = */

void chomp::homology::BitSets::remove	(	int_t	n,
		int_t	e
	)			`[inline]`

Removes an element from the given set.

Definition at line 155 of file bitsets.h.

References bits, and nbytes.

{
        unsigned char *buf = bits + n * nbytes;
        buf [e >> 3] &= (unsigned char) ~(0x01 << (e & 0x07));
        return;
} /* BitSets::remove */