Line data    Source code

       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 mp4_demuxer
      12             : {
      13             : 
      14             : template <typename T>
      15             : struct Interval
      16             : {
      17           0 :   Interval() : start(0), end(0) {}
      18           0 :   Interval(T aStart, T aEnd) : start(aStart), end(aEnd)
      19             :   {
      20           0 :     MOZ_ASSERT(aStart <= aEnd);
      21           0 :   }
      22           0 :   T Length() { return end - start; }
      23             :   Interval Intersection(const Interval& aOther) const
      24             :   {
      25             :     T s = start > aOther.start ? start : aOther.start;
      26             :     T e = end < aOther.end ? end : aOther.end;
      27             :     if (s > e) {
      28             :       return Interval();
      29             :     }
      30             :     return Interval(s, e);
      31             :   }
      32           0 :   bool Contains(const Interval& aOther) const
      33             :   {
      34           0 :     return aOther.start >= start && aOther.end <= end;
      35             :   }
      36             :   bool operator==(const Interval& aOther) const
      37             :   {
      38             :     return start == aOther.start && end == aOther.end;
      39             :   }
      40             :   bool operator!=(const Interval& aOther) const { return !(*this == aOther); }
      41           0 :   bool IsNull() const
      42             :   {
      43           0 :     return end == start;
      44             :   }
      45           0 :   Interval Extents(const Interval& aOther) const
      46             :   {
      47           0 :     if (IsNull()) {
      48           0 :       return aOther;
      49             :     }
      50           0 :     return Interval(std::min(start, aOther.start),
      51           0 :                     std::max(end, aOther.end));
      52             :   }
      53             : 
      54             :   T start;
      55             :   T end;
      56             : 
      57           0 :   static void SemiNormalAppend(nsTArray<Interval<T>>& aIntervals,
      58             :                                Interval<T> aInterval)
      59             :   {
      60           0 :     if (!aIntervals.IsEmpty() &&
      61           0 :         aIntervals.LastElement().end == aInterval.start) {
      62           0 :       aIntervals.LastElement().end = aInterval.end;
      63             :     } else {
      64           0 :       aIntervals.AppendElement(aInterval);
      65             :     }
      66           0 :   }
      67             : 
      68           0 :   static void Normalize(const nsTArray<Interval<T>>& aIntervals,
      69             :                         nsTArray<Interval<T>>* aNormalized)
      70             :   {
      71           0 :     if (!aNormalized || !aIntervals.Length()) {
      72           0 :       MOZ_ASSERT(aNormalized);
      73           0 :       return;
      74             :     }
      75           0 :     MOZ_ASSERT(aNormalized->IsEmpty());
      76             : 
      77           0 :     nsTArray<Interval<T>> sorted;
      78           0 :     sorted = aIntervals;
      79           0 :     sorted.Sort(Compare());
      80             : 
      81           0 :     Interval<T> current = sorted[0];
      82           0 :     for (size_t i = 1; i < sorted.Length(); i++) {
      83           0 :       MOZ_ASSERT(sorted[i].start <= sorted[i].end);
      84           0 :       if (current.Contains(sorted[i])) {
      85           0 :         continue;
      86             :       }
      87           0 :       if (current.end >= sorted[i].start) {
      88           0 :         current.end = sorted[i].end;
      89             :       } else {
      90           0 :         aNormalized->AppendElement(current);
      91           0 :         current = sorted[i];
      92             :       }
      93             :     }
      94           0 :     aNormalized->AppendElement(current);
      95             :   }
      96             : 
      97             :   static void Intersection(const nsTArray<Interval<T>>& a0,
      98             :                            const nsTArray<Interval<T>>& a1,
      99             :                            nsTArray<Interval<T>>* aIntersection)
     100             :   {
     101             :     MOZ_ASSERT(IsNormalized(a0));
     102             :     MOZ_ASSERT(IsNormalized(a1));
     103             :     size_t i0 = 0;
     104             :     size_t i1 = 0;
     105             :     while (i0 < a0.Length() && i1 < a1.Length()) {
     106             :       Interval i = a0[i0].Intersection(a1[i1]);
     107             :       if (i.Length()) {
     108             :         aIntersection->AppendElement(i);
     109             :       }
     110             :       if (a0[i0].end < a1[i1].end) {
     111             :         i0++;
     112             :         // Assert that the array is sorted
     113             :         MOZ_ASSERT(i0 == a0.Length() || a0[i0 - 1].start < a0[i0].start);
     114             :       } else {
     115             :         i1++;
     116             :         // Assert that the array is sorted
     117             :         MOZ_ASSERT(i1 == a1.Length() || a1[i1 - 1].start < a1[i1].start);
     118             :       }
     119             :     }
     120             :   }
     121             : 
     122             :   static bool IsNormalized(const nsTArray<Interval<T>>& aIntervals)
     123             :   {
     124             :     for (size_t i = 1; i < aIntervals.Length(); i++) {
     125             :       if (aIntervals[i - 1].end >= aIntervals[i].start) {
     126             :         return false;
     127             :       }
     128             :     }
     129             :     return true;
     130             :   }
     131             : 
     132             :   struct Compare
     133             :   {
     134           0 :     bool Equals(const Interval<T>& a0, const Interval<T>& a1) const
     135             :     {
     136           0 :       return a0.start == a1.start && a0.end == a1.end;
     137             :     }
     138             : 
     139           0 :     bool LessThan(const Interval<T>& a0, const Interval<T>& a1) const
     140             :     {
     141           0 :       return a0.start < a1.start;
     142             :     }
     143             :   };
     144             : };
     145             : }
     146             : 
     147             : #endif