%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 1995-2000, 2003-2007, 2011 The University of Melbourne.
% Copyright (C) 2014-2019, 2021, 2023-2026 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: rbtree.m.
% Main author: petdr.
% Stability: high.
%
% The file implements the 'map' abstract data type using red/black trees,
% a version of binary search trees that ensures that the tree always stays
% roughly in balance.
%
%--------------------------------------------------%
%--------------------------------------------------%
:- module rbtree.
:- interface.
:- import_module assoc_list.
:- import_module list.
%--------------------------------------------------%
:- type rbtree(K, V).
% Initialise the data structure.
%
:- func init = rbtree(K, V).
:- pred init(rbtree(K, V)::uo) is det.
% Check whether a tree is empty.
%
:- pred is_empty(rbtree(K, V)::in) is semidet.
% Initialise an rbtree containing the given key-value pair.
%
:- func singleton(K, V) = rbtree(K, V).
% Inserts a new key-value pair into the tree.
% Fails if the key is already in the tree.
%
:- pred insert(K::in, V::in, rbtree(K, V)::in, rbtree(K, V)::out) is semidet.
% Updates the value associated with the given key.
% Fails if the key is not already in the tree.
%
:- pred update(K::in, V::in, rbtree(K, V)::in, rbtree(K, V)::out) is semidet.
% Update the value for the given key by applying the given transformation
% to the old value. Fails if the key is not already in the tree.
% This is faster than first searching for the value and then updating it.
%
:- pred transform_value(pred(V, V)::in(pred(in, out) is det), K::in,
rbtree(K, V)::in, rbtree(K, V)::out) is semidet.
% Sets a value regardless of whether key exists or not.
%
:- func set(rbtree(K, V), K, V) = rbtree(K, V).
:- pred set(K::in, V::in, rbtree(K, V)::in, rbtree(K, V)::out) is det.
% Insert a duplicate key into the tree.
%
% Note: search does not support looking for duplicate keys.
%
:- func insert_duplicate(rbtree(K, V), K, V) = rbtree(K, V).
:- pred insert_duplicate(K::in, V::in,
rbtree(K, V)::in, rbtree(K, V)::out) is det.
:- pred member(rbtree(K, V)::in, K::out, V::out) is nondet.
% Search for the value stored with the given the key.
% Fails if the key is not in the tree.
%
:- pred search(rbtree(K, V)::in, K::in, V::out) is semidet.
% Looks up the value stored with the given the key.
% Throws an exception if the key is not in the tree.
%
:- func lookup(rbtree(K, V), K) = V.
:- pred lookup(rbtree(K, V)::in, K::in, V::out) is det.
% Search for a key-value pair using the key. If there is no entry
% for the given key, returns the pair for the next lower key instead.
% Fails if there is no key with the given or lower value.
%
:- pred lower_bound_search(rbtree(K, V)::in, K::in, K::out, V::out)
is semidet.
% Search for a key-value pair using the key. If there is no entry
% for the given key, returns the pair for the next lower key instead.
% Throws an exception if there is no key with the given or lower value.
%
:- pred lower_bound_lookup(rbtree(K, V)::in, K::in, K::out, V::out) is det.
% Search for a key-value pair using the key. If there is no entry
% for the given key, returns the pair for the next higher key instead.
% Fails if there is no key with the given or higher value.
%
:- pred upper_bound_search(rbtree(K, V)::in, K::in, K::out, V::out)
is semidet.
% Search for a key-value pair using the key. If there is no entry
% for the given key, returns the pair for the next higher key instead.
% Throws an exception if there is no key with the given or higher value.
%
:- pred upper_bound_lookup(rbtree(K, V)::in, K::in, K::out, V::out) is det.
% Delete the given key and its associated value from the tree.
% Do nothing if the key is not in the tree.
%
:- func delete(rbtree(K, V), K) = rbtree(K, V).
:- pred delete(K::in, rbtree(K, V)::in, rbtree(K, V)::out) is det.
% Delete the given key and its associated value from the tree.
% Fail if the key is not in the tree.
%
:- pred remove(K::in, V::out, rbtree(K, V)::in, rbtree(K, V)::out)
is semidet.
% Deletes the node with the minimum key from the tree,
% and returns the key and value fields.
%
:- pred remove_smallest(K::out, V::out,
rbtree(K, V)::in, rbtree(K, V)::out) is semidet.
% Deletes the node with the maximum key from the tree,
% and returns the key and value fields.
%
:- pred remove_largest(K::out, V::out,
rbtree(K, V)::in, rbtree(K, V)::out) is semidet.
% Returns an in-order list of all the keys in the rbtree.
%
:- func keys(rbtree(K, V)) = list(K).
:- pred keys(rbtree(K, V)::in, list(K)::out) is det.
% Returns a list of values such that the keys associated with the
% values are in-order.
%
:- func values(rbtree(K, V)) = list(V).
:- pred values(rbtree(K, V)::in, list(V)::out) is det.
% Count the number of elements in the tree.
%
:- func count(rbtree(K, V)) = int.
:- pred count(rbtree(K, V)::in, int::out) is det.
:- func ucount(rbtree(K, V)) = uint.
:- pred ucount(rbtree(K, V)::in, uint::out) is det.
:- func assoc_list_to_rbtree(assoc_list(K, V)) = rbtree(K, V).
:- pred assoc_list_to_rbtree(assoc_list(K, V)::in, rbtree(K, V)::out) is det.
:- func from_assoc_list(assoc_list(K, V)) = rbtree(K, V).
:- func rbtree_to_assoc_list(rbtree(K, V)) = assoc_list(K, V).
:- pred rbtree_to_assoc_list(rbtree(K, V)::in, assoc_list(K, V)::out)
is det.
:- func to_assoc_list(rbtree(K, V)) = assoc_list(K, V).
:- func foldl(func(K, V, A) = A, rbtree(K, V), A) = A.
:- pred foldl(pred(K, V, A, A), rbtree(K, V), A, A).
:- mode foldl(in(pred(in, in, in, out) is det), in, in, out) is det.
:- mode foldl(in(pred(in, in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldl(in(pred(in, in, di, uo) is det), in, di, uo) is det.
:- mode foldl(in(pred(in, in, in, out) is semidet), in, in, out)
is semidet.
:- mode foldl(in(pred(in, in, mdi, muo) is semidet), in, mdi, muo)
is semidet.
:- mode foldl(in(pred(in, in, di, uo) is semidet), in, di, uo)
is semidet.
:- pred foldl2(pred(K, V, A, A, B, B), rbtree(K, V), A, A, B, B).
:- mode foldl2(in(pred(in, in, in, out, in, out) is det),
in, in, out, in, out) is det.
:- mode foldl2(in(pred(in, in, in, out, mdi, muo) is det),
in, in, out, mdi, muo) is det.
:- mode foldl2(in(pred(in, in, in, out, di, uo) is det),
in, in, out, di, uo) is det.
:- mode foldl2(in(pred(in, in, di, uo, di, uo) is det),
in, di, uo, di, uo) is det.
:- mode foldl2(in(pred(in, in, in, out, in, out) is semidet),
in, in, out, in, out) is semidet.
:- mode foldl2(in(pred(in, in, in, out, mdi, muo) is semidet),
in, in, out, mdi, muo) is semidet.
:- mode foldl2(in(pred(in, in, in, out, di, uo) is semidet),
in, in, out, di, uo) is semidet.
:- pred foldl3(pred(K, V, A, A, B, B, C, C), rbtree(K, V),
A, A, B, B, C, C).
:- mode foldl3(in(pred(in, in, in, out, in, out, in, out) is det),
in, in, out, in, out, in, out) is det.
:- mode foldl3(in(pred(in, in, in, out, in, out, in, out) is semidet),
in, in, out, in, out, in, out) is semidet.
:- mode foldl3(in(pred(in, in, in, out, in, out, di, uo) is det),
in, in, out, in, out, di, uo) is det.
:- mode foldl3(in(pred(in, in, in, out, di, uo, di, uo) is det),
in, in, out, di, uo, di, uo) is det.
:- mode foldl3(in(pred(in, in, di, uo, di, uo, di, uo) is det),
in, di, uo, di, uo, di, uo) is det.
:- pred foldl_values(pred(V, A, A), rbtree(K, V), A, A).
:- mode foldl_values(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldl_values(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldl_values(in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode foldl_values(in(pred(in, in, out) is semidet), in, in, out) is semidet.
:- mode foldl_values(in(pred(in, mdi, muo) is semidet), in, mdi, muo)
is semidet.
:- mode foldl_values(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.
:- pred foldl2_values(pred(V, A, A, B, B), rbtree(K, V), A, A, B, B).
:- mode foldl2_values(in(pred(in, in, out, in, out) is det), in, in, out,
in, out) is det.
:- mode foldl2_values(in(pred(in, in, out, mdi, muo) is det), in, in, out,
mdi, muo) is det.
:- mode foldl2_values(in(pred(in, in, out, di, uo) is det), in, in, out,
di, uo) is det.
:- mode foldl2_values(in(pred(in, in, out, in, out) is semidet), in, in, out,
in, out) is semidet.
:- mode foldl2_values(in(pred(in, in, out, mdi, muo) is semidet), in, in, out,
mdi, muo) is semidet.
:- mode foldl2_values(in(pred(in, in, out, di, uo) is semidet), in, in, out,
di, uo) is semidet.
:- func foldr(func(K, V, A) = A, rbtree(K, V), A) = A.
:- pred foldr(pred(K, V, A, A), rbtree(K, V), A, A).
:- mode foldr(in(pred(in, in, in, out) is det), in, in, out) is det.
:- mode foldr(in(pred(in, in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldr(in(pred(in, in, di, uo) is det), in, di, uo) is det.
:- mode foldr(in(pred(in, in, in, out) is semidet), in, in, out) is semidet.
:- mode foldr(in(pred(in, in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldr(in(pred(in, in, di, uo) is semidet), in, di, uo) is semidet.
:- pred foldr2(pred(K, V, A, A, B, B), rbtree(K, V), A, A, B, B).
:- mode foldr2(in(pred(in, in, in, out, in, out) is det),
in, in, out, in, out) is det.
:- mode foldr2(in(pred(in, in, in, out, mdi, muo) is det),
in, in, out, mdi, muo) is det.
:- mode foldr2(in(pred(in, in, in, out, di, uo) is det),
in, in, out, di, uo) is det.
:- mode foldr2(in(pred(in, in, di, uo, di, uo) is det),
in, di, uo, di, uo) is det.
:- mode foldr2(in(pred(in, in, in, out, in, out) is semidet),
in, in, out, in, out) is semidet.
:- mode foldr2(in(pred(in, in, in, out, mdi, muo) is semidet),
in, in, out, mdi, muo) is semidet.
:- mode foldr2(in(pred(in, in, in, out, di, uo) is semidet),
in, in, out, di, uo) is semidet.
:- pred foldr_values(pred(V, A, A), rbtree(K, V), A, A).
:- mode foldr_values(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldr_values(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldr_values(in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode foldr_values(in(pred(in, in, out) is semidet), in, in, out) is semidet.
:- mode foldr_values(in(pred(in, mdi, muo) is semidet), in, mdi, muo)
is semidet.
:- mode foldr_values(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.
:- func map_values(func(K, V1) = V2, rbtree(K, V1)) = rbtree(K, V2).
:- pred map_values(pred(K, V1, V2), rbtree(K, V1), rbtree(K, V2)).
:- mode map_values(in(pred(in, in, out) is det), in, out) is det.
:- mode map_values(in(pred(in, in, out) is semidet), in, out) is semidet.
%--------------------------------------------------%
%--------------------------------------------------%