% Vasilenko V. IVBO-06-16   Variant 15

domains
i = integer
s = string
il = i*
pr = pair(i, i)
pair_list = pr*
bi_t = tree_b(bi_t, i, bi_t); nil
avl=avl(bt,i);nil
bt=bt(avl,i,avl);nil

predicates
    nondeterm smpl(i, i, il)
    nondeterm solve(i)
    nondeterm do(i) % Меню
    nondeterm translate(il, real, real)
    nondeterm checkLists(il, il)
    nondeterm checkLength(il, il) % Проверка двух списков на одинаковую длину
    nondeterm find(il, i, i)
    nondeterm checkList_47(il, il, il)
    nondeterm cutList(il, i, i, il) % Возвращает спискок, вырезая из него нужные числа
    nondeterm checkP(i, il)
    nondeterm getDiagram(il, i) % Рисует горизонтальную диаграмму для списка чисел
    nondeterm writeLine(i, i)
    nondeterm setWeight(il, i, i)
    nondeterm run(avl)
    nondeterm getMulti(il, il, pair_list)
    nondeterm checkIdentity(i, il, pair_list, pair_list, pair_list)
    nondeterm addPair(i, il, pair_list, i, pair_list)
    nondeterm checkPair(i, pr, i)
    nondeterm map(bi_t, i) % Функция для отрисовки дерева
    nondeterm tab(i) % Функция для отрисовки табов (Используется при отрисовке дерева)
    nondeterm create_tree(bi_t, bi_t) % Функция для создания бинарного дерева
    nondeterm insert(i, bi_t, bi_t) Функция для вставки дерева
    nondeterm insertA(i,avl,avl)
    nondeterm getPath(i, bi_t, s, s) % Возвращает путь в дереве до указанной вершины
    nondeterm unionA(avl,i,avl,i,avl,avl)
    nondeterm map_86(avl, i) % Функция для отрисовки АВЛ дерева
    nondeterm findMax(avl, i)
    nondeterm findMin(avl, i)
    nondeterm getMax(i,i, i) % Return max count
    nondeterm getMin(i, i, i) % Return min count

    max(i,i,i) Возвращает наибольшее из двух чисел
    add(pair_list, i, i, pair_list)
    writePairList(pair_list) выводит лист пар чисел на экран
    writePair(pr) Выводит пару чисел на экран
    getL(il, i, i)
    add(i,il,il)
    divide(il, il, il)
    divide(il, i, il, il)
    divideList(il, i, i, il, il)
    doubleArrays(il, il, il)
    checkList_29(il, i, i)
    numbersList(il, il)
    length(il, i) % Возвращает длину листа
    readlist(il) % Функция для заполнения листа
clauses
% Меню для работы с программой
% 99 - код для перезапуска меню
do(I):-
    I=99,
    write("***Enter current program***"),nl,nl,
    write("-1) Number 4"),nl,
    write("-2) Number 6"),nl,
    write("-3) Number 13"),nl,
    write("-4) Number 20"),nl,
    write("-5) Number 22"),nl,
    write("-6) Number 29"),nl,
    write("-7) Number 38"),nl,
    write("-8) Number 45"),nl,
    write("-9) Number 47"),nl,
    write("-10) Number 54"),nl,
    write("-11) Number 56"),nl,
    write("-12) Number 72"),nl,
    write("-13) Number 84"),nl,
    write("-14) Number 86"),nl,nl,

    write("--or enter empty string for quit--"),nl,
    readint(Number),
    do(Number).
do(I):-
    I=1,
    write("Current number = "), readint(N), write("Prime factors = "),
    solve(N),nl,
    do(99).

do(I):-
    I=2,
    readlist(EnteredList),nl,
        translate(EnteredList, _, K),
        write(K),nl,nl,
    do(99).
do(I):-
    I=3,
    readlist(EnteredList),
        numbersList(EnteredList, SignList),
        write(SignList),nl,nl,
    do(99).
do(I):-
    I=4,
    readlist(EnteredList),
        doubleArrays(FirstList, SecondList, EnteredList),
        write("First list: ", FirstList),nl,
        write("SecondList: ", SecondList),nl,nl,
        do(99).
do(I):-
    I=5,
    readlist(EnteredList),
        divide(EnteredList, NegativePos, PositivePos),
        write("Negative pos: ", NegativePos),nl,
        write("Positive pos: ", PositivePos),nl,nl,
        do(99).

