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_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 operator()(node &_self)

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

struct fill_nonleaf_value_handler

Public Functions

template<>
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

template<>
void operator()(node &_self)

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

struct leaf_value_type

Public Functions

template<>
bool operator==(const leaf_value_type &r) const

Public Members

template<>
key_type key

template<>
data_chain_type *data_chain

struct nonleaf_value_type

Public Functions

template<>
bool operator==(const nonleaf_value_type &r) const

Public Members

template<>
key_type low

template<>
key_type high

low range value (inclusive)

template<>
data_chain_type *data_chain

high range value (non-inclusive)

class search_result : public mdds::segment_tree<_Key, _Value>::search_result_base

Public Functions

template<>
search_result::iterator begin()

template<>
search_result::iterator end()

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

Public Functions

template<>
iterator()

Friends

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

class search_result_inserter : public std::unary_function<data_chain_type *, void>

Public Functions

template<>
search_result_inserter(search_result_base &result)

template<>
void operator()(data_chain_type *node_data)

class search_result_vector_inserter : public std::unary_function<data_chain_type *, void>

Public Functions

template<>
search_result_vector_inserter(search_result_type &result)

template<>
void operator()(data_chain_type *node_data)