mdds
|
#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_tree & | operator= (const segment_tree &r) |
segment_tree & | operator= (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_type > | boundary_keys () const |
void | check_integrity (const integrity_check_properties &props) const |
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.
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. |
using mdds::segment_tree< KeyT, ValueT >::key_type = KeyT |
The key type must be copyable, and may be moveable.
using mdds::segment_tree< KeyT, ValueT >::value_type = ValueT |
The value type must be either copyable or moveable.
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.
void mdds::segment_tree< KeyT, ValueT >::build_tree | ( | ) |
Build or re-build a tree based on the current set of segments.
void mdds::segment_tree< KeyT, ValueT >::clear | ( | ) |
Remove all segments data.
bool mdds::segment_tree< KeyT, ValueT >::empty | ( | ) | const |
Return whether or not the container stores any segments or none at all.
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.
pos | Position that references the segment to be removed. |
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.
pred | Predicate that tests each segment. A segment that evaluates true by the predicate gets removed. |
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.
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. |
size_type mdds::segment_tree< KeyT, ValueT >::leaf_size | ( | ) | const |
Return the number of leaf nodes.
bool mdds::segment_tree< KeyT, ValueT >::operator== | ( | const segment_tree< KeyT, ValueT > & | r | ) | const |
Check equality with another instance.
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.
point | A point to search the tree with. |
size_type mdds::segment_tree< KeyT, ValueT >::size | ( | ) | const |
Return the number of segments currently stored in this container.
|
noexcept |
Exchange the content of the tree with that of another.
r | Another tree instance to swap the contents with. |
std::string mdds::segment_tree< KeyT, ValueT >::to_string | ( | ) | const |
Create a string representation of the internal state of a tree.
|
inlinenoexcept |
Check whether or not the internal tree is in a valid state. The tree must be valid in order to perform searches.