[pitivi] Add code to represent and find gaps between timeline objects.

[Edward Hervey <edwardrv src gnome org>]

commit db2ddd2f50c26b1e077670adaca1f74ee0cc9d04
Author: Alessandro Decina <alessandro d gmail com>
Date:   Sun Jul 19 20:43:19 2009 +0200

    Add code to represent and find gaps between timeline objects.

 pitivi/timeline/Makefile.am |    5 +-
 pitivi/timeline/gap.py      |  122 +++++++++++++++++++++++++++++++++
 tests/Makefile.am           |    3 +-
 tests/test_gap.py           |  158 +++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 285 insertions(+), 3 deletions(-)
---
diff --git a/pitivi/timeline/Makefile.am b/pitivi/timeline/Makefile.am
index cb1aa81..8a87d32 100644
--- a/pitivi/timeline/Makefile.am
+++ b/pitivi/timeline/Makefile.am
@@ -3,8 +3,9 @@ timelinedir = $(libdir)/pitivi/python/pitivi/timeline
 timeline_PYTHON = 	\
 	__init__.py	\
 	timeline.py	\
-    timeline_undo.py \
-	track.py
+	timeline_undo.py \
+	track.py \
+	gap.py
 
 clean-local:
 	rm -rf *.pyc *.pyo
diff --git a/pitivi/timeline/gap.py b/pitivi/timeline/gap.py
new file mode 100644
index 0000000..c99e8a9
--- /dev/null
+++ b/pitivi/timeline/gap.py
@@ -0,0 +1,122 @@
+# PiTiVi , Non-linear video editor
+#
+#       pitivi/timeline/gap.py
+#
+# Copyright (c) 2009, Alessandro Decina <alessandro decina collabora co uk>
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU Lesser General Public
+# License as published by the Free Software Foundation; either
+# version 2.1 of the License, or (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+# Lesser General Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with this program; if not, write to the
+# Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+# Boston, MA 02111-1307, USA.
+
+from pitivi.utils import infinity
+
+class Gap(object):
+    def __init__(self, left_object, right_object, start, duration):
+        self.left_object = left_object
+        self.right_object = right_object
+        self.start = start
+        self.initial_duration = duration
+
+    def __cmp__(self, other):
+        if other is None or other is invalid_gap:
+            return -1
+        return cmp(self.duration, other.duration)
+
+    @classmethod
+    def findAroundObject(self, timeline_object, priority=-1):
+        from pitivi.timeline.timeline import TimelineError
+
+        timeline = timeline_object.timeline
+        try:
+            prev = timeline.getPreviousTimelineObject(timeline_object, priority)
+        except TimelineError:
+            left_object = None
+            right_object = timeline_object
+            start = 0
+            duration = timeline_object.start
+        else:
+            left_object = prev
+            right_object = timeline_object
+            start = prev.start + prev.duration
+            duration = timeline_object.start - start
+
+        left_gap = Gap(left_object, right_object, start, duration)
+
+        try:
+            next = timeline.getNextTimelineObject(timeline_object, priority)
+        except TimelineError:
+            left_object = timeline_object
+            right_object = None
+            start = timeline_object.start + timeline_object.duration
+            duration = infinity
+        else:
+            left_object = timeline_object
+            right_object = next
+            start = timeline_object.start + timeline_object.duration
+            duration = next.start - start
+
+        right_gap = Gap(left_object, right_object, start, duration)
+
+        return left_gap, right_gap
+
+    @property
+    def duration(self):
+        if self.left_object is None and self.right_object is None:
+            return self.initial_duration
+
+        if self.initial_duration is infinity:
+            return self.initial_duration
+
+        if self.left_object is None:
+            return self.right_object.start
+
+        if self.right_object is None:
+            return infinity
+
+        res = self.right_object.start - \
+                (self.left_object.start + self.left_object.duration)
+        return res
+
+class InvalidGap(object):
+    pass
+
+invalid_gap = InvalidGap()
+
+class SmallestGapsFinder(object):
+    def __init__(self, internal_objects):
+        self.left_gap = None
+        self.right_gap = None
+        self.internal_objects = internal_objects
+
+    def update(self, left_gap, right_gap):
+        self.updateGap(left_gap, "left_gap")
+        self.updateGap(right_gap, "right_gap")
+
+    def updateGap(self, gap, min_gap_name):
+        if self.isInternalGap(gap):
+            return
+
+        min_gap = getattr(self, min_gap_name)
+
+        if min_gap is invalid_gap or gap.duration < 0:
+            setattr(self, min_gap_name, invalid_gap)
+            return
+
+        if min_gap is None or gap < min_gap:
+            setattr(self, min_gap_name, gap)
+
+    def isInternalGap(self, gap):
+        gap_objects = set([gap.left_object, gap.right_object])
+
+        return gap_objects.issubset(self.internal_objects)
diff --git a/tests/Makefile.am b/tests/Makefile.am
index d3e12bf..6d87287 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -8,7 +8,8 @@ tests = \
 	test_pipeline.py		\
 	test_action.py			\
 	test_undo.py			\
