/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#ifndef DOM_MEDIA_INTERVALS_H_
#define DOM_MEDIA_INTERVALS_H_
#include <algorithm>
#include <type_traits>
#include "nsTArray.h"
#include "nsString.h"
#include "nsPrintfCString.h"
// Specialization for nsTArray CopyChooser.
namespace mozilla::media {
template <
class T>
class IntervalSet;
class TimeUnit;
}
// namespace mozilla::media
template <
class E>
struct nsTArray_RelocationStrategy<mozilla::media::IntervalSet<E>> {
typedef nsTArray_RelocateUsingMoveConstructor<mozilla::media::IntervalSet<E>>
Type;
};
namespace mozilla::media {
/* Interval defines an interval between two points. Unlike a traditional
interval [A,B] where A <= x <= B, the upper boundary B is exclusive: A <= x <
B (e.g [A,B[ or [A,B) depending on where you're living) It provides basic
interval arithmetic and fuzzy edges. The type T must provides a default
constructor and +, -, <, <= and == operators.
*/
template <
typename T>
class Interval {
public:
typedef Interval<T> SelfType;
Interval() : mStart(T()), mEnd(T()), mFuzz(T()) {}
template <
typename StartArg,
typename EndArg>
Interval(StartArg&& aStart, EndArg&& aEnd)
: mStart(aStart), mEnd(aEnd), mFuzz() {
MOZ_DIAGNOSTIC_ASSERT(mStart <= mEnd,
"Invalid Interval");
}
template <
typename StartArg,
typename EndArg,
typename FuzzArg>
Interval(StartArg&& aStart, EndArg&& aEnd, FuzzArg&& aFuzz)
: mStart(aStart), mEnd(aEnd), mFuzz(aFuzz) {
MOZ_DIAGNOSTIC_ASSERT(mStart <= mEnd,
"Invalid Interval");
}
Interval(
const SelfType& aOther)
: mStart(aOther.mStart), mEnd(aOther.mEnd), mFuzz(aOther.mFuzz) {}
Interval(SelfType&& aOther)
: mStart(std::move(aOther.mStart)),
mEnd(std::move(aOther.mEnd)),
mFuzz(std::move(aOther.mFuzz)) {}
SelfType&
operator=(
const SelfType& aOther) {
mStart = aOther.mStart;
mEnd = aOther.mEnd;
mFuzz = aOther.mFuzz;
return *
this;
}
SelfType&
operator=(SelfType&& aOther) {
MOZ_ASSERT(&aOther !=
this,
"self-moves are prohibited");
this->~Interval();
new (
this) Interval(std::move(aOther));
return *
this;
}
// Basic interval arithmetic operator definition.
SelfType
operator+(
const SelfType& aOther)
const {
return SelfType(mStart + aOther.mStart, mEnd + aOther.mEnd,
mFuzz + aOther.mFuzz);
}
SelfType
operator+(
const T& aVal)
const {
return SelfType(mStart + aVal, mEnd + aVal, mFuzz);
}
SelfType operator-(
const SelfType& aOther)
const {
return SelfType(mStart - aOther.mEnd, mEnd - aOther.mStart,
mFuzz + aOther.mFuzz);
}
SelfType operator-(
const T& aVal)
const {
return SelfType(mStart - aVal, mEnd - aVal, mFuzz);
}
SelfType&
operator+=(
const SelfType& aOther) {
mStart += aOther.mStart;
mEnd += aOther.mEnd;
mFuzz += aOther.mFuzz;
return *
this;
}
SelfType&
operator+=(
const T& aVal) {
mStart += aVal;
mEnd += aVal;
return *
this;
}
SelfType& operator-=(
const SelfType& aOther) {
mStart -= aOther.mStart;
mEnd -= aOther.mEnd;
mFuzz += aOther.mFuzz;
return *
this;
}
SelfType& operator-=(
const T& aVal) {
mStart -= aVal;
mEnd -= aVal;
return *
this;
}
bool operator==(
const SelfType& aOther)
const {
return mStart == aOther.mStart && mEnd == aOther.mEnd;
}
bool operator!=(
const SelfType& aOther)
const {
return !(*
this == aOther); }
bool Contains(
const T& aX)
const {
return mStart - mFuzz <= aX && aX < mEnd + mFuzz;
}
bool ContainsStrict(
const T& aX)
const {
return mStart <= aX && aX < mEnd; }
bool ContainsWithStrictEnd(
const T& aX)
const {
return mStart - mFuzz <= aX && aX < mEnd;
}
bool Contains(
const SelfType& aOther)
const {
return (mStart - mFuzz <= aOther.mStart + aOther.mFuzz) &&
(aOther.mEnd - aOther.mFuzz <= mEnd + mFuzz);
}
bool ContainsStrict(
const SelfType& aOther)
const {
return mStart <= aOther.mStart && aOther.mEnd <= mEnd;
}
bool ContainsWithStrictEnd(
const SelfType& aOther)
const {
return (mStart - mFuzz <= aOther.mStart + aOther.mFuzz) &&
aOther.mEnd <= mEnd;
}
bool Intersects(
const SelfType& aOther)
const {
return (mStart - mFuzz < aOther.mEnd + aOther.mFuzz) &&
(aOther.mStart - aOther.mFuzz < mEnd + mFuzz);
}
bool IntersectsStrict(
const SelfType& aOther)
const {
return mStart < aOther.mEnd && aOther.mStart < mEnd;
}
// Same as Intersects, but including the boundaries.
bool Touches(
const SelfType& aOther)
const {
return (mStart - mFuzz <= aOther.mEnd + aOther.mFuzz) &&
(aOther.mStart - aOther.mFuzz <= mEnd + mFuzz);
}
// Returns true if aOther is strictly to the right of this and contiguous.
// This operation isn't commutative.
bool Contiguous(
const SelfType& aOther)
const {
return mEnd <= aOther.mStart &&
aOther.mStart - mEnd <= mFuzz + aOther.mFuzz;
}
bool RightOf(
const SelfType& aOther)
const {
return aOther.mEnd - aOther.mFuzz <= mStart + mFuzz;
}
bool LeftOf(
const SelfType& aOther)
const {
return mEnd - mFuzz <= aOther.mStart + aOther.mFuzz;
}
SelfType Span(
const SelfType& aOther)
const {
if (IsEmpty()) {
return aOther;
}
SelfType result(*
this);
if (aOther.mStart < mStart) {
result.mStart = aOther.mStart;
}
if (mEnd < aOther.mEnd) {
result.mEnd = aOther.mEnd;
}
if (mFuzz < aOther.mFuzz) {
result.mFuzz = aOther.mFuzz;
}
return result;
}
SelfType Intersection(
const SelfType& aOther)
const {
const T& s = std::max(mStart, aOther.mStart);
const T& e = std::min(mEnd, aOther.mEnd);
const T& f = std::max(mFuzz, aOther.mFuzz);
if (s < e) {
return SelfType(s, e, f);
}
// Return an empty interval.
return SelfType();
}
T Length()
const {
return mEnd - mStart; }
bool IsEmpty()
const {
return mStart == mEnd; }
void SetFuzz(
const T& aFuzz) { mFuzz = aFuzz; }
// Returns true if the two intervals intersect with this being on the right
// of aOther
bool TouchesOnRight(
const SelfType& aOther)
const {
return aOther.mStart <= mStart &&
(mStart - mFuzz <= aOther.mEnd + aOther.mFuzz) &&
(aOther.mStart - aOther.mFuzz <= mEnd + mFuzz);
}
// Returns true if the two intervals intersect with this being on the right
// of aOther, ignoring fuzz.
bool TouchesOnRightStrict(
const SelfType& aOther)
const {
return aOther.mStart <= mStart && mStart <= aOther.mEnd;
}
nsCString ToString()
const {
if constexpr (std::is_same_v<T, TimeUnit>) {
return nsPrintfCString(
"[%s, %s](%s)", mStart.ToString().get(),
mEnd.ToString().get(), mFuzz.ToString().get());
}
else if constexpr (std::is_same_v<T,
double>) {
return nsPrintfCString(
"[%lf, %lf](%lf)", mStart, mEnd, mFuzz);
}
}
T mStart;
T mEnd;
T mFuzz;
};
// An IntervalSet in a collection of Intervals. The IntervalSet is always
// normalized.
template <
typename T>
class IntervalSet {
public:
typedef IntervalSet<T> SelfType;
typedef Interval<T> ElemType;
typedef AutoTArray<ElemType, 4> ContainerType;
typedef typename ContainerType::index_type IndexType;
IntervalSet() =
default;
virtual ~IntervalSet() =
default;
IntervalSet(
const SelfType& aOther) : mIntervals(aOther.mIntervals.Clone()) {}
IntervalSet(SelfType&& aOther) {
mIntervals.AppendElements(std::move(aOther.mIntervals));
}
explicit IntervalSet(
const ElemType& aOther) {
if (!aOther.IsEmpty()) {
mIntervals.AppendElement(aOther);
}
}
explicit IntervalSet(ElemType&& aOther) {
if (!aOther.IsEmpty()) {
mIntervals.AppendElement(std::move(aOther));
}
}
bool operator==(
const SelfType& aOther)
const {
return mIntervals == aOther.mIntervals;
}
bool operator!=(
const SelfType& aOther)
const {
return mIntervals != aOther.mIntervals;
}
SelfType&
operator=(
const SelfType& aOther) {
mIntervals = aOther.mIntervals.Clone();
return *
this;
}
SelfType&
operator=(SelfType&& aOther) {
MOZ_ASSERT(&aOther !=
this,
"self-moves are prohibited");
this->~IntervalSet();
new (
this) IntervalSet(std::move(aOther));
return *
this;
}
SelfType&
operator=(
const ElemType& aInterval) {
mIntervals.Clear();
if (!aInterval.IsEmpty()) {
mIntervals.AppendElement(aInterval);
}
return *
this;
}
SelfType&
operator=(ElemType&& aInterval) {
mIntervals.Clear();
if (!aInterval.IsEmpty()) {
mIntervals.AppendElement(std::move(aInterval));
}
return *
this;
}
SelfType& Add(
const SelfType& aIntervals) {
if (aIntervals.mIntervals.Length() == 1) {
Add(aIntervals.mIntervals[0]);
}
else {
mIntervals.AppendElements(aIntervals.mIntervals);
Normalize();
}
return *
this;
}
SelfType& Add(
const ElemType& aInterval) {
if (aInterval.IsEmpty()) {
return *
this;
}
if (mIntervals.IsEmpty()) {
mIntervals.AppendElement(aInterval);
return *
this;
}
ElemType& last = mIntervals.LastElement();
if (aInterval.TouchesOnRight(last)) {
last = last.Span(aInterval);
return *
this;
}
// Most of our actual usage is adding an interval that will be outside the
// range. We can speed up normalization here.
if (aInterval.RightOf(last)) {
mIntervals.AppendElement(aInterval);
return *
this;
}
ContainerType normalized;
ElemType current(aInterval);
IndexType i = 0;
for (; i < mIntervals.Length(); i++) {
ElemType& interval = mIntervals[i];
if (current.Touches(interval)) {
current = current.Span(interval);
}
else if (current.LeftOf(interval)) {
break;
}
else {
normalized.AppendElement(std::move(interval));
}
}
normalized.AppendElement(std::move(current));
for (; i < mIntervals.Length(); i++) {
normalized.AppendElement(std::move(mIntervals[i]));
}
mIntervals.Clear();
mIntervals.AppendElements(std::move(normalized));
return *
this;
}
SelfType&
operator+=(
const SelfType& aIntervals) {
Add(aIntervals);
return *
this;
}
SelfType&
operator+=(
const ElemType& aInterval) {
Add(aInterval);
return *
this;
}
SelfType
operator+(
const SelfType& aIntervals)
const {
SelfType intervals(*
this);
intervals.Add(aIntervals);
return intervals;
}
SelfType
operator+(
const ElemType& aInterval)
const {
SelfType intervals(*
this);
intervals.Add(aInterval);
return intervals;
}
friend SelfType
operator+(
const ElemType& aInterval,
const SelfType& aIntervals) {
SelfType intervals;
intervals.Add(aInterval);
intervals.Add(aIntervals);
return intervals;
}
// Excludes an interval from an IntervalSet.
SelfType& operator-=(
const ElemType& aInterval) {
if (aInterval.IsEmpty() || mIntervals.IsEmpty()) {
return *
this;
}
if (mIntervals.Length() == 1 &&
mIntervals[0].TouchesOnRightStrict(aInterval)) {
// Fast path when we're removing from the front of a set with a
// single interval. This is common for the buffered time ranges
// we see on Twitch.
if (aInterval.mEnd >= mIntervals[0].mEnd) {
mIntervals.RemoveElementAt(0);
}
else {
mIntervals[0].mStart = aInterval.mEnd;
mIntervals[0].mFuzz = std::max(mIntervals[0].mFuzz, aInterval.mFuzz);
}
return *
this;
}
// General case performed by inverting aInterval within the bounds of
// mIntervals and then doing the intersection.
T firstEnd = std::max(mIntervals[0].mStart, aInterval.mStart);
T secondStart = std::min(mIntervals.LastElement().mEnd, aInterval.mEnd);
ElemType startInterval(mIntervals[0].mStart, firstEnd);
ElemType endInterval(secondStart, mIntervals.LastElement().mEnd);
SelfType intervals(std::move(startInterval));
intervals += std::move(endInterval);
return Intersection(intervals);
}
SelfType& operator-=(
const SelfType& aIntervals) {
for (
const auto& interval : aIntervals.mIntervals) {
*
this -= interval;
}
return *
this;
}
SelfType operator-(
const SelfType& aInterval)
const {
SelfType intervals(*
this);
intervals -= aInterval;
return intervals;
}
SelfType operator-(
const ElemType& aInterval)
const {
SelfType intervals(*
this);
intervals -= aInterval;
return intervals;
}
// Mutate this IntervalSet to be the union of this and aOther.
SelfType&
Union(
const SelfType& aOther) {
Add(aOther);
return *
this;
}
SelfType&
Union(
const ElemType& aInterval) {
Add(aInterval);
return *
this;
}
// Mutate this TimeRange to be the intersection of this and aOther.
SelfType& Intersection(
const SelfType& aOther) {
ContainerType intersection;
// Ensure the intersection has enough capacity to store the upper bound on
// the intersection size. This ensures that we don't spend time reallocating
// the storage as we append, at the expense of extra memory.
intersection.SetCapacity(std::max(aOther.Length(), mIntervals.Length()));
const ContainerType& other = aOther.mIntervals;
IndexType i = 0, j = 0;
for (; i < mIntervals.Length() && j < other.Length();) {
if (mIntervals[i].IntersectsStrict(other[j])) {
intersection.AppendElement(mIntervals[i].Intersection(other[j]));
}
if (mIntervals[i].mEnd < other[j].mEnd) {
i++;
}
else {
j++;
}
}
mIntervals = std::move(intersection);
return *
this;
}
SelfType& Intersection(
const ElemType& aInterval) {
SelfType intervals(aInterval);
return Intersection(intervals);
}
const ElemType&
operator[](IndexType aIndex)
const {
return mIntervals[aIndex];
}
// Returns the start boundary of the first interval. Or a default constructed
// T if IntervalSet is empty (and aExists if provided will be set to false).
T GetStart(
bool* aExists = nullptr)
const {
bool exists = !mIntervals.IsEmpty();
if (aExists) {
*aExists = exists;
}
if (exists) {
return mIntervals[0].mStart;
}
else {
return T();
}
}
// Returns the end boundary of the last interval. Or a default constructed T
// if IntervalSet is empty (and aExists if provided will be set to false).
T GetEnd(
bool* aExists = nullptr)
const {
bool exists = !mIntervals.IsEmpty();
if (aExists) {
*aExists = exists;
}
if (exists) {
return mIntervals.LastElement().mEnd;
}
else {
return T();
}
}
IndexType Length()
const {
return mIntervals.Length(); }
bool IsEmpty()
const {
return mIntervals.IsEmpty(); }
T Start(IndexType aIndex)
const {
return mIntervals[aIndex].mStart; }
T Start(IndexType aIndex,
bool& aExists)
const {
aExists = aIndex < mIntervals.Length();
if (aExists) {
return mIntervals[aIndex].mStart;
}
else {
return T();
}
}
T End(IndexType aIndex)
const {
return mIntervals[aIndex].mEnd; }
T End(IndexType aIndex,
bool& aExists)
const {
aExists = aIndex < mIntervals.Length();
if (aExists) {
return mIntervals[aIndex].mEnd;
}
else {
return T();
}
}
bool Contains(
const ElemType& aInterval)
const {
for (
const auto& interval : mIntervals) {
if (interval.Contains(aInterval)) {
return true;
}
}
return false;
}
bool ContainsStrict(
const ElemType& aInterval)
const {
for (
const auto& interval : mIntervals) {
if (interval.ContainsStrict(aInterval)) {
return true;
}
}
return false;
}
bool Contains(
const T& aX)
const {
for (
const auto& interval : mIntervals) {
if (interval.Contains(aX)) {
return true;
}
}
return false;
}
bool ContainsStrict(
const T& aX)
const {
for (
const auto& interval : mIntervals) {
if (interval.ContainsStrict(aX)) {
return true;
}
}
return false;
}
bool ContainsWithStrictEnd(
const T& aX)
const {
for (
const auto& interval : mIntervals) {
if (interval.ContainsWithStrictEnd(aX)) {
return true;
}
}
return false;
}
bool ContainsWithStrictEnd(
const ElemType& aInterval)
const {
for (
const auto& interval : mIntervals) {
if (interval.ContainsWithStrictEnd(aInterval)) {
return true;
}
}
return false;
}
bool Intersects(
const ElemType& aInterval)
const {
for (
const auto& interval : mIntervals) {
if (interval.Intersects(aInterval)) {
return true;
}
}
return false;
}
bool IntersectsStrict(
const ElemType& aInterval)
const {
for (
const auto& interval : mIntervals) {
if (interval.IntersectsStrict(aInterval)) {
return true;
}
}
return false;
}
// Returns if there's any intersection between this and aOther.
bool IntersectsStrict(
const SelfType& aOther)
const {
const ContainerType& other = aOther.mIntervals;
IndexType i = 0, j = 0;
for (; i < mIntervals.Length() && j < other.Length();) {
if (mIntervals[i].IntersectsStrict(other[j])) {
return true;
}
if (mIntervals[i].mEnd < other[j].mEnd) {
i++;
}
else {
j++;
}
}
return false;
}
bool IntersectsWithStrictEnd(
const ElemType& aInterval)
const {
for (
const auto& interval : mIntervals) {
if (interval.IntersectsWithStrictEnd(aInterval)) {
return true;
}
}
return false;
}
// Shift all values by aOffset.
SelfType& Shift(
const T& aOffset) {
for (
auto& interval : mIntervals) {
interval.mStart = interval.mStart + aOffset;
interval.mEnd = interval.mEnd + aOffset;
}
return *
this;
}
void SetFuzz(
const T& aFuzz) {
for (
auto& interval : mIntervals) {
interval.SetFuzz(aFuzz);
}
MergeOverlappingIntervals();
}
static const IndexType NoIndex = IndexType(-1);
IndexType Find(
const T& aValue)
const {
for (IndexType i = 0; i < mIntervals.Length(); i++) {
if (mIntervals[i].Contains(aValue)) {
return i;
}
}
return NoIndex;
}
// Methods for range-based for loops.
typename ContainerType::iterator begin() {
return mIntervals.begin(); }
typename ContainerType::const_iterator begin()
const {
return mIntervals.begin();
}
typename ContainerType::const_iterator cbegin()
const {
return mIntervals.cbegin();
}
typename ContainerType::iterator end() {
return mIntervals.end(); }
typename ContainerType::const_iterator end()
const {
return mIntervals.end();
}
typename ContainerType::const_iterator cend()
const {
return mIntervals.cend();
}
ElemType& LastInterval() {
MOZ_ASSERT(!mIntervals.IsEmpty());
return mIntervals.LastElement();
}
const ElemType& LastInterval()
const {
MOZ_ASSERT(!mIntervals.IsEmpty());
return mIntervals.LastElement();
}
void Clear() { mIntervals.Clear(); }
protected:
ContainerType mIntervals;
private:
void Normalize() {
if (mIntervals.Length() < 2) {
return;
}
mIntervals.Sort(CompareIntervals());
MergeOverlappingIntervals();
}
void MergeOverlappingIntervals() {
if (mIntervals.Length() < 2) {
return;
}
// This merges the intervals in place.
IndexType read = 0;
IndexType write = 0;
while (read < mIntervals.Length()) {
ElemType current(mIntervals[read]);
read++;
while (read < mIntervals.Length() && current.Touches(mIntervals[read])) {
current = current.Span(mIntervals[read]);
read++;
}
mIntervals[write] = current;
write++;
}
mIntervals.SetLength(write);
}
struct CompareIntervals {
bool Equals(
const ElemType& aT1,
const ElemType& aT2)
const {
return aT1.mStart == aT2.mStart && aT1.mEnd == aT2.mEnd;
}
bool LessThan(
const ElemType& aT1,
const ElemType& aT2)
const {
return aT1.mStart < aT2.mStart;
}
};
};
// clang doesn't allow for this to be defined inline of IntervalSet.
template <
typename T>
IntervalSet<T>
Union(
const IntervalSet<T>& aIntervals1,
const IntervalSet<T>& aIntervals2) {
IntervalSet<T> intervals(aIntervals1);
intervals.
Union(aIntervals2);
return intervals;
}
template <
typename T>
IntervalSet<T> Intersection(
const IntervalSet<T>& aIntervals1,
const IntervalSet<T>& aIntervals2) {
IntervalSet<T> intersection(aIntervals1);
intersection.Intersection(aIntervals2);
return intersection;
}
}
// namespace mozilla::media
#endif // DOM_MEDIA_INTERVALS_H_
