% ILP-503 (Prof. Dr. Silvio do Lago Pereira)

% ---------------------------------------------------------------------
% EXEMPLO 1
% ---------------------------------------------------------------------

iSort([], []).
iSort([X|R], Lo) :-
    iSort(R, S),
    insere(X, S, Lo).

insere(X, [], [X]) :- !.
insere(X, [Y|A], [X,Y|A]) :- X =< Y, !.
insere(X, [Y|A], [Y|B]) :- insere(X, A, B).

% ---------------------------------------------------------------------
% EXEMPLO 4
% ---------------------------------------------------------------------

arv( nó(nó(nil,2,nil),1,nó(nó(nil,4,nil),3,nó(nil,5,nil))) ).

% ---------------------------------------------------------------------
% EXEMPLO 5
% ---------------------------------------------------------------------

exibe(A) :-
    exibe(A, 0).
exibe(nil, _).
exibe(nó(E,R,D), N) :-
    M is N + 3,
    exibe(D, M),
    format('~*c~w\n', [N, 32, R]),
    exibe(E, M).

% ---------------------------------------------------------------------
% EXEMPLO 6
% ---------------------------------------------------------------------

huffman(Texto) :-
    contar(Texto, Folhas),
    juntar(Folhas, Árvore),
    montar(Árvore, []).

contar(Texto, Folhas) :-
    atom_chars(Texto, Caracteres),
    msort(Caracteres, Ordenados),
    clumped(Ordenados, Frequências),
    setof(nó(F,C,nil,nil), member(C-F, Frequências), Folhas).

juntar([Árvore], Árvore) :- !.
juntar([A1,A2|As], Árvore) :-
    arg(1, A1, F1),
    arg(1, A2, F2),
    F3 is F1 + F2,
    msort([nó(F3,' ',A1,A2)|As], Floresta),
    juntar(Floresta, Árvore).

% ---------------------------------------------------------------------
% EXEMPLO 7
% ---------------------------------------------------------------------

abb(Lista, Árvore) :-
    abb(Lista, nil, Árvore).

abb([], A, A) :- !.
abb([X|L], A0, A) :- ins(X, A0, A1), abb(L, A1, A).

ins(X, nil, nó(nil,X,nil)) :- !.
ins(X, nó(E,R,D), nó(N,R,D)) :- X =< R, !, ins(X, E, N).
ins(X, nó(E,R,D), nó(E,R,N)) :- ins(X, D, N).

% ---------------------------------------------------------------------
% EXEMPLO 8
% ---------------------------------------------------------------------

lin(Árvore, Lista) :-
    lin(Árvore, [], Lista).

lin(nil, A, A) :- !.
lin(nó(E,R,D), S, L) :-
    lin(D, S, T),
    lin(E, [R|T], L).

% ---------------------------------------------------------------------
% EXEMPLO 9
% ---------------------------------------------------------------------

topsort(Grafo, Solução) :-
   grafo(Grafo, Vértices, Arestas),
   topsort(Vértices, Arestas, Solução).

topsort([], _, []).
topsort(Vs, As, [V|S]) :-
   select(V, Vs, NVs),
   not(member(_-V, As)),
   exclude(subsumes_term(V-_), As, NAs),
   topsort(NVs, NAs, S).

grafo(1, [1, 2, 3, 4, 5, 6, 7, 8, 9],
         [1-2, 3-6, 4-1, 4-5, 5-2, 6-5, 6-9, 8-9]).