dom/media/Intervals.h

/* -*- 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 "nsTArray.h"

// Specialization for nsTArray CopyChooser.
namespace mozilla {
namespace media {
template <class T>
class IntervalSet;
}  // namespace media
}  // namespace mozilla

template <class E>
struct nsTArray_RelocationStrategy<mozilla::media::IntervalSet<E>> {
  typedef nsTArray_RelocateUsingMoveConstructor<mozilla::media::IntervalSet<E>>
      Type;
};

namespace mozilla {
namespace 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(std::forward<StartArg>(aStart)),
        mEnd(std::forward<EndArg>(aEnd)),
        mFuzz() {
    MOZ_DIAGNOSTIC_ASSERT(mStart <= mEnd, "Invalid Interval");
  }

  template <typename StartArg, typename EndArg, typename FuzzArg>
  Interval(StartArg&& aStart, EndArg&& aEnd, FuzzArg&& aFuzz)
      : mStart(std::forward<StartArg>(aStart)),
        mEnd(std::forward<EndArg>(aEnd)),
        mFuzz(std::forward<FuzzArg>(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;
  }

  T mStart;
  T mEnd;
  T mFuzz;

 private:
};

// 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::iterator end() { return mIntervals.end(); }

  typename ContainerType::const_iterator end() const {
    return mIntervals.end();
  }

  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 - aT1.mFuzz < aT2.mStart + aT2.mFuzz;
    }
  };
};

// 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 media
}  // namespace mozilla

#endif  // DOM_MEDIA_INTERVALS_H_