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