From a8811094ea9241ac8678a7d4c3fff4ab2ac5bf20 Mon Sep 17 00:00:00 2001 From: Nicholas Bishop Date: Sun, 30 Dec 2012 18:20:52 +0000 Subject: Import the RangeTree library into extern 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 | 1 + extern/SConscript | 1 + extern/rangetree/CMakeLists.txt | 31 +++++ extern/rangetree/README.org | 13 ++ extern/rangetree/SConscript | 9 ++ extern/rangetree/range_tree.hh | 228 +++++++++++++++++++++++++++++++++++ extern/rangetree/range_tree_c_api.cc | 86 +++++++++++++ extern/rangetree/range_tree_c_api.h | 60 +++++++++ source/blenderplayer/CMakeLists.txt | 1 + source/creator/CMakeLists.txt | 1 + 10 files changed, 431 insertions(+) create mode 100644 extern/rangetree/CMakeLists.txt create mode 100644 extern/rangetree/README.org create mode 100644 extern/rangetree/SConscript create mode 100644 extern/rangetree/range_tree.hh create mode 100644 extern/rangetree/range_tree_c_api.cc create mode 100644 extern/rangetree/range_tree_c_api.h diff --git a/extern/CMakeLists.txt b/extern/CMakeLists.txt index 2640c528c94..2f7f6584f0f 100644 --- a/extern/CMakeLists.txt +++ b/extern/CMakeLists.txt @@ -27,6 +27,7 @@ remove_strict_flags() add_subdirectory(colamd) +add_subdirectory(rangetree) if(WITH_BULLET) add_subdirectory(bullet2) diff --git a/extern/SConscript b/extern/SConscript index 71998ee072c..6a0ffa3f588 100644 --- a/extern/SConscript +++ b/extern/SConscript @@ -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 index 00000000000..ba682233381 --- /dev/null +++ b/extern/rangetree/CMakeLists.txt @@ -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 index 00000000000..46a4cedaf8f --- /dev/null +++ b/extern/rangetree/README.org @@ -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 index 00000000000..787decd599e --- /dev/null +++ b/extern/rangetree/SConscript @@ -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 index 00000000000..2a47c5a1d93 --- /dev/null +++ b/extern/rangetree/range_tree.hh @@ -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 +#include +#include +#include + +#ifndef RANGE_TREE_DEBUG_PRINT_FUNCTION +# define RANGE_TREE_DEBUG_PRINT_FUNCTION 0 +#endif + +template +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 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& 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 << " "; + 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 index 00000000000..56f2d90d329 --- /dev/null +++ b/extern/rangetree/range_tree_c_api.cc @@ -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 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 index 00000000000..af6a7b161a8 --- /dev/null +++ b/extern/rangetree/range_tree_c_api.h @@ -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 */ + +#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__ */ diff --git a/source/blenderplayer/CMakeLists.txt b/source/blenderplayer/CMakeLists.txt index 85bb07d6e83..d606605e8d5 100644 --- a/source/blenderplayer/CMakeLists.txt +++ b/source/blenderplayer/CMakeLists.txt @@ -149,6 +149,7 @@ endif() bf_intern_raskter bf_intern_opencolorio bf_intern_opennl + extern_rangetree ) if(WITH_MOD_CLOTH_ELTOPO) diff --git a/source/creator/CMakeLists.txt b/source/creator/CMakeLists.txt index b66c000ac89..c53f27c7326 100644 --- a/source/creator/CMakeLists.txt +++ b/source/creator/CMakeLists.txt @@ -914,6 +914,7 @@ endif() cycles_subd bf_intern_raskter bf_intern_opencolorio + extern_rangetree ) if(WITH_COMPOSITOR) -- cgit v1.2.3