%--------------------------------------------------%
% 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 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: rbtree.m.
% Main author: petdr.
% Stability: medium.
%
% Contains an implementation of red black trees.
%
% *** Exit conditions of main predicates ***
% insert:
% fails if key already in tree.
% update:
% changes value of key already in tree. fails if key doesn't exist.
% transform_value:
% looks up an existing value in the tree, applies a transformation to the
% value and then updates the value. fails if the key doesn't exist.
% set:
% inserts or updates. Never fails.
%
% insert_duplicate:
% inserts duplicate keys into the tree, never fails. Search doesn't
% yet support looking for duplicates.
%
% delete:
% deletes a node from the tree if it exists.
% remove:
% fails if node to remove doesn't exist in the tree.
%
% lookup:
% Throws an exception if key looked up doesn't exist.
% search:
% Fails if key looked up doesn't exist.
%
%--------------------------------------------------%
%--------------------------------------------------%
:- module rbtree.
:- interface.
:- import_module assoc_list.
:- import_module list.
%--------------------------------------------------%
:- type rbtree(Key, Value).
% 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 key 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 a key.
% Fails if the key does not exist.
%
:- pred update(K::in, V::in, rbtree(K, V)::in, rbtree(K, V)::out) is semidet.
% Update the value at the given key by applying the supplied
% transformation to it. Fails if the key is not found. 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.
%
:- 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 a key-value pair using the key.
% Fails if the key does not exist.
%
:- pred search(rbtree(K, V)::in, K::in, V::out) is semidet.
% Lookup the value associated with a key.
% Throws an exception if the key does not exist.
%
:- 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 key-value pair associated with a key.
% Does nothing if the key does not exist.
%
:- func delete(rbtree(K, V), K) = rbtree(K, V).
:- pred delete(K::in, rbtree(K, V)::in, rbtree(K, V)::out) is det.
% Remove the key-value pair associated with a key.
% Fails if the key does not exist.
%
:- 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 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, T) = T, rbtree(K, V), T) = T.
:- pred foldl(pred(K, V, T, T), rbtree(K, V), T, T).
:- 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, T, T, U, U), rbtree(K, V), T, T, U, U).
:- 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, T, T, U, U, W, W), rbtree(K, V),
T, T, U, U, W, W).
:- 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, V) = W, rbtree(K, V)) = rbtree(K, W).
:- pred map_values(pred(K, V, W), rbtree(K, V), rbtree(K, W)).
:- 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.
%--------------------------------------------------%
%--------------------------------------------------%