PackedList< nBits > Class Template Reference

A dynamically allocatable list of packed unsigned integers. More...

Inheritance diagram for PackedList< nBits >:
Collaboration diagram for PackedList< nBits >:

Classes

class  const_iterator
 The const_iterator for PackedList. More...
 
class  iterator
 The iterator class used for PackedList. More...
 
class  iteratorBase
 The iterator base for PackedList. More...
 

Public Member Functions

 PackedList ()
 Null constructor. More...
 
 PackedList (const label size)
 Construct with given size, initializes list to 0. More...
 
 PackedList (const label size, const unsigned val)
 Construct with given size and value for all elements. More...
 
 PackedList (Istream &)
 Construct from Istream. More...
 
 PackedList (const PackedList< nBits > &)
 Copy constructor. More...
 
 PackedList (PackedList< nBits > &&)
 Move constructor. More...
 
 PackedList (const labelUList &)
 Construct from a list of labels. More...
 
 PackedList (const UIndirectList< label > &)
 Construct from an indirect list of labels. More...
 
autoPtr< PackedList< nBits > > clone () const
 Clone. More...
 
label capacity () const
 The number of elements that can be stored before reallocating. More...
 
label size () const
 Number of entries. More...
 
bool empty () const
 Return true if the list is empty (ie, size() is zero). More...
 
unsigned int get (const label) const
 Get value at index I. More...
 
bool set (const label, const unsigned int val=~0u)
 Set value at index I. Return true if value changed. More...
 
bool unset (const label)
 Unset the entry at index I. Return true if value changed. More...
 
List< unsigned int > & storage ()
 Return the underlying packed storage. More...
 
const List< unsigned int > & storage () const
 Return the underlying packed storage. More...
 
label packedLength () const
 The list length when packed. More...
 
std::streamsize byteSize () const
 Return the binary size in number of characters. More...
 
unsigned int count () const
 Count number of bits set, O(log(n)) More...
 
labelList values () const
 Return the values as a list of labels. More...
 
OstreamprintBits (Ostream &, const bool fullOutput=false) const
 Print bit patterns, optionally output unused elements. More...
 
OstreamprintInfo (Ostream &, const bool fullOutput=false) const
 Print information and bit patterns (with printBits) More...
 
bool trim ()
 Trim any trailing zero elements. More...
 
void flip ()
 Invert the bits in the addressable region. More...
 
void reset ()
 Clear all bits. More...
 
void setCapacity (const label)
 Alter the size of the underlying storage. More...
 
void resize (const label, const unsigned int &val=0u)
 Reset addressable list size, does not shrink the allocated size. More...
 
void setSize (const label, const unsigned int &val=0u)
 Alias for resize() More...
 
void reserve (const label)
 Reserve allocation space for at least this size. More...
 
void clear ()
 Clear the list, i.e. set addressable size to zero. More...
 
void clearStorage ()
 Clear the list and delete storage. More...
 
void shrink ()
 Shrink the allocated space to what is actually used. More...
 
void transfer (PackedList< nBits > &)
 Transfer the contents of the argument list into this list. More...
 
Istreamread (Istream &)
 Clear list and read from stream. More...
 
Ostreamwrite (Ostream &, const bool indexedOutput=false) const
 Write, optionally with indexedOutput. More...
 
PackedList< nBits > & append (const unsigned int val)
 Append a value at the end of the list. More...
 
unsigned int remove ()
 Remove and return the last element. More...
 
unsigned int operator[] (const label) const
 Get value at index I. More...
 
iteratorBase operator[] (const label)
 Set value at index I. More...
 
void operator= (const unsigned int val)
 Assignment of all entries to the given value. Takes linear time. More...
 
void operator= (const PackedList< nBits > &)
 Assignment operator. More...
 
void operator= (PackedList< nBits > &&)
 Move assignment operator. More...
 
void operator= (const labelUList &)
 Assignment operator. More...
 
void operator= (const UIndirectList< label > &)
 Assignment operator. More...
 
iterator begin ()
 Iterator set to the beginning of the PackedList. More...
 
iterator end ()
 Iterator set to beyond the end of the PackedList. More...
 
const_iterator cbegin () const
 const_iterator set to the beginning of the PackedList More...
 
const_iterator cend () const
 const_iterator set to beyond the end of the PackedList More...
 
const_iterator begin () const
 const_iterator set to the beginning of the PackedList More...
 
const_iterator end () const
 const_iterator set to beyond the end of the PackedList More...
 
