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

#include <dynamic_segment_tree.hpp>

Public Types
using	ValueT = ValueType

using	KeyT = KeyType

using	MyType = RangedMaxCombiner< KeyT, ValueT >

Public Member Functions
bool	collect_left (KeyT my_point, const MyType *left_child_combiner, ValueType edge_val)
	Combines this RangedMaxCombiner with a value, possibly of a child node. More...

bool	collect_right (KeyT my_point, const MyType *right_child_combiner, ValueType edge_val)
	Combines this RangedMaxCombiner with a value, possibly of a child node. More...

bool	traverse_left_edge_up (KeyT new_point, ValueT edge_val)
	Aggregates a value into the max value stored in this combiner. More...

bool	traverse_right_edge_up (KeyT new_point, 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 RangedMaxCombiner from values of its two children's RangedMaxCombiner. More...

ValueT	get () const noexcept
	Returns the currently stored combined value in this combiner. More...

bool	is_left_border_valid () const noexcept
	Returns whether the maximum stored in this RangedMaxCombiner is bounded to the left. More...

bool	is_right_border_valid () const noexcept
	Returns whether the maximum stored in this RangedMaxCombiner is bounded to the right. More...

KeyT	get_left_border () const noexcept
	Returns the left border of the interval over which the maximum stored in this combiner occurs. More...

KeyT	get_right_border () const noexcept
	Returns the right border of the interval over which the maximum stored in this combiner occurs. 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::RangedMaxCombiner< KeyType, ValueType >

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

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. It will also tell you in which range the maximum occurs.

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::RangedMaxCombiner< KeyType, ValueType >::collect_left	(	KeyT	my_point,
		const MyType *	left_child_combiner,
		ValueType	edge_val
	)

Combines this RangedMaxCombiner 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 RangedMaxCombiner 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 RangedMaxCombiner is associated with
left_child_combiner	The RangedMaxCombiner 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::RangedMaxCombiner< KeyType, ValueType >::collect_right	(	KeyT	my_point,
		const MyType *	right_child_combiner,
		ValueType	edge_val
	)

Combines this RangedMaxCombiner 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 RangedMaxCombiner 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 RangedMaxCombiner is associated with
right_child_combiner	The RangedMaxCombiner 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::RangedMaxCombiner< KeyType, ValueType >::get ( ) const

noexcept

Returns the currently stored combined value in this combiner.

Returns: the currently stored combined value in this combiner

◆ get_left_border()

template<class KeyType , class ValueType >

KeyT ygg::RangedMaxCombiner< KeyType, ValueType >::get_left_border ( ) const

noexcept

Returns the left border of the interval over which the maximum stored in this combiner occurs.

If there are multiple disjunct intervals during which the maximum value occurs, the leftmost such interval is returned.

Returns: The left border of the maximum interval

◆ get_right_border()

template<class KeyType , class ValueType >

KeyT ygg::RangedMaxCombiner< KeyType, ValueType >::get_right_border ( ) const

noexcept

Returns the right border of the interval over which the maximum stored in this combiner occurs.

If there are multiple disjunct intervals during which the maximum value occurs, the leftmost such interval is returned.

Returns: The right border of the maximum interval

◆ is_left_border_valid()

template<class KeyType , class ValueType >

bool ygg::RangedMaxCombiner< KeyType, ValueType >::is_left_border_valid ( ) const

noexcept

Returns whether the maximum stored in this RangedMaxCombiner is bounded to the left.

If this method returns false, the value of get_left_border() is not meaningful, and the maximum stored in this combiner should be treated to extend all the way to the left.

Note: This should never happen with combiners retrieved via get_combiner().

Returns: See above

◆ is_right_border_valid()

template<class KeyType , class ValueType >

bool ygg::RangedMaxCombiner< KeyType, ValueType >::is_right_border_valid ( ) const

noexcept

Returns whether the maximum stored in this RangedMaxCombiner is bounded to the right.

If this method returns false, the value of get_right_border() is not meaningful, and the maximum stored in this combiner should be treated to extend all the way to the right.

Note: This should never happen with combiners retrieved via get_combiner().

Returns: See above

◆ rebuild()

template<class KeyType , class ValueType >

bool ygg::RangedMaxCombiner< 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 RangedMaxCombiner from values of its two children's RangedMaxCombiner.

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 RangedMaxCombiner of the left child of this node
left_edge_val	The agg_left value of this node
right_child_combiner	The RangedMaxCombiner 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::RangedMaxCombiner< KeyType, ValueType >::traverse_left_edge_up	(	KeyT	new_point,
		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::RangedMaxCombiner< KeyType, ValueType >::traverse_right_edge_up	(	KeyT	new_point,
		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

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

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

Member Function Documentation

◆ collect_left()

◆ collect_right()

◆ get()

◆ get_left_border()

◆ get_right_border()

◆ is_left_border_valid()

◆ is_right_border_valid()

◆ rebuild()

◆ traverse_left_edge_up()

◆ traverse_right_edge_up()

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