Flat Segment Tree

Code Example

Simple use case

The following code demonstrates a simple use case of storing non-overlapping ranged values and performing queries using flat_segment_tree:

#include <mdds/flat_segment_tree.hpp>
#include <string>
#include <iostream>

using namespace std;

typedef mdds::flat_segment_tree<long, int> fst_type;

int main()
{
    // Define the begin and end points of the whole segment, and the default
    // value.
    fst_type db(0, 500, 0);

    db.insert_front(10, 20, 10);
    db.insert_back(50, 70, 15);
    db.insert_back(60, 65, 5);

    int value = -1;
    long beg = -1, end = -1;

    // Perform linear search.  This doesn't require the tree to be built
    // beforehand.  Note that the begin and end point parameters are optional.
    db.search(15, value, &beg, &end);
    cout << "The value at 15 is " << value << ", and this segment spans from " << beg << " to " << end << endl;;

    // Don't forget to build tree before calling search_tree().
    db.build_tree();

    // Perform tree search.  Tree search is generally a lot faster than linear
    // search, but requires the tree to be built beforehand.
    db.search_tree(62, value, &beg, &end);
    cout << "The value at 62 is " << value << ", and this segment spans from " << beg << " to " << end << endl;;
}

Two types of searches are available. One is linear search via search() which performs its search only through the leaf nodes.

Another one is tree search via search_tree() which performs better than the linear search counterpart, but it does require the search tree to be built ahead of time by calling build_tree().

API Reference

template <typename _Key, typename _Value>
class mdds::flat_segment_tree

Public Types

typedef _Key key_type
typedef _Value value_type
typedef size_t size_type
typedef __st::node<flat_segment_tree> node
typedef node::node_ptr node_ptr
typedef __st::nonleaf_node<flat_segment_tree> nonleaf_node

Public Functions

const_iterator begin() const
const_iterator end() const
const_reverse_iterator rbegin() const
const_reverse_iterator rend() const
flat_segment_tree(key_type min_val, key_type max_val, value_type init_val)
flat_segment_tree(const flat_segment_tree<key_type, value_type> &r)

Copy constructor only copies the leaf nodes.

~flat_segment_tree()
flat_segment_tree<key_type, value_type> &operator=(const flat_segment_tree<key_type, value_type> &other)

Assignment only copies the leaf nodes.

void swap(flat_segment_tree<key_type, value_type> &other)
void clear()
std::pair<const_iterator, bool> insert_front(key_type start_key, key_type end_key, value_type val)

Insert a new segment into the tree. It searches for the point of insertion from the first leaf node.

Return
pair of const_iterator corresponding to the start position of the inserted segment, and a boolean value indicating whether or not the insertion has modified the tree.
Parameters
  • start_key -

    start value of the segment being inserted. The value is inclusive.

  • end_key -

    end value of the segment being inserted. The value is not inclusive.

  • val -

    value associated with this segment.

std::pair<const_iterator, bool> insert_back(key_type start_key, key_type end_key, value_type val)

Insert a new segment into the tree. Unlike the insert_front() counterpart, this method searches for the point of insertion from the last leaf node toward the first.

Return
pair of const_iterator corresponding to the start position of the inserted segment, and a boolean value indicating whether or not the insertion has modified the tree.
Parameters
  • start_key -

    start value of the segment being inserted. The value is inclusive.

  • end_key -

    end value of the segment being inserted. The value is not inclusive.

  • val -

    value associated with this segment.

std::pair<const_iterator, bool> insert(const const_iterator &pos, key_type start_key, key_type end_key, value_type val)

Insert a new segment into the tree at or after specified point of insertion.

Return
pair of const_iterator corresponding to the start position of the inserted segment, and a boolean value indicating whether or not the insertion has modified the tree.
Parameters
  • pos -

    specified insertion point

  • start_key -

    start value of the segment being inserted. The value is inclusive.

  • end_key -

    end value of the segment being inserted. The value is not inclusive.

  • val -

    value associated with this segment.

void shift_left(key_type start_key, key_type end_key)

Remove a segment specified by the start and end key values, and shift the remaining segments (i.e. those segments that come after the removed segment) to left. Note that the start and end positions of the segment being removed must be within the base segment span.

Parameters
  • start_key -

    start position of the segment being removed.

  • end_key -

    end position of the segment being removed.

void shift_right(key_type pos, key_type size, bool skip_start_node)

Shift all segments that occur at or after the specified start position to right by the size specified.

Parameters
  • pos -

    position where the right-shift occurs.

  • size -

    amount of shift (must be greater than 0)

  • skip_start_node -

    if true, and the specified position is at an existing node position, that node will not be shifted. This argument has no effect if the position specified does not coincide with any of the existing nodes.

std::pair<const_iterator, bool> search(key_type key, value_type &value, key_type *start_key = nullptr, key_type *end_key = nullptr) const

