1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 |
|
10 |
|
11 |
|
12 |
|
13 | import * as go from '../release/go-module.js';
|
14 |
|
15 |
|
16 |
|
17 |
|
18 |
|
19 |
|
20 |
|
21 |
|
22 |
|
23 |
|
24 |
|
25 |
|
26 |
|
27 |
|
28 |
|
29 |
|
30 |
|
31 |
|
32 | export class SwimLaneLayout extends go.LayeredDigraphLayout {
|
33 |
|
34 | private _laneProperty: string | ((d: any) => string) = "lane"; // how to get lane identifier string from node data
|
35 | private _laneNames: Array<string> = []; // lane names, may be sorted using this.laneComparer
|
36 |
|
37 | private _laneComparer: ((a:string, b: string) => number) | null = null;
|
38 | private _laneSpacing: number = 0; // in columns
|
39 |
|
40 | private _router: any = { linkSpacing: 4 };
|
41 | private _reducer: any = null;
|
42 |
|
43 | // computed, read-only state
|
44 | private readonly _lanePositions: go.Map<string, number> = new go.Map(); // lane names --> start columns, left to right
|
45 | private readonly _laneBreadths: go.Map<string, number> = new go.Map(); // lane names --> needed width in columns
|
46 |
|
47 | // internal state
|
48 | private _layers: Array<Array<go.LayeredDigraphVertex>> = [[]];
|
49 | private _neededSpaces: Array<number> = [];
|
50 |
|
51 |
|
52 | /**
|
53 | * Gets or sets the name of the data property that holds the string which is the name of the lane that the node should be in.
|
54 | * The default value is "lane".
|
55 | */
|
56 | get laneProperty(): string | ((d: any) => string) { return this._laneProperty; }
|
57 | set laneProperty(val: string | ((d: any) => string)) {
|
58 | if (typeof val !== 'string' && typeof val !== 'function') throw new Error("new value for SwimLaneLayout.laneProperty must be a property name, not: " + val);
|
59 | if (this._laneProperty !== val) {
|
60 | this._laneProperty = val;
|
61 | this.invalidateLayout();
|
62 | }
|
63 | }
|
64 |
|
65 | /**
|
66 | * Gets or sets an Array of lane names.
|
67 | * If you set this before a layout happens, it will use those lanes in that order.
|
68 | * Any additional lane names that it discovers will be added to the end of this Array.
|
69 | *
|
70 | * This property is reset to an empty Array at the end of each layout.
|
71 | * The default value is an empty Array.
|
72 | */
|
73 | get laneNames(): Array<string> { return this._laneNames; }
|
74 | set laneNames(val: Array<string>) {
|
75 | if (!Array.isArray(val)) throw new Error("new value for SwimLaneLayout.laneNames must be an Array, not: " + val);
|
76 | if (this._laneNames !== val) {
|
77 | this._laneNames = val;
|
78 | this.invalidateLayout();
|
79 | }
|
80 | }
|
81 |
|
82 | /**
|
83 | * Gets or sets a function by which to compare lane names, for ordering the lanes within the {@link #laneNames} Array.
|
84 | * By default the function is null -- the lanes are not sorted.
|
85 | */
|
86 | get laneComparer(): ((a: string, b: string) => number) | null { return this._laneComparer; }
|
87 | set laneComparer(val: ((a: string, b: string) => number) | null) {
|
88 | if (typeof val !== 'function') throw new Error("new value for SwimLaneLayout.laneComparer must be a function, not: " + val);
|
89 | if (this._laneComparer !== val) {
|
90 | this._laneComparer = val;
|
91 | this.invalidateLayout();
|
92 | }
|
93 | }
|
94 |
|
95 | /**
|
96 | * Gets or sets the amount of additional space it allocates between the lanes.
|
97 | * This number specifies the number of columns, with the same meaning as {@link LayeredDigraphLayout#columnSpacing}.
|
98 | * The number unit is not in document coordinate or pixels.
|
99 | * The default value is zero columns.
|
100 | */
|
101 | get laneSpacing(): number { return this._laneSpacing; }
|
102 | set laneSpacing(val: number) {
|
103 | if (typeof val !== 'number') throw new Error("new value for SwimLaneLayout.laneSpacing must be a number, not: " + val);
|
104 | if (this._laneSpacing !== val) {
|
105 | this._laneSpacing = val;
|
106 | this.invalidateLayout();
|
107 | }
|
108 | }
|
109 |
|
110 | /**
|
111 | * @hidden
|
112 | */
|
113 | get router(): any { return this._router; }
|
114 | set router(val: any) {
|
115 | if (this._router !== val) {
|
116 | this._router = val;
|
117 | this.invalidateLayout();
|
118 | }
|
119 | }
|
120 |
|
121 | /**
|
122 | * @hidden
|
123 | */
|
124 | get reducer(): any { return this._reducer; }
|
125 | set reducer(val: any) {
|
126 | if (this._reducer !== val) {
|
127 | this._reducer = val;
|
128 | if (val) {
|
129 | const lay = this;
|
130 | val.findLane = function(v: go.LayeredDigraphVertex) { return lay.getLane(v); }
|
131 | val.getIndex = function(v: go.LayeredDigraphVertex): number { return v.index; }
|
132 | val.getBary = function(v: go.LayeredDigraphVertex): number { return (v as any).bary || 0; }
|
133 | val.setBary = function(v: go.LayeredDigraphVertex, val: number) { (v as any).bary = val; }
|
134 | val.getConnectedNodesIterator = function(v: go.LayeredDigraphVertex) { return v.vertexes; }
|
135 | }
|
136 | this.invalidateLayout();
|
137 | }
|
138 | }
|
139 |
|
140 | /**
|
141 | * The computed positions of each lane,
|
142 | * in the form of a {@link Map} mapping lane names (strings) to numbers.
|
143 | */
|
144 | protected get lanePositions(): go.Map<string, number> { return this._lanePositions; }
|
145 |
|
146 | /**
|
147 | * The computed breadths (widths or heights depending on the direction) of each lane,
|
148 | * in the form of a {@link Map} mapping lane names (strings) to numbers.
|
149 | */
|
150 | protected get laneBreadths(): go.Map<string, number> { return this._laneBreadths; }
|
151 |
|
152 | /**
|
153 | * @hidden
|
154 | * @param coll
|
155 | */
|
156 | doLayout(coll: (go.Diagram | go.Group | go.Iterable<go.Part>)): void {
|
157 | this.lanePositions.clear(); // lane names --> start columns, left to right
|
158 | this.laneBreadths.clear(); // lane names --> needed width in columns
|
159 | this._layers = [[]];
|
160 | this._neededSpaces = [];
|
161 | super.doLayout(coll);
|
162 | this.lanePositions.clear();
|
163 | this.laneBreadths.clear();
|
164 | this._layers = [[]];
|
165 | this._neededSpaces = [];
|
166 | this.laneNames = []; // clear out for next layout
|
167 | }
|
168 |
|
169 | /**
|
170 | * @hidden
|
171 | * @param v
|
172 | * @param topleft
|
173 | */
|
174 | nodeMinLayerSpace(v: go.LayeredDigraphVertex, topleft: boolean): number {
|
175 | if (!this._neededSpaces) this._neededSpaces = this.computeNeededLayerSpaces(this.network as go.LayeredDigraphNetwork);
|
176 | if (v.node === null) return 0;
|
177 | let lay = v.layer;
|
178 | if (!topleft) {
|
179 | if (lay > 0) lay--;
|
180 | }
|
181 | const overlaps = (this._neededSpaces[lay] || 0)/2;
|
182 | const edges = this.countEdgesForDirection(v, (this.direction > 135) ? !topleft : topleft);
|
183 | const needed = Math.max(overlaps, edges) * this.router.linkSpacing * 1.5;
|
184 | if (this.direction === 90 || this.direction === 270) {
|
185 | if (topleft) {
|
186 | return v.focus.y + 10 + needed;
|
187 | } else {
|
188 | return v.bounds.height - v.focus.y + 10 + needed;
|
189 | }
|
190 | } else {
|
191 | if (topleft) {
|
192 | return v.focus.x + 10 + needed;
|
193 | } else {
|
194 | return v.bounds.width - v.focus.x + 10 + needed;
|
195 | }
|
196 | }
|
197 | }
|
198 |
|
199 | private countEdgesForDirection(vertex: go.LayeredDigraphVertex, topleft: boolean) {
|
200 | let c = 0;
|
201 | const lay = vertex.layer;
|
202 | vertex.edges.each(function(e) {
|
203 | if (topleft) {
|
204 | if ((e.getOtherVertex(vertex) as go.LayeredDigraphVertex).layer >= lay) c++;
|
205 | } else {
|
206 | if ((e.getOtherVertex(vertex) as go.LayeredDigraphVertex).layer <= lay) c++;
|
207 | }
|
208 | });
|
209 | return c;
|
210 | }
|
211 |
|
212 | private computeNeededLayerSpaces(net: go.LayeredDigraphNetwork): Array<number> {
|
213 | // group all edges by their connected vertexes' least layer
|
214 | const layerMinEdges: Array<Array<go.LayeredDigraphEdge>> = [];
|
215 | net.edges.each(function(e) {
|
216 |
|
217 | const f = e.fromVertex as go.LayeredDigraphVertex;
|
218 | const t = e.toVertex as go.LayeredDigraphVertex;
|
219 | if (f.column === t.column) return;
|
220 | if (Math.abs(f.layer-t.layer) > 1) return;
|
221 | const lay = Math.min(f.layer, t.layer);
|
222 | let arr = layerMinEdges[lay];
|
223 | if (!arr) arr = layerMinEdges[lay] = [];
|
224 | arr.push(e as go.LayeredDigraphEdge);
|
225 | });
|
226 | // sort each array of edges by their lowest connected vertex column
|
227 | // for edges with the same minimum column, sort by their maximum column
|
228 | const layerMaxEdges: Array<Array<go.LayeredDigraphEdge>> = []; // same as layerMinEdges, but sorted by maximum column
|
229 | layerMinEdges.forEach(function(arr, lay) {
|
230 | if (!arr) return;
|
231 | arr.sort(function(e1, e2) {
|
232 | const f1c = (e1.fromVertex as go.LayeredDigraphVertex).column;
|
233 | const t1c = (e1.toVertex as go.LayeredDigraphVertex).column;
|
234 | const f2c = (e2.fromVertex as go.LayeredDigraphVertex).column;
|
235 | const t2c = (e2.toVertex as go.LayeredDigraphVertex).column;
|
236 | const e1mincol = Math.min(f1c, t1c);
|
237 | const e2mincol = Math.min(f2c, t2c);
|
238 | if (e1mincol > e2mincol) return 1;
|
239 | if (e1mincol < e2mincol) return -1;
|
240 | const e1maxcol = Math.max(f1c, t1c);
|
241 | const e2maxcol = Math.max(f2c, t2c);
|
242 | if (e1maxcol > e2maxcol) return 1;
|
243 | if (e1maxcol < e2maxcol) return -1;
|
244 | return 0;
|
245 | });
|
246 | layerMaxEdges[lay] = arr.slice(0);
|
247 | layerMaxEdges[lay].sort(function(e1, e2) {
|
248 | const f1c = (e1.fromVertex as go.LayeredDigraphVertex).column;
|
249 | const t1c = (e1.toVertex as go.LayeredDigraphVertex).column;
|
250 | const f2c = (e2.fromVertex as go.LayeredDigraphVertex).column;
|
251 | const t2c = (e2.toVertex as go.LayeredDigraphVertex).column;
|
252 | const e1maxcol = Math.max(f1c, t1c);
|
253 | const e2maxcol = Math.max(f2c, t2c);
|
254 | if (e1maxcol > e2maxcol) return 1;
|
255 | if (e1maxcol < e2maxcol) return -1;
|
256 | const e1mincol = Math.min(f1c, t1c);
|
257 | const e2mincol = Math.min(f2c, t2c);
|
258 | if (e1mincol > e2mincol) return 1;
|
259 | if (e1mincol < e2mincol) return -1;
|
260 | return 0;
|
261 | });
|
262 | });
|
263 |
|
264 | // run through each array of edges to count how many overlaps there might be
|
265 | const layerOverlaps: Array<number> = [];
|
266 | layerMinEdges.forEach(function(arr, lay) {
|
267 | const mins = arr;
|
268 | const maxs = layerMaxEdges[lay];
|
269 | let maxoverlap = 0;
|
270 | if (mins && maxs && mins.length > 1 && maxs.length > 1) {
|
271 | let mini = 0;
|
272 | let min = null;
|
273 | let maxi = 0;
|
274 | let max = null;
|
275 | while (mini < mins.length || maxi < maxs.length) {
|
276 | if (mini < mins.length) min = mins[mini];
|
277 | const mincol = min ? Math.min((min.fromVertex as go.LayeredDigraphVertex).column,(min.toVertex as go.LayeredDigraphVertex).column) : 0;
|
278 | if (maxi < maxs.length) max = maxs[maxi];
|
279 | const maxcol = max ? Math.max((max.fromVertex as go.LayeredDigraphVertex).column, (max.toVertex as go.LayeredDigraphVertex).column) : Infinity;
|
280 | maxoverlap = Math.max(maxoverlap, Math.abs(mini-maxi));
|
281 | if (mincol <= maxcol && mini < mins.length) {
|
282 | mini++;
|
283 | } else if (maxi < maxs.length) {
|
284 | maxi++;
|
285 | }
|
286 | }
|
287 | }
|
288 | layerOverlaps[lay] = maxoverlap * 1.5;
|
289 | });
|
290 | return layerOverlaps;
|
291 | }
|
292 |
|
293 | private setupLanes(): void {
|
294 | // set up some data structures
|
295 | const layout = this;
|
296 | const laneNameSet = new go.Set().addAll(this.laneNames);
|
297 | const laneIndexes = new go.Map(); // lane names --> index when sorted
|
298 |
|
299 | const vit = (this.network as go.LayeredDigraphNetwork).vertexes.iterator;
|
300 | while (vit.next()) {
|
301 | const v = vit.value as go.LayeredDigraphVertex;
|
302 |
|
303 | const lane = this.getLane(v); // cannot call findLane yet
|
304 | if (lane !== null && !laneNameSet.has(lane)) {
|
305 | laneNameSet.add(lane);
|
306 | this.laneNames.push(lane);
|
307 | }
|
308 |
|
309 | const layer = v.layer;
|
310 | if (layer >= 0) {
|
311 | const arr = this._layers[layer];
|
312 | if (!arr) {
|
313 | this._layers[layer] = [v];
|
314 | } else {
|
315 | arr.push(v);
|
316 | }
|
317 | }
|
318 | }
|
319 |
|
320 | // sort laneNames and initialize laneIndexes
|
321 | if (typeof this.laneComparer === "function") this.laneNames.sort(this.laneComparer);
|
322 | for (let i = 0; i < this.laneNames.length; i++) {
|
323 | laneIndexes.add(this.laneNames[i], i);
|
324 | }
|
325 | // now OK to call findLane
|
326 |
|
327 | // sort vertexes so that vertexes are grouped by lane
|
328 | for (let i = 0; i <= this.maxLayer; i++) {
|
329 | this._layers[i].sort(function(a, b) { return layout.compareVertexes(a, b); });
|
330 | }
|
331 | }
|
332 |
|
333 | /**
|
334 | * @hidden
|
335 | * Replace the standard reduceCrossings behavior so that it respects lanes.
|
336 | */
|
337 | reduceCrossings(): void {
|
338 | this.setupLanes();
|
339 |
|
340 | // this just cares about the .index and ignores .column
|
341 | const layers = this._layers;
|
342 | const red = this.reducer;
|
343 | if (red) {
|
344 | for (let i = 0; i < layers.length-1; i++) {
|
345 | red.reduceCrossings(layers[i], layers[i+1]);
|
346 | layers[i].forEach(function(v, j) { v.index = j; })
|
347 | }
|
348 | for (let i = layers.length-1; i > 0; i--) {
|
349 | red.reduceCrossings(layers[i], layers[i-1]);
|
350 | layers[i].forEach(function(v, j) { v.index = j; })
|
351 | }
|
352 | }
|
353 |
|
354 | this.computeLanes(); // and recompute all vertex.column values
|
355 | }
|
356 |
|
357 | private computeLanes(): void {
|
358 | // compute needed width for each lane, in columns
|
359 | for (let i = 0; i < this.laneNames.length; i++) {
|
360 | const lane = this.laneNames[i];
|
361 | this.laneBreadths.add(lane, this.computeMinLaneWidth(lane));
|
362 | }
|
363 | const lwidths = new go.Map<string, number>(); // reused for each layer
|
364 | for (let i = 0; i <= this.maxLayer; i++) {
|
365 | const arr = this._layers[i];
|
366 | if (arr) {
|
367 | const layout = this;
|
368 | // now run through Array finding width (in columns) of each lane
|
369 | // and max with this.laneBreadths.get(lane)
|
370 | for (let j = 0; j < arr.length; j++) {
|
371 | const v = arr[j];
|
372 | const w = this.nodeMinColumnSpace(v, true) + 1 + this.nodeMinColumnSpace(v, false);
|
373 | const ln = this.findLane(v) || "";
|
374 | const totw = lwidths.get(ln);
|
375 | if (totw === null) {
|
376 | lwidths.set(ln, w);
|
377 | } else {
|
378 | lwidths.set(ln, totw + w);
|
379 | }
|
380 | }
|
381 | lwidths.each(function(kvp) {
|
382 | const lane = kvp.key;
|
383 | const colsInLayer = kvp.value;
|
384 | const colsMax = layout.laneBreadths.get(lane) || 0;
|
385 | if (colsInLayer > colsMax) layout.laneBreadths.set(lane, colsInLayer);
|
386 | })
|
387 | lwidths.clear();
|
388 | }
|
389 | }
|
390 |
|
391 | // compute starting positions for each lane
|
392 | let x = 0;
|
393 | for (let i = 0; i < this.laneNames.length; i++) {
|
394 | const lane = this.laneNames[i];
|
395 | this.lanePositions.set(lane, x);
|
396 | const w = this.laneBreadths.get(lane) || 0;
|
397 | x += w + this.laneSpacing;
|
398 | }
|
399 |
|
400 | this.renormalizeColumns();
|
401 | }
|
402 |
|
403 | private renormalizeColumns(): void {
|
404 | // set new column and index on each vertex
|
405 | for (let i = 0; i < this._layers.length; i++) {
|
406 | let prevlane = null;
|
407 | let c = 0;
|
408 | const arr = this._layers[i];
|
409 | for (let j = 0; j < arr.length; j++) {
|
410 | const v = arr[j];
|
411 | v.index = j;
|
412 |
|
413 | const l = this.findLane(v);
|
414 | if (l && prevlane !== l) {
|
415 | c = this.lanePositions.get(l) || 0;
|
416 | const w = this.laneBreadths.get(l) || 0;
|
417 | // compute needed breadth within lane, in columns
|
418 | let z = this.nodeMinColumnSpace(v, true) + 1 + this.nodeMinColumnSpace(v, false);
|
419 | let k = j+1;
|
420 | while (k < arr.length && this.findLane(arr[k]) === l) {
|
421 | const vz = arr[k];
|
422 | z += this.nodeMinColumnSpace(vz, true) + 1 + this.nodeMinColumnSpace(vz, false);
|
423 | k++;
|
424 | }
|
425 | // if there is extra space, shift the vertexes to the middle of the lane
|
426 | if (z < w) {
|
427 | c += Math.floor((w-z)/2);
|
428 | }
|
429 | }
|
430 |
|
431 | c += this.nodeMinColumnSpace(v, true);
|
432 | v.column = c;
|
433 | c += 1;
|
434 | c += this.nodeMinColumnSpace(v, false);
|
435 | prevlane = l;
|
436 | }
|
437 | }
|
438 | }
|
439 |
|
440 | /**
|
441 | * Return the minimum lane width, in columns
|
442 | * @param lane
|
443 | */
|
444 | public computeMinLaneWidth(lane: string): number { return 0; }
|
445 |
|
446 | /**
|
447 | * @hidden
|
448 | * Disable normal straightenAndPack behavior, which would mess up the columns.
|
449 | */
|
450 | straightenAndPack(): void {}
|
451 |
|
452 | /**
|
453 | * Given a vertex, get the lane (name) that its node belongs in.
|
454 | * If the lane appears to be undefined, this returns the empty string.
|
455 | * For dummy vertexes (with no node) this will return null.
|
456 | * @param v
|
457 | */
|
458 | protected getLane(v: go.LayeredDigraphVertex | null): string | null {
|
459 | if (v === null) return null;
|
460 | const node = v.node;
|
461 | if (node !== null) {
|
462 | const data = node.data;
|
463 | if (data !== null) {
|
464 | let lane = null;
|
465 | if (typeof this.laneProperty === "function") {
|
466 | lane = this.laneProperty(data);
|
467 | } else {
|
468 | lane = data[this.laneProperty];
|
469 | }
|
470 | if (typeof lane === "string") return lane;
|
471 | return ""; // default lane
|
472 | }
|
473 | }
|
474 | return null;
|
475 | }
|
476 |
|
477 | /**
|
478 | * This is just like {@link #getLane} but handles dummy vertexes
|
479 | * for which the {@link #getLane} returns null by returning the
|
480 | * lane of the edge's source or destination vertex.
|
481 | * This can only be called after the lanes have been set up internally.
|
482 | * @param v
|
483 | */
|
484 | protected findLane(v: go.LayeredDigraphVertex | null): string | null {
|
485 | if (v !== null) {
|
486 | const lane = this.getLane(v);
|
487 | if (lane !== null) {
|
488 | return lane;
|
489 | } else {
|
490 | const srcv = this.findRealSource(v.sourceEdges.first());
|
491 | const dstv = this.findRealDestination(v.destinationEdges.first());
|
492 | const srcLane = this.getLane(srcv);
|
493 | const dstLane = this.getLane(dstv);
|
494 | if (srcLane !== null || dstLane !== null) {
|
495 | if (srcLane === dstLane) return srcLane;
|
496 | if (srcLane !== null) return srcLane;
|
497 | if (dstLane !== null) return dstLane;
|
498 | }
|
499 | }
|
500 | }
|
501 | return null;
|
502 | }
|
503 |
|
504 | private findRealSource(e: go.LayoutEdge | null): go.LayeredDigraphVertex | null {
|
505 | if (e === null) return null;
|
506 | const fv = e.fromVertex as go.LayeredDigraphVertex;
|
507 | if (fv && fv.node) return fv;
|
508 | return this.findRealSource(fv.sourceEdges.first());
|
509 | }
|
510 |
|
511 | private findRealDestination(e: go.LayoutEdge | null): go.LayeredDigraphVertex | null {
|
512 | if (e === null) return null;
|
513 | const tv = e.toVertex as go.LayeredDigraphVertex;
|
514 | if (tv.node) return tv;
|
515 | return this.findRealDestination(tv.destinationEdges.first());
|
516 | }
|
517 |
|
518 | private compareVertexes(v: go.LayeredDigraphVertex, w: go.LayeredDigraphVertex) {
|
519 | let laneV = this.findLane(v);
|
520 | if (laneV === null) laneV = "";
|
521 | let laneW = this.findLane(w);
|
522 | if (laneW === null) laneW = "";
|
523 | if (laneV < laneW) return -1;
|
524 | if (laneV > laneW) return 1;
|
525 | return 0;
|
526 | };
|
527 | }
|
528 |
|
\ | No newline at end of file |