[m-rev.] diff: cleanup library/rtree.m
Julien Fischer
juliensf at csse.unimelb.edu.au
Mon Oct 16 14:26:40 AEST 2006
Estimated hours taken: 2
Branches: main, (release?)
Cleanups for the rtree module.
library/rtree.m:
Add a reference to the paper by Guttman that is the basis of this
implementation.
Conform more closely to our coding standards.
doc/Mmakefile:
Include the rtree documentation in the library reference guide.
Julien.
Index: doc/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/mercury/doc/Mmakefile,v
retrieving revision 1.42
diff -u -r1.42 Mmakefile
--- doc/Mmakefile 28 Jun 2006 08:10:54 -0000 1.42
+++ doc/Mmakefile 19 Jul 2006 02:59:24 -0000
@@ -263,8 +263,6 @@
;; \
$(LIBRARY_DIR)/mutvar.m) \
;; \
- $(LIBRARY_DIR)/rtree.m) \
- ;; \
*) \
echo "* `basename $$filename .m`::"; \
;; \
@@ -295,8 +293,6 @@
;; \
$(LIBRARY_DIR)/mutvar.m) \
;; \
- $(LIBRARY_DIR)/rtree.m) \
- ;; \
*) \
file="`basename $$filename .m`"; \
echo "@node $$file"; \
Index: library/rtree.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/rtree.m,v
retrieving revision 1.4
diff -u -r1.4 rtree.m
--- library/rtree.m 27 Sep 2006 06:16:42 -0000 1.4
+++ library/rtree.m 16 Oct 2006 04:12:40 -0000
@@ -1,4 +1,4 @@
-%---------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%-----------------------------------------------------------------------------%
% Copyright (C) 2006 The University of Melbourne.
@@ -10,15 +10,16 @@
% Main author: gjd.
% Stability: low.
%
-% This file provides a region tree (R-tree) ADT. An R-tree associates
+% 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. R-trees accept spatial queries, e.g. a
+% 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 provides a region(K) typeclass that allows the user to
+% 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 1, 2 and 3 dimensional space respectively.
+% are provided: region(interval), region(box) and region(box3d)
+% corresponding to "square" regions in one, two and three dimensional spaces
+% respectively.
%
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -34,21 +35,21 @@
:- typeclass region(K) where [
- % Tests whether two regions intersect.
+ % Succeeds iff if two regions intersect.
%
pred intersects(K::in, K::in) is semidet,
- % Tests whether the first region is contained within the second.
+ % Succeeds iff the first region is contained within the second.
%
pred contains(K::in, K::in) is semidet,
- % Computes the "size" of a region.
+ % Returns the "size" of a region.
% e.g. for a 2D box, the "size" is equivalent to area.
%
func size(K) = float,
- % Computes a bounding region that contains both input regions.
- % The resulting region should be as small as possible.
+ % Returns a minimal bounding region that contains both
+ % input regions.
%
func bounding_region(K, K) = K,
@@ -56,9 +57,9 @@
% bounding_region/2, i.e.
%
% bounding_region_size(K1, K2) = size(bounding_region(K1, K2)).
- %
- % Lazy programmers can use this definition, however usually a
- % better implementation can be found, e.g. for intervals:
+ %
+ % 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).
@@ -75,19 +76,19 @@
%
:- func rtree.init = (rtree(K, V)::uo) is det <= region(K).
- % Check whether an rtree is empty.
+ % Succeeds iff the given rtree is empty.
%
:- pred rtree.is_empty(rtree(K, V)::in) is semidet.
% Insert a new key and corresponding value into an rtree.
%
:- func rtree.insert(K, V, rtree(K, V)) = rtree(K, V) <= region(K).
-:- pred rtree.insert(K::in, V::in, rtree(K, V)::in, rtree(K, V)::out) is det
- <= region(K).
+:- pred rtree.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.
+ % 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.
%
@@ -104,10 +105,10 @@
% 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.
+ % 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:
%
@@ -115,11 +116,11 @@
% <=> search_general(intersects(K), true, T, Vs)
%
% search_contains(T, K, Vs)
- % <=> search_general(contains(K),true,T,Vs)
+ % <=> search_general(contains(K), true, T, Vs)
%
:- func rtree.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.
+ pred(V)::in(pred(in) is semidet), rtree(K, V)::in) = (list(V)::out)
+ is det.
% search_first(KTest, VTest, Max, T, V, L).
%
@@ -132,7 +133,7 @@
% K1 contains K2, then if KTest(K2, L2) holds we have that
% KTest(K1, L1) holds with L2 >= L1.
%
- % If there exists multiple key-value pairs which satisfy the above
+ % If there exist multiple key-value pairs that satisfy the above
% conditions, then one of the candidates is chosen arbitrarily.
%
:- pred rtree.search_first(pred(K, L), pred(V, L), rtree(K, V), L, V, L).
@@ -158,32 +159,39 @@
:- pred rtree.fold(pred(K, V, A, A), rtree(K, V), A, A).
:- mode rtree.fold(pred(in, in, in, out) is det, in, in, out) is det.
:- mode rtree.fold(pred(in, in, di, uo) is det, in, di, uo) is det.
-:- mode rtree.fold(pred(in, in, in, out) is semidet, in, in, out) is semidet.
+:- mode rtree.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 rtree.map_values(pred(K, V, W), rtree(K, V), rtree(K, W)).
:- mode rtree.map_values(pred(in, in, out) is det, in, out) is det.
-:- mode rtree.map_values(pred(in, in, out) is semidet, in, out) is semidet.
+:- mode rtree.map_values(pred(in, in, out) is semidet, in, out)
+ is semidet.
%---------------------------------------------------------------------------%
%
-% Predefined regions
+% Pre-defined regions
%
% An interval type represented as interval(Min, Max).
%
-:- type interval ---> interval(float, float).
-:- instance region(interval).
-
- % A 2D axis aligned box represented as box(XMin,XMax,YMin,YMax).
+:- type interval
+ ---> interval(float, float).
+
+ % A 2D axis aligned box represented as box(XMin, XMax, YMin, YMax).
%
-:- type box ---> box(float, float, float, float).
-:- instance region(box).
+:- type box
+ ---> box(float, float, float, float).
- % A 3D axis aligned box represented as box(XMin,XMax,YMin,YMax,ZMin,ZMax).
+ % A 3D axis aligned box represented as
+ % box(XMin, XMax, YMin, YMax, ZMin, ZMax).
%
-:- type box3d ---> box3d(float, float, float, float, float, float).
+:- type box3d
+ ---> box3d(float, float, float, float, float, float).
+
+:- instance region(interval).
+:- instance region(box).
:- instance region(box3d).
%---------------------------------------------------------------------------%
@@ -196,6 +204,19 @@
:- import_module require.
%---------------------------------------------------------------------------%
+%
+% The implementation here is based on:
+%
+% A. Guttman, "R-trees: a dynamic index structure for spatial searching,"
+% in Proc. ACM-SIGMOD Int. Conf. Management of Data, Boston, MA, 1984,
+% pp.47--54.
+%
+% NOTES
+% -----
+% * What the paper refers to as "rectangles", we refer to as "regions".
+% * What the paper refers to as "area", we refer to as "size".
+%
+%---------------------------------------------------------------------------%
% The empty rtree and singleton rtrees are treated as a special case.
%
@@ -224,6 +245,10 @@
bound(four(ground, ground, ground, ground, ground, ground, ground,
ground)).
+:- type min_of_two_result
+ ---> min2_first
+ ; min2_second.
+
:- type min_of_three_result
---> min3_first
; min3_second
@@ -237,21 +262,22 @@
%-----------------------------------------------------------------------------%
%
-% init
+% Creation
%
rtree.init = empty.
%-----------------------------------------------------------------------------%
%
-% is_empty
+% Test for emptiness
%
rtree.is_empty(empty).
%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
%
-% insert
+% Insertion
%
rtree.insert(K, V, !.Tree) = !:Tree :-
@@ -273,14 +299,16 @@
insert_2(leaf(_), _, _, _) :-
error("insert: leaf unexpected").
insert_2(two(K0, T0, K1, T1), K, V, T) :-
- Result = include2(K, K0, K1),
- ( Result = min3_first ->
+ Result = choose_subtree(K, K0, K1),
+ (
+ Result = min2_first,
insert_and_split_child2(K0, T0, K1, T1, K, V, T)
;
+ Result = min2_second,
insert_and_split_child2(K1, T1, K0, T0, K, V, T)
).
insert_2(three(K0, T0, K1, T1, K2, T2), K, V, T) :-
- Result = include3(K, K0, K1, K2),
+ Result = choose_subtree(K, K0, K1, K2),
(
Result = min3_first,
insert_and_split_child3(K0, T0, K1, T1, K2, T2, K, V, T)
@@ -294,43 +322,82 @@
insert_2(Node, K, V, T) :-
Node = four(_, _, _, _, _, _, _, _),
split_4_node(Node, K0, T0, K1, T1),
- NRT = two(K0, T0, K1, T1),
- insert_2(NRT, K, V, T).
+ insert_2(two(K0, T0, K1, T1), K, V, T).
- % Decides which subtree to insert value with K0.
+%-----------------------------------------------------------------------------%
+%
+% Choosing what subtree to insert a new node into
+%
+
+% The following functions choose a subtree into which to insert a new
+% Key-Value pair. There are two versions, one for when we are inserting into
+% two-nodes and another for when we are inserting into three-nodes.
+% (Four-nodes should be split when they are encountered so we will never need
+% to insert into them.)
+%
+% In either case the algorithm is the same (c.f. the ChooseLeaf algorithm in
+% the paper by Guttman).
+%
+% We insert the new Value into the subtree whose associated region needs the
+% least enlargement to include Key. Ties are resolved in favour of the
+% subtree with the region of smallest size.
+
+ % choose_subtree(Key, KA, KB).
+ %
+ % Returns min2_first if we should insert the value associated with Key
+ % into the subtree associated with KA and min2_second if we should
+ % insert it into the subtree associated with KB.
%
-:- func include2(K, K, K) = min_of_three_result <= region(K).
+:- func choose_subtree(K, K, K) = min_of_two_result <= region(K).
-include2(K0, K1, K2) = Result :-
- A1 = size(K1),
- A2 = size(K2),
- A01 = bounding_region_size(K0, K1),
- A02 = bounding_region_size(K0, K2),
- D1 = A01 - A1,
- D2 = A02 - A2,
- include_min(D1, D2, A1, A2, min3_first, min3_second, Result).
-
- % Decides which subtree to insert value with K0.
- %
-:- func include3(K, K, K, K) = min_of_three_result <= region(K).
-
-include3(K0, K1, K2, K3) = Result :-
- A1 = size(K1),
- A2 = size(K2),
- A3 = size(K3),
- A01 = bounding_region_size(K0, K1),
- A02 = bounding_region_size(K0, K2),
- A03 = bounding_region_size(K0, K3),
- D1 = A01 - A1,
- D2 = A02 - A2,
- D3 = A03 - A3,
- include_min(D1, D2, A1, A2, min3_first, min3_second, Result0),
+choose_subtree(Key, KA, KB) = Result :-
+ SizeA = size(KA),
+ SizeB = size(KB),
+ %
+ % Compute the size of each of KA and KB enlarged to include Key.
+ %
+ EnlargedSizeA = bounding_region_size(Key, KA),
+ EnlargedSizeB = bounding_region_size(Key, KB),
+ IncreaseForA = EnlargedSizeA - SizeA,
+ IncreaseForB = EnlargedSizeB - SizeB,
+ ( IncreaseForA < IncreaseForB ->
+ Result = min2_first
+ ; IncreaseForA > IncreaseForB ->
+ Result = min2_second
+ ; SizeA =< SizeB ->
+ Result = min2_first
+ ;
+ Result = min2_second
+ ).
+
+ % Decides which subtree to insert value with Key.
+ %
+:- func choose_subtree(K, K, K, K) = min_of_three_result <= region(K).
+
+choose_subtree(Key, KA, KB, KC) = Result :-
+ AreaA = size(KA),
+ AreaB = size(KB),
+ AreaC = size(KC),
+ EnlargedAreaA = bounding_region_size(Key, KA),
+ EnlargedAreaB = bounding_region_size(Key, KB),
+ EnlargedAreaC = bounding_region_size(Key, KC),
+ IncreaseForA = EnlargedAreaA - AreaA,
+ IncreaseForB = EnlargedAreaB - AreaB,
+ IncreaseForC = EnlargedAreaC - AreaC,
+ include_min(IncreaseForA, IncreaseForB, AreaA, AreaB,
+ min3_first, min3_second, Result0),
( Result0 = min3_first ->
- include_min(D1, D3, A1, A3, min3_first, min3_third, Result)
+ include_min(IncreaseForA, IncreaseForC, AreaA, AreaC,
+ min3_first, min3_third, Result)
;
- include_min(D2, D3, A2, A3, min3_second, min3_third, Result)
+ include_min(IncreaseForB, IncreaseForC, AreaA, AreaB,
+ min3_second, min3_third, Result)
).
+ % D1 and D2 are the enlargement to the two rectangles caused by adding
+ % the new key. We choose the Key that causes the smallest enlargement.
+ % In the event of a tie with choose the Key with the smallest area.
+ %
:- pred include_min(float::in, float::in, float::in, float::in,
min_of_three_result::in, min_of_three_result::in,
min_of_three_result::out) is det.
@@ -345,6 +412,8 @@
;
R3 = R2
).
+
+%-----------------------------------------------------------------------------%
% Split the child (if a 4 node) and insert into T0.
%
@@ -352,24 +421,30 @@
rtree_2(K, V)::in, K::in, V::in, rtree_2(K, V)::out) is det <= region(K).
insert_and_split_child2(K0, T0, K1, T1, K, V, T) :-
- ( T0 = leaf(_),
+ (
+ T0 = leaf(_),
T = three(K0, T0, K1, T1, K, leaf(V))
- ; T0 = two(_, _, _, _),
+ ;
+ T0 = two(_, _, _, _),
NK0 = bounding_region(K, K0),
insert_2(T0, K, V, NT0),
T = two(NK0, NT0, K1, T1)
- ; T0 = three(_, _, _, _, _, _),
+ ;
+ T0 = three(_, _, _, _, _, _),
NK0 = bounding_region(K, K0),
insert_2(T0, K, V, NT0),
T = two(NK0, NT0, K1, T1)
- ; T0 = four(_, _, _, _, _, _, _, _),
+ ;
+ T0 = four(_, _, _, _, _, _, _, _),
split_4_node(T0, K2, T2, K3, T3),
- Result = include2(K, K2, K3),
- ( Result = min3_first ->
+ Result = choose_subtree(K, K2, K3),
+ (
+ Result = min2_first,
K4 = bounding_region(K, K2),
insert_2(T2, K, V, T4),
T = three(K1, T1, K3, T3, K4, T4)
;
+ Result = min2_second,
K4 = bounding_region(K, K3),
insert_2(T3, K, V, T4),
T = three(K1, T1, K2, T2, K4, T4)
@@ -399,19 +474,26 @@
;
T0 = four(_, _, _, _, _, _, _, _),
split_4_node(T0, K3, T3, K4, T4),
- Result = include2(K, K2, K3),
- ( Result = min3_first ->
+ Result = choose_subtree(K, K2, K3),
+ (
+ Result = min2_first,
K5 = bounding_region(K, K3),
insert_2(T3, K, V, T5),
T = four(K1, T1, K2, T2, K4, T4, K5, T5)
;
+ Result = min2_second,
K5 = bounding_region(K, K4),
insert_2(T4, K, V, T5),
T = four(K1, T1, K2, T2, K3, T3, K5, T5)
)
).
-
- % Split a 4 node into two 2 nodes.
+
+%-----------------------------------------------------------------------------%
+%
+% Node splitting
+%
+
+ % Split a 4-node into two 2-nodes.
% Attempts to minimise the size of the resulting keys.
%
:- pred split_4_node(rtree_2(K, V)::in(four), K::out, rtree_2(K, V)::out,
@@ -461,60 +543,66 @@
).
%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
%
-% delete
+% Deletion
%
-
- % When deleting from an rtree, we may need to collect some subtrees that
- % need to be reinserted.
+
+ % When deleting from an rtree we may need to collect some subtrees that
+ % need to be reinserted. These subtrees are called orphan entries.
%
-:- type deleted(K, V)
- ---> deleted(K, rtree_2(K, V)).
+:- type orphan(K, V)
+ ---> orphan(K, rtree_2(K, V)).
-:- type deleteds(K, V) == list(deleted(K, V)).
+:- type orphans(K, V) == list(orphan(K, V)).
:- type delete_info(K, V)
- ---> deleting(deleteds(K, V))
- ; finished(int, deleteds(K, V)).
+ ---> deleting(orphans(K, V))
+ ; finished(int, orphans(K, V)).
rtree.delete(K, V, one(K0, V), empty) :-
contains(K, K0).
-rtree.delete(K, V, rtree(T0), T) :-
- delete_2(T0, K, V, 1, _, DT, DI),
- (
- DI = finished(D, DLs),
- reinsert_deleted_subtrees(DLs, D, DT, T1),
- T = rtree(T1)
- ;
- DI = deleting(DLs),
- %
- % We are still deleting and we have reached the root node. This
- % means the path to the deleted leaf contained all 2-nodes
- % (including the root-node).
- %
+rtree.delete(K, V, !Tree) :-
+ some [!T] (
+ !.Tree = rtree(!:T),
+ delete_2(!.T, K, V, 1, _, !:T, Info),
(
- DLs = [deleted(NK, NT) | DLs0],
+ Info = finished(Depth, Orphans),
+ reinsert_deleted_subtrees(Orphans, Depth, !T),
+ !:Tree = rtree(!.T)
+ ;
+ Info = deleting(Orphans),
%
- % Here we detect the special case that the root was a 2-node
- % with two leaves (& one was deleted). Thus we need to drop
- % back to a 1-node.
+ % We are still deleting and we have reached the root node. This
+ % means the path to the deleted leaf contained all 2-nodes
+ % (including the root-node).
%
- ( NT = leaf(NV) ->
- ( DLs0 = [] ->
- T = one(NK, NV)
- ; DLs0 = [deleted(NK1, NT1)] ->
- T1 = two(NK, NT, NK1, NT1),
- T = rtree(T1)
+ (
+ Orphans = [ Orphan | Orphans0],
+ Orphan = orphan(OrphanKey, OrphanTree),
+ %
+ % Here we detect the special case that the root was a 2-node
+ % with two leaves (& one was deleted). Thus we need to drop
+ % back to a 1-node.
+ %
+ ( OrphanTree = leaf(OrphanValue) ->
+ ( Orphans0 = [] ->
+ !:Tree = one(OrphanKey, OrphanValue)
+ ; Orphans0 = [orphan(NextOrphanKey, NextOrphanTree)] ->
+ !:T = two(OrphanKey, OrphanTree, NextOrphanKey,
+ NextOrphanTree),
+ !:Tree = rtree(!.T)
+ ;
+ error("delete: unbalanced rtree")
+ )
;
- error("delete: unbalanced rtree")
+ reinsert_deleted_subtrees(Orphans0, 1, OrphanTree, !:T),
+ !:Tree = rtree(!.T)
)
;
- reinsert_deleted_subtrees(DLs0, 1, NT, T1),
- T = rtree(T1)
+ Orphans = [],
+ error("delete: expected delete info")
)
- ;
- DLs = [],
- error("delete: expected delete info")
)
).
@@ -524,78 +612,86 @@
:- pred delete_2(rtree_2(K, V)::in, K::in, V::in, int::in, K::out,
rtree_2(K, V)::out, delete_info(K, V)::out) is semidet <= region(K).
-delete_2(T, K, V, _, DK, DT, DeleteInfo) :-
- T = leaf(V),
- DK = K,
- DT = T,
- DeleteInfo = deleting([]).
-delete_2(two(K0, T0, K1, T1), K, V, D, DK, DT, DeleteInfo) :-
- ( try_deletion2(K0, T0, K1, T1, K, V, D, DK0, DT0, DI0) ->
+delete_2(leaf(V), K, V, _, K, leaf(V), deleting([])).
+delete_2(two(K0, T0, K1, T1), K, V, Depth, DK, DT, Info) :-
+ ( try_deletion2(K0, T0, K1, T1, K, V, Depth, DK0, DT0, Info0) ->
DK = DK0,
DT = DT0,
- DeleteInfo = DI0
+ Info = Info0
;
- try_deletion2(K1, T1, K0, T0, K, V, D, DK, DT, DeleteInfo)
+ try_deletion2(K1, T1, K0, T0, K, V, Depth, DK, DT, Info)
).
-delete_2(three(K0, T0, K1, T1, K2, T2), K, V, D, DK, DT, DeleteInfo) :-
- ( try_deletion3(K0, T0, K1, T1, K2, T2, K, V, D, DK0, DT0, DI0) ->
+delete_2(three(K0, T0, K1, T1, K2, T2), K, V, Depth, DK, DT, Info) :-
+ ( try_deletion3(K0, T0, K1, T1, K2, T2, K, V, Depth, DK0, DT0, Info0) ->
DK = DK0,
DT = DT0,
- DeleteInfo = DI0
- ; try_deletion3(K1, T1, K0, T0, K2, T2, K, V, D, DK0, DT0, DI0) ->
+ Info = Info0
+ ; try_deletion3(K1, T1, K0, T0, K2, T2, K, V, Depth, DK0, DT0, Info0) ->
DK = DK0,
DT = DT0,
- DeleteInfo = DI0
+ Info = Info0
;
- try_deletion3(K2, T2, K0, T0, K1, T1, K, V, D, DK, DT, DeleteInfo)
+ try_deletion3(K2, T2, K0, T0, K1, T1, K, V, Depth, DK, DT, Info)
).
-delete_2(four(K0, T0, K1, T1, K2, T2, K3, T3), K, V, D, DK, DT, DI) :-
- ( try_deletion4(K0, T0, K1, T1, K2, T2, K3, T3, K, V, D, DK0, DT0, DI0) ->
+delete_2(four(K0, T0, K1, T1, K2, T2, K3, T3), K, V, Depth, DK, DT, Info) :-
+ (
+ try_deletion4(K0, T0, K1, T1, K2, T2, K3, T3, K, V, Depth, DK0, DT0,
+ Info0)
+ ->
DK = DK0,
DT = DT0,
- DI = DI0
- ; try_deletion4(K1, T1, K0, T0, K2, T2, K3, T3, K, V, D, DK0, DT0, DI0) ->
+ Info = Info0
+ ;
+ try_deletion4(K1, T1, K0, T0, K2, T2, K3, T3, K, V, Depth, DK0, DT0,
+ Info0)
+ ->
DK = DK0,
DT = DT0,
- DI = DI0
- ; try_deletion4(K2, T2, K0, T0, K1, T1, K3, T3, K, V, D, DK0, DT0, DI0) ->
+ Info = Info0
+ ;
+ try_deletion4(K2, T2, K0, T0, K1, T1, K3, T3, K, V, Depth, DK0, DT0,
+ Info0)
+ ->
DK = DK0,
DT = DT0,
- DI = DI0
+ Info = Info0
;
- try_deletion4(K3, T3, K0, T0, K1, T1, K2, T2, K, V, D, DK, DT, DI)
+ try_deletion4(K3, T3, K0, T0, K1, T1, K2, T2, K, V, Depth, DK, DT,
+ Info)
).
+%-----------------------------------------------------------------------------%
+
:- pred try_deletion2(K::in, rtree_2(K, V)::in, K::in, rtree_2(K, V)::in,
K::in, V::in, int::in, K::out, rtree_2(K, V)::out, delete_info(K, V)::out)
is semidet <= region(K).
-try_deletion2(K0, T0, K1, T1, K, V, D, DK, DT, DI) :-
+try_deletion2(K0, T0, K1, T1, K, V, Depth, DK, DT, Info) :-
contains(K, K0),
- delete_2(T0, K, V, D + 1, DK0, DT0, DI0),
+ delete_2(T0, K, V, Depth + 1, DK0, DT0, Info0),
(
- DI0 = deleting(DLs),
- Del = deleted(K1, T1),
- DI = deleting([Del | DLs]),
- DT = DT0,
- DK = K
- ;
- DI0 = finished(_, _),
- DT = two(DK0, DT0, K1, T1),
- DK = bounding_region(K1, DK0),
- DI = DI0
+ Info0 = deleting(DLs),
+ Del = orphan(K1, T1),
+ Info = deleting([Del | DLs]),
+ DT = DT0,
+ DK = K
+ ;
+ Info0 = finished(_, _),
+ DT = two(DK0, DT0, K1, T1),
+ DK = bounding_region(K1, DK0),
+ Info = Info0
).
:- pred try_deletion3(K::in, rtree_2(K, V)::in, K::in, rtree_2(K, V)::in,
K::in, rtree_2(K, V)::in, K::in, V::in, int::in, K::out,
rtree_2(K, V)::out, delete_info(K, V)::out) is semidet <= region(K).
-try_deletion3(K0, T0, K1, T1, K2, T2, K, V, D, DK, DT, DI) :-
+try_deletion3(K0, T0, K1, T1, K2, T2, K, V, Depth, DK, DT, DI) :-
contains(K, K0),
- delete_2(T0, K, V, D + 1, DK0, DT0, DI0),
+ delete_2(T0, K, V, Depth + 1, DK0, DT0, DI0),
(
DI0 = deleting(DLs),
- DI = finished(D + 1, DLs),
+ DI = finished(Depth + 1, DLs),
DT = two(K1, T1, K2, T2),
DK = bounding_region(K1, K2)
;
@@ -628,19 +724,21 @@
DK = bounding_region(TK, K23)
).
+%-----------------------------------------------------------------------------%
+
% Given a list of deleted trees (with their bounding regions),
% (re)insert the trees back into the main tree at the specified depth.
%
-:- pred reinsert_deleted_subtrees(deleteds(K, V)::in, int::in,
+:- pred reinsert_deleted_subtrees(orphans(K, V)::in, int::in,
rtree_2(K, V)::in, rtree_2(K, V)::out) is det <= region(K).
-reinsert_deleted_subtrees([], _, T, T).
-reinsert_deleted_subtrees([deleted(K, T) | DLs], D, T0, T2) :-
- T1 = insert_tree(T0, K, T, 1, D),
+reinsert_deleted_subtrees([], _, !T).
+reinsert_deleted_subtrees([orphan(K, T) | DLs], Depth, T0, T2) :-
+ T1 = insert_tree(T0, K, T, 1, Depth),
( T0 = four(_, _, _, _, _, _, _, _) ->
- reinsert_deleted_subtrees(DLs, D + 2, T1, T2)
+ reinsert_deleted_subtrees(DLs, Depth + 2, T1, T2)
;
- reinsert_deleted_subtrees(DLs, D + 1, T1, T2)
+ reinsert_deleted_subtrees(DLs, Depth + 1, T1, T2)
).
% The code here is almost identical to 'insert', however we are
@@ -655,10 +753,12 @@
( D0 = D ->
T = three(K0, T0, K1, T1, K, S)
;
- Result = include2(K, K0, K1),
- ( Result = min3_first ->
+ Result = choose_subtree(K, K0, K1),
+ (
+ Result = min2_first,
insert_tree_and_split_child2(K0, T0, K1, T1, K, S, D0 + 1, D, T)
;
+ Result = min2_second,
insert_tree_and_split_child2(K1, T1, K0, T0, K, S, D0 + 1, D, T)
)
).
@@ -666,7 +766,7 @@
( D0 = D ->
T = four(K0, T0, K1, T1, K2, T2, K, S)
;
- Result = include3(K, K0, K1, K2),
+ Result = choose_subtree(K, K0, K1, K2),
(
Result = min3_first,
insert_tree_and_split_child3(K0, T0, K1, T1, K2, T2, K, S,
@@ -708,12 +808,14 @@
;
T0 = four(_, _, _, _, _, _, _, _),
split_4_node(T0, K2, T2, K3, T3),
- Result = include2(K, K2, K3),
- ( Result = min3_first ->
+ Result = choose_subtree(K, K2, K3),
+ (
+ Result = min2_first,
K4 = bounding_region(K, K2),
T4 = insert_tree(T2, K, S, D0, D),
T = three(K1, T1, K3, T3, K4, T4)
;
+ Result = min2_second,
K4 = bounding_region(K, K3),
T4 = insert_tree(T3, K, S, D0, D),
T = three(K1, T1, K2, T2, K4, T4)
@@ -741,12 +843,14 @@
;
T0 = four(_, _, _, _, _, _, _, _),
split_4_node(T0, K3, T3, K4, T4),
- Result = include2(K, K2, K3),
- ( Result = min3_first ->
+ Result = choose_subtree(K, K2, K3),
+ (
+ Result = min2_first,
K5 = bounding_region(K, K3),
T5 = insert_tree(T3, K, S, D0, D),
T = four(K1, T1, K2, T2, K4, T4, K5, T5)
;
+ Result = min2_second,
K5 = bounding_region(K, K4),
T5 = insert_tree(T4, K, S, D0, D),
T = four(K1, T1, K2, T2, K3, T3, K5, T5)
@@ -1283,7 +1387,7 @@
%-----------------------------------------------------------------------------%
%
-% fold
+% Fold
%
rtree.fold(_P, empty, !Acc).
@@ -1341,7 +1445,7 @@
:- mode map_values_2(pred(in, in, out) is semidet, in, out) is semidet.
map_values_2(_, leaf(_), _) :-
- error("map_values_2: leaf unexpected").
+ error("map_values_2: unexpected leaf.").
map_values_2(P, two(K0, T0, K1, T1), two(K0, U0, K1, U1)) :-
map_values_2(P, K0, T0, U0),
map_values_2(P, K1, T1, U1).
@@ -1372,7 +1476,7 @@
% Find the minimum of three values.
%
-:- func minimum_of_three(E, E, E) = min_of_three_result.
+:- func minimum_of_three(T, T, T) = min_of_three_result.
minimum_of_three(A, B, C) =
( compare((<), A, B) ->
@@ -1393,36 +1497,33 @@
% Find the minimum of four values.
%
-:- func minimum_of_four(E, E, E, E) = min_of_four_result.
+:- func minimum_of_four(T, T, T, T) = min_of_four_result.
-minimum_of_four(E0, E1, E2, E3) = M :-
- compare(R0, E0, E1),
- ( R0 = (<) ->
- M0 = min4_first,
- F0 = E0
+minimum_of_four(A, B, C, D) = Min :-
+ ( compare((<), A, B) ->
+ Min0 = min4_first,
+ MinItem0 = A
;
- M0 = min4_second,
- F0 = E1
+ Min0 = min4_second,
+ MinItem0 = B
),
- compare(R1, F0, E2),
- ( R1 = (<) ->
- M1 = M0,
- F1 = F0
+ ( compare((<), MinItem0, C) ->
+ Min1 = Min0,
+ MinItem = MinItem0
;
- M1 = min4_third,
- F1 = E2
+ Min1 = min4_third,
+ MinItem = C
),
- compare(R2, F1, E3),
- ( R2 = (<) ->
- M = M1
+ ( compare((<), MinItem, D) ->
+ Min = Min1
;
- M = min4_fourth
+ Min = min4_fourth
).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
%
-% Predefined regions
+% Pre-defined regions
%
%-----------------------------------------------------------------------------%
@@ -1439,76 +1540,75 @@
:- pred box3d_intersects(box3d::in, box3d::in) is semidet.
-box3d_intersects(Bx0, Bx1) :-
- Bx0 = box3d(X0, X1, Y0, Y1, Z0, Z1),
- Bx1 = box3d(A0, A1, B0, B1, C0, C1),
- ( X0 =< A0 ->
- X1 >= A0
+box3d_intersects(A, B) :-
+ A = box3d(AXMin, AXMax, AYMin, AYMax, AZMin, AZMax),
+ B = box3d(BXMin, BXMax, BYMin, BYMax, BZMin, BZMax),
+ ( AXMin =< BXMin ->
+ AXMax >= BXMin
;
- X0 =< A1
+ AXMin =< BXMax
),
- ( Y0 =< B0 ->
- Y1 >= B0
+ ( AYMin =< BYMin ->
+ AYMax >= BYMin
;
- Y0 =< B1
+ AYMin =< BYMax
),
- ( Z0 =< C0 ->
- Z1 >= C0
+ ( AZMin =< BZMin ->
+ AZMax >= BZMin
;
- Z0 =< C1
+ AZMin =< BZMax
).
%---------------------------------------------------------------------------%
:- pred box3d_contains(box3d::in, box3d::in) is semidet.
-box3d_contains(Bx0, Bx1) :-
- Bx0 = box3d(X0, X1, Y0, Y1, Z0, Z1),
- Bx1 = box3d(A0, A1, B0, B1, C0, C1),
- X0 >= A0,
- X1 =< A1,
- Y0 >= B0,
- Y1 =< B1,
- Z0 >= C0,
- Z1 =< C1.
+box3d_contains(A, B) :-
+ A = box3d(AXMin, AXMax, AYMin, AYMax, AZMin, AZMax),
+ B = box3d(BXMin, BXMax, BYMin, BYMax, BZMin, BZMax),
+ AXMin >= BXMin,
+ AXMax =< BXMax,
+ AYMin >= BYMin,
+ AYMax =< BYMax,
+ AZMin >= BZMin,
+ AZMax =< BZMax.
%-----------------------------------------------------------------------------%
:- func box3d_volume(box3d) = float.
-box3d_volume(Bx) = A :-
- Bx = box3d(X0, X1, Y0, Y1, Z0, Z1),
- A = (X1 - X0) * (Y1 - Y0) * (Z1 - Z0).
+box3d_volume(Box) = (XMax - XMin) * (YMax - YMin) * (ZMax - ZMin) :-
+ Box = box3d(XMin, XMax, YMin, YMax, ZMin, ZMax).
%-----------------------------------------------------------------------------%
:- func box3d_bounding_region(box3d, box3d) = box3d.
-box3d_bounding_region(Bx0, Bx1) = Bx2 :-
- Bx0 = box3d(X0, X1, Y0, Y1, Z0, Z1),
- Bx1 = box3d(A0, A1, B0, B1, C0, C1),
- M0 = min(X0, A0),
- M1 = max(X1, A1),
- N0 = min(Y0, B0),
- N1 = max(Y1, B1),
- O0 = min(Z0, C0),
- O1 = max(Z1, C1),
- Bx2 = box3d(M0, M1, N0, N1, O0, O1).
+box3d_bounding_region(A, B) = C :-
+ A = box3d(AXMin, AXMax, AYMin, AYMax, AZMin, AZMax),
+ B = box3d(BXMin, BXMax, BYMin, BYMax, BZMin, BZMax),
+ CXMin = min(AXMin, BXMin),
+ CXMax = max(AXMax, BXMax),
+ CYMin = min(AYMin, BYMin),
+ CYMax = max(AYMax, BYMax),
+ CZMin = min(AZMin, BZMin),
+ CZMax = max(AZMax, BZMax),
+ C = box3d(CXMin, CXMax, CYMin, CYMax, CZMin, CZMax).
%-----------------------------------------------------------------------------%
:- func box3d_bounding_region_volume(box3d, box3d) = float.
-box3d_bounding_region_volume(Bx0, Bx1) = CA :-
- Bx0 = box3d(X0, X1, Y0, Y1, Z0, Z1),
- Bx1 = box3d(A0, A1, B0, B1, C0, C1),
- M0 = min(X0, A0),
- M1 = max(X1, A1),
- N0 = min(Y0, B0),
- N1 = max(Y1, B1),
- O0 = min(Z0, C0),
- O1 = max(Z1, C1),
- CA = (M1 - M0) * (N1 - N0) * (O1 - O0).
+box3d_bounding_region_volume(A, B) = Volume :-
+ A = box3d(AXMin, AXMax, AYMin, AYMax, AZMin, AZMax),
+ B = box3d(BXMin, BXMax, BYMin, BYMax, BZMin, BZMax),
+ XMin = min(AXMin, BXMin),
+ XMax = max(AXMax, BXMax),
+ YMin = min(AYMin, BYMin),
+ YMax = max(AYMax, BYMax),
+ ZMin = min(AZMin, BZMin),
+ ZMax = max(AZMax, BZMax),
+ Volume = (XMax - XMin) * (YMax - YMin) * (ZMax - ZMin).
%-----------------------------------------------------------------------------%
@@ -1524,64 +1624,63 @@
:- pred box_intersects(box::in, box::in) is semidet.
-box_intersects(Bx0, Bx1) :-
- Bx0 = box(X0, X1, Y0, Y1),
- Bx1 = box(A0, A1, B0, B1),
- ( X0 =< A0 ->
- X1 >= A0
- ; X0 =< A1
+box_intersects(A, B) :-
+ A = box(AXMin, AXMax, AYMin, AYMax),
+ B = box(BXMin, BXMax, BYMin, BYMax),
+ ( AXMin =< BXMin ->
+ AXMax >= BXMin
+ ;
+ AXMin =< BXMax
),
- ( Y0 =< B0 ->
- Y1 >= B0
- ; Y0 =< B1
+ ( AYMin =< BYMin ->
+ AYMax >= BYMin
+ ;
+ AYMin =< BYMax
).
%---------------------------------------------------------------------------%
:- pred box_contains(box::in, box::in) is semidet.
-box_contains(Bx0, Bx1) :-
- Bx0 = box(X0, X1, Y0, Y1),
- Bx1 = box(A0, A1, B0, B1),
- X0 >= A0,
- X1 =< A1,
- Y0 >= B0,
- Y1 =< B1.
+box_contains(A, B) :-
+ A = box(AXMin, AXMax, AYMin, AYMax),
+ B = box(BXMin, BXMax, BYMin, BYMax),
+ AXMin >= BXMin,
+ AXMax =< BXMax,
+ AYMin >= BYMin,
+ AYMax =< BYMax.
%---------------------------------------------------------------------------%
:- func box_area(box) = float.
-box_area(Bx) = A :-
- Bx = box(X0, X1, Y0, Y1),
- A = (X1 - X0) * (Y1 - Y0).
+box_area(box(XMin, XMax, YMin, YMax)) = (XMax - XMin) * (YMax - YMin).
%---------------------------------------------------------------------------%
:- func box_bounding_region(box, box) = box.
-box_bounding_region(Bx0, Bx1) = Bx2 :-
- Bx0 = box(X0, X1, Y0, Y1),
- Bx1 = box(A0, A1, B0, B1),
- M0 = min(X0, A0),
- M1 = max(X1, A1),
- N0 = min(Y0, B0),
- N1 = max(Y1, B1),
- Bx2 = box(M0, M1, N0, N1).
+box_bounding_region(A, B) = C :-
+ A = box(AXMin, AXMax, AYMin, AYMax),
+ B = box(BXMin, BXMax, BYMin, BYMax),
+ CXMin = min(AXMin, BXMin),
+ CXMax = max(AXMax, BXMax),
+ CYMin = min(AYMin, BYMin),
+ CYMax = max(AYMax, BYMax),
+ C = box(CXMin, CXMax, CYMin, CYMax).
%---------------------------------------------------------------------------%
:- func box_bounding_region_area(box, box) = float.
-
-box_bounding_region_area(Bx0, Bx1) = CA :-
- Bx0 = box(X0, X1, Y0, Y1),
- Bx1 = box(A0, A1, B0, B1),
- M0 = min(X0, A0),
- M1 = max(X1, A1),
- N0 = min(Y0, B0),
- N1 = max(Y1, B1),
- CA = (M1 - M0) * (N1 - N0).
+box_bounding_region_area(A, B) = (XMax - XMin) * (YMax - YMin) :-
+ A = box(AXMin, AXMax, AYMin, AYMax),
+ B = box(BXMin, BXMax, BYMin, BYMax),
+ XMin = min(AXMin, BXMin),
+ XMax = max(AXMax, BXMax),
+ YMin = min(AYMin, BYMin),
+ YMax = max(AYMax, BYMax).
+
%-----------------------------------------------------------------------------%
:- instance region(interval) where [
@@ -1596,50 +1695,46 @@
:- pred interval_intersects(interval::in, interval::in) is semidet.
-interval_intersects(Bx0, Bx1) :-
- Bx0 = interval(X0, X1),
- Bx1 = interval(A0, A1),
- ( X0 =< A0 ->
- X1 >= A0
+interval_intersects(A, B) :-
+ A = interval(AMin, AMax),
+ B = interval(BMin, BMax),
+ ( AMin =< BMin ->
+ AMax >= BMin
;
- X0 =< A1
+ AMin =< BMax
).
%---------------------------------------------------------------------------%
:- pred interval_contains(interval::in, interval::in) is semidet.
-interval_contains(Bx0, Bx1) :-
- Bx0 = interval(X0, X1),
- Bx1 = interval(A0, A1),
- X0 >= A0,
- X1 =< A1.
+interval_contains(A, B) :-
+ A = interval(AMin, AMax),
+ B = interval(BMin, BMax),
+ AMin >= BMin,
+ AMax =< BMax.
%-----------------------------------------------------------------------------%
:- func interval_length(interval) = float.
-interval_length(Bx) = A :-
- Bx = interval(X0, X1),
- A = X1-X0.
+interval_length(interval(Max, Min)) = Max - Min.
%-----------------------------------------------------------------------------%
:- func interval_bounding_region(interval, interval) = interval.
-interval_bounding_region(Bx0, Bx1) = Bx2 :-
- Bx0 = interval(X0, X1),
- Bx1 = interval(A0, A1),
- Bx2 = interval(min(X0, A0), max(X1, A1)).
+interval_bounding_region(A, B) = interval(min(AMin, BMin), max(AMax, BMax)) :-
+ A = interval(AMin, AMax),
+ B = interval(BMin, BMax).
%-----------------------------------------------------------------------------%
:- func interval_bounding_region_length(interval, interval) = float.
-interval_bounding_region_length(Bx0, Bx1) = CA :-
- Bx0 = interval(X0, X1),
- Bx1 = interval(A0, A1),
- CA = max(X1, A1) - min(X0, A0).
+interval_bounding_region_length(A, B) = max(AMax, BMax) - min(AMin, BMin) :-
+ A = interval(AMin, AMax),
+ B = interval(BMin, BMax).
%-----------------------------------------------------------------------------%
:- end_module rtree.
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to: mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions: mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
More information about the reviews
mailing list