Main Page   Modules   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

vBitset_base Class Template Reference

#include <vbitset.hh>

Collaboration diagram for vBitset_base:

Collaboration graph
[legend]
List of all members.

Public Types

typedef W WordType
typedef A AllocatorType
typedef WordTypeMptr
typedef WordTypeMref
typedef size_t SizeType

Public Methods

 vBitset_base (SizeType len_=1)
 vBitset_base (const vBitset_base &o)
vBitset_base& operator= (const vBitset_base &o)
 ~vBitset_base ()
reference operator[] (SizeType n)
reference begin ()
reference end ()
void resize (SizeType n)
SizeType size () const
SizeType length () const
SizeType capacity () const
bool all0 () const
bool all1 () const
SizeType count1 () const
SizeType count0 () const
void flip ()
void doOr (const vBitset_base &o)
vBitset_base& operator|= (const vBitset_base &o)
void doAnd (const vBitset_base &o)
vBitset_base& operator &= (const vBitset_base &o)
bool operator== (const vBitset_base &o) const
bool operator!= (const vBitset_base &o) const
void clear ()

Static Public Methods

SizeType whichWord (SizeType bits)
SizeType whichBit (SizeType bits)
WordType maskBit (SizeType bits)

Static Public Attributes

const SizeType WORDBITS = sizeof(WordType) * 8
const SizeType WORDBYTES = sizeof(WordType)

Protected Methods

Mptr getWord (SizeType n) const
void grow (SizeType n)
void grow_fill (SizeType n, Mptr d)
void updateLimits ()

Private Attributes

Mptr data
Mptr endOfData
SizeType len
reference _begin
reference _end

Static Private Attributes

AllocatorType M_alloc

Detailed Description

template<class W, class A = allocator<W>> class vBitset_base

