Bug 1163445: Part3. Add IntervalSet::Contains(Interval) method. r=mattwoodrow
authorJean-Yves Avenard <jyavenard@mozilla.com>
Mon, 18 May 2015 16:13:20 +1000
changeset 244286 7cc62c82bb10460da898ddcc7bd904b6838c5440
parent 244285 d71d9f13a37d709817041b66e1fd782084a6de4c
child 244287 0fe9422de17bd3204764ee347915480045641e06
push id59889
push userjyavenard@mozilla.com
push dateMon, 18 May 2015 06:18:59 +0000
treeherdermozilla-inbound@24a7f0fda98b [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmattwoodrow
bugs1163445
milestone41.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1163445: Part3. Add IntervalSet::Contains(Interval) method. r=mattwoodrow
dom/media/Intervals.h
dom/media/gtest/TestIntervalSet.cpp
--- a/dom/media/Intervals.h
+++ b/dom/media/Intervals.h
@@ -468,26 +468,39 @@ public:
 
     if (aExists) {
       return mIntervals[aIndex].mEnd;
     } else {
       return T();
     }
   }
 
-  bool Contains(const T& aX) {
+  bool Contains(const ElemType& aInterval) const {
+    for (const auto& interval : mIntervals) {
+      if (aInterval.LeftOf(interval)) {
+        // Will never succeed.
+        return false;
+      }
+      if (interval.Contains(aInterval)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  bool Contains(const T& aX) const {
     for (const auto& interval : mIntervals) {
       if (interval.Contains(aX)) {
         return true;
       }
     }
     return false;
   }
 
-  bool ContainsStrict(const T& aX) {
+  bool ContainsStrict(const T& aX) const {
     for (const auto& interval : mIntervals) {
       if (interval.ContainsStrict(aX)) {
         return true;
       }
     }
     return false;
   }
 
--- a/dom/media/gtest/TestIntervalSet.cpp
+++ b/dom/media/gtest/TestIntervalSet.cpp
@@ -253,16 +253,49 @@ TEST(IntervalSet, IntersectionUnorderedN
   i1.Add(IntInterval(7, 15));
   i1.Add(IntInterval(10, 27));
   i1.Add(IntInterval(45, 50));
   i1.Add(IntInterval(53, 57));
 
   GeneratePermutations(i0, i1);
 }
 
+TEST(IntervalSet, IntersectionNonNormalizedInterval)
+{
+  media::IntervalSet<int> i0;
+  i0 += IntInterval(5, 10);
+  i0 += IntInterval(8, 25);
+  i0 += IntInterval(30, 60);
+
+  media::Interval<int> i1(9, 15);
+  i0.Intersection(i1);
+  EXPECT_EQ(1u, i0.Length());
+  EXPECT_EQ(i0[0].mStart, i1.mStart);
+  EXPECT_EQ(i0[0].mEnd, i1.mEnd);
+}
+
+TEST(IntervalSet, IntersectionUnorderedNonNormalizedInterval)
+{
+  media::IntervalSet<int> i0;
+  i0 += IntInterval(1, 3);
+  i0 += IntInterval(1, 10);
+  i0 += IntInterval(9, 12);
+  i0 += IntInterval(12, 15);
+  i0 += IntInterval(8, 25);
+  i0 += IntInterval(30, 60);
+  i0 += IntInterval(5, 10);
+  i0 += IntInterval(30, 60);
+
+  media::Interval<int> i1(9, 15);
+  i0.Intersection(i1);
+  EXPECT_EQ(1u, i0.Length());
+  EXPECT_EQ(i0[0].mStart, i1.mStart);
+  EXPECT_EQ(i0[0].mEnd, i1.mEnd);
+}
+
 static media::IntervalSet<int> Duplicate(const media::IntervalSet<int>& aValue)
 {
   media::IntervalSet<int> value(aValue);
   return value;
 }
 
 TEST(IntervalSet, Normalize)
 {
@@ -293,16 +326,91 @@ TEST(IntervalSet, Normalize)
                             media::TimeUnit::FromSeconds(3.203333));
   ti += media::TimeInterval(media::TimeUnit::FromSeconds(3.203366),
                             media::TimeUnit::FromSeconds(10.010065));
   EXPECT_EQ(2u, ti.Length());
   ti += media::TimeInterval(ti.Start(0), ti.End(0), media::TimeUnit::FromMicroseconds(35000));
   EXPECT_EQ(1u, ti.Length());
 }
 
+TEST(IntervalSet, ContainValue)
+{
+  media::IntervalSet<int> i0;
+  i0 += IntInterval(0, 10);
+  i0 += IntInterval(15, 20);
+  i0 += IntInterval(30, 50);
+  EXPECT_TRUE(i0.Contains(0)); // start is inclusive.
+  EXPECT_TRUE(i0.Contains(17));
+  EXPECT_FALSE(i0.Contains(20)); // end boundary is exclusive.
+  EXPECT_FALSE(i0.Contains(25));
+}
+
+TEST(IntervalSet, ContainValueWithFuzz)
+{
+  media::IntervalSet<int> i0;
+  i0 += IntInterval(0, 10);
+  i0 += IntInterval(15, 20, 1);
+  i0 += IntInterval(30, 50);
+  EXPECT_TRUE(i0.Contains(0)); // start is inclusive.
+  EXPECT_TRUE(i0.Contains(17));
+  EXPECT_TRUE(i0.Contains(20)); // end boundary is exclusive but we have a fuzz of 1.
+  EXPECT_FALSE(i0.Contains(25));
+}
+
+TEST(IntervalSet, ContainInterval)
+{
+  media::IntervalSet<int> i0;
+  i0 += IntInterval(0, 10);
+  i0 += IntInterval(15, 20);
+  i0 += IntInterval(30, 50);
+  EXPECT_TRUE(i0.Contains(IntInterval(2, 8)));
+  EXPECT_TRUE(i0.Contains(IntInterval(31, 50)));
+  EXPECT_TRUE(i0.Contains(IntInterval(0, 10)));
+  EXPECT_FALSE(i0.Contains(IntInterval(0, 11)));
+  EXPECT_TRUE(i0.Contains(IntInterval(0, 5)));
+  EXPECT_FALSE(i0.Contains(IntInterval(8, 15)));
+  EXPECT_FALSE(i0.Contains(IntInterval(15, 30)));
+  EXPECT_FALSE(i0.Contains(IntInterval(30, 55)));
+}
+
+TEST(IntervalSet, ContainIntervalWithFuzz)
+{
+  media::IntervalSet<int> i0;
+  i0 += IntInterval(0, 10);
+  i0 += IntInterval(15, 20);
+  i0 += IntInterval(30, 50);
+  EXPECT_TRUE(i0.Contains(IntInterval(2, 8)));
+  EXPECT_TRUE(i0.Contains(IntInterval(31, 50)));
+  EXPECT_TRUE(i0.Contains(IntInterval(0, 11, 1)));
+  EXPECT_TRUE(i0.Contains(IntInterval(0, 5)));
+  EXPECT_FALSE(i0.Contains(IntInterval(8, 15)));
+  EXPECT_FALSE(i0.Contains(IntInterval(15, 21)));
+  EXPECT_FALSE(i0.Contains(IntInterval(15, 30)));
+  EXPECT_FALSE(i0.Contains(IntInterval(30, 55)));
+
+  media::IntervalSet<int> i1;
+  i1 += IntInterval(0, 10, 1);
+  i1 += IntInterval(15, 20, 1);
+  i1 += IntInterval(30, 50, 1);
+  EXPECT_TRUE(i1.Contains(IntInterval(2, 8)));
+  EXPECT_TRUE(i1.Contains(IntInterval(29, 51)));
+  EXPECT_TRUE(i1.Contains(IntInterval(0, 11, 1)));
+  EXPECT_TRUE(i1.Contains(IntInterval(15, 21)));
+}
+
+TEST(IntervalSet, Span)
+{
+  IntInterval i0(0,10);
+  IntInterval i1(20,30);
+  IntInterval i{i0.Span(i1)};
+
+  EXPECT_EQ(i.mStart, 0);
+  EXPECT_EQ(i.mEnd, 30);
+}
+
 TEST(IntervalSet, Union)
 {
   media::IntervalSet<int> i0;
   i0 += IntInterval(5, 10);
   i0 += IntInterval(20, 25);
   i0 += IntInterval(40, 60);
 
   media::IntervalSet<int> i1;
@@ -369,38 +477,44 @@ TEST(IntervalSet, NormalizeFuzz)
 }
 
 TEST(IntervalSet, UnionFuzz)
 {
   media::IntervalSet<int> i0;
   i0 += IntInterval(5, 10, 1);
   i0 += IntInterval(11, 25, 0);
   i0 += IntInterval(40, 60, 1);
+  EXPECT_EQ(2u, i0.Length());
+  EXPECT_EQ(5, i0[0].mStart);
+  EXPECT_EQ(25, i0[0].mEnd);
+  EXPECT_EQ(40, i0[1].mStart);
+  EXPECT_EQ(60, i0[1].mEnd);
 
   media::IntervalSet<int> i1;
   i1.Add(IntInterval(7, 15, 1));
   i1.Add(IntInterval(16, 27, 1));
   i1.Add(IntInterval(45, 50, 1));
   i1.Add(IntInterval(53, 57, 1));
+  EXPECT_EQ(3u, i1.Length());
+  EXPECT_EQ(7, i1[0].mStart);
+  EXPECT_EQ(27, i1[0].mEnd);
+  EXPECT_EQ(45, i1[1].mStart);
+  EXPECT_EQ(50, i1[1].mEnd);
+  EXPECT_EQ(53, i1[2].mStart);
+  EXPECT_EQ(57, i1[2].mEnd);
 
   media::IntervalSet<int> i = media::Union(i0, i1);
 
   EXPECT_EQ(2u, i.Length());
 
   EXPECT_EQ(5, i[0].mStart);
   EXPECT_EQ(27, i[0].mEnd);
 
   EXPECT_EQ(40, i[1].mStart);
   EXPECT_EQ(60, i[1].mEnd);
-
-  EXPECT_EQ(2u, i0.Length());
-  EXPECT_EQ(5, i0[0].mStart);
-  EXPECT_EQ(25, i0[0].mEnd);
-  EXPECT_EQ(40, i0[1].mStart);
-  EXPECT_EQ(60, i0[1].mEnd);
 }
 
 TEST(IntervalSet, Contiguous)
 {
   EXPECT_FALSE(IntInterval(5, 10).Contiguous(IntInterval(11, 25)));
   EXPECT_TRUE(IntInterval(5, 10).Contiguous(IntInterval(10, 25)));
   EXPECT_TRUE(IntInterval(5, 10, 1).Contiguous(IntInterval(11, 25)));
   EXPECT_TRUE(IntInterval(5, 10).Contiguous(IntInterval(11, 25, 1)));