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 11 namespace mozilla { 12 13 template <typename T> 14 struct MP4Interval { MP4IntervalMP4Interval15 MP4Interval() : start(0), end(0) {} MP4IntervalMP4Interval16 MP4Interval(T aStart, T aEnd) : start(aStart), end(aEnd) { 17 MOZ_ASSERT(aStart <= aEnd); 18 } LengthMP4Interval19 T Length() { return end - start; } IntersectionMP4Interval20 MP4Interval Intersection(const MP4Interval& aOther) const { 21 T s = start > aOther.start ? start : aOther.start; 22 T e = end < aOther.end ? end : aOther.end; 23 if (s > e) { 24 return MP4Interval(); 25 } 26 return MP4Interval(s, e); 27 } ContainsMP4Interval28 bool Contains(const MP4Interval& aOther) const { 29 return aOther.start >= start && aOther.end <= end; 30 } 31 bool operator==(const MP4Interval& aOther) const { 32 return start == aOther.start && end == aOther.end; 33 } 34 bool operator!=(const MP4Interval& aOther) const { 35 return !(*this == aOther); 36 } IsNullMP4Interval37 bool IsNull() const { return end == start; } ExtentsMP4Interval38 MP4Interval Extents(const MP4Interval& aOther) const { 39 if (IsNull()) { 40 return aOther; 41 } 42 return MP4Interval(std::min(start, aOther.start), 43 std::max(end, aOther.end)); 44 } 45 46 T start; 47 T end; 48 SemiNormalAppendMP4Interval49 static void SemiNormalAppend(nsTArray<MP4Interval<T>>& aIntervals, 50 MP4Interval<T> aMP4Interval) { 51 if (!aIntervals.IsEmpty() && 52 aIntervals.LastElement().end == aMP4Interval.start) { 53 aIntervals.LastElement().end = aMP4Interval.end; 54 } else { 55 aIntervals.AppendElement(aMP4Interval); 56 } 57 } 58 NormalizeMP4Interval59 static void Normalize(const nsTArray<MP4Interval<T>>& aIntervals, 60 nsTArray<MP4Interval<T>>* aNormalized) { 61 if (!aNormalized || !aIntervals.Length()) { 62 MOZ_ASSERT(aNormalized); 63 return; 64 } 65 MOZ_ASSERT(aNormalized->IsEmpty()); 66 67 nsTArray<MP4Interval<T>> sorted = aIntervals.Clone(); 68 sorted.Sort(Compare()); 69 70 MP4Interval<T> current = sorted[0]; 71 for (size_t i = 1; i < sorted.Length(); i++) { 72 MOZ_ASSERT(sorted[i].start <= sorted[i].end); 73 if (current.Contains(sorted[i])) { 74 continue; 75 } 76 if (current.end >= sorted[i].start) { 77 current.end = sorted[i].end; 78 } else { 79 aNormalized->AppendElement(current); 80 current = sorted[i]; 81 } 82 } 83 aNormalized->AppendElement(current); 84 } 85 IntersectionMP4Interval86 static void Intersection(const nsTArray<MP4Interval<T>>& a0, 87 const nsTArray<MP4Interval<T>>& a1, 88 nsTArray<MP4Interval<T>>* aIntersection) { 89 MOZ_ASSERT(IsNormalized(a0)); 90 MOZ_ASSERT(IsNormalized(a1)); 91 size_t i0 = 0; 92 size_t i1 = 0; 93 while (i0 < a0.Length() && i1 < a1.Length()) { 94 MP4Interval i = a0[i0].Intersection(a1[i1]); 95 if (i.Length()) { 96 aIntersection->AppendElement(i); 97 } 98 if (a0[i0].end < a1[i1].end) { 99 i0++; 100 // Assert that the array is sorted 101 MOZ_ASSERT(i0 == a0.Length() || a0[i0 - 1].start < a0[i0].start); 102 } else { 103 i1++; 104 // Assert that the array is sorted 105 MOZ_ASSERT(i1 == a1.Length() || a1[i1 - 1].start < a1[i1].start); 106 } 107 } 108 } 109 IsNormalizedMP4Interval110 static bool IsNormalized(const nsTArray<MP4Interval<T>>& aIntervals) { 111 for (size_t i = 1; i < aIntervals.Length(); i++) { 112 if (aIntervals[i - 1].end >= aIntervals[i].start) { 113 return false; 114 } 115 } 116 return true; 117 } 118 119 struct Compare { EqualsMP4Interval::Compare120 bool Equals(const MP4Interval<T>& a0, const MP4Interval<T>& a1) const { 121 return a0.start == a1.start && a0.end == a1.end; 122 } 123 LessThanMP4Interval::Compare124 bool LessThan(const MP4Interval<T>& a0, const MP4Interval<T>& a1) const { 125 return a0.start < a1.start; 126 } 127 }; 128 }; 129 } // namespace mozilla 130 131 #endif 132