quic/core/quic_interval.h

// 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_H_
#define QUICHE_QUIC_CORE_QUIC_INTERVAL_H_

// An QuicInterval<T> is a data structure used to represent a contiguous,
// mutable range over an ordered type T. Supported operations include testing a
// value to see whether it is included in the QuicInterval, comparing two
// QuicIntervals, and performing their union, intersection, and difference. For
// the purposes of this library, an "ordered type" is any type that induces a
// total order on its values via its less-than operator (operator<()). Examples
// of such types are basic arithmetic types like int and double as well as class
// types like string.
//
// An QuicInterval<T> is represented using the usual C++ STL convention, namely
// as the half-open QuicInterval [min, max). A point p is considered to be
// contained in the QuicInterval iff p >= min && p < max. One consequence of
// this definition is that for any non-empty QuicInterval, min is contained in
// the QuicInterval but max is not. There is no canonical representation for the
// empty QuicInterval; rather, any QuicInterval where max <= min is regarded as
// empty. As a consequence, two empty QuicIntervals will still compare as equal
// despite possibly having different underlying min() or max() values. Also
// beware of the terminology used here: the library uses the terms "min" and
// "max" rather than "begin" and "end" as is conventional for the STL.
//
// T is required to be default- and copy-constructable, to have an assignment
// operator, and the full complement of comparison operators (<, <=, ==, !=, >=,
// >).  A difference operator (operator-()) is required if
// QuicInterval<T>::Length is used.
//
// QuicInterval supports operator==. Two QuicIntervals are considered equal if
// either they are both empty or if their corresponding min and max fields
// compare equal. QuicInterval also provides an operator<. Unfortunately,
// operator< is currently buggy because its behavior is inconsistent with
// operator==: two empty ranges with different representations may be regarded
// as equal by operator== but regarded as different by operator<. Bug 9240050
// has been created to address this.
//
//
// Examples:
//   QuicInterval<int> r1(0, 100);  // The QuicInterval [0, 100).
//   EXPECT_TRUE(r1.Contains(0));
//   EXPECT_TRUE(r1.Contains(50));
//   EXPECT_FALSE(r1.Contains(100));  // 100 is just outside the QuicInterval.
//
//   QuicInterval<int> r2(50, 150);  // The QuicInterval [50, 150).
//   EXPECT_TRUE(r1.Intersects(r2));
//   EXPECT_FALSE(r1.Contains(r2));
//   EXPECT_TRUE(r1.IntersectWith(r2));  // Mutates r1.
//   EXPECT_EQ(QuicInterval<int>(50, 100), r1);  // r1 is now [50, 100).
//
//   QuicInterval<int> r3(1000, 2000);  // The QuicInterval [1000, 2000).
//   EXPECT_TRUE(r1.IntersectWith(r3));  // Mutates r1.
//   EXPECT_TRUE(r1.Empty());  // Now r1 is empty.
//   EXPECT_FALSE(r1.Contains(r1.min()));  // e.g. doesn't contain its own min.

#include <stddef.h>
#include <algorithm>
#include <ostream>
#include <type_traits>
#include <utility>
#include <vector>

namespace quic {

template <typename T>
class QuicInterval {
 private:
  // Type trait for deriving the return type for QuicInterval::Length.  If
  // operator-() is not defined for T, then the return type is void.  This makes
  // the signature for Length compile so that the class can be used for such T,
  // but code that calls Length would still generate a compilation error.
  template <typename U>
  class DiffTypeOrVoid {
   private:
    template <typename V>
    static auto f(const V* v) -> decltype(*v - *v);
    template <typename V>
    static void f(...);

   public:
    using type = typename std::decay<decltype(f<U>(nullptr))>::type;
  };

 public:
  // Construct an QuicInterval representing an empty QuicInterval.
  QuicInterval() : min_(), max_() {}

  // Construct an QuicInterval representing the QuicInterval [min, max). If min
  // < max, the constructed object will represent the non-empty QuicInterval
  // containing all values from min up to (but not including) max. On the other
  // hand, if min >= max, the constructed object will represent the empty
  // QuicInterval.
  QuicInterval(const T& min, const T& max) : min_(min), max_(max) {}

  template <typename U1,
            typename U2,
            typename = typename std::enable_if<
                std::is_convertible<U1, T>::value &&
                std::is_convertible<U2, T>::value>::type>
  QuicInterval(U1&& min, U2&& max)
      : min_(std::forward<U1>(min)), max_(std::forward<U2>(max)) {}

  const T& min() const { return min_; }
  const T& max() const { return max_; }
  void SetMin(const T& t) { min_ = t; }
  void SetMax(const T& t) { max_ = t; }