A variable-length bit set (v stands for "variable" as oppsed to STL's bitset which has a fixedlength).

Template argument X is the word type to be used for the storage allocation.

Template argument A is the allocator to be used by the class.

Variable-length means that, as each operation is performed between two bitsets, the shortest one is grown to accomodate extra bits resulting from the operations. Shrinking is not yet implemented, and a call to resize with a length that is smaller that the actual bitset's size will cause certain operations to yield funny results.

Definition at line 99 of file vbitset.hh.


Member Typedef Documentation

template<class W, class A = allocator<W>>
typedef W vBitset_base<W, A>::WordType
 

The word type used for allocating memory. Each bit in the set is mapped to a single bit inside a word. It is essential for this type to be unsiged, as we do quite a bit of shifting on it.

Definition at line 116 of file vbitset.hh.

template<class W, class A = allocator<W>>
typedef A vBitset_base<W, A>::AllocatorType
 

Definition at line 118 of file vbitset.hh.

template<class W, class A = allocator<W>>
typedef WordType * vBitset_base<W, A>::Mptr
 

Storage pointer type.

Definition at line 123 of file vbitset.hh.

template<class W, class A = allocator<W>>
typedef WordType & vBitset_base<W, A>::Mref
 

Storage reference type.

Definition at line 128 of file vbitset.hh.

template<class W, class A = allocator<W>>
typedef size_t vBitset_base<W, A>::SizeType
 

The containers' size_type equivalent (size_t is a good choice).

Definition at line 133 of file vbitset.hh.


Constructor & Destructor Documentation

template<class W, class A = allocator<W>>
vBitset_base<W, A>::vBitset_base<W, A> ( SizeType len_ = 1 ) [inline]
 

Creates a new vBitSet of the given length and intializes it with 0.

Precondition:
len_ > 0

Definition at line 304 of file vbitset.hh.

template<class W, class A = allocator<W>>
vBitset_base<W, A>::vBitset_base<W, A> ( const vBitset_base<W, A> & o ) [inline]
 

Definition at line 317 of file vbitset.hh.

template<class W, class A = allocator<W>>
vBitset_base<W, A>::~vBitset_base<W, A> ( ) [inline]
 

Definition at line 341 of file vbitset.hh.


Member Function Documentation

template<class W, class A = allocator<W>>
SizeType vBitset_base<W, A>::whichWord ( SizeType bits ) [inline, static]
 

Definition at line 142 of file vbitset.hh.

Referenced by getWord(), grow(), grow_fill(), and vBitset_base().

template<class W, class A = allocator<W>>
SizeType vBitset_base<W, A>::whichBit ( SizeType bits ) [inline, static]
 

Definition at line 147 of file vbitset.hh.

Referenced by maskBit().

template<class W, class A = allocator<W>>
WordType vBitset_base<W, A>::maskBit ( SizeType bits ) [inline, static]
 

Definition at line 152 of file vbitset.hh.

Referenced by vBitset_base::reference::move().

template<class W, class A = allocator<W>>
vBitset_base<W, A> & vBitset_base<W, A>::operator= ( const vBitset_base<W, A> & o ) [inline]
 

Definition at line 330 of file vbitset.hh.

template<class W, class A = allocator<W>>
reference vBitset_base<W, A>::operator[] ( SizeType n ) [inline]
 

Returns a "bit reference". All the bit-level operations are implemented through bit refs.

Definition at line 351 of file vbitset.hh.

template<class W, class A = allocator<W>>
reference vBitset_base<W, A>::begin ( ) [inline]
 

Definition at line 356 of file vbitset.hh.

Referenced by BasicDfaGenerator::createBasicDfa(), LaParserWriter::makeLaCondition(), FollowPosGen::operator()(), and operator<<().

template<class W, class A = allocator<W>>
reference vBitset_base<W, A>::end ( ) [inline]
 

Definition at line 361 of file vbitset.hh.

Referenced by BasicDfaGenerator::createBasicDfa(), LaParserWriter::makeLaCondition(), FollowPosGen::operator()(), and operator<<().

template<class W, class A = allocator<W>>
void vBitset_base<W, A>::resize ( SizeType n ) [inline]
 

Changes the size of this bitset to n. If n > length(), the new extra space is 0 filled.

Definition at line 370 of file vbitset.hh.

template<class W, class A = allocator<W>>
SizeType vBitset_base<W, A>::size ( ) const [inline]
 

Returns the number of bits in this betset.

Definition at line 378 of file vbitset.hh.

Referenced by length().

template<class W, class A = allocator<W>>
SizeType vBitset_base<W, A>::length ( ) const [inline]
 

Alias for size.

Definition at line 386 of file vbitset.hh.

Referenced by count0(), doAnd(), doOr(), EbnfLaNode::dumpAttributes(), and EbnfLl1CheckAlgo::warn().

template<class W, class A = allocator<W>>
SizeType vBitset_base<W, A>::capacity ( ) const [inline]
 

Returns the number of storage words allocated for this bitset. The result satisfies the invarian: capacity() * WORDBITS >= size().

Definition at line 395 of file vbitset.hh.

Referenced by doAnd(), doOr(), grow(), grow_fill(), operator=(), operator==(), vBitset_base(), and ~vBitset_base().

template<class W, class A = allocator<W>>
bool vBitset_base<W, A>::all0 ( ) const [inline]
 

True is all bits are 0.

Definition at line 403 of file vbitset.hh.

Referenced by all1(), BasicDfaGenerator::createBasicDfa(), and EbnfLl1CheckAlgo::operator()().

template<class W, class A = allocator<W>>
bool vBitset_base<W, A>::all1 ( ) const [inline]
 

Returns true if all bits are 1.

Definition at line 411 of file vbitset.hh.

template<class W, class A = allocator<W>>
SizeType vBitset_base<W, A>::count1 ( ) const [inline]
 

Returns the number of bits that are set.

Definition at line 419 of file vbitset.hh.

Referenced by all0(), count0(), and DfaReNodeBuilder::createCharListNode().

template<class W, class A = allocator<W>>
SizeType vBitset_base<W, A>::count0 ( ) const [inline]
 

Returns the number of bits that are not set.

Definition at line 435 of file vbitset.hh.

template<class W, class A = allocator<W>>
void vBitset_base<W, A>::flip ( ) [inline]
 

Flips every bit in this bitset.

Definition at line 443 of file vbitset.hh.

Referenced by DfaReNodeBuilder::createCharListNode().

template<class W, class A = allocator<W>>
void vBitset_base<W, A>::doOr ( const vBitset_base<W, A> & o ) [inline]
 

Definition at line 448 of file vbitset.hh.

Referenced by operator|=().

template<class W, class A = allocator<W>>
vBitset_base<W, A> & vBitset_base<W, A>::operator|= ( const vBitset_base<W, A> & o ) [inline]
 

Definition at line 463 of file vbitset.hh.

template<class W, class A = allocator<W>>
void vBitset_base<W, A>::doAnd ( const vBitset_base<W, A> & o ) [inline]
 

Definition at line 469 of file vbitset.hh.

Referenced by operator &=().

template<class W, class A = allocator<W>>
vBitset_base<W, A> & vBitset_base<W, A>::operator &= ( const vBitset_base<W, A> & o ) [inline]
 

Definition at line 485 of file vbitset.hh.

template<class W, class A = allocator<W>>
bool vBitset_base<W, A>::operator== ( const vBitset_base<W, A> & o ) const [inline]
 

*this == o if any of these conditions are true:

  • both have the same length, and all the bits are equal.
  • all the bits up the smallest length of the two are equal, and any extra bits the longest set may have are all 0.

Definition at line 497 of file vbitset.hh.

template<class W, class A = allocator<W>>
bool vBitset_base<W, A>::operator!= ( const vBitset_base<W, A> & o ) const [inline]
 

Definition at line 510 of file vbitset.hh.

template<class W, class A = allocator<W>>
void vBitset_base<W, A>::clear ( ) [inline]
 

Definition at line 515 of file vbitset.hh.

template<class W, class A = allocator<W>>
Mptr vBitset_base<W, A>::getWord ( SizeType n ) const [inline, protected]
 

returns a pointer to the word containing the n'th bit.

Definition at line 527 of file vbitset.hh.

Referenced by vBitset_base::reference::move().

template<class W, class A = allocator<W>>
void vBitset_base<W, A>::grow ( SizeType n ) [inline, protected]
 

Ensures we have enough storage for holding n bits, by eventually growing the storage. Newly extra space is 0 filled.

Definition at line 536 of file vbitset.hh.

Referenced by doAnd(), and resize().

template<class W, class A = allocator<W>>
void vBitset_base<W, A>::grow_fill ( SizeType n,
Mptr d ) [inline, protected]
 

Ensures we have enough storage for n bits, by eventually growing the storage. The newly extra space is filled with bits copied from d[].

Definition at line 559 of file vbitset.hh.

Referenced by doOr().

template<class W, class A = allocator<W>>
void vBitset_base<W, A>::updateLimits ( ) [inline, protected]
 

Updates the _begin and _end iterators after allocating data.

Definition at line 581 of file vbitset.hh.

Referenced by clear(), doAnd(), doOr(), grow(), grow_fill(), operator=(), and vBitset_base().


Member Data Documentation

template<class W, class A = allocator<W>>
const SizeType vBitset_base<W, A>::WORDBITS = sizeof(WordType) * 8 [static]
 

How many bits long our storage word is.

Definition at line 138 of file vbitset.hh.

template<class W, class A = allocator<W>>
const SizeType vBitset_base<W, A>::WORDBYTES = sizeof(WordType) [static]
 

Definition at line 140 of file vbitset.hh.

template<class W, class A = allocator<W>>
Mptr vBitset_base<W, A>::data [private]
 

The internal storage

Definition at line 592 of file vbitset.hh.

template<class W, class A = allocator<W>>
Mptr vBitset_base<W, A>::endOfData [private]
 

First word past allocated storage.

Definition at line 597 of file vbitset.hh.

template<class W, class A = allocator<W>>
SizeType vBitset_base<W, A>::len [private]
 

The length of the bitvector in bits (this is what size() returns).

Definition at line 602 of file vbitset.hh.

template<class W, class A = allocator<W>>
reference vBitset_base<W, A>::_begin [private]
 

Always points to the first element.

Definition at line 607 of file vbitset.hh.

template<class W, class A = allocator<W>>
reference vBitset_base<W, A>::_end [private]
 

Always points to the last element.

Definition at line 612 of file vbitset.hh.

template<class W, class A = allocator<W>>
AllocatorType vBitset_base<W, A>::M_alloc [static, private]
 

Initial value:

                                    allocator<unsigned long>()

Definition at line 614 of file vbitset.hh.


The documentation for this class was generated from the following files:
Generated at Tue Jul 9 21:08:52 2002 for CppCC by doxygen1.2.8.1 written by Dimitri van Heesch, © 1997-2001