manual/tsort.awk


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#!/usr/bin/awk -f
# Generate topologically sorted list of manual chapters.
# Copyright (C) 1998-2017 Free Software Foundation, Inc.
# Written by Ulrich Drepper <drepper@cygnus.com>, 1998.

BEGIN {
  cnt = 0
  dnt = 0
}
{
  to[dnt] = $1
  from[dnt] = $2
  ++dnt
  all[cnt++] = $1
}
END {
  do {
    moved = 0
    for (i = 0; i < dnt; ++i) {
      for (j = 0; j < cnt; ++j) {
	if (all[j] == from[i]) {
	  for (k = j + 1; k < cnt; ++k) {
	    if (all[k] == to[i]) {
	      break;
	    }
	  }
	  if (k < cnt) {
	    for (l = k - 1; l >= j; --l) {
	      all[l + 1] = all[l]
	    }
	    all[j] = to[i]
	    break;
	  }
	}
      }
      if (j < cnt) {
	moved = 1
	break
      }
    }
  } while (moved)

  for (i = 0; i < cnt; ++i) {
    print all[i];
  }
}