#!/usr/bin/perl
# Variablendeklarationen erzwingen (Bessere Fehlererkennung)
use strict;
# Mehr Warungen (undefinierte Variablen etc.)
use warnings;
# Formatierte Ausgabe von Variablen (Datenstrukturen)
use Data::Dumper;

# Die Ausgangsadaten
my %HoA = (
    root=>['A', 'B'],
    A=>['C', 'D'],
    B=>['E', 'F'],
    C=>['G', 'H'],
    D=>['I'],
    G=>['K'],
    E=>['J'],
  );

# Einen Baum aus den Daten Bauen
# $tree : Der erzeugte Baum
# $names : Eine Liste aller Namen der vorhanden Knoten
my ($tree,$names)=make_tree(\%HoA,'root');
# Root hinzufügen (fehlt bei der Erzeugung)
$tree={'root' => $tree};

# Testweise Ausgabe des Baumes
print Dumper($tree);

# Aus dem Baum eine Liste mit "Pfaden" machen
# Alle Knoten von der Wurzel "root"
# bis zum entsprechenden Knoten
my @list=make_list($tree);

# Test Ausagabe
#print Dumper(\@list);

# Aus der Liste mit den Knotennamen
# und der Pfadliste die Abstände bestimmen

# mache eine Kopie der Namen
my @nn=@$names;

# entferne immer den ersten Eintrag bis die Liste leer ist
# teste das gegen den Rest der liste
# Da A <> B == B <> A braucht jede Kombination nur einmal getestet werden
# Da A <> A == 0 ist braucht man das nicht zu testen.
# Allso nimm einen wert aus der liste und teste ihn mit dem Rest.
# damit sind alle interessanten Kombinationen getestet

while(my $name=shift(@nn))
{
  # gehe den Rest der Liste durch
  for my $nn (@nn)
  {
    # bestimme die "Distanz"
    my $dist=make_diff(\@list,$name,$nn);
    # gib das Ergebnis aus
    print "dist $name <> $nn => $dist\n";
  }
}


########################################################################
# das Erzeugen des Baumes aus den Rohdaten
# ist eine rekursive Funktion
# sie ruft sich selber immer wieder mit neuen Werten auf,
# bis alle Elemente erfasst sind.
sub make_tree
{
  # die Rohdaten
  my $data=shift;
  # der zu erzeugende Knoten
  my $node=shift;
  # "nichts" turcükgeben wenn dieser Knoten keine Kinder hat
  return '',[$node] unless(exists($data->{$node}));

  # Der Hash der später die kinderkoten halten wird
  my $ref={};

  # Liste aller Knotennamen
  my @names=($node);

  # gehe alle Namen der Kinder des Kotens durch
  for my $name (@{$data->{$node}})
  {
    # Bestimme den Darunterliegenden Baum durch Rekursion
    my $nn;
    ($ref->{$name},$nn)=make_tree($data,$name);
    # Alle Namen der gefunden Knoten in die liste der Knoten eifügen
    push(@names,@$nn);
  }
  # die Ergebnisse zurückgeben
  return $ref,\@names;
}

# aus dem Baum eine Liste mit Pfaden machen
# Dazu wird der Baum rekursiv durchgegenagen
# und Zu jedem Teilbaum eine liste von Pfaden erstellt,
# bis keine Teilbäume mehr vorhanden sind
sub make_list
{
  # der zu untersuchende Teilbaum (Knoten mit KindElementen)
  my $tree=shift;

  # Die Liste mit Pfaden
  my @lst;

  Gehe alle KindElemente dieses Knotens
  for my $node (keys(%$tree))
  {
    #füge Dieses Kind als Pfad hinzu
    push(@lst,[$node]);

    #Wenn das Kind Kinder hat
    # dann ruft die Funtion sich selber auf,
    # um diese zu testen
    if(ref($tree->{$node}))
    {
      # rufe dich selber auf
      my @ret=make_list($tree->{$node});
      # vervollstänige die Liste mit den ergänzten Pfaden
      push(@lst,[$node,@$_]) for(@ret);
    }
  }

  # gib die fertige liste zurück
  return @lst;
}

# ermittle den Abstand der Knoten
# das solltest du überarbeiten
# ist nur ein schneller Wurf.
sub make_diff
{
  # liste der Pfade
  my $list=shift;
  # Knoten 1
  my $name1=shift;
  # knoten 2
  my $name2=shift;
  # zwischen den beiden soll der Absand bestimmt werden

  # die zum knoten gehörigen Pfade bestimmen
  my $l1;
  my $l2;

  # gehe die Liste durch
  # und wenn das Letzte Element des Pfades der gesuchte Knoten ist,
  # dann übernehme den Pfad
  for my $elm (@list)
  {
    $l1=$elm if($elm->[-1] eq $name1);
    $l2=$elm if($elm->[-1] eq $name2);
    # höre auf wenn die Pfade zu den Knoten gefunden wurden
    last if($1 and $l2);
  }
  # wenn nach der suche keine Pfade gefunden wurden,
  # dann gibt es sie nicht im Baum
  # der Abstand ist unbestimmt
  return -1 if(!$l1 or !$l2);

  # die vorläufige Abstand entspricht der Schritte Vom Ersten Knoten
  # bis zur Wurzel und zurück zum zweiten Knoten
  my $size=$#$l1+$#$l2+1;

  # wenn zwei Pfade gleiche Teilpfade haben
  # dann ziehe immer zwei ab bis sich die Pfade trennen
  my $p=0;
  while($p<$#$l1 and $p<$#$l2)
  {
    if($l1->[$p] eq $l2->[$p])
    { $size-=2; }
    else
    { last; }
    $p++;
  }

  # wenn eines ein Endpunkt ist (keine kinder)
  # dann verkürze den Abstand
  $size-- if($p==$#$l1 || $p==$#$l2);

  # Rückgabe des Abstandes
  return $size;
}