mdds::
segment_tree
¶Public Types
key_type
¶value_type
¶size_type
¶search_result_type
¶data_chain_type
¶segment_map_type
¶sorted_segment_map_type
¶node
¶nonleaf_node
¶Public Functions
segment_tree
()¶segment_tree
(const segment_tree &r)¶~segment_tree
()¶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.
operator!=
(const segment_tree &r) const¶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.
build_tree
()¶Build or re-build tree based on the current set of segments.
insert
(key_type begin_key, key_type end_key, value_type pdata)¶Insert a new segment.
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. search
(key_type point, search_result_type &result) const¶Search the tree and collect all segments that include a specified point.
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
(key_type point) const¶Search the tree and collect all segments that include a specified point.
point
: specified point valueremove
(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.
value
: value to remove a segment by. clear
()¶Remove all segments data.
size
() const¶Return the number of segments currently stored in this container.
empty
() const¶Return whether or not the container stores any segments or none at all.
leaf_size
() const¶Return the number of leaf nodes.
dispose_handler
¶fill_nonleaf_value_handler
¶Public Functions
operator()
(__st::nonleaf_node<segment_tree> &_self, const __st::node_base *left_node, const __st::node_base *right_node)¶init_handler
¶leaf_value_type
¶Public Functions
operator==
(const leaf_value_type &r) const¶nonleaf_value_type
¶Public Functions
operator==
(const nonleaf_value_type &r) const¶search_result
¶Inherits from mdds::segment_tree< _Key, _Value >::search_result_base
search_result_inserter
¶Inherits from std::unary_function< data_chain_type *, void >
search_result_vector_inserter
¶Inherits from std::unary_function< data_chain_type *, void >