mdds
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | List of all members
mdds::segment_tree< KeyT, ValueT > Class Template Reference

#include <segment_tree.hpp>

Classes

struct  integrity_check_properties
 
class  search_results
 

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)
 
segment_treeoperator= (const segment_tree &r)
 
segment_treeoperator= (segment_tree &&r)
 
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
 
void clear ()
 
size_type size () const
 
bool empty () const
 
size_type leaf_size () const
 
std::string to_string () const
 
std::vector< key_typeboundary_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
KeyTKey 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.
ValueTValue 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
posPosition 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
predPredicate 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_keystart key of a segment. The value is inclusive.
end_keyend key of a segment. The value is non-inclusive. It must be greater than the start key.
valuevalue to associate with this segment.

◆ leaf_size()

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

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
pointA 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
rAnother 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.