{*************************************************
 * HASHTREE.PAS - Last revised: 20/Jan/2001      *
 *                                               *
 * Manipula una tabla hash con arboles binarios. *
 *************************************************}

program HashStructures;
uses crt;
const
     {maximo numero de casillas en la tabla hash}
     MAX = 7;
type
    {Tipo de registro que nos interesa almacenar en la tabla}
    RecType = record
            key : String;
            name : String;
            phone : String;
    end;

    {Estructura del arbol binario}
    LeafPtr = ^Leaf;
    Leaf = record
         info : RecType;
         left : LeafPtr;
         right : LeafPtr;
    end;

    {usaremos arboles binarios para manejar colisiones}
    HashTable = Array [1..MAX] of LeafPtr;

    {Todos los indices posibles para accesar nuestra tabla}
    Index = 1..MAX;

Var
   {Tabla hash que guarda la informacion de las personas}
   people : HashTable;

   {la opcion del menu principal}
   op : char;

{ procedimiento recursivo que agrega una hoja al arbol binario
  especificado. Para ordenar el arbol se uso el valor ascii
  de los caracteres de la llave (o sea "Ace" es menor que "Klm"). }
procedure InsertTree (var ptr:LeafPtr; element:RecType);
var
   newPtr : LeafPtr;
begin
     if (ptr = nil) then
     begin
          new(newPtr);
          newPtr^.left:= nil;
          newPtr^.right:= nil;
          newPtr^.info:= element;
          ptr:= newPtr;
     end
     else
          if (element.key < ptr^.info.key) then
             InsertTree(ptr^.left, element)
          else
             InsertTree(ptr^.right, element);
end;

{ funcion recursiva que encuentra la hoja en un arbol binario que
  contiene al elemento con la llave especificada.
  Si lo encuentra devuelve un puntero a la hoja correspondiente,
  sino devuelve "nil".                                            }
function SeekTree (ptr:LeafPtr; key:String): LeafPtr;
begin
     if (ptr = nil) then
        SeekTree:= nil
     else
         if (key = ptr^.info.key) then
            SeekTree:= ptr
         else
             if (key < ptr^.info.key) then
                SeekTree:= SeekTree(ptr^.left, key)
             else
                SeekTree:= SeekTree(ptr^.right, key);
end;

{ procedimiento recursivo que libera la memoria de un arbol entero. }
procedure FreeMem (var ptr:LeafPtr );
begin
     if (ptr <> nil) then
     begin
          FreeMem(ptr^.left);
          FreeMem(ptr^.right);
          dispose(ptr);
     end;
end;

{ La funcion Hash. Indica en que posicion de la tabla debe colocarse
  la llave especificada. Toma un valor entre 1 y MAX. En este caso
  la llave es String y sumamos el valor ascii al cuadrado de cada uno
  de sus caracteres.                                                 }
function Hash(var key : String):Index;
var
   i, len, sum : Byte;
begin
     sum:= 0;
     len:= Length(key);
     for i:= 1 to len do
          sum:= sum + sqr(ord(key[i]));
     { "sum" resulta en un numero enorme, haciendo Modulo a MAX
        se obtiene un resultado adecuado entre 0 y MAX-1. Le sumamos
        1 para estar en el rango 1..MAX.                            }
     Hash:= (sum mod Max) + 1;
end;

{ Procedimiento que inicializa una tabla hash.
  Apunta todas sus casillas a 'nil' simbolizando que todos los
  arboles estan vacios.                                       }
procedure InitHash (var table:HashTable );
var
   i : Index;
begin
     for i:= 1 to MAX do
     begin
          { En caso de que no este vacio el arbol, liberamos su memoria.
            Buen habito para que no se trave la maquina por
            falta de memoria!                                           }
          FreeMem(table[i]);
          table[i]:= nil;
     end;
end;

{ Verifica si la llave ya esta ingresada en la tabla hash. }
function ExistsElement (var table:HashTable; key : String): Boolean;
var
   p : Index;
begin
     p:= Hash (key);
     { Si la funcion "SeekTre(...)" devuelve "nil", no existe, y viceversa. }
     ExistsElement:= SeekTree(table[p], key) <> nil;
end;

{ agrega un elemento a la tabla hash especificada. Si ya existe el
  elemento en la tabla (o tiene llave duplicada), despliega un mensaje
  de ERROR y no lo ingresa.                                           }
procedure InsertHash (var table:HashTable; element:RecType);
var
   p : Index;
begin
     if (ExistsElement(table, element.key)) then
     begin
          writeln;
          writeln('*** ERROR: La llave ', element.key,
                  ' ya existe en la estructura. ***');
          writeln('*** No se ingresara el registro: ', element.key,
                  ', ', element.name, ', ', element.phone, ' ***');
     end
     else
     begin
          p:= Hash (element.key);
          { como cada casilla de la tabla hash es la raiz de un arbol,
            simplemente se inserta el elemento en el arbol deseado    }
          InsertTree(table[p], element);
     end;
end;

{ Devuelve un puntero a una hoja que contiene la llave especifida. }
function GetElement (var table:HashTable; key:String): LeafPtr;
var
   p : Index;
begin
     p:= Hash(key);
     GetElement:= SeekTree(table[p], key);
end;

{ Inicializa la tabla especificada (perdiendo los valores anteriores),
  y carga todos los registros en un archivo separado por comas a la tabla.
  La estructura de los registros en el archivo debe ser:
  - <llave>,<nombre>,<telefono>
  el primer caracter de la linea se toma como el primer caracter de la
  llave, o sea que no debe haber espacio (ni cualquier otro caracter) al
  principio de la linea, y el telefono termina hasta que encuentre el
  final de la linea. Vea "people.csv" para un ejemplo.                   }
