![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
A simple bit vector of fixed size.
Contrary to standard implementations (like std::bitset, or QBitArray), this implementation provides an iterator.
#include <bitset.h>
Classes | |
class | iterator |
an iterator over a BitSet More... | |
Public Member Functions | |
BitSet () | |
default constructor; creates an empty set More... | |
BitSet (int asize) | |
constructor with size More... | |
BitSet (const BitSet &that) | |
copy constructor More... | |
~BitSet () | |
destructor, releases all data More... | |
BitSet & | operator= (const BitSet &that) |
assigment operator More... | |
BitSet & | swap (BitSet &that) |
swap contents with other object More... | |
int | size () const |
int | count () const |
This methods is expensive, as it scans the whole array. More... | |
void | clear () |
assign false to all bits More... | |
bool | contains (int offset) const |
void | add (int offset) |
assign true More... | |
void | remove (int offset) |
assign false More... | |
bool | operator[] (int offset) const |
BitSet & | operator+= (int offset) |
assign true More... | |
BitSet & | operator-= (int offset) |
assign false More... | |
void | add_lf (int offset) |
lock-free add operator; not used and not tested! More... | |
void | remove_lf (int offset) |
lock-free add operator; not used and not tested! More... | |
iterator | begin () const |
iterator | end () const |
iterator | first () const |
iterator | last () const |
Private Member Functions | |
void | copyBits (const BitSet &that) |
copy data More... | |
void | stealBits (BitSet &&that) |
steal data More... | |
int | next (int index) const |
find next index with a set (true) bit More... | |
int | prev (int off) const |
find previos index with a set (true) bit More... | |
Static Private Member Functions | |
static int | numberOfTrailingZeros (uint64_t word) |
compute number of trailing zeros in a 64 bit word More... | |
static int | numberOfLeadingZeros (uint64_t word) |
compute number of leading zeros in a 64 bit word More... | |
static int | bitCount (uint64_t word) |
compute number of set bits in a 64 bit word More... | |
static int64_t | compare_and_swap (volatile int64_t *value, int64_t old_value, int64_t update_value) |
atomic compare-and-swap More... | |
Private Attributes | |
int | _size |
number of valid bits More... | |
int | numWords |
number of allocated words (1 word = 64 bits) More... | |
uint64_t * | bits |
bit data More... | |
BitSet::BitSet | ( | ) |
default constructor; creates an empty set
Definition at line 11 of file bitset.cpp.
BitSet::BitSet | ( | int | asize | ) |
constructor with size
asize | number of allocated bits; all bits are initialized to false. |
Definition at line 13 of file bitset.cpp.
BitSet::BitSet | ( | const BitSet & | that | ) |
BitSet::~BitSet | ( | ) |
destructor, releases all data
Definition at line 33 of file bitset.cpp.
void BitSet::add | ( | int | offset | ) |
void BitSet::add_lf | ( | int | offset | ) |
lock-free add operator; not used and not tested!
Definition at line 89 of file bitset.cpp.
BitSet::iterator BitSet::begin | ( | ) | const |
Definition at line 128 of file bitset.cpp.
|
staticprivate |
compute number of set bits in a 64 bit word
word | a 64 bit word |
Definition at line 329 of file bitset.cpp.
void BitSet::clear | ( | ) |
assign false to all bits
Definition at line 67 of file bitset.cpp.
|
staticprivate |
atomic compare-and-swap
value | pointer to current value |
old_value | expected old value |
update_value | update value |
Replaces current value with update value, if it is equal to the expected (old) value. If the current value is not equal to the expected value, do nothing and return the actual value.
Compare and update are performed atomically, i.e. without being interrupted by another thread.
Definition at line 298 of file bitset.cpp.
bool BitSet::contains | ( | int | offset | ) | const |
offset | index into bit set |
Definition at line 71 of file bitset.cpp.
|
private |
int BitSet::count | ( | ) | const |
This methods is expensive, as it scans the whole array.
Definition at line 58 of file bitset.cpp.
|
inline |
|
inline |
|
inline |
|
private |
find next index with a set (true) bit
index | start index |
Definition at line 151 of file bitset.cpp.
|
staticprivate |
compute number of leading zeros in a 64 bit word
word | a 64 bit word |
Definition at line 321 of file bitset.cpp.
|
staticprivate |
compute number of trailing zeros in a 64 bit word
word | a 64 bit word |
Definition at line 313 of file bitset.cpp.
|
inline |
|
inline |
assigment operator
that | object to copy from |
Definition at line 38 of file bitset.cpp.
|
inline |
|
private |
find previos index with a set (true) bit
off | start index |
Definition at line 174 of file bitset.cpp.
void BitSet::remove | ( | int | offset | ) |
void BitSet::remove_lf | ( | int | offset | ) |
lock-free add operator; not used and not tested!
Definition at line 108 of file bitset.cpp.
int BitSet::size | ( | ) | const |
Definition at line 56 of file bitset.cpp.
|
private |
steal data
that | object to copy from; is empty on return |
Definition at line 144 of file bitset.cpp.
swap contents with other object
that | object to copy from |
Definition at line 44 of file bitset.cpp.
|
private |
|
private |