Classes | Public Member Functions | Static Public Member Functions | Static Public Attributes | Protected Attributes | Static Protected Attributes

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 >:
chomp::homology::FixDimBitmap< Dim, twoPower > chomp::homology::SetOfFullCubes

List of all members.

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

Static Public Member Functions

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

Static Public Attributes

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

Protected Attributes

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

Static Protected Attributes

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

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 a power of 2 (8 => 256).

Definition at line 120 of file bincube.h.


Constructor & Destructor Documentation

template<int Dim, int twoPower>
chomp::homology::bincube< Dim, twoPower >::bincube (  )  [inline]
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 393 of file bincube.h.

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

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

template<int Dim, int twoPower>
chomp::homology::bincube< Dim, twoPower >::bincube ( const bincube< Dim, twoPower > &  b  )  [inline]
template<int Dim, int twoPower>
chomp::homology::bincube< Dim, twoPower >::~bincube (  )  [inline]

The destructor.

Definition at line 421 of file bincube.h.

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

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


Member Function Documentation

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 578 of file bincube.h.

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

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

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

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 588 of file bincube.h.

References chomp::homology::bincube< Dim, twoPower >::add(), and chomp::homology::bincube< Dim, twoPower >::coord2num().

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

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 816 of file bincube.h.

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

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

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 565 of file bincube.h.

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

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

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

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 572 of file bincube.h.

References chomp::homology::bincube< Dim, twoPower >::check(), and chomp::homology::bincube< Dim, twoPower >::coord2num().

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

template<int Dim, int twoPower>
void chomp::homology::bincube< Dim, twoPower >::clear (  )  [inline]

Makes the set empty.

Definition at line 888 of file bincube.h.

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

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

template<int Dim, int twoPower>
template<class intType >
int chomp::homology::bincube< Dim, twoPower >::coord2num ( const intType *  coord  )  [inline, static]

Determines the number of the cube with given coordinates.

Verifies the range of the coordinates and uses wrapping.

Definition at line 476 of file bincube.h.

References chomp::homology::bincube< Dim, twoPower >::width, and chomp::homology::bincube< Dim, twoPower >::wrapped().

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

{
        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 */

template<int Dim, int twoPower>
int chomp::homology::bincube< Dim, twoPower >::count (  )  const [inline]
template<int Dim, int twoPower>
int chomp::homology::bincube< Dim, twoPower >::dimension (  )  [inline, static]

Retrieve the dimension of the cube.

Definition at line 431 of file bincube.h.

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

template<int Dim, int twoPower>
void chomp::homology::bincube< Dim, twoPower >::dontwrap ( int  dir  )  [inline, static]

Turns off wrapping in the given direction.

Definition at line 450 of file bincube.h.

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

template<int Dim, int twoPower>
bool chomp::homology::bincube< Dim, twoPower >::empty (  )  const [inline]

Verifies whether the set is empty or not.

Definition at line 882 of file bincube.h.

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

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

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 823 of file bincube.h.

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

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

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

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 521 of file bincube.h.

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

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

{
        // 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 */

template<int Dim, int twoPower>
const char * chomp::homology::bincube< Dim, twoPower >::getbuffer (  )  const [inline]

Gets the binary buffer for reading only.

Definition at line 831 of file bincube.h.

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

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

template<int Dim, int twoPower>
int chomp::homology::bincube< Dim, twoPower >::getbufsize (  )  [inline, static]

Gets the buffer size.

Definition at line 843 of file bincube.h.

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

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

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 796 of file bincube.h.

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

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 805 of file bincube.h.

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

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

template<int Dim, int twoPower>
template<class intType >
const intType * chomp::homology::bincube< Dim, twoPower >::num2coord ( int  number  )  [inline, static]

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 513 of file bincube.h.

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

template<int Dim, int twoPower>
template<class intType >
intType * chomp::homology::bincube< Dim, twoPower >::num2coord ( int  number,
intType *  coord 
) [inline, static]

Determines the coordinates of the cube with given number.

Definition at line 501 of file bincube.h.

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

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

template<int Dim, int twoPower>
chomp::homology::bincube< Dim, twoPower >::operator const char * (  )  const [inline]

Gets the binary buffer for reading only.

Definition at line 837 of file bincube.h.

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

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

template<int Dim, int twoPower>
chomp::homology::bincube< Dim, twoPower >::operator int (  )  const [inline]

Definition at line 876 of file bincube.h.

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

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

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 413 of file bincube.h.

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

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

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 849 of file bincube.h.

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

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

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 604 of file bincube.h.

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

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

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 594 of file bincube.h.

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

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

template<int Dim, int twoPower>
void chomp::homology::bincube< Dim, twoPower >::wrap ( int  dir  )  [inline, static]

Turns on wrapping in the given direction.

Definition at line 443 of file bincube.h.

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

template<int Dim, int twoPower>
template<class intType >
intType chomp::homology::bincube< Dim, twoPower >::wrap ( intType  coord,
int  dir 
) [inline, static]

Wraps the coordinate in the given direction if necessary.

Definition at line 458 of file bincube.h.

References chomp::homology::bincube< Dim, twoPower >::width, and chomp::homology::bincube< Dim, twoPower >::wrapped().

{
        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 */

template<int Dim, int twoPower>
bool chomp::homology::bincube< Dim, twoPower >::wrapped ( int  dir  )  [inline, static]

Verifies whether the space is wrapped in the given direction.

Definition at line 437 of file bincube.h.

Referenced by chomp::homology::bincube< Dim, twoPower >::coord2num(), and chomp::homology::bincube< Dim, twoPower >::wrap().

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


Member Data Documentation

template<int Dim, int twoPower>
bool chomp::homology::bincube< Dim, twoPower >::allocated [protected]

Was the memory for the buffer allocated?

Definition at line 336 of file bincube.h.

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

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 198 of file bincube.h.

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

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 329 of file bincube.h.

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

template<int Dim, int twoPower>
const int chomp::homology::bincube< Dim, twoPower >::MaxDim = Dim [static]

Definition at line 141 of file bincube.h.

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

The mask for extracting one coordinate from the number.

Definition at line 345 of file bincube.h.

template<int Dim, int twoPower>
const int chomp::homology::bincube< Dim, twoPower >::width = 1 << twoPower [static, protected]

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

Definition at line 348 of file bincube.h.

Referenced by chomp::homology::bincube< Dim, twoPower >::coord2num(), and chomp::homology::bincube< Dim, twoPower >::wrap().

template<int Dim, int twoPower>
int chomp::homology::bincube< Dim, twoPower >::wrapping = 0 [static, protected]

Wrapping in each direction.

Definition at line 351 of file bincube.h.


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