chomp::homology::bincube< Dim, twoPower > Class Template Reference

A binary n-dimensional hypercube for storing cubes as bits. More...

#include <bincube.h>

Inheritance diagram for chomp::homology::bincube< Dim, twoPower >:

Classes
class	iterator
	The iterator of the set of cubes within a bitmap. More...
class	neighborhood_iterator
	The neighborhood of a cube. More...

Public Member Functions
	bincube ()
	The default constructor. More...
	bincube (char *buffer)
	The constructor to use a given memory buffer. More...
	bincube (const bincube< Dim, twoPower > &b)
	The copying constructor. More...
bincube< Dim, twoPower > &	operator= (const bincube< Dim, twoPower > &b)
	The assignment operator. More...
	~bincube ()
	The destructor. More...
int	findcube (int start=0) const
	Finds the first existing cube beginning at the given number. More...
iterator	begin ()
	Returns the iterator that points at the first cube in the set. More...
iterator	end ()
	Returns the iterator that points beyond the end of the set. More...
neighborhood_iterator	neighborhood_begin (int number) const
	Creates a neighborhood iterator for the specified cube and sets it at the first cube. More...
neighborhood_iterator	neighborhood_end (int number) const
	Creates a one-behind-the-end iterator for the given cube. More...
void	add (int number)
	Sets the bit corresponding to the given cube (by number). More...
template<class intType >
void	add (const intType *coord)
	Sets the bit corresponding to the given cube (by number). More...
bool	check (int number) const
	Checks if the given cube belongs to the set or not. More...
template<class intType >
bool	check (const intType *coord) const
	Checks if the given cube belongs to the set or not. More...
void	remove (int number)
	Clears the bit corresponding to the given cube (by number). More...
template<class intType >
void	remove (const intType *coord)
	Clears the bit corresponding to the given cube (by number). More...
const char *	getbuffer () const
	Gets the binary buffer for reading only. More...
	operator const char * () const
	Gets the binary buffer for reading only. More...
std::istream &	read (std::istream &in)
	Reads the binary buffer from an input stream. More...
int	count () const
	Get the number of cubes in the set. More...
	operator int () const
bool	empty () const
	Verifies whether the set is empty or not. More...
void	clear ()
	Makes the set empty. More...

Static Public Member Functions
static int	dimension ()
	Retrieves the dimension of the cube. More...
static int	getbufsize ()
	Gets the buffer size. More...
static bool	wrapped (int dir)
	Verifies whether the space is wrapped in the given direction. More...
static void	wrap (int dir)
	Turns on wrapping in the given direction. More...
static void	dontwrap (int dir)
	Turns off wrapping in the given direction. More...
template<class intType >
static intType	wrap (intType coord, int dir)
	Wraps the coordinate in the given direction if necessary. More...
template<class intType >
static int	coord2num (const intType *coord)
	Determines the number of the cube with given coordinates. More...
template<class intType >
static intType *	num2coord (int number, intType *coord)
	Determines the coordinates of the cube with given number. More...
template<class intType >
static const intType *	num2coord (int number)
	Determines the coordinates of the cube with given number. More...

Static Public Attributes
static const int	MaxDim = Dim
	The maximal possible dimension of a cube. More...
static const int	max_neighbors = Power<3,Dim>::value - 1
	The maximal possible number of neighbors of a cube. More...
static const int	maxcount = 1 << (Dim * twoPower)
	The maximal number of cubes that can be stored in the set. More...

Protected Attributes
char *	buf
	The memory for storing the hypercubes. More...
bool	allocated
	Was the memory for the buffer allocated? More...
int	cardinality
	The number of cubes in the set (or -1 if unknown) More...

Static Protected Attributes
static const int	bufsize = 1 << (Dim * twoPower - 3)
	The size of the buffer in bytes. More...
static const int	twoMask = ~0u >> (32 - twoPower)
	The mask for extracting one coordinate from the number. More...
static const int	width = 1 << twoPower
	The width of the set in each direction (in cubes). More...
static int	wrapping = 0
	Wrapping in each direction. More...

Detailed Description

template<int Dim, int twoPower>
class chomp::homology::bincube< Dim, twoPower >

A binary n-dimensional hypercube for storing cubes as bits.

The size of the hypercube is given as the power to which 2 is to be raised (e.g. 8 means the size of the side = 256).

Definition at line 120 of file bincube.h.

Constructor & Destructor Documentation

bincube() [1/3]

template<int Dim, int twoPower>

chomp::homology::bincube< Dim, twoPower >::bincube

inline

The default constructor.

Definition at line 385 of file bincube.h.

{
        buf = new char [bufsize];
        allocated = true;
        memset (buf, 0, bufsize);
        cardinality = 0;
        return;
} /* bincube::bincube */

bincube() [2/3]

template<int Dim, int twoPower>

chomp::homology::bincube< Dim, twoPower >::bincube ( char *  buffer )

inline

The constructor to use a given memory buffer.

This memory buffer will not be released with delete[].

Definition at line 395 of file bincube.h.

{
        buf = buffer;
        allocated = false;
        cardinality = -1;
        return;
} /* bincube::bincube */

bincube() [3/3]

template<int Dim, int twoPower>

chomp::homology::bincube< Dim, twoPower >::bincube ( const bincube< Dim, twoPower > &  b )

inline

The copying constructor.

Definition at line 404 of file bincube.h.

{
        buf = new char [bufsize];
        allocated = true;
        memcpy (buf, b. buf, bufsize);
        cardinality = b. cardinality;
        return;
} /* bincube::bincube */

~bincube()

template<int Dim, int twoPower>

chomp::homology::bincube< Dim, twoPower >::~bincube

inline

The destructor.

Definition at line 423 of file bincube.h.

{
        if (allocated)
                delete [] buf;
        return;
} /* bincube::~bincube */

Member Function Documentation

add() [1/2]

template<int Dim, int twoPower>

template<class intType >

void chomp::homology::bincube< Dim, twoPower >::add ( const intType *  coord )

inline

Sets the bit corresponding to the given cube (by number).

Note: The range of the coordinates is corrected if necessary.

Definition at line 590 of file bincube.h.

{
        return add (coord2num (coord));
} /* bincube::add */

add() [2/2]

template<int Dim, int twoPower>

void chomp::homology::bincube< Dim, twoPower >::add ( int  number )

inline

Sets the bit corresponding to the given cube (by number).

Warning: The range of the number is not verified.

Definition at line 580 of file bincube.h.

{
        if ((cardinality >= 0) && !check (number))
                ++ cardinality;
        buf [number >> 3] |= (char) (1 << (number & 7));
        return;
} /* bincube::add */

Referenced by chomp::homology::addneighbors().

begin()

template<int Dim, int twoPower>

bincube< Dim, twoPower >::iterator chomp::homology::bincube< Dim, twoPower >::begin

inline

Returns the iterator that points at the first cube in the set.

Definition at line 825 of file bincube.h.

{
        return iterator (this, findcube ());
} /* bincube::begin */

References chomp::homology::bincube< Dim, twoPower >::findcube().

Referenced by chomp::homology::reduceFullCubesAlg().

check() [1/2]

template<int Dim, int twoPower>

template<class intType >

bool chomp::homology::bincube< Dim, twoPower >::check ( const intType *  coord ) const

inline

Checks if the given cube belongs to the set or not.

Note: The range of the coordinates is corrected if necessary.

Definition at line 574 of file bincube.h.

{
        return check (coord2num (coord));
} /* bincube::check */

check() [2/2]

template<int Dim, int twoPower>

bool chomp::homology::bincube< Dim, twoPower >::check ( int  number ) const

inline

Checks if the given cube belongs to the set or not.

Warning: The range of the number is not verified.

Definition at line 567 of file bincube.h.

{
        return buf [number >> 3] & (1 << (number & 7));
} /* bincube::check */

