1 files changed, 49 insertions, 33 deletions

diff --git a/lout/container.cc b/lout/container.cc
index d3385137..dcac4726 100644
--- a/lout/container.cc
+++ b/lout/container.cc
@@ -22,6 +22,7 @@
 
 #include "container.hh"
 #include "misc.hh"
+#include "debug.hh"
 
 namespace lout {
 
@@ -188,9 +189,10 @@ void Vector::remove(int pos)
 /**
  * Sort the elements in the vector. Assumes that all elements are Comparable's.
  */
-void Vector::sort()
+void Vector::sort(Comparator *comparator)
 {
-   qsort (array, numElements, sizeof(Object*), Comparable::compareFun);
+   Comparator::compareFunComparator = comparator;
+   qsort (array, numElements, sizeof(Object*), Comparator::compareFun);
 }
 
 /**
@@ -202,44 +204,58 @@ void Vector::sort()
  * size of the array. (This is the value which can be used for
  * insertion; see insertSortet()).
  */
-int Vector::bsearch(Object *key, bool mustExist)
+int Vector::bsearch(Object *key, bool mustExist, int start, int end,
+                    Comparator *comparator)
 {
    // The case !mustExist is not handled by bsearch(3), so here is a
    // new implementation.
-   if (numElements == 0)
-      return mustExist ? -1 : 0;
-
-   int high = numElements - 1, low = 0;
-
-   while (true) {
-      int index = (low + high) / 2;
-      int c = ((Comparable*) key)->compareTo ((Comparable*)array[index]);
-      if (c == 0)
-         return index;
-      else {
-         if (low >= high) {
-            if (mustExist)
-               return -1;
+
+   DBG_OBJ_MSGF ("container", 0,
+                 "<b>bsearch</b> (<i>key</i>, %s, %d, %d, <i>comparator</i>) "
+                 "[size is %d]",
+                 mustExist ? "true" : "false", start, end, size ());
+   DBG_OBJ_MSG_START ();
+
+   int result = -123; // Compiler happiness: GCC 4.7 does not handle this?
+
+   if (start > end) {
+      DBG_OBJ_MSG ("container", 1, "empty");
+      result = mustExist ? -1 : start;
+   } else {
+      int low = start, high = end;
+      bool found = false;
+
+      while (!found) {       
+         int index = (low + high) / 2;
+         int c = comparator->compare (key, array[index]);
+         DBG_OBJ_MSGF ("container", 1,
+                       "searching within %d and %d; compare key with #%d => %d",
+                       low, high, index, c);
+         if (c == 0) {
+            found = true;
+            result = index;
+         } else {
+            if (low >= high) {
+               if (mustExist) {
+                  found = true;
+                  result = -1;
+               } else {
+                  found = true;
+                  result = c > 0 ? index + 1 : index;
+               }
+            }
+            
+            if (c < 0)
+               high = index - 1;
             else
-               return c > 0 ? index + 1 : index;
+               low = index + 1;
          }
-
-         if (c < 0)
-            high = index - 1;
-         else
-            low = index + 1;
       }
-   }
-
+   }  
 
-   /*
-   void *result = ::bsearch (&key, array, numElements, sizeof (Object*),
-                             Comparable::compareFun);
-   if (result)
-      return (Object**)result - array;
-   else
-      return -1;
-   */
+   DBG_OBJ_MSGF ("container", 1, "result = %d", result);
+   DBG_OBJ_MSG_END ();
+   return result;
 }
 
 Object *Vector::VectorIterator::getNext()