Import the RangeTree library into extern
authorNicholas Bishop <nicholasbishop@gmail.com>
Sun, 30 Dec 2012 18:20:52 +0000 (18:20 +0000)
committerNicholas Bishop <nicholasbishop@gmail.com>
Sun, 30 Dec 2012 18:20:52 +0000 (18:20 +0000)
RangeTree is a simple C++ tree set for storing non-overlapping scalar
ranges. Original source from:
https://github.com/nicholasbishop/RangeTree

Also update the build systems to include RangeTree.

extern/CMakeLists.txt
extern/SConscript
extern/rangetree/CMakeLists.txt [new file with mode: 0644]
extern/rangetree/README.org [new file with mode: 0644]
extern/rangetree/SConscript [new file with mode: 0644]
extern/rangetree/range_tree.hh [new file with mode: 0644]
extern/rangetree/range_tree_c_api.cc [new file with mode: 0644]
extern/rangetree/range_tree_c_api.h [new file with mode: 0644]
source/blenderplayer/CMakeLists.txt
source/creator/CMakeLists.txt

index 2640c528c94c23f0431c47e332b1c90ba7e4343f..2f7f6584f0fe9305945777ead8e99eea35f6986c 100644 (file)
@@ -27,6 +27,7 @@
 remove_strict_flags()
 
 add_subdirectory(colamd)
+add_subdirectory(rangetree)
 
 if(WITH_BULLET)
        add_subdirectory(bullet2)
index 71998ee072c1c3e070b61399f8254e4241a289ab..6a0ffa3f58852973db67a6a4a425af076ad14a08 100644 (file)
@@ -4,6 +4,7 @@ Import('env')
 
 SConscript(['glew/SConscript'])
 SConscript(['colamd/SConscript'])
+SConscript(['rangetree/SConscript'])
 
 if env['WITH_BF_GAMEENGINE']:
     SConscript(['recastnavigation/SConscript'])
