#!/usr/bin/perl
# Compares node distances in memory for different layouts of the following
# binary tree:
#                      A
#                  /       \
#              B               C
#            /   \           /   \
#          D       E       F       G
#         / \     / \     / \     / \
#        H   I   J   K   L   M   N   O
#       / \ / \ / \ / \ / \ / \ / \ / \
#       P Q R S T U V W X Y Z 0 1 2 3 4

# Calculates the real node distance.
sub dist($$)
{
  my ($i, $j) = @_;
  return 0 if ($i == $j);
  ($j,$i) = ($i,$j) if ($i > $j);
  # $i<$j. Go one up from the larger node.
  return 1 + dist($i, ($j-1)>>1);
}

# Determines the average memory distance for nodes as a function of tree distance.
sub get_dists($$)
{
  my $tree = shift;     # Original tree ordering
  my $locality = shift; # Locality-based ordering

  my %dists = ();
  my %counts = ();

  for (my $i=0; $i<length($tree); $i++)
  {
    for (my $j=$i; $j<length($tree); $j++)
    {
      # Find location of $i and $j in the locality-based ordering.
      my $ni = substr($tree, $i, 1);
      my $nj = substr($tree, $j, 1);
      my $it = index($locality, $ni);
      my $jt = index($locality, $nj);
      my $d = (($i <= $j) ? ($j-$i) : ($i-$j));
      my $dt = (($it <= $jt) ? ($jt-$it) : ($it-$jt));
      my $treedist = dist($i, $j);
      $dists{$treedist} += $dt;
      $counts{$treedist}++;
    }
  }
  foreach my $k (sort keys %counts)
  {
    $dists{$k} /= $counts{$k};
  }
  return %dists;
}

my $tree = "ABCDEFGHIJKLMNOPQRSTUVWXYZ01234";    # original (breadth-first prefix) ordering
my $prefix = "ABDHPQIRSEJTUKVWCFLXYMZ0GN12O34";  # depth-first prefix ordering
my $infix = "PHQDRISBTJUEVKWAXLYFZM0C1N2G3O4";   # infix ordering
my $veb = "ABCDHPQIRSEJTUKVMFLXYMZ0GN12O34";     # V.E.B. layout (hope I got it right)

my %original_dists = get_dists($tree, $tree);
my %prefix_dists = get_dists($tree, $prefix);
my %infix_dists = get_dists($tree, $infix);
my %veb_dists = get_dists($tree, $veb);

print "set key top left;\n";
print "set title 'Locality ratios';\n";
print "set xlabel 'tree distance';\n";
print "set ylabel 'avg. memory distance';\n";

print "plot '-' w lp title 'original', '-' w lp title 'prefix ordering', '-' w lp title 'infix ordering', '-' w lp title 'van-Emde-Boas layout';\n";

foreach my $k (sort keys %original_dists)
{
  print "$k $original_dists{$k}\n";
}
print "e\n";
foreach my $k (sort keys %prefix_dists)
{
  print "$k $prefix_dists{$k}\n";
}
print "e\n";
foreach my $k (sort keys %infix_dists)
{
  print "$k $infix_dists{$k}\n";
}
print "e\n";
foreach my $k (sort keys %veb_dists)
{
  print "$k $veb_dists{$k}\n";
}
print "e\n";