|
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. |
| 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 |
| 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. |
| size_t mdds::segment_tree< _Key, _Value >::size | ( | ) | const |
Return the number of segments currently stored in this container.
1.8.19