dom/media/mp4/MP4Interval.h

   1 /* This Source Code Form is subject to the terms of the Mozilla Public
   2  * License, v. 2.0. If a copy of the MPL was not distributed with this
   3  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   4
   5 #ifndef INTERVAL_H_
   6 #define INTERVAL_H_
   7
   8 #include "nsTArray.h"
   9 #include <algorithm>
  10 #include <nsString.h>
  11
  12 namespace mozilla {
  13
  14 template <typename T>
  15 struct MP4Interval {
  16   MP4Interval() : start{}, end{} {}
  17   MP4Interval(T aStart, T aEnd) : start(aStart), end(aEnd) {
  18     MOZ_ASSERT(aStart <= aEnd);
  19   }
  20   T Length() { return end - start; }
  21   MP4Interval Intersection(const MP4Interval& aOther) const {
  22     T s = start > aOther.start ? start : aOther.start;
  23     T e = end < aOther.end ? end : aOther.end;
  24     if (s > e) {
  25       return MP4Interval();
  26     }
  27     return MP4Interval(s, e);
  28   }
  29   bool Contains(const MP4Interval& aOther) const {
  30     return aOther.start >= start && aOther.end <= end;
  31   }
  32   bool operator==(const MP4Interval& aOther) const {
  33     return start == aOther.start && end == aOther.end;
  34   }
  35   bool operator!=(const MP4Interval& aOther) const {
  36     return !(*this == aOther);
  37   }
  38   bool IsNull() const { return end == start; }
  39   MP4Interval Extents(const MP4Interval& aOther) const {
  40     if (IsNull()) {
  41       return aOther;
  42     }
  43     return MP4Interval(std::min(start, aOther.start),
  44                        std::max(end, aOther.end));
  45   }
  46
  47   T start;
  48   T end;
  49
  50   nsCString ToString() {
  51     return nsPrintfCString("[%s, %s]", start.ToString().get(),
  52                            end.ToString().get());
  53   }
  54
  55   static void SemiNormalAppend(nsTArray<MP4Interval<T>>& aIntervals,
  56                                MP4Interval<T> aMP4Interval) {
  57     if (!aIntervals.IsEmpty() &&
  58         aIntervals.LastElement().end == aMP4Interval.start) {
  59       aIntervals.LastElement().end = aMP4Interval.end;
  60     } else {
  61       aIntervals.AppendElement(aMP4Interval);
  62     }
  63   }
  64
  65   static void Normalize(const nsTArray<MP4Interval<T>>& aIntervals,
  66                         nsTArray<MP4Interval<T>>* aNormalized) {
  67     if (!aNormalized || !aIntervals.Length()) {
  68       MOZ_ASSERT(aNormalized);
  69       return;
  70     }
  71     MOZ_ASSERT(aNormalized->IsEmpty());
  72
  73     nsTArray<MP4Interval<T>> sorted = aIntervals.Clone();
  74     sorted.Sort(Compare());
  75
  76     MP4Interval<T> current = sorted[0];
  77     for (size_t i = 1; i < sorted.Length(); i++) {
  78       MOZ_ASSERT(sorted[i].start <= sorted[i].end);
  79       if (current.Contains(sorted[i])) {
  80         continue;
  81       }
  82       if (current.end >= sorted[i].start) {
  83         current.end = sorted[i].end;
  84       } else {
  85         aNormalized->AppendElement(current);
  86         current = sorted[i];
  87       }
  88     }
  89     aNormalized->AppendElement(current);
  90   }
  91
  92   static void Intersection(const nsTArray<MP4Interval<T>>& a0,
  93                            const nsTArray<MP4Interval<T>>& a1,
  94                            nsTArray<MP4Interval<T>>* aIntersection) {
  95     MOZ_ASSERT(IsNormalized(a0));
  96     MOZ_ASSERT(IsNormalized(a1));
  97     size_t i0 = 0;
  98     size_t i1 = 0;
  99     while (i0 < a0.Length() && i1 < a1.Length()) {
 100       MP4Interval i = a0[i0].Intersection(a1[i1]);
 101       if (i.Length()) {
 102         aIntersection->AppendElement(i);
 103       }
 104       if (a0[i0].end < a1[i1].end) {
 105         i0++;
 106         // Assert that the array is sorted
 107         MOZ_ASSERT(i0 == a0.Length() || a0[i0 - 1].start < a0[i0].start);
 108       } else {
 109         i1++;
 110         // Assert that the array is sorted
 111         MOZ_ASSERT(i1 == a1.Length() || a1[i1 - 1].start < a1[i1].start);
 112       }
 113     }
 114   }
 115
 116   static bool IsNormalized(const nsTArray<MP4Interval<T>>& aIntervals) {
 117     for (size_t i = 1; i < aIntervals.Length(); i++) {
 118       if (aIntervals[i - 1].end >= aIntervals[i].start) {
 119         return false;
 120       }
 121     }
 122     return true;
 123   }
 124
 125   struct Compare {
 126     bool Equals(const MP4Interval<T>& a0, const MP4Interval<T>& a1) const {
 127       return a0.start == a1.start && a0.end == a1.end;
 128     }
 129
 130     bool LessThan(const MP4Interval<T>& a0, const MP4Interval<T>& a1) const {
 131       return a0.start < a1.start;
 132     }
 133   };
 134 };
 135 }  // namespace mozilla
 136
 137 #endif