[pitivi: 12/28] gap.py, test_gap.py: check in findAllGaps() and unit test

[Edward Hervey <edwardrv src gnome org>]

commit 6b093798b597b60e318e17dd5ab2d432cf4d3457
Author: Brandon Lewis <brandon_lewis alum berkeley edu>
Date:   Thu Dec 3 18:39:07 2009 -0800

    gap.py, test_gap.py: check in findAllGaps() and unit test

 pitivi/timeline/gap.py |   21 +++++++++++++++
 tests/test_gap.py      |   66 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 87 insertions(+), 0 deletions(-)
---
diff --git a/pitivi/timeline/gap.py b/pitivi/timeline/gap.py
index 99f9d9b..c8b27b9 100644
--- a/pitivi/timeline/gap.py
+++ b/pitivi/timeline/gap.py
@@ -72,6 +72,27 @@ class Gap(object):
 
         return left_gap, right_gap
 
+    @classmethod
+    def findAllGaps(self, objs):
+        """Find all the gaps in a given set of objects: i.e. find all the
+        spans of time which are covered by no object in the given set"""
+        duration = 0
+        gaps = []
+        prev = None
+
+        # examine each object in order of increasing start time
+        for obj in sorted(objs, key=lambda x: x.start):
+            start = obj.start
+            end = obj.start + obj.duration
+
+            # only if the current object starts after the total timeline
+            # duration is a gap created.
+            if start > duration:
+                gaps.append(Gap(prev, obj, duration, start - duration))
+            duration = max(duration, end)
+            prev = obj
+        return gaps
+
     @property
     def duration(self):
         if self.left_object is None and self.right_object is None:
diff --git a/tests/test_gap.py b/tests/test_gap.py
index cff18a7..0006b62 100644
--- a/tests/test_gap.py
+++ b/tests/test_gap.py
@@ -156,3 +156,69 @@ class TestGap(TestCase):
         self.failUnlessEqual(left_gap.duration, 31 * gst.SECOND)
         self.failUnlessEqual(right_gap, invalid_gap)
 
+    def testFindAllGaps(self):
+
+        simple = (
+            (3 * gst.SECOND, 1 * gst.SECOND),
+            (1 * gst.SECOND, 1 * gst.SECOND)
+        )
+
+        objs = []
+        for start, duration in simple:
+            obj = self.makeTimelineObject()
+            obj.start = start
+            obj.duration = duration
+            objs.append(obj)
+
+        result = [(g.start, g.initial_duration) for g in
+            Gap.findAllGaps(objs)]
+
+        self.assertEquals(result, [
+            (0 * gst.SECOND, 1 * gst.SECOND),
+            (2 * gst.SECOND, 1 * gst.SECOND),
+        ])
+
+        complex = [
+            ( 1 * gst.SECOND, 2 * gst.SECOND),
+            ( 6 * gst.SECOND, 2 * gst.SECOND),
+            (10 * gst.SECOND, 2 * gst.SECOND),
+            ( 8 * gst.SECOND, 2 * gst.SECOND),
+            (14 * gst.SECOND, 1 * gst.SECOND),
+            ( 4 * gst.SECOND, 1 * gst.SECOND),
+        ]
+
+        objs = []
+        for start, duration in complex:
+            obj = self.makeTimelineObject()
+            obj.start = start
+            obj.duration = duration
+            objs.append(obj)
+
+        result = [(g.start, g.initial_duration) for g in
+            Gap.findAllGaps(objs)]
+
+        self.assertEquals(result, [
+            ( 0 * gst.SECOND, 1 * gst.SECOND),
+            ( 3 * gst.SECOND, 1 * gst.SECOND),
+            ( 5 * gst.SECOND, 1 * gst.SECOND),
+            (12 * gst.SECOND, 2 * gst.SECOND),
+        ])
+
+        complex.append((2 * gst.SECOND, 5 * gst.SECOND))
+
+        objs = []
+        for start, duration in complex:
+            obj = self.makeTimelineObject()
+            obj.start = start
+            obj.duration = duration
+            objs.append(obj)
+
+        result = [(g.start, g.initial_duration) for g in
+            Gap.findAllGaps(objs)]
+
+        self.assertEquals(result, [
+            ( 0 * gst.SECOND, 1 * gst.SECOND),
+            (12 * gst.SECOND, 2 * gst.SECOND),
+        ])
+
+