- Public Member Functions inherited from PackedListCore
 PackedListCore ()
 Construct null. More...
 
 ClassName ("PackedList")
 Define template name and debug. More...
 

Static Public Member Functions

static unsigned int max_bits ()
 The max. number of bits that can be templated. More...
 
static unsigned int max_value ()
 The max. value for an entry, which simultaneously the bit-mask. More...
 
static unsigned int packing ()
 The number of entries per packed storage element. More...
 
static unsigned int maskLower (unsigned offset)
 Masking for all bits below the offset. More...
 

Protected Types

typedef unsigned int StorageType
 
typedef List< StorageTypeStorageList
 

Protected Member Functions

void setPair (Istream &)
 Read an index/value pair and set accordingly. More...
 
template<>
unsigned int readValue (Istream &is)
 
template<>
void setPair (Istream &is)
 

Static Protected Member Functions

static label packedLength (const label)
 Calculate the list length when packed. More...
 
static unsigned int readValue (Istream &)
 Read a list entry (allows for specialization) More...
 

Friends

Istreamoperator>> (Istream &, PackedList< nBits > &)
 
Ostreamoperator (Ostream &, const PackedList< nBits > &)
 

Detailed Description

template<unsigned nBits = 1>
class Foam::PackedList< nBits >

A dynamically allocatable list of packed unsigned integers.

The list resizing is similar to DynamicList, thus the methods clear() and setSize() behave like their DynamicList counterparts and the methods reserve() and setCapacity() can be used to influence the allocation.

The number of bits per item is specified by the template parameter nBits.

Note
In a const context, the '[]' operator simply returns the stored value, with out-of-range elements returned as zero. In a non-const context, the '[]' operator returns an iteratorBase, which might not have a valid reference for out-of-range elements. The iteratorBase class handles the assignment of new values.

Using the iteratorBase as a proxy allows assignment of values between list elements. Thus the following bit of code works as expected:

list[1] = list[5]; // value assignment, not iterator position
list[2] = list[5] = 4; // propagates value
list[1] = list[5] = list[6]; // propagates value

Using get() or the '[]' operator are similarly fast. Looping and reading via an iterator is approx. 15% slower, but can be more flexible.

Using the set() operator (and the '[]' operator) are marginally slower (approx. 5%) than using an iterator, but the set() method has the advantage of also returning a bool if the value changed. This can be useful for branching on changed values.

list[5] = 4;
changed = list.set(5, 8);
if (changed) ...

The lazy evaluation used means that reading an out-of-range element returns zero, but does not affect the list size. Even in a non-const context, only the assignment itself causes the element to be created. For example,

list.resize(4);
Info<< list[10] << "\n"; // print zero, but doesn't adjust list
list[8] = 1;

Also note that all unused internal storage elements are guaranteed to always be bit-wise zero. This property must not be violated by any inheriting classes.

In addition to the normal output format, PackedList also supports a compact ASCII format that may be convenient for user input in some situations. The general format is a group of index/value pairs:

    { (index1 value1) (index2 value2) (index3 value3) }

The bool specialization just uses the indices corresponding to non-zero entries instead of a index/value pair:

    { index1 index2 index3 }

In both cases, the supplied indices can be randomly ordered.

See also
Foam::DynamicList
Source files

Definition at line 117 of file PackedList.H.

Member Typedef Documentation

◆ StorageType

typedef unsigned int StorageType
protected

Definition at line 157 of file PackedList.H.

◆ StorageList

typedef List<StorageType> StorageList
protected

Definition at line 158 of file PackedList.H.

Constructor & Destructor Documentation

◆ PackedList() [1/8]

PackedList ( )
inline

Null constructor.

Definition at line 168 of file PackedListI.H.

Referenced by PackedList< 2 >::PackedList().

Here is the caller graph for this function:

◆ PackedList() [2/8]

PackedList ( const label  size)
inlineexplicit

Construct with given size, initializes list to 0.

Definition at line 177 of file PackedListI.H.

◆ PackedList() [3/8]

PackedList ( const label  size,
const unsigned  val 
)
inline

Construct with given size and value for all elements.

◆ PackedList() [4/8]

PackedList ( Istream is)
inline

Construct from Istream.

Definition at line 204 of file PackedListI.H.

◆ PackedList() [5/8]

PackedList ( const PackedList< nBits > &  lst)
inline

Copy constructor.

Definition at line 215 of file PackedListI.H.

◆ PackedList() [6/8]

PackedList ( PackedList< nBits > &&  lst)
inline

Move constructor.

Definition at line 224 of file PackedListI.H.

◆ PackedList() [7/8]

PackedList ( const labelUList lst)
inlineexplicit

Construct from a list of labels.

Definition at line 231 of file PackedListI.H.

◆ PackedList() [8/8]

PackedList ( const UIndirectList< label > &  lst)
inlineexplicit

Construct from an indirect list of labels.

Definition at line 245 of file PackedListI.H.

Member Function Documentation

◆ packedLength() [1/2]

Foam::label packedLength ( const label  nElem)
inlinestaticprotected

Calculate the list length when packed.

Definition at line 62 of file PackedListI.H.

Referenced by PackedBoolList::unset().

Here is the caller graph for this function:

◆ readValue() [1/2]

unsigned int readValue ( Istream is)
inlinestaticprotected

Read a list entry (allows for specialization)

Definition at line 103 of file PackedListI.H.

Referenced by PackedList< 2 >::read().

Here is the caller graph for this function:

◆ setPair() [1/2]

void setPair ( Istream is)
inlineprotected

Read an index/value pair and set accordingly.

For bool specialization, read a single index value

Definition at line 120 of file PackedListI.H.

Referenced by PackedList< 2 >::read().

Here is the caller graph for this function:

◆ max_bits()

unsigned int max_bits ( )
inlinestatic

The max. number of bits that can be templated.

Might someday be useful for a template assert.

Definition at line 31 of file PackedListI.H.

◆ max_value()

unsigned int max_value ( )
inlinestatic

The max. value for an entry, which simultaneously the bit-mask.

eg, ((1 << 2) - 1) yields 0b0011

Definition at line 38 of file PackedListI.H.

Referenced by PackedList< nBits >::iteratorBase::get(), PackedList< 2 >::operator=(), PackedList< 2 >::resize(), and PackedList< nBits >::iteratorBase::set().

Here is the caller graph for this function:

◆ packing()

unsigned int packing ( )
inlinestatic

The number of entries per packed storage element.

Definition at line 45 of file PackedListI.H.

Referenced by PackedList< 2 >::capacity(), PackedList< nBits >::iteratorBase::get(), PackedList< 2 >::operator=(), PackedList< 2 >::resize(), PackedList< nBits >::iteratorBase::set(), and PackedList< 2 >::setCapacity().

Here is the caller graph for this function:

◆ maskLower()

unsigned int maskLower ( unsigned  offset)
inlinestatic

Masking for all bits below the offset.

Definition at line 52 of file PackedListI.H.

Referenced by PackedList< 2 >::operator=(), PackedList< 2 >::resize(), and PackedList< 2 >::setCapacity().

Here is the caller graph for this function:

◆ clone()

Foam::autoPtr< Foam::PackedList< nBits > > clone ( ) const
inline

Clone.

Definition at line 260 of file PackedListI.H.

◆ capacity()

Foam::label capacity ( ) const
inline

The number of elements that can be stored before reallocating.

Definition at line 831 of file PackedListI.H.

◆ size()

◆ empty()

bool empty ( ) const
inline

Return true if the list is empty (ie, size() is zero).

Definition at line 718 of file PackedListI.H.

Referenced by dynamicRefineFvMesh::selectRefineCells().

Here is the caller graph for this function:

◆ get()

◆ set()

bool set ( const label  i,
const unsigned int  val = ~0u 
)
inline

Set value at index I. Return true if value changed.

Does auto-vivify for non-existent entries. Default value set is the max_value.

Definition at line 985 of file PackedListI.H.

Referenced by PackedList< 2 >::operator[]().

Here is the caller graph for this function:

◆ unset()

bool unset ( const label  i)
inline

Unset the entry at index I. Return true if value changed.

Never auto-vivify entries.

Definition at line 1006 of file PackedListI.H.

◆ storage() [1/2]

Foam::List< unsigned int > & storage ( )
inline

Return the underlying packed storage.

Manipulate with utmost caution

Definition at line 916 of file PackedListI.H.

Referenced by PackedBoolList::operator^=(), PackedList< 2 >::read(), PackedBoolList::set(), PackedBoolList::subset(), PackedBoolList::unset(), and PackedList< 2 >::write().

Here is the caller graph for this function:

◆ storage() [2/2]

const Foam::List< unsigned int > & storage ( ) const
inline

Return the underlying packed storage.

Definition at line 923 of file PackedListI.H.

◆ packedLength() [2/2]

Foam::label packedLength ( ) const
inline

◆ byteSize()

std::streamsize byteSize ( ) const
inline

Return the binary size in number of characters.

