mdds::segment_tree< KeyT, ValueT > Class Template Reference

#include <segment_tree.hpp>

Classes
class	search_results
struct	integrity_check_properties

Public Types
using	key_type = KeyT
using	value_type = ValueT
using	size_type = std::size_t
using	node = st::detail::node<key_type, leaf_value_type>
using	node_ptr = typename node::node_ptr
using	nonleaf_node = typename st::detail::nonleaf_node<key_type, nonleaf_value_type>

Public Member Functions
	segment_tree (const segment_tree &r)
	segment_tree (segment_tree &&r)=default
segment_tree &	operator= (const segment_tree &r)
segment_tree &	operator= (segment_tree &&r) noexcept(nothrow_move_assignable_v)
bool	operator== (const segment_tree &r) const
bool	operator!= (const segment_tree &r) const
bool	valid_tree () const noexcept
void	build_tree ()
void	insert (key_type start_key, key_type end_key, value_type value)
search_results	search (const key_type &point) const
void	erase (const typename search_results::const_iterator &pos)
template<typename Pred>
size_type	erase_if (Pred pred)
void	swap (segment_tree &r) noexcept(nothrow_swappable_v)
void	clear ()
size_type	size () const
bool	empty () const
size_type	leaf_size () const noexcept(noexcept(st::detail::count_leaf_nodes< size_type >(m_left_leaf.get(), m_right_leaf.get())))
std::string	to_string () const
std::vector< key_type >	boundary_keys () const
void	check_integrity (const integrity_check_properties &props) const

Detailed Description

template<typename KeyT, typename ValueT>
class mdds::segment_tree< KeyT, ValueT >

Segment tree is a data structure designed for storing one-dimensional intervals or segments, either overlapping or non-overlapping. It is useful for detecting all the segments that contain a specific point.

Each segment has start and end positions where the start position is inclusive while the end position is not. This segment tree implementation allows associating a value with each segment so that you can use it as an associative container.

Template Parameters

KeyT	Key type. The key type must be copyable. If it's moveable then it gets moved instead of copied where possible. Additionally, the key type must support the <, <= and == operators. To use to_string(), the key type must support the ostream operator.
ValueT	Value type. The value type does not need to be copyable but must be at least moveable. Additionally, the value type must support the == operator. To use to_string(), the value type must support the ostream operator.

Member Typedef Documentation

key_type

template<typename KeyT, typename ValueT>

using mdds::segment_tree< KeyT, ValueT >::key_type = KeyT

The key type must be copyable, and may be moveable.

value_type

template<typename KeyT, typename ValueT>

using mdds::segment_tree< KeyT, ValueT >::value_type = ValueT

The value type must be either copyable or moveable.

Member Function Documentation

boundary_keys()

template<typename KeyT, typename ValueT>

std::vector< key_type > mdds::segment_tree< KeyT, ValueT >::boundary_keys

(

)

const

Create a sorted sequence of unique boundary keys. A boundary key is a key that is either the start or the end key of a stored segment.

Returns

A sorted sequence of unique boundary keys.

build_tree()

template<typename KeyT, typename ValueT>

void mdds::segment_tree< KeyT, ValueT >::build_tree

(

)

Build or re-build a tree based on the current set of segments.

Note

Building a tree with no logical stored segments will not result in a valid tree.

clear()

template<typename KeyT, typename ValueT>

void mdds::segment_tree< KeyT, ValueT >::clear

(

)

Remove all segments data.

empty()

template<typename KeyT, typename ValueT>

bool mdds::segment_tree< KeyT, ValueT >::empty

(

)

const

Return whether or not the container stores any segments or none at all.

erase()

template<typename KeyT, typename ValueT>

void mdds::segment_tree< KeyT, ValueT >::erase

(

const typename search_results::const_iterator &

pos

)

Remove a segment referenced by an iterator. Calling this method will not invalidate the tree; however, you might want to re-build the tree to compact its size if you have removed a large number of segments.

Parameters

pos	Position that references the segment to be removed.

erase_if()

template<typename KeyT, typename ValueT>

template<typename Pred>

size_type mdds::segment_tree< KeyT, ValueT >::erase_if

(

Pred

pred

)

Remove all segments that satisfy a predicate.

The predicate must take three parameters that are a start position, end position and a value of a segment in this order. The first two parameters are of the same type as the key_type while the last parameter is of the same type as the value_type.

// Given int as key_type and std::string as value_type, this predicate removes
// all the segments that 1) contain 5 and 2) store a value of "A".
auto pred = [](int start, int end, const std::string& value) {
    return start <= 5 && 5 < end && value == "A";
};

Parameters

pred	Predicate that tests each segment. A segment that evaluates true by the predicate gets removed.

Returns

Number of erased elements.

insert()

template<typename KeyT, typename ValueT>

void mdds::segment_tree< KeyT, ValueT >::insert	(	key_type	start_key,
		key_type	end_key,
		value_type	value )

Insert a new segment. Duplicate segments are allowed.

Parameters

start_key	start key of a segment. The value is inclusive.
end_key	end key of a segment. The value is non-inclusive. It must be greater than the start key.
value	value to associate with this segment.

leaf_size()

template<typename KeyT, typename ValueT>

size_type mdds::segment_tree< KeyT, ValueT >::leaf_size ( ) const

inlinenoexcept

Return the number of leaf nodes.

Returns

number of leaf nodes.

operator==()

template<typename KeyT, typename ValueT>

bool mdds::segment_tree< KeyT, ValueT >::operator==

(

const segment_tree< KeyT, ValueT > &

r

)

const

Check equality with another instance.

Note

Equality between two segment_tree instances is evaluated by comparing the logically stored segments only; the tree parts of the structures are not compared.

search()

template<typename KeyT, typename ValueT>

search_results mdds::segment_tree< KeyT, ValueT >::search

(

const key_type &

point

)

const

Search the tree to find all the segments that contain a specified point.

Parameters

point

A point to search the tree with.

Returns

Results object containing the segments that contain the specified point.

Note

You need to have a valid tree prior to calling this method. Call build_tree() to build one. To check if you have a valid tree, call valid_tree() and see if it returns true.

A point value can be any value allowed by the key_type. If the point is outside of the range of the tree, empty results will be returned.

size()

template<typename KeyT, typename ValueT>

size_type mdds::segment_tree< KeyT, ValueT >::size

(

)

const

Return the number of segments currently stored in this container.

swap()

template<typename KeyT, typename ValueT>

void mdds::segment_tree< KeyT, ValueT >::swap ( segment_tree< KeyT, ValueT > & r )

noexcept

Exchange the content of the tree with that of another.

Parameters

r	Another tree instance to swap the contents with.

to_string()

template<typename KeyT, typename ValueT>

std::string mdds::segment_tree< KeyT, ValueT >::to_string

(

)

const

Create a string representation of the internal state of a tree.

Returns

String representation of the internal state of a tree.

valid_tree()

template<typename KeyT, typename ValueT>

bool mdds::segment_tree< KeyT, ValueT >::valid_tree ( ) const

inlinenoexcept

Check whether or not the internal tree is in a valid state. The tree must be valid in order to perform searches.

Returns

true if the tree is valid, false otherwise.