Adding upstream version 2.1.1.upstream/2.1.1upstream

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

1 files changed, 113 insertions, 0 deletions

diff --git a/example/rtree_medium.cpp b/example/rtree_medium.cpp
new file mode 100644
index 0000000..ef46871
--- /dev/null
+++ b/example/rtree_medium.cpp
@@ -0,0 +1,113 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2020 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include <mdds/rtree.hpp>
+
+#include <iostream>
+#include <fstream>
+
+// Make the node capacity intentionally small.
+struct tiny_traits_2d
+{
+    constexpr static size_t dimensions = 2;
+    constexpr static size_t min_node_size = 2;
+    constexpr static size_t max_node_size = 5;
+    constexpr static size_t max_tree_depth = 100;
+
+    constexpr static bool enable_forced_reinsertion = true;
+    constexpr static size_t reinsertion_size = 2;
+};
+
+using rt_type = mdds::rtree<int, int, tiny_traits_2d>;
+
+int main() try
+{
+    // 2D rectangle with the top-left position (x, y), width and height.
+    struct rect
+    {
+        int x;
+        int y;
+        int w;
+        int h;
+    };
+
+    std::vector<rect> rects =
+    {
+        {  3731,  2433, 1356,  937 },
+        {  6003,  3172, 1066,  743 },
+        {  4119,  6403,  825, 1949 },
+        { 10305,  2315,  776,  548 },
+        { 13930,  5468, 1742,  626 },
+        {  8614,  4107, 2709, 1793 },
+        { 14606,  1887, 5368, 1326 },
+        { 17990,  5196, 1163, 1911 },
+        {  6728,  7881, 3676, 1210 },
+        { 14704,  9789, 5271, 1092 },
+        {  4071, 10723, 4739,  898 },
+        { 11755,  9010, 1357, 2806 },
+        { 13978,  4068,  776,  509 },
+        { 17507,  3717,  777,  471 },
+        { 20358,  6092,  824, 1093 },
+        {  6390,  4535, 1066, 1715 },
+        { 13978,  7182, 2516, 1365 },
+        { 17942, 11580, 2854,  665 },
+        {  9919, 10450,  873, 1716 },
+        {  5568, 13215, 7446,  509 },
+        {  7357, 15277, 3145, 3234 },
+        {  3539, 12592,  631,  509 },
+        {  4747, 14498,  825,  626 },
+        {  4554, 16913,  969, 1443 },
+        { 12771, 14693, 2323,  548 },
+        { 18714,  8193, 2372,  586 },
+        { 22292,  2743,  487, 1638 },
+        { 20987, 17535, 1163, 1249 },
+        { 19536, 18859,  632,  431 },
+        { 19778, 15394, 1356,  626 },
+        { 22969, 15394,  631, 2066 },
+    };
+
+    rt_type tree;
+
+    // Insert the rectangle objects into the tree.
+    int value = 0;
+    for (const auto& rect : rects)
+        tree.insert({{rect.x, rect.y}, {rect.x + rect.w, rect.y + rect.h}}, value++);
+
+    // Export the tree structure as a SVG for visualization.
+    std::string tree_svg = tree.export_tree(rt_type::export_tree_type::extent_as_svg);
+    std::ofstream fout("bounds.svg");
+    fout << tree_svg;
+
+    return EXIT_SUCCESS;
+}
+catch (...)
+{
+    return EXIT_FAILURE;
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */