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