diff --git a/extern/rangetree/CMakeLists.txt b/extern/rangetree/CMakeLists.txt
new file mode 100644 (file)
index 0000000..ba68223
--- /dev/null
@@ -0,0 +1,31 @@
+# ***** BEGIN GPL LICENSE BLOCK *****
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software Foundation,
+# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+#
+# ***** END GPL LICENSE BLOCK *****
+
+set(INC
+       .
+)
+
+set(SRC
+       range_tree.hh
+       range_tree_c_api.h
+
+       range_tree_c_api.cc
+)
+
+blender_add_lib(extern_rangetree "${SRC}" "${INC}" "")
+
diff --git a/extern/rangetree/README.org b/extern/rangetree/README.org
new file mode 100644 (file)
index 0000000..46a4ced
--- /dev/null
@@ -0,0 +1,13 @@
+* Overview
+  Basic class for storing non-overlapping scalar ranges. Underlying
+  representation is a C++ STL set for fast lookups.
+
+* License
+  GPL version 2 or later (see COPYING)
+
+* Author Note
+  This implementation is intended for storing free unique IDs in a new
+  undo system for BMesh in Blender, but could be useful elsewhere.
+
+* Website
+  https://github.com/nicholasbishop/RangeTree
diff --git a/extern/rangetree/SConscript b/extern/rangetree/SConscript
new file mode 100644 (file)
index 0000000..787decd
--- /dev/null
@@ -0,0 +1,9 @@
+2#!/usr/bin/python
+Import ('env')
+
+sources = env.Glob('*.cc')
+
+incs = '.'
+defs = ''
+
+env.BlenderLib ('extern_rangetree', sources, Split(incs), Split(defs), libtype=['extern'], priority=[100] )
diff --git a/extern/rangetree/range_tree.hh b/extern/rangetree/range_tree.hh
new file mode 100644 (file)
index 0000000..2a47c5a
--- /dev/null
@@ -0,0 +1,228 @@
+/* This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+   02110-1301, USA.
+*/
+
+#include <cassert>
+#include <climits>
+#include <iostream>
+#include <set>
+
+#ifndef RANGE_TREE_DEBUG_PRINT_FUNCTION
+#    define RANGE_TREE_DEBUG_PRINT_FUNCTION 0
+#endif
+
+template <typename T>
+struct RangeTree {
+       struct Range {
+               Range(T min_, T max_)
+                       : min(min_), max(max_), single(min_ == max_) {
+                       assert(min_ <= max_);
+               }
+
+               Range(T t)
+                       : min(t), max(t), single(true)
+               {}
+
+               bool operator<(const Range& v) const {
+                       return max < v.min;
+               }
+
+               const T min;
+               const T max;
+               const bool single;
+       };
+
+       typedef std::set<Range> Tree;
+       typedef typename Tree::iterator TreeIter;
+       typedef typename Tree::reverse_iterator TreeIterReverse;
+       typedef typename Tree::const_iterator TreeIterConst;
+
+       /* Initialize with a single range from 'min' to 'max', inclusive. */
+       RangeTree(T min, T max) {
+               tree.insert(Range(min, max));
+       }
+
+       /* Initialize with a single range from 0 to 'max', inclusive. */
+       RangeTree(T max) {
+               tree.insert(Range(0, max));
+       }
+
+       RangeTree(const RangeTree<T>& src) {
+               tree = src.tree;
+       }
+
+       /* Remove 't' from the associated range in the tree. Precondition:
+          a range including 't' must exist in the tree. */
+       void take(T t) {
+               #if RANGE_TREE_DEBUG_PRINT_FUNCTION
+               std::cout << __func__ << "(" << t << ")\n";
+               #endif
+
+               /* Find the range that includes 't' and its neighbors */
+               TreeIter iter = tree.find(Range(t));
+               assert(iter != tree.end());
+               Range cur = *iter;
+               TreeIter prev = iter;
+               TreeIter next = iter;
+               --prev;
+               ++next;
+
+               /* Remove the original range (note that this does not
+                  invalidate the prev/next iterators) */
+               tree.erase(iter);
+
+               /* Construct two new ranges that together cover the original
+                  range, except for 't' */
+               if (t > cur.min)
+                       tree.insert(Range(cur.min, t - 1));
+               if (t + 1 <= cur.max)
+                       tree.insert(Range(t + 1, cur.max));
+       }
+
+       /* Take the first element out of the first range in the
+          tree. Precondition: tree must not be empty. */
+       T take_any() {
+               #if RANGE_TREE_DEBUG_PRINT_FUNCTION
+               std::cout << __func__ << "()\n";
+               #endif
+
+               /* Find the first element */
+               TreeIter iter = tree.begin();
+               assert(iter != tree.end());
+               T first = iter->min;
+
+               /* Take the first element */
+               take(first);
+               return first;
+       }
+
+       /* Return 't' to the tree, either expanding/merging existing
+          ranges or adding a range to cover it. Precondition: 't' cannot
+          be in an existing range. */
+       void release(T t) {
+               #if RANGE_TREE_DEBUG_PRINT_FUNCTION
+               std::cout << __func__ << "(" << t << ")\n";
+               #endif
+
+               /* TODO: these cases should be simplified/unified */
+
+               TreeIter right = tree.upper_bound(t);
+               if (right != tree.end()) {
+                       TreeIter left = right;
+                       if (left != tree.begin())
+                               --left;
+
+                       if (left == right) {
+                               /* 't' lies before any existing ranges */
+                               if (t + 1 == left->min) {
+                                       /* 't' lies directly before the first range,
+                                          resize and replace that range */
+                                       const Range r(t, left->max);
+                                       tree.erase(left);
+                                       tree.insert(r);
+                               }
+                               else {
+                                       /* There's a gap between 't' and the first range,
+                                          add a new range */
+                                       tree.insert(Range(t));
+                               }
+                       }
+                       else if ((left->max + 1 == t) &&
+                               (t + 1 == right->min)) {
+                               /* 't' fills a hole. Remove left and right, and insert a
+                                  new range that covers both. */
+                               const Range r(left->min, right->max);
+                               tree.erase(left);
+                               tree.erase(right);
+                               tree.insert(r);
+                       }
+                       else if (left->max + 1 == t) {
+                               /* 't' lies directly after 'left' range, resize and
+                                  replace that range */
+                               const Range r(left->min, t);
+                               tree.erase(left);
+                               tree.insert(r);
+                       }
+                       else if (t + 1 == right->min) {
+                               /* 't' lies directly before 'right' range, resize and
+                                  replace that range */
+                               const Range r(t, right->max);
+                               tree.erase(right);
+                               tree.insert(r);
+                       }
+                       else {
+                               /* There's a gap between 't' and both adjacent ranges,
+                                  add a new range */
+                               tree.insert(Range(t));
+                       }
+               }
+               else {
+                       /* 't' lies after any existing ranges */
+                       right = tree.end();
+                       right--;
+                       if (right->max + 1 == t) {
+                               /* 't' lies directly after last range, resize and
+                                  replace that range */
+                               const Range r(right->min, t);
+                               tree.erase(right);
+                               tree.insert(r);
+                       }
+                       else {
+                               /* There's a gap between the last range and 't', add a
+                                  new range */
+                               tree.insert(Range(t));
+                       }
+               }
+       }
+
+       bool has(T t) const {
+               TreeIterConst iter = tree.find(Range(t));
+               return (iter != tree.end()) && (t <= iter->max);
+       }
+
+       bool has_range(T min, T max) const {
+               TreeIterConst iter = tree.find(Range(min, max));
+               return (iter != tree.end()) && (min == iter->min && max == iter->max);
+       }
+
+       bool empty() const {
+               return tree.empty();
+       }
+
+       int size() const {
+               return tree.size();
+       }
+
+       void print() const {
+               std::cout << "RangeTree:\n";
+               for (TreeIterConst iter = tree.begin(); iter != tree.end(); ++iter) {
+                       const Range& r = *iter;
+                       if (r.single)
+                               std::cout << "  [" << r.min << "]\n";
+                       else
+                               std::cout << "  [" << r.min << ", " << r.max << "]\n";
+               }
+               if (empty())
+                       std::cout << "  <empty>";
+               std::cout << "\n";
+       }
+
+       unsigned int allocation_lower_bound() const {
+               return tree.size() * sizeof(Range);
+       }
+
+private:
+       Tree tree;
+};
diff --git a/extern/rangetree/range_tree_c_api.cc b/extern/rangetree/range_tree_c_api.cc
new file mode 100644 (file)
index 0000000..56f2d90
--- /dev/null
@@ -0,0 +1,86 @@
+/* This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+   02110-1301, USA.
+*/
+
+#include "range_tree.hh"
+
+/* Give RangeTreeUInt a real type rather than the opaque struct type
+   defined for external use. */
+#define RANGE_TREE_C_API_INTERNAL
+typedef RangeTree<unsigned> RangeTreeUInt;
+
+#include "range_tree_c_api.h"
+
+RangeTreeUInt *range_tree_uint_alloc(unsigned min, unsigned max)
+{
+       return new RangeTreeUInt(min, max);
+}
+
+RangeTreeUInt *range_tree_uint_copy(RangeTreeUInt *src)
+{
+       return new RangeTreeUInt(*src);
+}
+
+void range_tree_uint_free(RangeTreeUInt *rt)
+{
+       delete rt;
+}
+
+void range_tree_uint_take(RangeTreeUInt *rt, unsigned v)
+{
+       rt->take(v);
+}
+
+unsigned range_tree_uint_take_any(RangeTreeUInt *rt)
+{
+       return rt->take_any();
+}
+
+void range_tree_uint_release(RangeTreeUInt *rt, unsigned v)
+{
+       rt->release(v);
+}
+
+int range_tree_uint_has(const RangeTreeUInt *rt, unsigned v)
+{
+       return rt->has(v);
+}
+
+int range_tree_uint_has_range(const RangeTreeUInt *rt,
+                                                         unsigned vmin,
+                                                         unsigned vmax)
+{
+       return rt->has_range(vmin, vmax);
+}
+
+int range_tree_uint_empty(const RangeTreeUInt *rt)
+{
+       return rt->empty();
+}
+
+unsigned range_tree_uint_size(const RangeTreeUInt *rt)
+{
+       return rt->size();
+}
+
+void range_tree_uint_print(const RangeTreeUInt *rt)
+{
+       rt->print();
+}
+
+unsigned int range_tree_uint_allocation_lower_bound(const RangeTreeUInt *rt)
+{
+       return rt->allocation_lower_bound();
+}
diff --git a/extern/rangetree/range_tree_c_api.h b/extern/rangetree/range_tree_c_api.h
new file mode 100644 (file)
index 0000000..af6a7b1
--- /dev/null
@@ -0,0 +1,60 @@
+/* This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+   02110-1301, USA.
+*/
+
+#ifndef RANGE_TREE_C_API_H
+#define RANGE_TREE_C_API_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* Simple C-accessible wrapper for RangeTree<unsigned> */
+
+#ifndef RANGE_TREE_C_API_INTERNAL
+typedef struct RangeTreeUInt RangeTreeUInt;
+#endif
+
+RangeTreeUInt *range_tree_uint_alloc(unsigned min, unsigned max);
+
+RangeTreeUInt *range_tree_uint_copy(RangeTreeUInt *src);
+
+void range_tree_uint_free(RangeTreeUInt *rt);
+
+void range_tree_uint_take(RangeTreeUInt *rt, unsigned v);
+
+unsigned range_tree_uint_take_any(RangeTreeUInt *rt);
+
+void range_tree_uint_release(RangeTreeUInt *rt, unsigned v);
+
+int range_tree_uint_has(const RangeTreeUInt *rt, unsigned v);
+
+int range_tree_uint_has_range(const RangeTreeUInt *rt,
+                                                         unsigned vmin,
+                                                         unsigned vmax);
+
+int range_tree_uint_empty(const RangeTreeUInt *rt);
+
+unsigned range_tree_uint_size(const RangeTreeUInt *rt);
+
+void range_tree_uint_print(const RangeTreeUInt *rt);
+
+unsigned int range_tree_uint_allocation_lower_bound(const RangeTreeUInt *rt);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __DUALCON_H__ */
index 85bb07d6e8398b2e1baff7ecc1de354e2edc76bd..d606605e8d5336869c4179f028ebfe81aaa58c54 100644 (file)
@@ -149,6 +149,7 @@ endif()
                bf_intern_raskter
                bf_intern_opencolorio
                bf_intern_opennl
+               extern_rangetree
        )
 
        if(WITH_MOD_CLOTH_ELTOPO)
index b66c000ac8904cd6b0be2d5dda54f694d370112c..c53f27c73268a872f6317bb61af4c056631e83c0 100644 (file)
@@ -914,6 +914,7 @@ endif()
                cycles_subd
                bf_intern_raskter
                bf_intern_opencolorio
+               extern_rangetree
        )
 
        if(WITH_COMPOSITOR)