Prolog "tree"
/**
* Warranty & Liability
* To the extent permitted by applicable law and unless explicitly
* otherwise agreed upon, XLOG Technologies AG makes no warranties
* regarding the provided information. XLOG Technologies AG assumes
* no liability that any problems might be solved with the information
* provided by XLOG Technologies AG.
*
* Rights & License
* All industrial property rights regarding the information - copyright
* and patent rights in particular - are the sole property of XLOG
* Technologies AG. If the company was not the originator of some
* excerpts, XLOG Technologies AG has at least obtained the right to
* reproduce, change and translate the information.
*
* Reproduction is restricted to the whole unaltered document. Reproduction
* of the information is only allowed for non-commercial uses. Selling,
* giving away or letting of the execution of the library is prohibited.
* The library can be distributed as part of your applications and libraries
* for execution provided this comment remains unchanged.
*
* Restrictions
* Only to be distributed with programs that add significant and primary
* functionality to the library. Not to be distributed with additional
* software intended to replace any components of the library.
*
* Trademarks
* Jekejeke is a registered trademark of XLOG Technologies AG.
*/
/**
* Compounds used:
* - 'V'(M,S,F): Value holder of a tree map M and its
total number of elements S, plus
* the compare closure F.
* - 'T'(C,L,P,R): Tree non-terminal node with color C,
* left branch L, key value pair P and right branch R.
* - 'E': Tree terminal leaf
* - 'R': Color red
* - 'B': Color back
*/
/**
* See also:
*
* Red-Black Trees in a Functional Setting - Chris Okasaki, 1993
* https://www.cs.tufts.edu/~nr/cs257/archive/chris-okasaki/redblack99.pdf
*/
:- ensure_loaded(library(hiord)).
% sys_meta_args(+Atom, +Integer, -List)
:- multifile(sys_meta_args/3).
% list processing
sys_meta_args(tree_new, 2, [t,g]).
/***************************************************************/
/* Pairs Access */
/***************************************************************/
/**
* tree_enum(T, P):
* The predicate succeeds in P with the key value pairs
* from the red-black tree T.
*/
% tree_enum(+Root, -Pair)
tree_enum('V'(T,_,_), P) :-
sys_tree_enum(T, P).
% sys_tree_enum(+Tree, -Pair)
sys_tree_enum('T'(_, L, _, _), Y) :-
sys_tree_enum(L, Y).
sys_tree_enum('T'(_, _, P, _), P).
sys_tree_enum('T'(_, _, _, R), Y) :-
sys_tree_enum(R, Y).
/**
* tree_pairs(T, L):
* The predicate succeeds in L with the key value pair
* list from the red-black tree T.
*/
% tree_pairs(+Root, -Pairs)
tree_pairs(H, L) :- var(H), !,
tree_new(H),
(member(K-V, L), tree_set(H, K, V), fail; true).
tree_pairs('V'(T,_,_), L) :-
sys_tree_pairs(T, L, []).
% sys_tree_pairs(+Tree, -Pairs, +Pairs)
sys_tree_pairs('E') --> !.
sys_tree_pairs('T'(_, L, P, R)) -->
sys_tree_pairs(L),
[P],
sys_tree_pairs(R).
/**
* tree_size(T, S):
* The predicate succeeds in S with the number of key value
* pairs of the red-black tree T.
*/
% tree_size(+Root, -Integer)
tree_size('V'(_,S,_), S).
/***************************************************************/
/* Basic Access */
/***************************************************************/
/**
* tree_new(T):
* tree_new(T, F):
* The predicate succeeds in R with a new red-black tree. The binary
* predicate allows specifying a term compare F.
*/
% tree_new(-Root)
tree_new(T) :-
tree_new(T, compare).
% tree_new(-Root, +Compare)
tree_new(T, F) :-
ir_site_new(F, F2),
T = 'V'('E',0,F2).
/**
* tree_current(T, K, V):
* The predicate succeeds in V with the value for the key K
* in the red-black tree T.
*/
% tree_current(+Root, +Term, -Term)
tree_current('V'(T,_,F), K, V) :-
sys_tree_current(T, K, V, F).
% sys_tree_current(+Tree, +Term, -Term, +Compare)
sys_tree_current(T, K, V, F) :-
T = 'T'(_, _, K2-_, _),
call(F, C, K, K2),
sys_tree_current_switch(C, T, K, V, F).
% sys_tree_current_switch(+Atom, +Tree, +Term, -Term, +Compare)
sys_tree_current_switch(<, 'T'(_, L, _, _), K, V, F) :-
sys_tree_current(L, K, V, F).
sys_tree_current_switch(=, 'T'(_, _, _-V, _), _, V, _).
sys_tree_current_switch(>, 'T'(_, _, _, R), K, V, F) :-
sys_tree_current(R, K, V, F).
/***************************************************************/
/* Backtracking Modification */
/***************************************************************/
/**
* tree_set(T, K, V, R):
* The predicate succeeds. It unifies R with the red-black tree T
* that is extended by the key value pair K,V if the key is new or
* else the value for the K is replaced by V.
*/
% tree_set(+Root, +Term, +Term, -Root)
tree_set('V'(T,S,F), K, V, 'V'(T3,S2,F)) :-
sys_tree_set(T, K, V, T2, F, D),
sys_node_black(T2, T3),
S2 is S+D.
% sys_tree_set(+Tree, +Term, +Term, -Tree, +Compare, -Integer)
sys_tree_set('E', K, V, 'T'('R', 'E', K-V, 'E'), _, 1).
sys_tree_set(T, K, V, T2, F, D) :-
T = 'T'(_, _, K2-_, _),
call(F, C, K, K2),
sys_tree_set_switch(C, T, K, V, T2, F, D).
% sys_tree_set_switch(+Atom, +Tree, +Term, +Term, -Tree, +Compare, -Integer)
sys_tree_set_switch(<, 'T'(C, L, P, R), K, V, T2, F, D) :-
sys_tree_set(L, K, V, L2, F, D),
sys_node_balance(C, L2, P, R, T2).
sys_tree_set_switch(=, 'T'(C, L, K2-_, R), _, V, 'T'(C, L, K2-V, R), _, 0).
sys_tree_set_switch(>, 'T'(C, L, P, R), K, V, T2, F, D) :-
sys_tree_set(R, K, V, R2, F, D),
sys_node_balance(C, L, P, R2, T2).
/**
* tree_remove(T, K, R):
* The predicate succeds always. It unifies R with the tree
* removed by an entry with key K.
*/
% tree_remove(+Root, +Term, -Root)
tree_remove('V'(T,S,F), K, 'V'(T3,S2,F)) :-
sys_tree_remove(T, K, T2, F, D),
sys_node_black(T2, T3),
S2 is S-D.
% sys_tree_remove(+Tree, +Term, -Tree, +Compare, -Integer)
sys_tree_remove('E', _, 'E', _, 0).
sys_tree_remove(T, K, T2, F, D) :-
T = 'T'(_, _, K2-_, _),
call(F, C, K, K2),
sys_tree_remove_switch(C, T, K, T2, F, D).
% sys_tree_remove_switch(+Atom, +Tree, +Term, -Tree, +Compare, -Integer)
sys_tree_remove_switch(<, 'T'(C, L, P, R), K, 'T'(C, L2, P, R), F, D) :-
sys_tree_remove(L, K, L2, F, D).
sys_tree_remove_switch(=, 'T'(_, 'E', _, R), _, R, _, 1) :- !.
sys_tree_remove_switch(=, 'T'(C, L, _, R), _, 'T'(C, L2, Q, R), _, 1) :-
sys_tree_remove_last(L, Q, L2).
sys_tree_remove_switch(>, 'T'(C, L, P, R), K, 'T'(C, L, P, R2), F, D) :-
sys_tree_remove(R, K, R2, F, D).
/***************************************************************/
/* Backtracking Node Helper */
/***************************************************************/
% sys_node_black(+Tree, -Tree)
sys_node_black('T'('R', L, P, R), M) :- !,
M = 'T'('B', L, P, R).
sys_node_black(T, T).
% sys_node_balance(+Atom, +Tree, +Pair, +Tree, -Tree)
sys_node_balance('B', 'T'('R','T'('R', A, X, B), Y, C), Z, D, M) :- !,
M = 'T'('R', 'T'('B', A, X, B), Y, 'T'('B', C, Z, D)).
sys_node_balance('B', 'T'('R', A, X, 'T'('R', B, Y, C)), Z, D, M) :- !,
M = 'T'('R', 'T'('B', A, X, B), Y, 'T'('B', C, Z, D)).
sys_node_balance('B', A, X, 'T'('R', 'T'('R', B, Y, C), Z, D), M) :- !,
M = 'T'('R', 'T'('B', A, X, B), Y, 'T'('B', C, Z, D)).
sys_node_balance('B', A, X, 'T'('R', B, Y, 'T'('R', C, Z, D)), M) :- !,
M = 'T'('R', 'T'('B', A, X, B), Y, 'T'('B', C, Z, D)).
sys_node_balance(C, L, P, R, 'T'(C, L, P, R)).
% sys_tree_remove_last(+Tree, -Pair, -Tree)
sys_tree_remove_last('T'(_, 'E', P, 'E'), P, 'E') :- !.
sys_tree_remove_last('T'(C, L, P, 'E'), P, 'T'(C, L2, Q, 'E')) :- !,
sys_tree_remove_last(L, Q, L2).
sys_tree_remove_last('T'(C, L, P, R), Q, 'T'(C, L, P, R2)) :-
sys_tree_remove_last(R, Q, R2).
/***************************************************************/
/* Non-Backtracking Modification */
/***************************************************************/
/**
* tree_set(T, K, V):
* The predicate succeeds. As a side effect the red-black tree T
* is extended by the key value pair K,V if the key is new or
* else the value for the K is replaced by V.
*/
% tree_set(+Root, +Term, +Term)
tree_set(U, K, V) :- U = 'V'(T,S,F),
sys_tree_set2(T, U, 1, K, V, F),
arg(1, U, T2),
sys_node_black(T2), !,
S2 is S+1,
change_arg(2, U, S2).
tree_set(_, _, _).
% sys_tree_set2(+Tree, +Compound, +Integer, +Term, +Term, +Compare)
sys_tree_set2('E', H, I, K, V, _) :-
change_arg(I, H, 'T'('R', 'E', K-V, 'E')).
sys_tree_set2(T, _, _, K, V, F) :-
T = 'T'(_, _, K2-_, _),
call(F, C, K, K2),
sys_tree_set_switch(C, T, K, V, F).
% sys_tree_set_switch(+Atom, +Tree, +Term, +Term, +Compare)
sys_tree_set_switch(<, T, K, V, F) :- T = 'T'(_, L, _, _),
sys_tree_set2(L, T, 2, K, V, F),
sys_node_balance(T).
sys_tree_set_switch(=, T, _, V, _) :- T = 'T'(_, _, P, _),
change_arg(2, P, V),
fail.
sys_tree_set_switch(>, T, K, V, F) :- T = 'T'(_, _, _, R),
sys_tree_set2(R, T, 4, K, V, F),
sys_node_balance(T).
/***************************************************************/
/* Non-Backtracking Node Helper */
/***************************************************************/
% sys_node_black(+Tree)
sys_node_black(T) :- T = 'T'('R', _, _, _), !,
change_arg(1, T, 'B').
sys_node_black(_).
% sys_node_balance(+Tree)
sys_node_balance(T) :- T = 'T'('B', P, U, Q),
(P = 'T'('R', M, V, N),
(M = 'T'('R', _, _, _), !,
change_arg(1, M, 'B'),
change_arg(1, P, 'B'),
change_arg(2, P, N),
change_arg(3, P, U),
change_arg(4, P, Q),
change_arg(1, T, 'R'),
change_arg(2, T, M),
change_arg(3, T, V),
change_arg(4, T, P);
N = 'T'('R', B, Y, C), !,
change_arg(1, P, 'B'),
change_arg(4, P, B),
change_arg(1, N, 'B'),
change_arg(2, N, C),
change_arg(3, N, U),
change_arg(4, N, Q),
change_arg(1, T, 'R'),
change_arg(2, T, P),
change_arg(3, T, Y),
change_arg(4, T, N));
Q = 'T'('R', M, V, N),
(M = 'T'('R', B, Y, C), !,
change_arg(1, M, 'B'),
change_arg(2, M, P),
change_arg(3, M, U),
change_arg(4, M, B),
change_arg(1, Q, 'B'),
change_arg(2, Q, C),
change_arg(1, T, 'R'),
change_arg(2, T, M),
change_arg(3, T, Y),
change_arg(4, T, Q);
N = 'T'('R', _, _, _), !,
change_arg(1, Q, 'B'),
change_arg(2, Q, P),
change_arg(3, Q, U),
change_arg(4, Q, M),
change_arg(1, N, 'B'),
change_arg(1, T, 'R'),
change_arg(2, T, Q),
change_arg(3, T, V),
change_arg(4, T, N))).
sys_node_balance(_).