manual/tsort.awk

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