do(I):-
    I=6,
    readlist(EnteredList),nl,
    write("Write current number: "),readint(CurrentNumber),
        checkList_29(EnteredList, CurrentNumber, Count),
        write("Result: ", Count),nl,nl,
        do(99).
do(I):-
    I=7,
    readlist(EnteredList),nl,
    write("Write current element: "),readint(CurrentNumber),
        divideList(EnteredList, CurrentNumber, 0, FirstList, SecondList),
        write("FirstList: ", FirstList),nl,
        write("SecondList: ", SecondList),nl,nl,
        do(99).
do(I):-
    I=8,
    write("***Enter first list***"),nl,
    readlist(FirstList),nl,
    write("***Enter second list***"),nl,
    readlist(SecondList),nl,
    checkLength(FirstList, SecondList),nl,
    do(99).
do(I):-
    I=9,
    write("***Enter list***"),nl,
    readlist(EnteredList),nl,
    checkList_47(EnteredList, EnteredList, []),nl,
    do(99).

do(I):-
    I=10,
    write("***Enter list***"),nl,
    readlist(EnteredList),nl,
    write("***Enter current position***"),nl,
    readint(Pos),
    checkP(Pos,EnteredList),
    write("***Enter length***"),nl,
    readint(Length),
    cutList(EnteredList, Pos, Length, []),nl,
    do(99).
do(I):-
    I=11,
    write("***Enter list***"),nl,
    readlist(EnteredList),nl,
    setWeight(EnteredList, 0, Weight),
    getDiagram(EnteredList, Weight),nl,
    do(99).
do(I):-
    I=12,
    write("***Enter list***"),nl,
    readlist(EnteredList),nl,
    getMulti(EnteredList, EnteredList, []),nl,
    do(99).
do(I):-
    I=13,
    write("***Enter binary tree***"), nl,
    create_tree(nil, Tree),nl,
    write("Enter current: "),nl,
    readint(Cur),
    getPath(Cur, Tree, " ", Result),
    write("Result: ", Result),nl,nl,
    do(99).
