#{{{ Procedures

$define SORT_W_ATTR(k,x,e,F) \
map(attributes, sort([seq(setattribute(k,x),e)],F))

sortLL0 := proc(L)
local x;
    SORT_W_ATTR(convert(x,'bytes'),x,x=L,'lexorder');
end proc:

sortLL1 := proc(L::listlist(nonnegint))
local B,X,n,x,j;
    B := max(map(op,L)[])+1;
    n := nops(L[1]);
    X := [seq(B^(n-j), j=1..n)]:
    SORT_W_ATTR(Float(inner(X,x)), x, x=L, `<`);
end proc:

sortLL2 := proc(L::listlist(nonnegint))
local M,n,B,X,C,k,x;
    M := map(lst -> max(op(lst)), `kernel/transpose`(L));
    n := nops(M);
    B := rtable(1..n);
    C := 0;
    for k from n to 1 by -1 do
        B[k] := C + 1;
        C := M[k]*B[k] + C;
    end do;
    X := [seq(B[k], k=1..n)];
    SORT_W_ATTR(Float(inner(X,x)), x, x=L, `<`);
end proc:

sortLL3 := proc(L::listlist(nonnegint))
local X,x,n,i;
    X := map(x -> 10^length(max(op(x))), `kernel/transpose`(L));
    n := nops(X);
    SORT_W_ATTR(cat("", seq(X[i]+x[i], i=1..n)), x, x=L, 'lexorder');
end proc:

sortLL4 := proc(L::listlist(nonnegint))
local X,x;
    X := seq(10^length(max(op(x))), x=`kernel/transpose`(L));
    SORT_W_ATTR(cat("", X+x[]), x, x=L, 'lexorder');
end proc:

sortLL5 := proc(L::listlist(integer))
local X,x;
    X := seq(2*10^length(max((-min,max)(op(x)))), x=`kernel/transpose`(L));
    SORT_W_ATTR(cat("", X+x[]), x, x=L, 'lexorder');
end proc:

# thread-safe version
sortLL6 := proc(L::listlist(integer))
local X,x;
    X := seq(10^length(max((-min,max)(op(x)))), x=`kernel/transpose`(L));
    SORT_W_ATTR([cat("", X+x[])], x, x=L, 'lexorder'[1]);
end proc:
#}}}
#{{{ TEST

$ifdef TEST
(cat(sortLL, 1..6))([[1,4,2],[1,2,3],[0,1,4]]);
$endif

#}}}
#{{{ varyM (measure performance vs number of sublists)

$ifdef varyM

with(Tine):

# We need to generate data to sort.  Assume we have m lists, each with
# a random sequence of N integers (in the range of 1 to N).  Let N
# be fixed,

N := 5: # items in each sublist

(M,Loops) := SeqLog(10..10^3,30,andinverse):

# Generate a list of [listlist].

Pargs := EvalFork([seq([RandomTools:-Generate(listlist(integer(range=1..10^5),m,N))], m = M)]):
#Pargs := EvalFork([seq([RandomTools:-Generate(list([seq(integer(range=1..10^(N-k+1)), k=1..N)],m))], m=M)]):
#Pargs := EvalFork([seq([RandomTools:-Generate(list([seq(integer(range=1..10^k), k=1..N)],m))], m=M)]):

PlotApplyMeas([cat(sortLL, 1..6)]
              , M, Loops, Pargs
              , field = [bytesused, totaltime]
              , postscript
              , basename = "vary-M-"
             );
$endif

#}}}
#{{{ varyN (measure performance vs length of sublists)

$ifdef varyN

with(Tine):

M := 10^2:   # number of sublists
MAX := 10^5: # max element

(N,Loops) := SeqLog(1..10^2,30,andinverse):

# Generate a list of [listlist].

Pargs := EvalFork([seq([RandomTools:-Generate(listlist(integer(range=1..MAX),M,n))], n = N)]):

PlotApplyMeas([cat(sortLL, 1..6)]
              , N, Loops, Pargs
              , field = [bytesused, totaltime]
              , postscript
              , basename = "vary-N-"
             );
$endif

#}}}
#{{{ varyMAX (measure performance vs max element)

$ifdef varyMAX

with(Tine):

# We need to generate data to sort.  Assume we have m lists, each with
# a random sequence of N integers (in the range of 1 to N).  Let N
# be fixed,

M := 10^2: # number of sublists
N := 5:    # items in each sublist

(MAX,Loops) := SeqLog(10..10^4,30,andinverse):

# Generate a list of [listlist].
Pargs := EvalFork([seq([RandomTools:-Generate(listlist(integer(range=1..mx),M,N))], mx = MAX)]):

PlotApplyMeas([cat(sortLL, 1..6)]
              , MAX, Loops, Pargs
              , field = [bytesused, totaltime]
              , postscript
              , basename = "vary-MAX-"
             );
$endif

#}}}

# Local Variables:
# mode: folding
# End: