Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
#include <simple_max.h>
Public Member Functions | |
SimpleMaxTree () | |
void | _clear () |
void | initialize (SizeType size) |
void | initialize (SizeType size_, const T &default_value) |
T | get (SizeType pos) |
void | set (SizeType pos, T value) |
T | get_max (SizeType left, SizeType right) |
Private Types | |
typedef std::vector< T >::size_type | SizeType |
Private Attributes | |
SizeType | base |
SizeType | original_size |
std::vector< T > | data |
This implementation of simple interval tree with following operations:
Implementation - specific details: This implementation is solely non-recursive and uses bottom-up approach instead of standard top-bottom recursive calls. Because of lack of recursion, you can't (easily) adapt this implementation to change whole intervals.
typedef std::vector<T>::size_type interval_trees::simple::SimpleMaxTree< T >::SizeType [private] |
SizeType is enough to store index to vector.
interval_trees::simple::SimpleMaxTree< T >::SimpleMaxTree | ( | ) | [inline] |
void interval_trees::simple::SimpleMaxTree< T >::_clear | ( | ) | [inline] |
Clear tree and set it's size to zero.
T interval_trees::simple::SimpleMaxTree< T >::get | ( | SizeType | pos | ) | [inline] |
get value at position pos
T interval_trees::simple::SimpleMaxTree< T >::get_max | ( | SizeType | left, |
SizeType | right | ||
) | [inline] |
get maximum over interval [left, right)
Note: right should be greater than left!
Implementation details: we walk simultaneously from the left and right up the heap-structure until we meet at the same point
void interval_trees::simple::SimpleMaxTree< T >::initialize | ( | SizeType | size | ) | [inline] |
Shorthand for initialization
void interval_trees::simple::SimpleMaxTree< T >::initialize | ( | SizeType | size_, |
const T & | default_value | ||
) | [inline] |
Initialize tree
void interval_trees::simple::SimpleMaxTree< T >::set | ( | SizeType | pos, |
T | value | ||
) | [inline] |
set value at position pos
SizeType interval_trees::simple::SimpleMaxTree< T >::base [private] |
Number of leaves in heap structure.
Also, pos+base is the index of leaf in data. Note that 2*base is the size of the whole tree.
std::vector<T> interval_trees::simple::SimpleMaxTree< T >::data [private] |
The data of the tree
SizeType interval_trees::simple::SimpleMaxTree< T >::original_size [private] |
The requested size of the structure, we won't allow access outside this range