do(I):-
    I=14,
    run(avl(nil,0)),nl,
    do(99).

    %******************Number 4**************
    % Func return prime factors of current count
    smpl(1,2,[1]):-!.
    smpl(A,A,[A]):-!.
    smpl(A,B,[B|C]):-
        A mod B=0,!,
        E=A div B,
        smpl(E,B,C).
    smpl(A,2,B):-!,
        smpl(A,3,B).
    smpl(A,B,C):-
        D=B+2,
        smpl(A,D,C).
    solve(A):-
        A<0,
        A1 = -A,
        smpl(A1,2,L),
        L1 = [-1|L],
        write(L1).
    solve(A):-
        A>0,
        smpl(A,2,L),
        write(L).
    solve(0):-write(0).

    %***************************************

    %************Number 6************
    % Func is used for translate number from decimal to binary
    translate([], 0.5, 0.0).
    translate([X|List1], Y, K):-
        translate(List1, Y1, K1),
        Y=Y1*2,
        K=K1+Y*X.
    %********************************

    %***********Number 13************
    % Func is used for change sign of counts in current list
    numbersList([], []):-!.
        numbersList([Head|Tail], [SignHead|SignTail]):-
            SignHead = -Head,
            numbersList(Tail, SignTail).
       %**********************************

       %**************Number 20***********
       % Func is used by divide current list for two lists
       % 1 - With positive positions
       % 2- With negative positions
        doubleArrays([X], [ ], [X]):-!.
    doubleArrays([ ], [Y], [Y]):-!.
    doubleArrays([ ], [ ], [ ]):-!.
    doubleArrays([X | Xs], [Y | Ys], [X, Y | Zs]) :- % X for negative, Y for Positive list
            doubleArrays(Xs, Ys, Zs). % And call this func again with new params
        %************************************

        %************Number 22***************
        divide(List, Negative, Positive):-
            divide(List, 1, Negative, Positive).

    divide([], _, [], []):-!.

    divide([Head|Tail], Pos, [Pos|TailNegative], Positive):-
            Head < 0, !, NextPos = Pos + 1,
        divide(Tail, NextPos, TailNegative, Positive).

    divide([Head|Tail], Pos, Negative, [Pos|TailPositive]):-
        Head > 0, !, NextPos = Pos + 1,
        divide(Tail, NextPos, Negative, TailPositive).

    divide([_|Tail], Pos, Negative, Positive):-
            NextPos = Pos + 1, % Head = 0
            divide(Tail, NextPos, Negative, Positive).
        %***************************************

        %***************Number 29****************
        checkList_29([A|B],A,X):-!,checkList_29(B,A,Y), X = Y+1.
    checkList_29([_|B],C,X):-checkList_29(B,C,X).
    checkList_29([],_,0).
    %****************************************

    %****************Number 38***************
    divideList([],_,_,[],[]):-!.
        divideList([H|T],CurrentNumber,CurrentPos,[H|Tb],Lm):-
            CurrentNumber+1 > CurrentPos+1,
            NextPos = CurrentPos + 1,
            divideList(T,CurrentNumber,NextPos, Tb,Lm),!.
        divideList([H|T],CurrentNumber,CurrentPos,Lb,[H|Tm]):-
            divideList(T,CurrentNumber, CurrentPos, Lb,Tm).
    %*****************************************

    %*****************Number 45***************
    checkLists([], []):-
        write("Lists equals!"),nl,!.
    checkLists([], _):-
        write("Lists equals!"),nl,!.

    checkLists([H|T], L):-
        find(L, H, Count),
        Count<>0,
        checkLists(T, L).

    checkLists([H|_], L):-
        find(L, H, Count),
        Count=0,
        write("Lists not equals!"),nl,!.

    checkLength(List1, List2):-
        length(List1, L1),
        length(List2, L2),
        L1<>L2,
        write("Lists not equals!"),nl,!.

    checkLength(List1, List2):-
        length(List1, L1),
        length(List2, L2),
        L1=L2,
        checkLists(List1, List2).
    %********************************************

    %****************Number 47*******************
    checkList_47([],[],[]):-!.
    checkList_47([H|T], EnteredList, Result):-
        find(EnteredList, H, Count),
        Count>1,
        find(Result, H, Count2),
        Count2=0,
        add(H, Result, NewR),
        checkList_47(T, EnteredList, NewR).
    checkList_47([H|T], EnteredList, Result):-
        find(EnteredList, H, Count),
        Count < 2,
        checkList_47(T, EnteredList, Result).
    checkList_47([H|T], EnteredList, Result):-
        find(EnteredList, H, Count),
        Count >1,
        find(Result, H, Count2),
        Count2<>0,
        checkList_47(T, EnteredList, Result).

    checkList_47([], _, Result):-
        write("Result: "),
        write(Result),nl.

    %******************************************

    %*****************Number 54****************
    cutList([], _, _, Result):-write("Result: ", Result),nl.
    cutList([H|T], P, L, Result):-
        P > 1,
        NewP = P - 1,
        add(H, Result, NewR),
        cutList(T, NewP, L, NewR).
    cutList([_|T], P, L, Result):-
        P < 2,
        L > 0,
        NewL = L - 1,
        cutList(T, P, NewL, Result).
    cutList([H|T], P, L, Result):-
        P < 2,
        L < 1,
        add(H, Result, NewR),
        cutList(T, P, L, NewR).

    checkP(Pos, List):-
        Pos>0,
        getL(List, 0, Result),
        NewR = Result + 1,
        Pos<NewR.
    checkP(Pos, List):-
        Pos>0,
        getL(List, 0, Result),
        Pos>Result,
        write("Invalid position!"),nl,fail.
    checkP(Pos, _):-
        Pos<1,
        write("Invalid position!"),nl,fail.

    getL([], L, Result):-Result = L.
    getL([_|T], L, Result):-
        NewL = L + 1,
        getL(T, NewL, Result).
    %**************************************************

    %*******************Number 56**********************
    getDiagram([], _).
    getDiagram([H|T], W):-
        write(" "),
        writeLine(H, W),
        getDiagram(T, W).

    writeLine(E, I):-
        E < 0,
        I = E,
        write(E),write(" "),
        NewI = I + 1,
        writeLine(E, NewI).
    writeLine(E, I):-
        E < 0,
        I < E,
        write(" "),
        NewI = I + 1,
        writeLine(E, NewI).
    writeLine(E, I):-
        E < 0,
        I > E,
        I <> 1,
        write("!"),
        NewI = I + 1,
        writeLine(E, NewI).
    writeLine(E, I):-
        E < 0,
        I > E,
        I = 1,
        write("|"),nl.
    writeLine(E, I):-
        E > 0,
        I < 0,
        write(" "),
        NewI = I + 1,
        writeLine(E, NewI).
    writeLine(E, I):-
        E > 0,
        I = 0,
        write("    "),
        write("|"),
        NewI = I + 1,
        writeLine(E, NewI).
    writeLine(E, I):-
        E > 0,
        I > 0,
        I < E,
        write("!"),
        NewI = I + 1,
        writeLine(E, NewI).
    writeLine(E, I):-
        E > 0,
        I > 0,
        I = E,
        write("!"),
        NewI = I + 1,
        writeLine(E, NewI).
    writeLine(E, I):-
        E > 0,
        I > 0,
        I > E,
        write(E),nl.

    writeLine(E, I):-
        E = 0,
        I < 1,
        write(" "),
        NewI = I + 1,
        NewI <> E,
        writeLine(E, NewI).
    writeLine(E, I):-
        E = 0,
        I < 1,
        write(" "),
        NewI = I + 1,
        NewI = E,
        write(E),
        writeLine(E, NewI).
    writeLine(E, I):-
        E = 0,
        I = 1,
        write("|"),nl.

    setWeight([], W, Result):-Result = W.
    setWeight([H|T], W, Result):-
        H < W,
        NewW = H,
        setWeight(T, NewW, Result).
    setWeight([H|T], W, Result):-
        H > W,
        setWeight(T, W, Result).
    setWeight([H|T], W, Result):-
        H = W,
        setWeight(T, W, Result).
    %*****************************************

    %*****************Number 72***************
    getMulti([], _,Result):-writePairList(Result),nl,write(Result),nl,nl.
    getMulti([H|T], List, Result):-
        checkIdentity(H, List, Result, Result, NewR),
        getMulti(T,List, NewR).

    writePairList([]).
    writePairList([H|T]):-
        writePair(H),
        writePairList(T).
    writePair(pair(E,C)):-
        write("Element: ", E),
        write("  Count: ", C),nl.

    addPair(E, [], PairL, Count, Result):-
        add(PairL, E, Count, NewR),
        Result = NewR.
    addPair(E, [H|T], PairL, Count, Result):-
        E<>H,
        addPair(E, T, PairL, Count, Result).
    addPair(E, [H|T], PairL, Count, Result):-
        E = H,
        NewC = Count + 1,
        addPair(E, T, PairL, NewC, Result).

    add([],E,C,Res):-
        Res = [pair(E,C)].
    add([H|T],E,C,[H|Res]):-
            add(T,E,C,Res).

    checkIdentity(E, List, ListForReturn, [], Result):-
        addPair(E, List, ListForReturn, 0, NewR),
        Result = NewR.
    checkIdentity(E, List, ListForReturn, [H|T], Result):-
        checkPair(E,H, Res),
        Res=1,
        checkIdentity(E, List, ListForReturn, T, Result).
    checkIdentity(E, _, ListForReturn, [H|_], PairList):-
        checkPair(E,H, Res),
        Res=0,
        PairList = ListForReturn.

    checkPair(E, pair(E2,_), Res):-
        E=E2,
        Res = 0.
    checkPair(E, pair(E2,_), Res):-
        E<>E2,
        Res = 1.
    %********************************************

    %******************Number 84*****************
    getPath(_, nil, _, _).
    getPath(Current, tree_b(_, E, _), Path, Result):-
        Current = E,
        concat(Path, "->", NewP),
        str_int(S, E),
        concat(NewP, S, Res),
        Result = Res,!.
    getPath(Current, tree_b(Left, E, Right), Path, Result):-
        Current <> E,
        Path <> " ",
        concat(Path, "->", NewP),
        str_int(S, E),
        concat(NewP, S, Res),
        getPath(Current, Left, Res, Result),
        getPath(Current, Right, Res, Result).
    getPath(Current, tree_b(Left, E, Right), Path, Result):-
        Current <> E,
        Path = " ",
        str_int(Res, E),
        getPath(Current, Left, Res, Result),
        getPath(Current, Right, Res, Result).

    create_tree(Tree, NewTree):-
        readint(C), !,
        insert(C, Tree, TempTree),
        nl, map(TempTree, 0), nl, nl,
        create_tree(TempTree, NewTree).
    create_tree(Tree, Tree).

    insert(N, nil, tree_b(nil, N, nil)).
    insert(E, tree_b(Left, E, Right), tree_b(Left, E, Right)).

    insert(N, tree_b(Left, E, Right), tree_b(NLeft, E, Right)):-
        N < E,
        insert(N, Left, NLeft).
    insert(N, tree_b(Left, E, Right), tree_b(Left, E, NRight)):-
        E < N,
        insert(N, Right, NRight).

    map(nil, _).
    map(tree_b(Left, E, Right), D):-
        NewD = D + 1,
        map(Right, NewD),
        tab(D), write(E), nl,
        map(Left, NewD).

    tab(0).
    tab(D):-
        write("     "),
        NewD = D - 1,
        tab(NewD).
    %********************************************

    %*****************Number 86******************
    findMax(avl(bt(avl(nil,0), E, avl(nil,0)),_), E).
    findMax(avl(bt(avl(nil,0), E, R), _), Max):-
        findMax(R, RMax),
        getMax(E, RMax, Max).
    findMax(avl(bt(L, E, avl(nil,0)), _), Max):-
        findMax(L, LMax),
        getMax(E, LMax, Max).
    findMax(avl(bt(L, E, R), _), Max):-
        findMax(L, LMax),
        findMax(R, RMax),
        getMax(RMax, LMax, Res),
        getMax(Res,E,Max).

    findMin(avl(bt(avl(nil,0), E, avl(nil,0)),_), E).
    findMin(avl(bt(avl(nil,0), E, R), _), Min):-
        findMin(R, RMin),
        getMin(E, RMin, Min).
    findMin(avl(bt(L, E, avl(nil,0)), _), Min):-
        findMin(L, LMin),
        getMin(E, LMin, Min).
    findMin(avl(bt(L, E, R), _), Min):-
        findMin(L, LMin),
        findMin(R, RMin),
        getMin(RMin, LMin, Res),
        getMin(Res,E,Min).


    getMax(E1,E2,Res):-E1>=E2,Res = E1.
    getMax(E1,E2,Res):-E1<E2, Res = E2.
    getMin(E1,E2,Res):-E1>=E2,Res = E2.
    getMin(E1,E2,Res):-E1<E2, Res = E1.


    insertA(New,avl(nil,0),avl(bt(avl(nil,0),New,avl(nil,0)),1)).
    insertA(E,avl(bt(Left,E,Right),H),avl(bt(Left,E,Right),H)).

    insertA(New,avl(bt(Left,E,Right),_),NewA):-
        New < E,
        insertA(New,Left,avl(bt(LT,X,RT),_)),
        unionA(LT,X,RT,E,Right,NewA).

    insertA(New,avl(bt(Left,E,Right),_),NewA):-
        New > E,
        insertA(New,Right,avl(bt(LT,X,RT),_)),
        unionA(Left,E,LT,X,RT,NewA).

    unionA(avl(T1,H1),A,avl(bt(L2,C,R2),H2),B,avl(T3,H3),avl(bt(avl(bt(avl(T1,H1),A,L2),HA),C,avl(bt(R2,B,avl(T3,H3)),HB)),HC)):-
        H2>H1,H2>H3,
        HA=H1+1,HB=H3+1,HC=HA+1.

    unionA(avl(T1,H1),A,avl(T2,H2),B,avl(T3,H3),avl(bt(avl(T1,H1),A,avl(bt(avl(T2,H2),B,avl(T3,H3)),HB)),HA)):-
        H1>=H2,H1>=H3,
        max(H2,H3,Hb), max(H1,HB,HA).

    unionA(avl(T1,H1),A,avl(T2,H2),B,avl(T3,H3),avl(bt(avl(bt(avl(T1,H1),A,avl(T2,H2)),HA),B,avl(T3,H3)),HB)):-
        H3>=H2,H3>=H1,
        max(H1,H2,HA),max(HA,H3,HB).

    max(X,Y,Z) :- X>Y, !, Z=X+1.
    max(X,Y,Z) :- X<=Y,!, Z=Y+1.

    map_86(avl(nil, _), _).
    map_86(avl(bt(Left, E, Right), _), D):-
        NewD = D + 1,
        map_86(Right, NewD),
        tab(D), write(E), nl,
        map_86(Left, NewD).
    run(A):-
        write("***Enter next element***"),nl,nl,
        readint(C), !,write("___"),nl,nl,
        insertA(C,A,An),
        map_86(An, 0),nl,nl,
        run(An);
        write("*************************"),nl,
        findMax(A, MaxElement),nl,
        write("Max element: ", MaxElement),nl,
        findMin(A, MinElement),nl,
        write("Min element: ", MinElement),nl.
    %*******************************************

    add(E,[],[E]).
    add(E,[H|T],[H|T1]):-
        add(E,T,T1).

    find([A|B],A,X):-!,
        find(B,A,Y),
        X = Y+1.

    find([_|B],C,X):-
    find(B,C,X).
    find([],_,0).

    length([], L):-L=0.
    length([_|T], L):-
        length(T, L2),
        L = L2 + 1.


readlist([Head|Tail]):-
    write("Enter next element: "), readint(Head), !,readlist(Tail).
    readlist([]).
goal
do(99),!.