I offer additional function for the class redBlackTree.
The predicate redBlackTree::insert rewrites an element in the unique rbt if this element exist.
It would be desirable to rewrite elements only in case of the success of some condition.
Such feature is very useful to realisation breadth-first search to find minPath (maxPath) and other tasks.
Let's consider in detail:
The RedBlackTree stores tuple(PreviousNode, NewPathWeight) at key NextNode. That is there is mapping: NextNode -> tuple(PreviousNode, NewPathWeight).
Now three steps should be made for RedBlackTree updating after a finding of the edge: Node1->NextNode of the current path in the graph, NewWeight - the weight of the new path:
1) To call the predicate redBlackTree::tryLookUp to get the "old" data tuple(Node, Weight) at key NextNode. Estimation is equal log(N).
2) If new weight NewWeight is less than "old" weight Weight (NewWeight<Weight), then to remove the "old" data tuple(Node, Weight). To call the predicate redBlackTree::delete for this purpose. Estimation is equal log(N).
3) To insert the new data tuple(Node1, NewWeight) at key NextNode. To call the predicate redBlackTree::insert for this purpose. Estimation is equal log(N).
Total 3*log(N).
The new predicate redBlackTree::insert1 will demand one step and an estimation log(N).
Declaration of the new predicate:
Code: Select all
predicates
insert1 : (tree{Key, Data} Tree1, Key Key, Data Data, predicate_dt{Data,Data} OverWriteCondition) -> tree{Key, Data} Tree0.
% @short #Tree0 is the result of inserting (#Key, #Data) into unique tree #Tree1
% @detail If predicate OverWriteCondition is succeed, then data #Data at #Key will be overwritten.
% @end
Code: Select all
clauses
insert1(tree(P, T), Key, Data, Cond) = tree(P, insert_rep1(P, Key, Data, T, Cond)).
class predicates
insert_rep1 : (treeProperty{Key} P, Key Key, Data Data, treeRep{Key, Data} Tree1, predicate_dt{Data, Data} OverWriteCondition) -> treeRep{Key, Data} Tree0.
clauses
insert_rep1(P, K, V, T, Cond) = makeblack(ins1(P, K, V, T, Cond)).
class predicates
ins1 : (treeProperty{Key} P, Key Key, Data Data, treeRep{Key, Data} Tree, predicate_dt{Data, Data} OverWriteCondition) -> treeRep{Key, Data} Tree.
clauses
ins1(_P, K, V, emptyRep, _Cond) = nodeR(emptyRep, K, V, emptyRep).
ins1(P, K, V, nodeB(A, Xk, Xd, B), Cond) = ins_black1(P, comp(P, K, Xk), K, V, A, Xk, Xd, B, Cond).
ins1(P, K, V, nodeR(A, Xk, Xd, B), Cond) = ins_red1(P, comp(P, K, Xk), K, V, A, Xk, Xd, B, Cond).
class predicates
ins_black1 : (treeProperty{Key} P, compareResult Compare, Key Key, Data Data, treeRep{Key, Data} A, Key Xkey, Data Xdata, treeRep{Key, Data} B, predicate_dt{Data, Data} OverWrite) ->
treeRep{Key, Data} Tree.
clauses
ins_black1(P, less(), K, V, A, Xk, Xd, B, Cond) = balance(ins1(P, K, V, A, Cond), Xk, Xd, B).
ins_black1(P, greater(), K, V, A, Xk, Xd, B, Cond) = balance(A, Xk, Xd, ins1(P, K, V, B, Cond)).
ins_black1(treeProperty(_, unique()), equal(), K, V, A, Xk, Xd, B, Cond) = NodeB :-
NodeB = if Cond(V,Xd) then nodeB(A, K, V, B) else nodeB(A, Xk, Xd, B) end if,
!.
ins_black1(P, equal(), K, V, A, Xk, Xd, B, Cond) = balance(ins1(P, K, V, A, Cond), Xk, Xd, B).
class predicates
ins_red1 : (treeProperty{Key} P, compareResult Compare, Key Key, Data Data, treeRep{Key, Data} A, Key Xkey, Data Xdata, treeRep{Key, Data} B, predicate_dt{Data, Data} OverWrite) ->
treeRep{Key, Data} Tree.
clauses
ins_red1(P, less(), K, V, A, Xk, Xd, B, Cond) = nodeR(ins1(P, K, V, A, Cond), Xk, Xd, B).
ins_red1(P, greater(), K, V, A, Xk, Xd, B, Cond) = nodeR(A, Xk, Xd, ins1(P, K, V, B, Cond)).
ins_red1(treeProperty(_, unique()), equal(), K, V, A, Xk, Xd, B, Cond) = NodeR :-
NodeR = if Cond(V,Xd) then nodeR(A, K, V, B) else nodeR(A, Xk, Xd, B) end if,
!.
ins_red1(P, equal(), K, V, A, Xk, Xd, B, Cond) = nodeR(A, Xk, Xd, ins1(P, K, V, B, Cond)).
I while realised really this predicate in a separate class.
Code optimisation is possible at addition of this predicate in the module redBlackTree.
Example of a call of a predicate in task about minPath:
Code: Select all
T1 = insert1(Tree, K, V, {(tuple(_,NewWeight),tuple(_,PrevWeight)) :- NewWeight<PrevWeight})
Code: Select all
T1 = insert1(Tree, K, V, {(tuple(_,NewWeight),tuple(_,PrevWeight)) :- NewWeight>PrevWeight})
Code: Select all
X = 23, % The fixed co-ordinate
T1 = insert1(Tree, K, V, {(Y1,Y2) :- sqrt(X^2+Y1^2) > sqrt(X^2+Y2^2)})