55 rbtree
%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%--------------------------------------------------%
% Copyright (C) 1995-2000, 2003-2007, 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: 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:
% Aborts program 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 rbtree.init = rbtree(K, V).
:- pred rbtree.init(rbtree(K, V)::uo) is det.
% Initialise an rbtree containing the given key-value pair.
%
:- func rbtree.singleton(K, V) = rbtree(K, V).
% Check whether a tree is empty.
%
:- pred rbtree.is_empty(rbtree(K, V)::in) is semidet.
% Inserts a new key-value pair into the tree.
% Fails if key already in the tree.
%
:- pred rbtree.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 rbtree.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 rbtree.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 rbtree.set(rbtree(K, V), K, V) = rbtree(K, V).
:- pred rbtree.set(K::in, V::in, rbtree(K, V)::in, rbtree(K, V)::out) is det.
% Insert a duplicate key into the tree.
%
:- func rbtree.insert_duplicate(rbtree(K, V), K, V) = rbtree(K, V).
:- pred rbtree.insert_duplicate(K::in, V::in,
rbtree(K, V)::in, rbtree(K, V)::out) is det.
:- pred rbtree.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 rbtree.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 rbtree.lookup(rbtree(K, V), K) = V.
:- pred rbtree.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 rbtree.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 rbtree.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 rbtree.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 rbtree.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 rbtree.delete(rbtree(K, V), K) = rbtree(K, V).
:- pred rbtree.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 rbtree.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 rbtree.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 rbtree.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 rbtree.keys(rbtree(K, V)) = list(K).
:- pred rbtree.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 rbtree.values(rbtree(K, V)) = list(V).
:- pred rbtree.values(rbtree(K, V)::in, list(V)::out) is det.
% Count the number of elements in the tree.
%
:- func rbtree.count(rbtree(K, V)) = int.
:- pred rbtree.count(rbtree(K, V)::in, int::out) is det.
:- func rbtree.assoc_list_to_rbtree(assoc_list(K, V)) = rbtree(K, V).
:- pred rbtree.assoc_list_to_rbtree(assoc_list(K, V)::in, rbtree(K, V)::out)
is det.
:- func rbtree.from_assoc_list(assoc_list(K, V)) = rbtree(K, V).
:- func rbtree.rbtree_to_assoc_list(rbtree(K, V)) = assoc_list(K, V).
:- pred rbtree.rbtree_to_assoc_list(rbtree(K, V)::in, assoc_list(K, V)::out)
is det.
:- func rbtree.to_assoc_list(rbtree(K, V)) = assoc_list(K, V).
:- func rbtree.foldl(func(K, V, T) = T, rbtree(K, V), T) = T.
:- pred rbtree.foldl(pred(K, V, T, T), rbtree(K, V), T, T).
:- mode rbtree.foldl(pred(in, in, in, out) is det, in, in, out) is det.
:- mode rbtree.foldl(pred(in, in, mdi, muo) is det, in, mdi, muo) is det.
:- mode rbtree.foldl(pred(in, in, di, uo) is det, in, di, uo) is det.
:- mode rbtree.foldl(pred(in, in, in, out) is semidet, in, in, out)
is semidet.
:- mode rbtree.foldl(pred(in, in, mdi, muo) is semidet, in, mdi, muo)
is semidet.
:- mode rbtree.foldl(pred(in, in, di, uo) is semidet, in, di, uo)
is semidet.
:- pred rbtree.foldl2(pred(K, V, T, T, U, U), rbtree(K, V), T, T, U, U).
:- mode rbtree.foldl2(pred(in, in, in, out, in, out) is det,
in, in, out, in, out) is det.
:- mode rbtree.foldl2(pred(in, in, in, out, mdi, muo) is det,
in, in, out, mdi, muo) is det.
:- mode rbtree.foldl2(pred(in, in, in, out, di, uo) is det,
in, in, out, di, uo) is det.
:- mode rbtree.foldl2(pred(in, in, di, uo, di, uo) is det,
in, di, uo, di, uo) is det.
:- mode rbtree.foldl2(pred(in, in, in, out, in, out) is semidet,
in, in, out, in, out) is semidet.
:- mode rbtree.foldl2(pred(in, in, in, out, mdi, muo) is semidet,
in, in, out, mdi, muo) is semidet.
:- mode rbtree.foldl2(pred(in, in, in, out, di, uo) is semidet,
in, in, out, di, uo) is semidet.
:- pred rbtree.foldl3(pred(K, V, T, T, U, U, W, W), rbtree(K, V),
T, T, U, U, W, W).
:- mode rbtree.foldl3(pred(in, in, in, out, in, out, in, out) is det,
in, in, out, in, out, in, out) is det.
:- mode rbtree.foldl3(pred(in, in, in, out, in, out, in, out) is semidet,
in, in, out, in, out, in, out) is semidet.
:- mode rbtree.foldl3(pred(in, in, in, out, in, out, di, uo) is det,
in, in, out, in, out, di, uo) is det.
:- mode rbtree.foldl3(pred(in, in, in, out, di, uo, di, uo) is det,
in, in, out, di, uo, di, uo) is det.
:- mode rbtree.foldl3(pred(in, in, di, uo, di, uo, di, uo) is det,
in, di, uo, di, uo, di, uo) is det.
:- func rbtree.map_values(func(K, V) = W, rbtree(K, V)) = rbtree(K, W).
:- pred rbtree.map_values(pred(K, V, W), rbtree(K, V), rbtree(K, W)).
:- mode rbtree.map_values(pred(in, in, out) is det, in, out) is det.
:- mode rbtree.map_values(pred(in, in, out) is semidet, in, out) is semidet.
%--------------------------------------------------%
%--------------------------------------------------%