Referenced by chomp::homology::NeighborsBdd< cubetype, settype >::check(), chomp::homology::Acyclic1d< SetT >::check(), chomp::homology::Acyclic2d< SetT >::check(), chomp::homology::Acyclic3d< SetT >::check(), and chomp::homology::bincube< Dim, twoPower >::neighborhood_iterator::operator++().

clear()

template<int Dim, int twoPower>

void chomp::homology::bincube< Dim, twoPower >::clear

inline

Makes the set empty.

Definition at line 897 of file bincube.h.

{
        memset (buf, 0, bufsize);
        cardinality = 0;
        return;
} /* bincube::clear */

References chomp::homology::bincube< Dim, twoPower >::buf, chomp::homology::bincube< Dim, twoPower >::bufsize, and chomp::homology::bincube< Dim, twoPower >::cardinality.

coord2num()

template<int Dim, int twoPower>

template<class intType >

int chomp::homology::bincube< Dim, twoPower >::coord2num ( const intType *  coord )

inlinestatic

Determines the number of the cube with given coordinates.

Verifies the range of the coordinates and uses wrapping.

Definition at line 478 of file bincube.h.

{
        int number = 0;
        for (int i = Dim - 1; i >= 0; -- i)
        {
                int c = coord [i];
                if (wrapped (i))
                {
                        // this is fast but can be very slow if the
                        // coordinates are far from the actual binary cube
                        while (c < 0)
                                c += width;
                        while (c >= width)
                                c -= width;
                }
                else if ((c < 0) || (c >= width))
                        throw SetOfFullCubes::OutOfRange ();
                number <<= twoPower;
                number |= c;
        }
        return number;
} /* bincube::coord2num */

Referenced by chomp::homology::bit2neighborAlg(), and chomp::homology::bincube< Dim, twoPower >::neighborhood_iterator::operator++().

count()

template<int Dim, int twoPower>

int chomp::homology::bincube< Dim, twoPower >::count

inline

Get the number of cubes in the set.

Definition at line 868 of file bincube.h.

{
        if (cardinality >= 0)
                return cardinality;
        char *byte = buf;
        char *end = byte + bufsize;
        int c = 0;
        while (byte != end)
        {
                c += bitcountbyte (*byte);
                ++ byte;
        }
        cardinality = c;
        return cardinality;
} /* bincube::count */

References chomp::homology::bitcountbyte(), chomp::homology::bincube< Dim, twoPower >::buf, chomp::homology::bincube< Dim, twoPower >::bufsize, chomp::homology::bincube< Dim, twoPower >::cardinality, and chomp::homology::bincube< Dim, twoPower >::end().

Referenced by chomp::homology::bincube< Dim, twoPower >::empty(), chomp::homology::bincube< Dim, twoPower >::operator int(), and chomp::homology::reduceFullCubesAlg().

dimension()

template<int Dim, int twoPower>

int chomp::homology::bincube< Dim, twoPower >::dimension

inlinestatic

Retrieves the dimension of the cube.

Definition at line 433 of file bincube.h.

{
        return Dim;
} /* bincube::dimension */

Referenced by chomp::homology::reduceFullCubes().

dontwrap()

template<int Dim, int twoPower>

void chomp::homology::bincube< Dim, twoPower >::dontwrap ( int  dir )

inlinestatic

Turns off wrapping in the given direction.

Definition at line 452 of file bincube.h.

{
        bincube<Dim,twoPower>::wrapping &= ~(1 << dir);
        return;
} /* bincube::dontwrap */

empty()

template<int Dim, int twoPower>

bool chomp::homology::bincube< Dim, twoPower >::empty

inline

Verifies whether the set is empty or not.

Definition at line 891 of file bincube.h.

{
        return !count ();
} /* bincube::empty */

References chomp::homology::bincube< Dim, twoPower >::count().

Referenced by chomp::homology::reduceFullCubesAlg().

end()

template<int Dim, int twoPower>

bincube< Dim, twoPower >::iterator chomp::homology::bincube< Dim, twoPower >::end

inline

Returns the iterator that points beyond the end of the set.

Definition at line 832 of file bincube.h.

