/************************************************************************
 * Representação do Mundo dos Blocos                                    *
 *                                                                      *
 * Humberto Costa de Sousa                                              *
 *                                                                      *
 ************************************************************************/

/************************************************************************
 * inverte(Entrada,Tmp,Saida).                                          *
 *                                                                      *
 * Funcao para inverter a ordem dos elementos de uma lista.             *
 * Processamento: Joga os elementos da Entrada na lista Tmp esvaziando  *
 *                a Lista, e apos Lista estar vazia, copia Tmp para     *
 *                Saida                                                 *
 *                                                                      *
 ************************************************************************/

inverte([X|Y],Tmp,Saida) :- 
	inverte(Y,[X|Tmp],Saida).
inverte([],X,X).

/************************************************************************
 * inverteTodas(Entrada,Tmp,Saida).                                     *
 *                                                                      *
 * Funcao para inverter a ordem dos elementos de um conjunto de listas, *
 * bem como inverter a propria ordem das listas.                        *
 * Processamento: Inverte cada uma das listas do conjunto e joga o      *
 *                resultado na lista Tmp, repetindo ate' que            *
 *                Entrada fique vazia. No fim copia a lista Tmp para    *
 *                Saida.                                                *
 *                                                                      *
 ************************************************************************/

inverteTodas([L1|Resto],Tmp,Saida) :- 
	inverte(L1,[],I1),
	inverteTodas(Resto,[I1|Tmp],Saida).
inverteTodas([],X,X).

/************************************************************************
 * transpoe(MatrizA, MatrizB).                                          *
 *                                                                      *
 * Funcao transposta onde MatrizB e' a transposta de MatrizA.           *
 * Processamento: MatrizA e' uma conjunto de listas onde cada lista e'  *
 * 		  	considerada uma linha da matriz. A MatrizB sera' o    *
 *			conjunto de listas onde cada lista e' considerada uma *
 *			linha da matriz transposta de MatrizA.                *
 *                                                                      *
 ************************************************************************/

transpoe(MatrizA, MatrizB) :-
	transpoe2(MatrizA, MatrizB, Tmp).

/************************************************************************
 * transpoe2(MatrizA, MatrizB, Tmp).                                    *
 *                                                                      *
 * Funcao auxiliar para tranpor a MatrizA.                              *
 * Processamento: Tmp e' o conjunto de listas temporario para execucao  *
 *		  	do processo.                                          *
 *                                                                      *
 ************************************************************************/

transpoe2(Matriz,[],[]) :-
	vazio(Matriz).

transpoe2(MatrizA, [LinhaB|RestoB], MatrizC) :-
	transp_aux(MatrizA, LinhaB, MatrizC),
	transpoe2(MatrizC, RestoB, _).

/************************************************************************
 * Funcao: transp_aux(A, B, C)                                          *
 * Entrada: uma lista A de listas 'l'.                                  *
 * Processamento: Divide cada lista 'l' em cabeca (que vai para lista B *
 *                como elemento), e cauda (que vai para a lista C), ou  *
 *                seja, transpoe a primeira coluna de uma matriz A para *
 *                B                                                     *
 *                                                                      *
 ************************************************************************/  

transp_aux([ [Elem|RestoLinhaA] | Resto], [Elem|RestoB],
 [RestoLinhaA|XX]) :-
	transp_aux(Resto, RestoB, XX ).

 transp_aux([[]|Resto], [' '|RestoB], [[]|XX]) :-
	transp_aux(Resto, RestoB, XX).
 
 transp_aux([],[],[]).
                                                                                                            
/************************************************************************
 * Funcao: vazio(Matriz)                                                *
 * Processamento: Verifica se a as linhas da Matriz sao listas vazias.  *
 *                                                                      *
 ************************************************************************/  

vazio([]).
vazio([A|Rest]) :-
	A == [],
	vazio(Rest).

/************************************************************************
 * Funcao: mostraLinha(Lista).                                          *
 * Processamento: Imprime os elementos da Lista.                        *
 *                                                                      *
 ************************************************************************/  

mostraLinha([X|Y]) :-
	write(' '),
	write(X),
	mostraLinha(Y).
mostraLinha([]).

/************************************************************************
 * Funcao: mostra(Lista).                                               *
 * Processamento: Imprime a representacao dos blocos.                   *
 *                                                                      *
 ************************************************************************/  

