/* --- Copyright University of Sussex 1989. All rights reserved. ----------
 > File:            $poplocal/local/plog/lib/hash_table.pl
 > Purpose:         Hash tables in Prolog (with some multi-language code)
 > Author:          Tom Khabaza, Jun 13 1989
 > Documentation:   PLOGHELP * HASH_TABLE
 > Related Files:   HELP * USEFUL, SHOWLIB * USEFUL
 */

% Hash tables in Prolog:
%                     
% Prolog is capable of implementing hash tables except for the fact                   
% that it has no updatable "vector" data type.  This problem is                   
% circumvented by using Poplog's multi-language facility to create                   
% an updating version of arg/3.                   
%                     
% Another minor use of the multi-language ability if to get at various                   
% characters in an atom, and its length, quickly in computing the hash                   
% code for atoms.  The hash coding is:                   
%     For an integer N, hash code is N modulo the size of the table                   
%     For an atom A, hash code is ((first char of A) + (last char of A)                   
%     + (length of A)) modulo the size of the table.                   
% Only words and integers are allowed as keys.                   


:- library(useful).     % Needs member/2

:- prolog_language(pop11).

/* Procedure for updating the Nth argument of a term from Prolog.
 * Takes same arguments as arg/3.
 */

define constant procedure prolog_update_arg(index, term, value, contin);
    lvars term index value contin;
    value -> prolog_arg_nd(prolog_deref(index), prolog_deref(term));
    contin();
enddefine;

prolog_update_arg -> prolog_valof("update_arg", 3);

:- prolog_language(prolog).



% Delete all copies of an item from a list

hash_list_delete(Item, [], []) :- !.

hash_list_delete(Item, [Item|List], NewList) :- !,
    hash_list_delete(Item, List, NewList).

hash_list_delete(Item, [X|List], [X|NewList]) :-
    hash_list_delete(Item, List, NewList).



% Compute a hash code: takes key and the table size.

hash_code(Key, Table_size, Number) :-
    integer(Key), !,
    Number is Key mod Table_size.

hash_code(Key, Table_size, Number) :-
    atom(Key), !,
    First is subscrw(1,Key),
    Last is subscrw(datalength(Key),Key),
    Number is ((First + Last + datalength(Key)) mod Table_size) + 1.

hash_code(Key, _, _) :-
    error('Hash key must be an atom', [Key]).



% Create a new hash table: takes initial association list and table size.
% Make the table, initialise it with []s, and finally set up the supplied
% initial associations.

hash_table(Assoc, Size, Hash_table) :-
    functor(Table, t, Size),
    hash_set_nils(Size, Table),
    Hash_table = hash_table(Size,Table),
    hash_set_initial(Assoc, Hash_table).



% Set initial contents of all table entries to [].

hash_set_nils(0, _) :- !.
hash_set_nils(N, Table) :-
    update_arg(N, Table, []),
    N1 is N - 1,
    hash_set_nils(N1, Table).



% Set the value for a given key in the hash table
%   Get the hash code and get the relevant entry, then delete any old
%   value for this key, and insert the remaining entry with the new
%   association back into the table.

hash_set(Key, Value, hash_table(Size,Table)) :-
    hash_code(Key, Size, Code),
    arg(Code, Table, Entry),
    hash_list_delete([Key|_], Entry, NewEntry),
    update_arg(Code, Table, [[Key|Value] | NewEntry]).



% Get the value for a given key in the hash table
%   Get the hash code and get the relevant entry, then find a pair
%   in the entry that unifies with the given key and value.
%   Fail if not found.

hash_get(Key, Value, hash_table(Size,Table)) :-
    hash_code(Key, Size, Code),
    arg(Code, Table, Entry),
    member([Key|Value], Entry).



% Set up initial table with given association list

hash_set_initial([], _) :- !.

hash_set_initial([[Key,Value] | Assoc], Hash_table) :-
    hash_set(Key, Value, Hash_table),
    hash_set_initial(Assoc, Hash_table).
