[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [53431] trunk/blender: Import the RangeTree library into extern
Nicholas Bishop
nicholasbishop at gmail.com
Sun Dec 30 19:20:55 CET 2012
Revision: 53431
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=53431
Author: nicholasbishop
Date: 2012-12-30 18:20:52 +0000 (Sun, 30 Dec 2012)
Log Message:
-----------
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.
Modified Paths:
--------------
trunk/blender/extern/CMakeLists.txt
trunk/blender/extern/SConscript
trunk/blender/source/blenderplayer/CMakeLists.txt
trunk/blender/source/creator/CMakeLists.txt
Added Paths:
-----------
trunk/blender/extern/rangetree/
trunk/blender/extern/rangetree/CMakeLists.txt
trunk/blender/extern/rangetree/README.org
trunk/blender/extern/rangetree/SConscript
trunk/blender/extern/rangetree/range_tree.hh
trunk/blender/extern/rangetree/range_tree_c_api.cc
trunk/blender/extern/rangetree/range_tree_c_api.h
Modified: trunk/blender/extern/CMakeLists.txt
===================================================================
--- trunk/blender/extern/CMakeLists.txt 2012-12-30 18:17:20 UTC (rev 53430)
+++ trunk/blender/extern/CMakeLists.txt 2012-12-30 18:20:52 UTC (rev 53431)
@@ -27,6 +27,7 @@
remove_strict_flags()
add_subdirectory(colamd)
+add_subdirectory(rangetree)
if(WITH_BULLET)
add_subdirectory(bullet2)
Modified: trunk/blender/extern/SConscript
===================================================================
--- trunk/blender/extern/SConscript 2012-12-30 18:17:20 UTC (rev 53430)
+++ trunk/blender/extern/SConscript 2012-12-30 18:20:52 UTC (rev 53431)
@@ -4,6 +4,7 @@
SConscript(['glew/SConscript'])
SConscript(['colamd/SConscript'])
+SConscript(['rangetree/SConscript'])
if env['WITH_BF_GAMEENGINE']:
SConscript(['recastnavigation/SConscript'])
Added: trunk/blender/extern/rangetree/CMakeLists.txt
===================================================================
--- trunk/blender/extern/rangetree/CMakeLists.txt (rev 0)
+++ trunk/blender/extern/rangetree/CMakeLists.txt 2012-12-30 18:20:52 UTC (rev 53431)
@@ -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}" "")
+
Added: trunk/blender/extern/rangetree/README.org
===================================================================
--- trunk/blender/extern/rangetree/README.org (rev 0)
+++ trunk/blender/extern/rangetree/README.org 2012-12-30 18:20:52 UTC (rev 53431)
@@ -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
Added: trunk/blender/extern/rangetree/SConscript
===================================================================
--- trunk/blender/extern/rangetree/SConscript (rev 0)
+++ trunk/blender/extern/rangetree/SConscript 2012-12-30 18:20:52 UTC (rev 53431)
@@ -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] )
Added: trunk/blender/extern/rangetree/range_tree.hh
===================================================================
--- trunk/blender/extern/rangetree/range_tree.hh (rev 0)
+++ trunk/blender/extern/rangetree/range_tree.hh 2012-12-30 18:20:52 UTC (rev 53431)
@@ -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;
+};
Added: trunk/blender/extern/rangetree/range_tree_c_api.cc
===================================================================
--- trunk/blender/extern/rangetree/range_tree_c_api.cc (rev 0)
+++ trunk/blender/extern/rangetree/range_tree_c_api.cc 2012-12-30 18:20:52 UTC (rev 53431)
@@ -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.
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list