Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
interval_trees::simple::SimpleMaxTree< T > Class Template Reference

#include <simple_max.h>

List of all members.

Public Member Functions

 SimpleMaxTree ()
void _clear ()
void initialize (SizeType size)
void initialize (SizeType size_, const T &default_value)
get (SizeType pos)
void set (SizeType pos, T value)
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

Detailed Description

template<typename T>
class interval_trees::simple::SimpleMaxTree< T >

This implementation of simple interval tree with following operations:

  • can change element at position i
  • can compute maximum over some range [left, right)

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.


Member Typedef Documentation

template<typename T >
typedef std::vector<T>::size_type interval_trees::simple::SimpleMaxTree< T >::SizeType [private]

SizeType is enough to store index to vector.


Constructor & Destructor Documentation

template<typename T >
interval_trees::simple::SimpleMaxTree< T >::SimpleMaxTree ( ) [inline]

Member Function Documentation

template<typename T >
void interval_trees::simple::SimpleMaxTree< T >::_clear ( ) [inline]

Clear tree and set it's size to zero.

template<typename T >
T interval_trees::simple::SimpleMaxTree< T >::get ( SizeType  pos) [inline]

get value at position pos

template<typename T >
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

template<typename T >
void interval_trees::simple::SimpleMaxTree< T >::initialize ( SizeType  size) [inline]

Shorthand for initialization

See also:
initialize(size, default_value
template<typename T >
void interval_trees::simple::SimpleMaxTree< T >::initialize ( SizeType  size_,
const T &  default_value 
) [inline]

Initialize tree

template<typename T >
void interval_trees::simple::SimpleMaxTree< T >::set ( SizeType  pos,
value 
) [inline]

set value at position pos


Member Data Documentation

template<typename T >
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.

template<typename T >
std::vector<T> interval_trees::simple::SimpleMaxTree< T >::data [private]

The data of the tree

template<typename T >
SizeType interval_trees::simple::SimpleMaxTree< T >::original_size [private]

The requested size of the structure, we won't allow access outside this range


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines