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


59 rtree

%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%--------------------------------------------------%
% Copyright (C) 2006-2007 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: rtree.m.
% Main author: gjd.
% Stability: low.
%
% This module provides a region tree (R-tree) ADT. A region tree associates
% values with regions in some space, e.g. rectangles in the 2D plane, or
% bounding spheres in 3D space. Region trees accept spatial queries, e.g. a
% typical usage is "find all pubs within a 2km radius".
%
% This module also provides the typeclass region(K) which allows the user to
% define new regions and spaces. Three "builtin" instances for region(K)
% are provided: region(interval), region(box) and region(box3d)
% corresponding to "square" regions in one, two and three dimensional spaces
% respectively.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module rtree.
:- interface.

:- import_module list.

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

:- type rtree(K, V).

:- typeclass region(K) where [

        % Succeeds iff two regions intersect.
        %
    pred intersects(K::in, K::in) is semidet,

        % Succeeds iff the first region is contained within the second.
        %
    pred contains(K::in, K::in) is semidet,

        % Returns the "size" of a region.
        % e.g. for a two dimensional box one possible measure of "size"
        %      would be the area.
        %
    func size(K) = float,

        % Return a region that contains both input regions.
        % The region returned should be minimal region that contains
        % both input regions.
        %
    func bounding_region(K, K) = K,

        % Computes the size of the bounding region returned by
        % bounding_region/2, i.e.
        %
        % bounding_region_size(K1, K2) = size(bounding_region(K1, K2)).
        %
        % While the above definition would suffice, a more efficient
        % implementation often exists, e.g. for intervals:
        %
        % bounding_region_size(interval(X0, X1), interval(Y0, Y1)) =
        %       max(X1, Y1) - min(X0, Y0).
        %
        % This version is more efficient since it does not create a
        % temporary interval.
        %
    func bounding_region_size(K, K) = float
].

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

    % Initialize an empty rtree.
    %
:- func init = (rtree(K, V)::uo) is det <= region(K).

    % Succeeds iff the given rtree is empty.
    %
:- pred is_empty(rtree(K, V)::in) is semidet.

    % Insert a new key and corresponding value into an rtree.
    %
:- func insert(K, V, rtree(K, V)) = rtree(K, V) <= region(K).
:- pred insert(K::in, V::in, rtree(K, V)::in, rtree(K, V)::out)
    is det <= region(K).

    % Delete a key-value pair from an rtree.
    % Assumes that K is either the key for V, or is contained in the key
    % for V.
    %
    % Fails if the key-value pair is not in the tree.
    %
:- pred delete(K::in, V::in, rtree(K, V)::in, rtree(K, V)::out)
    is semidet <= region(K).

    % Search for all values with keys that intersect the query key.
    %
:- func search_intersects(rtree(K, V), K) = list(V) <= region(K).

    % Search for all values with keys that contain the query key.
    %
:- func search_contains(rtree(K, V), K) = list(V) <= region(K).

    % search_general(KTest, VTest, T) = V.
    %
    % Search for all values V with associated keys K that satisfy
    % KTest(K) /\ VTest(V). The search assumes that for all K1, K2
    % such that K1 contains K2, then if KTest(K2) holds we have that
    % KTest(K1) also holds.
    %
    % We have that:
    %
    %   search_intersects(T, K, Vs)
    %       <=> search_general(intersects(K), true, T, Vs)
    %
    %   search_contains(T, K, Vs)
    %       <=> search_general(contains(K), true, T, Vs)
    %
:- func search_general(pred(K)::in(pred(in) is semidet),
    pred(V)::in(pred(in) is semidet), rtree(K, V)::in) = (list(V)::out)
    is det.

    % search_first(KTest, VTest, Max, T, V, L).
    %
    % Search for a value V with associated key K such that
    % KTest(K, _) /\ VTest(V, L) is satisfied and there does not exist a
    % V' with K' such that KTest(K', _) /\ VTest(V', L') /\ (L' < L) is
    % satisfied. Fail if no such key-value pair exists.
    %
    % The search assumes that for all K1, K2 such that
    % K1 contains K2, then if KTest(K2, L2) holds we have that
    % KTest(K1, L1) holds with L2 >= L1.
    %
    % If there exist multiple key-value pairs that satisfy the above
    % conditions, then one of the candidates is chosen arbitrarily.
    %
:- pred search_first(pred(K, L), pred(V, L), rtree(K, V), L, V, L).
:- mode search_first(pred(in, out) is semidet,
    pred(in, out) is semidet, in, in, out, out) is semidet.

    % search_general_fold(KTest, VPred, T, !A).
    %
    % Apply accumulator VPred to each key-value pair K-V that satisfies
    % KTest(K). The same assumptions for KTest from search_general apply
    % here.
    %
:- pred search_general_fold(pred(K), pred(K, V, A, A), rtree(K, V),
    A, A).
:- mode search_general_fold(pred(in) is semidet,
    pred(in, in, in, out) is det, in, in, out) is det.
:- mode search_general_fold(pred(in) is semidet,
    pred(in, in, di, uo) is det, in, di, uo) is det.

    % Perform a traversal of the rtree, applying an accumulator predicate
    % for each key-value pair.
    %
:- pred fold(pred(K, V, A, A), rtree(K, V), A, A).
:- mode fold(pred(in, in, in, out) is det, in, in, out) is det.
:- mode fold(pred(in, in, di, uo) is det, in, di, uo) is det.
:- mode fold(pred(in, in, in, out) is semidet, in, in, out)
    is semidet.

    % Apply a transformation predicate to all the values in an rtree.
    %
:- pred map_values(pred(K, V, W), rtree(K, V), rtree(K, W)).
:- mode map_values(pred(in, in, out) is det, in, out) is det.
:- mode map_values(pred(in, in, out) is semidet, in, out)
    is semidet.

%--------------------------------------------------%
%
% Pre-defined regions.
%

    % An interval type represented as interval(Min, Max).
    %
:- type interval
    --->    interval(float, float).

    % A 2D axis aligned box represented as box(XMin, XMax, YMin, YMax).
    %
:- type box
    --->    box(float, float, float, float).

    % A 3D axis aligned box represented as
    % box(XMin, XMax, YMin, YMax, ZMin, ZMax).
    %
:- type box3d
    --->    box3d(float, float, float, float, float, float).

:- instance region(interval).
:- instance region(box).
:- instance region(box3d).

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


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