[pitivi] Keep TrackObjects sorted by start time inside Track.

[Edward Hervey <edwardrv src gnome org>]

commit fc9d0fb055b9472732728880a8b31dd70c6e516f
Author: Alessandro Decina <alessandro d gmail com>
Date:   Sun Jul 19 20:37:57 2009 +0200

    Keep TrackObjects sorted by start time inside Track.
    
    Keep TrackObjects sorted by start inside Track so that we can implement decently
    fast getPreviousTrackObject and getNextTrackObject.

 pitivi/timeline/track.py |   36 ++++++++++++++-
 pitivi/utils.py          |  110 ++++++++++++++++++++++++++++++++++++++++++++++
 tests/test_track.py      |  101 ++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 244 insertions(+), 3 deletions(-)
---
diff --git a/pitivi/timeline/track.py b/pitivi/timeline/track.py
index d0035ad..8556a7e 100644
--- a/pitivi/timeline/track.py
+++ b/pitivi/timeline/track.py
@@ -23,7 +23,8 @@ import gst
 import weakref
 
 from pitivi.signalinterface import Signallable
-from pitivi.utils import UNKNOWN_DURATION, get_controllable_properties
+from pitivi.utils import get_controllable_properties, getPreviousObject, \
+        getNextObject, start_insort_right
 from pitivi.log.loggable import Loggable
 from pitivi.stream import VideoStream, AudioStream
 from pitivi.factories.test import VideoTestSourceFactory, \
@@ -585,7 +586,6 @@ class TrackObject(Signallable, Loggable):
     def _makeGnlObject(self):
         raise NotImplementedError()
 
-
 class SourceTrackObject(TrackObject):
     def _makeGnlObject(self):
         source = gst.element_factory_make('gnlsource')
@@ -664,6 +664,22 @@ class Track(Signallable):
             self.default_track_object = None
             raise
 
+    def getPreviousTrackObject(self, obj, priority=-1):
+        prev = getPreviousObject(obj, self.track_objects, priority,
+                [self.default_track_object])
+        if prev is None:
+            raise TrackError("no previous track object", obj)
+
+        return prev
+
+    def getNextTrackObject(self, obj, priority=-1):
+        next = getNextObject(obj, self.track_objects, priority,
+                [self.default_track_object])
+        if next is None:
+            raise TrackError("no next track object", obj)
+
+        return next
+
     start = property(_getStart)
 
     def _getDuration(self):
@@ -704,7 +720,8 @@ class Track(Signallable):
         track_object.makeBin()
 
         track_object.track = weakref.proxy(self)
-        self.track_objects.append(track_object)
+
+        start_insort_right(self.track_objects, track_object)
 
         try:
             self.composition.add(track_object.gnl_object)
@@ -765,12 +782,25 @@ class Track(Signallable):
     def _trackObjectPriorityChangedCb(self, track_object, priority):
         self._updateMaxPriority()
 
+    def _trackObjectStartChangedCb(self, track_object, start):
+        self.track_objects.remove(track_object)
+        start_insort_right(self.track_objects, track_object)
+
+    def _trackObjectDurationChangedCb(self, track_object, duration):
+        pass
+
     def _connectToTrackObject(self, track_object):
         track_object.connect('priority-changed',
                 self._trackObjectPriorityChangedCb)
+        track_object.connect('start-changed',
+                self._trackObjectStartChangedCb)
+        track_object.connect('duration-changed',
+                self._trackObjectDurationChangedCb)
 
     def _disconnectFromTrackObject(self, track_object):
         track_object.disconnect_by_function(self._trackObjectPriorityChangedCb)
+        track_object.disconnect_by_function(self._trackObjectStartChangedCb)
+        track_object.disconnect_by_function(self._trackObjectDurationChangedCb)
 
     def enableUpdates(self):
         self.composition.props.update = True
diff --git a/pitivi/utils.py b/pitivi/utils.py
index aa914ee..67200aa 100644
--- a/pitivi/utils.py
+++ b/pitivi/utils.py
@@ -328,3 +328,113 @@ def get_controllable_properties(element):
                 log.debug("utils", "adding property %r", prop)
                 res.append((element, prop))
     return res
