Generalizar HashTable para almacenar void * como valores.

Esto elimina la restriccion de usar personas para la tabla hash. El motivo es
que vamos a querer usar hashes _dentro_ de la clase persona, y sino tenemos
una referencia circular molesta. Aparte en el futuro podemos querer usarla
para almacenar otras cosas.

diff --git a/src/hashtable.cpp b/src/hashtable.cpp
new file mode 100644 (file)
index 0000000..463d6d0
--- /dev/null
+++ b/src/hashtable.cpp
@@ -0,0 +1,55 @@
+#include "hashtable.h"
+
+/// Constructor
+HashTable::
+HashTable(size_type size):
+       table(size)
+{
+}
+
+/// Función de hash
+HashTable::size_type
+HashTable::
+hash(const std::string& val)
+{
+       size_type h = 0;
+       for (unsigned char* p = (unsigned char*)val.c_str(); *p != '\0';
+                       p++)
+       {
+               h = 37 * h + *p;
+       }
+       return h % table.size();
+}
+
+// Uso interno
+namespace
+{
+       /// Functor para encontrar pares con clave igual
+       struct ClaveIgualA
+       {
+               const std::string& clave;
+               ClaveIgualA(const std::string& clave): clave(clave) {}
+               bool operator()(const HashTable::pair_type& par)
+               {
+                       return par.first == clave;
+               }
+       };
+}
+
+/// Agrega entrada
+void *&
+HashTable::
+operator[](const std::string& key)
+{
+       size_type pos = hash(key);
+       list_type::iterator par = std::find_if(table[pos].begin(),
+                       table[pos].end(), ClaveIgualA(key));
+       if (par == table[pos].end()) // No encontrada
+       {
+               // La agrego
+               table[pos].push_back(pair_type(key, 0));
+               return table[pos].back().second;
+       }
+       else return par->second;
+}
+

diff --git a/src/hashtable.h b/src/hashtable.h
new file mode 100644 (file)
index 0000000..a6d284d
--- /dev/null
+++ b/src/hashtable.h
@@ -0,0 +1,41 @@
+#ifndef _HASHTABLE_H_
+#define _HASHTABLE_H_
+
+#include <utility>
+#include <vector>
+#include <string>
+#include <list>
+
+/// Tabla Hash (abierta)
+struct HashTable
+{
+
+       /// Tipo de dato para almacenar los pares clave, valor
+       typedef std::pair< std::string, void * > pair_type;
+
+       /// Tipo de dato para almacenar una lista de pares
+       typedef std::list< pair_type > list_type;
+
+       /// Tipo de dato para almacenar los pares
+       typedef std::vector< list_type > table_type;
+
+       /// Tipo de dato del tamaño del contenedor
+       typedef table_type::size_type size_type;
+
+       /// Constructor
+       HashTable(size_type size);
+
+       /// Función de hash
+       size_type hash(const std::string& val);
+
+       /// Agrega entrada
+       void *& operator[](const std::string& key);
+
+       protected:
+
+       /// Contenedor usado para implementar la tabla hash
+       table_type table;
+
+};
+
+#endif // _HASHTABLE_H_

diff --git a/src/susanita.cpp b/src/susanita.cpp
index da0df11dfd4f5b76ae5ceba9182a97426cadfed4..d143b836e9ce3335b11fb2e5f9725214be8d9915 100644 (file)
--- a/src/susanita.cpp
+++ b/src/susanita.cpp
@@ -50,7 +50,7 @@ Persona*
 Susanita::
 get_persona(const std::string& nombre)
 {
-       return nombres[nombre];
+       return (Persona *) nombres[nombre];
 }
 
 void