%--------------------------------------------------%
% vim: ts=4 sw=4 et ft=mercury
%--------------------------------------------------%
% Copyright (C) 2020, 2022, 2024-2025 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: one_or_more_map.m.
% Stability: high.
%
% This file provides another version of the multi_map(K, V) abstract data type.
% A map (also known as a dictionary or an associative array) is a collection
% of (Key, Value) pairs which allows you to look up any Value given the Key.
% A multi_map is similar, but it allows more than one Value for each Key.
% A multi_map represents this by using list(V) as the range type, which works,
% but does not express the invariant maintained by the relevant operations,
% which is that these lists are never empty. A one_or_more_map is a multi_map
% in which the range type is not list(V) but one_or_more(V), which *does*
% express this invariant. Multiple occurrences of the same Value can be
% associated with a given Key.
%
%--------------------------------------------------%

:- module one_or_more_map.
:- interface.

:- import_module assoc_list.
:- import_module list.
:- import_module map.
:- import_module one_or_more.
:- import_module set.

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

:- type one_or_more_map(K, V) == map(K, one_or_more(V)).

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

    % Return an empty one_or_more_map.
    %
:- func init = one_or_more_map(K, V).
:- pred init(one_or_more_map(K, V)::uo) is det.

    % Check whether the one_or_more_map is empty.
    %
:- pred is_empty(one_or_more_map(K, V)::in) is semidet.

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

    % Check whether the one_or_more_map has an entry for the given key.
    %
:- pred contains(one_or_more_map(K, V)::in, K::in) is semidet.

    % Succeed once for each key-value pair in the one_or_more_map.
    %
:- pred member(one_or_more_map(K, V)::in, K::out, V::out) is nondet.

    % If the one_or_more_map has an entry for the given key, return the
    % list of corresponding values.
    %
:- pred search(one_or_more_map(K, V)::in, K::in, one_or_more(V)::out)
    is semidet.

    % If the one_or_more_map has an entry for the given key,
    % succeed once for each of the corresponding values.
    %
:- pred nondet_search(one_or_more_map(K, V)::in, K::in, V::out) is nondet.

    % If the one_or_more_map has an entry for the given key,
    % succeed once for each of the corresponding values.
    % Otherwise, throw an exception.
    %
:- func lookup(one_or_more_map(K, V), K) = one_or_more(V).
:- pred lookup(one_or_more_map(K, V)::in, K::in, one_or_more(V)::out) is det.

    % If the one_or_more_map has an entry for the given key,
    % succeed once for each of the corresponding values.
    % Otherwise, throw an exception.
    %
:- pred nondet_lookup(one_or_more_map(K, V)::in, K::in, V::out) is nondet.

    % If the one_or_more_map has an entry for keys with the given value,
    % succeed once for each of those keys.
    %
    % NOTE: The implementation of this predicate is necessarily inefficient,
    % and so this predicate is intended for non-performance-critical uses only.
    %
:- pred inverse_search(one_or_more_map(K, V)::in, V::in, K::out) is nondet.

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

    % Add the given key-value pair to the one_or_more_map.
    % Fail if the key already exists.
    %
