1 files changed, 558 insertions, 0 deletions
diff --git a/lout/container.cc b/lout/container.cc
new file mode 100644
index 00000000..0b00c195
--- /dev/null
+++ b/lout/container.cc
@@ -0,0 +1,558 @@
+/*
+ * Dillo Widget
+ *
+ * Copyright 2005-2007 Sebastian Geerken <sgeerken@dillo.org>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+
+
+#include "container.hh"
+#include "misc.hh"
+
+namespace lout {
+
+using namespace object;
+
+namespace container {
+
+namespace untyped {
+
+// -------------
+//    Iterator
+// -------------
+
+Iterator::Iterator()
+{
+   impl = NULL;
+}
+
+Iterator::Iterator(const Iterator &it2)
+{
+   impl = it2.impl;
+   if(impl)
+      impl->ref();
+}
+
+Iterator::Iterator(Iterator &it2)
+{
+   impl = it2.impl;
+   if(impl)
+      impl->ref();
+}
+
+Iterator &Iterator::operator=(const Iterator &it2)
+{
+   if(impl)
+      impl->unref();
+   impl = it2.impl;
+   if(impl)
+      impl->ref();
+   return *this;
+}
+
+Iterator &Iterator::operator=(Iterator &it2)
+{
+   if(impl)
+      impl->unref();
+   impl = it2.impl;
+   if(impl)
+      impl->ref();
+   return *this;
+}
+
+Iterator::~Iterator()
+{
+   if(impl)
+      impl->unref(); 
+}
+
+// ----------------
+//    Collection
+// ----------------
+
+void Collection::intoStringBuffer(misc::StringBuffer *sb)
+{
+   sb->append("{ ");
+   bool first = true;
+   for(Iterator it = iterator(); it.hasNext(); ) {
+      if(!first)
+         sb->append(", ");
+      it.getNext()->intoStringBuffer(sb);
+      first = false;
+   }
+   sb->append(" }");
+}
+
+// ------------
+//    Vector
+// ------------
+
+Vector::Vector(int initSize, bool ownerOfObjects)
+{
+   numAlloc = initSize == 0 ? 1 : initSize;
+   this->ownerOfObjects = ownerOfObjects;
+   numElements = 0;
+   array = (Object**)malloc(numAlloc * sizeof(Object*));
+}
+
+Vector::~Vector()
+{
+   clear();
+   free(array);
+}
+
+void Vector::put(Object *newElement, int newPos)
+{
+   if(newPos == -1)
+      newPos = numElements;
+
+   // Old entry is overwritten.
+   if(newPos < numElements) {
+      if(ownerOfObjects && array[newPos])
+         delete array[newPos];
+   }
+
+   // Allocated memory has to be increased.
+   if(newPos >= numAlloc) {
+      while (newPos >= numAlloc)
+         numAlloc *= 2;
+      array = (Object**)realloc(array, numAlloc * sizeof(Object*));
+   }
+
+   // Insert NULL's into possible gap before new position.
+   for(int i = numElements; i < newPos; i++)
+      array[i] = NULL;
+
+   if(newPos >= numElements)
+      numElements = newPos + 1;
+
+   array[newPos] = newElement;
+}
+
+void Vector::clear()
+{
+   if (ownerOfObjects) {
+      for(int i = 0; i < numElements; i++)
+         if(array[i])
+            delete array[i];
+   }
+
+   numElements = 0;
+}
+
+void Vector::insert(Object *newElement, int pos)
+{
+   if(pos >= numElements)
+      put(newElement, pos);
+   else {
+      numElements++;
+
+      // Allocated memory has to be increased.
+      if(numElements >= numAlloc) {
+         numAlloc *= 2;
+         array = (Object**)realloc(array, numAlloc * sizeof(Object*));
+      }
+
+      for(int i = numElements - 1; i > pos; i--)
+         array[i] = array[i - 1];
+
+      array[pos] = newElement;
+   }
+}
+
+void Vector::remove(int pos)
+{
+   if(ownerOfObjects && array[pos])
+      delete array[pos];
+
+   for(int i = pos + 1; i < numElements; i++)
+      array[i - 1] = array[i];
+
+   numElements--;
+}
+
+/**
+ * Sort the elements in the vector. Assumes that all elements are Comparable's.
+ */
+void Vector::sort()
+{
+   qsort(array, numElements, sizeof(Object*), misc::Comparable::compareFun);
+}
+
+
+/**
+ * \bug Not implemented.
+ */
+Collection0::AbstractIterator* Vector::createIterator()
+{
+   return NULL;
+}
+
+// ------------
+//    List
+// ------------
+
+List::List(bool ownerOfObjects)
+{
+   this->ownerOfObjects = ownerOfObjects;
+   first = last = NULL;
+   numElements = 0;
+}
+
+List::~List()
+{
+   clear();
+}
+
+void List::clear()
+{
+   while(first) {
+      if(ownerOfObjects && first->object)
+         delete first->object;
+      Node *next = first->next;
+      delete first;
+      first = next;
+   }
+
+   last = NULL;
+   numElements = 0;
+}
+
+void List::append(Object *element)
+{
+   Node *newLast = new Node;
+   newLast->next = NULL;
+   newLast->object = element;
+
+   if(last) {
+      last->next = newLast;
+      last = newLast;
+   } else 
+      first = last = newLast;
+
+   numElements++;
+}
+
+
+bool List::remove0(Object *element, bool compare, bool doNotDeleteAtAll)
+{
+   Node *beforeCur, *cur;
+
+   for(beforeCur = NULL, cur = first; cur; beforeCur = cur, cur = cur->next) {
+      if (compare ?
+          (cur->object && element->equals(cur->object)) :
+          element == cur->object) {
+         if(beforeCur) {
+            beforeCur->next = cur->next;
+            if(cur->next == NULL)
+               last = beforeCur;
+         } else {
+            first = cur->next;
+            if(first == NULL)
+               last = NULL;
+         }
+
+         if(ownerOfObjects && cur->object && !doNotDeleteAtAll)
+            delete cur->object;
+         delete cur;
+
+         numElements--;
+         return true;
+      }
+   }
+
+   return false;
+}
+
+Object *List::ListIterator::getNext()
+{
+   Object *object;
+
+   if(current) {
+      object = current->object;
+      current = current->next;
+   } else
+      object = NULL;
+
+   return object;
+}
+
+bool List::ListIterator::hasNext()
+{
+   return current != NULL;
+}
+
+Collection0::AbstractIterator* List::createIterator()
+{
+   return new ListIterator(first);
+}
+
+
+// ---------------
+//    HashTable
+// ---------------
+
+HashTable::HashTable(bool ownerOfKeys, bool ownerOfValues, int tableSize)
+{
+   this->ownerOfKeys = ownerOfKeys;
+   this->ownerOfValues = ownerOfValues;
+   this->tableSize = tableSize;
+
+   table = new Node*[tableSize];
+   for(int i = 0; i < tableSize; i++)
+      table[i] = NULL;
+}
+
+HashTable::~HashTable()
+{
+   for(int i = 0; i < tableSize; i++) {
+      Node *n1 = table[i];
+      while(n1) {
+         Node *n2 = n1->next;
+
+         if(ownerOfValues && n1->value)
+            delete n1->value;
+         if(ownerOfKeys)
+            delete n1->key;
+         delete n1;
+
+         n1 = n2;
+      }
+   }
+
+   delete[] table;
+}
+
+void HashTable::intoStringBuffer(misc::StringBuffer *sb)
+{
+   sb->append("{ ");
+
+   bool first = true;
+   for(int i = 0; i < tableSize; i++) {
+      for(Node *node = table[i]; node; node = node->next) {
+         if(!first)
+            sb->append(", ");
+         node->key->intoStringBuffer(sb);
+         sb->append(" => ");
+         node->value->intoStringBuffer(sb);
+         first = false;
+      }
+   }
+
+   sb->append(" }");
+}
+
+void HashTable::put(Object *key, Object *value)
+{
+   int h = calcHashValue(key);
+   Node *n = new Node;
+   n->key = key;
+   n->value = value;
+   n->next = table[h];
+   table[h] = n;
+}
+
+bool HashTable::contains(Object *key)
+{
+   int h = calcHashValue(key);
+   for(Node *n = table[h]; n; n = n->next) {
+      if (key->equals(n->key))
+         return true;
+   }
+
+   return false;
+}
+
+Object *HashTable::get(Object *key)
+{
+   int h = calcHashValue(key);
+   for(Node *n = table[h]; n; n = n->next) {
+      if (key->equals(n->key))
+         return n->value;
+   }
+
+   return NULL;
+}
+
+bool HashTable::remove(Object *key)
+{
+   int h = calcHashValue(key);
+   Node *last, *cur;
+
+   for(last = NULL, cur = table[h]; cur; last = cur, cur = cur->next) {
+      if (key->equals(cur->key)) {
+         if(last)
+            last->next = cur->next;
+         else
+            table[h] = cur->next;
+
+         if(ownerOfValues && cur->value)
+            delete cur->value;
+         if(ownerOfKeys)
+            delete cur->key;
+         delete cur;
+
+         return true;
+      }
+   }
+
+   return false;
+}
+
+Object *HashTable::getKey (Object *key)
+{
+   int h = calcHashValue(key);
+   for(Node *n = table[h]; n; n = n->next) {
+      if (key->equals(n->key))
+         return n->key;
+   }
+
+   return NULL;
+}
+
+HashTable::HashTableIterator::HashTableIterator(HashTable *table)
+{
+   this->table = table;
+   node = NULL;
+   pos = -1;
+   gotoNext();
+}
+
+void HashTable::HashTableIterator::gotoNext()
+{
+   if(node)
+      node = node->next;
+
+   while(node == NULL) {
+      if(pos >= table->tableSize - 1)
+         return;
+      pos++;
+      node = table->table[pos];
+   }
+}
+
+
+Object *HashTable::HashTableIterator::getNext()
+{
+   Object *result;
+   if(node)
+      result = node->key;
+   else
+      result = NULL;
+
+   gotoNext();
+   return result;
+}
+
+bool HashTable::HashTableIterator::hasNext()
+{
+   return node != NULL;
+}
+
+Collection0::AbstractIterator* HashTable::createIterator()
+{
+   return new HashTableIterator(this);
+}
+
+// -----------
+//    Stack
+// -----------
+
+Stack::Stack (bool ownerOfObjects)
+{
+   this->ownerOfObjects = ownerOfObjects;
+   bottom = top = NULL;
+   numElements = 0;
+}
+
+Stack::~Stack()
+{
+   while (top)
+      pop ();
+}
+
+void Stack::push (object::Object *object)
+{
+   Node *newTop = new Node ();
+   newTop->object = object;
+   newTop->prev = top;
+
+   top = newTop;
+   if(bottom == NULL)
+      bottom = top;
+
+   numElements++;
+}
+
+void Stack::pushUnder (object::Object *object)
+{
+   Node *newBottom = new Node ();
+   newBottom->object = object;
+   newBottom->prev = NULL;
+   if(bottom != NULL)
+      bottom->prev = newBottom;
+
+   bottom = newBottom;
+   if(top == NULL)
+      top = bottom;
+
+   numElements++;
+}
+
+void Stack::pop ()
+{
+   Node *newTop = top->prev;
+
+   if (ownerOfObjects)
+      delete top->object;
+   delete top;
+
+   top = newTop;
+   if(top == NULL)
+      bottom = NULL;
+
+   numElements--;
+}
+
+Object *Stack::StackIterator::getNext()
+{
+   Object *object;
+
+   if(current) {
+      object = current->object;
+      current = current->prev;
+   } else
+      object = NULL;
+
+   return object;
+}
+
+bool Stack::StackIterator::hasNext()
+{
+   return current != NULL;
+}
+
+Collection0::AbstractIterator* Stack::createIterator()
+{
+   return new StackIterator(top);
+}
+
+} // namespace untyped
+
+} // namespace container
+
+} // namespace lout