carl  24.04
Computer ARithmetic Library
Data Structures | Public Member Functions | Private Member Functions | Private Attributes
carl::CompactTree< Entry, FastIndex > Class Template Reference

This class packs a complete binary tree in a vector. More...

#include <CompactTree.h>

Inheritance diagram for carl::CompactTree< Entry, FastIndex >:
Inheritance graph
[legend]
Collaboration diagram for carl::CompactTree< Entry, FastIndex >:
Collaboration graph
[legend]

Data Structures

class  Node
 

Public Member Functions

 CompactTree (std::size_t initialCapacity=0)
 
 CompactTree (const CompactTree &tree, std::size_t minCapacity=0)
 
 ~CompactTree ()
 
Entry & operator[] (Node n)
 
const Entry & operator[] (Node n) const
 
bool empty () const
 
std::size_t size () const
 
std::size_t capacity () const
 
Node lastLeaf () const
 
void pushBack (const Entry &value)
 
void pushBackWithCapacity (const Entry &value)
 
void popBack ()
 
bool hasFreeCapacity (size_t extraCapacity) const
 
void increaseCapacity ()
 
void swap (CompactTree &tree)
 
void print (std::ostream &out) const
 
void clear ()
 
std::size_t getMemoryUse () const
 
bool isValid () const
 
std::vector< Entry > getCopy () const
 

Private Member Functions

CompactTree & operator= (const CompactTree &tree) const =delete
 

Private Attributes

Entry * _array
 
Node _lastLeaf
 
Node _capacityEnd
 

Detailed Description

template<class Entry, bool FastIndex>
class carl::CompactTree< Entry, FastIndex >

This class packs a complete binary tree in a vector.

The idea is to have the root at index 1, and then the left child of node n will be at index 2n and the right child will be at index 2n + 1. The corresponding formulas when indexes start at 0 take more computation, so we need a 1-based array so we can't use std::vector.

Also, when sizeof(Entry) is a power of 2 it is faster to keep track of i * sizeof(Entry) than directly keeping track of an index i. This doesn't work well when sizeof(Entry) is not a power of two. So we need both possibilities. That is why this class never exposes indexes. Instead you interact with Node objects that serve the role of an index, but the precise value it stores is encapsulated. This way you can't do something like _array[i * sizeof(Entry)] by accident. Client code also does not need to (indeed, can't) be aware of how indexes are calculated, stored and looked up.

If FastIndex is false, then Nodes contain an index i. If FastIndex is true, then Nodes contain the byte offset i * sizeof(Entry). FastIndex must be false if sizeof(Entry) is not a power of two.

Definition at line 42 of file CompactTree.h.

Constructor & Destructor Documentation

◆ CompactTree() [1/2]

template<class Entry , bool FastIndex>
carl::CompactTree< Entry, FastIndex >::CompactTree ( std::size_t  initialCapacity = 0)
explicit

◆ CompactTree() [2/2]

template<class Entry , bool FastIndex>
carl::CompactTree< Entry, FastIndex >::CompactTree ( const CompactTree< Entry, FastIndex > &  tree,
std::size_t  minCapacity = 0 
)

◆ ~CompactTree()

template<class Entry , bool FastIndex>
carl::CompactTree< Entry, FastIndex >::~CompactTree ( )
inline

Definition at line 48 of file CompactTree.h.

Member Function Documentation

◆ capacity()

template<class Entry , bool FastIndex>
std::size_t carl::CompactTree< Entry, FastIndex >::capacity ( ) const
inline

Definition at line 66 of file CompactTree.h.

◆ clear()

template<class E , bool FI>
void carl::CompactTree< E, FI >::clear

Definition at line 194 of file CompactTree.h.

◆ empty()

template<class Entry , bool FastIndex>
bool carl::CompactTree< Entry, FastIndex >::empty ( ) const
inline

Definition at line 56 of file CompactTree.h.

Here is the caller graph for this function:

◆ getCopy()

template<class Entry , bool FastIndex>
std::vector<Entry> carl::CompactTree< Entry, FastIndex >::getCopy ( ) const
inline

Definition at line 174 of file CompactTree.h.

Here is the caller graph for this function:

◆ getMemoryUse()

template<class E , bool FI>
size_t carl::CompactTree< E, FI >::getMemoryUse

Definition at line 200 of file CompactTree.h.

◆ hasFreeCapacity()

template<class E , bool FI>
bool carl::CompactTree< E, FI >::hasFreeCapacity ( size_t  extraCapacity) const

Definition at line 373 of file CompactTree.h.

Here is the call graph for this function:

◆ increaseCapacity()

template<class E , bool FI>
void carl::CompactTree< E, FI >::increaseCapacity

Definition at line 379 of file CompactTree.h.

Here is the call graph for this function:

◆ isValid()

template<class E , bool FI>
bool carl::CompactTree< E, FI >::isValid

Definition at line 353 of file CompactTree.h.

◆ lastLeaf()

template<class Entry , bool FastIndex>
Node carl::CompactTree< Entry, FastIndex >::lastLeaf ( ) const
inline

Definition at line 71 of file CompactTree.h.

Here is the caller graph for this function:

◆ operator=()

template<class Entry , bool FastIndex>
CompactTree& carl::CompactTree< Entry, FastIndex >::operator= ( const CompactTree< Entry, FastIndex > &  tree) const
privatedelete

◆ operator[]() [1/2]

template<class E , bool FI>
E & carl::CompactTree< E, FI >::operator[] ( Node  n)

Definition at line 243 of file CompactTree.h.

◆ operator[]() [2/2]

template<class E , bool FI>
const E & carl::CompactTree< E, FI >::operator[] ( Node  n) const

Definition at line 255 of file CompactTree.h.

◆ popBack()

template<class E , bool FI>
void carl::CompactTree< E, FI >::popBack

Definition at line 279 of file CompactTree.h.

Here is the caller graph for this function:

◆ print()

template<class E , bool FI>
void carl::CompactTree< E, FI >::print ( std::ostream &  out) const

Definition at line 337 of file CompactTree.h.

Here is the call graph for this function:

◆ pushBack()

template<class Entry , bool FastIndex>
void carl::CompactTree< E, FI >::pushBack ( const Entry &  value)

Definition at line 261 of file CompactTree.h.

Here is the caller graph for this function:

◆ pushBackWithCapacity()

template<class Entry , bool FastIndex>
void carl::CompactTree< E, FI >::pushBackWithCapacity ( const Entry &  value)

Definition at line 271 of file CompactTree.h.

◆ size()

template<class Entry , bool FastIndex>
std::size_t carl::CompactTree< Entry, FastIndex >::size ( ) const
inline

Definition at line 61 of file CompactTree.h.

Here is the caller graph for this function:

◆ swap()

template<class E , bool FI>
void carl::CompactTree< E, FI >::swap ( CompactTree< Entry, FastIndex > &  tree)

Definition at line 286 of file CompactTree.h.

Here is the call graph for this function:

Field Documentation

◆ _array

template<class Entry , bool FastIndex>
Entry* carl::CompactTree< Entry, FastIndex >::_array
private

Definition at line 188 of file CompactTree.h.

◆ _capacityEnd

template<class Entry , bool FastIndex>
Node carl::CompactTree< Entry, FastIndex >::_capacityEnd
private

Definition at line 190 of file CompactTree.h.

◆ _lastLeaf

template<class Entry , bool FastIndex>
Node carl::CompactTree< Entry, FastIndex >::_lastLeaf
private

Definition at line 189 of file CompactTree.h.

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