-
Notifications
You must be signed in to change notification settings - Fork 315
/
stratify.js
145 lines (126 loc) · 4.01 KB
/
stratify.js
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
import {optional} from "./accessors.js";
import {Node, computeHeight} from "./hierarchy/index.js";
var preroot = {depth: -1},
ambiguous = {},
imputed = {};
function defaultId(d) {
return d.id;
}
function defaultParentId(d) {
return d.parentId;
}
export default function() {
var id = defaultId,
parentId = defaultParentId,
path;
function stratify(data) {
var nodes = Array.from(data),
currentId = id,
currentParentId = parentId,
n,
d,
i,
root,
parent,
node,
nodeId,
nodeKey,
nodeByKey = new Map;
if (path != null) {
const I = nodes.map((d, i) => normalize(path(d, i, data)));
const P = I.map(parentof);
const S = new Set(I).add("");
for (const i of P) {
if (!S.has(i)) {
S.add(i);
I.push(i);
P.push(parentof(i));
nodes.push(imputed);
}
}
currentId = (_, i) => I[i];
currentParentId = (_, i) => P[i];
}
for (i = 0, n = nodes.length; i < n; ++i) {
d = nodes[i], node = nodes[i] = new Node(d);
if ((nodeId = currentId(d, i, data)) != null && (nodeId += "")) {
nodeKey = node.id = nodeId;
nodeByKey.set(nodeKey, nodeByKey.has(nodeKey) ? ambiguous : node);
}
if ((nodeId = currentParentId(d, i, data)) != null && (nodeId += "")) {
node.parent = nodeId;
}
}
for (i = 0; i < n; ++i) {
node = nodes[i];
if (nodeId = node.parent) {
parent = nodeByKey.get(nodeId);
if (!parent) throw new Error("missing: " + nodeId);
if (parent === ambiguous) throw new Error("ambiguous: " + nodeId);
if (parent.children) parent.children.push(node);
else parent.children = [node];
node.parent = parent;
} else {
if (root) throw new Error("multiple roots");
root = node;
}
}
if (!root) throw new Error("no root");
// When imputing internal nodes, only introduce roots if needed.
// Then replace the imputed marker data with null.
if (path != null) {
while (root.data === imputed && root.children.length === 1) {
root = root.children[0], --n;
}
for (let i = nodes.length - 1; i >= 0; --i) {
node = nodes[i];
if (node.data !== imputed) break;
node.data = null;
}
}
root.parent = preroot;
root.eachBefore(function(node) { node.depth = node.parent.depth + 1; --n; }).eachBefore(computeHeight);
root.parent = null;
if (n > 0) throw new Error("cycle");
return root;
}
stratify.id = function(x) {
return arguments.length ? (id = optional(x), stratify) : id;
};
stratify.parentId = function(x) {
return arguments.length ? (parentId = optional(x), stratify) : parentId;
};
stratify.path = function(x) {
return arguments.length ? (path = optional(x), stratify) : path;
};
return stratify;
}
// To normalize a path, we coerce to a string, strip the trailing slash if any
// (as long as the trailing slash is not immediately preceded by another slash),
// and add leading slash if missing.
function normalize(path) {
path = `${path}`;
let i = path.length;
if (slash(path, i - 1) && !slash(path, i - 2)) path = path.slice(0, -1);
return path[0] === "/" ? path : `/${path}`;
}
// Walk backwards to find the first slash that is not the leading slash, e.g.:
// "/foo/bar" ⇥ "/foo", "/foo" ⇥ "/", "/" ↦ "". (The root is special-cased
// because the id of the root must be a truthy value.)
function parentof(path) {
let i = path.length;
if (i < 2) return "";
while (--i > 1) if (slash(path, i)) break;
return path.slice(0, i);
}
// Slashes can be escaped; to determine whether a slash is a path delimiter, we
// count the number of preceding backslashes escaping the forward slash: an odd
// number indicates an escaped forward slash.
function slash(path, i) {
if (path[i] === "/") {
let k = 0;
while (i > 0 && path[--i] === "\\") ++k;
if ((k & 1) === 0) return true;
}
return false;
}