{
        return iterator (this, maxcount);
} /* bincube::end */

References chomp::homology::bincube< Dim, twoPower >::maxcount.

Referenced by chomp::homology::addneighbors(), chomp::homology::bincube< Dim, twoPower >::count(), and chomp::homology::reduceFullCubesAlg().

findcube()

template<int Dim, int twoPower>

int chomp::homology::bincube< Dim, twoPower >::findcube ( int  start = 0 ) const

inline

Finds the first existing cube beginning at the given number.

The range of 'start' is not verified; must be >= 0, < maxcount. Returns the number of the cube found or maxcount if failed.

Definition at line 523 of file bincube.h.

{
        // determine the offset of the byte containing the cube
        int offset = start >> 3;
 
        // don't look for cubes outside the valid range
        if (offset >= bufsize)
                return maxcount;
 
        // look for a cube within this byte
        if (buf [offset])
        {
                int bitnumber = start & 7;
                while (bitnumber < 8)
                {
                        if (buf [offset] & (1 << bitnumber))
                                return (offset << 3) + bitnumber;
                        ++ bitnumber;
                }
        }
 
        // search for a non-zero byte
        while (1)
        {
                ++ offset;
                if (offset >= bufsize)
                        return maxcount;
                if (buf [offset])
                        break;
        }
 
        // retrieve the cube with the non-zero bit within this byte
        int bitnumber = 0;
        while (1)
        {
                if (buf [offset] & (1 << bitnumber))
                        return (offset << 3) + bitnumber;
                ++ bitnumber;
        }
} /* bincube::findcube */

Referenced by chomp::homology::bincube< Dim, twoPower >::begin(), and chomp::homology::bincube< Dim, twoPower >::iterator::operator++().

getbuffer()

template<int Dim, int twoPower>

const char * chomp::homology::bincube< Dim, twoPower >::getbuffer

inline

Gets the binary buffer for reading only.

Definition at line 840 of file bincube.h.

{
        return buf;
} /* bincube::getbuffer */

References chomp::homology::bincube< Dim, twoPower >::buf.

getbufsize()

template<int Dim, int twoPower>

int chomp::homology::bincube< Dim, twoPower >::getbufsize

inlinestatic

Gets the buffer size.

Definition at line 852 of file bincube.h.

{
        return bufsize;
} /* bincube::getbufsize */

References chomp::homology::bincube< Dim, twoPower >::bufsize.

Referenced by chomp::homology::operator<<().

neighborhood_begin()

template<int Dim, int twoPower>

bincube< Dim, twoPower >::neighborhood_iterator chomp::homology::bincube< Dim, twoPower >::neighborhood_begin ( int  number ) const

inline

Creates a neighborhood iterator for the specified cube and sets it at the first cube.

Definition at line 805 of file bincube.h.

{
        typename bincube<Dim,twoPower>::neighborhood_iterator iter
                (const_cast<bincube<Dim,twoPower> *> (this), n);
        return ++ iter;
} /* bincube::neighborhood_begin */

Referenced by chomp::homology::addneighbors().

neighborhood_end()

template<int Dim, int twoPower>

bincube< Dim, twoPower >::neighborhood_iterator chomp::homology::bincube< Dim, twoPower >::neighborhood_end ( int  number ) const

inline

Creates a one-behind-the-end iterator for the given cube.

Definition at line 814 of file bincube.h.

{
        return neighborhood_iterator
                (const_cast<bincube<Dim,twoPower> *> (this), n,
                max_neighbors);
} /* bincube::neighborhood_end */

References chomp::homology::bincube< Dim, twoPower >::max_neighbors.

Referenced by chomp::homology::addneighbors().

num2coord() [1/2]

template<int Dim, int twoPower>

template<class intType >

const intType * chomp::homology::bincube< Dim, twoPower >::num2coord ( int  number )

inlinestatic

Determines the coordinates of the cube with given number.

Returns 0 if this function is inavailable. One must use the other function in that case.

Definition at line 515 of file bincube.h.

