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