mdds
Classes | Public Types | Public Member Functions | Friends | List of all members
mdds::segment_tree< _Key, _Value > Class Template Reference

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_treenode
 
typedef node::node_ptr node_ptr
 
typedef __st::nonleaf_node< segment_treenonleaf_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 >
 

Member Function Documentation

◆ build_tree()

template<typename _Key, typename _Value>
void mdds::segment_tree< _Key, _Value >::build_tree ( )

Build or re-build tree based on the current set of segments.

◆ clear()

template<typename _Key, typename _Value>
void mdds::segment_tree< _Key, _Value >::clear ( )

Remove all segments data.

◆ empty()

template<typename _Key, typename _Value>
bool mdds::segment_tree< _Key, _Value >::empty ( ) const

Return whether or not the container stores any segments or none at all.

◆ insert()

template<typename _Key, typename _Value>
bool mdds::segment_tree< _Key, _Value >::insert ( key_type  begin_key,
key_type  end_key,
value_type  pdata 
)

Insert a new segment.

Parameters
begin_keybegin point of the segment. The value is inclusive.
end_keyend point of the segment. The value is non-inclusive.
pdatapointer to the data instance associated with this segment. Note that the caller must manage the life cycle of the data instance.

◆ is_tree_valid()

template<typename _Key, typename _Value>
bool mdds::segment_tree< _Key, _Value >::is_tree_valid ( ) const
inline

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.

◆ leaf_size()

template<typename _Key, typename _Value>
size_t mdds::segment_tree< _Key, _Value >::leaf_size ( ) const

Return the number of leaf nodes.

Returns
number of leaf nodes.

◆ operator==()

template<typename _Key, typename _Value>
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.

◆ remove()

template<typename _Key, typename _Value>
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.

Parameters
valuevalue to remove a segment by.

◆ search() [1/2]

template<typename _Key, typename _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.

Parameters
pointspecified point value
resultdoubly-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() [2/2]

template<typename _Key, typename _Value>
search_result mdds::segment_tree< _Key, _Value >::search ( key_type  point) const

Search the tree and collect all segments that include a specified point.

Parameters
pointspecified point value
Returns
object containing the result of the search, which can be accessed via iterator.

◆ size()

template<typename _Key, typename _Value>
size_t mdds::segment_tree< _Key, _Value >::size ( ) const

Return the number of segments currently stored in this container.