atlas  0.6
Classes | Public Types | Public Member Functions | Private Attributes | Static Private Attributes | List of all members
atlas::bitmap::BitMap Class Reference

Container of a large (more than twice the machine word size) set of bits. More...

#include <bitmap.h>


class  iterator
 Traverses the set bits of a BitMap. More...

Public Types

typedef unsigned long value_type
typedef value_typereference
typedef const value_typeconst_reference
typedef value_typepointer
typedef const value_typeconst_pointer
typedef ptrdiff_t difference_type
typedef unsigned long size_type
typedef iterator const_iterator

Public Member Functions

iterator begin () const
iterator end () const
 returns the past-the-end iterator for the bitmap. More...
 BitMap ()
 BitMap (unsigned long n)
 Constructs a zero-initialized bitmap with a capacity of n bits. More...
 BitMap (const BitMap &b)
 Copy constructor. More...
template<typename I >
 BitMap (unsigned long n, const I &first, const I &last)
template<typename U >
 BitMap (unsigned long n, const std::vector< U > &v)
template<typename I , typename J >
 BitMap (const I &first, const I &last, const J &fsub, const J &lsub)
 Set of offsets into [first,last[ of values (also) found in [fsub,lsub[. More...
BitMapoperator= (const BitMap &)
unsigned long capacity () const
size_type size () const
bool operator< (const BitMap &b) const
bool operator== (const BitMap &b) const
bool operator!= (const BitMap &b) const
bool empty () const
bool full () const
bool isMember (unsigned long n) const
bool contains (const BitMap &b) const
bool disjoint (const BitMap &b) const
unsigned long n_th (unsigned long n) const
 Value at index |n| if viewed as list of |unsigned long| values. More...
unsigned long position (unsigned long n) const
 Number of values |<n| present (set) in the bitmap. More...
unsigned long front () const
bool back_up (unsigned long &n) const
unsigned long range (unsigned long first, unsigned long number) const
BitMap operator& (const BitMap &other) const
BitMap operator| (const BitMap &other) const
BitMap operator^ (const BitMap &other) const
BitMapoperator~ ()
bool operator&= (const BitMap &)
BitMapoperator|= (const BitMap &)
BitMapoperator^= (const BitMap &)
BitMapandnot (const BitMap &b)
BitMapoperator>>= (unsigned long delta)
BitMapoperator<<= (unsigned long delta)
void insert (unsigned long n)
void remove (unsigned long n)
void set_to (unsigned long n, bool b)
void set_mod2 (unsigned long n, unsigned long v)
void flip (unsigned long n)
void fill ()
void reset ()
void fill (size_t start, size_t stop)
 Sets all the bits in positions |i| with |start<=i<stop|. More...
void clear (size_t start, size_t stop)
 Sets all the bits in positions |i| with |start<=i<stop|. More...
template<typename I >
void insert (I, I)
void set_capacity (unsigned long n)
void extend_capacity (bool b)
void setRange (unsigned long start, unsigned long amount, unsigned long source)
void swap (BitMap &)

Private Attributes

size_t d_capacity
std::vector< unsigned long > d_map

Static Private Attributes

static unsigned long posBits = constants::posBits
static unsigned long baseBits = constants::baseBits
static unsigned long baseShift = constants::baseShift

Detailed Description

Container of a large (more than twice the machine word size) set of bits.

From the point of view of a user of the class, a BitMap should be seen as a container of unsigned long, not bits: these unsigned longs are the addresses of the set bits. When the class is used for example to flag the noncompact roots in a set of roots, it is most convenient to think of it as containing the numbers of the noncompact roots (on a fixed list of all roots). The class obeys the semantics of a Forward Container (from the C++ standard library). Its "size" as a container is the number of unsigned long that it "contains"; that is, the number of set bits in the bitmap.

The basic data is in d_map, a vector of unsigned long integers. Each of these integers is a "chunk" (of size longBits, presumably the machine word length) of the bit map. The capacity (in bits) of the BitMap is d_capacity; the size of the vector d_map is d_capacity/longBits (plus one if there is a remainder in the division).

We wish to provide bit-address access to this map; for this purpose we use the reference trick from vector<bool>. Also we wish to define an iterator class, which traverses the set bits of the bitmap; so that for instance, b.begin() would be a reference to the first set bit. Dereferencing the iterator yields its bit-address.

Member Typedef Documentation

typedef unsigned long atlas::bitmap::BitMap::size_type
typedef unsigned long atlas::bitmap::BitMap::value_type

type for a component of the vector d_map holding the BitMap

Constructor & Destructor Documentation

atlas::bitmap::BitMap::BitMap ( )
atlas::bitmap::BitMap::BitMap ( unsigned long  n)

Constructs a zero-initialized bitmap with a capacity of n bits.

Note that the size of the vector |d_map| exceeds |n >> baseShift| by one, unless |longBits| exactly divides |n|.

atlas::bitmap::BitMap::BitMap ( const BitMap b)

Copy constructor.

template<typename I >
atlas::bitmap::BitMap::BitMap ( unsigned long  n,
const I &  first,
const I &  last 
template<typename U >
atlas::bitmap::BitMap::BitMap ( unsigned long  n,
const std::vector< U > &  v 
template<typename I , typename J >
atlas::bitmap::BitMap::BitMap ( const I &  first,
const I &  last,
const J &  fsub,
const J &  lsub 

Set of offsets into [first,last[ of values (also) found in [fsub,lsub[.

In this constructor template we assume that I and J are iterator types with the same value_type. The idea is that [first,last[ is an ordered range, for which we can call lower_bound. Then we construct the bitmap which flags the elements from [fsub,lsub[ (not necessarily assumed ordered or in range; I should be random-access, but J can basically be any input iterator.) It is assumed of course that the elements from [fsub,lsub[ will be found in [first,last[.

Member Function Documentation

BitMap & atlas::bitmap::BitMap::andnot ( const BitMap b)

Synopsis: takes the current bitmap into its set-difference with |b|, i.e., removes from our bitmap any elements appearing in |b|; the latter should not exceed the size of the current bitmap (but may be smaller). Return whether any bits remain in the result.

bool atlas::bitmap::BitMap::back_up ( unsigned long &  n) const

Synopsis: decrements |n| until it points to a member of the bitset, or if none is found returns |false| (in which case |n| is unchanged)

BitMap::iterator atlas::bitmap::BitMap::begin ( ) const

******* range bounds

Returns an iterator pointing to the first set bit in the bitmap.

If the bitset is empty, this is will be equal to |end()|.

unsigned long atlas::bitmap::BitMap::capacity ( ) const

Number of bits in use in the bitmap. This is the capacity of the BitMap as a standard library container, not d_map.size(), which is approximately longBits times smaller.

void atlas::bitmap::BitMap::clear ( size_t  start,
size_t  stop 

Sets all the bits in positions |i| with |start<=i<stop|.

bool atlas::bitmap::BitMap::contains ( const BitMap b) const
bool atlas::bitmap::BitMap::disjoint ( const BitMap b) const
bool atlas::bitmap::BitMap::empty ( ) const

Tells whether the bitmap is empty. Thanks to our convention of zeroing unused bits, it is enough to check whether all the components of d_map are zero.

BitMap::iterator atlas::bitmap::BitMap::end ( ) const

returns the past-the-end iterator for the bitmap.

This is only needed to allow using these iterators in genereric algorithms which typically do |for (iterator it=x.begin(), it!=x.end(); ++it)|. In code that knows which kind of iterator this is, using |it()| as second clause is to be preferred.

Note that only the middle argument |d_capacity| is of any importance, since the only thing one can meaningfully do with end() is test for (in)equality. The operator |++| below does not in fact advance to |d_chunk==d_map.end()|!

void atlas::bitmap::BitMap::extend_capacity ( bool  b)
void atlas::bitmap::BitMap::fill ( )

Synopsis: sets all the bits in the bitmap.

As usual we have to be careful to leave the unused bits at the end to zero.

void atlas::bitmap::BitMap::fill ( size_t  start,
size_t  stop 

Sets all the bits in positions |i| with |start<=i<stop|.

void atlas::bitmap::BitMap::flip ( unsigned long  n)
unsigned long atlas::bitmap::BitMap::front ( ) const

Synopsis: returns the address of the first member (set bit) of the bitmap, or past-the-end indicator |d_capacity| if there is no such.

bool atlas::bitmap::BitMap::full ( ) const

Tells whether the bitmap is full. This means that all blocks are full, except maybe for the last one where we have to look only at the significant part.

void atlas::bitmap::BitMap::insert ( unsigned long  n)

Set the bit at position n (that is, inserts the value |n| into the set); this makes |isMember(n)| hold.

template<typename I >
void atlas::bitmap::BitMap::insert ( first,

Here we assume that I is an iterator whose value_type is unsigned long, and we do the sequence of insertions from the range [first,last[.

bool atlas::bitmap::BitMap::isMember ( unsigned long  n) const

Tests whether bit n in the bitmap is set; that is, whether element n is a member of the set.

unsigned long atlas::bitmap::BitMap::n_th ( unsigned long  i) const

Value at index |n| if viewed as list of |unsigned long| values.

Synopsis: returns the index of set bit number i in the bitset; in other words, viewing a bitset b as a container of unsigned long, b.n_th(i) is the value of the element i of b, and the syntax b[i] would have been logical (as usual, the first element is number 0). This returns d_capacity if there is no such element, in other words if at most i bits are set in the bitmap. The condition b.position(b.n_th(i))==i holds whenever 0<=i<=size().

bool atlas::bitmap::BitMap::operator!= ( const BitMap b) const
BitMap atlas::bitmap::BitMap::operator& ( const BitMap other) const
bool atlas::bitmap::BitMap::operator&= ( const BitMap b)

Synopsis: intersects the current bitmap with |b|, return value tells whether the result is non-empty.

bool atlas::bitmap::BitMap::operator< ( const BitMap b) const
BitMap & atlas::bitmap::BitMap::operator<<= ( unsigned long  delta)
bool atlas::bitmap::BitMap::operator== ( const BitMap b) const
BitMap & atlas::bitmap::BitMap::operator>>= ( unsigned long  delta)
BitMap atlas::bitmap::BitMap::operator^ ( const BitMap other) const

Synopsis: xor's |b| into the current bitmap.

BitMap atlas::bitmap::BitMap::operator| ( const BitMap other) const

Synopsis: unites |b| into the current bitmap.

BitMap & atlas::bitmap::BitMap::operator~ ( )

Synopsis: transforms the bitmap into its bitwise complement at returns itself

NOTE: one has to be careful about the last chunk, resetting the unused bits to zero.

NOTE: the naming of this manipulator is dangerous, as the user might write something like |a &= ~b| and be surprised by the fact that |b| changes value. Incidentally, for that special case there is |a.andnot(b)|.

unsigned long atlas::bitmap::BitMap::position ( unsigned long  n) const

Number of values |<n| present (set) in the bitmap.

Synopsis: returns the number of set bits in positions < n; viewing a bitset b as a container of unsigned long, this is the number of values < n that b contains. If n itself is a member of b, then n==b.n_th(b.position(n)).

unsigned long atlas::bitmap::BitMap::range ( unsigned long  n,
unsigned long  r 
) const

Synopsis: returns r bits from position n.

Precondition: r divides longBits, and n is a multiple of r.

Thus the bits extracted are found in single element of d_map, and such elements define an integral number of disjoint ranges

It is required that |n<capacity()|, but not that |n+r<=capacity()|; if the latter fails, the return value is padded out with (leading) zero bits.

void atlas::bitmap::BitMap::remove ( unsigned long  n)

Clear the bit at position n (that is, removes an element of the set); this makes |isMember(n)| false.

void atlas::bitmap::BitMap::reset ( )
void atlas::bitmap::BitMap::set_capacity ( unsigned long  n)
void atlas::bitmap::BitMap::set_mod2 ( unsigned long  n,
unsigned long  v 
void atlas::bitmap::BitMap::set_to ( unsigned long  n,
bool  b 
void atlas::bitmap::BitMap::setRange ( unsigned long  n,
unsigned long  r,
unsigned long  a 

Synopsis: sets r bits from position n to the first r bits in a.

Precondition: |n| and |n+r-1| have same integer quotient by |longBits| (or |r==0| in which case nothing happens), so in particular |r<=longBits|. This condition is always satisfied if |r| divides |longBits| and |n| is a multiple of |r|. It ensures that only a single word in |d_map| is affected.

unsigned long atlas::bitmap::BitMap::size ( ) const

Returns the number of set bits in the bitmap (this is its size as a container of unsigned long.)

NOTE: correctness depends on unused bits in the final word being cleared.

void atlas::bitmap::BitMap::swap ( BitMap other)

Member Data Documentation

unsigned long atlas::bitmap::BitMap::baseBits = constants::baseBits

Constant used to pick a bit-address apart: this is the logical complement of posBits, and masks the word-address within a BitMap index (which still must be shifted right by baseShift to be interpreted correctly, whence this constant is actually little used).

It is assumed that the number of bits in an unsigned long is a power of two.

unsigned long atlas::bitmap::BitMap::baseShift = constants::baseShift

Constant saying how much we have to shift the BitMap index n of a bit (that is, the power of two by which it much be divided) to get the index of the d_map element that contains this bit (it is the number of set bits in posBits, typically 5 or 6).

size_t atlas::bitmap::BitMap::d_capacity
std::vector<unsigned long> atlas::bitmap::BitMap::d_map
unsigned long atlas::bitmap::BitMap::posBits = constants::posBits

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