leaves.awk

   1 function first(A,     i)
   2 {
   3         for(i in A) {
   4                 delete A[i];
   5                 return i;
   6         }
   7         return 0;
   8 }
   9 {
  10         if (dir == "push")
  11                 tree[$2] = tree[$2] " " $1;
  12         else
  13                 tree[$1] = tree[$1] " " $2;
  14 }
  15 END {
  16         queue[start] = 1;
  17         while(1)
  18         {
  19                 candidate = first(queue);
  20                 if(!candidate)
  21                         break;
  22                 if(candidate in processed)
  23                         continue;
  24                 processed[candidate] = 1;
  25                 if(candidate in tree)
  26                 {
  27                         new_candidates = tree[candidate];
  28                         split(new_candidates, tmp);
  29                         for(c in tmp)
  30                                 queue[tmp[c]] = 1;
  31                 }
  32                 else
  33                 {
  34                         leaves[candidate] = 1;
  35                 }
  36         }
  37         for(leave in leaves)
  38                 print leave;
  39 }