ygg::MaxCombiner< KeyType, ValueType > Class Template Reference

A combiner that allows to retrieve the maximum value over any range. More...

#include <dynamic_segment_tree.hpp>

Public Types
using	ValueT = ValueType
using	KeyT = KeyType
using	MyType = MaxCombiner< KeyT, ValueT >

Public Member Functions
bool	collect_left (const KeyT my_point, const MyType *left_child_combiner, const ValueType edge_val)
	Combines this MaxCombiner with a value, possibly of a child node. More...
bool	collect_right (const KeyT my_point, const MyType *right_child_combiner, const ValueType edge_val)
	Combines this MaxCombiner with a value, possibly of a child node. More...
bool	traverse_left_edge_up (const KeyT new_point, const ValueT edge_val)
	Aggregates a value into the max value stored in this combiner. More...
bool	traverse_right_edge_up (const KeyT new_point, const ValueT edge_val)
	Aggregates a value into the max value stored in this combiner. More...
bool	rebuild (KeyT my_point, const MyType *left_child_combiner, ValueT left_edge_val, const MyType *right_child_combiner, ValueT right_edge_val)
	Rebuilds the value in this MaxCombiner from values of its two children's MaxCombiners. More...
ValueT	get () const noexcept
	Returns the currently stored combined value in this combiner. More...
std::string	get_dbg_value () const

Static Public Member Functions
static std::string	get_name ()

Detailed Description

template<class KeyType, class ValueType>
class ygg::MaxCombiner< KeyType, ValueType >

A combiner that allows to retrieve the maximum value over any range.

This is a combiner (see TODO for what a combiner is) that, when added to a Dynamic Segment Tree, allows you to efficiently retrieve the maximum aggregate value over any range in your segment tree.

Template Parameters

KeyType	The type of the interval borders
ValueType	The type of values associated with your intervals

Member Function Documentation

collect_left()

template<class KeyType , class ValueType >

bool ygg::MaxCombiner< KeyType, ValueType >::collect_left	(	const KeyT	my_point,
		const MyType *	left_child_combiner,
		const ValueType	edge_val
	)

Combines this MaxCombiner with a value, possibly of a child node.

This sets the maximum currently stored at this combiner to the maximum of the currently stored value and the value of left_child_combiner plus edge_val.

Usually, a will be the value of the MaxCombiner of a child of the node that this combiner belongs to. edge_val will then be the agg_left value of the node this combiner belongs to.

Parameters

my_point	The point of the inner node that this MaxCombiner is associated with
left_child_combiner	The MaxCombiner belonging to the left child of this node
edge_val	The aggregate value of the left edge going out of this node

Returns

FIXME ignored for now

collect_right()

template<class KeyType , class ValueType >

bool ygg::MaxCombiner< KeyType, ValueType >::collect_right	(	const KeyT	my_point,
		const MyType *	right_child_combiner,
		const ValueType	edge_val
	)

Combines this MaxCombiner with a value, possibly of a child node.

This sets the maximum currently stored at this combiner to the maximum of the currently stored value and the value of right_child_combiner plus edge_val.

Usually, a will be the value of the MaxCombiner of a child of the node that this combiner belongs to. edge_val will then be the agg_right value of the node this combiner belongs to.

Parameters

my_point	The point of the inner node that this MaxCombiner is associated with
right_child_combiner	The MaxCombiner belonging to the right child of this node
edge_val	The aggregate value of the right edge going out of this node

Returns

FIXME ignored for now

get()

template<class KeyType , class ValueType >

ValueT ygg::MaxCombiner< KeyType, ValueType >::get ( ) const

noexcept

Returns the currently stored combined value in this combiner.

Returns

the currently stored combined value in this combiner

rebuild()

template<class KeyType , class ValueType >

bool ygg::MaxCombiner< KeyType, ValueType >::rebuild	(	KeyT	my_point,
		const MyType *	left_child_combiner,
		ValueT	left_edge_val,
		const MyType *	right_child_combiner,
		ValueT	right_edge_val
	)

Rebuilds the value in this MaxCombiner from values of its two children's MaxCombiners.

This sets the maximum currently stored at this combiner to the maximum of the left_child_combiner's value plus left_edge_val and right_child_combiner's value plus right_edge_val.

Parameters

my_point	The point of the node this combiner belongs to
left_child_combiner	The MaxCombiner of the left child of this node
left_edge_val	The agg_left value of this node
right_child_combiner	The MaxCombiner of the right child of this node
left_edge_val	The agg_right value of this node

Returns

FIXME ignored for now

traverse_left_edge_up()

template<class KeyType , class ValueType >

bool ygg::MaxCombiner< KeyType, ValueType >::traverse_left_edge_up	(	const KeyT	new_point,
		const ValueT	edge_val
	)

Aggregates a value into the max value stored in this combiner.

This adds edge_val to the maximum currently stored in this combiner. This is used when traversing up a left edge in the tree.

Parameters

new_point	The point of the node we traversed into
edge_val	The value of the edge we traversed

Returns

FIXME ignored for now

traverse_right_edge_up()

template<class KeyType , class ValueType >

bool ygg::MaxCombiner< KeyType, ValueType >::traverse_right_edge_up	(	const KeyT	new_point,
		const ValueT	edge_val
	)

Aggregates a value into the max value stored in this combiner.

This adds edge_val to the maximum currently stored in this combiner. This is used when traversing up a right edge in the tree.

Parameters

new_point	The point of the node we traversed into
edge_val	The value of the edge we traversed

Returns

FIXME ignored for now

---

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

• /home/lukas/src/intervaltree/ygg/src/dynamic_segment_tree.hpp