  void Set(const T& min, const T& max) {
    SetMin(min);
    SetMax(max);
  }

  void Clear() { *this = {}; }

  bool Empty() const { return min() >= max(); }

  // Returns the length of this QuicInterval. The value returned is zero if
  // Empty() is true; otherwise the value returned is max() - min().
  typename DiffTypeOrVoid<T>::type Length() const {
    return (Empty() ? min() : max()) - min();
  }

  // Returns true iff t >= min() && t < max().
  bool Contains(const T& t) const { return min() <= t && max() > t; }

  // Returns true iff *this and i are non-empty, and *this includes i. "*this
  // includes i" means that for all t, if i.Contains(t) then this->Contains(t).
  // Note the unintuitive consequence of this definition: this method always
  // returns false when i is the empty QuicInterval.
  bool Contains(const QuicInterval& i) const {
    return !Empty() && !i.Empty() && min() <= i.min() && max() >= i.max();
  }

  // Returns true iff there exists some point t for which this->Contains(t) &&
  // i.Contains(t) evaluates to true, i.e. if the intersection is non-empty.
  bool Intersects(const QuicInterval& i) const {
    return !Empty() && !i.Empty() && min() < i.max() && max() > i.min();
  }

  // Returns true iff there exists some point t for which this->Contains(t) &&
  // i.Contains(t) evaluates to true, i.e. if the intersection is non-empty.
  // Furthermore, if the intersection is non-empty and the out pointer is not
  // null, this method stores the calculated intersection in *out.
  bool Intersects(const QuicInterval& i, QuicInterval* out) const;

  // Sets *this to be the intersection of itself with i. Returns true iff
  // *this was modified.
  bool IntersectWith(const QuicInterval& i);

  // Calculates the smallest QuicInterval containing both *this i, and updates
  // *this to represent that QuicInterval, and returns true iff *this was
  // modified.
  bool SpanningUnion(const QuicInterval& i);

  // Determines the difference between two QuicIntervals by finding all points
  // that are contained in *this but not in i, coalesces those points into the
  // largest possible contiguous QuicIntervals, and appends those QuicIntervals
  // to the *difference vector. Intuitively this can be thought of as "erasing"
  // i from *this. This will either completely erase *this (leaving nothing
  // behind), partially erase some of *this from the left or right side (leaving
  // some residual behind), or erase a hole in the middle of *this (leaving
  // behind an QuicInterval on either side). Therefore, 0, 1, or 2 QuicIntervals
  // will be appended to *difference. The method returns true iff the
  // intersection of *this and i is non-empty. The caller owns the vector and
  // the QuicInterval* pointers inside it. The difference vector is required to
  // be non-null.
  bool Difference(const QuicInterval& i,
                  std::vector<QuicInterval*>* difference) const;

  // Determines the difference between two QuicIntervals as in
  // Difference(QuicInterval&, vector*), but stores the results directly in out
  // parameters rather than dynamically allocating an QuicInterval* and
  // appending it to a vector. If two results are generated, the one with the
  // smaller value of min() will be stored in *lo and the other in *hi.
  // Otherwise (if fewer than two results are generated), unused arguments will
  // be set to the empty QuicInterval (it is possible that *lo will be empty and
  // *hi non-empty). The method returns true iff the intersection of *this and i
  // is non-empty.
  bool Difference(const QuicInterval& i,
                  QuicInterval* lo,
                  QuicInterval* hi) const;

  friend bool operator==(const QuicInterval& a, const QuicInterval& b) {
    bool ae = a.Empty();
    bool be = b.Empty();
    if (ae && be)
      return true;  // All empties are equal.
    if (ae != be)
      return false;  // Empty cannot equal nonempty.
    return a.min() == b.min() && a.max() == b.max();
  }

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

  // Defines a comparator which can be used to induce an order on QuicIntervals,
  // so that, for example, they can be stored in an ordered container such as
  // std::set. The ordering is arbitrary, but does provide the guarantee that,
  // for non-empty QuicIntervals X and Y, if X contains Y, then X <= Y.
  // TODO(kosak): The current implementation of this comparator has a problem
  // because the ordering it induces is inconsistent with that of Equals(). In
  // particular, this comparator does not properly consider all empty
  // QuicIntervals equivalent. Bug 9240050 has been created to track this.
  friend bool operator<(const QuicInterval& a, const QuicInterval& b) {
    return a.min() < b.min() || (!(b.min() < a.min()) && b.max() < a.max());
  }

