Segment Tree

API Reference

template <typename _Key, typename _Value>
class mdds::segment_tree

Public Types

typedef _Key key_type
typedef _Value value_type
typedef size_t size_type
typedef std::vector<value_type> search_result_type
typedef std::vector<value_type> data_chain_type
typedef std::unordered_map<value_type, std::pair<key_type, key_type>> segment_map_type
typedef std::map<value_type, std::pair<key_type, key_type>> sorted_segment_map_type
typedef __st::node<segment_tree> node
typedef node::node_ptr node_ptr
typedef __st::nonleaf_node<segment_tree> nonleaf_node

Public Functions

segment_tree()
segment_tree(const segment_tree &r)
~segment_tree()
bool operator==(const segment_tree &r) const

Equality between two segment_tree instances is evaluated by comparing the segments that they store. The trees are not compared.

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

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

Return
true if the tree is valid, false otherwise.

void build_tree()

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

bool insert(key_type begin_key, key_type end_key, value_type pdata)

Insert a new segment.

Parameters
  • begin_key -

    begin point of the segment. The value is inclusive.

  • end_key -

    end point of the segment. The value is non-inclusive.

  • pdata -

    pointer to the data instance associated with this segment. Note that the caller must manage the life cycle of the data instance.

bool search(key_type point, search_result_type &result) const

Search the tree and collect all segments that include a specified point.

Return
true if the search is performed successfully, false if the search has ended prematurely due to error conditions.
Parameters
  • point -

    specified point value

  • result -

    doubly-linked list of data instances associated with the segments that include the specified point. Note that the search result gets appended to the list; the list will not get emptied on each search. It is caller’s responsibility to empty the list before passing it to this method in case the caller so desires.

search_result search(key_type point) const

Search the tree and collect all segments that include a specified point.

Return
object containing the result of the search, which can be accessed via iterator.
Parameters
  • point -

    specified point value

void remove(value_type value)

Remove a segment that matches by the value. This will not invalidate the tree; however, if you have removed lots of segments, you might want to re-build the tree to shrink its size.

Parameters
  • value -

    value to remove a segment by.

void clear()

Remove all segments data.

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

size_t leaf_size() const

Return the number of leaf nodes.

Return
number of leaf nodes.

struct dispose_handler

Public Functions

template<>
void mdds::segment_tree<_Key, _Value>::dispose_handler::operator()(node &_self)
template<>
void mdds::segment_tree<_Key, _Value>::dispose_handler::operator()(__st::nonleaf_node<segment_tree> &_self)
struct fill_nonleaf_value_handler

Public Functions

template<>
void mdds::segment_tree<_Key, _Value>::fill_nonleaf_value_handler::operator()(__st::nonleaf_node<segment_tree> &_self, const __st::node_base *left_node, const __st::node_base *right_node)
struct init_handler

Public Functions

template<>
void mdds::segment_tree<_Key, _Value>::init_handler::operator()(node &_self)
template<>
void mdds::segment_tree<_Key, _Value>::init_handler::operator()(__st::nonleaf_node<segment_tree> &_self)
struct leaf_value_type

Public Functions

template<>
bool mdds::segment_tree<_Key, _Value>::leaf_value_type::operator==(const leaf_value_type &r) const

Public Members

template<>
key_type mdds::segment_tree<_Key, _Value>::leaf_value_type::key
template<>
data_chain_type *mdds::segment_tree<_Key, _Value>::leaf_value_type::data_chain
struct nonleaf_value_type

Public Functions

template<>
bool mdds::segment_tree<_Key, _Value>::nonleaf_value_type::operator==(const nonleaf_value_type &r) const

Public Members

template<>
key_type mdds::segment_tree<_Key, _Value>::nonleaf_value_type::low
template<>
key_type mdds::segment_tree<_Key, _Value>::nonleaf_value_type::high

low range value (inclusive)

template<>
data_chain_type *mdds::segment_tree<_Key, _Value>::nonleaf_value_type::data_chain

high range value (non-inclusive)

class search_result

Inherits from mdds::segment_tree< _Key, _Value >::search_result_base

Public Functions

template<>
search_result::iterator mdds::segment_tree<_Key, _Value>::search_result::begin()
template<>
search_result::iterator mdds::segment_tree<_Key, _Value>::search_result::end()
class iterator

Inherits from mdds::segment_tree< _Key, _Value >::iterator_base

Public Functions

template<>
mdds::segment_tree<_Key, _Value>::search_result::iterator::iterator()

Friends

friend mdds::segment_tree::segment_tree< _Key, _Value >::search_result
class search_result_inserter

Inherits from std::unary_function< data_chain_type *, void >

Public Functions

template<>
mdds::segment_tree<_Key, _Value>::search_result_inserter::search_result_inserter(search_result_base &result)
template<>
void mdds::segment_tree<_Key, _Value>::search_result_inserter::operator()(data_chain_type *node_data)
class search_result_vector_inserter

Inherits from std::unary_function< data_chain_type *, void >

Public Functions

template<>
mdds::segment_tree<_Key, _Value>::search_result_vector_inserter::search_result_vector_inserter(search_result_type &result)
template<>
void mdds::segment_tree<_Key, _Value>::search_result_vector_inserter::operator()(data_chain_type *node_data)