/*
* 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, see <http://www.gnu.org/licenses/>.
*/
#define PRINTF(fmt, ...)
//#define PRINTF printf
#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*), 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.
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;
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()
{
if (index < vector->numElements - 1)
index++;
return index < vector->numElements ? vector->array[index] : NULL;
}
bool Vector::VectorIterator::hasNext()
{
return index < vector->numElements - 1;
}
Collection0::AbstractIterator* Vector::createIterator()
{
return new VectorIterator(this);
}
// ------------
// 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);
}
// ---------------
// HashSet
// ---------------
HashSet::HashSet(bool ownerOfObjects, int tableSize)
{
this->ownerOfObjects = ownerOfObjects;
this->tableSize = tableSize;
table = new Node*[tableSize];
for (int i = 0; i < tableSize; i++)
table[i] = NULL;
}
HashSet::~HashSet()
{
for (int i = 0; i < tableSize; i++) {
Node *n1 = table[i];
while (n1) {
Node *n2 = n1->next;
// It seems appropriate to call "clearNode(n1)" here instead
// of "delete n1->object", but since this is the destructor,
// the implementation of a sub class would not be called
// anymore. This is the reason why HashTable has an
// destructor.
if (ownerOfObjects) {
PRINTF ("- deleting object: %s\n", n1->object->toString());
delete n1->object;
}
delete n1;
n1 = n2;
}
}
delete[] table;
}
HashSet::Node *HashSet::createNode()
{
return new Node;
}
void HashSet::clearNode(HashSet::Node *node)
{
if (ownerOfObjects) {
PRINTF ("- deleting object: %s\n", node->object->toString());
delete node->object;
}
}
HashSet::Node *HashSet::findNode(Object *object) const
{
int h = calcHashValue(object);
for (Node *node = table[h]; node; node = node->next) {
if (object->equals(node->object))
return node;
}
return NULL;
}
HashSet::Node *HashSet::insertNode(Object *object)
{
// Look whether object is already contained.
Node *node = findNode(object);
if (node)
clearNode(node);
else {
int h = calcHashValue(object);
node = createNode ();
node->next = table[h];
table[h] = node;
}
node->object = object;
return node;
}
void HashSet::put(Object *object)
{
insertNode (object);
}
bool HashSet::contains(Object *object) const
{
int h = calcHashValue(object);
for (Node *n = table[h]; n; n = n->next) {
if (object->equals(n->object))
return true;
}
return false;
}
bool HashSet::remove(Object *object)
{
int h = calcHashValue(object);
Node *last, *cur;
for (last = NULL, cur = table[h]; cur; last = cur, cur = cur->next) {
if (object->equals(cur->object)) {
if (last)
last->next = cur->next;
else
table[h] = cur->next;
clearNode (cur);
delete cur;
return true;
}
}
return false;
// TODO for HashTable: also remove value.
}
// For historical reasons: this method once existed under the name
// "getKey" in HashTable. It could be used to get the real object from
// the table, but it was dangerous, because a change of this object
// would also change the hash value, and so confuse the table.
/*Object *HashSet::getReference (Object *object)
{
int h = calcHashValue(object);
for (Node *n = table[h]; n; n = n->next) {
if (object->equals(n->object))
return n->object;
}
return NULL;
}*/
HashSet::HashSetIterator::HashSetIterator(HashSet *set)
{
this->set = set;
node = NULL;
pos = -1;
gotoNext();
}
void HashSet::HashSetIterator::gotoNext()
{
if (node)
node = node->next;
while (node == NULL) {
if (pos >= set->tableSize - 1)
return;
pos++;
node = set->table[pos];
}
}
Object *HashSet::HashSetIterator::getNext()
{
Object *result;
if (node)
result = node->object;
else
result = NULL;
gotoNext();
return result;
}
bool HashSet::HashSetIterator::hasNext()
{
return node != NULL;
}
Collection0::AbstractIterator* HashSet::createIterator()
{
return new HashSetIterator(this);
}
// ---------------
// HashTable
// ---------------
HashTable::HashTable(bool ownerOfKeys, bool ownerOfValues, int tableSize) :
HashSet (ownerOfKeys, tableSize)
{
this->ownerOfValues = ownerOfValues;
}
HashTable::~HashTable()
{
// See comment in the destructor of HashSet.
for (int i = 0; i < tableSize; i++) {
for (Node *n = table[i]; n; n = n->next) {
if (ownerOfValues) {
Object *value = ((KeyValuePair*)n)->value;
if (value) {
PRINTF ("- deleting value: %s\n", value->toString());
delete value;
}
}
}
}
}
HashSet::Node *HashTable::createNode()
{
return new KeyValuePair;
}
void HashTable::clearNode(HashSet::Node *node)
{
HashSet::clearNode (node);
if (ownerOfValues) {
Object *value = ((KeyValuePair*)node)->value;
if (value) {
PRINTF ("- deleting value: %s\n", value->toString());
delete value;
}
}
}
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->object->intoStringBuffer(sb);
sb->append(" => ");
Object *value = ((KeyValuePair*)node)->value;
if (value)
value->intoStringBuffer(sb);
else
sb->append ("null");
first = false;
}
}
sb->append(" }");
}
void HashTable::put(Object *key, Object *value)
{
KeyValuePair *node = (KeyValuePair*)insertNode(key);
node->value = value;
}
Object *HashTable::get(Object *key) const
{
Node *node = findNode(key);
if (node)
return ((KeyValuePair*)node)->value;
else
return NULL;
}
// -----------
// 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