/* * * Copyright (c) 2011 Erik Garrison * * Permission is hereby granted, free of charge, to any person obtaining a copy of * this software and associated documentation files (the "Software"), to deal in * the Software without restriction, including without limitation the rights to * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies * of the Software, and to permit persons to whom the Software is furnished to do * so, subject to the following conditions: * The above copyright notice and this permission notice shall be included in all * copies or substantial portions of the Software. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ // Pulled from https://github.com/ekg/intervaltree - thanks to Erik Garrison #ifndef __INTERVAL_TREE_H #define __INTERVAL_TREE_H #include #include #include template class Interval { public: K start; K stop; T value; Interval(K s, K e, const T& v) : start(s) , stop(e) , value(v) { } }; template K intervalStart(const Interval& i) { return i.start; } template K intervalStop(const Interval& i) { return i.stop; } template std::ostream& operator<<(std::ostream& out, Interval& i) { out << "Interval(" << i.start << ", " << i.stop << "): " << i.value; return out; } template class IntervalStartSorter { public: bool operator() (const Interval& a, const Interval& b) { return a.start < b.start; } }; template class IntervalTree { public: typedef Interval interval; typedef std::vector intervalVector; typedef IntervalTree intervalTree; intervalVector intervals; intervalTree* left; intervalTree* right; K center; IntervalTree(void) : left(NULL) , right(NULL) , center(0) { } IntervalTree(const intervalTree& other) : left(NULL) , right(NULL) { center = other.center; intervals = other.intervals; if (other.left) { left = new intervalTree(*other.left); } if (other.right) { right = new intervalTree(*other.right); } } IntervalTree& operator=(const intervalTree& other) { center = other.center; intervals = other.intervals; if (other.left) { left = new intervalTree(*other.left); } else { if (left) delete left; left = NULL; } if (other.right) { right = new intervalTree(*other.right); } else { if (right) delete right; right = NULL; } return *this; } IntervalTree( intervalVector& ivals, std::size_t depth = 16, std::size_t minbucket = 64, K leftextent = 0, K rightextent = 0, std::size_t maxbucket = 512 ) : left(NULL) , right(NULL) { --depth; IntervalStartSorter intervalStartSorter; if (depth == 0 || (ivals.size() < minbucket && ivals.size() < maxbucket)) { std::sort(ivals.begin(), ivals.end(), intervalStartSorter); intervals = ivals; } else { if (leftextent == 0 && rightextent == 0) { // sort intervals by start std::sort(ivals.begin(), ivals.end(), intervalStartSorter); } K leftp = 0; K rightp = 0; K centerp = 0; if (leftextent || rightextent) { leftp = leftextent; rightp = rightextent; } else { leftp = ivals.front().start; std::vector stops; stops.resize(ivals.size()); transform(ivals.begin(), ivals.end(), stops.begin(), intervalStop); rightp = *max_element(stops.begin(), stops.end()); } //centerp = ( leftp + rightp ) / 2; centerp = ivals.at(ivals.size() / 2).start; center = centerp; intervalVector lefts; intervalVector rights; for (typename intervalVector::iterator i = ivals.begin(); i != ivals.end(); ++i) { interval& interval = *i; if (interval.stop < center) { lefts.push_back(interval); } else if (interval.start > center) { rights.push_back(interval); } else { intervals.push_back(interval); } } if (!lefts.empty()) { left = new intervalTree(lefts, depth, minbucket, leftp, centerp); } if (!rights.empty()) { right = new intervalTree(rights, depth, minbucket, centerp, rightp); } } } void findOverlapping(K start, K stop, intervalVector& overlapping) const { if (!intervals.empty() && ! (stop < intervals.front().start)) { for (typename intervalVector::const_iterator i = intervals.begin(); i != intervals.end(); ++i) { const interval& interval = *i; if (interval.stop >= start && interval.start <= stop) { overlapping.push_back(interval); } } } if (left && start <= center) { left->findOverlapping(start, stop, overlapping); } if (right && stop >= center) { right->findOverlapping(start, stop, overlapping); } } void findContained(K start, K stop, intervalVector& contained) const { if (!intervals.empty() && ! (stop < intervals.front().start)) { for (typename intervalVector::const_iterator i = intervals.begin(); i != intervals.end(); ++i) { const interval& interval = *i; if (interval.start >= start && interval.stop <= stop) { contained.push_back(interval); } } } if (left && start <= center) { left->findContained(start, stop, contained); } if (right && stop >= center) { right->findContained(start, stop, contained); } } ~IntervalTree(void) { // traverse the left and right // delete them all the way down if (left) { delete left; } if (right) { delete right; } } }; #endif