2 files changed, 239 insertions, 96 deletions

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 <http://www.gnu.org/licenses/>.
  */
 
-
+#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;
 }
 
 // -----------
diff --git a/lout/container.hh b/lout/container.hh
index d2484b13..f1008e82 100644
--- a/lout/container.hh
+++ b/lout/container.hh
@@ -179,46 +179,78 @@ public:
 
 
 /**
- * \brief A hash table.
+ * \brief A hash set.
  */
-class HashTable: public Collection
+class HashSet: public Collection
 {
-   friend class HashTableIterator;
+   friend class HashSetIterator;
 
-private:
+protected:
    struct Node
    {
-      object::Object *key, *value;
+      object::Object *object;
       Node *next;
    };
 
-   class HashTableIterator: public Collection0::AbstractIterator
+   Node **table;
+   int tableSize;
+   bool ownerOfObjects;
+
+   inline int calcHashValue(object::Object *object)
+   {
+      return abs(object->hashValue()) % tableSize;
+   }
+
+   virtual Node *createNode();
+   virtual void clearNode(Node *node);
+
+   Node *findNode(object::Object *object);
+   Node *insertNode(object::Object *object);
+
+   AbstractIterator* createIterator();
+
+private:
+   class HashSetIterator: public Collection0::AbstractIterator
    {
    private:
-      HashTable *table;
-      HashTable::Node *node;
+      HashSet *set;
+      HashSet::Node *node;
       int pos;
 
       void gotoNext();
 
    public:
-      HashTableIterator(HashTable *table);
+      HashSetIterator(HashSet *set);
       bool hasNext();
       Object *getNext();
    };
 
-   Node **table;
-   int tableSize;
-   bool ownerOfKeys, ownerOfValues;
+public:
+   HashSet(bool ownerOfObjects, int tableSize = 251);
+   ~HashSet();
 
+   void put (object::Object *object);
+   bool contains (object::Object *key);
+   bool remove (object::Object *key);
+   //Object *getReference (object::Object *object);
+};
+
+/**
+ * \brief A hash table.
+ */
+class HashTable: public HashSet
+{
 private:
-   inline int calcHashValue(object::Object *key)
+   bool ownerOfValues;
+
+   struct KeyValuePair: public Node
    {
-      return abs(key->hashValue()) % tableSize;
-   }
+      object::Object *value;
+   };
 
 protected:
-   AbstractIterator* createIterator();
+   Node *createNode();
+   void clearNode(Node *node);
 
 public:
    HashTable(bool ownerOfKeys, bool ownerOfValues, int tableSize = 251);
@@ -227,10 +259,7 @@ public:
    void intoStringBuffer(misc::StringBuffer *sb);
 
    void put (object::Object *key, object::Object *value);
-   bool contains (object::Object *key);
-   Object *get (object::Object *key);
-   bool remove (object::Object *key);
-   Object *getKey (Object *key);
+   object::Object *get (object::Object *key);
 };
 
 /**
@@ -328,6 +357,9 @@ protected:
    untyped::Collection *base;
 
 public:
+   Collection () { this->base = NULL; }
+   ~Collection () { if (this->base) delete this->base; }
+
    void intoStringBuffer(misc::StringBuffer *sb)
    { this->base->intoStringBuffer(sb); }
 
@@ -344,7 +376,6 @@ template <class T> class Vector: public Collection <T>
 public:
    inline Vector(int initSize, bool ownerOfObjects) {
       this->base = new untyped::Vector(initSize, ownerOfObjects); }
-   ~Vector() { delete this->base; }
 
    inline void put(T *newElement, int newPos = -1)
    { ((untyped::Vector*)this->base)->put(newElement, newPos); }
@@ -367,7 +398,6 @@ template <class T> class List: public Collection <T>
 public:
    inline List(bool ownerOfObjects)
    { this->base = new untyped::List(ownerOfObjects); }
-   ~List() { delete this->base; }
 
    inline void clear() { ((untyped::List*)this->base)->clear(); }
    inline void append(T *element)
@@ -388,28 +418,42 @@ public:
    { return (T*)((untyped::List*)this->base)->getLast(); }
 };
 
+/**
+ * \brief Typed version of container::untyped::HashSet.
+ */
+template <class T> class HashSet: public Collection <T>
+{
+protected:
+   inline HashSet() { }
+
+public:
+   inline HashSet(bool owner, int tableSize = 251)
+   { this->base = new untyped::HashSet(owner, tableSize); }
+
+   inline void put(T *object)
+   { return ((untyped::HashSet*)this->base)->put(object); }
+   inline bool contains(T *object)
+   { return ((untyped::HashSet*)this->base)->contains(object); }
+   inline bool remove(T *object)
+   { return ((untyped::HashSet*)this->base)->remove(object); }
+   //inline T *getReference(T *object)
+   //{ return (T*)((untyped::HashSet*)this->base)->getReference(object); }
+};
 
 /**
  * \brief Typed version of container::untyped::HashTable.
  */
-template <class K, class V> class HashTable: public Collection <K>
+template <class K, class V> class HashTable: public HashSet <K>
 {
 public:
    inline HashTable(bool ownerOfKeys, bool ownerOfValues, int tableSize = 251)
    { this->base = new untyped::HashTable(ownerOfKeys, ownerOfValues,
                                          tableSize); }
-   ~HashTable() { delete this->base; }
 
    inline void put(K *key, V *value)
    { return ((untyped::HashTable*)this->base)->put(key, value); }
-   inline bool contains(K *key)
-   { return ((untyped::HashTable*)this->base)->contains(key); }
    inline V *get(K *key)
    { return (V*)((untyped::HashTable*)this->base)->get(key); }
-   inline bool remove(K *key)
-   { return ((untyped::HashTable*)this->base)->remove(key); }
-   inline K *getKey(K *key)
-   { return (K*)((untyped::HashTable*)this->base)->getKey(key); }
 };
 
 /**
@@ -420,7 +464,6 @@ template <class T> class Stack: public Collection <T>
 public:
    inline Stack (bool ownerOfObjects)
    { this->base = new untyped::Stack (ownerOfObjects); }
-   ~Stack() { delete this->base; }
 
    inline void push (T *object) {
       ((untyped::Stack*)this->base)->push (object); }