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] |
1.7.1