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.

6 files changed, 427 insertions, 0 deletions

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 <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
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<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
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<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__ */