Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
interval_trees::fenwick::FenwickTree< ValueType, Operation > Class Template Reference

#include <fenwick.h>

List of all members.

Public Types

typedef size_t SizeType

Public Member Functions

void initialize (FenwickDirection type_, size_t size, const ValueType &initial)
void update (SizeType pos, ValueType value)
ValueType get_on_interval (SizeType pos)

Private Member Functions

SizeType _advance (SizeType pos, FenwickDirection direction)
SizeType last_one (SizeType x)

Private Attributes

std::vector< ValueType > data
FenwickDirection type

Detailed Description

template<typename ValueType, class Operation>
class interval_trees::fenwick::FenwickTree< ValueType, Operation >

General Fenwick interval tree.

can update position pos by applying "Operation" can report an "Operation" over values at interval [0..pos] or [pos..size) (not both at once)

Note: sensible operations are only plus, min, max

Precondition:
  • If you need a custom operation, you will need following concept: operation on [a..b) == operation( operation on [a..c), operation on [c..b) )

Member Typedef Documentation

template<typename ValueType, class Operation>
typedef size_t interval_trees::fenwick::FenwickTree< ValueType, Operation >::SizeType

Member Function Documentation

template<typename ValueType, class Operation>
SizeType interval_trees::fenwick::FenwickTree< ValueType, Operation >::_advance ( SizeType  pos,
FenwickDirection  direction 
) [inline, private]

advance to next position in the structure

template<typename ValueType, class Operation>
ValueType interval_trees::fenwick::FenwickTree< ValueType, Operation >::get_on_interval ( SizeType  pos) [inline]

Return value of operation on interval [0, pos] or [pos, size) depending on the type of a tree

template<typename ValueType, class Operation>
void interval_trees::fenwick::FenwickTree< ValueType, Operation >::initialize ( FenwickDirection  type_,
size_t  size,
const ValueType &  initial 
) [inline]

Initialize fenwick tree

template<typename ValueType, class Operation>
SizeType interval_trees::fenwick::FenwickTree< ValueType, Operation >::last_one ( SizeType  x) [inline, private]
Returns:
last set bit of an integer
template<typename ValueType, class Operation>
void interval_trees::fenwick::FenwickTree< ValueType, Operation >::update ( SizeType  pos,
ValueType  value 
) [inline]

Update value on position by value using operator Operation::operation(old, value);


Member Data Documentation

template<typename ValueType, class Operation>
std::vector<ValueType> interval_trees::fenwick::FenwickTree< ValueType, Operation >::data [private]
template<typename ValueType, class Operation>
FenwickDirection interval_trees::fenwick::FenwickTree< ValueType, Operation >::type [private]

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