A binary n-dimensional hypercube for storing cubes as bits. More...
#include <bincube.h>
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. |
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.
chomp::homology::bincube< Dim, twoPower >::bincube | ( | ) | [inline] |
The default constructor.
Definition at line 383 of file bincube.h.
References chomp::homology::bincube< Dim, twoPower >::allocated, chomp::homology::bincube< Dim, twoPower >::buf, chomp::homology::bincube< Dim, twoPower >::bufsize, and chomp::homology::bincube< Dim, twoPower >::cardinality.
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 */
chomp::homology::bincube< Dim, twoPower >::bincube | ( | const bincube< Dim, twoPower > & | b | ) | [inline] |
The copying constructor.
Definition at line 402 of file bincube.h.
References chomp::homology::bincube< Dim, twoPower >::allocated, chomp::homology::bincube< Dim, twoPower >::buf, chomp::homology::bincube< Dim, twoPower >::bufsize, and chomp::homology::bincube< Dim, twoPower >::cardinality.
{ buf = new char [bufsize]; allocated = true; memcpy (buf, b. buf, bufsize); cardinality = b. cardinality; return; } /* bincube::bincube */
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.
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 */
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().
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 */
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 */
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().
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 */
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 */
int chomp::homology::bincube< Dim, twoPower >::count | ( | ) | const [inline] |
Get the number of cubes in the set.
Definition at line 859 of file bincube.h.
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(), and chomp::homology::bincube< Dim, twoPower >::operator int().
{ 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 */
int chomp::homology::bincube< Dim, twoPower >::dimension | ( | ) | [inline, static] |
void chomp::homology::bincube< Dim, twoPower >::dontwrap | ( | int | dir | ) | [inline, static] |
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 */
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 */
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 */
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 */
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 */
bincube< Dim, twoPower >::neighborhood_iterator chomp::homology::bincube< Dim, twoPower >::neighborhood_begin | ( | int | number | ) | const [inline] |
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 */
const intType * chomp::homology::bincube< Dim, twoPower >::num2coord | ( | int | number | ) | [inline, static] |
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 */
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 * */
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 */
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 */
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 */
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 */
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 */
void chomp::homology::bincube< Dim, twoPower >::wrap | ( | int | dir | ) | [inline, static] |
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().
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 */
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().
char* chomp::homology::bincube< Dim, twoPower >::buf [protected] |
The memory for storing the hypercubes.
Definition at line 333 of file bincube.h.
Referenced by chomp::homology::bincube< Dim, twoPower >::add(), chomp::homology::bincube< Dim, twoPower >::bincube(), chomp::homology::bincube< Dim, twoPower >::check(), chomp::homology::bincube< Dim, twoPower >::clear(), chomp::homology::bincube< Dim, twoPower >::count(), chomp::homology::bincube< Dim, twoPower >::findcube(), chomp::homology::bincube< Dim, twoPower >::getbuffer(), chomp::homology::bincube< Dim, twoPower >::operator const char *(), chomp::homology::bincube< Dim, twoPower >::operator=(), chomp::homology::bincube< Dim, twoPower >::read(), chomp::homology::bincube< Dim, twoPower >::remove(), and chomp::homology::bincube< Dim, twoPower >::~bincube().
const int chomp::homology::bincube< Dim, twoPower >::bufsize = 1 << (Dim * twoPower - 3) [static, protected] |
The size of the buffer in bytes.
Definition at line 342 of file bincube.h.
Referenced by chomp::homology::bincube< Dim, twoPower >::bincube(), chomp::homology::bincube< Dim, twoPower >::clear(), chomp::homology::bincube< Dim, twoPower >::count(), chomp::homology::bincube< Dim, twoPower >::findcube(), chomp::homology::bincube< Dim, twoPower >::getbufsize(), chomp::homology::bincube< Dim, twoPower >::operator=(), and chomp::homology::bincube< Dim, twoPower >::read().
int chomp::homology::bincube< Dim, twoPower >::cardinality [mutable, protected] |
The number of cubes in the set (or -1 if unknown).
Definition at line 339 of file bincube.h.
Referenced by chomp::homology::bincube< Dim, twoPower >::add(), chomp::homology::bincube< Dim, twoPower >::bincube(), chomp::homology::bincube< Dim, twoPower >::clear(), chomp::homology::bincube< Dim, twoPower >::count(), chomp::homology::bincube< Dim, twoPower >::operator=(), chomp::homology::bincube< Dim, twoPower >::read(), and chomp::homology::bincube< Dim, twoPower >::remove().
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().
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().
const int chomp::homology::bincube< Dim, twoPower >::MaxDim = Dim [static] |
const int chomp::homology::bincube< Dim, twoPower >::twoMask = ~0u >> (32 - twoPower) [static, protected] |
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().
int chomp::homology::bincube< Dim, twoPower >::wrapping = 0 [static, protected] |