{
        return 0;
} /* bincube::num2coord */

num2coord() [2/2]

template<int Dim, int twoPower>

template<class intType >

intType * chomp::homology::bincube< Dim, twoPower >::num2coord ( int  number, intType *  coord  )

inlinestatic

Determines the coordinates of the cube with given number.

Definition at line 503 of file bincube.h.

{
        for (int i = 0; i < Dim; ++ i)
        {
                coord [i] = number & bincube<Dim,twoPower>::twoMask;
                number >>= twoPower;
        }
        return coord;
} /* bincube::num2coord */

Referenced by chomp::homology::bit2neighborAlg(), chomp::homology::bincube< Dim, twoPower >::iterator::coord(), and chomp::homology::bincube< Dim, twoPower >::neighborhood_iterator::neighborhood_iterator().

operator const char *()

template<int Dim, int twoPower>

chomp::homology::bincube< Dim, twoPower >::operator const char *

inline

Gets the binary buffer for reading only.

Definition at line 846 of file bincube.h.

{
        return buf;
} /* bincube::operator const char * */

References chomp::homology::bincube< Dim, twoPower >::buf.

operator int()

template<int Dim, int twoPower>

chomp::homology::bincube< Dim, twoPower >::operator int

inline

Definition at line 885 of file bincube.h.

{
        return count ();
} /* bincube::operator int */

References chomp::homology::bincube< Dim, twoPower >::count().

operator=()

template<int Dim, int twoPower>

bincube< Dim, twoPower > & chomp::homology::bincube< Dim, twoPower >::operator= ( const bincube< Dim, twoPower > &  b )

inline

The assignment operator.

Definition at line 415 of file bincube.h.

{
        memcpy (buf, b. buf, bufsize);
        cardinality = b. cardinality;
        return *this;
} /* bincube::bincube */

read()

template<int Dim, int twoPower>

std::istream & chomp::homology::bincube< Dim, twoPower >::read ( std::istream &  in )

inline

Reads the binary buffer from an input stream.

Definition at line 858 of file bincube.h.

{
        in. read (buf, bufsize);
        cardinality = -1;
        return in;
} /* bincube::read */

References chomp::homology::bincube< Dim, twoPower >::buf, chomp::homology::bincube< Dim, twoPower >::bufsize, chomp::homology::bincube< Dim, twoPower >::cardinality, and chomp::homology::bincube< Dim, twoPower >::read().

Referenced by chomp::homology::operator>>(), and chomp::homology::bincube< Dim, twoPower >::read().

remove() [1/2]

template<int Dim, int twoPower>

template<class intType >

void chomp::homology::bincube< Dim, twoPower >::remove ( const intType *  coord )

inline

Clears the bit corresponding to the given cube (by number).

Note: The range of the coordinates is corrected if necessary.

Definition at line 606 of file bincube.h.

{
        return remove (coord2num (coord));
} /* bincube::remove */

remove() [2/2]

template<int Dim, int twoPower>

void chomp::homology::bincube< Dim, twoPower >::remove ( int  number )

inline

Clears the bit corresponding to the given cube (by number).

Warning: The range of the number is not verified.

Definition at line 596 of file bincube.h.

{
        if ((cardinality > 0) && check (number))
                -- cardinality;
        buf [number >> 3] &= (char) (~(1 << (number & 7)));
        return;
} /* bincube::remove */

Referenced by chomp::homology::reduceFullCubesAlg().

wrap() [1/2]

template<int Dim, int twoPower>

void chomp::homology::bincube< Dim, twoPower >::wrap ( int  dir )

inlinestatic

Turns on wrapping in the given direction.

Definition at line 445 of file bincube.h.

{
        bincube<Dim,twoPower>::wrapping |= (1 << dir);
        return;
} /* bincube::wrap */

wrap() [2/2]

template<int Dim, int twoPower>

template<class intType >

intType chomp::homology::bincube< Dim, twoPower >::wrap ( intType  coord, int  dir  )

inlinestatic

Wraps the coordinate in the given direction if necessary.