procedure LoadFileToHash (var table:HashTable);
var
   filePtr : Text;
   input, key, name, phone, fileName : String;
   len, coma, secondComa : Integer;
   element : RecType;
begin
     InitHash(table);
     Write('Ingrese nombre del archivo a cargar: ');
     Readln(fileName);
     Write('Cargando ', fileName, '... ');

     { Solo por preciona ENTER sin escribir algo. Si no hacemos esto y
       el usuario ingresa hilera vacia, se toma como archivo de entrada
       INPUT, o sea el teclado.                                        }
     if (fileName = '') then
     begin
          Writeln('No existe el archivo');
          exit;
     end;

     assign(filePtr, fileName);
     reset(filePtr);
     while (not EOF(filePtr)) Do
     begin
          Readln(filePtr, input);

          { obtenemos la llave de la linea "input" leida del archivo. }
          len:= Length(input);
          coma:= Pos (',',input);
          key:= copy(input,1,coma-1);

          { obtenemos el nombre. }
          input:= copy(input, coma+1, len-coma);
          len:= Length(input);
          coma:= Pos (',',input);
          name:= copy(input,1,coma-1);

          { obtenemos el telefono. }
          phone:= copy(input, coma+1, len-coma);

          {creamos un nuevo registro para agregarlo a la tabla. }
          element.key:= key;
          element.name:= name;
          element.phone:= phone;
          InsertHash(table, element);
     end;
     writeln('[Ok]');
end;

{ Solo sirve para que el usuario pueda leer el output comodamente. }
procedure WaitForKeyPress;
var
   trash : char;
begin
     writeln('Presione cualquier tecla para continuar...');
     trash:= Readkey;
     { si el usuario apacho F1,F2,...,F12, Flecha Arriba, Flecha Abajo, etc
       ReadKey devuelve #0 y espera un segundo ReadKey para devolver el
       codigo extendido. Simplemente hacemos otro ReadKey para vaciar el
       "buffer", si no lo hacemos, se queda basura en el buffer y al hacer
       otro ReadKey podria causar problemas.                               }
     if (trash = #0) then
        trash:= Readkey;
end;

{ Interactua con el usuario para desplegar la informacion de un elemento
  (o sea los datos de la persona, en este caso) en la tabla hash.
  Se le pide la llave del elemento para poder encontrarlo.              }
procedure FindInHash (var table:HashTable);
var
   key : String;
   ptr : LeafPtr;
begin
     Write('Ingrese llave a buscar: ');
     Readln(key);
     ptr:= GetElement(table,key);
     if (ptr = nil) then
        writeln('No se encontro ningun elemento.')
     else
         with ptr^.info do
         begin
              writeln('--- Datos --- ');
              writeln('Llave: ', key);
              writeln('Nombre: ', name);
              writeln('Telefono: ', phone);
              writeln('------------- ');
         end;
     WaitForKeyPress;
end;

{ Interactua con el usuario para Modificar la informacion de un elemento
  en la tabla hash. Se le pide la llave del elemento para poder encontrarlo. }
procedure ModifyHash (var table:HashTable);
var
   key, name, phone : String;
   ptr : LeafPtr;
   opcion : Char;
begin
     Write('Ingrese llave a buscar: ');
     Readln(key);
     ptr:= GetElement(table,key);
     if (ptr = nil) then
        { si no lo encuentra, no lo podemos modificar }
        writeln('No se encontro ningun elemento.')
     else
     begin
         { mustra la informacion actual }
         with ptr^.info do
         begin
              writeln('--- Datos --- ');
              writeln('Llave: ', key);
              writeln('Nombre: ', name);
              writeln('Telefono: ', phone);
              writeln('------------- ');
         end;
         { Menu para modificar los atributos Nombre y Telefono. NOTE que
           la llave NO SE PUEDE MODIFICAR (quebraria nuestra estructura).
           Le pide al usuario que ingrese una opcion valida, si ingresa
           una opcion erronea, no continua.                              }
         repeat
               writeln('--- Que dato quiere modificar: ---');
               writeln('1. Nombre');
               writeln('2. Telefono');
               writeln('3. Ninguno');
               Write('Ingrese opcion: ');
               opcion:= ReadKey;
               writeln(opcion);
               case opcion of
                    '1' : begin
                               write('Ingrese nuevo nombre: ');
                               Readln(name);
                               ptr^.info.name:= name;
                               writeln('Nombre cambiado exitosamente.');
                          end;
                    '2' : begin
                               write('Ingrese nuevo telefono: ');
                               Readln(phone);
                               ptr^.info.phone:= phone;
                               writeln('Telefono cambiado exitosamente.');
                          end;
                    '3' : writeln('Modificacion Cancelada.');
                    else writeln('Opcion invalida, pruebe de nuevo...');
               end;
         until opcion in ['1'..'3'];
     end;
     WaitForKeyPress;
end;


{--- Programa Principal ---}
begin
     ClrScr;
     InitHash(people);
     { Menu principal }
     Repeat
           Writeln;
           Writeln('*** Manipulacion de la Tabla Hash ***');
           Writeln('1. Cargar archivo');
           Writeln('2. Buscar elemento');
           Writeln('3. Modificar elemento');
           Writeln('4. Salir');
           Write('Ingrese opcion: ');
           op:= ReadKey;
           Writeln(Op);
           case op of
                '1' : LoadFileToHash(people);
                '2' : FindInHash(people);
                '3' : ModifyHash(people);
                '4' : Writeln('Adios!');
                else Writeln('*** Opcion invalida, pruebe de nuevo... ***');
           end;
     until op = '4';
end.