 |
atlas
0.6
|
Container of a large (more than twice the machine word size) set of bits. More...
#include <bitmap.h>
Classes | |
| class | iterator |
| Traverses the set bits of a BitMap. More... | |
Public Types | |
| typedef unsigned long | value_type |
| typedef value_type & | reference |
| typedef const value_type & | const_reference |
| typedef value_type * | pointer |
| typedef const value_type * | const_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... | |
| BitMap & | operator= (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 |
| BitMap & | operator~ () |
| bool | operator&= (const BitMap &) |
| BitMap & | operator|= (const BitMap &) |
| BitMap & | operator^= (const BitMap &) |
| BitMap & | andnot (const BitMap &b) |
| BitMap & | operator>>= (unsigned long delta) |
| BitMap & | operator<<= (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 |
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.
| typedef const value_type* atlas::bitmap::BitMap::const_pointer |
| typedef const value_type& atlas::bitmap::BitMap::const_reference |
| typedef ptrdiff_t atlas::bitmap::BitMap::difference_type |
| typedef value_type* atlas::bitmap::BitMap::pointer |
| 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
|
inline |
|
inlineexplicit |
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|.
|
inline |
Copy constructor.
| atlas::bitmap::BitMap::BitMap | ( | unsigned long | n, |
| const I & | first, | ||
| const I & | last | ||
| ) |
|
inline |
| 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[.
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()|.
|
inline |
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|.
|
inline |
| 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.
|
inline |
Set the bit at position n (that is, inserts the value |n| into the set); this makes |isMember(n)| hold.
| void atlas::bitmap::BitMap::insert | ( | I | first, |
| I | last | ||
| ) |
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[.
|
inline |
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().
|
inline |
|
inline |
| bool atlas::bitmap::BitMap::operator&= | ( | const BitMap & | b | ) |
Synopsis: intersects the current bitmap with |b|, return value tells whether the result is non-empty.
|
inline |
| BitMap & atlas::bitmap::BitMap::operator<<= | ( | unsigned long | delta | ) |
| BitMap & atlas::bitmap::BitMap::operator= | ( | const BitMap & | a | ) |
|
inline |
| BitMap & atlas::bitmap::BitMap::operator>>= | ( | unsigned long | delta | ) |
|
inline |
| BitMap & atlas::bitmap::BitMap::operator^= | ( | const BitMap & | b | ) |
Synopsis: xor's |b| into the current bitmap.
|
inline |
| BitMap & atlas::bitmap::BitMap::operator|= | ( | const BitMap & | b | ) |
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.
|
inline |
Clear the bit at position n (that is, removes an element of the set); this makes |isMember(n)| false.
|
inline |
| void atlas::bitmap::BitMap::set_capacity | ( | unsigned long | n | ) |
|
inline |
|
inline |
| 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 | ) |
|
staticprivate |
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.
|
staticprivate |
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).
|
private |
|
private |
|
staticprivate |
1.8.11
