Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
frechet::data::BitSet Class Reference

Detailed Description

A simple bit vector of fixed size.

Contrary to standard implementations (like std::bitset, or QBitArray), this implementation provides an iterator.

Author
Peter Schäfer

Definition at line 16 of file bitset.h.

#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...
 
BitSetoperator= (const BitSet &that)
 assigment operator More...
 
BitSetswap (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
 
BitSetoperator+= (int offset)
 assign true More...
 
BitSetoperator-= (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...
 

Constructor & Destructor Documentation

◆ BitSet() [1/3]

BitSet::BitSet ( )

default constructor; creates an empty set

Definition at line 11 of file bitset.cpp.

◆ BitSet() [2/3]

BitSet::BitSet ( int  asize)

constructor with size

Parameters
asizenumber of allocated bits; all bits are initialized to false.

Definition at line 13 of file bitset.cpp.

◆ BitSet() [3/3]

BitSet::BitSet ( const BitSet that)

copy constructor

Parameters
thatobjec to copy from

Definition at line 28 of file bitset.cpp.

◆ ~BitSet()

BitSet::~BitSet ( )

destructor, releases all data

Definition at line 33 of file bitset.cpp.

Member Function Documentation

◆ add()

void BitSet::add ( int  offset)

assign true

Parameters
offsetindex into bit set

Definition at line 77 of file bitset.cpp.

◆ add_lf()

void BitSet::add_lf ( int  offset)

lock-free add operator; not used and not tested!

Definition at line 89 of file bitset.cpp.

◆ begin()

BitSet::iterator BitSet::begin ( ) const
Returns
an iterator that points to the first set (true) bit

Definition at line 128 of file bitset.cpp.

◆ bitCount()

int BitSet::bitCount ( uint64_t  word)
staticprivate

compute number of set bits in a 64 bit word

Parameters
worda 64 bit word
Returns
number of set bits

Definition at line 329 of file bitset.cpp.

◆ clear()

void BitSet::clear ( )

assign false to all bits

Definition at line 67 of file bitset.cpp.

◆ compare_and_swap()

int64_t BitSet::compare_and_swap ( volatile int64_t *  value,
int64_t  old_value,
int64_t  update_value 
)
staticprivate

atomic compare-and-swap

Parameters
valuepointer to current value
old_valueexpected old value
update_valueupdate value
Returns
actual old 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.

◆ contains()

bool BitSet::contains ( int  offset) const
Parameters
offsetindex into bit set
Returns
true if the bit at 'offset' is true

Definition at line 71 of file bitset.cpp.

◆ copyBits()

void BitSet::copyBits ( const BitSet that)
private

copy data

Parameters
thatobject to copy from

Definition at line 130 of file bitset.cpp.

◆ count()

int BitSet::count ( ) const

This methods is expensive, as it scans the whole array.

Returns
number of set (true) bits

Definition at line 58 of file bitset.cpp.

◆ end()

iterator frechet::data::BitSet::end ( ) const
inline
Returns
an iterator that points one beyond the end of this BitSet. This iterator is invalid, but can be decremented.

Definition at line 167 of file bitset.h.

◆ first()

iterator frechet::data::BitSet::first ( ) const
inline
Returns
an iterator that points to the first set (true) bit

Definition at line 170 of file bitset.h.

◆ last()

iterator frechet::data::BitSet::last ( ) const
inline
Returns
an iterator that points to the last set (true) bit

Definition at line 172 of file bitset.h.

◆ next()

int BitSet::next ( int  index) const
private

find next index with a set (true) bit

Parameters
indexstart index

Definition at line 151 of file bitset.cpp.

◆ numberOfLeadingZeros()

int BitSet::numberOfLeadingZeros ( uint64_t  word)
staticprivate

compute number of leading zeros in a 64 bit word

Parameters
worda 64 bit word
Returns
number of leading zeros

Definition at line 321 of file bitset.cpp.

◆ numberOfTrailingZeros()

int BitSet::numberOfTrailingZeros ( uint64_t  word)
staticprivate

compute number of trailing zeros in a 64 bit word

Parameters
worda 64 bit word
Returns
number of trailing zeros

Definition at line 313 of file bitset.cpp.

◆ operator+=()

BitSet& frechet::data::BitSet::operator+= ( int  offset)
inline

assign true

Parameters
offsetindex into bit set
Returns
this object, after adding a bit

Definition at line 73 of file bitset.h.

◆ operator-=()

BitSet& frechet::data::BitSet::operator-= ( int  offset)
inline

assign false

Parameters
offsetindex into bit set
Returns
this object, after clearing a bit

Definition at line 77 of file bitset.h.

◆ operator=()

BitSet & BitSet::operator= ( const BitSet that)

assigment operator

Parameters
thatobject to copy from
Returns
this object, after assigning a copy

Definition at line 38 of file bitset.cpp.

◆ operator[]()

bool frechet::data::BitSet::operator[] ( int  offset) const
inline
Parameters
offsetindex into bit set
Returns
true if the bit at 'offset' is true

Definition at line 69 of file bitset.h.

◆ prev()

int BitSet::prev ( int  off) const
private

find previos index with a set (true) bit

Parameters
offstart index

Definition at line 174 of file bitset.cpp.

◆ remove()

void BitSet::remove ( int  offset)

assign false

Parameters
offsetindex into bit set

Definition at line 83 of file bitset.cpp.

◆ remove_lf()

void BitSet::remove_lf ( int  offset)

lock-free add operator; not used and not tested!

Definition at line 108 of file bitset.cpp.

◆ size()

int BitSet::size ( ) const
Returns
number of valid bits

Definition at line 56 of file bitset.cpp.

◆ stealBits()

void BitSet::stealBits ( BitSet &&  that)
private

steal data

Parameters
thatobject to copy from; is empty on return

Definition at line 144 of file bitset.cpp.

◆ swap()

BitSet & BitSet::swap ( BitSet that)

swap contents with other object

Parameters
thatobject to copy from
Returns
this object, after exchanging content with 'that'

Definition at line 44 of file bitset.cpp.

Member Data Documentation

◆ _size

int frechet::data::BitSet::_size
private

number of valid bits

Definition at line 19 of file bitset.h.

◆ bits

uint64_t* frechet::data::BitSet::bits
private

bit data

Definition at line 23 of file bitset.h.

◆ numWords

int frechet::data::BitSet::numWords
private

number of allocated words (1 word = 64 bits)

Definition at line 21 of file bitset.h.


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