#!/usr/bin/perl -w

# $Id$
#
# Author: Scott Smedley
#
# Vertical layout of table with grouped elements. See:
# http://www.fvwm.org/doc/unstable/allCommands.html
# Optimised to reduce vertical height.

my $nCols = 5;

while (<>)
{
	chop();
	my $letter = substr($_, 0, 1);
	push(@{$data{$letter}}, $_);
	$n++;
}
print "$n items.\n";

my @letters = sort(keys(%data));
foreach (@letters)
{
	#print "$_ " . scalar(@{$data{$_}}) . "\n";
	push(@group, scalar(@{$data{$_}}));
}

my $nGroups = scalar(@group);
print "$nGroups groups.\n";

my $minRows = int($n / $nCols);
$minRows++ if ($minRows % $n != 0);
print "minRows=$minRows\n";

sub eek ($$)
{
	my ($col, $pa) = @_;

	for (my $i = $col; $i < $nCols - 1; $i++)
	{
		my $sum = 0;
		my $start = ($i == 0 ? 0 : $pa->[$i-1]);
		for (my $j = $start; $j < $nGroups; $j++)
		{
			$pa->[$i] = $j, last if ($sum + $group[$j] > $minRows);
			$sum += $group[$j];
		}
	}
}

eek(0, \@bp);

sub getColData ($$)
{
	my ($col, $pa) = @_;

	my @colData = ();
	my $start = ($col == 0 ? 0 : $pa->[$col-1]);
	my $end = ($col < $nCols-1 ? $pa->[$col] : $nGroups);
	for (my $j = $start; $j < $end; $j++)
	{
		push(@colData, @{$data{$letters[$j]}});
	}
	return @colData;
}

sub calcMaxRows ($)
{
	my ($pa) = @_;

	my $maxRows = -1;
	for (my $i = 0; $i < $nCols; $i++)
	{
		my $rows = scalar(getColData($i, $pa));
		$maxRows = $rows if ($rows > $maxRows);
	}
	return $maxRows;
}

sub display ($)
{
	my ($pa) = @_;

	for (my $i = 0; $i < $nCols; $i++)
	{
		push(@{$col[$i]}, getColData($i, $pa));

		my $rows = scalar(@{$col[$i]});
		printf("column $i has $rows items.\n");
	}

	my $maxRows = calcMaxRows($pa);
	for (my $r = 0; $r < $maxRows; $r++)
	{
		for (my $i = 0; $i < $nCols; $i++)
		{
			my ($prefix, $cmd) = ('', '');
			if ($r < scalar(@{$col[$i]}))
			{
				$cmd = $col[$i][$r];
				my $letter = substr($cmd, 0, 1);
				if (!defined $seen{$letter})
				{
					$prefix = $letter;
					$seen{$letter} = 1;
				}
			}
			printf("%-2s%-21s ", $prefix, $cmd);
		}
		print "\n";
	}
}

my $bestRows = calcMaxRows(\@bp);
print "initial: " . join(",", @bp) . "=" . $bestRows . "\n";
my @best = @bp;

sub recurse ($$);

sub recurse ($$)
{
	my ($col, $pa) = @_;

	if ($col == $nCols - 1)
	{
		my $nRows = calcMaxRows($pa);
		if ($nRows < $bestRows)
		{
			@best = @{$pa};
			$bestRows = $nRows;
		}
		# print join(",", @{$pa}) . "=" . $nRows . "\n";
		return;
	}

	recurse($col+1, $pa);

	my $sum = getColData($col, $pa);
	for (my $i = $pa->[$col]; $i < $nGroups; $i++)
	{
		last if ($sum + $group[$i] > $bestRows);
		my @c = @{$pa};
		$c[$col] = $i+1;
		eek($col+1, \@c);
		recurse($col+1, \@c);
		$sum += $group[$i];
	}
}

recurse(0, \@bp);

display(\@best);

# vim:ts=4 sw=4