Perform leaf-node search for a value associated with a key.

Return
a pair of const_iterator corresponding to the start position of the segment containing the key, and a boolean value indicating whether or not the search has been successful.
Parameters
  • key -

    key value

  • value -

    value associated with key specified gets stored upon successful search.

  • start_key -

    pointer to a variable where the start key value of the segment that contains the key gets stored upon successful search.

  • end_key -

    pointer to a varaible where the end key value of the segment that contains the key gets stored upon successful search.

std::pair<const_iterator, bool> search(const const_iterator &pos, key_type key, value_type &value, key_type *start_key = nullptr, key_type *end_key = nullptr) const

Perform leaf-node search for a value associated with a key.

Return
a pair of const_iterator corresponding to the start position of the segment containing the key, and a boolean value indicating whether or not the search has been successful.
Parameters
  • pos -

    position from which the search should start. When the position is invalid, it falls back to the normal search.

  • key -

    key value

  • value -

    value associated with key specified gets stored upon successful search.

  • start_key -

    pointer to a variable where the start key value of the segment that contains the key gets stored upon successful search.

  • end_key -

    pointer to a varaible where the end key value of the segment that contains the key gets stored upon successful search.

std::pair<const_iterator, bool> search_tree(key_type key, value_type &value, key_type *start_key = nullptr, key_type *end_key = nullptr) const

Perform tree search for a value associated with a key. This method assumes that the tree is valid. Call is_tree_valid() to find out whether the tree is valid, and build_tree() to build a new tree in case it’s not.

Return
a pair of const_iterator corresponding to the start position of the segment containing the key, and a boolean value indicating whether or not the search has been successful.
Parameters
  • key -

    key value

  • value -

    value associated with key specified gets stored upon successful search.

  • start_key -

    pointer to a variable where the start key value of the segment that contains the key gets stored upon successful search.

  • end_key -

    pointer to a varaible where the end key value of the segment that contains the key gets stored upon successful search.

void build_tree()

Build a tree of non-leaf nodes based on the values stored in the leaf nodes. The tree must be valid before you can call the search_tree() method.

bool is_tree_valid() const

Return
true if the tree is valid, otherwise false. The tree must be valid before you can call the search_tree() method.

bool operator==(const flat_segment_tree<key_type, value_type> &r) const

Equality between two flat_segment_tree instances is evaluated by comparing the keys and the values of the leaf nodes only. Neither the non-leaf nodes nor the validity of the tree is evaluated.

bool operator!=(const flat_segment_tree<key_type, value_type> &r) const
key_type min_key() const
key_type max_key() const
value_type default_value() const
size_type leaf_size() const

Return the number of leaf nodes.

Return
number of leaf nodes.

Friends

friend mdds::flat_segment_tree::::mdds::__fst::itr_forward_handler< flat_segment_tree >
friend mdds::flat_segment_tree::::mdds::__fst::itr_reverse_handler< flat_segment_tree >
class const_iterator

Inherits from mdds::__fst::const_iterator_base< flat_segment_tree,::mdds::__fst::itr_forward_handler< flat_segment_tree > >

Public Functions

template<>
mdds::flat_segment_tree<_Key, _Value>::const_iterator::const_iterator()
class const_reverse_iterator

Inherits from mdds::__fst::const_iterator_base< flat_segment_tree,::mdds::__fst::itr_reverse_handler< flat_segment_tree > >

Public Functions

template<>
mdds::flat_segment_tree<_Key, _Value>::const_reverse_iterator::const_reverse_iterator()
struct dispose_handler

Public Functions

template<>
void mdds::flat_segment_tree<_Key, _Value>::dispose_handler::operator()(node&)
template<>
void mdds::flat_segment_tree<_Key, _Value>::dispose_handler::operator()(__st::nonleaf_node<flat_segment_tree>&)
struct fill_nonleaf_value_handler

Public Functions

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

Public Functions

template<>
void mdds::flat_segment_tree<_Key, _Value>::init_handler::operator()(node&)
template<>
void mdds::flat_segment_tree<_Key, _Value>::init_handler::operator()(__st::nonleaf_node<flat_segment_tree>&)
struct leaf_value_type

Public Functions

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

Public Members

template<>
key_type mdds::flat_segment_tree<_Key, _Value>::leaf_value_type::key
template<>
value_type mdds::flat_segment_tree<_Key, _Value>::leaf_value_type::value
struct nonleaf_value_type

Public Functions

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

high range value (non-inclusive)

template<>
mdds::flat_segment_tree<_Key, _Value>::nonleaf_value_type::nonleaf_value_type()

Public Members

template<>
key_type mdds::flat_segment_tree<_Key, _Value>::nonleaf_value_type::low
template<>
key_type mdds::flat_segment_tree<_Key, _Value>::nonleaf_value_type::high

low range value (inclusive)