used in the underlying storage

Definition at line 937 of file PackedListI.H.

Referenced by PackedList< 2 >::read(), and PackedList< 2 >::write().

Here is the caller graph for this function:

◆ count()

unsigned int count ( ) const

Count number of bits set, O(log(n))

Uses the Hamming weight (population count) method http://en.wikipedia.org/wiki/Hamming_weight

Definition at line 55 of file PackedList.C.

Referenced by polyMeshFilter::filterEdges(), NASedgeFormat::read(), and STARCDedgeFormat::read().

Here is the caller graph for this function:

◆ values()

Foam::labelList values ( ) const

Return the values as a list of labels.

Definition at line 134 of file PackedList.C.

◆ printBits()

Foam::Ostream & printBits ( Ostream os,
const bool  fullOutput = false 
) const

Print bit patterns, optionally output unused elements.

addressable bits: on: '1', off: '-'

non-addressable bits: on: '!', off: '.'

Definition at line 166 of file PackedList.C.

Referenced by PackedList< nBits >::iteratorBase::printInfo().

Here is the caller graph for this function:

◆ printInfo()

Foam::Ostream & printInfo ( Ostream os,
const bool  fullOutput = false 
) const

Print information and bit patterns (with printBits)

Definition at line 235 of file PackedList.C.

Referenced by PackedList< 2 >::printBits().

Here is the caller graph for this function:

◆ trim()

bool trim ( )

Trim any trailing zero elements.

Definition at line 74 of file PackedList.C.

Referenced by Foam::operator^(), and PackedBoolList::operator^=().

Here is the caller graph for this function:

◆ flip()

void flip ( )

Invert the bits in the addressable region.

Definition at line 104 of file PackedList.C.

Referenced by PackedBoolList::operator~().

Here is the caller graph for this function:

◆ reset()

void reset ( )
inline

Clear all bits.

Definition at line 882 of file PackedListI.H.

Referenced by PackedList< 2 >::clear().

Here is the caller graph for this function:

◆ setCapacity()

void setCapacity ( const label  nElem)
inline

Alter the size of the underlying storage.

The addressed size will be truncated if needed to fit, but will remain otherwise untouched.

Definition at line 838 of file PackedListI.H.

Referenced by polyTopoChange::addMesh(), and polyTopoChange::setCapacity().

Here is the caller graph for this function:

◆ resize()

void resize ( const label  newSize,
const unsigned int &  val = 0u 
)
inline

Reset addressable list size, does not shrink the allocated size.

Optionally specify a value for new elements.

Definition at line 726 of file PackedListI.H.

Referenced by PackedList< 2 >::empty(), PackedList< nBits >::iteratorBase::operator=(), PackedList< 2 >::read(), PackedList< 2 >::remove(), PackedList< 2 >::set(), and PackedList< 2 >::setSize().

Here is the caller graph for this function:

◆ setSize()

void setSize ( const label  newSize,
const unsigned int &  val = 0u 
)
inline

Alias for resize()

Definition at line 820 of file PackedListI.H.

Referenced by PatchTools::matchEdges(), and PackedList< 2 >::resize().

Here is the caller graph for this function:

◆ reserve()

void reserve ( const label  nElem)
inline

Reserve allocation space for at least this size.

Never shrinks the allocated size. The list size is adjusted as per DynamicList with SizeInc=0, SizeMult=2, SizeDiv=1

Definition at line 860 of file PackedListI.H.

Referenced by PackedList< 2 >::append(), PackedList< 2 >::resize(), and PackedBoolList::subsetIndices().

Here is the caller graph for this function:

◆ clear()

void clear ( )
inline

Clear the list, i.e. set addressable size to zero.

Does not adjust the underlying storage

Definition at line 889 of file PackedListI.H.

Referenced by dynamicRefineFvMesh::calculateProtectedCells(), dynamicRefineFvMesh::dynamicRefineFvMesh(), and PackedList< 2 >::read().

Here is the caller graph for this function:

◆ clearStorage()

void clearStorage ( )
inline

Clear the list and delete storage.

Definition at line 897 of file PackedListI.H.

Referenced by polyTopoChange::changeMesh(), polyTopoChange::clear(), and polyTopoChange::makeMesh().

Here is the caller graph for this function:

◆ shrink()

void shrink ( )
inline

Shrink the allocated space to what is actually used.

Definition at line 905 of file PackedListI.H.

◆ transfer()

void transfer ( PackedList< nBits > &  lst)
inline

Transfer the contents of the argument list into this list.

and annul the argument list.

