%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 2004-2006, 2010-2012 The University of Melbourne.
% Copyright (C) 2013-2015, 2017-2023 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: version_hash_table.m.
% Main author: rafe, wangp.
% Stability: low.
%
% (See the header comments in version_array.m for an explanation of version
% types.)
%
% Version hash tables. The "latest" version of the hash table provides
% roughly the same performance as the unique hash table implementation.
% "Older" versions of the hash table are still accessible, but will incur
% a performance penalty that grows as more updates are made to the hash table.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module version_hash_table.
:- interface.

:- import_module assoc_list.

%--------------------------------------------------%

:- type version_hash_table(K, V).

:- type hash_pred(K) == (pred(K,  int)).
:- inst hash_pred    == (pred(in, out) is det).

    % init(HashPred, N, MaxOccupancy):
    %
    % Construct a new hash table with initial size 2 ^ N that is doubled
    % whenever MaxOccupancy is achieved. Elements are indexed using HashPred.
    %
    % HashPred must compute a hash for a given key.
    % N must be greater than 0.
    % MaxOccupancy must be in (0.0, 1.0).
    %
    % XXX Values too close to the limits may cause bad things to happen.
    %
:- func init(hash_pred(K)::in(hash_pred), int::in, float::in) =
    (version_hash_table(K, V)::out) is det.

    % unsafe_init(HashPred, N, MaxOccupancy):
    %
    % Like init/3, but the constructed hash table is backed by a
    % non-thread-safe version array. It is unsafe to concurrently access
    % or update the hash table from different threads, or any two hash tables
    % which were produced from operations on the same original hash table.
    % However, if the hash table or its descendants will not be used in such a
    % manner, a non-thread-safe hash table can be much faster than a thread
    % safe one.
    %
:- func unsafe_init(hash_pred(K)::in(hash_pred), int::in, float::in) =
    (version_hash_table(K, V)::out) is det.

    % init_default(HashFn) constructs a hash table with default size and
    % occupancy arguments.
    %
:- func init_default(hash_pred(K)::in(hash_pred)) =
    (version_hash_table(K, V)::out) is det.

    % unsafe_init_default(HashFn)
    %
    % Like init_default/3 but the constructed hash table is backed by a
    % non-thread-safe version array. See the description of unsafe_init/3
    % above.
    %
:- func unsafe_init_default(hash_pred(K)::in(hash_pred)) =
    (version_hash_table(K, V)::out) is det.

    % Retrieve the hash_pred associated with a hash table.
    %
% :- func hash_pred(version_hash_table(K, V)) = hash_pred(K).

    % Return the number of buckets in a hash table.
    %
:- func num_buckets(version_hash_table(K, V)) = int.

    % Return the number of occupants in a hash table.
    %
:- func num_occupants(version_hash_table(K, V)) = int.

    % Copy the hash table explicitly.
    %
    % An explicit copy allows programmers to control the cost of copying
    % the table. For more information see the comments at the top of the
    % version_array module.
    %
    % This is not a deep copy: it copies only the structure.
    %
:- func copy(version_hash_table(K, V)) = version_hash_table(K, V).

    % Search for the value associated with the given key.
    % Fail if there is no entry for the key.
    %
:- func search(version_hash_table(K, V), K) = V is semidet.
:- pred search(version_hash_table(K, V)::in, K::in, V::out) is semidet.

    % Lookup the value associated with the given key.
    % Throw an exception if there is no entry for the key.
    %
:- func lookup(version_hash_table(K, V), K) = V.
:- pred lookup(version_hash_table(K, V)::in, K::in, V::out) is det.

    % Field access for hash tables.
    % `HT ^ elem(K)' is equivalent to `lookup(HT, K)'.
    %
:- func elem(K, version_hash_table(K, V)) = V.

    % Insert key-value binding into a hash table.
    % If one is already there, then overwrite the previous value.
    %
:- func set(version_hash_table(K, V), K, V) = version_hash_table(K, V).
:- pred set(K::in, V::in,
    version_hash_table(K, V)::in, version_hash_table(K, V)::out) is det.

    % Field update for hash tables.
    % `HT ^ elem(K) := V' is equivalent to `set(HT, K, V)'.
    %
:- func 'elem :='(K, version_hash_table(K, V), V) = version_hash_table(K, V).

    % Insert a key-value binding into a hash table.
    % Throw an exception if a binding for the key is already present.
    %
:- func det_insert(version_hash_table(K, V), K, V) = version_hash_table(K, V).
:- pred det_insert(K::in, V::in,
    version_hash_table(K, V)::in, version_hash_table(K, V)::out) is det.

    % Change a key-value binding in a hash table.
    % Throw exception if a binding for the key does not already exist.
    %
:- func det_update(version_hash_table(K, V), K, V) = version_hash_table(K, V).
:- pred det_update(K::in, V::in,
    version_hash_table(K, V)::in, version_hash_table(K, V)::out) is det.

    % Delete the entry for the given key. If there is no such entry,
    % leave the hash table unchanged.
    %
:- func delete(version_hash_table(K, V), K) = version_hash_table(K, V).
:- pred delete(K::in,
    version_hash_table(K, V)::in, version_hash_table(K, V)::out) is det.

    % Convert a hash table into an association list.
    %
:- func to_assoc_list(version_hash_table(K, V)) = assoc_list(K, V).

    % from_assoc_list(HashPred, N, MaxOccupancy, AssocList) = Table:
    %
    % Convert an association list into a hash table. The first three parameters
    % are the same as for init/3 above.
    %
:- func from_assoc_list(hash_pred(K)::in(hash_pred), int::in, float::in,
    assoc_list(K, V)::in) = (version_hash_table(K, V)::out) is det.

    % A simpler version of from_assoc_list/4, in which the values for N and
    % MaxOccupancy are configured with defaults such as in init_default/1
    %
:- func from_assoc_list(hash_pred(K)::in(hash_pred), assoc_list(K, V)::in) =
    (version_hash_table(K, V)::out) is det.

    % Fold a function over the key-value bindings in the given hash table.
    %
:- func fold(func(K, V, T) = T, version_hash_table(K, V), T) = T.

    % Fold a predicate over the key-value bindings in the given hash table.
    %
:- pred fold(pred(K, V, T, T), version_hash_table(K, V), T, T).
:- mode fold(in(pred(in, in, in, out) is det), in, in, out) is det.
:- mode fold(in(pred(in, in, mdi, muo) is det), in, mdi, muo) is det.
:- mode fold(in(pred(in, in, di, uo) is det), in, di, uo) is det.
:- mode fold(in(pred(in, in, in, out) is semidet), in, in, out) is semidet.
:- mode fold(in(pred(in, in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode fold(in(pred(in, in, di, uo) is semidet), in, di, uo) is semidet.

%--------------------------------------------------%

    % Test if two version_hash_tables are equal.
    % Unifications on the version_hash_table type are defined
    % by this predicate.
    %
:- pred equal(version_hash_table(K, V)::in, version_hash_table(K, V)::in)
    is semidet.
% This pragma is required because termination analysis can't analyse
% the use of higher order code.
:- pragma terminates(pred(equal/2)).

%--------------------------------------------------%
%--------------------------------------------------%