[pitivi] misc: Rewrite binary_search and fix the test

[Mathieu Duponchelle <mathieudu src gnome org>]

commit b8affeb76ab89582e9a6c511ec1eabaf30ba070f
Author: Alexandru Băluț <alexandru balut gmail com>
Date:   Sun Dec 8 10:45:41 2013 +0100

    misc: Rewrite binary_search and fix the test

 pitivi/utils/misc.py        |   50 +++++++++++++++++--------------------
 tests/test_binary_search.py |   58 +++++++++++++++----------------------------
 2 files changed, 43 insertions(+), 65 deletions(-)
---
diff --git a/pitivi/utils/misc.py b/pitivi/utils/misc.py
index 937283e..182fb30 100644
--- a/pitivi/utils/misc.py
+++ b/pitivi/utils/misc.py
@@ -27,8 +27,9 @@ from gi.repository import GLib
 from gi.repository import GObject
 from gi.repository import Gst
 from gi.repository import Gtk
-from urllib import quote, unquote
-from urlparse import urlsplit, urlunsplit, urlparse
+from urllib import unquote
+from urlparse import urlsplit, urlparse
+import bisect
 import hashlib
 import os
 import struct
@@ -124,7 +125,6 @@ def isWritable(path):
         # open(path, "rw") will IOError if the file doesn't already exist.
         # Therefore, simply check the directory permissions instead:
         return os.access(os.path.dirname(path), os.W_OK)
-    return True
 
 
 def uri_is_valid(uri):
@@ -361,30 +361,26 @@ def quantize(input, interval):
     return (input // interval) * interval
 
 
-# Python re-implementation of binary search algorithm found here:
-# http://en.wikipedia.org/wiki/Binary_search
-#
-# This is the iterative version without the early termination branch, which
-# also tells us the element of A that are nearest to Value, if the element we
-# want is not found. This is useful for implementing edge snaping in the UI,
-# where we repeatedly search through a list of control points for the one
-# closes to the cursor. Because we don't care whether the cursor position
-# matches the list, this function returns the index of the lement closest to
-# value in the array.
-
-
-def binary_search(col, value):
-    low = 0
-    high = len(col)
-    while (low < high):
-        mid = (low + high) / 2
-        if (col[mid] < value):
-            low = mid + 1
-        else:
-            #can't be high = mid-1: here col[mid] >= value,
-            #so high can't be < mid if col[mid] == value
-            high = mid
-    return low
+def binary_search(elements, value):
+    """Returns the index of the element closest to value.
+
+    @param elements: A sorted list.
+    """
+    if not elements:
+        return -1
+    closest_index = bisect.bisect_left(elements, value, 0, len(elements) - 1)
+    element = elements[closest_index]
+    closest_distance = abs(element - value)
+    if closest_distance == 0:
+        return closest_index
+    for index in (closest_index - 1,):
+        if index < 0:
+            continue
+        distance = abs(elements[index] - value)
+        if closest_distance > distance:
+            closest_index = index
+            closest_distance = distance
+    return closest_index
 
 
 def argmax(func, seq):
diff --git a/tests/test_binary_search.py b/tests/test_binary_search.py
index 73a3922..3d12395 100644
--- a/tests/test_binary_search.py
+++ b/tests/test_binary_search.py
@@ -1,46 +1,28 @@
 import unittest
-import pitivi
-from pitivi.application import Pitivi
 from pitivi.utils.misc import binary_search
 from common import TestCase
 
 
-class BasicTest(TestCase):
-    """
-    Basic test to create the proper creation of the Pitivi object
-    """
-
-    def testBinarySearch(self):
-        # binary_search always returns an index, so we do the comparison here
-        def found(A, result, value):
-            if ((result < len(A)) and (A[result] == value)):
-                return result
-            else:
-                return False
-
-        for offset in xrange(1, 5):
-            for length in xrange(1, 2049, 300):
-                A = [i * offset for i in xrange(0, length)]
-
-## check negative hits
-
-                # search value too low
-                # error if value is found
-                # if search returns non-negative index, fail
-                value = A[0] - 1
-                self.assertFalse(found(A, binary_search(A, value), value))
-
-                # search value too high
-                # error if value is found
-                # if search returns non-negative index, fail
-                value = A[-1] + 1
-                self.assertFalse(found(A, binary_search(A, value), value))
-
-## check positive hits
-                for i, a in enumerate(A):
-                    # error if value is NOT found
-                    # if search does not return correct value, fail
-                    self.assertEquals(binary_search(A, A[i]), i)
+class BinarySearchTest(TestCase):
+
+    def testEmptyList(self):
+        self.assertEquals(binary_search([], 10), -1)
+
+    def testExisting(self):
+        A = [10, 20, 30]
+        for index, element in enumerate(A):
+            self.assertEquals(binary_search([10, 20, 30], element), index)
+
+    def testMissingLeft(self):
+        self.assertEquals(binary_search([10, 20, 30], 1), 0)
+        self.assertEquals(binary_search([10, 20, 30], 16), 1)
+        self.assertEquals(binary_search([10, 20, 30], 29), 2)
+
+    def testMissingRight(self):
+        self.assertEquals(binary_search([10, 20, 30], 11), 0)
+        self.assertEquals(binary_search([10, 20, 30], 24), 1)
+        self.assertEquals(binary_search([10, 20, 30], 40), 2)
+
 
 if __name__ == "__main__":
     unittest.main()