chromium/net/third_party/quiche/src/quiche/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>

#include "quiche/quic/platform/api/quic_export.h"

namespace quic {

template <typename T>
class QUICHE_NO_EXPORT QuicInterval { … };

// Constructs an QuicInterval by deducing the types from the function arguments.
template <typename T>
QuicInterval<T> MakeQuicInterval(T&& lhs, 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()) { … }

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

template <typename T>
bool QuicInterval<T>::Intersects(const QuicInterval& i,
                                 QuicInterval* out) const { … }

template <typename T>
bool QuicInterval<T>::IntersectWith(const QuicInterval& i) { … }

template <typename T>
bool QuicInterval<T>::SpanningUnion(const QuicInterval& i) { … }

template <typename T>
bool QuicInterval<T>::Difference(const QuicInterval& i,
                                 std::vector<QuicInterval*>* difference) const { … }

template <typename T>
bool QuicInterval<T>::Difference(const QuicInterval& i, QuicInterval* lo,
                                 QuicInterval* hi) const { … }

}  // namespace quic

#endif  // QUICHE_QUIC_CORE_QUIC_INTERVAL_H_