for review: lower bound and upper bound searching
Zoltan Somogyi
zs at cs.mu.OZ.AU
Fri Mar 5 17:34:06 AEDT 1999
For review by anyone. Note that the new predicates are very similar to
the existing predicates, except they check the results of recursive calls
for which they know the required bound, and substitute that bound if the
recursive call fails.
-----
Add predicates to perform lower-bound and upper-bound searching, in which
if a search for a key fails, we return the next lower (or higher) key and
its associated value.
library/bintree.m:
library/rbtree.m:
library/tree234.m:
library/map.m:
Add lower-bound and upper-bound search and lookup predicates.
Add plain lookup predicates where missing, or move them next
to their corresponding search preds.
Make the handling of lookup errors more uniform.
library/require.m:
Move map__lookup_error here as report_lookup_error, for use
by bintree, rbtree and tree234, as well as map.
Zoltan.
cvs diff: Diffing .
Index: bintree.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/bintree.m,v
retrieving revision 1.38
diff -u -b -u -r1.38 bintree.m
--- bintree.m 1998/01/23 12:33:10 1.38
+++ bintree.m 1999/03/05 06:15:51
@@ -1,5 +1,5 @@
%---------------------------------------------------------------------------%
-% Copyright (C) 1993-1995, 1997 The University of Melbourne.
+% Copyright (C) 1993-1995, 1997, 1999 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.
%-----------------------------------------------------------------------------%
@@ -50,6 +50,21 @@
:- mode bintree__search(in, in, in) is semidet. % implied
:- mode bintree__search(in, in, out) is semidet.
+:- pred bintree__lookup(bintree(K,V), K, V).
+:- mode bintree__lookup(in, in, out) is det.
+
+:- pred bintree__lower_bound_search(bintree(K,V), K, K, V).
+:- mode bintree__lower_bound_search(in, in, out, out) is semidet.
+
+:- pred bintree__lower_bound_lookup(bintree(K,V), K, K, V).
+:- mode bintree__lower_bound_lookup(in, in, out, out) is det.
+
+:- pred bintree__upper_bound_search(bintree(K,V), K, K, V).
+:- mode bintree__upper_bound_search(in, in, out, out) is semidet.
+
+:- pred bintree__upper_bound_lookup(bintree(K,V), K, K, V).
+:- mode bintree__upper_bound_lookup(in, in, out, out) is det.
+
:- pred bintree__delete(bintree(K,V), K, bintree(K,V)).
:- mode bintree__delete(in, in, out) is det.
@@ -177,7 +192,7 @@
(
Result = (=)
->
- V0 = V
+ V = V0
;
Result = (<)
->
@@ -186,6 +201,81 @@
bintree__search(Left, K, V)
).
+bintree__lookup(Tree, K, V) :-
+ ( bintree__search(Tree, K, V0) ->
+ V = V0
+ ;
+ report_lookup_error("bintree__lookup: key not found", K, V)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+:- bintree__lower_bound_search(A, B, _, _) when A and B.
+
+bintree__lower_bound_search(tree(K0, V0, Left, Right), SearchK, K, V) :-
+ compare(Result, K0, SearchK),
+ (
+ Result = (=)
+ ->
+ K = K0,
+ V = V0
+ ;
+ Result = (<)
+ ->
+ ( bintree__lower_bound_search(Right, SearchK, Kp, Vp) ->
+ K = Kp,
+ V = Vp
+ ;
+ K = K0,
+ V = V0
+ )
+ ;
+ bintree__lower_bound_search(Left, SearchK, K, V)
+ ).
+
+bintree__lower_bound_lookup(Tree, SearchK, K, V) :-
+ ( bintree__lower_bound_search(Tree, SearchK, K0, V0) ->
+ K = K0,
+ V = V0
+ ;
+ report_lookup_error("bintree__lower_bound_lookup: key not found",
+ SearchK, V)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+:- bintree__upper_bound_search(A, B, _, _) when A and B.
+
+bintree__upper_bound_search(tree(K0, V0, Left, Right), SearchK, K, V) :-
+ compare(Result, K0, SearchK),
+ (
+ Result = (=)
+ ->
+ K = K0,
+ V = V0
+ ;
+ Result = (<)
+ ->
+ bintree__upper_bound_search(Right, SearchK, K, V)
+ ;
+ ( bintree__upper_bound_search(Left, SearchK, Kp, Vp) ->
+ K = Kp,
+ V = Vp
+ ;
+ K = K0,
+ V = V0
+ )
+ ).
+
+bintree__upper_bound_lookup(Tree, SearchK, K, V) :-
+ ( bintree__upper_bound_search(Tree, SearchK, K0, V0) ->
+ K = K0,
+ V = V0
+ ;
+ report_lookup_error("bintree__lower_bound_lookup: key not found",
+ SearchK, V)
+ ).
+
%-----------------------------------------------------------------------------%
:- bintree__delete(A, B, _) when A and B.
@@ -318,7 +408,8 @@
( bintree__insert(Tree0, K, V, Tree1) ->
Tree2 = Tree1
;
- error("bintree__from_list: duplicate key")
+ report_lookup_error("bintree__from_list: key already present",
+ K, V)
),
bintree__from_list_2(List, Tree2, Tree).
@@ -364,9 +455,7 @@
( bintree__from_corresponding_lists_2(Keys, Values, empty, Tree0) ->
Tree = Tree0
;
- % Either the list weren't the same length, or the
- % key list contained duplicates
- error("bintree__from_corresponding_lists")
+ error("bintree__from_corresponding_lists: lists are of different lengths")
).
:- pred bintree__from_corresponding_lists_2(list(K), list(V), bintree(K,V),
@@ -375,8 +464,12 @@
bintree__from_corresponding_lists_2([], [], Tree, Tree).
bintree__from_corresponding_lists_2([K | Ks], [V | Vs], Tree0, Tree) :-
- bintree__insert(Tree0, K, V, Tree1),
- bintree__from_corresponding_lists_2(Ks, Vs, Tree1, Tree).
+ ( bintree__insert(Tree0, K, V, Tree1) ->
+ Tree2 = Tree1
+ ;
+ report_lookup_error("bintree__from_corresponding_lists: key already present", K, V)
+ ),
+ bintree__from_corresponding_lists_2(Ks, Vs, Tree2, Tree).
%-----------------------------------------------------------------------------%
Index: map.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/map.m,v
retrieving revision 1.67
diff -u -b -u -r1.67 map.m
--- map.m 1998/10/28 05:33:32 1.67
+++ map.m 1999/03/05 06:17:23
@@ -52,9 +52,20 @@
% Search map for key, but abort if search fails.
:- pred map__lookup(map(K,V), K, V).
-:- mode map__lookup(in, in, in) is semidet. % implied
:- mode map__lookup(in, in, out) is det.
+:- pred map__lower_bound_search(map(K,V), K, K, V).
+:- mode map__lower_bound_search(in, in, out, out) is semidet.
+
+:- pred map__lower_bound_lookup(map(K,V), K, K, V).
+:- mode map__lower_bound_lookup(in, in, out, out) is det.
+
+:- pred map__upper_bound_search(map(K,V), K, K, V).
+:- mode map__upper_bound_search(in, in, out, out) is semidet.
+
+:- pred map__upper_bound_lookup(map(K,V), K, K, V).
+:- mode map__upper_bound_lookup(in, in, out, out) is det.
+
% Search map for data.
:- pred map__inverse_search(map(K,V), V, K).
:- mode map__inverse_search(in, in, out) is nondet.
@@ -267,33 +278,32 @@
( tree234__search(Map, K, V1) ->
V = V1
;
- map__lookup_error("map__lookup: key_not_found", K, V)
+ report_lookup_error("map__lookup: key not found", K, V)
+ ).
+
+map__lower_bound_search(Map, SearchK, K, V) :-
+ tree234__lower_bound_search(Map, SearchK, K, V).
+
+map__lower_bound_lookup(Map, SearchK, K, V) :-
+ ( tree234__lower_bound_search(Map, SearchK, K1, V1) ->
+ K = K1,
+ V = V1
+ ;
+ report_lookup_error("map__lower_bound_lookup: key not found",
+ SearchK, V)
).
-:- pred map__lookup_error(string, K, V).
-:- mode map__lookup_error(in, in, unused) is erroneous.
-map__lookup_error(Msg, K, V) :-
- KeyType = type_name(type_of(K)),
- ValueType = type_name(type_of(V)),
- functor(K, Functor, Arity),
- ( Arity = 0 ->
- FunctorStr = Functor
+map__upper_bound_search(Map, SearchK, K, V) :-
+ tree234__upper_bound_search(Map, SearchK, K, V).
+
+map__upper_bound_lookup(Map, SearchK, K, V) :-
+ ( tree234__upper_bound_search(Map, SearchK, K1, V1) ->
+ K = K1,
+ V = V1
;
- string__int_to_string(Arity, ArityStr),
- string__append_list([Functor, "/", ArityStr],
- FunctorStr)
- ),
- string__append_list(
- [Msg,
- "\n\tKey Type: ",
- KeyType,
- "\n\tKey Functor: ",
- FunctorStr,
- "\n\tValue Type: ",
- ValueType
- ],
- ErrorString),
- error(ErrorString).
+ report_lookup_error("map__upper_bound_lookup: key not found",
+ SearchK, V)
+ ).
map__insert(Map0, K, V, Map) :-
tree234__insert(Map0, K, V, Map).
@@ -302,7 +312,8 @@
( tree234__insert(Map0, K, V, Map1) ->
Map = Map1
;
- map__lookup_error("map__det_insert: key already present", K, V)
+ report_lookup_error("map__det_insert: key already present",
+ K, V)
).
map__det_insert_from_corresponding_lists(Map0, Ks, Vs, Map) :-
@@ -330,7 +341,7 @@
( tree234__update(Map0, K, V, Map1) ->
Map = Map1
;
- map__lookup_error("map__det_update: key not found", K, V)
+ report_lookup_error("map__det_update: key not found", K, V)
).
map__set(Map0, K, V, Map) :-
@@ -375,7 +386,8 @@
Value = Value1,
Map = Map1
;
- map__lookup_error("map__det_remove: key not found", Key, Value)
+ report_lookup_error("map__det_remove: key not found",
+ Key, Value)
).
map__count(Map, Count) :-
Index: rbtree.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/rbtree.m,v
retrieving revision 1.9
diff -u -b -u -r1.9 rbtree.m
--- rbtree.m 1998/01/08 08:11:54 1.9
+++ rbtree.m 1999/03/05 06:21:00
@@ -1,5 +1,5 @@
%-----------------------------------------------------------------------------%
-% Copyright (C) 1995-1998 The University of Melbourne.
+% Copyright (C) 1995-1999 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.
%-----------------------------------------------------------------------------%
@@ -65,15 +65,39 @@
:- pred rbtree__insert_duplicate(rbtree(K, V), K, V, rbtree(K, V)).
:- mode rbtree__insert_duplicate(in, in, in, out) is det.
+ % Search for a key-value pair using the key. Fails if key doesn't
+ % exist.
+:- pred rbtree__search(rbtree(K, V), K, V).
+:- mode rbtree__search(in, in, out) is semidet.
+
% Lookup a value associated with a key. Program abort's if key
% doesn't exist.
:- pred rbtree__lookup(rbtree(K, V), K, V).
:- mode rbtree__lookup(in, in, out) is det.
- % Search for a key-value pair using the key. Fails if key doesn't
- % exist.
-:- pred rbtree__search(rbtree(K, V), K, V).
-:- mode rbtree__search(in, in, 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.
+ % Fails if there is no key with the given or lower value.
+:- pred rbtree__lower_bound_search(rbtree(K, V), K, K, V).
+:- mode rbtree__lower_bound_search(in, in, out, 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.
+ % Aborts if there is no key with the given or lower value.
+:- pred rbtree__lower_bound_lookup(rbtree(K, V), K, K, V).
+:- mode rbtree__lower_bound_lookup(in, in, out, 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), K, K, V).
+:- mode rbtree__upper_bound_search(in, in, out, 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.
+ % Aborts if there is no key with the given or higher value.
+:- pred rbtree__upper_bound_lookup(rbtree(K, V), K, K, V).
+:- mode rbtree__upper_bound_lookup(in, in, out, out) is det.
% Delete the key value pair associated with a key. Does nothing
% if the key doesn't exist.
@@ -560,32 +584,98 @@
%-----------------------------------------------------------------------------%
+rbtree__search(Tree, K, V) :-
+ ( Tree = red(K0, V0, Left, Right)
+ ; Tree = black(K0, V0, Left, Right)
+ ),
+ compare(Result, K, K0),
+ (
+ Result = (=)
+ ->
+ V = V0
+ ;
+ Result = (<)
+ ->
+ rbtree__search(Left, K, V)
+ ;
+ rbtree__search(Right, K, V)
+ ).
+
rbtree__lookup(T, K, V) :-
+ ( rbtree__search(T, K, V0) ->
+ V = V0
+ ;
+ report_lookup_error("rbtree__lookup: key not found", K, V)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+rbtree__lower_bound_search(Tree, SearchK, K, V) :-
+ ( Tree = red(K0, V0, Left, Right)
+ ; Tree = black(K0, V0, Left, Right)
+ ),
+ compare(Result, SearchK, K0),
(
- rbtree__search(T, K, V0)
+ Result = (=)
->
+ K = K0,
+ V = V0
+ ;
+ Result = (<)
+ ->
+ rbtree__lower_bound_search(Left, SearchK, K, V)
+ ;
+ ( rbtree__lower_bound_search(Right, SearchK, Kp, Vp) ->
+ K = Kp,
+ V = Vp
+ ;
+ K = K0,
+ V = V0
+ )
+ ).
+
+rbtree__lower_bound_lookup(T, SearchK, K, V) :-
+ ( rbtree__lower_bound_search(T, SearchK, K0, V0) ->
+ K = K0,
V = V0
;
- error("rbtree__lookup: key not found.")
+ report_lookup_error("rbtree__lower_bound_lookup: key not found",
+ SearchK, V)
).
%-----------------------------------------------------------------------------%
-rbtree__search(Tree, K, V) :-
+rbtree__upper_bound_search(Tree, SearchK, K, V) :-
( Tree = red(K0, V0, Left, Right)
; Tree = black(K0, V0, Left, Right)
),
- compare(Result, K, K0),
+ compare(Result, SearchK, K0),
(
Result = (=)
->
+ K = K0,
V = V0
;
Result = (<)
->
- rbtree__search(Left, K, V)
+ ( rbtree__upper_bound_search(Left, SearchK, Kp, Vp) ->
+ K = Kp,
+ V = Vp
;
- rbtree__search(Right, K, V)
+ K = K0,
+ V = V0
+ )
+ ;
+ rbtree__upper_bound_search(Right, SearchK, K, V)
+ ).
+
+rbtree__upper_bound_lookup(T, SearchK, K, V) :-
+ ( rbtree__upper_bound_search(T, SearchK, K0, V0) ->
+ K = K0,
+ V = V0
+ ;
+ report_lookup_error("rbtree__upper_bound_lookup: key not found",
+ SearchK, V)
).
%-----------------------------------------------------------------------------%
Index: require.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/require.m,v
retrieving revision 1.26
diff -u -b -u -r1.26 require.m
--- require.m 1998/11/13 14:06:56 1.26
+++ require.m 1999/03/05 05:56:41
@@ -1,5 +1,5 @@
%-----------------------------------------------------------------------------%
-% Copyright (C) 1993-1998 The University of Melbourne.
+% Copyright (C) 1993-1999 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.
%-----------------------------------------------------------------------------%
@@ -31,10 +31,21 @@
% most circumstances you should use an explicit if-then-else
% with a call to error/1 in the "else".
+:- pred report_lookup_error(string, K, V).
+:- mode report_lookup_error(in, in, unused) is erroneous.
+
+% report_lookup_error(Message, Key, Value)
+% Abort with an error that is message appropriate for
+% the failure of a lookup operation, which either did not find
+% what it expected to find or found something it did not expect
+% to find.
+
%-----------------------------------------------------------------------------%
:- implementation.
+:- import_module string, list, std_util.
+
require(Goal, Message) :-
( call(Goal) ->
true
@@ -42,6 +53,28 @@
error(Message),
fail
).
+
+report_lookup_error(Msg, K, V) :-
+ KeyType = type_name(type_of(K)),
+ ValueType = type_name(type_of(V)),
+ functor(K, Functor, Arity),
+ ( Arity = 0 ->
+ FunctorStr = Functor
+ ;
+ string__int_to_string(Arity, ArityStr),
+ string__append_list([Functor, "/", ArityStr], FunctorStr)
+ ),
+ string__append_list(
+ [Msg,
+ "\n\tKey Type: ",
+ KeyType,
+ "\n\tKey Functor: ",
+ FunctorStr,
+ "\n\tValue Type: ",
+ ValueType
+ ],
+ ErrorString),
+ error(ErrorString).
%-----------------------------------------------------------------------------%
Index: tree234.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/tree234.m,v
retrieving revision 1.25
diff -u -b -u -r1.25 tree234.m
--- tree234.m 1998/03/31 23:16:29 1.25
+++ tree234.m 1999/03/05 05:59:06
@@ -1,5 +1,5 @@
%---------------------------------------------------------------------------%
-% Copyright (C) 1994-1997 The University of Melbourne.
+% Copyright (C) 1994-1997, 1999 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.
%---------------------------------------------------------------------------%
@@ -32,6 +32,18 @@
:- pred tree234__lookup(tree234(K, V), K, V).
:- mode tree234__lookup(in, in, out) is det.
+:- pred tree234__lower_bound_search(tree234(K, V), K, K, V).
+:- mode tree234__lower_bound_search(in, in, out, out) is semidet.
+
+:- pred tree234__lower_bound_lookup(tree234(K, V), K, K, V).
+:- mode tree234__lower_bound_lookup(in, in, out, out) is det.
+
+:- pred tree234__upper_bound_search(tree234(K, V), K, K, V).
+:- mode tree234__upper_bound_search(in, in, out, out) is semidet.
+
+:- pred tree234__upper_bound_lookup(tree234(K, V), K, K, V).
+:- mode tree234__upper_bound_lookup(in, in, out, out) is det.
+
:- pred tree234__insert(tree234(K, V), K, V, tree234(K, V)).
:- mode tree234__insert(in, in, in, out) is semidet.
% :- mode tree234__insert(di_tree234, in, in, uo_tree234) is semidet.
@@ -278,6 +290,335 @@
)
).
+tree234__lookup(T, K, V) :-
+ ( tree234__search(T, K, V0) ->
+ V = V0
+ ;
+ report_lookup_error("tree234__lookup: key not found.", K, V)
+ ).
+
+%------------------------------------------------------------------------------%
+
+tree234__lower_bound_search(T, SearchK, K, V) :-
+ (
+ T = empty,
+ fail
+ ;
+ T = two(K0, _, _, _),
+ compare(Result, SearchK, K0),
+ (
+ Result = (<),
+ T = two(_, _, T0, _),
+ tree234__lower_bound_search(T0, SearchK, K, V)
+ ;
+ Result = (=),
+ T = two(_, V0, _, _),
+ K = SearchK,
+ V = V0
+ ;
+ Result = (>),
+ T = two(_, _, _, T1),
+ ( tree234__lower_bound_search(T1, SearchK, Kp, Vp) ->
+ K = Kp,
+ V = Vp
+ ;
+ T = two(_, V0, _, _),
+ K = K0,
+ V = V0
+ )
+ )
+ ;
+ T = three(K0, _, _, _, _, _, _),
+ compare(Result0, SearchK, K0),
+ (
+ Result0 = (<),
+ T = three(_, _, _, _, T0, _, _),
+ tree234__lower_bound_search(T0, SearchK, K, V)
+ ;
+ Result0 = (=),
+ T = three(_, V0, _, _, _, _, _),
+ K = SearchK,
+ V = V0
+ ;
+ Result0 = (>),
+ T = three(_, _, K1, _, _, _, _),
+ compare(Result1, SearchK, K1),
+ (
+ Result1 = (<),
+ T = three(_, _, _, _, _, T1, _),
+ ( tree234__lower_bound_search(T1, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ T = three(_, V0, _, _, _, _, _),
+ K = K0,
+ V = V0
+ )
+ ;
+ Result1 = (=),
+ T = three(_, _, _, V1, _, _, _),
+ K = SearchK,
+ V = V1
+ ;
+ Result1 = (>),
+ T = three(_, _, _, _, _, _, T2),
+ ( tree234__lower_bound_search(T2, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ T = three(_, _, _, V1, _, _, _),
+ K = K1,
+ V = V1
+ )
+ )
+ )
+ ;
+ T = four(_, _, K1, _, _, _, _, _, _, _),
+ compare(Result1, SearchK, K1),
+ (
+ Result1 = (<),
+ T = four(K0, _, _, _, _, _, _, _, _, _),
+ compare(Result0, SearchK, K0),
+ (
+ Result0 = (<),
+ T = four(_, _, _, _, _, _, T0, _, _, _),
+ tree234__lower_bound_search(T0, SearchK, K, V)
+ ;
+ Result0 = (=),
+ T = four(_, V0, _, _, _, _, _, _, _, _),
+ K = SearchK,
+ V = V0
+ ;
+ Result0 = (>),
+ T = four(_, _, _, _, _, _, _, T1, _, _),
+ ( tree234__lower_bound_search(T1, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ T = four(_, V0, _, _, _, _, _, _, _, _),
+ K = K0,
+ V = V0
+ )
+ )
+ ;
+ Result1 = (=),
+ T = four(_, _, _, V1, _, _, _, _, _, _),
+ K = SearchK,
+ V = V1
+ ;
+ Result1 = (>),
+ T = four(_, _, _, _, K2, _, _, _, _, _),
+ compare(Result2, SearchK, K2),
+ (
+ Result2 = (<),
+ T = four(_, _, _, _, _, _, _, _, T2, _),
+ ( tree234__lower_bound_search(T2, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ T = four(_, _, _, V1, _, _, _, _, _, _),
+ K = K1,
+ V = V1
+ )
+ ;
+ Result2 = (=),
+ T = four(_, _, _, _, _, V2, _, _, _, _),
+ K = SearchK,
+ V = V2
+ ;
+ Result2 = (>),
+ T = four(_, _, _, _, _, _, _, _, _, T3),
+ ( tree234__lower_bound_search(T3, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ T = four(_, _, _, _, _, V2, _, _, _, _),
+ K = K2,
+ V = V2
+ )
+ )
+ )
+ ).
+
+tree234__lower_bound_lookup(T, SearchK, K, V) :-
+ ( tree234__lower_bound_search(T, SearchK, K0, V0) ->
+ K = K0,
+ V = V0
+ ;
+ report_lookup_error("tree234__lower_bound_lookup: key not found.",
+ SearchK, V)
+ ).
+
+%------------------------------------------------------------------------------%
+
+tree234__upper_bound_search(T, SearchK, K, V) :-
+ (
+ T = empty,
+ fail
+ ;
+ T = two(K0, _, _, _),
+ compare(Result, SearchK, K0),
+ (
+ Result = (<),
+ T = two(_, _, T0, _),
+ ( tree234__upper_bound_search(T0, SearchK, Kp, Vp) ->
+ K = Kp,
+ V = Vp
+ ;
+ T = two(_, V0, _, _),
+ K = K0,
+ V = V0
+ )
+ ;
+ Result = (=),
+ T = two(_, V0, _, _),
+ K = SearchK,
+ V = V0
+ ;
+ Result = (>),
+ T = two(_, _, _, T1),
+ tree234__upper_bound_search(T1, SearchK, K, V)
+ )
+ ;
+ T = three(K0, _, _, _, _, _, _),
+ compare(Result0, SearchK, K0),
+ (
+ Result0 = (<),
+ T = three(_, _, _, _, T0, _, _),
+ ( tree234__upper_bound_search(T0, SearchK, Kp, Vp) ->
+ K = Kp,
+ V = Vp
+ ;
+ T = three(_, V0, _, _, _, _, _),
+ K = K0,
+ V = V0
+ )
+ ;
+ Result0 = (=),
+ T = three(_, V0, _, _, _, _, _),
+ K = SearchK,
+ V = V0
+ ;
+ Result0 = (>),
+ T = three(_, _, K1, _, _, _, _),
+ compare(Result1, SearchK, K1),
+ (
+ Result1 = (<),
+ T = three(_, _, _, _, _, T1, _),
+ ( tree234__upper_bound_search(T1, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ T = three(_, _, _, V1, _, _, _),
+ K = K1,
+ V = V1
+ )
+ ;
+ Result1 = (=),
+ T = three(_, _, _, V1, _, _, _),
+ K = SearchK,
+ V = V1
+ ;
+ Result1 = (>),
+ T = three(_, _, _, _, _, _, T2),
+ tree234__upper_bound_search(T2, SearchK, K, V)
+ )
+ )
+ ;
+ T = four(_, _, K1, _, _, _, _, _, _, _),
+ compare(Result1, SearchK, K1),
+ (
+ Result1 = (<),
+ T = four(K0, _, _, _, _, _, _, _, _, _),
+ compare(Result0, SearchK, K0),
+ (
+ Result0 = (<),
+ T = four(_, _, _, _, _, _, T0, _, _, _),
+ ( tree234__upper_bound_search(T0, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ T = four(_, V0, _, _, _, _, _, _, _, _),
+ K = K0,
+ V = V0
+ )
+ ;
+ Result0 = (=),
+ T = four(_, V0, _, _, _, _, _, _, _, _),
+ K = SearchK,
+ V = V0
+ ;
+ Result0 = (>),
+ T = four(_, _, _, _, _, _, _, T1, _, _),
+ ( tree234__upper_bound_search(T1, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ T = four(_, _, _, V1, _, _, _, _, _, _),
+ K = K1,
+ V = V1
+ )
+ )
+ ;
+ Result1 = (=),
+ T = four(_, _, _, V1, _, _, _, _, _, _),
+ K = SearchK,
+ V = V1
+ ;
+ Result1 = (>),
+ T = four(_, _, _, _, K2, _, _, _, _, _),
+ compare(Result2, SearchK, K2),
+ (
+ Result2 = (<),
+ T = four(_, _, _, _, _, _, _, _, T2, _),
+ ( tree234__upper_bound_search(T2, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ T = four(_, _, _, _, _, V2, _, _, _, _),
+ K = K2,
+ V = V2
+ )
+ ;
+ Result2 = (=),
+ T = four(_, _, _, _, _, V2, _, _, _, _),
+ K = SearchK,
+ V = V2
+ ;
+ Result2 = (>),
+ T = four(_, _, _, _, _, _, _, _, _, T3),
+ tree234__upper_bound_search(T3, SearchK, K, V)
+ )
+ )
+ ).
+
+tree234__upper_bound_lookup(T, SearchK, K, V) :-
+ ( tree234__upper_bound_search(T, SearchK, K0, V0) ->
+ K = K0,
+ V = V0
+ ;
+ report_lookup_error("tree234__upper_bound_lookup: key not found.",
+ SearchK, V)
+ ).
+
%------------------------------------------------------------------------------%
tree234__update(Tin, K, V, Tout) :-
@@ -395,17 +736,6 @@
T0, T1, T2, NewT3)
)
)
- ).
-
-%------------------------------------------------------------------------------%
-
-tree234__lookup(T, K, V) :-
- (
- tree234__search(T, K, V0)
- ->
- V = V0
- ;
- error("tree234__lookup: key not found.")
).
%------------------------------------------------------------------------------%
More information about the developers
mailing list