Definition at line 460 of file bincube.h.

{
        if (wrapped (dir))
        {
                // this is fast but can be very slow if the
                // coordinates are far from the actual binary cube
                while (coord < 0)
                        coord += width;
                while (coord >= width)
                        coord -= width;
        }
        return coord;
} /* bincube::wrap */

wrapped()

template<int Dim, int twoPower>

bool chomp::homology::bincube< Dim, twoPower >::wrapped ( int  dir )

inlinestatic

Verifies whether the space is wrapped in the given direction.

Definition at line 439 of file bincube.h.

{
        return bincube<Dim,twoPower>::wrapping & (1 << dir);
} /* bincube::wrapped */

Member Data Documentation

allocated

template<int Dim, int twoPower>

bool chomp::homology::bincube< Dim, twoPower >::allocated

protected

Was the memory for the buffer allocated?

Definition at line 338 of file bincube.h.

buf

template<int Dim, int twoPower>

char* chomp::homology::bincube< Dim, twoPower >::buf

protected

The memory for storing the hypercubes.

Definition at line 335 of file bincube.h.

Referenced by chomp::homology::bincube< Dim, twoPower >::clear(), chomp::homology::bincube< Dim, twoPower >::count(), chomp::homology::bincube< Dim, twoPower >::getbuffer(), chomp::homology::bincube< Dim, twoPower >::operator const char *(), and chomp::homology::bincube< Dim, twoPower >::read().

bufsize

template<int Dim, int twoPower>

const int chomp::homology::bincube< Dim, twoPower >::bufsize = 1 << (Dim * twoPower - 3)

staticprotected

The size of the buffer in bytes.

Definition at line 344 of file bincube.h.

Referenced by chomp::homology::bincube< Dim, twoPower >::clear(), chomp::homology::bincube< Dim, twoPower >::count(), chomp::homology::bincube< Dim, twoPower >::getbufsize(), and chomp::homology::bincube< Dim, twoPower >::read().

cardinality

template<int Dim, int twoPower>

int chomp::homology::bincube< Dim, twoPower >::cardinality

mutableprotected

The number of cubes in the set (or -1 if unknown)

Definition at line 341 of file bincube.h.

Referenced by chomp::homology::bincube< Dim, twoPower >::clear(), chomp::homology::bincube< Dim, twoPower >::count(), and chomp::homology::bincube< Dim, twoPower >::read().

max_neighbors

template<int Dim, int twoPower>

const int chomp::homology::bincube< Dim, twoPower >::max_neighbors = Power<3,Dim>::value - 1

static

The maximal possible number of neighbors of a cube.

Definition at line 200 of file bincube.h.

Referenced by chomp::homology::bincube< Dim, twoPower >::neighborhood_end().

maxcount

template<int Dim, int twoPower>

const int chomp::homology::bincube< Dim, twoPower >::maxcount = 1 << (Dim * twoPower)

static

The maximal number of cubes that can be stored in the set.

Definition at line 331 of file bincube.h.

Referenced by chomp::homology::bincube< Dim, twoPower >::end().

MaxDim

template<int Dim, int twoPower>

const int chomp::homology::bincube< Dim, twoPower >::MaxDim = Dim

static

The maximal possible dimension of a cube.

Definition at line 143 of file bincube.h.

twoMask

template<int Dim, int twoPower>

const int chomp::homology::bincube< Dim, twoPower >::twoMask = ~0u >> (32 - twoPower)

staticprotected

The mask for extracting one coordinate from the number.

Definition at line 347 of file bincube.h.

width

template<int Dim, int twoPower>

const int chomp::homology::bincube< Dim, twoPower >::width = 1 << twoPower

staticprotected

The width of the set in each direction (in cubes).

Definition at line 350 of file bincube.h.

wrapping

template<int Dim, int twoPower>

int chomp::homology::bincube< Dim, twoPower >::wrapping = 0

staticprotected

Wrapping in each direction.

Definition at line 353 of file bincube.h.

---

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

• chomp/cubes/bincube.h