diff options
author | Campbell Barton <ideasman42@gmail.com> | 2016-10-13 07:51:20 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2016-10-26 15:33:41 +0300 |
commit | 72921a1e43033d7fea998dd607a68250da5d93bd (patch) | |
tree | de5defe233ec5b73b6fd7bf8da07b6d4e8270cac /extern/rangetree/range_tree.hh | |
parent | 44522a5b98f908928e93ab32c9d6046de4342d9b (diff) |
RangeTree API rewrite
Rewrite the current range-tree API used by dyn-topo undo
to avoid inefficiencies from stdc++'s set use.
- every call to `take_any` (called for all verts & faces)
removed and added to the set.
- further range adjustment also took 2x btree edits.
This patch inlines a btree which is modified in-place,
so common resizing operations don't need to perform a remove & insert.
Ranges are stored in a list so `take_any` can access the first item
without a btree lookup.
Since range-tree isn't a bottleneck in sculpting, this only gives minor speedups.
Measured approx ~15% overall faster calculation for sculpting,
although this number time doesn't include GPU updates and depends on how
much edits fragment the range-tree.
Diffstat (limited to 'extern/rangetree/range_tree.hh')
-rw-r--r-- | extern/rangetree/range_tree.hh | 251 |
1 files changed, 0 insertions, 251 deletions
diff --git a/extern/rangetree/range_tree.hh b/extern/rangetree/range_tree.hh deleted file mode 100644 index b247a0c6a1e..00000000000 --- a/extern/rangetree/range_tree.hh +++ /dev/null @@ -1,251 +0,0 @@ -/* 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) - {} - - Range& operator=(const Range& v) { - *this = v; - return *this; - } - - 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; - - /* 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)); - } - - /* clone of 'take' that checks if the item exists */ - bool retake(T t) { - #if RANGE_TREE_DEBUG_PRINT_FUNCTION - std::cout << __func__ << "(" << t << ")\n"; - #endif - - TreeIter iter = tree.find(Range(t)); - if (iter == tree.end()) { - return false; - } - - Range cur = *iter; - tree.erase(iter); - if (t > cur.min) - tree.insert(Range(cur.min, t - 1)); - if (t + 1 <= cur.max) - tree.insert(Range(t + 1, cur.max)); - - return true; - } - - - /* 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; -}; |