The Dynamic Segment Tree class. More...

#include <dynamic_segment_tree.hpp>

Public Types
using	KeyT = typename Node::KeyT

using	ValueT = typename Node::ValueT

using	AggValueT = typename Node::AggValueT

using	MyClass = DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >

template<bool reverse>
using	const_iterator = typename InnerTree::template const_iterator< reverse >

template<bool reverse>
using	iterator = typename InnerTree::template iterator< reverse >

Public Member Functions
	DynamicSegmentTree (MyClass &&other)
	Move constructor.

	DynamicSegmentTree ()
	Default constructor.

void	insert (Node &n)
	Insert an interval into the dynamic segment tree. More...

void	remove (Node &n)
	Removes an intervals from the dynamic segment tree. More...

bool	empty () const
	Returns whether the dynamic segment tree is empty. More...

AggValueT	query (const typename Node::KeyT &x) const noexcept
	Perform a stabbing query at point x. More...

template<class Combiner >
Combiner	get_combiner () const

template<class Combiner >
Combiner	get_combiner (const typename Node::KeyT &lower, const typename Node::KeyT &upper, bool lower_closed=true, bool upper_closed=false) const

template<class Combiner >
Combiner::ValueT	get_combined () const

template<class Combiner >
Combiner::ValueT	get_combined (const typename Node::KeyT &lower, const typename Node::KeyT &upper, bool lower_closed=true, bool upper_closed=false) const

const_iterator< false >	cbegin () const

const_iterator< false >	cend () const

const_iterator< false >	begin () const

iterator< false >	begin ()

const_iterator< false >	end () const

iterator< false >	end ()

const_iterator< true >	crbegin () const

const_iterator< true >	crend () const

const_iterator< true >	rbegin () const

iterator< true >	rbegin ()

const_iterator< true >	rend () const

iterator< true >	rend ()

const_iterator< false >	lower_bound_event (const typename Node::KeyT &key) const

iterator< false >	lower_bound_event (const typename Node::KeyT &key)

const_iterator< false >	upper_bound_event (const typename Node::KeyT &key) const

iterator< false >	upper_bound_event (const typename Node::KeyT &key)

void	clear ()
	Removes all elements from the tree. More...

void	dbg_verify () const

template<class Combiner >
void	dbg_verify_max_combiner () const

void	dbg_print_inner_tree () const

std::stringstream &	dbg_get_dot () const

Detailed Description

template<class Node, class NodeTraits, class Combiners, class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>
class ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >

The Dynamic Segment Tree class.

This class provides a dynamic version of a segment tree. For details on the implementation, see DOCTODO. The dynamic segment tree provides the following operations:

Querying for the aggregate value ta a point x (a "stabbing query") in O(log n) * A
Insertion of a new interval in O(log n) * A
Deletion of an interval in O(log n) * A

where n is the number of intervals in the dynamic segment tree and A is the time it takes to aggregate a value, i.e., compute operator+(AggValueT, ValueT).

The DynamicSegmentTree can be based either on a red-black tree (the RBTree), or on a Zip Tree (the ZTree). By default, the red-black tree is used. However, especially for applications where segments are moved frequently, the Zip Tree has proven to be more efficient. You select the underlying tree via the TreeSelector template parameter.

DOCTODO combiners

Template Parameters

Node	The node class in your tree, must be derived from DynSegTreeNodeBase
NodeTraits	The node traits for your node class, must be derived from DynSegTreeNodeTraits
Options	Options for this tree. See DOCTODO for details.
TreeSelector	Specifies which balanced binary tree implementation to use for the underlying tree. Must be one of UseRBTree<...> (to use the red-black tree), UseZipTree<...> (to use the zip tree) or UseWBTree<...> (to use the weight-balanced tree). You need to specify the same selector at the DynSegTreeNodeBase!
Tag	The tag of this tree. Allows to insert the same node in multiple dynamic segment trees. See DOCTODO for details.

Member Function Documentation

◆ begin()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

const_iterator<false> ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::begin ( ) const

Returns an iterator pointing to the smallest InnerNode representing a start or end event.

◆ cbegin()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

const_iterator<false> ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::cbegin ( ) const

Returns an iterator pointing to the smallest InnerNode representing a start or end event.

◆ cend()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

const_iterator<false> ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::cend ( ) const

Returns an iterator pointing after the largest InnerNode representing a start or end event.

◆ clear()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

void ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::clear ( )

Removes all elements from the tree.

TODO write a test for this method

Removes all elements from the tree.

◆ crbegin()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

const_iterator<true> ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::crbegin ( ) const

Returns an reverse iterator pointing to the largest InnerNode representing a start or end event.

◆ crend()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

const_iterator<true> ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::crend ( ) const

Returns an reverse iterator pointing before the smallest InnerNode representing a start or end event.

◆ empty()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

bool ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::empty ( ) const

Returns whether the dynamic segment tree is empty.

This method runs in O(1).

Returns: true if the dynamic segment tree is empty, false otherwise

◆ end()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

const_iterator<false> ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::end ( ) const

Returns an iterator pointing after the largest InnerNode representing a start or end event.

◆ insert()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

void ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::insert ( Node & n )

Insert an interval into the dynamic segment tree.

This inserts the interval represented by the node n into the dynamic segment tree. The interval may not be empty.

Parameters

n	The node representing the interval being inserted

◆ lower_bound_event()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

const_iterator<false> ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::lower_bound_event ( const typename Node::KeyT & key ) const

Returns an iterator to the first event the key of which is not less than <key>

Parameters

key	The key to search for.

Returns: An iterator to the first event the key of which is not less than <key>

◆ query()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

AggValueT ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::query ( const typename Node::KeyT & x ) const

noexcept

Perform a stabbing query at point x.

This query asks for the aggregate value over all intervals containing point x. This is a "stabbing query".

Parameters

x	The point to query for

Returns: The aggregated value for all intervals containing x

◆ rbegin()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

const_iterator<true> ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::rbegin ( ) const

Returns an reverse iterator pointing to the largest InnerNode representing a start or end event.

◆ remove()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

void ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::remove ( Node & n )

Removes an intervals from the dynamic segment tree.

Removes the (previously inserted) node n from the dynamic segment tree

Parameters

n	The node to be removed

◆ rend()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

const_iterator<true> ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::rend ( ) const

Returns an reverse iterator pointing before the smallest InnerNode representing a start or end event.

◆ upper_bound_event()

template<class Node , class NodeTraits , class Combiners , class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>

const_iterator<false> ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >::upper_bound_event ( const typename Node::KeyT & key ) const

Returns an iterator to the first event the key of which is greater than <key>

Parameters

key	The key to search for.

Returns: An iterator to the first event the key of which is greater than <key>

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

Detailed Description

template<class Node, class NodeTraits, class Combiners, class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int> class ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >

Member Function Documentation

◆ begin()

◆ cbegin()

◆ cend()

◆ clear()

◆ crbegin()

◆ crend()

◆ empty()

◆ end()

◆ insert()

◆ lower_bound_event()

◆ query()

◆ rbegin()

◆ remove()

◆ rend()

◆ upper_bound_event()

template<class Node, class NodeTraits, class Combiners, class Options = DefaultOptions, class TreeSelector = UseDefaultRBTree, class Tag = int>
class ygg::DynamicSegmentTree< Node, NodeTraits, Combiners, Options, TreeSelector, Tag >