#!/usr/bin/env python
# encoding=utf-8 (pep 0263)

nil = None

def add(tree, x):
    yield addroot(tree, x)
    if tree == nil:
        return
    left, y, right = tree
    if y > x:
        yield (add(left, x), y, right)
    else:
        yield (left, y, add(right, x))

def addroot(tree, x):
    if tree == nil:
        return (nil, x, nil)
    left, y, right = tree
    if y > x:
        left1, _, left2 = addroot(left, x)
        return (left1, x, (left2, y, right))
    if y < x:
        right1, _, right2 = addroot(right, x)
        return ((left, y, right1), x, right2)
    return tree

def del_(tree, x):
    if tree == nil:
        return
    for tree1 in delroot(tree, x):
        yield tree1
    left, y, right = tree
    if y > x:
        for left1 in del_(left, x):
            yield (left1, y, right)
    else:
        for right1 in del_(right, x):
            yield (left, y, right1)

def delroot(tree, x):
    if tree == nil:
        return
    tree_left, tree_y, tree_right = tree
    if tree_y != x:
        return
    if tree_left == nil and tree_right == nil:
        yield nil
    if tree_right != nil:
        left1 = tree_left
        left2, y, right = tree_right
        if y > x:
            for left in delroot((left1, x, left2), x):
                yield (left, y, right)
    if tree_left != nil:
        left, y, right1 = tree_left
        right2 = tree_right
        if y < x:
            for right in delroot((right1, x, right2), x):
                yield (left, y, right)
    yield tree

def show(tree):
    show2(tree, 0)

def show2(tree, indent):
    if tree == nil:
        return
    left, root, right = tree
    show2(right, indent+2)
    print("%s%s" % (" " * indent, root))
    show2(left, indent+2)

# demonstracni vypis
if __name__ == "__main__":
    print("Binarni stromy")
    print("--------------\n")
    print("Vytvoreni stromu:")
    print("T = next(add(nil, 6)); T1 = next(add(T, 8)); T2 = next(add(T1, 2)); " +
          "T3 = next(add(T2, 4)); T4 = next(add(T3, 1)); show(T4) :")
    T = next(add(nil, 6))
    T1 = next(add(T, 8))
    T2 = next(add(T1, 2))
    T3 = next(add(T2, 4))
    T4 = next(add(T3, 1))
    show(T4)

    print("\nSmazani uzlu s hodnotou 8:")
    print("T5 = next(del_(T4, 8)); show(T5) :")
    T5 = next(del_(T4, 8))
    show(T5)

    print("\nSmazani uzlu s hodnotou 2:")
    print("T6 = next(del_(T5, 2)); show(T6) :")
    T6 = next(del_(T5, 2))
    show(T6)

Binarni stromy
--------------

Vytvoreni stromu:
T = next(add(nil, 6)); T1 = next(add(T, 8)); T2 = next(add(T1, 2)); T3 = next(add(T2, 4)); T4 = next(add(T3, 1)); show(T4) :
    8
      6
  4
    2
1

Smazani uzlu s hodnotou 8:
T5 = next(del_(T4, 8)); show(T5) :
    6
  4
    2
1

Smazani uzlu s hodnotou 2:
T6 = next(del_(T5, 2)); show(T6) :
    6
  4
1

% nacteni:
/* ['2.8_17.pl']. */

% ve SWISH muze hlasit chybu "No permission to call sandboxed `tab(_4808)'"
% reseni viz https://github.com/SWI-Prolog/swish/issues/119

add(T,X,T1) :- addroot(T,X,T1).
add(t(L,Y,R),X,t(L1,Y,R)) :- gt(Y,X),add(L,X,L1).
add(t(L,Y,R),X,t(L,Y,R1)) :- gt(X,Y),add(R,X,R1).

addroot(nil ,X,t( nil ,X, nil )).
addroot(t(L,Y,R),X,t(L1,X,t(L2,Y,R))) :- gt(Y,X),addroot(L,X,t(L1,X,L2)).
addroot(t(L,Y,R),X,t( t(L,Y,R1),X,R2)) :- gt(X,Y),addroot(R,X,t(R1,X,R2)).
addroot(t(L,X,R),X,t(L,X,R)).

del(T,X,T1) :- add(T1,X,T).

gt(X, Y) :- X > Y.

show(T) :- show2(T,0).
show2(nil,_).
show2(t(L,X,R),Indent) :- Ind2 is Indent+2,show2(R,Ind2),tab(Indent),
                          write(X),nl,show2(L,Ind2).

%maketree(+LIST,-TREE)
%LIST - prvky kt. maji byt ve stromu ulozeny
%TREE - vytvoreny strom
%note: vypise vytvoreny strom!!!
maketree([],nil).
maketree([H|T],TREE) :- maketreeacc([H|T],nil,TREE), show(TREE).
%akumulatorova verze predikatu =>
%optimalizace pro "odstraneni" backtrackingu a zrychleni
maketreeacc([],TREE,TREE).
maketreeacc([H|T],PTREE,TREE) :- add(PTREE,H,RTREE), 
                                maketreeacc(T,RTREE,TREE).

%delitems(+TREE,+ITEMS,-NEWTREE).
%smaze ze stromu TREE uzly odpovidajici polozkam ITEMS, vrati NEWTREE
%(pokud takove neexistuji, pokracuje-pro zmenu chovani odebrat posledni kl.)
%note: vypise vytvoreny strom!!!
delitems(TREE,[],TREE) :- show(TREE).
delitems(TREE,[H|T],NEWTREE) :- del(TREE,H,PTREE), 
                                delitems(PTREE,T,NEWTREE).
%v pripade, ze dany prvek ve stromu neni, pokracuj...
delitems(TREE,[_H|T],NEWTREE) :- delitems(TREE,T,NEWTREE). 


% demonstracni vypis

  % abychom se vyhli varovanim "Redefined static procedure ..."
:- dynamic
       start/0.
       
start:- 
    write('Binarni stromy'),nl,
    write('--------------'),nl, nl,
    write('Vytvoreni stromu: '),nl,
    write('add(nil ,6,T),add(Tr,8,Tr1), add(Tr1,2,Tr2),'),nl, 
    write('add(Tr2,4,Tr3), add(Tr3,1,Tr4), show(Tr4) :'),nl,
    add(nil ,6,Tr),add(Tr,8,Tr1), add(Tr1,2,Tr2), add(Tr2,4,Tr3), add(Tr3,1,Tr4),
    show(Tr4),

    write('Smazani uzlu s hodnotou 8:'),nl,
    write('del(Tr4, 8, Tr5), show(Tr5) :'),nl,
    del(Tr4, 8, Tr5), show(Tr5),

    write('Smazani uzlu s hodnotou 2:'),nl,
    write('del(Tr5, 2, Tr6), show(Tr6) :'),nl,
    del(Tr5, 2, Tr6), show(Tr6).

?-start.

:- retractall(write_all_X/3).
:- retractall(start/0).

Binarni stromy
--------------

Vytvoreni stromu: 
add(nil ,6,T),add(Tr,8,Tr1), add(Tr1,2,Tr2),
add(Tr2,4,Tr3), add(Tr3,1,Tr4), show(Tr4) :
    8
      6
  4
    2
1
Smazani uzlu s hodnotou 8:
del(Tr4, 8, Tr5), show(Tr5) :
    6
  4
    2
1
Smazani uzlu s hodnotou 2:
del(Tr5, 2, Tr6), show(Tr6) :
    6
  4
1