chomp::homology::BitSets Class Reference

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. More...
	BitSets (const BitSets &s)
	Copy constructor. More...
BitSets &	operator= (const BitSets &s)
	Assignment operator. More...
	~BitSets ()
	Destructor. More...
void	add (int_t n, int_t e)
	Adds an element to the given set. More...
void	remove (int_t n, int_t e)
	Removes an element from the given set. More...
bool	check (int_t n, int_t e) const
	Checks if an element belongs to the given set. More...
void	addset (int_t n, int_t m)
	Adds the entire set 'm' to the set 'n'. More...
int_t	get (int_t n, int_t start=0) const
	Retrieves an element >= 'start' in the given set. More...

Private Member Functions
int_t	arraySize ()
	Computes the size of the memory array for storing the bits. More...

Private Attributes
int_t	nsets
	The number of sets. More...
int_t	nelem
	The maximal number of elements in each set. More...
int_t	nunits
	The number of array entries used for each set. More...
unsigned long *	bits
	The memory buffer for storing the bits. More...

Static Private Attributes
static const int_t	longBits = sizeof (long) * 8
static const int_t	longBitMask = longBits - 1
static const int_t	longBitShift = (sizeof (long) == 8) ? 6 : 5

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 57 of file bitsets.h.

Constructor & Destructor Documentation

BitSets() [1/2]

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. Both numbers must be positive.

Definition at line 123 of file bitsets.h.

                                                  :
        nsets (_nsets), nelem (_nelem),
        nunits ((_nelem + (sizeof (unsigned long) << 3) - 1) /
        (sizeof (unsigned long) << 3)), bits (0)
{
        int_t size = arraySize ();
        bits = new unsigned long [size];
        for (int_t i = 0; i < size; ++ i)
                bits [i] = 0;
        return;
} /* BitSets::BitSets */

References arraySize(), and bits.

BitSets() [2/2]

chomp::homology::BitSets::BitSets ( const BitSets &  s )

inline

Copy constructor.

Definition at line 135 of file bitsets.h.

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

References arraySize(), and bits.

~BitSets()

chomp::homology::BitSets::~BitSets ( )

inline

Destructor.

Definition at line 160 of file bitsets.h.

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

References bits.

Member Function Documentation

add()

void chomp::homology::BitSets::add ( int_t  n, int_t  e  )

inline

Adds an element to the given set.

Definition at line 166 of file bitsets.h.

{
//      sbug << "Add " << e << " to " << n << ".\n";
        unsigned long *buf = bits + n * nunits;
        buf [e >> longBitShift] |= (1ul << (e & longBitMask));
        return;
} /* BitSets::add */

References bits, longBitMask, longBitShift, and nunits.

addset()

void chomp::homology::BitSets::addset ( int_t  n, int_t  m  )

inline

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

Definition at line 187 of file bitsets.h.

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

References bits, and nunits.

arraySize()

int_t chomp::homology::BitSets::arraySize ( )

inlineprivate

Computes the size of the memory array for storing the bits.

Definition at line 115 of file bitsets.h.

{
        long size = static_cast<long> (nsets) * static_cast<long> (nunits);
        if (static_cast<long> (static_cast<int_t> (size)) != size)
                throw "Too large BitSets requested.";
        return static_cast<int_t> (size);
} /* BitSets::arraySize */

References nsets, and nunits.

Referenced by BitSets(), and operator=().

check()

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 181 of file bitsets.h.

{
        unsigned long *buf = bits + n * nunits;
        return !!(buf [e >> longBitShift] & (1ul << (e & longBitMask)));
} /* BitSets::check */

References bits, longBitMask, longBitShift, and nunits.

get()

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 196 of file bitsets.h.

{
        if (start >= nelem)
                return -1;
        unsigned long *buf = bits + n * nunits;
        int_t offset = start >> longBitShift;
        int bit = start & longBitMask;
        if (buf [offset] & (~0ul << bit))
        {
                for (; bit < longBits; ++ bit)
                {
                        if (buf [offset] & (1ul << bit))
                                return (offset << longBitShift) + bit;
                }
                throw "Wrong bit number in BitSets.";
        }
        for (++ offset; offset < nunits; ++ offset)
        {
                if (!buf [offset])
                        continue;
                for (int bit = 0; bit < longBits; ++ bit)
                {
                        if (buf [offset] & (1ul << bit))
                                return (offset << longBitShift) + bit;
                }
                throw "False bit in BitSets.";
        }
        return -1;
} /* BitSets::get */

References bits, longBitMask, longBits, longBitShift, nelem, and nunits.

operator=()

BitSets & chomp::homology::BitSets::operator= ( const BitSets &  s )

inline

Assignment operator.

Definition at line 145 of file bitsets.h.

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

References arraySize(), bits, nelem, nsets, and nunits.

remove()

void chomp::homology::BitSets::remove ( int_t  n, int_t  e  )

inline

Removes an element from the given set.

Definition at line 174 of file bitsets.h.

{
        unsigned long *buf = bits + n * nunits;
        buf [e >> longBitShift] &= ~(1ul << (e & longBitMask));
        return;
} /* BitSets::remove */

References bits, longBitMask, longBitShift, and nunits.

Member Data Documentation

bits

unsigned long* chomp::homology::BitSets::bits

private

The memory buffer for storing the bits.

Definition at line 106 of file bitsets.h.

Referenced by add(), addset(), BitSets(), check(), get(), operator=(), remove(), and ~BitSets().

longBitMask

const int_t chomp::homology::BitSets::longBitMask = longBits - 1

staticprivate

Definition at line 60 of file bitsets.h.

Referenced by add(), check(), get(), and remove().

longBits

const int_t chomp::homology::BitSets::longBits = sizeof (long) * 8

staticprivate

Definition at line 59 of file bitsets.h.

Referenced by get().

longBitShift

const int_t chomp::homology::BitSets::longBitShift = (sizeof (long) == 8) ? 6 : 5

staticprivate

Definition at line 61 of file bitsets.h.

Referenced by add(), check(), get(), and remove().

nelem

int_t chomp::homology::BitSets::nelem

private

The maximal number of elements in each set.

Definition at line 100 of file bitsets.h.

Referenced by get(), and operator=().

nsets

int_t chomp::homology::BitSets::nsets

private

The number of sets.

Definition at line 97 of file bitsets.h.

Referenced by arraySize(), and operator=().

nunits

int_t chomp::homology::BitSets::nunits

private

The number of array entries used for each set.

Definition at line 103 of file bitsets.h.

Referenced by add(), addset(), arraySize(), check(), get(), operator=(), and remove().

---

The documentation for this class was generated from the following file:

• chomp/struct/bitsets.h