Vector::bsearch and insertSorted.

3 files changed, 90 insertions, 2 deletions

diff --git a/lout/container.cc b/lout/container.cc
index 9e71ba77..5e5eda73 100644
--- a/lout/container.cc
+++ b/lout/container.cc
@@ -190,7 +190,54 @@ void Vector::remove(int pos)
  */
 void Vector::sort()
 {
-   qsort(array, numElements, sizeof(Object*), Comparable::compareFun);
+   qsort (array, numElements, sizeof(Object*), Comparable::compareFun);
+}
+
+/**
+ * \brief Use binary search to find an element in a sorted vector.
+ *
+ * If "mustExist" is true, only exact matches are found; otherwise, -1
+ * is returned. If it is false, the position of the next greater
+ * element is returned, or, if the key is the greatest element, the
+ * size of the array. (This is the value which can be used for
+ * insertion; see insertSortet()).
+ */
+int Vector::bsearch(Object *key, bool mustExist)
+{
+   // The case !mustExist is not handled by bsearch(3), so here is a
+   // new implementation.
+   
+   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;
+            else
+               return c > 0 ? index + 1 : index;
+         }
+
+         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;
+   */
 }
 
 Object *Vector::VectorIterator::getNext()
diff --git a/lout/container.hh b/lout/container.hh
index 10139211..c87eb10c 100644
--- a/lout/container.hh
+++ b/lout/container.hh
@@ -130,12 +130,23 @@ public:
 
    void put(object::Object *newElement, int newPos = -1);
    void insert(object::Object *newElement, int pos);
+
+   /**
+    * \brief Insert into an already sorted vector.
+    *
+    * Notice that insertion is not very efficient, unless the position
+    * is rather at the end.
+    */
+   inline void insertSorted(object::Object *newElement)
+   { insert (newElement, bsearch (newElement, false)); }
+
    void remove(int pos);
    inline object::Object *get(int pos)
    { return (pos >= 0 && pos < numElements) ? array[pos] : NULL; }
    inline int size() { return numElements; }
    void clear();
    void sort();
+   int bsearch(Object *key, bool mustExist);
 };
 
 
@@ -395,12 +406,16 @@ public:
    { ((untyped::Vector*)this->base)->put(newElement, newPos); }
    inline void insert(T *newElement, int pos)
    { ((untyped::Vector*)this->base)->insert(newElement, pos); }
+   inline void insertSorted(T *newElement)
+   { ((untyped::Vector*)this->base)->insertSorted(newElement); }
    inline void remove(int pos) { ((untyped::Vector*)this->base)->remove(pos); }
    inline T *get(int pos)
    { return (T*)((untyped::Vector*)this->base)->get(pos); }
    inline int size() { return ((untyped::Vector*)this->base)->size(); }
    inline void clear() { ((untyped::Vector*)this->base)->clear(); }
    inline void sort() { ((untyped::Vector*)this->base)->sort(); }
+   inline int bsearch(T *key, bool mustExist)
+   { return ((untyped::Vector*)this->base)->bsearch(key, mustExist); }
 };
 
 
diff --git a/test/containers.cc b/test/containers.cc
index adb58317..d8107bdf 100644
--- a/test/containers.cc
+++ b/test/containers.cc
@@ -45,12 +45,38 @@ void testVector ()
    v.put (new String ("one"));
    v.put (new String ("two"));
    v.put (new String ("three"));
-
    puts (v.toString());
 
    v.sort ();
+   puts (v.toString());
+
+   v.insertSorted (new String ("five"));
+   puts (v.toString());
 
+   v.insertSorted (new String ("six"));
    puts (v.toString());
+
+   v.insertSorted (new String ("four"));
+   puts (v.toString());
+
+   for (int b = 0; b < 2; b++) {
+      bool mustExist = b;
+      printf ("mustExist = %s\n", mustExist ? "true" : "false");
+   
+      String k ("alpha");
+      printf ("   '%s' -> %d\n", k.chars(), v.bsearch (&k, mustExist));
+      
+      for (Iterator<String> it = v.iterator(); it.hasNext(); ) {
+         String *k1 = it.getNext();
+         printf ("   '%s' -> %d\n", k1->chars(), v.bsearch (k1, mustExist));
+         
+         char buf[64];
+         strcpy (buf, k1->chars());
+         strcat (buf, "-var");
+         String k2 (buf);
+         printf ("   '%s' -> %d\n", k2.chars(), v.bsearch (&k2, mustExist));
+      }
+   }
 }
 
 int main (int argc, char *argv[])