csPost.js (1280B)
1 "use strict"; 2 3 Object.defineProperty(exports, "__esModule", { 4 value: true 5 }); 6 exports.csPost = csPost; 7 8 var _csTdfs = require("./csTdfs.js"); 9 10 /** 11 * Post order a tree of forest 12 * 13 * @param {Array} parent The tree or forest 14 * @param {Number} n Number of columns 15 * 16 * Reference: http://faculty.cse.tamu.edu/davis/publications.html 17 */ 18 function csPost(parent, n) { 19 // check inputs 20 if (!parent) { 21 return null; 22 } // vars 23 24 25 var k = 0; 26 var j; // allocate result 27 28 var post = []; // (n) 29 // workspace, head: first n entries, next: next n entries, stack: last n entries 30 31 var w = []; // (3 * n) 32 33 var head = 0; 34 var next = n; 35 var stack = 2 * n; // initialize workspace 36 37 for (j = 0; j < n; j++) { 38 // empty linked lists 39 w[head + j] = -1; 40 } // traverse nodes in reverse order 41 42 43 for (j = n - 1; j >= 0; j--) { 44 // check j is a root 45 if (parent[j] === -1) { 46 continue; 47 } // add j to list of its parent 48 49 50 w[next + j] = w[head + parent[j]]; 51 w[head + parent[j]] = j; 52 } // loop nodes 53 54 55 for (j = 0; j < n; j++) { 56 // skip j if it is not a root 57 if (parent[j] !== -1) { 58 continue; 59 } // depth-first search 60 61 62 k = (0, _csTdfs.csTdfs)(j, k, w, head, next, post, stack); 63 } 64 65 return post; 66 }