8 #ifndef Sawyer_IntervalSet_H
9 #define Sawyer_IntervalSet_H
11 #include <Sawyer/IntervalMap.h>
12 #include <Sawyer/Optional.h>
13 #include <Sawyer/Sawyer.h>
15 #include <boost/integer_traits.hpp>
16 #include <boost/iterator/iterator_facade.hpp>
17 #include <boost/serialization/access.hpp>
18 #include <boost/serialization/nvp.hpp>
61 friend class boost::serialization::access;
64 void serialize(S &s,
const unsigned ) {
65 s & BOOST_SERIALIZATION_NVP(map_);
77 boost::bidirectional_traversal_tag> {
79 MapNodeIterator iter_;
83 friend class boost::iterator_core_access;
86 const Interval& dereference()
const {
return iter_->key(); }
88 void increment() { ++iter_; }
89 void decrement() { --iter_; }
90 MapNodeIterator base()
const {
return iter_; }
100 class ConstScalarIterator:
public boost::iterator_facade<ConstScalarIterator, const typename Interval::Value,
101 boost::bidirectional_traversal_tag> {
109 friend class boost::iterator_core_access;
112 ASSERT_require2(iter_->least() <= iter_->greatest(),
"stored interval cannot be empty");
113 ASSERT_require(iter_->least() + offset_ <= iter_->greatest());
114 value_ = iter_->least() + offset_;
118 return iter_ == other.iter_ && offset_ == other.offset_;
121 ASSERT_require2(iter_->least() <= iter_->greatest(),
"stored interval cannot be empty");
122 if (iter_->least() + offset_ == iter_->greatest()) {
130 ASSERT_require2(iter_->least() <= iter_->greatest(),
"stored interval cannot be empty");
133 offset_ = width(*iter_);
152 template<
class Interval2>
155 for (OtherIntervalIterator otherIter=other.
intervals().begin(); otherIter!=other.
intervals().end(); ++otherIter)
163 template<
class Interval2,
class T,
class Policy>
166 for (OtherNodeIterator otherIter=other.
nodes().begin(); otherIter!=other.
nodes().end(); ++otherIter)
174 template<
class Iterator>
176 for (Iterator iter=intervals.begin(); iter!=intervals.end(); ++iter)
184 template<
class Interval2>
188 for (OtherIntervalIterator otherIter=other.
intervals().begin(); otherIter!=other.
intervals().end(); ++otherIter)
199 template<
class Interval2,
class T,
class Policy>
203 for (OtherNodeIterator otherIter=other.
nodes().begin(); otherIter!=other.
nodes().end(); ++otherIter)
212 template<
class Iterator>
215 for (Iterator iter=intervals.begin(); iter!=intervals.end(); ++iter)
225 boost::iterator_range<ConstIntervalIterator>
intervals()
const {
226 return boost::iterator_range<ConstIntervalIterator>(ConstIntervalIterator(map_.
nodes().begin()),
227 ConstIntervalIterator(map_.
nodes().end()));
231 boost::iterator_range<ConstScalarIterator>
scalars()
const {
232 return boost::iterator_range<ConstScalarIterator>(ConstScalarIterator(
intervals().begin()),
240 return ConstIntervalIterator(map_.
lowerBound(scalar));
247 return ConstIntervalIterator(map_.
upperBound(scalar));
254 return ConstIntervalIterator(map_.
findPrior(scalar));
261 return ConstIntervalIterator(map_.
find(scalar));
267 boost::iterator_range<ConstIntervalIterator>
findAll(
const Interval &interval)
const {
268 boost::iterator_range<typename Map::ConstNodeIterator> range = map_.
findAll(interval);
269 return boost::iterator_range<ConstIntervalIterator>(ConstIntervalIterator(range.begin()),
270 ConstIntervalIterator(range.end()));
285 std::pair<ConstIntervalIterator, ConstIntervalIterator>
287 std::pair<typename Map::ConstNodeIterator, typename Map::ConstNodeIterator> found =
289 return std::make_pair(ConstIntervalIterator(found.first), ConstIntervalIterator(found.second));
334 template<
class Interval2>
336 return map_.isOverlapping(interval);
338 template<
class Interval2>
343 template<
class Interval2>
345 return map_.overlaps(other.map_);
347 template<
class Interval2>
352 template<
class Interval2,
class T2,
class Policy2>
354 return map_.overlaps(other);
356 template<
class Interval2,
class T2,
class Policy2>
367 template<
class Interval2>
372 template<
class Interval2>
377 template<
class Interval2,
class T2,
class Policy2>
399 template<
class Interval2>
401 return map_.contains(interval);
404 template<
class Interval2>
406 return map_.contains(other.map_);
409 template<
class Interval2,
class T2,
class Policy2>
411 return map_.contains(other);
436 return map_.
least(lowerLimit);
473 return ConstIntervalIterator(map_.
firstFit(size, start.iter_));
487 return ConstIntervalIterator(map_.
bestFit(size, start.iter_));
513 void invert(
const Interval &restricted) {
517 bool insertTop =
true;
520 if (iter->least() > restricted.
greatest())
522 if (pending < iter->
least())
524 if (iter->greatest() < restricted.
greatest()) {
525 pending = iter->greatest() + 1;
534 std::swap(map_, inverted.map_);
543 template<
class Interval2>
548 template<
class Interval2>
551 for (OtherIterator otherIter=other.
intervals().begin(); otherIter!=other.
intervals().end(); ++otherIter)
552 map_.
insert(*otherIter, 0);
555 template<
class Interval2,
class T,
class Policy>
558 for (OtherIterator otherIter=other.
intervals().begin(); otherIter!=other.
intervals().end(); ++otherIter)
559 map_.
insert(*otherIter, 0);
569 template<
class Interval2>
570 void erase(
const Interval2 &interval) {
571 map_.
erase(interval);
574 template<
class Interval2>
576 ASSERT_forbid2((
void*)&other==(
void*)
this,
"use IntervalSet::clear() instead");
578 for (OtherIntervalIterator otherIter=other.
intervals().begin(); otherIter!=other.
intervals().end(); ++otherIter)
579 map_.
erase(*otherIter);
582 template<
class Interval2,
class T,
class Policy>
585 for (OtherIntervalIterator otherIter=other.
intervals().begin(); otherIter!=other.
intervals().end(); ++otherIter)
586 map_.
erase(otherIter->first);
597 template<
class Interval2>
601 if (interval.isEmpty()) {
607 if (
hull().greatest() > interval.greatest())
611 template<
class Interval2>
617 template<
class Interval2,
class T,
class Policy>
628 return !(*
this!=other);
NodeIterator upperBound(const typename Interval::Value &scalar)
Find the first node whose interval begins above the specified scalar key.
NodeIterator firstFit(const typename Interval::Value &size, NodeIterator start)
Find the first fit node at or after a starting point.
IntervalSet operator|(const IntervalSet &other) const
Union of two sets.
Interval hull() const
Returns the range of values in this map.
boost::iterator_range< ConstIntervalIterator > intervals() const
Iterators for traversing keys.
IntervalSet & operator-=(const Interval &interval)
In-place subtraction of an interval.
size_t nIntervals() const
Number of storage nodes.
IntervalSet & operator-=(const IntervalSet &other)
In-place subtraction.
ConstIntervalIterator upperBound(const typename Interval::Value &scalar) const
Find the first node whose interval begins above the specified scalar key.
ConstIntervalIterator bestFit(const typename Interval::Value &size, ConstIntervalIterator start) const
Find the best fit node at or after a starting point.
Optional< Scalar > greatestNonExistent(Scalar upperLimit) const
Returns the limited-maximum scalar not contained in this set.
bool isEmpty() const
True if interval is empty.
NodeIterator findPrior(const typename Interval::Value &scalar)
Find the last node whose interval starts at or below the specified scalar key.
IntervalSet & operator&=(const Interval &interval)
In-place intersection with an interval.
IntervalSet operator-(const IntervalSet &other) const
Subtract another set from this one.
IntervalSet & operator&=(const IntervalSet &other)
In-place intersection.
IntervalSet operator~() const
Return inverse of specified set.
bool contains(const IntervalMap< Interval2, T2, Policy2 > &other) const
Determines whether this set fully contains the argument.
ConstIntervalIterator lowerBound(const typename Interval::Value &scalar) const
Find the first node whose interval ends at or above the specified scalar key.
IntervalSet()
Default constructor.
Interval::Value least() const
Returns the minimum scalar key.
bool exists(const typename Interval::Value &scalar) const
Determines if a value exists in the set.
IntervalSet operator&(const IntervalSet &other) const
Intersection of two sets.
Optional< Scalar > least(Scalar lowerLimit) const
Returns the limited-minimum scalar contained in this set.
bool isEmpty() const
Determine whether the container is empty.
Holds a value or nothing.
NodeIterator bestFit(const typename Interval::Value &size, NodeIterator start)
Find the best fit node at or after a starting point.
bool contains(const Interval2 &interval) const
Determines whether this set fully contains the argument.
bool isOverlapping(const IntervalMap< Interval2, T2, Policy2 > &other) const
Determines whether this set overlaps with the argument.
IntervalSet operator&(const Interval &interval) const
Intersection of set with interval.
IntervalSet operator-(const Interval &interval) const
Subtract an interval from this set.
bool operator!=(const IntervalSet &other) const
Determines if two sets contain different elements.
IntervalSet(const boost::iterator_range< Iterator > &intervals)
Construct from an iterator range.
bool isDistinct(const IntervalSet< Interval2 > &other) const
Determines whether this set is distinct from the argument.
T Value
Types of values in the interval.
bool overlaps(const IntervalMap< Interval2, T2, Policy2 > &other) const
Determines whether this set overlaps with the argument.
Interval::Value size() const
Returns the number of values represented by this container.
bool isEmpty() const
Determine if the container is empty.
Interval::Value greatest() const
Returns the maximum scalar key.
void insertMultiple(const IntervalSet< Interval2 > &other)
Insert specified values.
IntervalSet(const IntervalSet< Interval2 > &other)
Copy constructor.
A container holding a set of values.
IntervalSet & operator|=(const IntervalSet &other)
In-place union.
void insert(const Interval2 &interval)
Insert specified values.
Name space for the entire library.
void eraseMultiple(const IntervalSet< Interval2 > &other)
Remove specified values.
Optional< typename Interval::Value > leastUnmapped(typename Interval::Value lowerLimit) const
Returns the limited-minimum unmapped scalar key.
T least() const
Returns lower limit.
IntervalSet operator|(const Interval &interval) const
Union of set with interval.
NodeIterator findFirstOverlap(const Interval &interval)
Find first interval that overlaps with the specified interval.
ConstIntervalIterator findPrior(const typename Interval::Value &scalar) const
Find the last node whose interval starts at or below the specified scalar key.
IntervalSet(const IntervalMap< Interval2, T, Policy > &other)
Construct from an IntervalMap.
void clear()
Empties the container.
void erase(const Interval &erasure)
Erase the specified interval.
IntervalSet & operator=(const IntervalMap< Interval2, T, Policy > &other)
Assignment from an IntervalMap.
boost::iterator_range< ConstScalarIterator > scalars() const
Iterator range for all scalar values logically represented by this set.
void insert(Interval key, Value value, bool makeHole=true)
Insert a key/value pair.
void erase(const Interval2 &interval)
Remove specified values.
static Interval whole()
Construct an interval that covers the entire domain.
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
ConstIntervalIterator findFirstOverlap(const Interval &interval) const
Finds first node that overlaps with the specified interval.
Optional< Scalar > greatest(Scalar upperLimit) const
Returns the limited-maximum scalar contained in this set.
bool isOverlapping(const IntervalSet< Interval2 > &other) const
Determines whether this set overlaps with the argument.
Optional< typename Interval::Value > greatestUnmapped(typename Interval::Value upperLimit) const
Returns the limited-maximum unmapped scalar key.
bool contains(const typename Interval::Value &scalar) const
Determines whether this set fully contains the argument.
void intersect(const Interval2 &interval)
Interset with specified values.
void eraseMultiple(const IntervalMap< Interval2, T, Policy > &other)
Remove specified values.
boost::iterator_range< NodeIterator > nodes()
Iterators for traversing nodes.
Optional< Scalar > leastNonExistent(Scalar lowerLimit) const
Returns the limited-minimum scalar not contained in this set.
Interval hull() const
Returns the range of values in this map.
IntervalSet & operator=(const boost::iterator_range< Iterator > &intervals)
Assignment from an iterator range.
bool isOverlapping(const Interval2 &interval) const
Determines whether this set overlaps with the argument.
void clear()
Remove all values.
boost::iterator_range< NodeIterator > findAll(const Interval &interval)
Finds all nodes overlapping the specified interval.
IntervalSet & operator=(const IntervalSet< Interval2 > &other)
Assignment from another set.
boost::iterator_range< ConstIntervalIterator > intervals() const
Iterator range for all intervals actually stored by this set.
Scalar least() const
Returns the minimum scalar contained in this set.
IntervalSet & operator|=(const Interval &interval)
In-place union with interval.
bool isDistinct(const IntervalMap< Interval2, T2, Policy2 > &other) const
Determines whether this set is distinct from the argument.
bool isDistinct(const Interval2 &interval) const
Determines whether this set is distinct from the argument.
Bidirectional iterator over keys.
void insertMultiple(const IntervalMap< Interval2, T, Policy > &other)
Insert specified values.
size_t nIntervals() const
Number of nodes in the container.
void invert(const Interval &restricted)
Invert and intersect.
NodeIterator lowerBound(const typename Interval::Value &scalar)
Find the first node whose interval ends at or above the specified scalar key.
Interval::Value size() const
Number of scalar elements represented.
bool contains(const IntervalSet< Interval2 > &other) const
Determines whether this set fully contains the argument.
ConstIntervalIterator firstFit(const typename Interval::Value &size, ConstIntervalIterator start) const
Find the first fit node at or after a starting point.
T greatest() const
Returns upper limit.
NodeIterator find(const typename Interval::Value &scalar)
Find the node containing the specified scalar key.
bool operator==(const IntervalSet &other) const
Determines if two sets contain the same elements.
void intersect(IntervalSet< Interval2 > other)
Interset with specified values.
Scalar greatest() const
Returns the maximum scalar contained in this set.
ConstIntervalIterator find(const typename Interval::Value &scalar) const
Find the node containing the specified scalar key.
I::Value Scalar
Type of scalar values stored in this set.
void eraseMultiple(const IntervalMap< Interval, T2, Policy2 > &other)
Erase intervals specified in another IntervalMap.
boost::iterator_range< ConstIntervalIterator > findAll(const Interval &interval) const
Finds all nodes overlapping the specified interval.
bool overlaps(const Interval2 &interval) const
Determines whether this set overlaps with the argument.
Bidirectional iterator over key/value nodes.
bool overlaps(const IntervalSet< Interval2 > &other) const
Determines whether this set overlaps with the argument.
std::pair< ConstIntervalIterator, ConstIntervalIterator > findFirstOverlap(ConstIntervalIterator thisIter, const IntervalSet &other, ConstIntervalIterator otherIter) const
Find first nodes that overlap.