API Reference¶

template<typename KeyT, typename ValueT> class segment_tree¶

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.

Public Types

using key_type = KeyT ¶: The key type must be copyable, and may be moveable.

using value_type = ValueT ¶: The value type must be either copyable or moveable.

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 Functions

segment_tree() noexcept(nothrow_default_constructible_v)¶

segment_tree(const segment_tree &r)¶

segment_tree(segment_tree &&r) = default¶

~segment_tree()¶

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¶: 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.

bool operator!=(const segment_tree &r) const¶

inline bool valid_tree() const noexcept¶

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.

void 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.

void 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.

search_results search(const key_type &point) const¶

Search the tree to find all the segments that contain a 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.

Note

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.

Parameters:: point – A point to search the tree with.
Returns:: Results object containing the segments that contain the specified point.

void 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.

template<typename Pred> size_type 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.

void swap(segment_tree &r) noexcept(nothrow_swappable_v)¶

Exchange the content of the tree with that of another.

Parameters:: r – Another tree instance to swap the contents with.

void clear()¶: Remove all segments data.

size_type size() const¶: Return the number of segments currently stored in this container.

bool empty() const¶: Return whether or not the container stores any segments or none at all.

inline size_type leaf_size() const noexcept(noexcept(st::detail::count_leaf_nodes<size_type>(m_left_leaf.get(), m_right_leaf.get())))¶

Return the number of leaf nodes.

Returns:: number of leaf nodes.

std::string to_string() const¶

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

Returns:: String representation of the internal state of a tree.

std::vector<key_type> 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.

void check_integrity(const integrity_check_properties &props) const¶

struct integrity_check_properties¶

Public Members

std::vector<leaf_node> leaf_nodes¶

struct leaf_node¶

Public Members

key_type key = {}¶

std::vector<value_type> value_chain¶

class search_results : public mdds::segment_tree<KeyT, ValueT>::search_results_base¶

Public Functions

inline bool empty() const¶

Check if this results pool is empty or not.

Returns:: true if this results pool is empty, otherwise false.

inline size_type size() const¶

Count the number of results in this results pool.

Returns:: number of results in this results pool.

inline search_results::const_iterator begin() const¶

inline search_results::const_iterator end() const¶

class const_iterator : public mdds::segment_tree<KeyT, ValueT>::const_iterator_base¶

Public Functions

inline const_iterator()¶

inline const_iterator(const const_iterator &r)¶

inline const_iterator &operator=(const const_iterator &r)¶

Friends

friend class segment_tree< KeyT, ValueT >::search_results