| 1 | import { csTdfs } from './csTdfs'
|
| 2 |
|
| 3 | /**
|
| 4 | * Post order a tree of forest
|
| 5 | *
|
| 6 | * @param {Array} parent The tree or forest
|
| 7 | * @param {Number} n Number of columns
|
| 8 | *
|
| 9 | * Reference: http://faculty.cse.tamu.edu/davis/publications.html
|
| 10 | */
|
| 11 | export function csPost (parent, n) {
|
| 12 | // check inputs
|
| 13 | if (!parent) { return null }
|
| 14 | // vars
|
| 15 | let k = 0
|
| 16 | let j
|
| 17 | // allocate result
|
| 18 | const post = [] // (n)
|
| 19 | // workspace, head: first n entries, next: next n entries, stack: last n entries
|
| 20 | const w = [] // (3 * n)
|
| 21 | const head = 0
|
| 22 | const next = n
|
| 23 | const stack = 2 * n
|
| 24 | // initialize workspace
|
| 25 | for (j = 0; j < n; j++) {
|
| 26 | // empty linked lists
|
| 27 | w[head + j] = -1
|
| 28 | }
|
| 29 | // traverse nodes in reverse order
|
| 30 | for (j = n - 1; j >= 0; j--) {
|
| 31 | // check j is a root
|
| 32 | if (parent[j] === -1) { continue }
|
| 33 | // add j to list of its parent
|
| 34 | w[next + j] = w[head + parent[j]]
|
| 35 | w[head + parent[j]] = j
|
| 36 | }
|
| 37 | // loop nodes
|
| 38 | for (j = 0; j < n; j++) {
|
| 39 | // skip j if it is not a root
|
| 40 | if (parent[j] !== -1) { continue }
|
| 41 | // depth-first search
|
| 42 | k = csTdfs(j, k, w, head, next, post, stack)
|
| 43 | }
|
| 44 | return post
|
| 45 | }
|