 private:
  T min_;  // Inclusive lower bound.
  T max_;  // Exclusive upper bound.
};

// Constructs an QuicInterval by deducing the types from the function arguments.
template <typename T>
QuicInterval<T> MakeQuicInterval(T&& lhs, T&& rhs) {
  return QuicInterval<T>(std::forward<T>(lhs), std::forward<T>(rhs));
}

// Note: ideally we'd use
//   decltype(out << "[" << i.min() << ", " << i.max() << ")")
// as return type of the function, but as of July 2017 this triggers g++
// "sorry, unimplemented: string literal in function template signature" error.
template <typename T>
auto operator<<(std::ostream& out, const QuicInterval<T>& i)
    -> decltype(out << i.min()) {
  return out << "[" << i.min() << ", " << i.max() << ")";
}

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

template <typename T>
bool QuicInterval<T>::Intersects(const QuicInterval& i,
                                 QuicInterval* out) const {
  if (!Intersects(i))
    return false;
  if (out != nullptr) {
    *out = QuicInterval(std::max(min(), i.min()), std::min(max(), i.max()));
  }
  return true;
}

template <typename T>
bool QuicInterval<T>::IntersectWith(const QuicInterval& i) {
  if (Empty())
    return false;
  bool modified = false;
  if (i.min() > min()) {
    SetMin(i.min());
    modified = true;
  }
  if (i.max() < max()) {
    SetMax(i.max());
    modified = true;
  }
  return modified;
}

template <typename T>
bool QuicInterval<T>::SpanningUnion(const QuicInterval& i) {
  if (i.Empty())
    return false;
  if (Empty()) {
    *this = i;
    return true;
  }
  bool modified = false;
  if (i.min() < min()) {
    SetMin(i.min());
    modified = true;
  }
  if (i.max() > max()) {
    SetMax(i.max());
    modified = true;
  }
  return modified;
}

template <typename T>
bool QuicInterval<T>::Difference(const QuicInterval& i,
                                 std::vector<QuicInterval*>* difference) const {
  if (Empty()) {
    // <empty> - <i> = <empty>
    return false;
  }
  if (i.Empty()) {
    // <this> - <empty> = <this>
    difference->push_back(new QuicInterval(*this));
    return false;
  }
  if (min() < i.max() && min() >= i.min() && max() > i.max()) {
    //            [------ this ------)
    // [------ i ------)
    //                 [-- result ---)
    difference->push_back(new QuicInterval(i.max(), max()));
    return true;
  }
  if (max() > i.min() && max() <= i.max() && min() < i.min()) {
    // [------ this ------)
    //            [------ i ------)
    // [- result -)
    difference->push_back(new QuicInterval(min(), i.min()));
    return true;
  }
  if (min() < i.min() && max() > i.max()) {
    // [------- this --------)
    //      [---- i ----)
    // [ R1 )           [ R2 )
    // There are two results: R1 and R2.
    difference->push_back(new QuicInterval(min(), i.min()));
    difference->push_back(new QuicInterval(i.max(), max()));
    return true;
  }
  if (min() >= i.min() && max() <= i.max()) {
    //   [--- this ---)
    // [------ i --------)
    // Intersection is <this>, so difference yields the empty QuicInterval.
    // Nothing is appended to *difference.
    return true;
  }
  // No intersection. Append <this>.
  difference->push_back(new QuicInterval(*this));
  return false;
}

template <typename T>
bool QuicInterval<T>::Difference(const QuicInterval& i,
                                 QuicInterval* lo,
                                 QuicInterval* hi) const {
  // Initialize *lo and *hi to empty
  *lo = {};
  *hi = {};
  if (Empty())
    return false;
  if (i.Empty()) {
    *lo = *this;
    return false;
  }
  if (min() < i.max() && min() >= i.min() && max() > i.max()) {
    //            [------ this ------)
    // [------ i ------)
    //                 [-- result ---)
    *hi = QuicInterval(i.max(), max());
    return true;
  }
  if (max() > i.min() && max() <= i.max() && min() < i.min()) {
    // [------ this ------)
    //            [------ i ------)
    // [- result -)
    *lo = QuicInterval(min(), i.min());
    return true;
  }
  if (min() < i.min() && max() > i.max()) {
    // [------- this --------)
    //      [---- i ----)
    // [ R1 )           [ R2 )
    // There are two results: R1 and R2.
    *lo = QuicInterval(min(), i.min());
    *hi = QuicInterval(i.max(), max());
    return true;
  }
  if (min() >= i.min() && max() <= i.max()) {
    //   [--- this ---)
    // [------ i --------)
    // Intersection is <this>, so difference yields the empty QuicInterval.
    return true;
  }
  *lo = *this;  // No intersection.
  return false;
}

}  // namespace quic

#endif  // QUICHE_QUIC_CORE_QUIC_INTERVAL_H_