%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 2006-2007 The University of Melbourne.
% Copyright (C) 2014-2019 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% 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(in(pred(in, out) is semidet),
in(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(in(pred(in) is semidet),
in(pred(in, in, in, out) is det), in, in, out) is det.
:- mode search_general_fold(in(pred(in) is semidet),
in(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(in(pred(in, in, in, out) is det), in, in, out) is det.
:- mode fold(in(pred(in, in, di, uo) is det), in, di, uo) is det.
:- mode fold(in(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(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.
%--------------------------------------------------%
%
% 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).
%--------------------------------------------------%
%--------------------------------------------------%