chromium/net/base/interval.h

// Copyright 2015 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// An Interval<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 interval, comparing two intervals, 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 Interval<T> is represented using the usual C++ STL convention, namely as
// the half-open interval [min, max). A point p is considered to be contained in
// the interval iff p >= min && p < max. One consequence of this definition is
// that for any non-empty interval, min is contained in the interval but max is
// not. There is no canonical representation for the empty interval; rather, any
// interval where max <= min is regarded as empty. As a consequence, two empty
// intervals 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 Interval<T>::Length
// is used.
//
// For equality comparisons, Interval<T> supports an Equals() method and an
// operator==() which delegates to it. Two intervals are considered equal if
// either they are both empty or if their corresponding min and max fields
// compare equal. For ordered comparisons, Interval<T> also provides the
// comparator Interval<T>::Less and an operator<() which delegates to it.
// Unfortunately this comparator is currently buggy because its behavior is
// inconsistent with Equals(): two empty ranges with different representations
// may be regarded as equivalent by Equals() but regarded as different by
// the comparator. Bug 9240050 has been created to address this.
//
// This class is thread-compatible if T is thread-compatible. (See
// go/thread-compatible).
//
// Examples:
//   Interval<int> r1(0, 100);  // The interval [0, 100).
//   EXPECT_TRUE(r1.Contains(0));
//   EXPECT_TRUE(r1.Contains(50));
//   EXPECT_FALSE(r1.Contains(100));  // 100 is just outside the interval.
//
//   Interval<int> r2(50, 150);  // The interval [50, 150).
//   EXPECT_TRUE(r1.Intersects(r2));
//   EXPECT_FALSE(r1.Contains(r2));
//   EXPECT_TRUE(r1.IntersectWith(r2));  // Mutates r1.
//   EXPECT_EQ(Interval<int>(50, 100), r1);  // r1 is now [50, 100).
//
//   Interval<int> r3(1000, 2000);  // The interval [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.

#ifndef NET_BASE_INTERVAL_H_
#define NET_BASE_INTERVAL_H_

#include <stddef.h>

#include <algorithm>
#include <functional>
#include <ostream>
#include <utility>
#include <vector>

namespace net {

template <typename T>
class Interval { … };

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

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

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

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

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

}  // namespace net

#endif  // NET_BASE_INTERVAL_H_