// Code ----------------------------------------------------------------------------------------------------------------------------------
is.tree { // test if a term is a valid binary tree
(nil)^ :- true;
(n(_,_,:l,:r))^ :- #is.tree(:l), #is.tree(:r);
(_) :- false;
}
btr.length { // how many nodes is there on a binary tree
(nil,0)^ :- true;
(n(_,_,:l,:r),:n) :- #btr.length(:l,:l.n),
#btr.length(:r,:r.n),
sum(:l.n,:r.n,1,:n);
}
btr.insert { // insert a new node in a tree
(:k,:v,nil,n(:k,:v,nil,nil))^ :- true;
(:k,:v,n(:n.k?[gt(:k)],:n.v,:l,:r),n(:n.k,:n.v,:l1,:r))^ :- #btr.insert(:k,:v,:l,:l1);
(:k,:v,n(:n.k?[lt(:k)],:n.v,:l,:r),n(:n.k,:n.v,:l,:r1))^ :- #btr.insert(:k,:v,:r,:r1);
}
btr.remove { // remove a node from a tree
(:k,nil,nil)^ :- true;
(:k,n(:k,_,nil,nil),nil)^ :- true;
(:k,n(:k,_,nil,:r),:r)^ :- true;
(:k,n(:k,_,:l,nil),:l)^ :- true;
(:k,n(:k,_,:l,:r),:n)^ :- #btr.inject(:l,:r,:n);
(:k,n(:n.k?[gt(:k)],:n.v,:n.l,:n.r),n(:n.k,:n.v,:l1,:n.r))^ :- #btr.remove(:k,:n.l,:l1);
(:k,n(:n.k?[lt(:k)],:n.v,:n.l,:n.r),n(:n.k,:n.v,:n.l,:r1))^ :- #btr.remove(:k,:n.r,:r1);
}
btr.inject { // inject a node into a tree
(n(:k,:v,:l,:r),nil,n(:k,:v,:l,:r))^ :- true;
(n(:k,:v,:l,:r),n(:n.k?[gt(:k)],:n.v,:n.l,:n.r),n(:n.k,:n.v,:l1,:n.r))^ :- #btr.inject(n(:k,:v,:l,:r),:n.l,:l1);
(n(:k,:v,:l,:r),n(:n.k?[lt(:k)],:n.v,:n.l,:n.r),n(:n.k,:n.v,:n.l,:r1))^ :- #btr.inject(n(:k,:v,:l,:r),:n.r,:r1);
}
btr.assign { // change the value assigned to a node, insert the node if needed
(:k,:v,nil,n(:k,:v,nil,nil))^ :- true;
(:k,:v,n(:k,_,:l,:r),n(:k,:v,:l,:r))^ :- true;
(:k,:v,n(:n.k?[gt(:k)],:n.v,:l,:r),n(:n.k,:n.v,:l1,:r))^ :- #btr.assign(:k,:v,:l,:l1);
(:k,:v,n(:n.k?[lt(:k)],:n.v,:l,:r),n(:n.k,:n.v,:l,:r1))^ :- #btr.assign(:k,:v,:r,:r1);
}
btr.make { // build a binary tree given a list of values
(:l,:t)^ :- #btr.make(:l,:t,nil);
([],:t,:t)^ :- true;
([[:k,:v]|:r],:t,:t0) :- #btr.insert(:k,:v,:t0,:t1), #btr.make(:r,:t,:t1);
}
btr.keys { // collect all the keys into a sorted list
(n(:k,_,nil,nil),[:k])^ :- true;
(n(:k,_,:l,:r),:rest) :- #btr.keys(:l,:ll), #btr.keys(:r,:rl),
lst.cat(:ll,:k,:rl,:rest);
}
btr.values { // collect all the values into a list (sorted by the keys)
(n(_,:v,nil,nil),[:v])^ :- true;
(n(_,:v,:l,:r),:rest) :- #btr.values(:l,:ll), #btr.values(:r,:rl),
lst.cat(:ll,:v,:rl,:rest);
}
btr.pairs { // collect all the pairs store in the tree into a list (sorted by the keys)
(n(:k,:v,nil,nil),[[:k,:v]])^ :- true;
(n(:k,:v,:l,nil),:rest)^ :- #btr.pairs(:l,:ll),
lst.cat(:ll,[[:k,:v]],:rest);
(n(:k,:v,nil,r),:rest)^ :- #btr.pairs(:r,:rr),
lst.cat([[:k,:v]],:rr,:rest);
(n(:k,:v,:l,:r),:rest) :- #btr.pairs(:l,:ll), #btr.pairs(:r,:rl),
lst.cat(:ll,[[:k,:v]],:rl,:rest);
}
btr.make.sorted { // build a binary tree given a sorted list of pairs
([],nil)^ :- true;
(:l,n(:k,:v,:ll,:rr)) :- lst.length(:l,:l.s), div.int(:l.s,2,:m),lst.item(:l,:m,[:k,:v]),
sub(:m,1,:m.0), add(:m,1,:m.1), sub(:l.s,1,:l.i),
#btr.make.sorted(:l,0,:m.0,:ll), #btr.make.sorted(:l,:m.1,:l.i,:rr);
(:l,:i,:i,n(:k,:v,nil,nil))^ :- lst.item(:l,:i,[:k,:v]);
(:l,:i,:j?[add(:i,1,:j)],n(:k,:v,:ll,nil)) :- lst.item(:l,:j,[:k,:v]), #btr.make.sorted(:l,:i,:i,:ll);
(:l,:i.h,:i.t?[gt(:i.h)],n(:k,:v,:ll,:rr))^ :- sub(:i.t,:i.h,:a), add(:a,1,:l.s), div.int(:l.s,2,:n), add(:n,:i.h,:i.m),
sub(:i.m,1,:i.m.0), add(:i.m,1,:i.m.1), lst.item(:l,:i.m,[:k,:v]),
#btr.make.sorted(:l,:i.h,:i.m.0,:ll), #btr.make.sorted(:l,:i.m.1,:i.t,:rr);
(_,_,_,nil) :- true;
}
btr.balance { // balance a binary tree
(:t.i,:t.o) :- #btr.pairs(:t.i,:p), #btr.make.sorted(:p,:t.o);
}