Loading...
Searching...
No Matches
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

inline noexcept

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

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