Adding upstream version 2.1.1.upstream/2.1.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 268 insertions, 0 deletions

diff --git a/doc/flat_segment_tree.rst b/doc/flat_segment_tree.rst
new file mode 100644
index 0000000..d5e7b8a
--- /dev/null
+++ b/doc/flat_segment_tree.rst
@@ -0,0 +1,268 @@
+.. highlight:: cpp
+
+Flat Segment Tree
+=================
+
+Overview
+--------
+
+Flat segment tree is a derivative of `segment tree
+<https://en.wikipedia.org/wiki/Segment_tree>`_, and is designed to store
+non-overlapping 1-dimensional range values such that *the values of the
+neighboring ranges are guaranteed to be different.*  An insertion of a range
+value into this structure will always overwrite one or more existing ranges
+that overlap with the new range.  If an insertion of a new range would cause
+any adjacent ranges to have the equal value, those ranges will be merged into
+one range.
+
+An instance of this structure is initialized with fixed lower and upper
+bounaries, which will not change throughout the life time of the instance.
+
+The flat segment tree structure consists of two parts: the leaf-node part
+which also forms a doubly-linked list, and the non-leaf-node part which forms
+a balanced-binary tree and is used only when performing tree-based queries.
+The range values are stored in the leaf-nodes, while the non-leaf nodes are
+used only for queries.
+
+
+Quick start
+-----------
+
+This section demonstrates a simple use case of storing non-overlapping ranged
+values and performing queries using :cpp:class:`~mdds::flat_segment_tree`.
+
+First, we need to instantiate a concrete type from the template:
+
+.. literalinclude:: ../example/flat_segment_tree.cpp
+   :language: C++
+   :start-after: //!code-start: type
+   :end-before: //!code-end: type
+   :dedent: 4
+
+then create an instance of this type:
+
+.. literalinclude:: ../example/flat_segment_tree.cpp
+   :language: C++
+   :start-after: //!code-start: instance
+   :end-before: //!code-end: instance
+   :dedent: 4
+
+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:
+
+.. figure:: _static/images/fst-example1-initial.svg
+   :align: center
+
+   The new instance is initialized with an initial segment.
+
+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.
+Note that the end key of a segment is not inclusive.
+
+The following lines insert two new segments into this structure:
+
+.. literalinclude:: ../example/flat_segment_tree.cpp
+   :language: C++
+   :start-after: //!code-start: insert-1
+   :end-before: //!code-end: insert-1
+   :dedent: 4
+
+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:
+
+.. figure:: _static/images/fst-example1-insert1.svg
+   :align: center
+
+   Two new segments have been inserted.
+
+You can insert a new segment either via :cpp:func:`~mdds::flat_segment_tree::insert_front`
+or :cpp:func:`~mdds::flat_segment_tree::insert_back`.  The end result will be
+the same regardless of which method you use; the difference is that
+:cpp:func:`~mdds::flat_segment_tree::insert_front` begins its search for
+the insertion point from the first node associated with the minimum key value,
+whereas :cpp:func:`~mdds::flat_segment_tree::insert_back` starts its search
+from the last node associated with the maximum key value.
+
+After the insertions, the tree now contains a total of six leaf nodes to
+represent all stored segments.  Note that one leaf node typically 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:
+
+.. literalinclude:: ../example/flat_segment_tree.cpp
+   :language: C++
+   :start-after: //!code-start: insert-2
+   :end-before: //!code-end: insert-2
+   :dedent: 4
+
+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 the new segment.  At
+this point, the tree contains a total of eight leaf nodes representing seven
+segments:
+
+.. figure:: _static/images/fst-example1-insert2.svg
+   :align: center
+
+   A new segment has been inserted that overlaps an existing non-empty segment.
+
+Next, we are going to query the value associated with a key of 15 via
+:cpp:func:`~mdds::flat_segment_tree::search`:
+
+.. literalinclude:: ../example/flat_segment_tree.cpp
+   :language: C++
+   :start-after: //!code-start: linear-search
+   :end-before: //!code-end: linear-search
+   :dedent: 4
+
+Executing this code will yield the following output:
+
+.. code-block:: none
+
+    The value at 15 is 10, and this segment spans from 10 to 20
+
+One thing to note is that the :cpp:func:`~mdds::flat_segment_tree::search`
+method performs a linear search which involves traversing only through the
+leaf nodes in this data structure in order to find the target segment.  As
+such, the worst-case lookup performance is directly proportional to the number
+of leaf nodes.
+
+There is another way to perform the query with better worse-case performance,
+that is through :cpp:func:`~mdds::flat_segment_tree::search_tree` as seen in
+the following code:
+
+.. literalinclude:: ../example/flat_segment_tree.cpp
+   :language: C++
+   :start-after: //!code-start: tree-search
+   :end-before: //!code-end: tree-search
+   :dedent: 4
+
+The signature of the :cpp:func:`~mdds::flat_segment_tree::search_tree` method
+is identical to that of the :cpp:func:`~mdds::flat_segment_tree::search` method
+except for the name.  This code generates the following output:
+
+.. code-block:: none
+
+    The value at 62 is 5, and this segment spans from 60 to 65
+
+Query via :cpp:func:`~mdds::flat_segment_tree::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
+:cpp:func:`~mdds::flat_segment_tree::build_tree`.  Please be aware that if the
+segments have been modified after the tree was last built, you will have to rebuild
+the tree by calling :cpp:func:`~mdds::flat_segment_tree::build_tree`.
+
+.. warning::
+
+   You need to build the tree by calling :cpp:func:`~mdds::flat_segment_tree::build_tree`
+   before performing a tree-based search via :cpp:func:`~mdds::flat_segment_tree::search_tree`.
+   If the segments have been modified after the tree was last built, you will have to
+   rebuild the tree by calling :cpp:func:`~mdds::flat_segment_tree::build_tree` again.
+
+
+Iterate through stored segments
+-------------------------------
+
+:cpp:class:`~mdds::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
+:cpp:func:`~mdds::flat_segment_tree::begin` and :cpp:func:`~mdds::flat_segment_tree::end`:
+
+.. literalinclude:: ../example/flat_segment_tree_itrs.cpp
+   :language: C++
+   :start-after: //!code-start: iterate-nodes
+   :end-before: //!code-end: iterate-nodes
+   :dedent: 4
+
+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:
+
+.. code-block:: none
+
+    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.  Note that the value stored
+in the last node is currently not used.  It is set to be the zero value of the
+value type, but this may change in the future.
+
+One thing to keep in mind is that :cpp:class:`~mdds::flat_segment_tree` does
+not support mutable iterators that let you modify the stored keys or values.
+
+.. note::
+
+   :cpp:class:`~mdds::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:
+
+.. literalinclude:: ../example/flat_segment_tree_itrs.cpp
+   :language: C++
+   :start-after: //!code-start: loop-nodes
+   :end-before: //!code-end: loop-nodes
+   :dedent: 4
+
+The output from this code is identical to that from the previous one.
+
+Now, one major inconvenience of navigating through the individual leaf nodes
+is that you need to manually 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
+:cpp:class:`~mdds::flat_segment_tree` does provide a way to iterate through
+the segments directly as the following code demonstrates:
+
+.. literalinclude:: ../example/flat_segment_tree_itrs.cpp
+   :language: C++
+   :start-after: //!code-start: iterate-segments
+   :end-before: //!code-end: iterate-segments
+   :dedent: 4
+
+This code uses :cpp:func:`~mdds::flat_segment_tree::begin_segment` and
+:cpp:func:`~mdds::flat_segment_tree::end_segment` to iterate through one
+segment at a time with the value of each iterator 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:
+
+.. code-block:: none
+
+    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
+
+It's also possible to iterate through the segments in a range-based for loop, by
+calling :cpp:func:`~mdds::flat_segment_tree::segment_range()`:
+
+.. literalinclude:: ../example/flat_segment_tree_itrs.cpp
+   :language: C++
+   :start-after: //!code-start: loop-segments
+   :end-before: //!code-end: loop-segments
+   :dedent: 4
+
+This code should generate output identical to that of the previous code.
+
+
+API Reference
+-------------
+
+.. doxygenclass:: mdds::flat_segment_tree
+   :members: