%   Module : lists
%   Authors: Bob Welham, Lawrence Byrd, and Richard A. O'Keefe
%   Updated: 31 Jan 1994
%   Defines: list processing utilities
%   SeeAlso: library(flatten)

%   Adapted from shared code written by the same authors; all changes
%   Copyright (C) 1987, Quintus Computer Systems, Inc.  All rights reserved.

%   (...)

%   transpose(?X, ?Y)
%   is true when X is a list of the form [[X11,...,X1m],...,[Xn1,...,Xnm]]
%   and Y is its transpose, that is, Y = [[X11,...,Xn1],...,[X1m,...,Xnm]]
%   We insist that both lists should have this rectangular form, so that
%   the predicate can be invertible.  For the same reason, we reject empty
%   arrays with m = 0 or n = 0.

transpose(Xs, Ys) :-
	Xs = [X|_],	same_length(X, Ys), % length(X) = length([Y|Ys]) = M
	Ys = [Y|_],	same_length(Y, Xs), % length(Y) = length([X|Xs]) = N
	transpose(Ys, Xs, Xs).

transpose([], Zs, Xs) :-
	transpose_1(Zs, Xs).
transpose([Y|Ys], Zs, Xs) :-
	transpose_1(Xs, Y, Xs1),
	transpose(Ys, Zs, Xs1).

transpose_1([], []).
transpose_1([_|Zs], [[]|Xs]) :-
	transpose_1(Zs, Xs).

transpose_1([], [], []).
transpose_1([[H|T]|Xs], [H|Hs], [T|Ts]) :-
	transpose_1(Xs, Hs, Ts).