Segment Tree¶

API Reference¶

template <typename _Key, typename _Value>

class

Public Types

typedef

typedef

typedef

typedef

typedef

typedef

typedef

typedef

typedef

typedef

Public Functions

mdds::segment_tree::segment_tree()¶

mdds::segment_tree::segment_tree(const segment_tree &r)¶

mdds::segment_tree::~segment_tree()¶

bool mdds::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.

bool mdds::segment_tree::operator!=(const segment_tree &r)¶
const

bool mdds::segment_tree::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.

Return

true if the tree is valid, false otherwise.

void mdds::segment_tree::build_tree()¶

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

bool mdds::segment_tree::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 mdds::segment_tree::search(key_type point, search_result_type &result)¶
const

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

Return

true if the search is performed successfully, false if the search has ended prematurely due to error conditions.

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.

search_result mdds::segment_tree::search(key_type point)¶
const

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

Return

object containing the result of the search, which can be accessed via iterator.

Parameters

• point -

  specified point value

void mdds::segment_tree::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 mdds::segment_tree::clear()¶

Remove all segments data.

size_t mdds::segment_tree::size()¶
const

Return the number of segments currently stored in this container.

bool mdds::segment_tree::empty()¶
const

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

size_t mdds::segment_tree::leaf_size()¶
const

Return the number of leaf nodes.

Return

number of leaf nodes.

struct

Public Functions

template<>
void mdds::segment_tree<_Key, _Value>::dispose_handler::operator()(node &_self)¶

template<>
void mdds::segment_tree<_Key, _Value>::dispose_handler::operator()(__st::nonleaf_node<segment_tree> &_self)¶

struct

Public Functions

template<>
void mdds::segment_tree<_Key, _Value>::fill_nonleaf_value_handler::operator()(__st::nonleaf_node<segment_tree> &_self, const __st::node_base *left_node, const __st::node_base *right_node)¶

struct

Public Functions

template<>
void mdds::segment_tree<_Key, _Value>::init_handler::operator()(node &_self)¶

template<>
void mdds::segment_tree<_Key, _Value>::init_handler::operator()(__st::nonleaf_node<segment_tree> &_self)¶

struct

Public Functions

template<>
bool mdds::segment_tree<_Key, _Value>::leaf_value_type::operator==(const leaf_value_type &r)¶
const

Public Members

template<>
key_type mdds::segment_tree<_Key, _Value>::leaf_value_type::key¶

template<>
data_chain_type *mdds::segment_tree<_Key, _Value>::leaf_value_type::data_chain¶

struct

Public Functions

template<>
bool mdds::segment_tree<_Key, _Value>::nonleaf_value_type::operator==(const nonleaf_value_type &r)¶
const

Public Members

template<>
key_type mdds::segment_tree<_Key, _Value>::nonleaf_value_type::low¶

template<>
key_type mdds::segment_tree<_Key, _Value>::nonleaf_value_type::high¶

low range value (inclusive)

template<>
data_chain_type *mdds::segment_tree<_Key, _Value>::nonleaf_value_type::data_chain¶

high range value (non-inclusive)

class

Inherits from mdds::segment_tree< _Key, _Value >::search_result_base

Public Functions

template<>
search_result::iterator mdds::segment_tree<_Key, _Value>::search_result::begin()¶

template<>
search_result::iterator mdds::segment_tree<_Key, _Value>::search_result::end()¶

class

Inherits from mdds::segment_tree< _Key, _Value >::iterator_base

Public Functions

template<>
mdds::segment_tree<_Key, _Value>::search_result::iterator::iterator()¶

Friends

friend mdds::segment_tree::segment_tree< _Key, _Value >::search_result

class

Public Functions

template<>
mdds::segment_tree<_Key, _Value>::search_result_inserter::search_result_inserter(search_result_base &result)¶

template<>
void mdds::segment_tree<_Key, _Value>::search_result_inserter::operator()(data_chain_type *node_data)¶

class

Public Functions

template<>
mdds::segment_tree<_Key, _Value>::search_result_vector_inserter::search_result_vector_inserter(search_result_type &result)¶

template<>
void mdds::segment_tree<_Key, _Value>::search_result_vector_inserter::operator()(data_chain_type *node_data)¶