1 files changed, 122 insertions, 34 deletions

diff --git a/lout/container.cc b/lout/container.cc
index d3385137..366a58fa 100644
--- a/lout/container.cc
+++ b/lout/container.cc
@@ -22,6 +22,7 @@
 
 #include "container.hh"
 #include "misc.hh"
+#include "debug.hh"
 
 namespace lout {
 
@@ -103,6 +104,8 @@ void Collection::intoStringBuffer(misc::StringBuffer *sb)
 
 Vector::Vector(int initSize, bool ownerOfObjects)
 {
+   DBG_OBJ_CREATE ("lout::container::untyped::Vector");
+
    numAlloc = initSize == 0 ? 1 : initSize;
    this->ownerOfObjects = ownerOfObjects;
    numElements = 0;
@@ -113,6 +116,13 @@ Vector::~Vector()
 {
    clear();
    free(array);
+
+   DBG_OBJ_DELETE ();
+}
+
+int Vector::size ()
+{
+   return numElements;
 }
 
 void Vector::put(Object *newElement, int newPos)
@@ -188,9 +198,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 +213,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()
@@ -276,6 +301,32 @@ List::~List()
    clear();
 }
 
+int List::size ()
+{
+   return numElements;
+}
+
+bool List::equals(Object *other)
+{
+   List *otherList = (List*)other;
+   Node *node1 = first, *node2 = otherList->first;
+   while (node1 != NULL && node2 != NULL ) {
+      if (!node1->object->equals (node2->object))
+         return false;
+      node1 = node1->next;
+      node2 = node2->next;
+   }
+   return node1 == NULL && node2 == NULL;
+}
+
+int List::hashValue()
+{
+   int h = 0;
+   for (Node *node = first; node; node = node->next)
+      h = h ^ node->object->hashValue ();
+   return h;
+}
+
 void List::clear()
 {
    while (first) {
@@ -305,6 +356,28 @@ void List::append(Object *element)
    numElements++;
 }
 
+bool List::insertBefore(object::Object *beforeThis, object::Object *neew)
+{
+   Node *beforeCur, *cur;
+
+   for (beforeCur = NULL, cur = first; cur; beforeCur = cur, cur = cur->next) {
+      if (cur->object == beforeThis) {
+         Node *newNode = new Node;
+         newNode->next = cur;
+         newNode->object = neew;
+         
+         if (beforeCur)
+            beforeCur->next = newNode;
+         else
+            first = newNode;
+
+         numElements++;
+         return true;
+      }
+   }
+
+   return false;
+}
 
 bool List::remove0(Object *element, bool compare, bool doNotDeleteAtAll)
 {
@@ -372,6 +445,8 @@ HashSet::HashSet(bool ownerOfObjects, int tableSize)
    table = new Node*[tableSize];
    for (int i = 0; i < tableSize; i++)
       table[i] = NULL;
+
+   numElements = 0;
 }
 
 HashSet::~HashSet()
@@ -399,6 +474,11 @@ HashSet::~HashSet()
    delete[] table;
 }
 
+int HashSet::size ()
+{
+   return numElements;
+}
+
 HashSet::Node *HashSet::createNode()
 {
    return new Node;
@@ -427,13 +507,15 @@ HashSet::Node *HashSet::insertNode(Object *object)
 {
    // Look whether object is already contained.
    Node *node = findNode(object);
-   if (node)
+   if (node) {
       clearNode(node);
-   else {
+      numElements--;
+   } else {
       int h = calcHashValue(object);
       node = createNode ();
       node->next = table[h];
       table[h] = node;
+      numElements++;
    }
 
    node->object = object;
@@ -471,6 +553,7 @@ bool HashSet::remove(Object *object)
 
          clearNode (cur);
          delete cur;
+         numElements--;
 
          return true;
       }
@@ -642,6 +725,11 @@ Stack::~Stack()
       pop ();
 }
 
+int Stack::size ()
+{
+   return numElements;
+}
+
 void Stack::push (object::Object *object)
 {
    Node *newTop = new Node ();