From d8f1e1bcfa59947b0dabc7a1ec61232d2eb5535e Mon Sep 17 00:00:00 2001 From: Sebastian Geerken Date: Tue, 29 Jan 2013 18:17:26 +0100 Subject: Some cleanup in HashTable; new container HashSet (of which HashTable is a sub class); fixed a glitch in both (inserting equal node again does not remove the first instance). --- lout/container.cc | 230 +++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 165 insertions(+), 65 deletions(-) (limited to 'lout/container.cc') diff --git a/lout/container.cc b/lout/container.cc index 0a3d6acd..deeede57 100644 --- a/lout/container.cc +++ b/lout/container.cc @@ -17,7 +17,8 @@ * along with this program. If not, see . */ - +#define PRINTF(fmt, ...) +//#define PRINTF printf #include "container.hh" #include "misc.hh" @@ -302,13 +303,12 @@ Collection0::AbstractIterator* List::createIterator() // --------------- -// HashTable +// HashSet // --------------- -HashTable::HashTable(bool ownerOfKeys, bool ownerOfValues, int tableSize) +HashSet::HashSet(bool ownerOfObjects, int tableSize) { - this->ownerOfKeys = ownerOfKeys; - this->ownerOfValues = ownerOfValues; + this->ownerOfObjects = ownerOfObjects; this->tableSize = tableSize; table = new Node*[tableSize]; @@ -316,19 +316,24 @@ HashTable::HashTable(bool ownerOfKeys, bool ownerOfValues, int tableSize) table[i] = NULL; } -HashTable::~HashTable() +HashSet::~HashSet() { 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; + // 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; } } @@ -336,73 +341,77 @@ HashTable::~HashTable() delete[] table; } -void HashTable::intoStringBuffer(misc::StringBuffer *sb) +HashSet::Node *HashSet::createNode() { - sb->append("{ "); + return new Node; +} - 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; - } +void HashSet::clearNode(HashSet::Node *node) +{ + if (ownerOfObjects) { + PRINTF ("- deleting object: %s\n", node->object->toString()); + delete node->object; } - - sb->append(" }"); } -void HashTable::put(Object *key, Object *value) +HashSet::Node *HashSet::findNode(Object *object) { - int h = calcHashValue(key); - Node *n = new Node; - n->key = key; - n->value = value; - n->next = table[h]; - table[h] = n; + int h = calcHashValue(object); + for (Node *node = table[h]; node; node = node->next) { + if (object->equals(node->object)) + return node; + } + + return NULL; } -bool HashTable::contains(Object *key) +HashSet::Node *HashSet::insertNode(Object *object) { - int h = calcHashValue(key); - for (Node *n = table[h]; n; n = n->next) { - if (key->equals(n->key)) - return true; + // 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; } - return false; + node->object = object; + return node; } -Object *HashTable::get(Object *key) + +void HashSet::put(Object *object) +{ + insertNode (object); +} + +bool HashSet::contains(Object *object) { - int h = calcHashValue(key); + int h = calcHashValue(object); for (Node *n = table[h]; n; n = n->next) { - if (key->equals(n->key)) - return n->value; + if (object->equals(n->object)) + return true; } - return NULL; + return false; } -bool HashTable::remove(Object *key) +bool HashSet::remove(Object *object) { - int h = calcHashValue(key); + int h = calcHashValue(object); Node *last, *cur; for (last = NULL, cur = table[h]; cur; last = cur, cur = cur->next) { - if (key->equals(cur->key)) { + if (object->equals(cur->object)) { if (last) last->next = cur->next; else table[h] = cur->next; - if (ownerOfValues && cur->value) - delete cur->value; - if (ownerOfKeys) - delete cur->key; + clearNode (cur); delete cur; return true; @@ -410,46 +419,53 @@ bool HashTable::remove(Object *key) } return false; + + // TODO for HashTable: also remove value. } -Object *HashTable::getKey (Object *key) +// 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(key); + int h = calcHashValue(object); for (Node *n = table[h]; n; n = n->next) { - if (key->equals(n->key)) - return n->key; + if (object->equals(n->object)) + return n->object; } return NULL; -} +}*/ -HashTable::HashTableIterator::HashTableIterator(HashTable *table) +HashSet::HashSetIterator::HashSetIterator(HashSet *set) { - this->table = table; + this->set = set; node = NULL; pos = -1; gotoNext(); } -void HashTable::HashTableIterator::gotoNext() +void HashSet::HashSetIterator::gotoNext() { if (node) node = node->next; while (node == NULL) { - if (pos >= table->tableSize - 1) + if (pos >= set->tableSize - 1) return; pos++; - node = table->table[pos]; + node = set->table[pos]; } } -Object *HashTable::HashTableIterator::getNext() +Object *HashSet::HashSetIterator::getNext() { Object *result; if (node) - result = node->key; + result = node->object; else result = NULL; @@ -457,14 +473,98 @@ Object *HashTable::HashTableIterator::getNext() return result; } -bool HashTable::HashTableIterator::hasNext() +bool HashSet::HashSetIterator::hasNext() { return node != NULL; } -Collection0::AbstractIterator* HashTable::createIterator() +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) { - return new HashTableIterator(this); + Node *node = findNode(key); + if (node) + return ((KeyValuePair*)node)->value; + else + return NULL; } // ----------- -- cgit v1.2.3