// Copyright (c) 2019 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.

#ifndef QUICHE_QUIC_CORE_QUIC_INTERVAL_SET_H_
#define QUICHE_QUIC_CORE_QUIC_INTERVAL_SET_H_

// QuicIntervalSet<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
// QuicIntervalSet, comparing two QuicIntervalSets, and performing
// QuicIntervalSet union, intersection, and difference.
//
// QuicIntervalSet maintains the minimum number of entries needed to represent
// the set of underlying intervals. When the QuicIntervalSet 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 value_type.
//
// QuicIntervalSet has constant-time move operations.
//
//
// Examples:
//   QuicIntervalSet<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)));

#include <stddef.h>
#include <algorithm>
#include <initializer_list>
#include <set>
#include <utility>
#include <vector>

#include <iterator>
#include <string>

#include "absl/types/variant.h"
#include "quic/core/quic_interval.h"
#include "quic/platform/api/quic_containers.h"
#include "quic/platform/api/quic_flags.h"
#include "quic/platform/api/quic_logging.h"

namespace quic {
namespace oldquic {

template <typename T>
class QUIC_NO_EXPORT QuicIntervalSet {
 public:
  using value_type = QuicInterval<T>;

 private:
  struct QUIC_NO_EXPORT IntervalLess {
    bool operator()(const value_type& a, const value_type& b) const;
  };
  // TODO(wub): Switch to absl::btree_set when it is available in Chromium.
  using Set = std::set<value_type, IntervalLess>;

 public:
  using const_iterator = typename Set::const_iterator;
  using const_reverse_iterator = typename Set::const_reverse_iterator;

  // Instantiates an empty QuicIntervalSet.
  QuicIntervalSet() {}

  // Instantiates an QuicIntervalSet containing exactly one initial half-open
  // interval [min, max), unless the given interval is empty, in which case the
  // QuicIntervalSet will be empty.
  explicit QuicIntervalSet(const value_type& interval) { Add(interval); }

  // Instantiates an QuicIntervalSet containing the half-open interval [min,
  // max).
  QuicIntervalSet(const T& min, const T& max) { Add(min, max); }

  QuicIntervalSet(std::initializer_list<value_type> il) { assign(il); }

  // Clears this QuicIntervalSet.
  void Clear() { intervals_.clear(); }

  // Returns the number of disjoint intervals contained in this QuicIntervalSet.
  size_t Size() const { return intervals_.size(); }

  // Returns the smallest interval that contains all intervals in this
  // QuicIntervalSet, or the empty interval if the set is empty.
  value_type SpanningInterval() const;

  // Adds "interval" to this QuicIntervalSet. Adding the empty interval has no
  // effect.
  void Add(const value_type& interval);

  // Adds the interval [min, max) to this QuicIntervalSet. Adding the empty
  // interval has no effect.
  void Add(const T& min, const T& max) { Add(value_type(min, max)); }

  // Same semantics as Add(const value_type&), but optimized for the case where
  // rbegin()->min() <= |interval|.min() <= rbegin()->max().
  void AddOptimizedForAppend(const value_type& interval) {
    if (Empty()) {
      Add(interval);
      return;
    }

    const_reverse_iterator last_interval = intervals_.rbegin();

    // If interval.min() is outside of [last_interval->min, last_interval->max],
    // we can not simply extend last_interval->max.
    if (interval.min() < last_interval->min() ||
        interval.min() > last_interval->max()) {
      Add(interval);
      return;
    }

    if (interval.max() <= last_interval->max()) {
      // interval is fully contained by last_interval.
      return;
    }

    // Extend last_interval.max to interval.max, in place.
    //
    // Set does not allow in-place updates due to the potential of violating its
    // ordering requirements. But we know setting the max of the last interval
    // is safe w.r.t set ordering and other invariants of QuicIntervalSet, so we
    // force an in-place update for performance.
    const_cast<value_type*>(&(*last_interval))->SetMax(interval.max());
  }

  // Same semantics as Add(const T&, const T&), but optimized for the case where
  // rbegin()->max() == |min|.
  void AddOptimizedForAppend(const T& min, const T& max) {
    AddOptimizedForAppend(value_type(min, max));
  }

  // TODO(wub): Similar to AddOptimizedForAppend, we can also have a
  // AddOptimizedForPrepend if there is a use case.

  // Remove the first interval.
  // REQUIRES: !Empty()
  void PopFront() {
    QUICHE_DCHECK(!Empty());
    intervals_.erase(intervals_.begin());
  }

  // Trim all values that is smaller than |value|. Which means
  // a) If all values in an interval is smaller than |value|, the entire
  //    interval is removed.
  // b) If some but not all values in an interval is smaller than |value|, the
  //    min of that interval is raised to |value|.
  // Returns true if some intervals are trimmed.
  bool TrimLessThan(const T& value) {
    // Number of intervals that are fully or partially trimmed.
    size_t num_intervals_trimmed = 0;

    while (!intervals_.empty()) {
      const_iterator first_interval = intervals_.begin();
      if (first_interval->min() >= value) {
        break;
      }

      ++num_intervals_trimmed;

      if (first_interval->max() <= value) {
        // a) Trim the entire interval.
        intervals_.erase(first_interval);
        continue;
      }

      // b) Trim a prefix of the interval.
      //
      // Set does not allow in-place updates due to the potential of violating
      // its ordering requirements. But increasing the min of the first interval
      // will not break the ordering, hence the const_cast.
      const_cast<value_type*>(&(*first_interval))->SetMin(value);
      break;
    }

    return num_intervals_trimmed != 0;
  }

  // Returns true if this QuicIntervalSet is empty.
  bool Empty() const { return intervals_.empty(); }

  // Returns true if any interval in this QuicIntervalSet contains the indicated
  // value.
  bool Contains(const T& value) const;

  // Returns true if there is some interval in this QuicIntervalSet 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 value_type::Contains(). This method returns false on
  // the empty interval, due to a (perhaps unintuitive) convention inherited
  // from value_type.
  // Example:
  //   Assume an QuicIntervalSet 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 value_type& interval) const;

  // Returns true if for each interval in "other", there is some (possibly
  // different) interval in this QuicIntervalSet which wholly contains it. See
  // Contains(const value_type& 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())). The method could be rewritten to run in O(other.Size()
  // + this->Size()), and this alternative could be implemented as a free
  // function using the public API.
  bool Contains(const QuicIntervalSet<T>& other) const;

  // Returns true if there is some interval in this QuicIntervalSet that wholly
  // contains the interval [min, max). See Contains(const value_type&).
  bool Contains(const T& min, const T& max) const {
    return Contains(value_type(min, max));
  }

  // Returns true if for some interval in "other", there is some interval in
  // this QuicIntervalSet that intersects with it. See value_type::Intersects()
  // for the definition of interval intersection.
  bool Intersects(const QuicIntervalSet& other) const;

  // Returns an iterator to the value_type in the QuicIntervalSet that contains
  // the given value. In other words, returns an iterator to the unique interval
  // [min, max) in the QuicIntervalSet 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 value_type in the QuicIntervalSet that wholly
  // contains the given interval. In other words, returns an iterator to the
  // unique interval outer in the QuicIntervalSet 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 value_type& interval) const;

  // Returns an iterator to the value_type in the QuicIntervalSet that wholly
  // contains [min, max). In other words, returns an iterator to the unique
  // interval outer in the QuicIntervalSet 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(value_type(min, max));
  }

  // Returns an iterator pointing to the first value_type which contains or
  // goes after the given value.
  //
  // Example:
  //   [10, 20)  [30, 40)
  //   ^                    LowerBound(10)
  //   ^                    LowerBound(15)
  //             ^          LowerBound(20)
  //             ^          LowerBound(25)
  const_iterator LowerBound(const T& value) const;

  // Returns an iterator pointing to the first value_type which goes after
  // the given value.
  //
  // Example:
  //   [10, 20)  [30, 40)
  //             ^          UpperBound(10)
  //             ^          UpperBound(15)
  //             ^          UpperBound(20)
  //             ^          UpperBound(25)
  const_iterator UpperBound(const T& value) const;

  // Returns true if every value within the passed interval is not Contained
  // within the QuicIntervalSet.
  // Note that empty intervals are always considered disjoint from the
  // QuicIntervalSet (even though the QuicIntervalSet doesn't `Contain` them).
  bool IsDisjoint(const value_type& interval) const;

  // Merges all the values contained in "other" into this QuicIntervalSet.
  void Union(const QuicIntervalSet& other);

  // Modifies this QuicIntervalSet so that it contains only those values that
  // are currently present both in *this and in the QuicIntervalSet "other".
  void Intersection(const QuicIntervalSet& other);

  // Mutates this QuicIntervalSet so that it contains only those values that are
  // currently in *this but not in "interval".
  void Difference(const value_type& interval);

  // Mutates this QuicIntervalSet 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 QuicIntervalSet so that it contains only those values that are
  // currently in *this but not in the QuicIntervalSet "other".
  void Difference(const QuicIntervalSet& other);

  // Mutates this QuicIntervalSet 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);

  // QuicIntervalSet's begin() iterator. The invariants of QuicIntervalSet
  // 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 QuicIntervalSet invalidate these
  // iterators.
  const_iterator begin() const { return intervals_.begin(); }

  // QuicIntervalSet's end() iterator.
  const_iterator end() const { return intervals_.end(); }

  // QuicIntervalSet'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(); }

  template <typename Iter>
  void assign(Iter first, Iter last) {
    Clear();
    for (; first != last; ++first)
      Add(*first);
  }

  void assign(std::initializer_list<value_type> il) {
    assign(il.begin(), il.end());
  }

  // 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;

  QuicIntervalSet& operator=(std::initializer_list<value_type> il) {
    assign(il.begin(), il.end());
    return *this;
  }

  friend bool operator==(const QuicIntervalSet& a, const QuicIntervalSet& b) {
    return a.Size() == b.Size() &&
           std::equal(a.begin(), a.end(), b.begin(), NonemptyIntervalEq());
  }

  friend bool operator!=(const QuicIntervalSet& a, const QuicIntervalSet& b) {
    return !(a == b);
  }

 private:
  // Simple member-wise equality, since all intervals are non-empty.
  struct QUIC_NO_EXPORT NonemptyIntervalEq {
    bool operator()(const value_type& a, const value_type& b) const {
      return a.min() == b.min() && a.max() == b.max();
    }
  };

  // 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 QUICHE_DCHECK).
  bool Valid() const;

  // Finds the first interval that potentially intersects 'other'.
  const_iterator FindIntersectionCandidate(const QuicIntervalSet& other) const;

  // Finds the first interval that potentially intersects 'interval'.
  const_iterator FindIntersectionCandidate(const value_type& 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 QuicIntervalSet& y,
                                           const_iterator* mine,
                                           const_iterator* theirs,
                                           Func on_hole);

  // The variant of the above method that doesn't mutate this QuicIntervalSet.
  bool FindNextIntersectingPair(const QuicIntervalSet& other,
                                const_iterator* mine,
                                const_iterator* theirs) const {
    return FindNextIntersectingPairImpl(
        this, other, mine, theirs,
        [](const QuicIntervalSet*, const_iterator, const_iterator) {});
  }

  // The variant of the above method that mutates this QuicIntervalSet by
  // erasing holes.
  bool FindNextIntersectingPairAndEraseHoles(const QuicIntervalSet& other,
                                             const_iterator* mine,
                                             const_iterator* theirs) {
    return FindNextIntersectingPairImpl(
        this, other, mine, theirs,
        [](QuicIntervalSet* 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>
auto operator<<(std::ostream& out, const QuicIntervalSet<T>& seq)
    -> decltype(out << *seq.begin()) {
  out << "{";
  for (const auto& interval : seq) {
    out << " " << interval;
  }
  out << " }";

  return out;
}

//==============================================================================
// Implementation details: Clients can stop reading here.

template <typename T>
typename QuicIntervalSet<T>::value_type QuicIntervalSet<T>::SpanningInterval()
    const {
  value_type result;
  if (!intervals_.empty()) {
    result.SetMin(intervals_.begin()->min());
    result.SetMax(intervals_.rbegin()->max());
  }
  return result;
}

template <typename T>
void QuicIntervalSet<T>::Add(const value_type& 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 QuicIntervalSet 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 value_type target_end(interval.max(), interval.max());
  const typename Set::iterator end = intervals_.upper_bound(target_end);
  Compact(begin, end);
}

template <typename T>
bool QuicIntervalSet<T>::Contains(const T& value) const {
  value_type 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 QuicIntervalSet<T>::Contains(const value_type& 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 QuicIntervalSet<T>::Contains(const QuicIntervalSet<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 QuicIntervalSet. 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 QuicIntervalSet 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 QuicIntervalSet 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 QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::Find(
    const T& value) const {
  value_type 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 QuicIntervalSet. 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 QuicIntervalSet 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 QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::Find(
    const value_type& 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>
typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::LowerBound(
    const T& value) const {
  const_iterator it = intervals_.lower_bound(value_type(value, value));
  if (it == intervals_.begin()) {
    return it;
  }

  // The previous intervals_.lower_bound() checking is essentially based on
  // interval.min(), so we need to check whether the `value` is contained in
  // the previous interval.
  --it;
  if (it->Contains(value)) {
    return it;
  } else {
    return ++it;
  }
}

template <typename T>
typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::UpperBound(
    const T& value) const {
  return intervals_.upper_bound(value_type(value, value));
}

template <typename T>
bool QuicIntervalSet<T>::IsDisjoint(const value_type& interval) const {
  if (interval.Empty())
    return true;
  value_type 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 QuicIntervalSet<T>::Union(const QuicIntervalSet& other) {
  intervals_.insert(other.begin(), other.end());
  Compact(intervals_.begin(), intervals_.end());
}

template <typename T>
typename QuicIntervalSet<T>::const_iterator
QuicIntervalSet<T>::FindIntersectionCandidate(
    const QuicIntervalSet& other) const {
  return FindIntersectionCandidate(*other.intervals_.begin());
}

template <typename T>
typename QuicIntervalSet<T>::const_iterator
QuicIntervalSet<T>::FindIntersectionCandidate(
    const value_type& 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 QuicIntervalSet<T>::FindNextIntersectingPairImpl(X* x,
                                                      const QuicIntervalSet& y,
                                                      const_iterator* mine,
                                                      const_iterator* theirs,
                                                      Func on_hole) {
  QUICHE_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 QuicIntervalSet<T>::Intersection(const QuicIntervalSet& 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.
    value_type i(*mine);
    intervals_.erase(mine);
    mine = intervals_.end();
    value_type intersection;
    while (theirs != other.intervals_.end() &&
           i.Intersects(*theirs, &intersection)) {
      std::pair<typename Set::iterator, bool> ins =
          intervals_.insert(intersection);
      QUICHE_DCHECK(ins.second);
      mine = ins.first;
      ++theirs;
    }
    QUICHE_DCHECK(mine != intervals_.end());
    --theirs;
    ++mine;
  }
  QUICHE_DCHECK(Valid());
}

template <typename T>
bool QuicIntervalSet<T>::Intersects(const QuicIntervalSet& 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 QuicIntervalSet<T>::Difference(const value_type& interval) {
  if (!SpanningInterval().Intersects(interval)) {
    return;
  }
  Difference(QuicIntervalSet<T>(interval));
}

template <typename T>
void QuicIntervalSet<T>::Difference(const T& min, const T& max) {
  Difference(value_type(min, max));
}

template <typename T>
void QuicIntervalSet<T>::Difference(const QuicIntervalSet& 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.
    value_type i(*mine);
    intervals_.erase(mine++);
    value_type lo;
    value_type 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);
      QUICHE_DCHECK(ins.second);
    }

    if (!hi.Empty()) {
      std::pair<typename Set::iterator, bool> ins = intervals_.insert(hi);
      QUICHE_DCHECK(ins.second);
      mine = ins.first;
    }
  }
  QUICHE_DCHECK(Valid());
}

template <typename T>
void QuicIntervalSet<T>::Complement(const T& min, const T& max) {
  QuicIntervalSet<T> span(min, max);
  span.Difference(*this);
  intervals_.swap(span.intervals_);
}

template <typename T>
std::string QuicIntervalSet<T>::ToString() const {
  std::ostringstream os;
  os << *this;
  return os.str();
}

// This method compacts the QuicIntervalSet, merging pairs of overlapping
// intervals into a single interval. In the steady state, the QuicIntervalSet
// does not contain any such pairs. However, the way the Union() and Add()
// methods work is to temporarily put the QuicIntervalSet 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
// QuicIntervalSet does exactly what is needed, ordering first by ascending
// min(), then by descending max().
template <typename T>
void QuicIntervalSet<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());
      value_type i(min, max);
      intervals_.erase(prev);
      intervals_.erase(it);
      std::pair<typename Set::iterator, bool> ins = intervals_.insert(i);
      QUICHE_DCHECK(ins.second);
      prev = ins.first;
    } else {
      prev = it;
    }
    it = next;
  }
}

template <typename T>
bool QuicIntervalSet<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;
}

// 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
// QuicIntervalSet 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>
bool QuicIntervalSet<T>::IntervalLess::operator()(const value_type& a,
                                                  const value_type& b) const {
  return a.min() < b.min() || (a.min() == b.min() && a.max() > b.max());
}

}  // namespace oldquic

namespace newquic {
template <typename T>
class QUIC_NO_EXPORT QuicIntervalSet {
 public:
  typedef QuicInterval<T> value_type;

 private:
  struct QUIC_NO_EXPORT IntervalLess {
    using is_transparent = void;
    bool operator()(const value_type& a, const value_type& b) const;
    // These transparent overloads are used when we do all of our searches (via
    // Set::lower_bound() and Set::upper_bound()), which avoids the need to
    // construct an interval when we are looking for a point and also avoids
    // needing to worry about comparing overlapping intervals in the overload
    // that takes two value_types (the one just above this comment).
    bool operator()(const value_type& a, const T& point) const;
    bool operator()(const value_type& a, T&& point) const;
    bool operator()(const T& point, const value_type& a) const;
    bool operator()(T&& point, const value_type& a) const;
  };

  typedef QuicOrderedSet<value_type,
                         IntervalLess,
                         QuicInlinedVector<value_type, 10>>
      Set;

 public:
  typedef typename Set::const_iterator const_iterator;
  typedef typename Set::const_reverse_iterator const_reverse_iterator;

  // Instantiates an empty QuicIntervalSet.
  QuicIntervalSet() = default;

  // Instantiates a QuicIntervalSet containing exactly one initial half-open
  // interval [min, max), unless the given interval is empty, in which case the
  // QuicIntervalSet will be empty.
  explicit QuicIntervalSet(const value_type& interval) { Add(interval); }

  // Instantiates a QuicIntervalSet containing the half-open interval [min,
  // max).
  QuicIntervalSet(const T& min, const T& max) { Add(min, max); }

  QuicIntervalSet(std::initializer_list<value_type> il) { assign(il); }

  // Clears this QuicIntervalSet.
  void Clear() { intervals_.clear(); }

  // Returns the number of disjoint intervals contained in this QuicIntervalSet.
  size_t Size() const { return intervals_.size(); }

  // Returns the smallest interval that contains all intervals in this
  // QuicIntervalSet, or the empty interval if the set is empty.
  value_type SpanningInterval() const;

  // Adds "interval" to this QuicIntervalSet. Adding the empty interval has no
  // effect.
  void Add(const value_type& interval);

  // Adds the interval [min, max) to this QuicIntervalSet. Adding the empty
  // interval has no effect.
  void Add(const T& min, const T& max) { Add(value_type(min, max)); }

  // Same semantics as Add(const value_type&), but optimized for the case where
  // rbegin()->min() <= |interval|.min() <= rbegin()->max().
  void AddOptimizedForAppend(const value_type& interval) {
    if (Empty()) {
      Add(interval);
      return;
    }

    const_reverse_iterator last_interval = intervals_.rbegin();

    // If interval.min() is outside of [last_interval->min, last_interval->max],
    // we can not simply extend last_interval->max.
    if (interval.min() < last_interval->min() ||
        interval.min() > last_interval->max()) {
      Add(interval);
      return;
    }

    if (interval.max() <= last_interval->max()) {
      // interval is fully contained by last_interval.
      return;
    }

    // Extend last_interval.max to interval.max, in place.
    //
    // Set does not allow in-place updates due to the potential of violating its
    // ordering requirements. But we know setting the max of the last interval
    // is safe w.r.t set ordering and other invariants of QuicIntervalSet, so we
    // force an in-place update for performance.
    const_cast<value_type*>(&(*last_interval))->SetMax(interval.max());
  }

  // Same semantics as Add(const T&, const T&), but optimized for the case where
  // rbegin()->max() == |min|.
  void AddOptimizedForAppend(const T& min, const T& max) {
    AddOptimizedForAppend(value_type(min, max));
  }

  // TODO(wub): Similar to AddOptimizedForAppend, we can also have a
  // AddOptimizedForPrepend if there is a use case.

  // Remove the first interval.
  // REQUIRES: !Empty()
  void PopFront() {
    QUICHE_DCHECK(!Empty());
    intervals_.erase(intervals_.begin());
  }

  // Trim all values that are smaller than |value|. Which means
  // a) If all values in an interval is smaller than |value|, the entire
  //    interval is removed.
  // b) If some but not all values in an interval is smaller than |value|, the
  //    min of that interval is raised to |value|.
  // Returns true if some intervals are trimmed.
  bool TrimLessThan(const T& value) {
    // Number of intervals that are fully or partially trimmed.
    size_t num_intervals_trimmed = 0;

    while (!intervals_.empty()) {
      const_iterator first_interval = intervals_.begin();
      if (first_interval->min() >= value) {
        break;
      }

      ++num_intervals_trimmed;

      if (first_interval->max() <= value) {
        // a) Trim the entire interval.
        intervals_.erase(first_interval);
        continue;
      }

      // b) Trim a prefix of the interval.
      //
      // Set does not allow in-place updates due to the potential of violating
      // its ordering requirements. But increasing the min of the first interval
      // will not break the ordering, hence the const_cast.
      const_cast<value_type*>(&(*first_interval))->SetMin(value);
      break;
    }

    return num_intervals_trimmed != 0;
  }

  // Returns true if this QuicIntervalSet is empty.
  bool Empty() const { return intervals_.empty(); }

  // Returns true if any interval in this QuicIntervalSet contains the indicated
  // value.
  bool Contains(const T& value) const;

  // Returns true if there is some interval in this QuicIntervalSet 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 value_type::Contains(). This method returns false on
  // the empty interval, due to a (perhaps unintuitive) convention inherited
  // from value_type.
  // Example:
  //   Assume an QuicIntervalSet 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 value_type& interval) const;

  // Returns true if for each interval in "other", there is some (possibly
  // different) interval in this QuicIntervalSet which wholly contains it. See
  // Contains(const value_type& 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())). The method could be rewritten to run in O(other.Size()
  // + this->Size()), and this alternative could be implemented as a free
  // function using the public API.
  bool Contains(const QuicIntervalSet<T>& other) const;

  // Returns true if there is some interval in this QuicIntervalSet that wholly
  // contains the interval [min, max). See Contains(const value_type&).
  bool Contains(const T& min, const T& max) const {
    return Contains(value_type(min, max));
  }

  // Returns true if for some interval in "other", there is some interval in
  // this QuicIntervalSet that intersects with it. See value_type::Intersects()
  // for the definition of interval intersection.  Runs in time O(n+m) where n
  // is the number of intervals in this and m is the number of intervals in
  // other.
  bool Intersects(const QuicIntervalSet& other) const;

  // Returns an iterator to the value_type in the QuicIntervalSet that contains
  // the given value. In other words, returns an iterator to the unique interval
  // [min, max) in the QuicIntervalSet 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 value_type in the QuicIntervalSet that wholly
  // contains the given interval. In other words, returns an iterator to the
  // unique interval outer in the QuicIntervalSet 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 value_type& interval) const;

  // Returns an iterator to the value_type in the QuicIntervalSet that wholly
  // contains [min, max). In other words, returns an iterator to the unique
  // interval outer in the QuicIntervalSet 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(value_type(min, max));
  }

  // Returns an iterator pointing to the first value_type which contains or
  // goes after the given value.
  //
  // Example:
  //   [10, 20)  [30, 40)
  //   ^                    LowerBound(10)
  //   ^                    LowerBound(15)
  //             ^          LowerBound(20)
  //             ^          LowerBound(25)
  const_iterator LowerBound(const T& value) const;

  // Returns an iterator pointing to the first value_type which goes after
  // the given value.
  //
  // Example:
  //   [10, 20)  [30, 40)
  //             ^          UpperBound(10)
  //             ^          UpperBound(15)
  //             ^          UpperBound(20)
  //             ^          UpperBound(25)
  const_iterator UpperBound(const T& value) const;

  // Returns true if every value within the passed interval is not Contained
  // within the QuicIntervalSet.
  // Note that empty intervals are always considered disjoint from the
  // QuicIntervalSet (even though the QuicIntervalSet doesn't `Contain` them).
  bool IsDisjoint(const value_type& interval) const;

  // Merges all the values contained in "other" into this QuicIntervalSet.
  //
  // Performance: Let n == Size() and m = other.Size().  Union() runs in O(m)
  // Set operations, so that if Set is a tree, it runs in time O(m log(n+m)) and
  // if Set is a flat_set it runs in time O(m(n+m)).  In principle, for the
  // flat_set, we should be able to make this run in time O(n+m).
  //
  // TODO(bradleybear): Make Union() run in time O(n+m) for flat_set.  This may
  // require an additional template parameter to indicate that the Set is a
  // linear-time data structure instead of a log-time data structure.
  void Union(const QuicIntervalSet& other);

  // Modifies this QuicIntervalSet so that it contains only those values that
  // are currently present both in *this and in the QuicIntervalSet "other".
  void Intersection(const QuicIntervalSet& other);

  // Mutates this QuicIntervalSet so that it contains only those values that are
  // currently in *this but not in "interval".
  void Difference(const value_type& interval);

  // Mutates this QuicIntervalSet 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 QuicIntervalSet so that it contains only those values that are
  // currently in *this but not in the QuicIntervalSet "other".  Runs in time
  // O(n+m) where n is this->Size(), m is other.Size(), regardless of whether
  // the Set is a flat_set or a std::set.
  void Difference(const QuicIntervalSet& other);

  // Mutates this QuicIntervalSet 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);

  // QuicIntervalSet's begin() iterator. The invariants of QuicIntervalSet
  // 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 QuicIntervalSet invalidate these
  // iterators.
  const_iterator begin() const { return intervals_.begin(); }

  // QuicIntervalSet's end() iterator.
  const_iterator end() const { return intervals_.end(); }

  // QuicIntervalSet'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(); }

  template <typename Iter>
  void assign(Iter first, Iter last) {
    Clear();
    for (; first != last; ++first)
      Add(*first);
  }

  void assign(std::initializer_list<value_type> il) {
    assign(il.begin(), il.end());
  }

  // 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;

  QuicIntervalSet& operator=(std::initializer_list<value_type> il) {
    assign(il.begin(), il.end());
    return *this;
  }

  friend bool operator==(const QuicIntervalSet& a, const QuicIntervalSet& b) {
    return a.Size() == b.Size() &&
           std::equal(a.begin(), a.end(), b.begin(), NonemptyIntervalEq());
  }

  friend bool operator!=(const QuicIntervalSet& a, const QuicIntervalSet& b) {
    return !(a == b);
  }

 private:
  // Simple member-wise equality, since all intervals are non-empty.
  struct QUIC_NO_EXPORT NonemptyIntervalEq {
    bool operator()(const value_type& a, const value_type& b) const {
      return a.min() == b.min() && a.max() == b.max();
    }
  };

  // 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 QUICHE_DCHECK).
  bool Valid() const;

  // Finds the first interval that potentially intersects 'other'.
  const_iterator FindIntersectionCandidate(const QuicIntervalSet& other) const;

  // Finds the first interval that potentially intersects 'interval'.  More
  // precisely, return an interator it pointing at the last interval J such that
  // interval <= J.  If all the intervals are > J then return begin().
  const_iterator FindIntersectionCandidate(const value_type& 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". "on_hole" must return an iterator to the
  // first element in 'x' after the hole, or x->intervals_.end() if no elements
  // exist after the hole.
  template <typename X, typename Func>
  static bool FindNextIntersectingPairImpl(X* x,
                                           const QuicIntervalSet& y,
                                           const_iterator* mine,
                                           const_iterator* theirs,
                                           Func on_hole);

  // The variant of the above method that doesn't mutate this QuicIntervalSet.
  bool FindNextIntersectingPair(const QuicIntervalSet& other,
                                const_iterator* mine,
                                const_iterator* theirs) const {
    return FindNextIntersectingPairImpl(
        this, other, mine, theirs,
        [](const QuicIntervalSet*, const_iterator, const_iterator end) {
          return end;
        });
  }

  // The variant of the above method that mutates this QuicIntervalSet by
  // erasing holes.
  bool FindNextIntersectingPairAndEraseHoles(const QuicIntervalSet& other,
                                             const_iterator* mine,
                                             const_iterator* theirs) {
    return FindNextIntersectingPairImpl(
        this, other, mine, theirs,
        [](QuicIntervalSet* x, const_iterator from, const_iterator to) {
          return 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>
auto operator<<(std::ostream& out, const QuicIntervalSet<T>& seq)
    -> decltype(out << *seq.begin()) {
  out << "{";
  for (const auto& interval : seq) {
    out << " " << interval;
  }
  out << " }";

  return out;
}

//==============================================================================
// Implementation details: Clients can stop reading here.

template <typename T>
typename QuicIntervalSet<T>::value_type QuicIntervalSet<T>::SpanningInterval()
    const {
  value_type result;
  if (!intervals_.empty()) {
    result.SetMin(intervals_.begin()->min());
    result.SetMax(intervals_.rbegin()->max());
  }
  return result;
}

template <typename T>
void QuicIntervalSet<T>::Add(const value_type& interval) {
  if (interval.Empty())
    return;
  const_iterator it = intervals_.lower_bound(interval.min());
  value_type the_union = interval;
  if (it != intervals_.begin()) {
    --it;
    if (it->Separated(the_union)) {
      ++it;
    }
  }
  // Don't erase the elements one at a time, since that will produce quadratic
  // work on a flat_set, and apparently an extra log-factor of work for a
  // tree-based set.  Instead identify the first and last intervals that need to
  // be erased, and call erase only once.
  const_iterator start = it;
  while (it != intervals_.end() && !it->Separated(the_union)) {
    the_union.SpanningUnion(*it);
    ++it;
  }
  intervals_.erase(start, it);
  intervals_.insert(the_union);
}

template <typename T>
bool QuicIntervalSet<T>::Contains(const T& value) const {
  // Find the first interval with min() > value, then move back one step
  const_iterator it = intervals_.upper_bound(value);
  if (it == intervals_.begin())
    return false;
  --it;
  return it->Contains(value);
}

template <typename T>
bool QuicIntervalSet<T>::Contains(const value_type& interval) const {
  // Find the first interval with min() > value, then move back one step.
  const_iterator it = intervals_.upper_bound(interval.min());
  if (it == intervals_.begin())
    return false;
  --it;
  return it->Contains(interval);
}

template <typename T>
bool QuicIntervalSet<T>::Contains(const QuicIntervalSet<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 QuicIntervalSet. 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.
//
// Another detail involves the choice of which Set method to use to try to find
// the candidate interval. The most appropriate entry point is
// Set::upper_bound(), which finds the least interval with a min > the
// value. The semantics of upper_bound() are slightly different from what we
// want (namely, to find the greatest 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 QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::Find(
    const T& value) const {
  const_iterator it = intervals_.upper_bound(value);
  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 QuicIntervalSet. The way this is done is to locate
// the "candidate interval", the only interval that could *possibly* contain
// "probe", and test it using Contains().  We use the same algorithm as for
// Find(value), except that instead of checking that the value is contained, we
// check that the probe is contained.
template <typename T>
typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::Find(
    const value_type& probe) const {
  const_iterator it = intervals_.upper_bound(probe.min());
  if (it == intervals_.begin())
    return intervals_.end();
  --it;
  if (it->Contains(probe))
    return it;
  else
    return intervals_.end();
}

template <typename T>
typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::LowerBound(
    const T& value) const {
  const_iterator it = intervals_.lower_bound(value);
  if (it == intervals_.begin()) {
    return it;
  }

  // The previous intervals_.lower_bound() checking is essentially based on
  // interval.min(), so we need to check whether the `value` is contained in
  // the previous interval.
  --it;
  if (it->Contains(value)) {
    return it;
  } else {
    return ++it;
  }
}

template <typename T>
typename QuicIntervalSet<T>::const_iterator QuicIntervalSet<T>::UpperBound(
    const T& value) const {
  return intervals_.upper_bound(value);
}

template <typename T>
bool QuicIntervalSet<T>::IsDisjoint(const value_type& interval) const {
  if (interval.Empty())
    return true;
  // Find the first interval with min() > interval.min()
  const_iterator it = intervals_.upper_bound(interval.min());
  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 QuicIntervalSet<T>::Union(const QuicIntervalSet& other) {
  for (const value_type& interval : other.intervals_) {
    Add(interval);
  }
}

template <typename T>
typename QuicIntervalSet<T>::const_iterator
QuicIntervalSet<T>::FindIntersectionCandidate(
    const QuicIntervalSet& other) const {
  return FindIntersectionCandidate(*other.intervals_.begin());
}

template <typename T>
typename QuicIntervalSet<T>::const_iterator
QuicIntervalSet<T>::FindIntersectionCandidate(
    const value_type& 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.min());
  if (mine != intervals_.begin()) {
    --mine;
  }
  return mine;
}

template <typename T>
template <typename X, typename Func>
bool QuicIntervalSet<T>::FindNextIntersectingPairImpl(X* x,
                                                      const QuicIntervalSet& y,
                                                      const_iterator* mine,
                                                      const_iterator* theirs,
                                                      Func on_hole) {
  QUICHE_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);
    }
    *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 QuicIntervalSet<T>::Intersection(const QuicIntervalSet& other) {
  if (!SpanningInterval().Intersects(other.SpanningInterval())) {
    intervals_.clear();
    return;
  }

  const_iterator mine = FindIntersectionCandidate(other);
  // Remove any intervals that cannot possibly intersect with other.intervals_.
  mine = 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.
    value_type i(*mine);
    intervals_.erase(mine);
    mine = intervals_.end();
    value_type intersection;
    while (theirs != other.intervals_.end() &&
           i.Intersects(*theirs, &intersection)) {
      std::pair<const_iterator, bool> ins = intervals_.insert(intersection);
      QUICHE_DCHECK(ins.second);
      mine = ins.first;
      ++theirs;
    }
    QUICHE_DCHECK(mine != intervals_.end());
    --theirs;
    ++mine;
  }
  QUICHE_DCHECK(Valid());
}

template <typename T>
bool QuicIntervalSet<T>::Intersects(const QuicIntervalSet& other) const {
  // Don't bother to handle nonoverlapping spanning intervals as a special case.
  // This code runs in time O(n+m), as guaranteed, even for that case .
  // Handling the nonoverlapping spanning intervals as a special case doesn't
  // improve the asymptotics but does make the code more complex.
  auto mine = intervals_.begin();
  auto theirs = other.intervals_.begin();
  while (mine != intervals_.end() && theirs != other.intervals_.end()) {
    if (mine->Intersects(*theirs))
      return true;
    else if (*mine < *theirs)
      ++mine;
    else
      ++theirs;
  }
  return false;
}

template <typename T>
void QuicIntervalSet<T>::Difference(const value_type& interval) {
  if (!SpanningInterval().Intersects(interval)) {
    return;
  }
  Difference(QuicIntervalSet<T>(interval));
}

template <typename T>
void QuicIntervalSet<T>::Difference(const T& min, const T& max) {
  Difference(value_type(min, max));
}

template <typename T>
void QuicIntervalSet<T>::Difference(const QuicIntervalSet& other) {
  // In order to avoid quadratic-time when using a flat set, we don't try to
  // update intervals_ in place.  Instead we build up a new result_, always
  // inserting at the end which is O(1) time per insertion.  Since the number of
  // elements in the result is O(Size() + other.Size()), the cost for all the
  // insertions is also O(Size() + other.Size()).
  //
  // We look at all the elements of intervals_, so that's O(Size()).
  //
  // We also look at all the elements of other.intervals_, for O(other.Size()).
  if (Empty())
    return;
  Set result;
  const_iterator mine = intervals_.begin();
  value_type myinterval = *mine;
  const_iterator theirs = other.intervals_.begin();
  while (mine != intervals_.end()) {
    // Loop invariants:
    //   myinterval is nonempty.
    //   mine points at a range that is a suffix of myinterval.
    QUICHE_DCHECK(!myinterval.Empty());
    QUICHE_DCHECK(myinterval.max() == mine->max());

    // There are 3 cases.
    //  myinterval is completely before theirs (treat theirs==end() as if it is
    //  infinity).
    //    --> consume myinterval into result.
    //  myinterval is completely after theirs
    //    --> theirs can no longer affect us, so ++theirs.
    //  myinterval touches theirs with a prefix of myinterval not touching
    //  *theirs.
    //    --> consume the prefix of myinterval into the result.
    //  myinterval touches theirs, with the first element of myinterval in
    //  *theirs.
    //    -> reduce myinterval
    if (theirs == other.intervals_.end() || myinterval.max() <= theirs->min()) {
      // Keep all of my_interval.
      result.insert(result.end(), myinterval);
      myinterval.Clear();
    } else if (theirs->max() <= myinterval.min()) {
      ++theirs;
    } else if (myinterval.min() < theirs->min()) {
      // Keep a nonempty prefix of my interval.
      result.insert(result.end(), value_type(myinterval.min(), theirs->min()));
      myinterval.SetMin(theirs->max());
    } else {
      // myinterval starts at or after *theirs, chop down myinterval.
      myinterval.SetMin(theirs->max());
    }
    // if myinterval became empty, find the next interval
    if (myinterval.Empty()) {
      ++mine;
      if (mine != intervals_.end()) {
        myinterval = *mine;
      }
    }
  }
  std::swap(result, intervals_);
  QUICHE_DCHECK(Valid());
}

template <typename T>
void QuicIntervalSet<T>::Complement(const T& min, const T& max) {
  QuicIntervalSet<T> span(min, max);
  span.Difference(*this);
  intervals_.swap(span.intervals_);
}

template <typename T>
std::string QuicIntervalSet<T>::ToString() const {
  std::ostringstream os;
  os << *this;
  return os.str();
}

template <typename T>
bool QuicIntervalSet<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;
}

// This comparator orders intervals first by ascending min().  The Set never
// contains overlapping intervals, so that suffices.
template <typename T>
bool QuicIntervalSet<T>::IntervalLess::operator()(const value_type& a,
                                                  const value_type& b) const {
  // This overload is probably used only by Set::insert().
  return a.min() < b.min();
}

// It appears that the Set::lower_bound(T) method uses only two overloads of the
// comparison operator that take a T as the second argument..  In contrast
// Set::upper_bound(T) uses the two overloads that take T as the first argument.
template <typename T>
bool QuicIntervalSet<T>::IntervalLess::operator()(const value_type& a,
                                                  const T& point) const {
  // Compare an interval to a point.
  return a.min() < point;
}

template <typename T>
bool QuicIntervalSet<T>::IntervalLess::operator()(const value_type& a,
                                                  T&& point) const {
  // Compare an interval to a point
  return a.min() < point;
}

// It appears that the Set::upper_bound(T) method uses only the next two
// overloads of the comparison operator.
template <typename T>
bool QuicIntervalSet<T>::IntervalLess::operator()(const T& point,
                                                  const value_type& a) const {
  // Compare an interval to a point.
  return point < a.min();
}

template <typename T>
bool QuicIntervalSet<T>::IntervalLess::operator()(T&& point,
                                                  const value_type& a) const {
  // Compare an interval to a point.
  return point < a.min();
}

}  // namespace newquic

// TODO(bradleybear): Get rid of this when we get rid of
// quic_startup_faster_interval_set_flag.
class QUIC_NO_EXPORT QuicIntervalSetParameterSetter {
 private:
  // friend the tests so that we can SetUseFasterIntervalSet in the tests.
  template <typename T>
  friend class QuicIntervalSet;
  friend void Quic_Test_Set_Fast(bool fast);
  static bool* UseFasterIntervalSetAddress() {
    static bool result = GetQuicRestartFlag(quic_startup_faster_interval_set);
    return &result;
  }
  static void SetUseFasterIntervalSet(bool use) {
    *UseFasterIntervalSetAddress() = use;
  }
  static bool UseFasterIntervalSet() { return *UseFasterIntervalSetAddress(); }
};

template <typename T>
class QUIC_NO_EXPORT QuicIntervalSet {
  template <class old_iterator, class new_iterator>
  class InternalIterator;
  using OldSet = oldquic::QuicIntervalSet<T>;
  using NewSet = newquic::QuicIntervalSet<T>;
  using QISet = absl::variant<OldSet, NewSet>;

 public:
  typedef QuicInterval<T> value_type;
  using const_iterator = InternalIterator<typename OldSet::const_iterator,
                                          typename NewSet::const_iterator>;
  using const_reverse_iterator =
      InternalIterator<typename OldSet::const_reverse_iterator,
                       typename NewSet::const_reverse_iterator>;

  QuicIntervalSet()
      : qiset_(QuicIntervalSetParameterSetter::UseFasterIntervalSet()
                   ? QISet(NewSet())
                   : QISet(OldSet())) {}

  explicit QuicIntervalSet(const value_type& interval)
      : qiset_(QuicIntervalSetParameterSetter::UseFasterIntervalSet()
                   ? QISet(NewSet(interval))
                   : QISet(OldSet(interval))) {}

  QuicIntervalSet(const T& min, const T& max)
      : qiset_(QuicIntervalSetParameterSetter::UseFasterIntervalSet()
                   ? QISet(NewSet(min, max))
                   : QISet(OldSet(min, max))) {}

  QuicIntervalSet(std::initializer_list<value_type> il)
      : qiset_(QuicIntervalSetParameterSetter::UseFasterIntervalSet()
                   ? QISet(NewSet(il))
                   : QISet(OldSet(il))) {}

  void Clear() {
    return absl::visit([](auto& s) { s.Clear(); }, qiset_);
  }
  size_t Size() const {
    return absl::visit([](const auto& s) { return s.Size(); }, qiset_);
  }
  value_type SpanningInterval() const {
    return absl::visit([](auto& s) { return s.SpanningInterval(); }, qiset_);
  }
  void Add(const value_type& interval) {
    return absl::visit([&](auto& s) { return s.Add(interval); }, qiset_);
  }
  void Add(const T& min, const T& max) {
    return absl::visit([&](auto& s) { return s.Add(min, max); }, qiset_);
  }
  void AddOptimizedForAppend(const value_type& interval) {
    return absl::visit(
        [&](auto& s) { return s.AddOptimizedForAppend(interval); }, qiset_);
  }
  void AddOptimizedForAppend(const T& min, const T& max) {
    return absl::visit(
        [&](auto& s) { return s.AddOptimizedForAppend(min, max); }, qiset_);
  }
  void PopFront() {
    return absl::visit([](auto& s) { return s.PopFront(); }, qiset_);
  }
  bool Empty() const {
    return absl::visit([](auto& s) { return s.Empty(); }, qiset_);
  }
  bool Contains(const T& value) const {
    return absl::visit([&](auto& s) { return s.Contains(value); }, qiset_);
  }
  bool Contains(const value_type& interval) const {
    return absl::visit([&](auto& s) { return s.Contains(interval); }, qiset_);
  }
  bool Contains(const T& min, const T& max) const {
    return absl::visit([&](auto& s) { return s.Contains(min, max); }, qiset_);
  }

 private:
  template <class A, class B, class C>
  struct overloader : A, B, C {
    overloader(A a, B b, C c) : A(a), B(b), C(c) {}
    using A::operator();
    using B::operator();
    using C::operator();
  };
  template <class A, class B, class C>
  static auto make_visitor(A a, B b, C c) {
    return overloader<A, B, C>(a, b, c);
  }

 public:
  bool Contains(const QuicIntervalSet<T>& other) const {
    return absl::visit(
        make_visitor(
            // Sadly C++11's templated lambda system isn't quite powerful enough
            // to specify that the two auto&& arguments are the same, so we have
            // to specify two functions.
            [](const OldSet& a, const OldSet& b) { return a.Contains(b); },
            [](const NewSet& a, const NewSet& b) { return a.Contains(b); },
            // If the types mismatch then return false.  This shouldn't happen
            // in production since we capture the
            // quic_startup_faster_interval_set flag very early.  But tests can
            // make it happen.
            []([[maybe_unused]] auto&& a, [[maybe_unused]] auto&& b) {
              return false;
            }),
        qiset_, other.qiset_);
  }
  bool Intersects(const QuicIntervalSet& other) const {
    return absl::visit(
        make_visitor(
            [](const OldSet& a, const OldSet& b) { return a.Intersects(b); },
            [](const NewSet& a, const NewSet& b) { return a.Intersects(b); },
            []([[maybe_unused]] auto&& a, [[maybe_unused]] auto&& b) {
              return false;
            }),
        qiset_, other.qiset_);
  }
  const_iterator Find(const T& value) const {
    return absl::visit([&](auto& s) { return const_iterator(s.Find(value)); },
                       qiset_);
  }
  const_iterator Find(const T& min, const T& max) const {
    return absl::visit(
        [&](auto& s) { return const_iterator(s.Find(min, max)); }, qiset_);
  }
  const_iterator LowerBound(const T& value) const {
    return absl::visit(
        [&](auto& s) { return const_iterator(s.LowerBound(value)); }, qiset_);
  }
  const_iterator UpperBound(const T& value) const {
    return absl::visit(
        [&](auto& s) { return const_iterator(s.UpperBound(value)); }, qiset_);
  }
  bool IsDisjoint(const value_type& interval) const {
    return absl::visit([&](auto& s) { return s.IsDisjoint(interval); }, qiset_);
  }
  void Union(const QuicIntervalSet& other) {
    return absl::visit(
        make_visitor([](OldSet& a, const OldSet& b) { return a.Union(b); },
                     [](NewSet& a, const NewSet& b) { return a.Union(b); },
                     []([[maybe_unused]] auto&& a, [[maybe_unused]] auto&& b) {
                       return void();
                     }),
        qiset_, other.qiset_);
  }
  void Intersection(const QuicIntervalSet& other) {
    return absl::visit(
        make_visitor(
            [](OldSet& a, const OldSet& b) { return a.Intersection(b); },
            [](NewSet& a, const NewSet& b) { return a.Intersection(b); },
            []([[maybe_unused]] auto&& a, [[maybe_unused]] auto&& b) {
              return void();
            }),
        qiset_, other.qiset_);
  }
  void Difference(const value_type& interval) {
    return absl::visit([&](auto& s) { return s.Difference(interval); }, qiset_);
  }
  void Difference(const T& min, const T& max) {
    return absl::visit([&](auto& s) { return s.Difference(min, max); }, qiset_);
  }
  void Difference(const QuicIntervalSet& other) {
    return absl::visit(
        make_visitor([](OldSet& a, const OldSet& b) { return a.Difference(b); },
                     [](NewSet& a, const NewSet& b) { return a.Difference(b); },
                     []([[maybe_unused]] auto&& a, [[maybe_unused]] auto&& b) {
                       return void();
                     }),
        qiset_, other.qiset_);
  }

  void Complement(const T& min, const T& max) {
    return absl::visit([&](auto& s) { return s.Complement(min, max); }, qiset_);
  }
  bool TrimLessThan(const T& value) {
    return absl::visit([&](auto& s) { return s.TrimLessThan(value); }, qiset_);
  }
  const_iterator begin() const {
    return absl::visit([](auto& s) { return const_iterator(s.begin()); },
                       qiset_);
  }
  const_iterator end() const {
    return absl::visit([](auto& s) { return const_iterator(s.end()); }, qiset_);
  }
  const_reverse_iterator rbegin() const {
    return absl::visit(
        [](auto& s) { return const_reverse_iterator(s.rbegin()); }, qiset_);
  }
  const_reverse_iterator rend() const {
    return absl::visit([](auto& s) { return const_reverse_iterator(s.rend()); },
                       qiset_);
  }
  template <typename Iter>
  void assign(Iter first, Iter last) {
    return absl::visit([&](auto& s) { return s.assign(first, last); }, qiset_);
  }
  void assign(std::initializer_list<value_type> il) {
    return absl::visit([&](auto& s) { return s.assign(il); }, qiset_);
  }
  std::string ToString() const {
    return absl::visit([](auto& s) { return s.ToString(); }, qiset_);
  }
  friend bool operator==(const QuicIntervalSet& a, const QuicIntervalSet& b) {
    return absl::visit(
        make_visitor([](const OldSet& a, const OldSet& b) { return a == b; },
                     [](const NewSet& a, const NewSet& b) { return a == b; },
                     []([[maybe_unused]] auto&& a, [[maybe_unused]] auto&& b) {
                       return false;
                     }),
        a.qiset_, b.qiset_);
  }
  friend bool operator!=(const QuicIntervalSet& a, const QuicIntervalSet& b) {
    return absl::visit(
        make_visitor([](const OldSet& a, const OldSet& b) { return a != b; },
                     [](const NewSet& a, const NewSet& b) { return a != b; },
                     []([[maybe_unused]] auto&& a, [[maybe_unused]] auto&& b) {
                       return true;
                     }),
        a.qiset_, b.qiset_);
  }

 private:
  template <class old_iterator, class new_iterator>
  // This same idea appeared in cl/338686797 as IteratorWrapper. Perhaps we
  // should implement it once and for all.
  class InternalIterator
      : public std::iterator<std::forward_iterator_tag,    // iterator category
                             QuicIntervalSet::value_type,  // value_type
                             ptrdiff_t,                    // difference_type
                             const value_type*,            // pointer
                             const value_type&             // reference
                             > {
   public:
    const value_type* operator->() const {
      return absl::visit([](auto& it) { return &*it; }, it_);
    }
    const value_type& operator*() const {
      // Must return &*it (rather than just returning *it) since, for some
      // iterators (especially const_iterators) return a value_type instead of a
      // value_type&.  The standard says that it must return a "reference,
      // convertible to T" but doesn't actually say that the "reference" must be
      // a reference type.  The standard isn't very clear, but the simpler code
      // doesn't work.
      return *absl::visit([](auto& it) { return &*it; }, it_);
    }
    InternalIterator& operator++() {
      absl::visit([](auto& it) { ++it; }, it_);
      return *this;
    }
    InternalIterator& operator--() {
      absl::visit([](auto& it) { --it; }, it_);
      return *this;
    }

   private:
    friend QuicIntervalSet;
    // The following doesn't work for some compiler combinations:
    //   explicit InternalIterator(old_iterator it) : it_(std::move(it)) {}
    //   explicit InternalIterator(new_iterator it) : it_(std::move(it)) {}
    // So we are using emplace instead.
    explicit InternalIterator(old_iterator it) {
      it_.template emplace<0>(std::move(it));
    }
    explicit InternalIterator(new_iterator it) {
      it_.template emplace<1>(std::move(it));
    }
    friend bool operator==(const InternalIterator& a,
                           const InternalIterator& b) {
      return absl::visit(
          make_visitor([](const old_iterator& a,
                          const old_iterator& b) { return a == b; },
                       [](const new_iterator& a, const new_iterator& b) {
                         return a == b;
                       },
                       []([[maybe_unused]] auto&& a,
                          [[maybe_unused]] auto&& b) { return false; }),
          a.it_, b.it_);
    }
    friend bool operator!=(const InternalIterator& a,
                           const InternalIterator& b) {
      return absl::visit(
          make_visitor([](const old_iterator& a,
                          const old_iterator& b) { return a != b; },
                       [](const new_iterator& a, const new_iterator& b) {
                         return a != b;
                       },
                       []([[maybe_unused]] auto&& a,
                          [[maybe_unused]] auto&& b) { return true; }),
          a.it_, b.it_);
    }
    absl::variant<old_iterator, new_iterator> it_;
  };

  QISet qiset_;
};

template <typename T>
auto operator<<(std::ostream& out, const QuicIntervalSet<T>& seq)
    -> decltype(out << *seq.begin()) {
  out << "{";
  for (const auto& interval : seq) {
    out << " " << interval;
  }
  out << " }";

  return out;
}

}  // namespace quic

#endif  // QUICHE_QUIC_CORE_QUIC_INTERVAL_SET_H_