mostra([Lin1|Resto]) :-	
	nl, mostraLinha(Lin1),
	mostra(Resto).
mostra([]) :-
	nl,write('--------------'),nl.

/************************************************************************
 * Funcao: Imprime(Estado).                                             *
 * Processamento: Executa os passos para converter a lista de listas no *
 *		  diagrama do mundo dos blocos.                             *
 *                                                                      *
 * Solucao Proposta:                                                    *
 *	A solucao proposta para o problema foi considerar a lista de      *
 * listas uma matriz.                                                   *
 * Ex: [[a,b,c],[d],[e,f]] = a b c                                      *
 *                           d                                          *
 *                           e f                                        *
 *                                                                      *
 * 	O problema foi entao considerado como a transposicao da matriz    *
 * acima, onde:                                                         *
 *          a b c   t     a d e                                         *
 *          d     ----->  b   f                                         *
 *          e f           c                                             *
 *                                                                      *
 *	Nota-se que a diferenca entre a tranposta da matriz e a           *
 * representacao desejada e' a disposicao dos elementos vazios da       *
 * matriz. Esta disposicao foi alterada invertendo os elementos das     *
 * linhas da matriz, de maneira que:                                    *
 *                                                                      *
 *          a b c   i1    c b a                                         *
 *          d     ------> d                                             *
 *          e f           f e                                           *
 *                                                                      *
 *	Uma vez invertidos a ordem dos elementos da matriz, como          *
 * ilustrado acima, realizou-se a transposta da matriz com os elementos *
 * invertidos:                                                          *
 *          c b a   t    c d f                                          *
 *          d    ------> b   e                                          *
 *          f e          a                                              *
 *                                                                      *
 *	Invertendo a ordem das linhas da matriz resultante, tem-se a      *
 * representacao desejada:                                              *
 *                                                                      *
 *          c d f   i2    a                                             *
 *          b   e ------> b   e                                         *
 *          a             c d f                                         *
 *                                                                      *
 * Obs: Extendendo o enunciado do exercicio, esta solucao permite a     *
 *      representacao de mais de 3 pilhas de blocos.                    *
 *                                                                      *
 ************************************************************************/  

imprime(Estado) :- 
	inverteTodas(Estado,[],Estado2),  /* Passo i1 */
	inverte(Estado2,[],Estado3),
	transpoe(Estado3,Estado4),        /* Passo t  */	
	inverte(Estado4,[],Estado5),      /* Passo i2 */
	mostra(Estado5).                  /* Impressao do resultado */

/************************************************************************  
 * Testes:                                                              *
 *                                                                      *
 * ?- imprime([[a,b,c],[d],[e,f]]).                                     *
 *                                                                      *
 *  a                                                                   *
 *  b   e                                                               *
 *  c d f                                                               *
 * --------------                                                       *
 * yes                                                                  *
 *                                                                      *
 * ?- imprime([[a,b],[d,e,f,g],[h,i]]).                                 *
 *                                                                      *
 *    d                                                                 *
 *    e                                                                 *
 *  a f h                                                               *
 *  b g i                                                               *
 * --------------                                                       *
 * yes                                                                  *
 *                                                                      *
 * ?- imprime([[a,b],[d,e,f,g],[h,i],[j,k,l],[m],[n,o]]).               *
 *                                                                      *
 *    d                                                                 *
 *    e   j                                                             *
 *  a f h k   n                                                         *
 *  b g i l m o                                                         *
 * --------------                                                       *
 * yes                                                                  *
 *                                                                      *
 * ?- imprime([[a],[b,c]]).                                             *
 *                                                                      *
 *    b                                                                 *
 *  a c                                                                 *
 * --------------                                                       *
 * yes                                                                  *
 *                                                                      *
 * ?- imprime([[],[b,c],[d,e,f]]).                                      *
 *                                                                      *
 *      d                                                               *
 *    b e                                                               *
 *    c f                                                               *
 * --------------                                                       *
 * yes                                                                  *
 *                                                                      *
 * ?- imprime([[],[],[e,f,g]]).                                         *
 *                                                                      *
 *      e                                                               *
 *      f                                                               *
 *      g                                                               *
 * --------------                                                       *
 * yes                                                                  *
 *                                                                      *
 * ?- imprime([[],[],[]]).                                              *
 *                                                                      *
 * --------------                                                       *
 * yes                                                                  *
 *                                                                      *
 ************************************************************************/  