Definition at line 944 of file PackedListI.H.

Referenced by PackedBoolList::transfer().

Here is the caller graph for this function:

◆ read()

Foam::Istream & read ( Istream is)

Clear list and read from stream.

Definition at line 254 of file PackedList.C.

Referenced by Foam::writeEntry().

Here is the caller graph for this function:

◆ write()

Foam::Ostream & write ( Ostream os,
const bool  indexedOutput = false 
) const

Write, optionally with indexedOutput.

The indexed output may be convenient in some situations. The general format is a group of index/value pairs:

    { (index1 value1) (index2 value2) (index3 value3) }

The bool specialization just uses the indices corresponding to non-zero entries instead of a index/value pair:

   { index1 index2 index3 }

Note the indexed output is only supported for ASCII streams.

Definition at line 399 of file PackedList.C.

Referenced by PackedList< 2 >::read(), and Foam::writeEntry().

Here is the caller graph for this function:

◆ append()

Foam::PackedList< nBits > & append ( const unsigned int  val)
inline

Append a value at the end of the list.

Definition at line 1022 of file PackedListI.H.

Referenced by extendedEdgeMesh::edgeBaffles(), and PackedList< 2 >::read().

Here is the caller graph for this function:

◆ remove()

unsigned int remove ( )
inline

Remove and return the last element.

Definition at line 1034 of file PackedListI.H.

◆ operator[]() [1/2]

unsigned int operator[] ( const label  i) const
inline

Get value at index I.

Never auto-vivify entries.

Definition at line 969 of file PackedListI.H.

◆ operator[]() [2/2]

Foam::PackedList< nBits >::iteratorBase operator[] ( const label  i)
inline

Set value at index I.

Returns iterator to perform the actual operation. Does not auto-vivify entries, but will when assigned to.

Definition at line 1052 of file PackedListI.H.

◆ operator=() [1/5]

void operator= ( const unsigned int  val)
inline

Assignment of all entries to the given value. Takes linear time.

Definition at line 1059 of file PackedListI.H.

Referenced by PackedBoolList::operator=().

Here is the caller graph for this function:

◆ operator=() [2/5]

void operator= ( const PackedList< nBits > &  lst)

Assignment operator.

Definition at line 496 of file PackedList.C.

◆ operator=() [3/5]

void operator= ( PackedList< nBits > &&  lst)

Move assignment operator.

Definition at line 504 of file PackedList.C.

◆ operator=() [4/5]

void operator= ( const labelUList lst)

Assignment operator.

Definition at line 511 of file PackedList.C.

◆ operator=() [5/5]

void operator= ( const UIndirectList< label > &  lst)

Assignment operator.

Definition at line 524 of file PackedList.C.

◆ begin() [1/2]

Foam::PackedList< nBits >::iterator begin ( )
inline

Iterator set to the beginning of the PackedList.

Definition at line 662 of file PackedListI.H.

◆ end() [1/2]

Foam::PackedList< nBits >::iterator end ( )
inline

Iterator set to beyond the end of the PackedList.

Definition at line 686 of file PackedListI.H.

◆ cbegin()

Foam::PackedList< nBits >::const_iterator cbegin ( ) const
inline

const_iterator set to the beginning of the PackedList

Definition at line 678 of file PackedListI.H.

Referenced by PackedList< 2 >::write().

Here is the caller graph for this function:

◆ cend()

Foam::PackedList< nBits >::const_iterator cend ( ) const
inline

const_iterator set to beyond the end of the PackedList

Definition at line 702 of file PackedListI.H.

Referenced by PackedList< 2 >::write().

Here is the caller graph for this function:

◆ begin() [2/2]

Foam::PackedList< nBits >::const_iterator begin ( ) const
inline

const_iterator set to the beginning of the PackedList

Definition at line 670 of file PackedListI.H.

◆ end() [2/2]

Foam::PackedList< nBits >::const_iterator end ( ) const
inline

const_iterator set to beyond the end of the PackedList

Definition at line 694 of file PackedListI.H.

◆ readValue() [2/2]

unsigned int readValue ( Istream is)
inlineprotected

Definition at line 72 of file PackedListI.H.

◆ setPair() [2/2]

void setPair ( Istream is)
inlineprotected

Definition at line 79 of file PackedListI.H.

Friends And Related Function Documentation

◆ operator>>

Istream& operator>> ( Istream ,
PackedList< nBits > &   
)
friend

◆ operator

Ostream& operator ( Ostream ,
const PackedList< nBits > &   
)
friend

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