Next: , Previous: , Up: Top   [Contents]


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.

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


Next: , Previous: , Up: Top   [Contents]