mdds
|
Classes | |
struct | dispose_handler |
struct | fill_nonleaf_value_handler |
struct | init_handler |
struct | leaf_value_type |
struct | nonleaf_value_type |
class | search_result |
class | search_result_inserter |
class | search_result_vector_inserter |
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 Member Functions | |
segment_tree (const segment_tree &r) | |
bool | operator== (const segment_tree &r) const |
bool | operator!= (const segment_tree &r) const |
bool | is_tree_valid () const |
void | build_tree () |
bool | insert (key_type begin_key, key_type end_key, value_type pdata) |
bool | search (key_type point, search_result_type &result) const |
search_result | search (key_type point) const |
void | remove (value_type value) |
void | clear () |
size_t | size () const |
bool | empty () const |
size_t | leaf_size () const |
Friends | |
class | rectangle_set< _Key, _Value > |
void mdds::segment_tree< _Key, _Value >::build_tree | ( | ) |
Build or re-build tree based on the current set of segments.
void mdds::segment_tree< _Key, _Value >::clear | ( | ) |
Remove all segments data.
bool mdds::segment_tree< _Key, _Value >::empty | ( | ) | const |
Return whether or not the container stores any segments or none at all.
bool mdds::segment_tree< _Key, _Value >::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. |
|
inline |
Check whether or not the internal tree is in a valid state. The tree must be valid in order to perform searches.
size_t mdds::segment_tree< _Key, _Value >::leaf_size | ( | ) | const |
Return the number of leaf nodes.
bool mdds::segment_tree< _Key, _Value >::operator== | ( | const segment_tree< _Key, _Value > & | r | ) | const |
Equality between two segment_tree instances is evaluated by comparing the segments that they store. The trees are not compared.
void mdds::segment_tree< _Key, _Value >::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.
value | value to remove a segment by. |
bool mdds::segment_tree< _Key, _Value >::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_result mdds::segment_tree< _Key, _Value >::search | ( | key_type | point | ) | const |
Search the tree and collect all segments that include a specified point.
point | specified point value |
size_t mdds::segment_tree< _Key, _Value >::size | ( | ) | const |
Return the number of segments currently stored in this container.