Flat Segment Tree¶
Quick start¶
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 <iostream>
using namespace std;
using fst_type = mdds::flat_segment_tree<long, int>;
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;;
}
Let’s walk through this code step-by-step. The first step is to declare the instance:
// Define the begin and end points of the whole segment, and the default
// value.
fst_type db(0, 500, 0);
Here, the first and second arguments specify the lower and upper boundaries of the whole segment. The third argument specifies the value for the empty segments. What this line does is to create a new instance and initializes it with one initial segment ranging from 0 to 500 with a value of 0.
Internally, this initial range is represented by two leaf nodes, with the first one storing the start key and the value for the segment both of which happen to be 0 in this example, and the second one storing the end key of 500.
The following lines insert two new segments into this structure:
db.insert_front(10, 20, 10);
db.insert_back(50, 70, 15);
The first line inserts a segment ranging from 10 to 20 with a value of 10, and the second line from 50 to 70 with a value of 15.
You can insert a new segment either via insert_front()
or insert_back()
. The end result will be
the same regardless of which method you use; the difference is that
insert_front()
begins its search for
the insertion point from the first node associated with the minimum key value,
whereas insert_back()
starts its search
from the last node associated with the maximum key value.
At this point, the tree contains six leaf nodes in total to represent all stored segments. Note that one leaf node represents both the end of a segment and the start of the adjacent segment that comes after it, unless it’s either the first or the last node.
The next line inserts another segment ranging from 60 to 65 having a value of 5:
db.insert_back(60, 65, 5);
As this new segment overlaps with the existing segment of 50 to 70, it will cut into a middle part of that segment to make room for itself. At this point, the tree contains eight leaf nodes representing seven segments in total.
The next part queries the value associated with a key value of 15 via
search()
:
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;;
When executing this code, you will see the following output:
The value at 15 is 10, and this segment spans from 10 to 20
One thing to note is that the search()
method performs a linear search which involves traversing only through
the leaf nodes of the structure in order to find the target segment. As such,
the worst-case lookup performance is directly proportional to the number of
linear nodes.
There is another way to perform the query with better worse-case performance,
that is through search_tree()
as seen in
the following code:
// 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;;
The signature of the search_tree()
method
is identical to that of the search()
method
except for the name. This code generate the following output:
The value at 62 is 5, and this segment spans from 60 to 65
Query via search_tree()
generally performs
better since it traverses through the search tree to find the target segment.
But it does require the search tree to be built ahead of time by calling
build_tree()
.
Iterate through stored segments¶
flat_segment_tree
supports two types of iterators to allow
you to iterate through the segments stored in your tree. The first way is to
iterate through the individual leaf nodes one at a time by using
begin()
and end()
:
for (auto it = db.begin(); it != db.end(); ++it)
{
cout << "key: " << it->first << "; value: " << it->second << endl;
}
Each iterator value contains a pair of two values named first
and second
,
with the first one being the key of the segment that the node initiates, and the
second one being the value associated with that segment. When executing this
code with the tree from the example code above, you’ll get the following output:
key: 0; value: 0
key: 10; value: 10
key: 20; value: 0
key: 50; value: 15
key: 60; value: 5
key: 65; value: 15
key: 70; value: 0
key: 500; value: 0
Each node stores the start key and the value of the segment it initiates, and the key stored in each node is also the end key of the segment that the previous node initiates except for the first node.
except for the last node, which stores the end key of the segment the previous note initiates. Note that the value stored in the last node is not associated with any of the segments stored in the tree; in fact it is the default value for empty segments.
One thing to keep in mind is that flat_segment_tree
does
not support mutable iterators that let you modify the stored keys or values.
Note
flat_segment_tree
does not support mutable iterators;
you can only traverse the values in a read-only fashion.
You can also use range-based for loop to iterate through the leaf nodes in a similar fashion:
for (const auto& node : db)
{
cout << "key: " << node.first << "; value: " << node.second << endl;
}
The output from this code is identical to that from the previous one.
Now, one major inconvenience of navigating through the individual leaf nodes
one node at a time is that you need to keep track of the start and end points
of each segment if you need to operate on the segments rather than the nodes
that comprise the segments. The good news is that flat_segment_tree
does provide a way to iterate through the segments directly as the following
code demonstrates:
for (auto it = db.begin_segment(); it != db.end_segment(); ++it)
{
cout << "start: " << it->start << "; end: " << it->end << "; value: " << it->value << endl;
}
This code uses begin_segment()
and
end_segment()
to iterate through one
segment at a time with each iterator value containing start
, end
and
value
members that correspond with the start key, end key and the value of
the segment, respectively. Running this code produces the following output:
start: 0; end: 10; value: 0
start: 10; end: 20; value: 10
start: 20; end: 50; value: 0
start: 50; end: 60; value: 15
start: 60; end: 65; value: 5
start: 65; end: 70; value: 15
start: 70; end: 500; value: 0
API Reference¶
-
template <typename _Key, typename _Value>
classflat_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 __st::nonleaf_node<flat_segment_tree>
nonleaf_node
¶
-
template<>
usingconst_segment_iterator
= mdds::__fst::const_segment_iterator<flat_segment_tree>¶
Public Functions
-
const_iterator
begin
() const¶ Return an iterator that points to the first leaf node that correspondes with the start position of the first segment.
- Return
- immutable iterator that points to the first leaf node that corresponds with the start position of the first segment.
-
const_iterator
end
() const¶ Return an iterator that points to the position past the last leaf node that corresponds with the end position of the last segment.
- Return
- immutable iterator that points to the position past last leaf node that corresponds with the end position of the last segment.
-
const_reverse_iterator
rbegin
() const¶ Return an iterator that points to the last leaf node that correspondes with the end position of the last segment. This iterator moves in the reverse direction of a normal iterator.
- Return
- immutable reverse iterator that points to the last leaf node that corresponds with the end position of the last segment.
-
const_reverse_iterator
rend
() const¶ Return an iterator that points to the position past the first leaf node that corresponds with the start position of the first segment. This iterator moves in the reverse direction of a normal iterator.
- Return
- immutable reverse iterator that points to the position past first leaf node that corresponds with the start position of the first segment.
-
const_segment_iterator
begin_segment
() const¶ Return an immutable iterator that points to the first segment stored in the tree. It iterates through the segments one segment at a time. Each iterator value consists of
start
,end
, andvalue
members that correspond with the start and end positions of a segment and the value of that segment, respectively.- Return
- immutable iterator that points to the first segment stored in the tree.
-
const_segment_iterator
end_segment
() const¶ Return an immutable iterator that points to the position past the last segment stored in the tree. It iterates through the segments one segment at a time. Each iterator value consists of
start
,end
, andvalue
members that correspond with the start and end positions of a segment and the value of that segment, respectively.- Return
- immutable iterator that points to the position past the last segment stored in the tree.
-
flat_segment_tree
(key_type min_val, key_type max_val, value_type init_val)¶ Constructor that takes minimum and maximum keys and the value to be used for the initial segment.
- Parameters
min_val
: minimum allowed key value for the entire series of segments.max_val
: maximum allowed key value for the entires series of segments.init_val
: value to be used for the initial segment. This value will also be used for empty segments.
-
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)¶ Swap the content of the tree with another instance.
- Parameters
other
: instance of flat_segment_tree to swap content with.
-
void
clear
()¶ Remove all stored segments except for the initial segment. The minimum and maximum keys and the default value will be retained after the call returns. This call will also remove the tree.
-
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 pointstart_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 valuevalue
: 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 valuevalue
: 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 valuevalue
: 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¶
-
value_type
default_value
() const¶
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
: public mdds::__fst::const_iterator_base<flat_segment_tree, mdds::__fst::itr_forward_handler<flat_segment_tree>>¶ Public Functions
-
template<>
const_iterator
()¶
-
template<>
-
class
const_reverse_iterator
: public mdds::__fst::const_iterator_base<flat_segment_tree, mdds::__fst::itr_reverse_handler<flat_segment_tree>>¶ Public Functions
-
template<>
const_reverse_iterator
()¶
-
template<>
-
struct
dispose_handler
¶
-
struct
fill_nonleaf_value_handler
¶ Public Functions
-
template<>
voidoperator()
(__st::nonleaf_node<flat_segment_tree> &_self, const __st::node_base *left_node, const __st::node_base *right_node)¶
-
template<>
-
struct
init_handler
¶
-
struct
leaf_value_type
¶
-
typedef _Key