manual/tsort.awk

   1 #!/usr/bin/awk -f
   2 # Generate topologically sorted list of manual chapters.
   3 # Copyright (C) 1998-2017 Free Software Foundation, Inc.
   4 # Written by Ulrich Drepper <drepper@cygnus.com>, 1998.
   5
   6 BEGIN {
   7   cnt = 0
   8   dnt = 0
   9 }
  10 {
  11   to[dnt] = $1
  12   from[dnt] = $2
  13   ++dnt
  14   all[cnt++] = $1
  15 }
  16 END {
  17   do {
  18     moved = 0
  19     for (i = 0; i < dnt; ++i) {
  20       for (j = 0; j < cnt; ++j) {
  21         if (all[j] == from[i]) {
  22           for (k = j + 1; k < cnt; ++k) {
  23             if (all[k] == to[i]) {
  24               break;
  25             }
  26           }
  27           if (k < cnt) {
  28             for (l = k - 1; l >= j; --l) {
  29               all[l + 1] = all[l]
  30             }
  31             all[j] = to[i]
  32             break;
  33           }
  34         }
  35       }
  36       if (j < cnt) {
  37         moved = 1
  38         break
  39       }
  40     }
  41   } while (moved)
  42
  43   for (i = 0; i < cnt; ++i) {
  44     print all[i];
  45   }
  46 }