diff options
Diffstat (limited to 'net/quic/interval_set.h')
| -rw-r--r-- | net/quic/interval_set.h | 856 |
1 files changed, 856 insertions, 0 deletions
diff --git a/net/quic/interval_set.h b/net/quic/interval_set.h new file mode 100644 index 0000000..eae4fd7 --- /dev/null +++ b/net/quic/interval_set.h @@ -0,0 +1,856 @@ +// Copyright 2015 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. +// +// IntervalSet<T> is a data structure used to represent a sorted set of +// non-empty, non-adjacent, and mutually disjoint intervals. Mutations to an +// interval set preserve these properties, altering the set as needed. For +// example, adding [2, 3) to a set containing only [1, 2) would result in the +// set containing the single interval [1, 3). +// +// Supported operations include testing whether an Interval is contained in the +// IntervalSet, comparing two IntervalSets, and performing IntervalSet union, +// intersection, and difference. +// +// IntervalSet maintains the minimum number of entries needed to represent the +// set of underlying intervals. When the IntervalSet is modified (e.g. due to an +// Add operation), other interval entries may be coalesced, removed, or +// otherwise modified in order to maintain this invariant. The intervals are +// maintained in sorted order, by ascending min() value. +// +// The reader is cautioned to beware of the terminology used here: this library +// uses the terms "min" and "max" rather than "begin" and "end" as is +// conventional for the STL. The terminology [min, max) refers to the half-open +// interval which (if the interval is not empty) contains min but does not +// contain max. An interval is considered empty if min >= max. +// +// T is required to be default- and copy-constructible, to have an assignment +// operator, a difference operator (operator-()), and the full complement of +// comparison operators (<, <=, ==, !=, >=, >). These requirements are inherited +// from Interval<T>. +// +// IntervalSet has constant-time move operations. +// +// This class is thread-compatible if T is thread-compatible. (See +// go/thread-compatible). +// +// Examples: +// IntervalSet<int> intervals; +// intervals.Add(Interval<int>(10, 20)); +// intervals.Add(Interval<int>(30, 40)); +// // intervals contains [10,20) and [30,40). +// intervals.Add(Interval<int>(15, 35)); +// // intervals has been coalesced. It now contains the single range [10,40). +// EXPECT_EQ(1, intervals.Size()); +// EXPECT_TRUE(intervals.Contains(Interval<int>(10, 40))); +// +// intervals.Difference(Interval<int>(10, 20)); +// // intervals should now contain the single range [20, 40). +// EXPECT_EQ(1, intervals.Size()); +// EXPECT_TRUE(intervals.Contains(Interval<int>(20, 40))); + +#ifndef NET_QUIC_INTERVAL_SET_H_ +#define NET_QUIC_INTERVAL_SET_H_ + +#include <stddef.h> +#include <algorithm> +#include <set> +#include <string> +#include <utility> +#include <vector> + +#include "base/logging.h" +#include "net/quic/interval.h" + +namespace net { + +template <typename T> +class IntervalSet { + private: + struct IntervalComparator { + bool operator()(const Interval<T>& a, const Interval<T>& b) const; + }; + typedef std::set<Interval<T>, IntervalComparator> Set; + + public: + typedef typename Set::value_type value_type; + typedef typename Set::const_iterator const_iterator; + typedef typename Set::const_reverse_iterator const_reverse_iterator; + + // Instantiates an empty IntervalSet. + IntervalSet() {} + + // Instantiates an IntervalSet containing exactly one initial half-open + // interval [min, max), unless the given interval is empty, in which case the + // IntervalSet will be empty. + explicit IntervalSet(const Interval<T>& interval) { Add(interval); } + + // Instantiates an IntervalSet containing the half-open interval [min, max). + IntervalSet(const T& min, const T& max) { Add(min, max); } + +// TODO(rtenneti): Implement after suupport for std::initializer_list. +#if 0 + IntervalSet(std::initializer_list<value_type> il) { assign(il); } +#endif + + // Clears this IntervalSet. + void Clear() { intervals_.clear(); } + + // Returns the number of disjoint intervals contained in this IntervalSet. + size_t Size() const { return intervals_.size(); } + + // Returns the smallest interval that contains all intervals in this + // IntervalSet, or the empty interval if the set is empty. + Interval<T> SpanningInterval() const; + + // Adds "interval" to this IntervalSet. Adding the empty interval has no + // effect. + void Add(const Interval<T>& interval); + + // Adds the interval [min, max) to this IntervalSet. Adding the empty interval + // has no effect. + void Add(const T& min, const T& max) { Add(Interval<T>(min, max)); } + + // DEPRECATED(kosak). Use Union() instead. This method merges all of the + // values contained in "other" into this IntervalSet. + void Add(const IntervalSet& other); + + // Returns true if this IntervalSet represents exactly the same set of + // intervals as the ones represented by "other". + bool Equals(const IntervalSet& other) const; + + // Returns true if this IntervalSet is empty. + bool Empty() const { return intervals_.empty(); } + + // Returns true if any interval in this IntervalSet contains the indicated + // value. + bool Contains(const T& value) const; + + // Returns true if there is some interval in this IntervalSet that wholly + // contains the given interval. An interval O "wholly contains" a non-empty + // interval I if O.Contains(p) is true for every p in I. This is the same + // definition used by Interval<T>::Contains(). This method returns false on + // the empty interval, due to a (perhaps unintuitive) convention inherited + // from Interval<T>. + // Example: + // Assume an IntervalSet containing the entries { [10,20), [30,40) }. + // Contains(Interval(15, 16)) returns true, because [10,20) contains + // [15,16). However, Contains(Interval(15, 35)) returns false. + bool Contains(const Interval<T>& interval) const; + + // Returns true if for each interval in "other", there is some (possibly + // different) interval in this IntervalSet which wholly contains it. See + // Contains(const Interval<T>& interval) for the meaning of "wholly contains". + // Perhaps unintuitively, this method returns false if "other" is the empty + // set. The algorithmic complexity of this method is O(other.Size() * + // log(this->Size())), which is not efficient. The method could be rewritten + // to run in O(other.Size() + this->Size()). + bool Contains(const IntervalSet<T>& other) const; + + // Returns true if there is some interval in this IntervalSet that wholly + // contains the interval [min, max). See Contains(const Interval<T>&). + bool Contains(const T& min, const T& max) const { + return Contains(Interval<T>(min, max)); + } + + // Returns true if for some interval in "other", there is some interval in + // this IntervalSet that intersects with it. See Interval<T>::Intersects() + // for the definition of interval intersection. + bool Intersects(const IntervalSet& other) const; + + // Returns an iterator to the Interval<T> in the IntervalSet that contains the + // given value. In other words, returns an iterator to the unique interval + // [min, max) in the IntervalSet that has the property min <= value < max. If + // there is no such interval, this method returns end(). + const_iterator Find(const T& value) const; + + // Returns an iterator to the Interval<T> in the IntervalSet that wholly + // contains the given interval. In other words, returns an iterator to the + // unique interval outer in the IntervalSet that has the property that + // outer.Contains(interval). If there is no such interval, or if interval is + // empty, returns end(). + const_iterator Find(const Interval<T>& interval) const; + + // Returns an iterator to the Interval<T> in the IntervalSet that wholly + // contains [min, max). In other words, returns an iterator to the unique + // interval outer in the IntervalSet that has the property that + // outer.Contains(Interval<T>(min, max)). If there is no such interval, or if + // interval is empty, returns end(). + const_iterator Find(const T& min, const T& max) const { + return Find(Interval<T>(min, max)); + } + + // Returns true if every value within the passed interval is not Contained + // within the IntervalSet. + bool IsDisjoint(const Interval<T>& interval) const; + + // Merges all the values contained in "other" into this IntervalSet. + void Union(const IntervalSet& other); + + // Modifies this IntervalSet so that it contains only those values that are + // currently present both in *this and in the IntervalSet "other". + void Intersection(const IntervalSet& other); + + // Mutates this IntervalSet so that it contains only those values that are + // currently in *this but not in "interval". + void Difference(const Interval<T>& interval); + + // Mutates this IntervalSet so that it contains only those values that are + // currently in *this but not in the interval [min, max). + void Difference(const T& min, const T& max); + + // Mutates this IntervalSet so that it contains only those values that are + // currently in *this but not in the IntervalSet "other". + void Difference(const IntervalSet& other); + + // Mutates this IntervalSet so that it contains only those values that are + // in [min, max) but not currently in *this. + void Complement(const T& min, const T& max); + + // IntervalSet's begin() iterator. The invariants of IntervalSet guarantee + // that for each entry e in the set, e.min() < e.max() (because the entries + // are non-empty) and for each entry f that appears later in the set, + // e.max() < f.min() (because the entries are ordered, pairwise-disjoint, and + // non-adjacent). Modifications to this IntervalSet invalidate these + // iterators. + const_iterator begin() const { return intervals_.begin(); } + + // IntervalSet's end() iterator. + const_iterator end() const { return intervals_.end(); } + + // IntervalSet's rbegin() and rend() iterators. Iterator invalidation + // semantics are the same as those for begin() / end(). + const_reverse_iterator rbegin() const { return intervals_.rbegin(); } + + const_reverse_iterator rend() const { return intervals_.rend(); } + + // Appends the intervals in this IntervalSet to the end of *out. + void Get(std::vector<Interval<T>>* out) const { + out->insert(out->end(), begin(), end()); + } + + // Copies the intervals in this IntervalSet to the given output iterator. + template <typename Iter> + Iter Get(Iter out_iter) const { + return std::copy(begin(), end(), out_iter); + } + + template <typename Iter> + void assign(Iter first, Iter last) { + Clear(); + for (; first != last; ++first) + Add(*first); + } + +// TODO(rtenneti): Implement after suupport for std::initializer_list. +#if 0 + void assign(std::initializer_list<value_type> il) { + assign(il.begin(), il.end()); + } +#endif + + // Returns a human-readable representation of this set. This will typically be + // (though is not guaranteed to be) of the form + // "[a1, b1) [a2, b2) ... [an, bn)" + // where the intervals are in the same order as given by traversal from + // begin() to end(). This representation is intended for human consumption; + // computer programs should not rely on the output being in exactly this form. + std::string ToString() const; + + // Equality for IntervalSet<T>. Delegates to Equals(). + bool operator==(const IntervalSet& other) const { return Equals(other); } + + // Inequality for IntervalSet<T>. Delegates to Equals() (and returns its + // negation). + bool operator!=(const IntervalSet& other) const { return !Equals(other); } + +// TODO(rtenneti): Implement after suupport for std::initializer_list. +#if 0 + IntervalSet& operator=(std::initializer_list<value_type> il) { + assign(il.begin(), il.end()); + return *this; + } +#endif + + // Swap this IntervalSet with *other. This is a constant-time operation. + void Swap(IntervalSet<T>* other) { intervals_.swap(other->intervals_); } + + private: + // Removes overlapping ranges and coalesces adjacent intervals as needed. + void Compact(const typename Set::iterator& begin, + const typename Set::iterator& end); + + // Returns true if this set is valid (i.e. all intervals in it are non-empty, + // non-adjacent, and mutually disjoint). Currently this is used as an + // integrity check by the Intersection() and Difference() methods, but is only + // invoked for debug builds (via DCHECK). + bool Valid() const; + + // Finds the first interval that potentially intersects 'other'. + const_iterator FindIntersectionCandidate(const IntervalSet& other) const; + + // Finds the first interval that potentially intersects 'interval'. + const_iterator FindIntersectionCandidate(const Interval<T>& interval) const; + + // Helper for Intersection() and Difference(): Finds the next pair of + // intervals from 'x' and 'y' that intersect. 'mine' is an iterator + // over x->intervals_. 'theirs' is an iterator over y.intervals_. 'mine' + // and 'theirs' are advanced until an intersecting pair is found. + // Non-intersecting intervals (aka "holes") from x->intervals_ can be + // optionally erased by "on_hole". + template <typename X, typename Func> + static bool FindNextIntersectingPairImpl(X* x, + const IntervalSet& y, + const_iterator* mine, + const_iterator* theirs, + Func on_hole); + + // The variant of the above method that doesn't mutate this IntervalSet. + bool FindNextIntersectingPair(const IntervalSet& other, + const_iterator* mine, + const_iterator* theirs) const { + return FindNextIntersectingPairImpl( + this, other, mine, theirs, + [](const IntervalSet*, const_iterator, const_iterator) {}); + } + + // The variant of the above method that mutates this IntervalSet by erasing + // holes. + bool FindNextIntersectingPairAndEraseHoles(const IntervalSet& other, + const_iterator* mine, + const_iterator* theirs) { + return FindNextIntersectingPairImpl( + this, other, mine, theirs, + [](IntervalSet* x, const_iterator from, const_iterator to) { + x->intervals_.erase(from, to); + }); + } + + // The representation for the intervals. The intervals in this set are + // non-empty, pairwise-disjoint, non-adjacent and ordered in ascending order + // by min(). + Set intervals_; +}; + +template <typename T> +std::ostream& operator<<(std::ostream& out, const IntervalSet<T>& seq); + +template <typename T> +void swap(IntervalSet<T>& x, IntervalSet<T>& y); + +//============================================================================== +// Implementation details: Clients can stop reading here. + +template <typename T> +Interval<T> IntervalSet<T>::SpanningInterval() const { + Interval<T> result; + if (!intervals_.empty()) { + result.SetMin(intervals_.begin()->min()); + result.SetMax(intervals_.rbegin()->max()); + } + return result; +} + +template <typename T> +void IntervalSet<T>::Add(const Interval<T>& interval) { + if (interval.Empty()) + return; + std::pair<typename Set::iterator, bool> ins = intervals_.insert(interval); + if (!ins.second) { + // This interval already exists. + return; + } + // Determine the minimal range that will have to be compacted. We know that + // the IntervalSet was valid before the addition of the interval, so only + // need to start with the interval itself (although Compact takes an open + // range so begin needs to be the interval to the left). We don't know how + // many ranges this interval may cover, so we need to find the appropriate + // interval to end with on the right. + typename Set::iterator begin = ins.first; + if (begin != intervals_.begin()) + --begin; + const Interval<T> target_end(interval.max(), interval.max()); + const typename Set::iterator end = intervals_.upper_bound(target_end); + Compact(begin, end); +} + +template <typename T> +void IntervalSet<T>::Add(const IntervalSet& other) { + for (const_iterator it = other.begin(); it != other.end(); ++it) { + Add(*it); + } +} + +template <typename T> +bool IntervalSet<T>::Equals(const IntervalSet& other) const { + if (intervals_.size() != other.intervals_.size()) + return false; + for (typename Set::iterator i = intervals_.begin(), + j = other.intervals_.begin(); + i != intervals_.end(); ++i, ++j) { + // Simple member-wise equality, since all intervals are non-empty. + if (i->min() != j->min() || i->max() != j->max()) + return false; + } + return true; +} + +template <typename T> +bool IntervalSet<T>::Contains(const T& value) const { + Interval<T> tmp(value, value); + // Find the first interval with min() > value, then move back one step + const_iterator it = intervals_.upper_bound(tmp); + if (it == intervals_.begin()) + return false; + --it; + return it->Contains(value); +} + +template <typename T> +bool IntervalSet<T>::Contains(const Interval<T>& interval) const { + // Find the first interval with min() > value, then move back one step. + const_iterator it = intervals_.upper_bound(interval); + if (it == intervals_.begin()) + return false; + --it; + return it->Contains(interval); +} + +template <typename T> +bool IntervalSet<T>::Contains(const IntervalSet<T>& other) const { + if (!SpanningInterval().Contains(other.SpanningInterval())) { + return false; + } + + for (const_iterator i = other.begin(); i != other.end(); ++i) { + // If we don't contain the interval, can return false now. + if (!Contains(*i)) { + return false; + } + } + return true; +} + +// This method finds the interval that Contains() "value", if such an interval +// exists in the IntervalSet. The way this is done is to locate the "candidate +// interval", the only interval that could *possibly* contain value, and test it +// using Contains(). The candidate interval is the interval with the largest +// min() having min() <= value. +// +// Determining the candidate interval takes a couple of steps. First, since the +// underlying std::set stores intervals, not values, we need to create a "probe +// interval" suitable for use as a search key. The probe interval used is +// [value, value). Now we can restate the problem as finding the largest +// interval in the IntervalSet that is <= the probe interval. +// +// This restatement only works if the set's comparator behaves in a certain way. +// In particular it needs to order first by ascending min(), and then by +// descending max(). The comparator used by this library is defined in exactly +// this way. To see why descending max() is required, consider the following +// example. Assume an IntervalSet containing these intervals: +// +// [0, 5) [10, 20) [50, 60) +// +// Consider searching for the value 15. The probe interval [15, 15) is created, +// and [10, 20) is identified as the largest interval in the set <= the probe +// interval. This is the correct interval needed for the Contains() test, which +// will then return true. +// +// Now consider searching for the value 30. The probe interval [30, 30) is +// created, and again [10, 20] is identified as the largest interval <= the +// probe interval. This is again the correct interval needed for the Contains() +// test, which in this case returns false. +// +// Finally, consider searching for the value 10. The probe interval [10, 10) is +// created. Here the ordering relationship between [10, 10) and [10, 20) becomes +// vitally important. If [10, 10) were to come before [10, 20), then [0, 5) +// would be the largest interval <= the probe, leading to the wrong choice of +// interval for the Contains() test. Therefore [10, 10) needs to come after +// [10, 20). The simplest way to make this work in the general case is to order +// by ascending min() but descending max(). In this ordering, the empty interval +// is larger than any non-empty interval with the same min(). The comparator +// used by this library is careful to induce this ordering. +// +// Another detail involves the choice of which std::set method to use to try to +// find the candidate interval. The most appropriate entry point is +// set::upper_bound(), which finds the smallest interval which is > the probe +// interval. The semantics of upper_bound() are slightly different from what we +// want (namely, to find the largest interval which is <= the probe interval) +// but they are close enough; the interval found by upper_bound() will always be +// one step past the interval we are looking for (if it exists) or at begin() +// (if it does not). Getting to the proper interval is a simple matter of +// decrementing the iterator. +template <typename T> +typename IntervalSet<T>::const_iterator IntervalSet<T>::Find( + const T& value) const { + Interval<T> tmp(value, value); + const_iterator it = intervals_.upper_bound(tmp); + if (it == intervals_.begin()) + return intervals_.end(); + --it; + if (it->Contains(value)) + return it; + else + return intervals_.end(); +} + +// This method finds the interval that Contains() the interval "probe", if such +// an interval exists in the IntervalSet. The way this is done is to locate the +// "candidate interval", the only interval that could *possibly* contain +// "probe", and test it using Contains(). The candidate interval is the largest +// interval that is <= the probe interval. +// +// The search for the candidate interval only works if the comparator used +// behaves in a certain way. In particular it needs to order first by ascending +// min(), and then by descending max(). The comparator used by this library is +// defined in exactly this way. To see why descending max() is required, +// consider the following example. Assume an IntervalSet containing these +// intervals: +// +// [0, 5) [10, 20) [50, 60) +// +// Consider searching for the probe [15, 17). [10, 20) is the largest interval +// in the set which is <= the probe interval. This is the correct interval +// needed for the Contains() test, which will then return true, because [10, 20) +// contains [15, 17). +// +// Now consider searching for the probe [30, 32). Again [10, 20] is the largest +// interval <= the probe interval. This is again the correct interval needed for +// the Contains() test, which in this case returns false, because [10, 20) does +// not contain [30, 32). +// +// Finally, consider searching for the probe [10, 12). Here the ordering +// relationship between [10, 12) and [10, 20) becomes vitally important. If +// [10, 12) were to come before [10, 20), then [0, 5) would be the largest +// interval <= the probe, leading to the wrong choice of interval for the +// Contains() test. Therefore [10, 12) needs to come after [10, 20). The +// simplest way to make this work in the general case is to order by ascending +// min() but descending max(). In this ordering, given two intervals with the +// same min(), the wider one goes before the narrower one. The comparator used +// by this library is careful to induce this ordering. +// +// Another detail involves the choice of which std::set method to use to try to +// find the candidate interval. The most appropriate entry point is +// set::upper_bound(), which finds the smallest interval which is > the probe +// interval. The semantics of upper_bound() are slightly different from what we +// want (namely, to find the largest interval which is <= the probe interval) +// but they are close enough; the interval found by upper_bound() will always be +// one step past the interval we are looking for (if it exists) or at begin() +// (if it does not). Getting to the proper interval is a simple matter of +// decrementing the iterator. +template <typename T> +typename IntervalSet<T>::const_iterator IntervalSet<T>::Find( + const Interval<T>& probe) const { + const_iterator it = intervals_.upper_bound(probe); + if (it == intervals_.begin()) + return intervals_.end(); + --it; + if (it->Contains(probe)) + return it; + else + return intervals_.end(); +} + +template <typename T> +bool IntervalSet<T>::IsDisjoint(const Interval<T>& interval) const { + Interval<T> tmp(interval.min(), interval.min()); + // Find the first interval with min() > interval.min() + const_iterator it = intervals_.upper_bound(tmp); + if (it != intervals_.end() && interval.max() > it->min()) + return false; + if (it == intervals_.begin()) + return true; + --it; + return it->max() <= interval.min(); +} + +template <typename T> +void IntervalSet<T>::Union(const IntervalSet& other) { + intervals_.insert(other.begin(), other.end()); + Compact(intervals_.begin(), intervals_.end()); +} + +template <typename T> +typename IntervalSet<T>::const_iterator +IntervalSet<T>::FindIntersectionCandidate(const IntervalSet& other) const { + return FindIntersectionCandidate(*other.intervals_.begin()); +} + +template <typename T> +typename IntervalSet<T>::const_iterator +IntervalSet<T>::FindIntersectionCandidate(const Interval<T>& interval) const { + // Use upper_bound to efficiently find the first interval in intervals_ + // where min() is greater than interval.min(). If the result + // isn't the beginning of intervals_ then move backwards one interval since + // the interval before it is the first candidate where max() may be + // greater than interval.min(). + // In other words, no interval before that can possibly intersect with any + // of other.intervals_. + const_iterator mine = intervals_.upper_bound(interval); + if (mine != intervals_.begin()) { + --mine; + } + return mine; +} + +template <typename T> +template <typename X, typename Func> +bool IntervalSet<T>::FindNextIntersectingPairImpl(X* x, + const IntervalSet& y, + const_iterator* mine, + const_iterator* theirs, + Func on_hole) { + CHECK(x != nullptr); + if ((*mine == x->intervals_.end()) || (*theirs == y.intervals_.end())) { + return false; + } + while (!(**mine).Intersects(**theirs)) { + const_iterator erase_first = *mine; + // Skip over intervals in 'mine' that don't reach 'theirs'. + while (*mine != x->intervals_.end() && (**mine).max() <= (**theirs).min()) { + ++(*mine); + } + on_hole(x, erase_first, *mine); + // We're done if the end of intervals_ is reached. + if (*mine == x->intervals_.end()) { + return false; + } + // Skip over intervals 'theirs' that don't reach 'mine'. + while (*theirs != y.intervals_.end() && + (**theirs).max() <= (**mine).min()) { + ++(*theirs); + } + // If the end of other.intervals_ is reached, we're done. + if (*theirs == y.intervals_.end()) { + on_hole(x, *mine, x->intervals_.end()); + return false; + } + } + return true; +} + +template <typename T> +void IntervalSet<T>::Intersection(const IntervalSet& other) { + if (!SpanningInterval().Intersects(other.SpanningInterval())) { + intervals_.clear(); + return; + } + + const_iterator mine = FindIntersectionCandidate(other); + // Remove any intervals that cannot possibly intersect with other.intervals_. + intervals_.erase(intervals_.begin(), mine); + const_iterator theirs = other.FindIntersectionCandidate(*this); + + while (FindNextIntersectingPairAndEraseHoles(other, &mine, &theirs)) { + // OK, *mine and *theirs intersect. Now, we find the largest + // span of intervals in other (starting at theirs) - say [a..b] + // - that intersect *mine, and we replace *mine with (*mine + // intersect x) for all x in [a..b] Note that subsequent + // intervals in this can't intersect any intervals in [a..b) -- + // they may only intersect b or subsequent intervals in other. + Interval<T> i(*mine); + intervals_.erase(mine); + mine = intervals_.end(); + Interval<T> intersection; + while (theirs != other.intervals_.end() && + i.Intersects(*theirs, &intersection)) { + std::pair<typename Set::iterator, bool> ins = + intervals_.insert(intersection); + DCHECK(ins.second); + mine = ins.first; + ++theirs; + } + DCHECK(mine != intervals_.end()); + --theirs; + ++mine; + } + DCHECK(Valid()); +} + +template <typename T> +bool IntervalSet<T>::Intersects(const IntervalSet& other) const { + if (!SpanningInterval().Intersects(other.SpanningInterval())) { + return false; + } + + const_iterator mine = FindIntersectionCandidate(other); + if (mine == intervals_.end()) { + return false; + } + const_iterator theirs = other.FindIntersectionCandidate(*mine); + + return FindNextIntersectingPair(other, &mine, &theirs); +} + +template <typename T> +void IntervalSet<T>::Difference(const Interval<T>& interval) { + if (!SpanningInterval().Intersects(interval)) { + return; + } + Difference(IntervalSet<T>(interval)); +} + +template <typename T> +void IntervalSet<T>::Difference(const T& min, const T& max) { + Difference(Interval<T>(min, max)); +} + +template <typename T> +void IntervalSet<T>::Difference(const IntervalSet& other) { + if (!SpanningInterval().Intersects(other.SpanningInterval())) { + return; + } + + const_iterator mine = FindIntersectionCandidate(other); + // If no interval in mine reaches the first interval of theirs then we're + // done. + if (mine == intervals_.end()) { + return; + } + const_iterator theirs = other.FindIntersectionCandidate(*this); + + while (FindNextIntersectingPair(other, &mine, &theirs)) { + // At this point *mine and *theirs overlap. Remove mine from + // intervals_ and replace it with the possibly two intervals that are + // the difference between mine and theirs. + Interval<T> i(*mine); + intervals_.erase(mine++); + Interval<T> lo; + Interval<T> hi; + i.Difference(*theirs, &lo, &hi); + + if (!lo.Empty()) { + // We have a low end. This can't intersect anything else. + std::pair<typename Set::iterator, bool> ins = intervals_.insert(lo); + DCHECK(ins.second); + } + + if (!hi.Empty()) { + std::pair<typename Set::iterator, bool> ins = intervals_.insert(hi); + DCHECK(ins.second); + mine = ins.first; + } + } + DCHECK(Valid()); +} + +template <typename T> +void IntervalSet<T>::Complement(const T& min, const T& max) { + IntervalSet<T> span(min, max); + span.Difference(*this); + intervals_.swap(span.intervals_); +} + +template <typename T> +std::string IntervalSet<T>::ToString() const { + std::ostringstream os; + os << *this; + return os.str(); +} + +// This method compacts the IntervalSet, merging pairs of overlapping intervals +// into a single interval. In the steady state, the IntervalSet does not contain +// any such pairs. However, the way the Union() and Add() methods work is to +// temporarily put the IntervalSet into such a state and then to call Compact() +// to "fix it up" so that it is no longer in that state. +// +// Compact() needs the interval set to allow two intervals [a,b) and [a,c) +// (having the same min() but different max()) to briefly coexist in the set at +// the same time, and be adjacent to each other, so that they can be efficiently +// located and merged into a single interval. This state would be impossible +// with a comparator which only looked at min(), as such a comparator would +// consider such pairs equal. Fortunately, the comparator used by IntervalSet +// does exactly what is needed, ordering first by ascending min(), then by +// descending max(). +template <typename T> +void IntervalSet<T>::Compact(const typename Set::iterator& begin, + const typename Set::iterator& end) { + if (begin == end) + return; + typename Set::iterator next = begin; + typename Set::iterator prev = begin; + typename Set::iterator it = begin; + ++it; + ++next; + while (it != end) { + ++next; + if (prev->max() >= it->min()) { + // Overlapping / coalesced range; merge the two intervals. + T min = prev->min(); + T max = std::max(prev->max(), it->max()); + Interval<T> i(min, max); + intervals_.erase(prev); + intervals_.erase(it); + std::pair<typename Set::iterator, bool> ins = intervals_.insert(i); + DCHECK(ins.second); + prev = ins.first; + } else { + prev = it; + } + it = next; + } +} + +template <typename T> +bool IntervalSet<T>::Valid() const { + const_iterator prev = end(); + for (const_iterator it = begin(); it != end(); ++it) { + // invalid or empty interval. + if (it->min() >= it->max()) + return false; + // Not sorted, not disjoint, or adjacent. + if (prev != end() && prev->max() >= it->min()) + return false; + prev = it; + } + return true; +} + +template <typename T> +inline std::ostream& operator<<(std::ostream& out, const IntervalSet<T>& seq) { +// TODO(rtenneti): Implement << method of IntervalSet. +#if 0 + util::gtl::LogRangeToStream(out, seq.begin(), seq.end(), + util::gtl::LogLegacy()); +#endif // 0 + return out; +} + +template <typename T> +void swap(IntervalSet<T>& x, IntervalSet<T>& y) { + x.Swap(&y); +} + +// This comparator orders intervals first by ascending min() and then by +// descending max(). Readers who are satisified with that explanation can stop +// reading here. The remainder of this comment is for the benefit of future +// maintainers of this library. +// +// The reason for this ordering is that this comparator has to serve two +// masters. First, it has to maintain the intervals in its internal set in the +// order that clients expect to see them. Clients see these intervals via the +// iterators provided by begin()/end() or as a result of invoking Get(). For +// this reason, the comparator orders intervals by ascending min(). +// +// If client iteration were the only consideration, then ordering by ascending +// min() would be good enough. This is because the intervals in the IntervalSet +// are non-empty, non-adjacent, and mutually disjoint; such intervals happen to +// always have disjoint min() values, so such a comparator would never even have +// to look at max() in order to work correctly for this class. +// +// However, in addition to ordering by ascending min(), this comparator also has +// a second responsibility: satisfying the special needs of this library's +// peculiar internal implementation. These needs require the comparator to order +// first by ascending min() and then by descending max(). The best way to +// understand why this is so is to check out the comments associated with the +// Find() and Compact() methods. +template <typename T> +inline bool IntervalSet<T>::IntervalComparator::operator()( + const Interval<T>& a, + const Interval<T>& b) const { + return (a.min() < b.min() || (a.min() == b.min() && a.max() > b.max())); +} + +} // namespace net + +#endif // NET_QUIC_INTERVAL_SET_H_ |