:- pred insert(K::in, V::in,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is semidet.

    % Add the given key-value pair to the one_or_more_map.
    % Throw an exception if the key already exists.
    %
:- func det_insert(one_or_more_map(K, V), K, V) = one_or_more_map(K, V).
:- pred det_insert(K::in, V::in,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is det.

    % Add the given key-value pair to the one_or_more_map.
    % Fail if the key does not already exist.
    %
:- pred update(K::in, V::in,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is semidet.

    % Add the given key-value pair to the one_or_more_map.
    % Throw an exception if the key does not already exist.
    %
:- func det_update(one_or_more_map(K, V), K, V) = one_or_more_map(K, V).
:- pred det_update(K::in, V::in,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is det.

    % Replace the list of values corresponding to the given key.
    % Fails if the key does not already exist.
    %
:- pred replace(K::in, one_or_more(V)::in,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is semidet.

    % Replace the list of values corresponding to the given key.
    % Throws an exception if the key does not already exist.
    %
:- func det_replace(one_or_more_map(K, V), K,
    one_or_more(V)) = one_or_more_map(K, V).
:- pred det_replace(K::in, one_or_more(V)::in,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is det.

    % Add the given key-value pair to the one_or_more_map.
    % (`set' is a synonym for `add'.)
    %
:- func add(one_or_more_map(K, V), K, V) = one_or_more_map(K, V).
:- pred add(K::in, V::in,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is det.
:- func set(one_or_more_map(K, V), K, V) = one_or_more_map(K, V).
:- pred set(K::in, V::in,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is det.

    % Add the given value-key pair to the one_or_more_map.
    % (`reverse_set' is a synonym for `reverse_add'.)
    %
:- func reverse_add(one_or_more_map(K, V), V, K) = one_or_more_map(K, V).
:- pred reverse_add(V::in, K::in,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is det.
:- func reverse_set(one_or_more_map(K, V), V, K) = one_or_more_map(K, V).
:- pred reverse_set(V::in, K::in,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is det.

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

    % Delete a key and its corresponding values from a one_or_more_map.
    % If the key is not present, leave the one_or_more_map unchanged.
    %
:- func delete(one_or_more_map(K, V), K) = one_or_more_map(K, V).
:- pred delete(K::in,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is det.

    % Delete the given key-value pair from a one_or_more_map.
    % If the key is not present, leave the one_or_more_map unchanged.
    %
:- func delete(one_or_more_map(K, V), K, V) = one_or_more_map(K, V).
:- pred delete(K::in, V::in,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is det.

    % Delete a key from a one_or_more_map and return the list of values
    % previously corresponding to it.
    % Fail if the key is not present.
    %
:- pred remove(K::in, one_or_more(V)::out,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is semidet.

    % Delete a key from a one_or_more_map and return the list of values
    % previously corresponding to it.
    % Throw an exception if the key is not present.
    %
:- pred det_remove(K::in, one_or_more(V)::out,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is det.

    % Remove the smallest key and its corresponding values from the
    % one_or_more_map.
    % Fails if the one_or_more_map is empty.
    %
:- pred remove_smallest(K::out, one_or_more(V)::out,
    one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is semidet.

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

    % Select takes a one_or_more_map and a set of keys and returns
    % a one_or_more_map containing only the keys in the set,
    % together with their corresponding values.
    %
:- func select(one_or_more_map(K, V), set(K)) = one_or_more_map(K, V).
:- pred select(one_or_more_map(K, V)::in, set(K)::in,
    one_or_more_map(K, V)::out) is det.

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

    % merge(MultiMapA, MultiMapB, MultiMap):
    %
    % Merge MultiMapA and MultiMapB so that
    %
    % - if a key occurs in both MultiMapA and MultiMapB, then the values
    %   corresponding to that key in MultiMap will be the concatenation
    %   of the values to that key from MultiMapA and MultiMapB; while
    % - if a key occurs in only one of MultiMapA and MultiMapB, then
    %   the values corresponding to it in that map will be carried over
    %   to MultiMap.
    %
:- func merge(one_or_more_map(K, V), one_or_more_map(K, V))
    = one_or_more_map(K, V).
:- pred merge(one_or_more_map(K, V)::in, one_or_more_map(K, V)::in,
    one_or_more_map(K, V)::out) is det.

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

    % Declaratively, a no-operation.
    % Operationally, a suggestion that the implementation optimize
    % the representation of the one_or_more_map, in the expectation that the
    % following operations will consist of searches and lookups
    % but (almost) no updates.
    %
:- func optimize(one_or_more_map(K, V)) = one_or_more_map(K, V).
:- pred optimize(one_or_more_map(K, V)::in, one_or_more_map(K, V)::out) is det.

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

    % Convert a one_or_more_map to an association list.
    %
:- func to_flat_assoc_list(one_or_more_map(K, V)) = assoc_list(K, V).
:- pred to_flat_assoc_list(one_or_more_map(K, V)::in,
    assoc_list(K, V)::out) is det.

    % Convert an association list to a one_or_more_map.
    %
:- func from_flat_assoc_list(assoc_list(K, V)) = one_or_more_map(K, V).
:- pred from_flat_assoc_list(assoc_list(K, V)::in,
    one_or_more_map(K, V)::out) is det.

    % Convert a one_or_more_map to an association list, with all the values
    % for each key in one element of the association list.
    %
:- func to_assoc_list(one_or_more_map(K, V)) = assoc_list(K, one_or_more(V)).
:- pred to_assoc_list(one_or_more_map(K, V)::in,
    assoc_list(K, one_or_more(V))::out) is det.

    % Convert an association list with all the values for each key
    % in one element of the list to a one_or_more_map.
    %
:- func from_assoc_list(assoc_list(K, one_or_more(V))) = one_or_more_map(K, V).
:- pred from_assoc_list(assoc_list(K, one_or_more(V))::in,
    one_or_more_map(K, V)::out) is det.

    % Convert a sorted association list to a one_or_more_map.
    %
:- func from_sorted_assoc_list(assoc_list(K, one_or_more(V)))
    = one_or_more_map(K, V).
:- pred from_sorted_assoc_list(assoc_list(K, one_or_more(V))::in,
    one_or_more_map(K, V)::out) is det.

    % Convert the corresponding elements of a list of keys and a
    % list of values (which must be of the same length) to a one_or_more_map.
    % A key may occur more than once in the list of keys.
    % Throw an exception if the two lists are not the same length.
    %
:- func from_corresponding_lists(list(K), list(V))
    = one_or_more_map(K, V).
:- pred from_corresponding_lists(list(K)::in, list(V)::in,
    one_or_more_map(K, V)::out) is det.

    % Convert the corresponding elements of a list of keys and a
    % *list of lists* of values to a one_or_more_map.
    % A key may *not* occur more than once in the list of keys.
    % Throw an exception if the two lists are not the same length,
    % or if a key does occur more than once in the list of keys.
    %
:- func from_corresponding_list_lists(list(K), list(one_or_more(V)))
    = one_or_more_map(K, V).
:- pred from_corresponding_list_lists(list(K)::in, list(one_or_more(V))::in,
    one_or_more_map(K, V)::out) is det.

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

    % Given a list of keys, produce a list of their values in a
    % specified one_or_more_map.
    %
:- func apply_to_list(list(K), one_or_more_map(K, V)) = list(V).
:- pred apply_to_list(list(K)::in, one_or_more_map(K, V)::in, list(V)::out)
    is det.

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

    % Given a one_or_more_map, return a list of all the keys in it.
    %
:- func keys(one_or_more_map(K, V)) = list(K).
:- pred keys(one_or_more_map(K, V)::in, list(K)::out) is det.

    % Given a one_or_more_map, return a list of all the keys in it
    % in sorted order.
    %
:- func sorted_keys(one_or_more_map(K, V)) = list(K).
:- pred sorted_keys(one_or_more_map(K, V)::in, list(K)::out) is det.

    % Given a one_or_more_map, return a list of all the keys in it
    % as a set
    %
:- func keys_as_set(one_or_more_map(K, V)) = set(K).
:- pred keys_as_set(one_or_more_map(K, V)::in, set(K)::out) is det.

    % Given a one_or_more_map, return a list of all the values in it.
    %
:- func values(one_or_more_map(K, V)) = list(V).
:- pred values(one_or_more_map(K, V)::in, list(V)::out) is det.

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

    % Count the number of keys in the one_or_more_map.
    %
:- func count(one_or_more_map(K, V)) = int.
:- pred count(one_or_more_map(K, V)::in, int::out) is det.

    % Count the number of key-value pairs in the one_or_more_map.
    %
:- func all_count(one_or_more_map(K, V)) = int.
:- pred all_count(one_or_more_map(K, V)::in, int::out) is det.

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