/*
 * 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