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>
58#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
60 friend class boost::serialization::access;
63 void serialize(S &s,
const unsigned ) {
64 s & BOOST_SERIALIZATION_NVP(map_);
68#ifdef SAWYER_HAVE_CEREAL
70 friend class cereal::access;
72 template<
class Archive>
73 void CEREAL_SERIALIZE_FUNCTION_NAME(Archive &archive) {
74 archive(CEREAL_NVP(map_));
88 boost::bidirectional_traversal_tag> {
90 MapNodeIterator iter_;
94 friend class boost::iterator_core_access;
97 const Interval& dereference()
const {
return iter_->key(); }
99 void increment() { ++iter_; }
100 void decrement() { --iter_; }
101 MapNodeIterator base()
const {
return iter_; }
111 class ConstScalarIterator:
public boost::iterator_facade<ConstScalarIterator, const typename Interval::Value,
112 boost::bidirectional_traversal_tag> {
120 friend class boost::iterator_core_access;
123 ASSERT_require2(iter_->least() <= iter_->greatest(),
"stored interval cannot be empty");
124 ASSERT_require(iter_->least() + offset_ <= iter_->
greatest());
125 value_ = iter_->least() + offset_;
129 return iter_ == other.iter_ && offset_ == other.offset_;
132 ASSERT_require2(iter_->least() <= iter_->greatest(),
"stored interval cannot be empty");
133 if (iter_->least() + offset_ == iter_->greatest()) {
141 ASSERT_require2(iter_->least() <= iter_->greatest(),
"stored interval cannot be empty");
144 offset_ = width(*iter_);
163 template<
class Interval2>
166 for (OtherIntervalIterator otherIter=other.
intervals().begin(); otherIter!=other.
intervals().end(); ++otherIter)
174 template<
class Interval2,
class T,
class Policy>
177 for (OtherNodeIterator otherIter=other.
nodes().begin(); otherIter!=other.
nodes().end(); ++otherIter)
185 template<
class Iterator>
195 template<
class Interval2>
199 for (OtherIntervalIterator otherIter=other.
intervals().begin(); otherIter!=other.
intervals().end(); ++otherIter)
210 template<
class Interval2,
class T,
class Policy>
214 for (OtherNodeIterator otherIter=other.
nodes().begin(); otherIter!=other.
nodes().end(); ++otherIter)
223 template<
class Iterator>
236 boost::iterator_range<ConstIntervalIterator>
intervals()
const {
242 boost::iterator_range<ConstScalarIterator>
scalars()
const {
278 boost::iterator_range<ConstIntervalIterator>
findAll(
const Interval &interval)
const {
279 boost::iterator_range<typename Map::ConstNodeIterator> range = map_.
findAll(interval);
295 std::pair<ConstIntervalIterator, ConstIntervalIterator>
297 std::pair<typename Map::ConstNodeIterator, typename Map::ConstNodeIterator> found =
344 template<
class Interval2>
346 return map_.isOverlapping(interval);
348 template<
class Interval2>
353 template<
class Interval2>
355 return map_.overlaps(other.map_);
357 template<
class Interval2>
362 template<
class Interval2,
class T2,
class Policy2>
364 return map_.overlaps(other);
366 template<
class Interval2,
class T2,
class Policy2>
377 template<
class Interval2>
382 template<
class Interval2>
387 template<
class Interval2,
class T2,
class Policy2>
409 template<
class Interval2>
411 return map_.contains(interval);
414 template<
class Interval2>
416 return map_.contains(other.map_);
419 template<
class Interval2,
class T2,
class Policy2>
421 return map_.contains(other);
446 return map_.
least(lowerLimit);
523 void invert(
const Interval &restricted) {
525 if (!restricted.isEmpty()) {
527 bool insertTop =
true;
530 if (iter->least() > restricted.greatest())
532 if (pending < iter->
least())
534 if (iter->greatest() < restricted.greatest()) {
535 pending = iter->greatest() + 1;
544 std::swap(map_, inverted.map_);
553 template<
class Interval2>
558 template<
class Interval2>
561 for (OtherIterator otherIter=other.
intervals().begin(); otherIter!=other.
intervals().end(); ++otherIter)
562 map_.
insert(*otherIter, 0);
565 template<
class Interval2,
class T,
class Policy>
568 for (OtherIterator otherIter=other.
intervals().begin(); otherIter!=other.
intervals().end(); ++otherIter)
569 map_.
insert(*otherIter, 0);
579 template<
class Interval2>
580 void erase(
const Interval2 &interval) {
581 map_.
erase(interval);
584 template<
class Interval2>
586 ASSERT_forbid2((
void*)&other==(
void*)
this,
"use IntervalSet::clear() instead");
588 for (OtherIntervalIterator otherIter=other.
intervals().begin(); otherIter!=other.
intervals().end(); ++otherIter)
589 map_.
erase(*otherIter);
592 template<
class Interval2,
class T,
class Policy>
595 for (OtherIntervalIterator otherIter=other.
intervals().begin(); otherIter!=other.
intervals().end(); ++otherIter)
596 map_.
erase(otherIter->first);
607 template<
class Interval2>
611 if (interval.isEmpty()) {
621 template<
class Interval2>
627 template<
class Interval2,
class T,
class Policy>
638 return !(*
this!=other);
706 return *
this | other;
722 return *
this | interval;
An associative container whose keys are non-overlapping intervals.
size_t nIntervals() const
Number of nodes in the container.
void insert(Interval key, Value value, bool makeHole=true)
Insert a key/value pair.
void clear()
Empties the container.
Interval::Value greatest() const
Returns the maximum scalar key.
void eraseMultiple(const IntervalMap< Interval, T2, Policy2 > &other)
Erase intervals specified in another IntervalMap.
Interval hull() const
Returns the range of values in this map.
NodeIterator upperBound(const typename Interval::Value &scalar)
Find the first node whose interval begins above the specified scalar key.
boost::iterator_range< NodeIterator > nodes()
Iterators for traversing nodes.
Interval::Value least() const
Returns the minimum scalar key.
NodeIterator firstFit(const typename Interval::Value &size, NodeIterator start)
Find the first fit node at or after a starting point.
void erase(const Interval &erasure)
Erase the specified interval.
NodeIterator lowerBound(const typename Interval::Value &scalar)
Find the first node whose interval ends at or above the specified scalar key.
NodeIterator find(const typename Interval::Value &scalar)
Find the node containing the specified scalar key.
boost::iterator_range< ConstIntervalIterator > intervals() const
Iterators for traversing keys.
boost::iterator_range< NodeIterator > findAll(const Interval &interval)
Finds all nodes overlapping the specified interval.
NodeIterator findPrior(const typename Interval::Value &scalar)
Find the last node whose interval starts at or below the specified scalar key.
NodeIterator findFirstOverlap(const Interval &interval)
Find first interval that overlaps with the specified interval.
Optional< typename Interval::Value > greatestUnmapped(typename Interval::Value upperLimit) const
Returns the limited-maximum unmapped scalar key.
bool isEmpty() const
Determine if the container is empty.
Interval::Value size() const
Returns the number of values represented by this container.
Optional< typename Interval::Value > leastUnmapped(typename Interval::Value lowerLimit) const
Returns the limited-minimum unmapped scalar key.
NodeIterator bestFit(const typename Interval::Value &size, NodeIterator start)
Find the best fit node at or after a starting point.
A container holding a set of values.
bool isOverlapping(const IntervalSet< Interval2 > &other) const
Determines whether this set overlaps with the argument.
ConstIntervalIterator bestFit(const typename Interval::Value &size, ConstIntervalIterator start) const
Find the best fit node at or after a starting point.
bool isDistinct(const IntervalSet< Interval2 > &other) const
Determines whether this set is distinct from the argument.
IntervalSet & operator+=(const IntervalSet &other)
In-place union.
IntervalSet operator-(const IntervalSet &other) const
Subtract another set from this one.
void erase(const Interval2 &interval)
Remove specified values.
ConstIntervalIterator upperBound(const typename Interval::Value &scalar) const
Find the first node whose interval begins above the specified scalar key.
IntervalSet & operator|=(const Interval &interval)
In-place union with interval.
bool overlaps(const IntervalMap< Interval2, T2, Policy2 > &other) const
Determines whether this set overlaps with the argument.
bool exists(const typename Interval::Value &scalar) const
Determines if a value exists in the set.
ConstIntervalIterator findFirstOverlap(const Interval &interval) const
Finds first node that overlaps with the specified interval.
void eraseMultiple(const IntervalMap< Interval2, T, Policy > &other)
Remove specified values.
IntervalSet & operator|=(const IntervalSet &other)
In-place union.
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.
ConstIntervalIterator findPrior(const typename Interval::Value &scalar) const
Find the last node whose interval starts at or below the specified scalar key.
Optional< Scalar > least(Scalar lowerLimit) const
Returns the limited-minimum scalar contained in this set.
Optional< Scalar > greatest(Scalar upperLimit) const
Returns the limited-maximum scalar contained in this set.
boost::iterator_range< ConstScalarIterator > scalars() const
Iterator range for all scalar values logically represented by this set.
bool contains(const IntervalSet< Interval2 > &other) const
Determines whether this set fully contains the argument.
void intersect(const IntervalMap< Interval2, T, Policy > &other)
Interset with specified values.
IntervalSet operator~() const
Return inverse of specified set.
Optional< Scalar > greatestNonExistent(Scalar upperLimit) const
Returns the limited-maximum scalar not contained in this set.
Interval hull() const
Returns the range of values in this map.
boost::iterator_range< ConstIntervalIterator > findAll(const Interval &interval) const
Finds all nodes overlapping the specified interval.
bool contains(const typename Interval::Value &scalar) const
Determines whether this set fully contains the argument.
IntervalSet()
Default constructor.
void eraseMultiple(const IntervalSet< Interval2 > &other)
Remove specified values.
IntervalSet(const IntervalSet< Interval2 > &other)
Copy constructor.
IntervalSet & operator+=(const Interval &interval)
In-place union with interval.
IntervalSet operator&(const Interval &interval) const
Intersection of set with interval.
ConstIntervalIterator firstFit(const typename Interval::Value &size, ConstIntervalIterator start) const
Find the first fit node at or after a starting point.
void insertMultiple(const IntervalMap< Interval2, T, Policy > &other)
Insert specified values.
Interval::Value size() const
Number of scalar elements represented.
bool overlaps(const IntervalSet< Interval2 > &other) const
Determines whether this set overlaps with the argument.
ConstIntervalIterator lowerBound(const typename Interval::Value &scalar) const
Find the first node whose interval ends at or above the specified scalar key.
bool isOverlapping(const IntervalMap< Interval2, T2, Policy2 > &other) const
Determines whether this set overlaps with the argument.
size_t nIntervals() const
Number of storage nodes.
bool operator==(const IntervalSet &other) const
Determines if two sets contain the same elements.
bool overlaps(const Interval2 &interval) const
Determines whether this set overlaps with the argument.
void intersect(IntervalSet< Interval2 > other)
Interset with specified values.
void insert(const Interval2 &interval)
Insert specified values.
IntervalSet operator&(const IntervalSet &other) const
Intersection of two sets.
bool isEmpty() const
Determine whether the container is empty.
IntervalSet operator+(const IntervalSet &other) const
Union of two sets.
IntervalSet operator|(const Interval &interval) const
Union of set with interval.
Scalar least() const
Returns the minimum scalar contained in this set.
void clear()
Remove all values.
bool contains(const Interval2 &interval) const
Determines whether this set fully contains the argument.
bool isDistinct(const Interval2 &interval) const
Determines whether this set is distinct from the argument.
IntervalSet operator+(const Interval &interval) const
Union of set with interval.
bool contains(const IntervalMap< Interval2, T2, Policy2 > &other) const
Determines whether this set fully contains the argument.
Optional< Scalar > leastNonExistent(Scalar lowerLimit) const
Returns the limited-minimum scalar not contained in this set.
IntervalSet & operator=(const IntervalSet< Interval2 > &other)
Assignment from another set.
Scalar greatest() const
Returns the maximum scalar contained in this set.
bool isDistinct(const IntervalMap< Interval2, T2, Policy2 > &other) const
Determines whether this set is distinct from the argument.
IntervalSet operator-(const Interval &interval) const
Subtract an interval from this set.
boost::iterator_range< ConstIntervalIterator > intervals() const
Iterator range for all intervals actually stored by this set.
void invert(const Interval &restricted)
Invert and intersect.
IntervalSet & operator-=(const Interval &interval)
In-place subtraction of an interval.
void insertMultiple(const IntervalSet< Interval2 > &other)
Insert specified values.
IntervalSet & operator&=(const Interval &interval)
In-place intersection with an interval.
IntervalSet & operator-=(const IntervalSet &other)
In-place subtraction.
IntervalSet operator|(const IntervalSet &other) const
Union of two sets.
IntervalSet & operator=(const boost::iterator_range< Iterator > &intervals)
Assignment from an iterator range.
IntervalSet & operator&=(const IntervalSet &other)
In-place intersection.
ConstIntervalIterator find(const typename Interval::Value &scalar) const
Find the node containing the specified scalar key.
bool isOverlapping(const Interval2 &interval) 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.
IntervalSet & operator=(const IntervalMap< Interval2, T, Policy > &other)
Assignment from an IntervalMap.
void intersect(const Interval2 &interval)
Interset with specified values.
I::Value Scalar
Type of scalar values stored in this set.
IntervalSet(const IntervalMap< Interval2, T, Policy > &other)
Construct from an IntervalMap.
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
T Value
Types of values in the interval.
static Interval whole()
Construct an interval that covers the entire domain.
Bidirectional iterator over keys.
Bidirectional iterator over key/value nodes.
Holds a value or nothing.