dom/media/Intervals.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef DOM_MEDIA_INTERVALS_H_
   8 #define DOM_MEDIA_INTERVALS_H_
   9
  10 #include <algorithm>
  11 #include <type_traits>
  12
  13 #include "nsTArray.h"
  14 #include "nsString.h"
  15 #include "nsPrintfCString.h"
  16
  17 // Specialization for nsTArray CopyChooser.
  18 namespace mozilla::media {
  19 template <class T>
  20 class IntervalSet;
  21 class TimeUnit;
  22 }  // namespace mozilla::media
  23
  24 template <class E>
  25 struct nsTArray_RelocationStrategy<mozilla::media::IntervalSet<E>> {
  26   typedef nsTArray_RelocateUsingMoveConstructor<mozilla::media::IntervalSet<E>>
  27       Type;
  28 };
  29
  30 namespace mozilla::media {
  31
  32 /* Interval defines an interval between two points. Unlike a traditional
  33    interval [A,B] where A <= x <= B, the upper boundary B is exclusive: A <= x <
  34    B (e.g [A,B[ or [A,B) depending on where you're living) It provides basic
  35    interval arithmetic and fuzzy edges. The type T must provides a default
  36    constructor and +, -, <, <= and == operators.
  37  */
  38 template <typename T>
  39 class Interval {
  40  public:
  41   typedef Interval<T> SelfType;
  42
  43   Interval() : mStart(T()), mEnd(T()), mFuzz(T()) {}
  44
  45   template <typename StartArg, typename EndArg>
  46   Interval(StartArg&& aStart, EndArg&& aEnd)
  47       : mStart(aStart), mEnd(aEnd), mFuzz() {
  48     MOZ_DIAGNOSTIC_ASSERT(mStart <= mEnd, "Invalid Interval");
  49   }
  50
  51   template <typename StartArg, typename EndArg, typename FuzzArg>
  52   Interval(StartArg&& aStart, EndArg&& aEnd, FuzzArg&& aFuzz)
  53       : mStart(aStart), mEnd(aEnd), mFuzz(aFuzz) {
  54     MOZ_DIAGNOSTIC_ASSERT(mStart <= mEnd, "Invalid Interval");
  55   }
  56
  57   Interval(const SelfType& aOther)
  58       : mStart(aOther.mStart), mEnd(aOther.mEnd), mFuzz(aOther.mFuzz) {}
  59
  60   Interval(SelfType&& aOther)
  61       : mStart(std::move(aOther.mStart)),
  62         mEnd(std::move(aOther.mEnd)),
  63         mFuzz(std::move(aOther.mFuzz)) {}
  64
  65   SelfType& operator=(const SelfType& aOther) {
  66     mStart = aOther.mStart;
  67     mEnd = aOther.mEnd;
  68     mFuzz = aOther.mFuzz;
  69     return *this;
  70   }
  71
  72   SelfType& operator=(SelfType&& aOther) {
  73     MOZ_ASSERT(&aOther != this, "self-moves are prohibited");
  74     this->~Interval();
  75     new (this) Interval(std::move(aOther));
  76     return *this;
  77   }
  78
  79   // Basic interval arithmetic operator definition.
  80   SelfType operator+(const SelfType& aOther) const {
  81     return SelfType(mStart + aOther.mStart, mEnd + aOther.mEnd,
  82                     mFuzz + aOther.mFuzz);
  83   }
  84
  85   SelfType operator+(const T& aVal) const {
  86     return SelfType(mStart + aVal, mEnd + aVal, mFuzz);
  87   }
  88
  89   SelfType operator-(const SelfType& aOther) const {
  90     return SelfType(mStart - aOther.mEnd, mEnd - aOther.mStart,
  91                     mFuzz + aOther.mFuzz);
  92   }
  93
  94   SelfType operator-(const T& aVal) const {
  95     return SelfType(mStart - aVal, mEnd - aVal, mFuzz);
  96   }
  97
  98   SelfType& operator+=(const SelfType& aOther) {
  99     mStart += aOther.mStart;
 100     mEnd += aOther.mEnd;
 101     mFuzz += aOther.mFuzz;
 102     return *this;
 103   }
 104
 105   SelfType& operator+=(const T& aVal) {
 106     mStart += aVal;
 107     mEnd += aVal;
 108     return *this;
 109   }
 110
 111   SelfType& operator-=(const SelfType& aOther) {
 112     mStart -= aOther.mStart;
 113     mEnd -= aOther.mEnd;
 114     mFuzz += aOther.mFuzz;
 115     return *this;
 116   }
 117
 118   SelfType& operator-=(const T& aVal) {
 119     mStart -= aVal;
 120     mEnd -= aVal;
 121     return *this;
 122   }
 123
 124   bool operator==(const SelfType& aOther) const {
 125     return mStart == aOther.mStart && mEnd == aOther.mEnd;
 126   }
 127
 128   bool operator!=(const SelfType& aOther) const { return !(*this == aOther); }
 129
 130   bool Contains(const T& aX) const {
 131     return mStart - mFuzz <= aX && aX < mEnd + mFuzz;
 132   }
 133
 134   bool ContainsStrict(const T& aX) const { return mStart <= aX && aX < mEnd; }
 135
 136   bool ContainsWithStrictEnd(const T& aX) const {
 137     return mStart - mFuzz <= aX && aX < mEnd;
 138   }
 139
 140   bool Contains(const SelfType& aOther) const {
 141     return (mStart - mFuzz <= aOther.mStart + aOther.mFuzz) &&
 142            (aOther.mEnd - aOther.mFuzz <= mEnd + mFuzz);
 143   }
 144
 145   bool ContainsStrict(const SelfType& aOther) const {
 146     return mStart <= aOther.mStart && aOther.mEnd <= mEnd;
 147   }
 148
 149   bool ContainsWithStrictEnd(const SelfType& aOther) const {
 150     return (mStart - mFuzz <= aOther.mStart + aOther.mFuzz) &&
 151            aOther.mEnd <= mEnd;
 152   }
 153
 154   bool Intersects(const SelfType& aOther) const {
 155     return (mStart - mFuzz < aOther.mEnd + aOther.mFuzz) &&
 156            (aOther.mStart - aOther.mFuzz < mEnd + mFuzz);
 157   }
 158
 159   bool IntersectsStrict(const SelfType& aOther) const {
 160     return mStart < aOther.mEnd && aOther.mStart < mEnd;
 161   }
 162
 163   // Same as Intersects, but including the boundaries.
 164   bool Touches(const SelfType& aOther) const {
 165     return (mStart - mFuzz <= aOther.mEnd + aOther.mFuzz) &&
 166            (aOther.mStart - aOther.mFuzz <= mEnd + mFuzz);
 167   }
 168
 169   // Returns true if aOther is strictly to the right of this and contiguous.
 170   // This operation isn't commutative.
 171   bool Contiguous(const SelfType& aOther) const {
 172     return mEnd <= aOther.mStart &&
 173            aOther.mStart - mEnd <= mFuzz + aOther.mFuzz;
 174   }
 175
 176   bool RightOf(const SelfType& aOther) const {
 177     return aOther.mEnd - aOther.mFuzz <= mStart + mFuzz;
 178   }
 179
 180   bool LeftOf(const SelfType& aOther) const {
 181     return mEnd - mFuzz <= aOther.mStart + aOther.mFuzz;
 182   }
 183
 184   SelfType Span(const SelfType& aOther) const {
 185     if (IsEmpty()) {
 186       return aOther;
 187     }
 188     SelfType result(*this);
 189     if (aOther.mStart < mStart) {
 190       result.mStart = aOther.mStart;
 191     }
 192     if (mEnd < aOther.mEnd) {
 193       result.mEnd = aOther.mEnd;
 194     }
 195     if (mFuzz < aOther.mFuzz) {
 196       result.mFuzz = aOther.mFuzz;
 197     }
 198     return result;
 199   }
 200
 201   SelfType Intersection(const SelfType& aOther) const {
 202     const T& s = std::max(mStart, aOther.mStart);
 203     const T& e = std::min(mEnd, aOther.mEnd);
 204     const T& f = std::max(mFuzz, aOther.mFuzz);
 205     if (s < e) {
 206       return SelfType(s, e, f);
 207     }
 208     // Return an empty interval.
 209     return SelfType();
 210   }
 211
 212   T Length() const { return mEnd - mStart; }
 213
 214   bool IsEmpty() const { return mStart == mEnd; }
 215
 216   void SetFuzz(const T& aFuzz) { mFuzz = aFuzz; }
 217
 218   // Returns true if the two intervals intersect with this being on the right
 219   // of aOther
 220   bool TouchesOnRight(const SelfType& aOther) const {
 221     return aOther.mStart <= mStart &&
 222            (mStart - mFuzz <= aOther.mEnd + aOther.mFuzz) &&
 223            (aOther.mStart - aOther.mFuzz <= mEnd + mFuzz);
 224   }
 225
 226   // Returns true if the two intervals intersect with this being on the right
 227   // of aOther, ignoring fuzz.
 228   bool TouchesOnRightStrict(const SelfType& aOther) const {
 229     return aOther.mStart <= mStart && mStart <= aOther.mEnd;
 230   }
 231
 232   nsCString ToString() const {
 233     if constexpr (std::is_same_v<T, TimeUnit>) {
 234       return nsPrintfCString("[%s, %s](%s)", mStart.ToString().get(),
 235                              mEnd.ToString().get(), mFuzz.ToString().get());
 236     } else if constexpr (std::is_same_v<T, double>) {
 237       return nsPrintfCString("[%lf, %lf](%lf)", mStart, mEnd, mFuzz);
 238     }
 239   }
 240
 241   T mStart;
 242   T mEnd;
 243   T mFuzz;
 244 };
 245
 246 // An IntervalSet in a collection of Intervals. The IntervalSet is always
 247 // normalized.
 248 template <typename T>
 249 class IntervalSet {
 250  public:
 251   typedef IntervalSet<T> SelfType;
 252   typedef Interval<T> ElemType;
 253   typedef AutoTArray<ElemType, 4> ContainerType;
 254   typedef typename ContainerType::index_type IndexType;
 255
 256   IntervalSet() = default;
 257   virtual ~IntervalSet() = default;
 258
 259   IntervalSet(const SelfType& aOther) : mIntervals(aOther.mIntervals.Clone()) {}
 260
 261   IntervalSet(SelfType&& aOther) {
 262     mIntervals.AppendElements(std::move(aOther.mIntervals));
 263   }
 264
 265   explicit IntervalSet(const ElemType& aOther) {
 266     if (!aOther.IsEmpty()) {
 267       mIntervals.AppendElement(aOther);
 268     }
 269   }
 270
 271   explicit IntervalSet(ElemType&& aOther) {
 272     if (!aOther.IsEmpty()) {
 273       mIntervals.AppendElement(std::move(aOther));
 274     }
 275   }
 276
 277   bool operator==(const SelfType& aOther) const {
 278     return mIntervals == aOther.mIntervals;
 279   }
 280
 281   bool operator!=(const SelfType& aOther) const {
 282     return mIntervals != aOther.mIntervals;
 283   }
 284
 285   SelfType& operator=(const SelfType& aOther) {
 286     mIntervals = aOther.mIntervals.Clone();
 287     return *this;
 288   }
 289
 290   SelfType& operator=(SelfType&& aOther) {
 291     MOZ_ASSERT(&aOther != this, "self-moves are prohibited");
 292     this->~IntervalSet();
 293     new (this) IntervalSet(std::move(aOther));
 294     return *this;
 295   }
 296
 297   SelfType& operator=(const ElemType& aInterval) {
 298     mIntervals.Clear();
 299     if (!aInterval.IsEmpty()) {
 300       mIntervals.AppendElement(aInterval);
 301     }
 302     return *this;
 303   }
 304
 305   SelfType& operator=(ElemType&& aInterval) {
 306     mIntervals.Clear();
 307     if (!aInterval.IsEmpty()) {
 308       mIntervals.AppendElement(std::move(aInterval));
 309     }
 310     return *this;
 311   }
 312
 313   SelfType& Add(const SelfType& aIntervals) {
 314     if (aIntervals.mIntervals.Length() == 1) {
 315       Add(aIntervals.mIntervals[0]);
 316     } else {
 317       mIntervals.AppendElements(aIntervals.mIntervals);
 318       Normalize();
 319     }
 320     return *this;
 321   }
 322
 323   SelfType& Add(const ElemType& aInterval) {
 324     if (aInterval.IsEmpty()) {
 325       return *this;
 326     }
 327     if (mIntervals.IsEmpty()) {
 328       mIntervals.AppendElement(aInterval);
 329       return *this;
 330     }
 331     ElemType& last = mIntervals.LastElement();
 332     if (aInterval.TouchesOnRight(last)) {
 333       last = last.Span(aInterval);
 334       return *this;
 335     }
 336     // Most of our actual usage is adding an interval that will be outside the
 337     // range. We can speed up normalization here.
 338     if (aInterval.RightOf(last)) {
 339       mIntervals.AppendElement(aInterval);
 340       return *this;
 341     }
 342
 343     ContainerType normalized;
 344     ElemType current(aInterval);
 345     IndexType i = 0;
 346     for (; i < mIntervals.Length(); i++) {
 347       ElemType& interval = mIntervals[i];
 348       if (current.Touches(interval)) {
 349         current = current.Span(interval);
 350       } else if (current.LeftOf(interval)) {
 351         break;
 352       } else {
 353         normalized.AppendElement(std::move(interval));
 354       }
 355     }
 356     normalized.AppendElement(std::move(current));
 357     for (; i < mIntervals.Length(); i++) {
 358       normalized.AppendElement(std::move(mIntervals[i]));
 359     }
 360     mIntervals.Clear();
 361     mIntervals.AppendElements(std::move(normalized));
 362
 363     return *this;
 364   }
 365
 366   SelfType& operator+=(const SelfType& aIntervals) {
 367     Add(aIntervals);
 368     return *this;
 369   }
 370
 371   SelfType& operator+=(const ElemType& aInterval) {
 372     Add(aInterval);
 373     return *this;
 374   }
 375
 376   SelfType operator+(const SelfType& aIntervals) const {
 377     SelfType intervals(*this);
 378     intervals.Add(aIntervals);
 379     return intervals;
 380   }
 381
 382   SelfType operator+(const ElemType& aInterval) const {
 383     SelfType intervals(*this);
 384     intervals.Add(aInterval);
 385     return intervals;
 386   }
 387
 388   friend SelfType operator+(const ElemType& aInterval,
 389                             const SelfType& aIntervals) {
 390     SelfType intervals;
 391     intervals.Add(aInterval);
 392     intervals.Add(aIntervals);
 393     return intervals;
 394   }
 395
 396   // Excludes an interval from an IntervalSet.
 397   SelfType& operator-=(const ElemType& aInterval) {
 398     if (aInterval.IsEmpty() || mIntervals.IsEmpty()) {
 399       return *this;
 400     }
 401     if (mIntervals.Length() == 1 &&
 402         mIntervals[0].TouchesOnRightStrict(aInterval)) {
 403       // Fast path when we're removing from the front of a set with a
 404       // single interval. This is common for the buffered time ranges
 405       // we see on Twitch.
 406       if (aInterval.mEnd >= mIntervals[0].mEnd) {
 407         mIntervals.RemoveElementAt(0);
 408       } else {
 409         mIntervals[0].mStart = aInterval.mEnd;
 410         mIntervals[0].mFuzz = std::max(mIntervals[0].mFuzz, aInterval.mFuzz);
 411       }
 412       return *this;
 413     }
 414
 415     // General case performed by inverting aInterval within the bounds of
 416     // mIntervals and then doing the intersection.
 417     T firstEnd = std::max(mIntervals[0].mStart, aInterval.mStart);
 418     T secondStart = std::min(mIntervals.LastElement().mEnd, aInterval.mEnd);
 419     ElemType startInterval(mIntervals[0].mStart, firstEnd);
 420     ElemType endInterval(secondStart, mIntervals.LastElement().mEnd);
 421     SelfType intervals(std::move(startInterval));
 422     intervals += std::move(endInterval);
 423     return Intersection(intervals);
 424   }
 425
 426   SelfType& operator-=(const SelfType& aIntervals) {
 427     for (const auto& interval : aIntervals.mIntervals) {
 428       *this -= interval;
 429     }
 430     return *this;
 431   }
 432
 433   SelfType operator-(const SelfType& aInterval) const {
 434     SelfType intervals(*this);
 435     intervals -= aInterval;
 436     return intervals;
 437   }
 438
 439   SelfType operator-(const ElemType& aInterval) const {
 440     SelfType intervals(*this);
 441     intervals -= aInterval;
 442     return intervals;
 443   }
 444
 445   // Mutate this IntervalSet to be the union of this and aOther.
 446   SelfType& Union(const SelfType& aOther) {
 447     Add(aOther);
 448     return *this;
 449   }
 450
 451   SelfType& Union(const ElemType& aInterval) {
 452     Add(aInterval);
 453     return *this;
 454   }
 455
 456   // Mutate this TimeRange to be the intersection of this and aOther.
 457   SelfType& Intersection(const SelfType& aOther) {
 458     ContainerType intersection;
 459
 460     // Ensure the intersection has enough capacity to store the upper bound on
 461     // the intersection size. This ensures that we don't spend time reallocating
 462     // the storage as we append, at the expense of extra memory.
 463     intersection.SetCapacity(std::max(aOther.Length(), mIntervals.Length()));
 464
 465     const ContainerType& other = aOther.mIntervals;
 466     IndexType i = 0, j = 0;
 467     for (; i < mIntervals.Length() && j < other.Length();) {
 468       if (mIntervals[i].IntersectsStrict(other[j])) {
 469         intersection.AppendElement(mIntervals[i].Intersection(other[j]));
 470       }
 471       if (mIntervals[i].mEnd < other[j].mEnd) {
 472         i++;
 473       } else {
 474         j++;
 475       }
 476     }
 477     mIntervals = std::move(intersection);
 478     return *this;
 479   }
 480
 481   SelfType& Intersection(const ElemType& aInterval) {
 482     SelfType intervals(aInterval);
 483     return Intersection(intervals);
 484   }
 485
 486   const ElemType& operator[](IndexType aIndex) const {
 487     return mIntervals[aIndex];
 488   }
 489
 490   // Returns the start boundary of the first interval. Or a default constructed
 491   // T if IntervalSet is empty (and aExists if provided will be set to false).
 492   T GetStart(bool* aExists = nullptr) const {
 493     bool exists = !mIntervals.IsEmpty();
 494
 495     if (aExists) {
 496       *aExists = exists;
 497     }
 498
 499     if (exists) {
 500       return mIntervals[0].mStart;
 501     } else {
 502       return T();
 503     }
 504   }
 505
 506   // Returns the end boundary of the last interval. Or a default constructed T
 507   // if IntervalSet is empty (and aExists if provided will be set to false).
 508   T GetEnd(bool* aExists = nullptr) const {
 509     bool exists = !mIntervals.IsEmpty();
 510     if (aExists) {
 511       *aExists = exists;
 512     }
 513
 514     if (exists) {
 515       return mIntervals.LastElement().mEnd;
 516     } else {
 517       return T();
 518     }
 519   }
 520
 521   IndexType Length() const { return mIntervals.Length(); }
 522
 523   bool IsEmpty() const { return mIntervals.IsEmpty(); }
 524
 525   T Start(IndexType aIndex) const { return mIntervals[aIndex].mStart; }
 526
 527   T Start(IndexType aIndex, bool& aExists) const {
 528     aExists = aIndex < mIntervals.Length();
 529
 530     if (aExists) {
 531       return mIntervals[aIndex].mStart;
 532     } else {
 533       return T();
 534     }
 535   }
 536
 537   T End(IndexType aIndex) const { return mIntervals[aIndex].mEnd; }
 538
 539   T End(IndexType aIndex, bool& aExists) const {
 540     aExists = aIndex < mIntervals.Length();
 541
 542     if (aExists) {
 543       return mIntervals[aIndex].mEnd;
 544     } else {
 545       return T();
 546     }
 547   }
 548
 549   bool Contains(const ElemType& aInterval) const {
 550     for (const auto& interval : mIntervals) {
 551       if (interval.Contains(aInterval)) {
 552         return true;
 553       }
 554     }
 555     return false;
 556   }
 557
 558   bool ContainsStrict(const ElemType& aInterval) const {
 559     for (const auto& interval : mIntervals) {
 560       if (interval.ContainsStrict(aInterval)) {
 561         return true;
 562       }
 563     }
 564     return false;
 565   }
 566
 567   bool Contains(const T& aX) const {
 568     for (const auto& interval : mIntervals) {
 569       if (interval.Contains(aX)) {
 570         return true;
 571       }
 572     }
 573     return false;
 574   }
 575
 576   bool ContainsStrict(const T& aX) const {
 577     for (const auto& interval : mIntervals) {
 578       if (interval.ContainsStrict(aX)) {
 579         return true;
 580       }
 581     }
 582     return false;
 583   }
 584
 585   bool ContainsWithStrictEnd(const T& aX) const {
 586     for (const auto& interval : mIntervals) {
 587       if (interval.ContainsWithStrictEnd(aX)) {
 588         return true;
 589       }
 590     }
 591     return false;
 592   }
 593
 594   bool ContainsWithStrictEnd(const ElemType& aInterval) const {
 595     for (const auto& interval : mIntervals) {
 596       if (interval.ContainsWithStrictEnd(aInterval)) {
 597         return true;
 598       }
 599     }
 600     return false;
 601   }
 602
 603   bool Intersects(const ElemType& aInterval) const {
 604     for (const auto& interval : mIntervals) {
 605       if (interval.Intersects(aInterval)) {
 606         return true;
 607       }
 608     }
 609     return false;
 610   }
 611
 612   bool IntersectsStrict(const ElemType& aInterval) const {
 613     for (const auto& interval : mIntervals) {
 614       if (interval.IntersectsStrict(aInterval)) {
 615         return true;
 616       }
 617     }
 618     return false;
 619   }
 620
 621   // Returns if there's any intersection between this and aOther.
 622   bool IntersectsStrict(const SelfType& aOther) const {
 623     const ContainerType& other = aOther.mIntervals;
 624     IndexType i = 0, j = 0;
 625     for (; i < mIntervals.Length() && j < other.Length();) {
 626       if (mIntervals[i].IntersectsStrict(other[j])) {
 627         return true;
 628       }
 629       if (mIntervals[i].mEnd < other[j].mEnd) {
 630         i++;
 631       } else {
 632         j++;
 633       }
 634     }
 635     return false;
 636   }
 637
 638   bool IntersectsWithStrictEnd(const ElemType& aInterval) const {
 639     for (const auto& interval : mIntervals) {
 640       if (interval.IntersectsWithStrictEnd(aInterval)) {
 641         return true;
 642       }
 643     }
 644     return false;
 645   }
 646
 647   // Shift all values by aOffset.
 648   SelfType& Shift(const T& aOffset) {
 649     for (auto& interval : mIntervals) {
 650       interval.mStart = interval.mStart + aOffset;
 651       interval.mEnd = interval.mEnd + aOffset;
 652     }
 653     return *this;
 654   }
 655
 656   void SetFuzz(const T& aFuzz) {
 657     for (auto& interval : mIntervals) {
 658       interval.SetFuzz(aFuzz);
 659     }
 660     MergeOverlappingIntervals();
 661   }
 662
 663   static const IndexType NoIndex = IndexType(-1);
 664
 665   IndexType Find(const T& aValue) const {
 666     for (IndexType i = 0; i < mIntervals.Length(); i++) {
 667       if (mIntervals[i].Contains(aValue)) {
 668         return i;
 669       }
 670     }
 671     return NoIndex;
 672   }
 673
 674   // Methods for range-based for loops.
 675   typename ContainerType::iterator begin() { return mIntervals.begin(); }
 676
 677   typename ContainerType::const_iterator begin() const {
 678     return mIntervals.begin();
 679   }
 680
 681   typename ContainerType::const_iterator cbegin() const {
 682     return mIntervals.cbegin();
 683   }
 684
 685   typename ContainerType::iterator end() { return mIntervals.end(); }
 686
 687   typename ContainerType::const_iterator end() const {
 688     return mIntervals.end();
 689   }
 690
 691   typename ContainerType::const_iterator cend() const {
 692     return mIntervals.cend();
 693   }
 694
 695   ElemType& LastInterval() {
 696     MOZ_ASSERT(!mIntervals.IsEmpty());
 697     return mIntervals.LastElement();
 698   }
 699
 700   const ElemType& LastInterval() const {
 701     MOZ_ASSERT(!mIntervals.IsEmpty());
 702     return mIntervals.LastElement();
 703   }
 704
 705   void Clear() { mIntervals.Clear(); }
 706
 707  protected:
 708   ContainerType mIntervals;
 709
 710  private:
 711   void Normalize() {
 712     if (mIntervals.Length() < 2) {
 713       return;
 714     }
 715     mIntervals.Sort(CompareIntervals());
 716     MergeOverlappingIntervals();
 717   }
 718
 719   void MergeOverlappingIntervals() {
 720     if (mIntervals.Length() < 2) {
 721       return;
 722     }
 723
 724     // This merges the intervals in place.
 725     IndexType read = 0;
 726     IndexType write = 0;
 727     while (read < mIntervals.Length()) {
 728       ElemType current(mIntervals[read]);
 729       read++;
 730       while (read < mIntervals.Length() && current.Touches(mIntervals[read])) {
 731         current = current.Span(mIntervals[read]);
 732         read++;
 733       }
 734       mIntervals[write] = current;
 735       write++;
 736     }
 737     mIntervals.SetLength(write);
 738   }
 739
 740   struct CompareIntervals {
 741     bool Equals(const ElemType& aT1, const ElemType& aT2) const {
 742       return aT1.mStart == aT2.mStart && aT1.mEnd == aT2.mEnd;
 743     }
 744
 745     bool LessThan(const ElemType& aT1, const ElemType& aT2) const {
 746       return aT1.mStart < aT2.mStart;
 747     }
 748   };
 749 };
 750
 751 // clang doesn't allow for this to be defined inline of IntervalSet.
 752 template <typename T>
 753 IntervalSet<T> Union(const IntervalSet<T>& aIntervals1,
 754                      const IntervalSet<T>& aIntervals2) {
 755   IntervalSet<T> intervals(aIntervals1);
 756   intervals.Union(aIntervals2);
 757   return intervals;
 758 }
 759
 760 template <typename T>
 761 IntervalSet<T> Intersection(const IntervalSet<T>& aIntervals1,
 762                             const IntervalSet<T>& aIntervals2) {
 763   IntervalSet<T> intersection(aIntervals1);
 764   intersection.Intersection(aIntervals2);
 765   return intersection;
 766 }
 767
 768 }  // namespace mozilla::media
 769
 770 #endif  // DOM_MEDIA_INTERVALS_H_