43 multi_map
%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%--------------------------------------------------%
% Copyright (C) 1995, 1997, 2000, 2002-2006, 2011 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: multi_map.m.
% Main author: dylan. Based on map.m, by fjh, conway.
% Stability: low.
%
% This file provides the 'multi_map' ADT.
% A map (also known as a dictionary or an associative array) is a collection
% of (Key, Data) pairs which allows you to look up any Data item given the
% Key. A multi_map is similar, though allows a one to many relationship
% between keys and data.
%
% This is implemented almost as a special case of map.m.
%
%--------------------------------------------------%
%--------------------------------------------------%
:- module multi_map.
:- interface.
:- import_module assoc_list.
:- import_module list.
:- import_module map.
:- import_module set.
%--------------------------------------------------%
:- type multi_map(Key, Data) == map(Key, list(Data)).
%--------------------------------------------------%
% Initialize an empty multi_map.
%
:- func multi_map.init = multi_map(_, _).
:- pred multi_map.init(multi_map(_, _)::uo) is det.
% Check whether a multi_map is empty.
%
:- pred multi_map.is_empty(multi_map(_, _)::in) is semidet.
% Check whether multi_map contains key.
%
:- pred multi_map.contains(multi_map(K, _V)::in, K::in) is semidet.
:- pred multi_map.member(multi_map(K, V)::in, K::out, V::out) is nondet.
% Search multi_map for given key.
%
:- pred multi_map.search(multi_map(K, V)::in, K::in, list(V)::out) is semidet.
% Search multi_map for given key.
%
:- pred multi_map.nondet_search(multi_map(K, V)::in, K::in, V::out) is nondet.
% Search multi_map for key, but abort if search fails.
%
:- func multi_map.lookup(multi_map(K, V), K) = list(V).
:- pred multi_map.lookup(multi_map(K, V)::in, K::in, list(V)::out) is det.
% Search multi_map for key.
%
:- pred multi_map.nondet_lookup(multi_map(K, V)::in, K::in, V::out) is nondet.
% Search multi_map for data.
%
:- pred multi_map.inverse_search(multi_map(K, V)::in, V::in, K::out) is nondet.
% Insert a new key and corresponding value into a multi_map.
% Fail if the key already exists.
%
:- pred multi_map.insert(K::in, V::in,
multi_map(K, V)::in, multi_map(K, V)::out) is semidet.
% Insert a new key and corresponding value into a multi_map.
% Aborts if the key already exists.
%
:- func multi_map.det_insert(multi_map(K, V), K, V) = multi_map(K, V).
:- pred multi_map.det_insert(K::in, V::in,
multi_map(K, V)::in, multi_map(K, V)::out) is det.
% Update (add) the value corresponding to a given key.
% Fails if the key does not already exist.
%
:- pred multi_map.update(K::in, V::in,
multi_map(K, V)::in, multi_map(K, V)::out) is semidet.
% Update (add) the value corresponding to a given key.
% Aborts if the key does not already exist.
%
:- func multi_map.det_update(multi_map(K, V), K, V) = multi_map(K, V).
:- pred multi_map.det_update(K::in, V::in,
multi_map(K, V)::in, multi_map(K, V)::out) is det.
% Update (replace) the value corresponding to a given key.
% Fails if the key does not already exist.
%
:- pred multi_map.replace(K::in, list(V)::in,
multi_map(K, V)::in, multi_map(K, V)::out) is semidet.
% Update (replace) the value corresponding to a given key.
% Aborts if the key does not already exist.
%
:- func multi_map.det_replace(multi_map(K, V), K, list(V)) = multi_map(K, V).
:- pred multi_map.det_replace(K::in, list(V)::in,
multi_map(K, V)::in, multi_map(K, V)::out) is det.
% Update (add) value if the key is already present, otherwise
% insert the new key and value.
%
:- func multi_map.set(multi_map(K, V), K, V) = multi_map(K, V).
:- pred multi_map.set(K::in, V::in,
multi_map(K, V)::in, multi_map(K, V)::out) is det.
:- func multi_map.add(multi_map(K, V), K, V) = multi_map(K, V).
:- pred multi_map.add(K::in, V::in,
multi_map(K, V)::in, multi_map(K, V)::out) is det.
% Given a multi_map, return a list of all the keys in the multi_map.
%
:- func multi_map.keys(multi_map(K, _V)) = list(K).
:- pred multi_map.keys(multi_map(K, _V)::in, list(K)::out) is det.
% Given a multi_map, return a list of all the data values in the
% multi_map.
%
:- func multi_map.values(multi_map(_K, V)) = list(V).
:- pred multi_map.values(multi_map(_K, V)::in, list(V)::out) is det.
% Convert a multi_map to an association list.
%
:- func multi_map.to_flat_assoc_list(multi_map(K, V)) = assoc_list(K, V).
:- pred multi_map.to_flat_assoc_list(multi_map(K, V)::in,
assoc_list(K, V)::out) is det.
% Convert an association list to a multi_map.
%
:- func multi_map.from_flat_assoc_list(assoc_list(K, V)) = multi_map(K, V).
:- pred multi_map.from_flat_assoc_list(assoc_list(K, V)::in,
multi_map(K, V)::out) is det.
% Convert a multi_map to an association list, with all the
% values for each key in one element of the association list.
%
:- func multi_map.to_assoc_list(multi_map(K, V)) = assoc_list(K, list(V)).
:- pred multi_map.to_assoc_list(multi_map(K, V)::in,
assoc_list(K, list(V))::out) is det.
% Convert an association list with all the values for each
% key in one element of the list to a multi_map.
%
:- func multi_map.from_assoc_list(assoc_list(K, list(V))) = multi_map(K, V).
:- pred multi_map.from_assoc_list(assoc_list(K, list(V))::in,
multi_map(K, V)::out) is det.
% Convert a sorted association list to a multi_map.
%
:- func multi_map.from_sorted_assoc_list(assoc_list(K, list(V)))
= multi_map(K, V).
:- pred multi_map.from_sorted_assoc_list(assoc_list(K, list(V))::in,
multi_map(K, V)::out) is det.
% Delete a key and data from a multi_map
% if the key is not present, leave the multi_map unchanged.
%
:- func multi_map.delete(multi_map(K, V), K) = multi_map(K, V).
:- pred multi_map.delete(K::in,
multi_map(K, V)::in, multi_map(K, V)::out) is det.
% Delete a data value from a key in a multi_map
% if the key is not present, leave the multi_map unchanged.
%
:- func multi_map.delete(multi_map(K, V), K, V) = multi_map(K, V).
:- pred multi_map.delete(K::in, V::in,
multi_map(K, V)::in, multi_map(K, V)::out) is det.
% Delete a key-value pair from a multi_map and return the value.
% Fails if the key is not present.
%
:- pred multi_map.remove(K::in, list(V)::out,
multi_map(K, V)::in, multi_map(K, V)::out) is semidet.
% Delete a key-value pair from a multi_map and return the value.
% Aborts if the key is not present.
%
:- pred multi_map.det_remove(K::in, list(V)::out,
multi_map(K, V)::in, multi_map(K, V)::out) is det.
% Count the number of elements (keys) in the multi_map.
%
:- func multi_map.count(multi_map(K, V)) = int.
:- pred multi_map.count(multi_map(K, V)::in, int::out) is det.
% Count the number of data elements in the multi_map.
%
:- func multi_map.all_count(multi_map(K, V)) = int.
:- pred multi_map.all_count(multi_map(K, V)::in, int::out) is det.
% Convert a pair of lists (which must be of the same length)
% to a multi_map.
%
:- func multi_map.from_corresponding_lists(list(K), list(V))
= multi_map(K, V).
:- pred multi_map.from_corresponding_lists(list(K)::in, list(V)::in,
multi_map(K, V)::out) is det.
% Convert a pair of lists (which must be of the same length)
% to a multi_map.
%
:- func multi_map.from_corresponding_list_lists(list(K), list(list(V)))
= multi_map(K, V).
:- pred multi_map.from_corresponding_list_lists(list(K)::in, list(list(V))::in,
multi_map(K, V)::out) is det.
% multi_map.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 corresponding to that key from `MultiMapA' and
% `MultiMapB'.
%
:- func multi_map.merge(multi_map(K, V), multi_map(K, V))
= multi_map(K, V).
:- pred multi_map.merge(multi_map(K, V)::in, multi_map(K, V)::in,
multi_map(K, V)::out) is det.
% multi_map.select takes a multi_map and a set of keys and returns
% a multi_map containing the keys in the set and their corresponding
% values.
%
:- func multi_map.select(multi_map(K, V), set(K)) = multi_map(K, V).
:- pred multi_map.select(multi_map(K, V)::in, set(K)::in,
multi_map(K, V)::out) is det.
% Given a list of keys, produce a list of their values in a
% specified multi_map.
%
:- func multi_map.apply_to_list(list(K), multi_map(K, V)) = list(V).
:- pred multi_map.apply_to_list(list(K)::in, multi_map(K, V)::in,
list(V)::out) is det.
% Declaratively, a NOP.
% Operationally, a suggestion that the implementation
% optimize the representation of the multi_map in the expectation
% of a number of lookups but few or no modifications.
%
:- func multi_map.optimize(multi_map(K, V)) = multi_map(K, V).
:- pred multi_map.optimize(multi_map(K, V)::in, multi_map(K, V)::out) is det.
% Remove the smallest item from the multi_map.
% Fails if the multi_map is empty.
%
:- pred multi_map.remove_smallest(K::out, list(V)::out,
multi_map(K, V)::in, multi_map(K, V)::out) is semidet.
%--------------------------------------------------%
%--------------------------------------------------%