-	test_timeline_undo.py
+	test_timeline_undo.py		\
+	test_gap.py
 
 EXTRA_DIST = $(tests) runtests.py common.py
 
diff --git a/tests/test_gap.py b/tests/test_gap.py
new file mode 100644
index 0000000..975b854
--- /dev/null
+++ b/tests/test_gap.py
@@ -0,0 +1,158 @@
+# PiTiVi , Non-linear video editor
+#
+#       tests/test_gap.py
+#
+# Copyright (c) 2009, Alessandro Decina <alessandro decina collabora co uk>
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU Lesser General Public
+# License as published by the Free Software Foundation; either
+# version 2.1 of the License, or (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+# Lesser General Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with this program; if not, write to the
+# Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+# Boston, MA 02111-1307, USA.
+
+from unittest import TestCase
+
+import gobject
+gobject.threads_init()
+import gst
+
+from tests.common import StubFactory
+from pitivi.stream import AudioStream
+from pitivi.timeline.track import Track, SourceTrackObject
+from pitivi.timeline.timeline import Timeline, TimelineObject
+from pitivi.timeline.gap import Gap, SmallestGapsFinder, invalid_gap
+from pitivi.utils import infinity
+
+class TestGap(TestCase):
+    def setUp(self):
+        self.factory = StubFactory()
+        self.stream = AudioStream(gst.Caps('audio/x-raw-int'))
+        self.factory.addOutputStream(self.stream)
+        self.track1 = Track(self.stream)
+        self.timeline = Timeline()
+
+    def makeTimelineObject(self):
+        track_object = SourceTrackObject(self.factory, self.stream)
+        self.track1.addTrackObject(track_object)
+        timeline_object = TimelineObject(self.factory)
+        timeline_object.addTrackObject(track_object)
+        self.timeline.addTimelineObject(timeline_object)
+
+        return timeline_object
+
+    def testGapCmp(self):
+        gap1 = Gap(None, None, start=10, duration=5)
+        gap2 = Gap(None, None, start=10, duration=5)
+        self.failUnlessEqual(gap1, gap2)
+
+        gap2 = Gap(None, None, start=15, duration=4)
+        self.failUnless(gap1 > gap2)
+        self.failUnless(gap2 < gap1)
+
+    def testFindAroundObject(self):
+        timeline_object1 = self.makeTimelineObject()
+        timeline_object2 = self.makeTimelineObject()
+
+        timeline_object1.start = 5 * gst.SECOND
+        timeline_object1.duration = 10 * gst.SECOND
+        timeline_object2.start = 20 * gst.SECOND
+        timeline_object2.duration = 10 * gst.SECOND
+
+        left_gap, right_gap = Gap.findAroundObject(timeline_object1)
+        self.failUnlessEqual(left_gap.left_object, None)
+        self.failUnlessEqual(left_gap.right_object, timeline_object1)
+        self.failUnlessEqual(left_gap.start, 0 * gst.SECOND)
+        self.failUnlessEqual(left_gap.duration, 5 * gst.SECOND)
+        self.failUnlessEqual(right_gap.left_object, timeline_object1)
+        self.failUnlessEqual(right_gap.right_object, timeline_object2)
+        self.failUnlessEqual(right_gap.start, 15 * gst.SECOND)
+        self.failUnlessEqual(right_gap.duration, 5 * gst.SECOND)
+
+        left_gap, right_gap = Gap.findAroundObject(timeline_object2)
+        self.failUnlessEqual(left_gap.left_object, timeline_object1)
+        self.failUnlessEqual(left_gap.right_object, timeline_object2)
+        self.failUnlessEqual(left_gap.start, 15 * gst.SECOND)
+        self.failUnlessEqual(left_gap.duration, 5 * gst.SECOND)
+        self.failUnlessEqual(right_gap.left_object, timeline_object2)
+        self.failUnlessEqual(right_gap.right_object, None)
+        self.failUnlessEqual(right_gap.start, 30 * gst.SECOND)
+        self.failUnlessEqual(right_gap.duration, infinity)
+
+        # make the objects overlap
+        timeline_object2.start = 10 * gst.SECOND
+        left_gap, right_gap = Gap.findAroundObject(timeline_object1)
+        self.failUnlessEqual(right_gap.left_object, timeline_object1)
+        self.failUnlessEqual(right_gap.right_object, timeline_object2)
+        self.failUnlessEqual(right_gap.start, 15 * gst.SECOND)
+        self.failUnlessEqual(right_gap.duration, -5 * gst.SECOND)
+
+    def testGapFinder(self):
+        timeline_object1 = self.makeTimelineObject()
+        timeline_object2 = self.makeTimelineObject()
+        timeline_object3 = self.makeTimelineObject()
+        timeline_object4 = self.makeTimelineObject()
+        
+        timeline_object1.start = 5 * gst.SECOND
+        timeline_object1.duration = 10 * gst.SECOND
+        timeline_object1.priority = 1
+
+        timeline_object2.start = 20 * gst.SECOND
+        timeline_object2.duration = 10 * gst.SECOND
+        timeline_object2.priority = 1
+
+        timeline_object3.start = 31 * gst.SECOND
+        timeline_object3.duration = 10 * gst.SECOND
+        timeline_object3.priority = 2
+
+        timeline_object4.start = 50 * gst.SECOND
+        timeline_object4.duration = 10 * gst.SECOND
+        timeline_object4.priority = 2
+
+        gap_finder = SmallestGapsFinder(set([timeline_object2,
+                timeline_object3]))
+        gap_finder.update(*Gap.findAroundObject(timeline_object2))
+        gap_finder.update(*Gap.findAroundObject(timeline_object3))
+
+        left_gap = gap_finder.left_gap
+        right_gap = gap_finder.right_gap
+        self.failUnlessEqual(left_gap.left_object, timeline_object1)
+        self.failUnlessEqual(left_gap.right_object, timeline_object2)
+        self.failUnlessEqual(left_gap.start, 15 * gst.SECOND)
+        self.failUnlessEqual(left_gap.duration, 5 * gst.SECOND)
+        self.failUnlessEqual(right_gap.left_object, timeline_object3)
+        self.failUnlessEqual(right_gap.right_object, timeline_object4)
+        self.failUnlessEqual(right_gap.start, 41 * gst.SECOND)
+        self.failUnlessEqual(right_gap.duration, 9 * gst.SECOND)
+
+        # make timeline_object3 and timeline_object4 overlap
+        timeline_object3.duration = 20 * gst.SECOND
+
+        gap_finder = SmallestGapsFinder(set([timeline_object4]))
+        gap_finder.update(*Gap.findAroundObject(timeline_object4))
+        left_gap = gap_finder.left_gap
+        right_gap = gap_finder.right_gap
+        self.failUnlessEqual(left_gap, invalid_gap)
+        self.failUnlessEqual(right_gap.left_object, timeline_object4)
+        self.failUnlessEqual(right_gap.right_object, None)
+        self.failUnlessEqual(right_gap.start, 60 * gst.SECOND)
+        self.failUnlessEqual(right_gap.duration, infinity)
+
+        gap_finder = SmallestGapsFinder(set([timeline_object3]))
+        gap_finder.update(*Gap.findAroundObject(timeline_object3))
+        left_gap = gap_finder.left_gap
+        right_gap = gap_finder.right_gap
+        self.failUnlessEqual(left_gap.left_object, None)
+        self.failUnlessEqual(left_gap.right_object, timeline_object3)
+        self.failUnlessEqual(left_gap.start, 0 * gst.SECOND)
+        self.failUnlessEqual(left_gap.duration, 31 * gst.SECOND)
+        self.failUnlessEqual(right_gap, invalid_gap)
+