+
+def start_insort_left(a, x, lo=0, hi=None):
+    if hi is None:
+        hi = len(a)
+    while lo < hi:
+        mid = (lo+hi)//2
+        if a[mid].start < x.start: lo = mid+1
+        else: hi = mid
+    a.insert(lo, x)
+
+def start_insort_right(a, x, lo=0, hi=None):
+    if hi is None:
+        hi = len(a)
+    while lo < hi:
+        mid = (lo+hi)//2
+        if x.start < a[mid].start: hi = mid
+        else: lo = mid+1
+    a.insert(lo, x)
+
+def start_bisect_left(a, x, lo=0, hi=None):
+    if hi is None:
+        hi = len(a)
+    while lo < hi:
+        mid = (lo+hi)//2
+        if a[mid].start < x.start: lo = mid+1
+        else: hi = mid
+    return lo
+
+class Infinity(object):
+    def __cmp__(self, other):
+        if isinstance(other, Infinity):
+            return 0
+
+        return 1
+
+infinity = Infinity()
+
+def findObject(obj, objects):
+    low = 0
+    high = len(objects)
+    while low < high:
+        low = start_bisect_left(objects, obj, lo=low)
+        if low == high:
+            break
+
+        if objects[low] is obj:
+            return low
+        else:
+            low = low + 1
+
+    return low
+
+def getPreviousObject(obj, objects, priority=-1, exclude=None):
+    if priority == -1:
+        priority = obj.priority
+
+    if exclude is None:
+        exclude = []
+
+    obj_index = findObject(obj, objects)
+    if obj_index is None:
+        import pdb; pdb.set_trace()
+    # check if there are same-start objects
+    prev_obj_index = obj_index + 1
+    while prev_obj_index < len(objects):
+        prev_obj = objects[prev_obj_index]
+        if prev_obj in exclude:
+            continue
+
+        if prev_obj.start != obj.start:
+            break
+
+        if priority is None or prev_obj.priority == priority:
+            return prev_obj
+
+        prev_obj_index += 1
+
+    # check if there are objects with start < obj.start
+    prev_obj_index = obj_index - 1
+    while prev_obj_index >= 0:
+        prev_obj = objects[prev_obj_index]
+        if prev_obj not in exclude and \
+                (priority is None or \
+                    prev_obj.priority == priority):
+            return prev_obj
+
+        prev_obj_index -= 1
+
+    return None
+
+def getNextObject(obj, objects, priority=-1, exclude=None):
+    if priority == -1:
+        priority = obj.priority
+
+    if exclude is None:
+        exclude = []
+
+    obj_index = findObject(obj, objects)
+    next_obj_index = obj_index + 1
+    objs_len = len(objects)
+    while next_obj_index < objs_len:
+        next_obj = objects[next_obj_index]
+        if next_obj not in exclude and \
+                (priority is None or \
+                    next_obj.priority == priority):
+            return next_obj
+
+        next_obj_index += 1
+
+    return None
diff --git a/tests/test_track.py b/tests/test_track.py
index 2dee1f0..aa41697 100644
--- a/tests/test_track.py
+++ b/tests/test_track.py
@@ -393,3 +393,104 @@ class TestTrack(TestCase):
 
         track.removeTrackObject(obj3)
         self.failUnlessEqual(track.max_priority, 0)
+
+    def testGetPreviousTrackObject(self):
+        factory = self.factory
+        stream = self.stream
+        track1 = self.track1
+
+        obj1 = SourceTrackObject(factory, stream)
+        track1.addTrackObject(obj1)
+
+        obj2 = SourceTrackObject(factory, stream)
+        track1.addTrackObject(obj2)
+
+        obj3 = SourceTrackObject(factory, stream)
+        track1.addTrackObject(obj3)
+
+        obj4 = SourceTrackObject(factory, stream)
+        track1.addTrackObject(obj4)
+
+        obj1.start = 1 * gst.SECOND
+        obj1.duration = 5 * gst.SECOND
+        obj1.priority = 1
+
+        obj2.start = 8 * gst.SECOND
+        obj2.duration = 5 * gst.SECOND
+        obj2.priority = 1
+
+        obj3.start = 6 * gst.SECOND
+        obj3.duration = 5 * gst.SECOND
+        obj3.priority = 2
+
+        obj4.start = 7 * gst.SECOND
+        obj4.duration = 5 * gst.SECOND
+        obj4.priority = 3
+
+        # no previous object
+        self.failUnlessRaises(TrackError, track1.getPreviousTrackObject, obj4)
+
+        # same priority
+        prev = track1.getPreviousTrackObject(obj2)
+        self.failUnlessEqual(prev, obj1)
+
+        # given priority
+        prev = track1.getPreviousTrackObject(obj2, priority=2)
+        self.failUnlessEqual(prev, obj3)
+
+        # any priority
+        prev = track1.getPreviousTrackObject(obj2, priority=None)
+        self.failUnlessEqual(prev, obj4)
+
+        obj3.start = 8 * gst.SECOND
+        # same start
+        prev = track1.getPreviousTrackObject(obj2, priority=None)
+        self.failUnlessEqual(prev, obj3)
+
+    def testGetNextTrackObject(self):
+        factory = self.factory
+        stream = self.stream
+        track1 = self.track1
+
+        obj1 = SourceTrackObject(factory, stream)
+        track1.addTrackObject(obj1)
+
+        obj2 = SourceTrackObject(factory, stream)
+        track1.addTrackObject(obj2)
+
+        obj3 = SourceTrackObject(factory, stream)
+        track1.addTrackObject(obj3)
+
+        obj4 = SourceTrackObject(factory, stream)
+        track1.addTrackObject(obj4)
+
+        obj1.start = 1 * gst.SECOND
+        obj1.duration = 5 * gst.SECOND
+        obj1.priority = 1
+
+        obj2.start = 8 * gst.SECOND
+        obj2.duration = 5 * gst.SECOND
+        obj2.priority = 1
+
+        obj3.start = 6 * gst.SECOND
+        obj3.duration = 5 * gst.SECOND
+        obj3.priority = 2
+
+        obj4.start = 7 * gst.SECOND
+        obj4.duration = 5 * gst.SECOND
+        obj4.priority = 3
+
+        # no next object
+        self.failUnlessRaises(TrackError, track1.getNextTrackObject, obj2)
+
+        # same priority
+        prev = track1.getNextTrackObject(obj1)
+        self.failUnlessEqual(prev, obj2)
+
+        # given priority
+        prev = track1.getNextTrackObject(obj1, priority=2)
+        self.failUnlessEqual(prev, obj3)
+
+        # any priority
+        prev = track1.getNextTrackObject(obj3, priority=None)
+        self.failUnlessEqual(prev, obj4)