Segment Tree

API Reference

template<typename _Key, typename _Value>
class segment_tree

Public Types

typedef _Key key_type

typedef _Value value_type

typedef size_t size_type

typedef std::vector<value_type> search_results_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.

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

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

Returns:

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_results_type &result) const

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

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.

Returns:

true if the search is performed successfully, false if the search has ended prematurely due to error conditions.

search_results search(key_type point) const

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

Parameters:

point – specified point value

Returns:

object containing the result of the search, which can be accessed via iterator.

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.

Returns:

number of leaf nodes.

struct dispose_handler

Public Functions

inline void operator()(node &_self)

inline void operator()(__st::nonleaf_node<segment_tree> &_self)

struct fill_nonleaf_value_handler

Public Functions

inline void operator()(__st::nonleaf_node<segment_tree> &_self, const __st::node_base *left_node, const __st::node_base *right_node)

struct init_handler

Public Functions

inline void operator()(node &_self)

inline void operator()(__st::nonleaf_node<segment_tree> &_self)

struct leaf_value_type

Public Functions

inline bool operator==(const leaf_value_type &r) const

Public Members

key_type key

data_chain_type *data_chain

struct nonleaf_value_type

Public Functions

inline bool operator==(const nonleaf_value_type &r) const

Public Members

key_type low

key_type high

low range value (inclusive)

data_chain_type *data_chain

high range value (non-inclusive)

class search_result_inserter

Public Functions

inline search_result_inserter(search_results_base &result)

inline void operator()(data_chain_type *node_data)

class search_result_vector_inserter

Public Functions

inline search_result_vector_inserter(search_results_type &result)

inline void operator()(data_chain_type *node_data)

class search_results : public mdds::segment_tree<_Key, _Value>::search_results_base

Public Functions

inline search_results::iterator begin()

inline search_results::iterator end()

class iterator : public mdds::segment_tree<_Key, _Value>::iterator_base

Public Functions

inline iterator()

Friends

friend class segment_tree< _Key, _Value >::search_results