1 | import { a7 as isObjectLike, a8 as baseGetTag, a9 as Symbol$1, aa as isArray, ab as isObject, ac as getNative, ad as eq, ae as isArrayLike, af as isArguments, ag as isBuffer, ah as isTypedArray, ai as baseKeys, aj as isPrototype, ak as memoize, al as overArg, am as ListCache, an as Map, ao as MapCache, ap as root, aq as getTag, ar as nodeUtil, as as baseUnary, at as isLength, v as isFunction, au as Set, av as isEmpty } from "./mermaid-4b4b971d.js";
|
2 | var symbolTag$3 = "[object Symbol]";
|
3 | function isSymbol(value) {
|
4 | return typeof value == "symbol" || isObjectLike(value) && baseGetTag(value) == symbolTag$3;
|
5 | }
|
6 | function arrayMap(array, iteratee) {
|
7 | var index = -1, length = array == null ? 0 : array.length, result = Array(length);
|
8 | while (++index < length) {
|
9 | result[index] = iteratee(array[index], index, array);
|
10 | }
|
11 | return result;
|
12 | }
|
13 | var INFINITY$3 = 1 / 0;
|
14 | var symbolProto$2 = Symbol$1 ? Symbol$1.prototype : void 0, symbolToString = symbolProto$2 ? symbolProto$2.toString : void 0;
|
15 | function baseToString(value) {
|
16 | if (typeof value == "string") {
|
17 | return value;
|
18 | }
|
19 | if (isArray(value)) {
|
20 | return arrayMap(value, baseToString) + "";
|
21 | }
|
22 | if (isSymbol(value)) {
|
23 | return symbolToString ? symbolToString.call(value) : "";
|
24 | }
|
25 | var result = value + "";
|
26 | return result == "0" && 1 / value == -INFINITY$3 ? "-0" : result;
|
27 | }
|
28 | var reWhitespace = /\s/;
|
29 | function trimmedEndIndex(string) {
|
30 | var index = string.length;
|
31 | while (index-- && reWhitespace.test(string.charAt(index))) {
|
32 | }
|
33 | return index;
|
34 | }
|
35 | var reTrimStart = /^\s+/;
|
36 | function baseTrim(string) {
|
37 | return string ? string.slice(0, trimmedEndIndex(string) + 1).replace(reTrimStart, "") : string;
|
38 | }
|
39 | var NAN = 0 / 0;
|
40 | var reIsBadHex = /^[-+]0x[0-9a-f]+$/i;
|
41 | var reIsBinary = /^0b[01]+$/i;
|
42 | var reIsOctal = /^0o[0-7]+$/i;
|
43 | var freeParseInt = parseInt;
|
44 | function toNumber(value) {
|
45 | if (typeof value == "number") {
|
46 | return value;
|
47 | }
|
48 | if (isSymbol(value)) {
|
49 | return NAN;
|
50 | }
|
51 | if (isObject(value)) {
|
52 | var other = typeof value.valueOf == "function" ? value.valueOf() : value;
|
53 | value = isObject(other) ? other + "" : other;
|
54 | }
|
55 | if (typeof value != "string") {
|
56 | return value === 0 ? value : +value;
|
57 | }
|
58 | value = baseTrim(value);
|
59 | var isBinary = reIsBinary.test(value);
|
60 | return isBinary || reIsOctal.test(value) ? freeParseInt(value.slice(2), isBinary ? 2 : 8) : reIsBadHex.test(value) ? NAN : +value;
|
61 | }
|
62 | var INFINITY$2 = 1 / 0, MAX_INTEGER = 17976931348623157e292;
|
63 | function toFinite(value) {
|
64 | if (!value) {
|
65 | return value === 0 ? value : 0;
|
66 | }
|
67 | value = toNumber(value);
|
68 | if (value === INFINITY$2 || value === -INFINITY$2) {
|
69 | var sign = value < 0 ? -1 : 1;
|
70 | return sign * MAX_INTEGER;
|
71 | }
|
72 | return value === value ? value : 0;
|
73 | }
|
74 | function toInteger(value) {
|
75 | var result = toFinite(value), remainder = result % 1;
|
76 | return result === result ? remainder ? result - remainder : result : 0;
|
77 | }
|
78 | function identity(value) {
|
79 | return value;
|
80 | }
|
81 | var objectCreate = Object.create;
|
82 | var baseCreate = function() {
|
83 | function object() {
|
84 | }
|
85 | return function(proto) {
|
86 | if (!isObject(proto)) {
|
87 | return {};
|
88 | }
|
89 | if (objectCreate) {
|
90 | return objectCreate(proto);
|
91 | }
|
92 | object.prototype = proto;
|
93 | var result = new object();
|
94 | object.prototype = void 0;
|
95 | return result;
|
96 | };
|
97 | }();
|
98 | const baseCreate$1 = baseCreate;
|
99 | function apply(func, thisArg, args) {
|
100 | switch (args.length) {
|
101 | case 0:
|
102 | return func.call(thisArg);
|
103 | case 1:
|
104 | return func.call(thisArg, args[0]);
|
105 | case 2:
|
106 | return func.call(thisArg, args[0], args[1]);
|
107 | case 3:
|
108 | return func.call(thisArg, args[0], args[1], args[2]);
|
109 | }
|
110 | return func.apply(thisArg, args);
|
111 | }
|
112 | function noop() {
|
113 | }
|
114 | function copyArray(source, array) {
|
115 | var index = -1, length = source.length;
|
116 | array || (array = Array(length));
|
117 | while (++index < length) {
|
118 | array[index] = source[index];
|
119 | }
|
120 | return array;
|
121 | }
|
122 | var HOT_COUNT = 800, HOT_SPAN = 16;
|
123 | var nativeNow = Date.now;
|
124 | function shortOut(func) {
|
125 | var count = 0, lastCalled = 0;
|
126 | return function() {
|
127 | var stamp = nativeNow(), remaining = HOT_SPAN - (stamp - lastCalled);
|
128 | lastCalled = stamp;
|
129 | if (remaining > 0) {
|
130 | if (++count >= HOT_COUNT) {
|
131 | return arguments[0];
|
132 | }
|
133 | } else {
|
134 | count = 0;
|
135 | }
|
136 | return func.apply(void 0, arguments);
|
137 | };
|
138 | }
|
139 | function constant(value) {
|
140 | return function() {
|
141 | return value;
|
142 | };
|
143 | }
|
144 | var defineProperty = function() {
|
145 | try {
|
146 | var func = getNative(Object, "defineProperty");
|
147 | func({}, "", {});
|
148 | return func;
|
149 | } catch (e) {
|
150 | }
|
151 | }();
|
152 | const defineProperty$1 = defineProperty;
|
153 | var baseSetToString = !defineProperty$1 ? identity : function(func, string) {
|
154 | return defineProperty$1(func, "toString", {
|
155 | "configurable": true,
|
156 | "enumerable": false,
|
157 | "value": constant(string),
|
158 | "writable": true
|
159 | });
|
160 | };
|
161 | const baseSetToString$1 = baseSetToString;
|
162 | var setToString = shortOut(baseSetToString$1);
|
163 | const setToString$1 = setToString;
|
164 | function arrayEach(array, iteratee) {
|
165 | var index = -1, length = array == null ? 0 : array.length;
|
166 | while (++index < length) {
|
167 | if (iteratee(array[index], index, array) === false) {
|
168 | break;
|
169 | }
|
170 | }
|
171 | return array;
|
172 | }
|
173 | function baseFindIndex(array, predicate, fromIndex, fromRight) {
|
174 | var length = array.length, index = fromIndex + (fromRight ? 1 : -1);
|
175 | while (fromRight ? index-- : ++index < length) {
|
176 | if (predicate(array[index], index, array)) {
|
177 | return index;
|
178 | }
|
179 | }
|
180 | return -1;
|
181 | }
|
182 | function baseIsNaN(value) {
|
183 | return value !== value;
|
184 | }
|
185 | function strictIndexOf(array, value, fromIndex) {
|
186 | var index = fromIndex - 1, length = array.length;
|
187 | while (++index < length) {
|
188 | if (array[index] === value) {
|
189 | return index;
|
190 | }
|
191 | }
|
192 | return -1;
|
193 | }
|
194 | function baseIndexOf(array, value, fromIndex) {
|
195 | return value === value ? strictIndexOf(array, value, fromIndex) : baseFindIndex(array, baseIsNaN, fromIndex);
|
196 | }
|
197 | function arrayIncludes(array, value) {
|
198 | var length = array == null ? 0 : array.length;
|
199 | return !!length && baseIndexOf(array, value, 0) > -1;
|
200 | }
|
201 | var MAX_SAFE_INTEGER = 9007199254740991;
|
202 | var reIsUint = /^(?:0|[1-9]\d*)$/;
|
203 | function isIndex(value, length) {
|
204 | var type = typeof value;
|
205 | length = length == null ? MAX_SAFE_INTEGER : length;
|
206 | return !!length && (type == "number" || type != "symbol" && reIsUint.test(value)) && (value > -1 && value % 1 == 0 && value < length);
|
207 | }
|
208 | function baseAssignValue(object, key, value) {
|
209 | if (key == "__proto__" && defineProperty$1) {
|
210 | defineProperty$1(object, key, {
|
211 | "configurable": true,
|
212 | "enumerable": true,
|
213 | "value": value,
|
214 | "writable": true
|
215 | });
|
216 | } else {
|
217 | object[key] = value;
|
218 | }
|
219 | }
|
220 | var objectProto$9 = Object.prototype;
|
221 | var hasOwnProperty$8 = objectProto$9.hasOwnProperty;
|
222 | function assignValue(object, key, value) {
|
223 | var objValue = object[key];
|
224 | if (!(hasOwnProperty$8.call(object, key) && eq(objValue, value)) || value === void 0 && !(key in object)) {
|
225 | baseAssignValue(object, key, value);
|
226 | }
|
227 | }
|
228 | function copyObject(source, props, object, customizer) {
|
229 | var isNew = !object;
|
230 | object || (object = {});
|
231 | var index = -1, length = props.length;
|
232 | while (++index < length) {
|
233 | var key = props[index];
|
234 | var newValue = customizer ? customizer(object[key], source[key], key, object, source) : void 0;
|
235 | if (newValue === void 0) {
|
236 | newValue = source[key];
|
237 | }
|
238 | if (isNew) {
|
239 | baseAssignValue(object, key, newValue);
|
240 | } else {
|
241 | assignValue(object, key, newValue);
|
242 | }
|
243 | }
|
244 | return object;
|
245 | }
|
246 | var nativeMax$2 = Math.max;
|
247 | function overRest(func, start, transform) {
|
248 | start = nativeMax$2(start === void 0 ? func.length - 1 : start, 0);
|
249 | return function() {
|
250 | var args = arguments, index = -1, length = nativeMax$2(args.length - start, 0), array = Array(length);
|
251 | while (++index < length) {
|
252 | array[index] = args[start + index];
|
253 | }
|
254 | index = -1;
|
255 | var otherArgs = Array(start + 1);
|
256 | while (++index < start) {
|
257 | otherArgs[index] = args[index];
|
258 | }
|
259 | otherArgs[start] = transform(array);
|
260 | return apply(func, this, otherArgs);
|
261 | };
|
262 | }
|
263 | function baseRest(func, start) {
|
264 | return setToString$1(overRest(func, start, identity), func + "");
|
265 | }
|
266 | function isIterateeCall(value, index, object) {
|
267 | if (!isObject(object)) {
|
268 | return false;
|
269 | }
|
270 | var type = typeof index;
|
271 | if (type == "number" ? isArrayLike(object) && isIndex(index, object.length) : type == "string" && index in object) {
|
272 | return eq(object[index], value);
|
273 | }
|
274 | return false;
|
275 | }
|
276 | function createAssigner(assigner) {
|
277 | return baseRest(function(object, sources) {
|
278 | var index = -1, length = sources.length, customizer = length > 1 ? sources[length - 1] : void 0, guard = length > 2 ? sources[2] : void 0;
|
279 | customizer = assigner.length > 3 && typeof customizer == "function" ? (length--, customizer) : void 0;
|
280 | if (guard && isIterateeCall(sources[0], sources[1], guard)) {
|
281 | customizer = length < 3 ? void 0 : customizer;
|
282 | length = 1;
|
283 | }
|
284 | object = Object(object);
|
285 | while (++index < length) {
|
286 | var source = sources[index];
|
287 | if (source) {
|
288 | assigner(object, source, index, customizer);
|
289 | }
|
290 | }
|
291 | return object;
|
292 | });
|
293 | }
|
294 | function baseTimes(n, iteratee) {
|
295 | var index = -1, result = Array(n);
|
296 | while (++index < n) {
|
297 | result[index] = iteratee(index);
|
298 | }
|
299 | return result;
|
300 | }
|
301 | var objectProto$8 = Object.prototype;
|
302 | var hasOwnProperty$7 = objectProto$8.hasOwnProperty;
|
303 | function arrayLikeKeys(value, inherited) {
|
304 | var isArr = isArray(value), isArg = !isArr && isArguments(value), isBuff = !isArr && !isArg && isBuffer(value), isType = !isArr && !isArg && !isBuff && isTypedArray(value), skipIndexes = isArr || isArg || isBuff || isType, result = skipIndexes ? baseTimes(value.length, String) : [], length = result.length;
|
305 | for (var key in value) {
|
306 | if ((inherited || hasOwnProperty$7.call(value, key)) && !(skipIndexes &&
|
307 | (key == "length" ||
|
308 | isBuff && (key == "offset" || key == "parent") ||
|
309 | isType && (key == "buffer" || key == "byteLength" || key == "byteOffset") ||
|
310 | isIndex(key, length)))) {
|
311 | result.push(key);
|
312 | }
|
313 | }
|
314 | return result;
|
315 | }
|
316 | function keys(object) {
|
317 | return isArrayLike(object) ? arrayLikeKeys(object) : baseKeys(object);
|
318 | }
|
319 | function nativeKeysIn(object) {
|
320 | var result = [];
|
321 | if (object != null) {
|
322 | for (var key in Object(object)) {
|
323 | result.push(key);
|
324 | }
|
325 | }
|
326 | return result;
|
327 | }
|
328 | var objectProto$7 = Object.prototype;
|
329 | var hasOwnProperty$6 = objectProto$7.hasOwnProperty;
|
330 | function baseKeysIn(object) {
|
331 | if (!isObject(object)) {
|
332 | return nativeKeysIn(object);
|
333 | }
|
334 | var isProto = isPrototype(object), result = [];
|
335 | for (var key in object) {
|
336 | if (!(key == "constructor" && (isProto || !hasOwnProperty$6.call(object, key)))) {
|
337 | result.push(key);
|
338 | }
|
339 | }
|
340 | return result;
|
341 | }
|
342 | function keysIn(object) {
|
343 | return isArrayLike(object) ? arrayLikeKeys(object, true) : baseKeysIn(object);
|
344 | }
|
345 | var reIsDeepProp = /\.|\[(?:[^[\]]*|(["'])(?:(?!\1)[^\\]|\\.)*?\1)\]/, reIsPlainProp = /^\w*$/;
|
346 | function isKey(value, object) {
|
347 | if (isArray(value)) {
|
348 | return false;
|
349 | }
|
350 | var type = typeof value;
|
351 | if (type == "number" || type == "symbol" || type == "boolean" || value == null || isSymbol(value)) {
|
352 | return true;
|
353 | }
|
354 | return reIsPlainProp.test(value) || !reIsDeepProp.test(value) || object != null && value in Object(object);
|
355 | }
|
356 | var MAX_MEMOIZE_SIZE = 500;
|
357 | function memoizeCapped(func) {
|
358 | var result = memoize(func, function(key) {
|
359 | if (cache.size === MAX_MEMOIZE_SIZE) {
|
360 | cache.clear();
|
361 | }
|
362 | return key;
|
363 | });
|
364 | var cache = result.cache;
|
365 | return result;
|
366 | }
|
367 | var rePropName = /[^.[\]]+|\[(?:(-?\d+(?:\.\d+)?)|(["'])((?:(?!\2)[^\\]|\\.)*?)\2)\]|(?=(?:\.|\[\])(?:\.|\[\]|$))/g;
|
368 | var reEscapeChar = /\\(\\)?/g;
|
369 | var stringToPath = memoizeCapped(function(string) {
|
370 | var result = [];
|
371 | if (string.charCodeAt(0) === 46) {
|
372 | result.push("");
|
373 | }
|
374 | string.replace(rePropName, function(match, number, quote, subString) {
|
375 | result.push(quote ? subString.replace(reEscapeChar, "$1") : number || match);
|
376 | });
|
377 | return result;
|
378 | });
|
379 | const stringToPath$1 = stringToPath;
|
380 | function toString(value) {
|
381 | return value == null ? "" : baseToString(value);
|
382 | }
|
383 | function castPath(value, object) {
|
384 | if (isArray(value)) {
|
385 | return value;
|
386 | }
|
387 | return isKey(value, object) ? [value] : stringToPath$1(toString(value));
|
388 | }
|
389 | var INFINITY$1 = 1 / 0;
|
390 | function toKey(value) {
|
391 | if (typeof value == "string" || isSymbol(value)) {
|
392 | return value;
|
393 | }
|
394 | var result = value + "";
|
395 | return result == "0" && 1 / value == -INFINITY$1 ? "-0" : result;
|
396 | }
|
397 | function baseGet(object, path) {
|
398 | path = castPath(path, object);
|
399 | var index = 0, length = path.length;
|
400 | while (object != null && index < length) {
|
401 | object = object[toKey(path[index++])];
|
402 | }
|
403 | return index && index == length ? object : void 0;
|
404 | }
|
405 | function get(object, path, defaultValue) {
|
406 | var result = object == null ? void 0 : baseGet(object, path);
|
407 | return result === void 0 ? defaultValue : result;
|
408 | }
|
409 | function arrayPush(array, values2) {
|
410 | var index = -1, length = values2.length, offset = array.length;
|
411 | while (++index < length) {
|
412 | array[offset + index] = values2[index];
|
413 | }
|
414 | return array;
|
415 | }
|
416 | var spreadableSymbol = Symbol$1 ? Symbol$1.isConcatSpreadable : void 0;
|
417 | function isFlattenable(value) {
|
418 | return isArray(value) || isArguments(value) || !!(spreadableSymbol && value && value[spreadableSymbol]);
|
419 | }
|
420 | function baseFlatten(array, depth, predicate, isStrict, result) {
|
421 | var index = -1, length = array.length;
|
422 | predicate || (predicate = isFlattenable);
|
423 | result || (result = []);
|
424 | while (++index < length) {
|
425 | var value = array[index];
|
426 | if (depth > 0 && predicate(value)) {
|
427 | if (depth > 1) {
|
428 | baseFlatten(value, depth - 1, predicate, isStrict, result);
|
429 | } else {
|
430 | arrayPush(result, value);
|
431 | }
|
432 | } else if (!isStrict) {
|
433 | result[result.length] = value;
|
434 | }
|
435 | }
|
436 | return result;
|
437 | }
|
438 | function flatten(array) {
|
439 | var length = array == null ? 0 : array.length;
|
440 | return length ? baseFlatten(array, 1) : [];
|
441 | }
|
442 | function flatRest(func) {
|
443 | return setToString$1(overRest(func, void 0, flatten), func + "");
|
444 | }
|
445 | var getPrototype = overArg(Object.getPrototypeOf, Object);
|
446 | const getPrototype$1 = getPrototype;
|
447 | var objectTag$2 = "[object Object]";
|
448 | var funcProto = Function.prototype, objectProto$6 = Object.prototype;
|
449 | var funcToString = funcProto.toString;
|
450 | var hasOwnProperty$5 = objectProto$6.hasOwnProperty;
|
451 | var objectCtorString = funcToString.call(Object);
|
452 | function isPlainObject(value) {
|
453 | if (!isObjectLike(value) || baseGetTag(value) != objectTag$2) {
|
454 | return false;
|
455 | }
|
456 | var proto = getPrototype$1(value);
|
457 | if (proto === null) {
|
458 | return true;
|
459 | }
|
460 | var Ctor = hasOwnProperty$5.call(proto, "constructor") && proto.constructor;
|
461 | return typeof Ctor == "function" && Ctor instanceof Ctor && funcToString.call(Ctor) == objectCtorString;
|
462 | }
|
463 | function arrayReduce(array, iteratee, accumulator, initAccum) {
|
464 | var index = -1, length = array == null ? 0 : array.length;
|
465 | if (initAccum && length) {
|
466 | accumulator = array[++index];
|
467 | }
|
468 | while (++index < length) {
|
469 | accumulator = iteratee(accumulator, array[index], index, array);
|
470 | }
|
471 | return accumulator;
|
472 | }
|
473 | function stackClear() {
|
474 | this.__data__ = new ListCache();
|
475 | this.size = 0;
|
476 | }
|
477 | function stackDelete(key) {
|
478 | var data = this.__data__, result = data["delete"](key);
|
479 | this.size = data.size;
|
480 | return result;
|
481 | }
|
482 | function stackGet(key) {
|
483 | return this.__data__.get(key);
|
484 | }
|
485 | function stackHas(key) {
|
486 | return this.__data__.has(key);
|
487 | }
|
488 | var LARGE_ARRAY_SIZE$1 = 200;
|
489 | function stackSet(key, value) {
|
490 | var data = this.__data__;
|
491 | if (data instanceof ListCache) {
|
492 | var pairs = data.__data__;
|
493 | if (!Map || pairs.length < LARGE_ARRAY_SIZE$1 - 1) {
|
494 | pairs.push([key, value]);
|
495 | this.size = ++data.size;
|
496 | return this;
|
497 | }
|
498 | data = this.__data__ = new MapCache(pairs);
|
499 | }
|
500 | data.set(key, value);
|
501 | this.size = data.size;
|
502 | return this;
|
503 | }
|
504 | function Stack(entries) {
|
505 | var data = this.__data__ = new ListCache(entries);
|
506 | this.size = data.size;
|
507 | }
|
508 | Stack.prototype.clear = stackClear;
|
509 | Stack.prototype["delete"] = stackDelete;
|
510 | Stack.prototype.get = stackGet;
|
511 | Stack.prototype.has = stackHas;
|
512 | Stack.prototype.set = stackSet;
|
513 | function baseAssign(object, source) {
|
514 | return object && copyObject(source, keys(source), object);
|
515 | }
|
516 | function baseAssignIn(object, source) {
|
517 | return object && copyObject(source, keysIn(source), object);
|
518 | }
|
519 | var freeExports = typeof exports == "object" && exports && !exports.nodeType && exports;
|
520 | var freeModule = freeExports && typeof module == "object" && module && !module.nodeType && module;
|
521 | var moduleExports = freeModule && freeModule.exports === freeExports;
|
522 | var Buffer = moduleExports ? root.Buffer : void 0, allocUnsafe = Buffer ? Buffer.allocUnsafe : void 0;
|
523 | function cloneBuffer(buffer, isDeep) {
|
524 | if (isDeep) {
|
525 | return buffer.slice();
|
526 | }
|
527 | var length = buffer.length, result = allocUnsafe ? allocUnsafe(length) : new buffer.constructor(length);
|
528 | buffer.copy(result);
|
529 | return result;
|
530 | }
|
531 | function arrayFilter(array, predicate) {
|
532 | var index = -1, length = array == null ? 0 : array.length, resIndex = 0, result = [];
|
533 | while (++index < length) {
|
534 | var value = array[index];
|
535 | if (predicate(value, index, array)) {
|
536 | result[resIndex++] = value;
|
537 | }
|
538 | }
|
539 | return result;
|
540 | }
|
541 | function stubArray() {
|
542 | return [];
|
543 | }
|
544 | var objectProto$5 = Object.prototype;
|
545 | var propertyIsEnumerable = objectProto$5.propertyIsEnumerable;
|
546 | var nativeGetSymbols$1 = Object.getOwnPropertySymbols;
|
547 | var getSymbols = !nativeGetSymbols$1 ? stubArray : function(object) {
|
548 | if (object == null) {
|
549 | return [];
|
550 | }
|
551 | object = Object(object);
|
552 | return arrayFilter(nativeGetSymbols$1(object), function(symbol) {
|
553 | return propertyIsEnumerable.call(object, symbol);
|
554 | });
|
555 | };
|
556 | const getSymbols$1 = getSymbols;
|
557 | function copySymbols(source, object) {
|
558 | return copyObject(source, getSymbols$1(source), object);
|
559 | }
|
560 | var nativeGetSymbols = Object.getOwnPropertySymbols;
|
561 | var getSymbolsIn = !nativeGetSymbols ? stubArray : function(object) {
|
562 | var result = [];
|
563 | while (object) {
|
564 | arrayPush(result, getSymbols$1(object));
|
565 | object = getPrototype$1(object);
|
566 | }
|
567 | return result;
|
568 | };
|
569 | const getSymbolsIn$1 = getSymbolsIn;
|
570 | function copySymbolsIn(source, object) {
|
571 | return copyObject(source, getSymbolsIn$1(source), object);
|
572 | }
|
573 | function baseGetAllKeys(object, keysFunc, symbolsFunc) {
|
574 | var result = keysFunc(object);
|
575 | return isArray(object) ? result : arrayPush(result, symbolsFunc(object));
|
576 | }
|
577 | function getAllKeys(object) {
|
578 | return baseGetAllKeys(object, keys, getSymbols$1);
|
579 | }
|
580 | function getAllKeysIn(object) {
|
581 | return baseGetAllKeys(object, keysIn, getSymbolsIn$1);
|
582 | }
|
583 | var objectProto$4 = Object.prototype;
|
584 | var hasOwnProperty$4 = objectProto$4.hasOwnProperty;
|
585 | function initCloneArray(array) {
|
586 | var length = array.length, result = new array.constructor(length);
|
587 | if (length && typeof array[0] == "string" && hasOwnProperty$4.call(array, "index")) {
|
588 | result.index = array.index;
|
589 | result.input = array.input;
|
590 | }
|
591 | return result;
|
592 | }
|
593 | var Uint8Array = root.Uint8Array;
|
594 | const Uint8Array$1 = Uint8Array;
|
595 | function cloneArrayBuffer(arrayBuffer) {
|
596 | var result = new arrayBuffer.constructor(arrayBuffer.byteLength);
|
597 | new Uint8Array$1(result).set(new Uint8Array$1(arrayBuffer));
|
598 | return result;
|
599 | }
|
600 | function cloneDataView(dataView, isDeep) {
|
601 | var buffer = isDeep ? cloneArrayBuffer(dataView.buffer) : dataView.buffer;
|
602 | return new dataView.constructor(buffer, dataView.byteOffset, dataView.byteLength);
|
603 | }
|
604 | var reFlags = /\w*$/;
|
605 | function cloneRegExp(regexp) {
|
606 | var result = new regexp.constructor(regexp.source, reFlags.exec(regexp));
|
607 | result.lastIndex = regexp.lastIndex;
|
608 | return result;
|
609 | }
|
610 | var symbolProto$1 = Symbol$1 ? Symbol$1.prototype : void 0, symbolValueOf$1 = symbolProto$1 ? symbolProto$1.valueOf : void 0;
|
611 | function cloneSymbol(symbol) {
|
612 | return symbolValueOf$1 ? Object(symbolValueOf$1.call(symbol)) : {};
|
613 | }
|
614 | function cloneTypedArray(typedArray, isDeep) {
|
615 | var buffer = isDeep ? cloneArrayBuffer(typedArray.buffer) : typedArray.buffer;
|
616 | return new typedArray.constructor(buffer, typedArray.byteOffset, typedArray.length);
|
617 | }
|
618 | var boolTag$2 = "[object Boolean]", dateTag$2 = "[object Date]", mapTag$3 = "[object Map]", numberTag$2 = "[object Number]", regexpTag$2 = "[object RegExp]", setTag$3 = "[object Set]", stringTag$2 = "[object String]", symbolTag$2 = "[object Symbol]";
|
619 | var arrayBufferTag$2 = "[object ArrayBuffer]", dataViewTag$2 = "[object DataView]", float32Tag$1 = "[object Float32Array]", float64Tag$1 = "[object Float64Array]", int8Tag$1 = "[object Int8Array]", int16Tag$1 = "[object Int16Array]", int32Tag$1 = "[object Int32Array]", uint8Tag$1 = "[object Uint8Array]", uint8ClampedTag$1 = "[object Uint8ClampedArray]", uint16Tag$1 = "[object Uint16Array]", uint32Tag$1 = "[object Uint32Array]";
|
620 | function initCloneByTag(object, tag, isDeep) {
|
621 | var Ctor = object.constructor;
|
622 | switch (tag) {
|
623 | case arrayBufferTag$2:
|
624 | return cloneArrayBuffer(object);
|
625 | case boolTag$2:
|
626 | case dateTag$2:
|
627 | return new Ctor(+object);
|
628 | case dataViewTag$2:
|
629 | return cloneDataView(object, isDeep);
|
630 | case float32Tag$1:
|
631 | case float64Tag$1:
|
632 | case int8Tag$1:
|
633 | case int16Tag$1:
|
634 | case int32Tag$1:
|
635 | case uint8Tag$1:
|
636 | case uint8ClampedTag$1:
|
637 | case uint16Tag$1:
|
638 | case uint32Tag$1:
|
639 | return cloneTypedArray(object, isDeep);
|
640 | case mapTag$3:
|
641 | return new Ctor();
|
642 | case numberTag$2:
|
643 | case stringTag$2:
|
644 | return new Ctor(object);
|
645 | case regexpTag$2:
|
646 | return cloneRegExp(object);
|
647 | case setTag$3:
|
648 | return new Ctor();
|
649 | case symbolTag$2:
|
650 | return cloneSymbol(object);
|
651 | }
|
652 | }
|
653 | function initCloneObject(object) {
|
654 | return typeof object.constructor == "function" && !isPrototype(object) ? baseCreate$1(getPrototype$1(object)) : {};
|
655 | }
|
656 | var mapTag$2 = "[object Map]";
|
657 | function baseIsMap(value) {
|
658 | return isObjectLike(value) && getTag(value) == mapTag$2;
|
659 | }
|
660 | var nodeIsMap = nodeUtil && nodeUtil.isMap;
|
661 | var isMap = nodeIsMap ? baseUnary(nodeIsMap) : baseIsMap;
|
662 | const isMap$1 = isMap;
|
663 | var setTag$2 = "[object Set]";
|
664 | function baseIsSet(value) {
|
665 | return isObjectLike(value) && getTag(value) == setTag$2;
|
666 | }
|
667 | var nodeIsSet = nodeUtil && nodeUtil.isSet;
|
668 | var isSet = nodeIsSet ? baseUnary(nodeIsSet) : baseIsSet;
|
669 | const isSet$1 = isSet;
|
670 | var CLONE_DEEP_FLAG$1 = 1, CLONE_FLAT_FLAG = 2, CLONE_SYMBOLS_FLAG$1 = 4;
|
671 | var argsTag$1 = "[object Arguments]", arrayTag$1 = "[object Array]", boolTag$1 = "[object Boolean]", dateTag$1 = "[object Date]", errorTag$1 = "[object Error]", funcTag = "[object Function]", genTag = "[object GeneratorFunction]", mapTag$1 = "[object Map]", numberTag$1 = "[object Number]", objectTag$1 = "[object Object]", regexpTag$1 = "[object RegExp]", setTag$1 = "[object Set]", stringTag$1 = "[object String]", symbolTag$1 = "[object Symbol]", weakMapTag = "[object WeakMap]";
|
672 | var arrayBufferTag$1 = "[object ArrayBuffer]", dataViewTag$1 = "[object DataView]", float32Tag = "[object Float32Array]", float64Tag = "[object Float64Array]", int8Tag = "[object Int8Array]", int16Tag = "[object Int16Array]", int32Tag = "[object Int32Array]", uint8Tag = "[object Uint8Array]", uint8ClampedTag = "[object Uint8ClampedArray]", uint16Tag = "[object Uint16Array]", uint32Tag = "[object Uint32Array]";
|
673 | var cloneableTags = {};
|
674 | cloneableTags[argsTag$1] = cloneableTags[arrayTag$1] = cloneableTags[arrayBufferTag$1] = cloneableTags[dataViewTag$1] = cloneableTags[boolTag$1] = cloneableTags[dateTag$1] = cloneableTags[float32Tag] = cloneableTags[float64Tag] = cloneableTags[int8Tag] = cloneableTags[int16Tag] = cloneableTags[int32Tag] = cloneableTags[mapTag$1] = cloneableTags[numberTag$1] = cloneableTags[objectTag$1] = cloneableTags[regexpTag$1] = cloneableTags[setTag$1] = cloneableTags[stringTag$1] = cloneableTags[symbolTag$1] = cloneableTags[uint8Tag] = cloneableTags[uint8ClampedTag] = cloneableTags[uint16Tag] = cloneableTags[uint32Tag] = true;
|
675 | cloneableTags[errorTag$1] = cloneableTags[funcTag] = cloneableTags[weakMapTag] = false;
|
676 | function baseClone(value, bitmask, customizer, key, object, stack) {
|
677 | var result, isDeep = bitmask & CLONE_DEEP_FLAG$1, isFlat = bitmask & CLONE_FLAT_FLAG, isFull = bitmask & CLONE_SYMBOLS_FLAG$1;
|
678 | if (customizer) {
|
679 | result = object ? customizer(value, key, object, stack) : customizer(value);
|
680 | }
|
681 | if (result !== void 0) {
|
682 | return result;
|
683 | }
|
684 | if (!isObject(value)) {
|
685 | return value;
|
686 | }
|
687 | var isArr = isArray(value);
|
688 | if (isArr) {
|
689 | result = initCloneArray(value);
|
690 | if (!isDeep) {
|
691 | return copyArray(value, result);
|
692 | }
|
693 | } else {
|
694 | var tag = getTag(value), isFunc = tag == funcTag || tag == genTag;
|
695 | if (isBuffer(value)) {
|
696 | return cloneBuffer(value, isDeep);
|
697 | }
|
698 | if (tag == objectTag$1 || tag == argsTag$1 || isFunc && !object) {
|
699 | result = isFlat || isFunc ? {} : initCloneObject(value);
|
700 | if (!isDeep) {
|
701 | return isFlat ? copySymbolsIn(value, baseAssignIn(result, value)) : copySymbols(value, baseAssign(result, value));
|
702 | }
|
703 | } else {
|
704 | if (!cloneableTags[tag]) {
|
705 | return object ? value : {};
|
706 | }
|
707 | result = initCloneByTag(value, tag, isDeep);
|
708 | }
|
709 | }
|
710 | stack || (stack = new Stack());
|
711 | var stacked = stack.get(value);
|
712 | if (stacked) {
|
713 | return stacked;
|
714 | }
|
715 | stack.set(value, result);
|
716 | if (isSet$1(value)) {
|
717 | value.forEach(function(subValue) {
|
718 | result.add(baseClone(subValue, bitmask, customizer, subValue, value, stack));
|
719 | });
|
720 | } else if (isMap$1(value)) {
|
721 | value.forEach(function(subValue, key2) {
|
722 | result.set(key2, baseClone(subValue, bitmask, customizer, key2, value, stack));
|
723 | });
|
724 | }
|
725 | var keysFunc = isFull ? isFlat ? getAllKeysIn : getAllKeys : isFlat ? keysIn : keys;
|
726 | var props = isArr ? void 0 : keysFunc(value);
|
727 | arrayEach(props || value, function(subValue, key2) {
|
728 | if (props) {
|
729 | key2 = subValue;
|
730 | subValue = value[key2];
|
731 | }
|
732 | assignValue(result, key2, baseClone(subValue, bitmask, customizer, key2, value, stack));
|
733 | });
|
734 | return result;
|
735 | }
|
736 | var CLONE_DEEP_FLAG = 1, CLONE_SYMBOLS_FLAG = 4;
|
737 | function cloneDeep(value) {
|
738 | return baseClone(value, CLONE_DEEP_FLAG | CLONE_SYMBOLS_FLAG);
|
739 | }
|
740 | var HASH_UNDEFINED = "__lodash_hash_undefined__";
|
741 | function setCacheAdd(value) {
|
742 | this.__data__.set(value, HASH_UNDEFINED);
|
743 | return this;
|
744 | }
|
745 | function setCacheHas(value) {
|
746 | return this.__data__.has(value);
|
747 | }
|
748 | function SetCache(values2) {
|
749 | var index = -1, length = values2 == null ? 0 : values2.length;
|
750 | this.__data__ = new MapCache();
|
751 | while (++index < length) {
|
752 | this.add(values2[index]);
|
753 | }
|
754 | }
|
755 | SetCache.prototype.add = SetCache.prototype.push = setCacheAdd;
|
756 | SetCache.prototype.has = setCacheHas;
|
757 | function arraySome(array, predicate) {
|
758 | var index = -1, length = array == null ? 0 : array.length;
|
759 | while (++index < length) {
|
760 | if (predicate(array[index], index, array)) {
|
761 | return true;
|
762 | }
|
763 | }
|
764 | return false;
|
765 | }
|
766 | function cacheHas(cache, key) {
|
767 | return cache.has(key);
|
768 | }
|
769 | var COMPARE_PARTIAL_FLAG$5 = 1, COMPARE_UNORDERED_FLAG$3 = 2;
|
770 | function equalArrays(array, other, bitmask, customizer, equalFunc, stack) {
|
771 | var isPartial = bitmask & COMPARE_PARTIAL_FLAG$5, arrLength = array.length, othLength = other.length;
|
772 | if (arrLength != othLength && !(isPartial && othLength > arrLength)) {
|
773 | return false;
|
774 | }
|
775 | var arrStacked = stack.get(array);
|
776 | var othStacked = stack.get(other);
|
777 | if (arrStacked && othStacked) {
|
778 | return arrStacked == other && othStacked == array;
|
779 | }
|
780 | var index = -1, result = true, seen = bitmask & COMPARE_UNORDERED_FLAG$3 ? new SetCache() : void 0;
|
781 | stack.set(array, other);
|
782 | stack.set(other, array);
|
783 | while (++index < arrLength) {
|
784 | var arrValue = array[index], othValue = other[index];
|
785 | if (customizer) {
|
786 | var compared = isPartial ? customizer(othValue, arrValue, index, other, array, stack) : customizer(arrValue, othValue, index, array, other, stack);
|
787 | }
|
788 | if (compared !== void 0) {
|
789 | if (compared) {
|
790 | continue;
|
791 | }
|
792 | result = false;
|
793 | break;
|
794 | }
|
795 | if (seen) {
|
796 | if (!arraySome(other, function(othValue2, othIndex) {
|
797 | if (!cacheHas(seen, othIndex) && (arrValue === othValue2 || equalFunc(arrValue, othValue2, bitmask, customizer, stack))) {
|
798 | return seen.push(othIndex);
|
799 | }
|
800 | })) {
|
801 | result = false;
|
802 | break;
|
803 | }
|
804 | } else if (!(arrValue === othValue || equalFunc(arrValue, othValue, bitmask, customizer, stack))) {
|
805 | result = false;
|
806 | break;
|
807 | }
|
808 | }
|
809 | stack["delete"](array);
|
810 | stack["delete"](other);
|
811 | return result;
|
812 | }
|
813 | function mapToArray(map2) {
|
814 | var index = -1, result = Array(map2.size);
|
815 | map2.forEach(function(value, key) {
|
816 | result[++index] = [key, value];
|
817 | });
|
818 | return result;
|
819 | }
|
820 | function setToArray(set) {
|
821 | var index = -1, result = Array(set.size);
|
822 | set.forEach(function(value) {
|
823 | result[++index] = value;
|
824 | });
|
825 | return result;
|
826 | }
|
827 | var COMPARE_PARTIAL_FLAG$4 = 1, COMPARE_UNORDERED_FLAG$2 = 2;
|
828 | var boolTag = "[object Boolean]", dateTag = "[object Date]", errorTag = "[object Error]", mapTag = "[object Map]", numberTag = "[object Number]", regexpTag = "[object RegExp]", setTag = "[object Set]", stringTag = "[object String]", symbolTag = "[object Symbol]";
|
829 | var arrayBufferTag = "[object ArrayBuffer]", dataViewTag = "[object DataView]";
|
830 | var symbolProto = Symbol$1 ? Symbol$1.prototype : void 0, symbolValueOf = symbolProto ? symbolProto.valueOf : void 0;
|
831 | function equalByTag(object, other, tag, bitmask, customizer, equalFunc, stack) {
|
832 | switch (tag) {
|
833 | case dataViewTag:
|
834 | if (object.byteLength != other.byteLength || object.byteOffset != other.byteOffset) {
|
835 | return false;
|
836 | }
|
837 | object = object.buffer;
|
838 | other = other.buffer;
|
839 | case arrayBufferTag:
|
840 | if (object.byteLength != other.byteLength || !equalFunc(new Uint8Array$1(object), new Uint8Array$1(other))) {
|
841 | return false;
|
842 | }
|
843 | return true;
|
844 | case boolTag:
|
845 | case dateTag:
|
846 | case numberTag:
|
847 | return eq(+object, +other);
|
848 | case errorTag:
|
849 | return object.name == other.name && object.message == other.message;
|
850 | case regexpTag:
|
851 | case stringTag:
|
852 | return object == other + "";
|
853 | case mapTag:
|
854 | var convert = mapToArray;
|
855 | case setTag:
|
856 | var isPartial = bitmask & COMPARE_PARTIAL_FLAG$4;
|
857 | convert || (convert = setToArray);
|
858 | if (object.size != other.size && !isPartial) {
|
859 | return false;
|
860 | }
|
861 | var stacked = stack.get(object);
|
862 | if (stacked) {
|
863 | return stacked == other;
|
864 | }
|
865 | bitmask |= COMPARE_UNORDERED_FLAG$2;
|
866 | stack.set(object, other);
|
867 | var result = equalArrays(convert(object), convert(other), bitmask, customizer, equalFunc, stack);
|
868 | stack["delete"](object);
|
869 | return result;
|
870 | case symbolTag:
|
871 | if (symbolValueOf) {
|
872 | return symbolValueOf.call(object) == symbolValueOf.call(other);
|
873 | }
|
874 | }
|
875 | return false;
|
876 | }
|
877 | var COMPARE_PARTIAL_FLAG$3 = 1;
|
878 | var objectProto$3 = Object.prototype;
|
879 | var hasOwnProperty$3 = objectProto$3.hasOwnProperty;
|
880 | function equalObjects(object, other, bitmask, customizer, equalFunc, stack) {
|
881 | var isPartial = bitmask & COMPARE_PARTIAL_FLAG$3, objProps = getAllKeys(object), objLength = objProps.length, othProps = getAllKeys(other), othLength = othProps.length;
|
882 | if (objLength != othLength && !isPartial) {
|
883 | return false;
|
884 | }
|
885 | var index = objLength;
|
886 | while (index--) {
|
887 | var key = objProps[index];
|
888 | if (!(isPartial ? key in other : hasOwnProperty$3.call(other, key))) {
|
889 | return false;
|
890 | }
|
891 | }
|
892 | var objStacked = stack.get(object);
|
893 | var othStacked = stack.get(other);
|
894 | if (objStacked && othStacked) {
|
895 | return objStacked == other && othStacked == object;
|
896 | }
|
897 | var result = true;
|
898 | stack.set(object, other);
|
899 | stack.set(other, object);
|
900 | var skipCtor = isPartial;
|
901 | while (++index < objLength) {
|
902 | key = objProps[index];
|
903 | var objValue = object[key], othValue = other[key];
|
904 | if (customizer) {
|
905 | var compared = isPartial ? customizer(othValue, objValue, key, other, object, stack) : customizer(objValue, othValue, key, object, other, stack);
|
906 | }
|
907 | if (!(compared === void 0 ? objValue === othValue || equalFunc(objValue, othValue, bitmask, customizer, stack) : compared)) {
|
908 | result = false;
|
909 | break;
|
910 | }
|
911 | skipCtor || (skipCtor = key == "constructor");
|
912 | }
|
913 | if (result && !skipCtor) {
|
914 | var objCtor = object.constructor, othCtor = other.constructor;
|
915 | if (objCtor != othCtor && ("constructor" in object && "constructor" in other) && !(typeof objCtor == "function" && objCtor instanceof objCtor && typeof othCtor == "function" && othCtor instanceof othCtor)) {
|
916 | result = false;
|
917 | }
|
918 | }
|
919 | stack["delete"](object);
|
920 | stack["delete"](other);
|
921 | return result;
|
922 | }
|
923 | var COMPARE_PARTIAL_FLAG$2 = 1;
|
924 | var argsTag = "[object Arguments]", arrayTag = "[object Array]", objectTag = "[object Object]";
|
925 | var objectProto$2 = Object.prototype;
|
926 | var hasOwnProperty$2 = objectProto$2.hasOwnProperty;
|
927 | function baseIsEqualDeep(object, other, bitmask, customizer, equalFunc, stack) {
|
928 | var objIsArr = isArray(object), othIsArr = isArray(other), objTag = objIsArr ? arrayTag : getTag(object), othTag = othIsArr ? arrayTag : getTag(other);
|
929 | objTag = objTag == argsTag ? objectTag : objTag;
|
930 | othTag = othTag == argsTag ? objectTag : othTag;
|
931 | var objIsObj = objTag == objectTag, othIsObj = othTag == objectTag, isSameTag = objTag == othTag;
|
932 | if (isSameTag && isBuffer(object)) {
|
933 | if (!isBuffer(other)) {
|
934 | return false;
|
935 | }
|
936 | objIsArr = true;
|
937 | objIsObj = false;
|
938 | }
|
939 | if (isSameTag && !objIsObj) {
|
940 | stack || (stack = new Stack());
|
941 | return objIsArr || isTypedArray(object) ? equalArrays(object, other, bitmask, customizer, equalFunc, stack) : equalByTag(object, other, objTag, bitmask, customizer, equalFunc, stack);
|
942 | }
|
943 | if (!(bitmask & COMPARE_PARTIAL_FLAG$2)) {
|
944 | var objIsWrapped = objIsObj && hasOwnProperty$2.call(object, "__wrapped__"), othIsWrapped = othIsObj && hasOwnProperty$2.call(other, "__wrapped__");
|
945 | if (objIsWrapped || othIsWrapped) {
|
946 | var objUnwrapped = objIsWrapped ? object.value() : object, othUnwrapped = othIsWrapped ? other.value() : other;
|
947 | stack || (stack = new Stack());
|
948 | return equalFunc(objUnwrapped, othUnwrapped, bitmask, customizer, stack);
|
949 | }
|
950 | }
|
951 | if (!isSameTag) {
|
952 | return false;
|
953 | }
|
954 | stack || (stack = new Stack());
|
955 | return equalObjects(object, other, bitmask, customizer, equalFunc, stack);
|
956 | }
|
957 | function baseIsEqual(value, other, bitmask, customizer, stack) {
|
958 | if (value === other) {
|
959 | return true;
|
960 | }
|
961 | if (value == null || other == null || !isObjectLike(value) && !isObjectLike(other)) {
|
962 | return value !== value && other !== other;
|
963 | }
|
964 | return baseIsEqualDeep(value, other, bitmask, customizer, baseIsEqual, stack);
|
965 | }
|
966 | var COMPARE_PARTIAL_FLAG$1 = 1, COMPARE_UNORDERED_FLAG$1 = 2;
|
967 | function baseIsMatch(object, source, matchData, customizer) {
|
968 | var index = matchData.length, length = index, noCustomizer = !customizer;
|
969 | if (object == null) {
|
970 | return !length;
|
971 | }
|
972 | object = Object(object);
|
973 | while (index--) {
|
974 | var data = matchData[index];
|
975 | if (noCustomizer && data[2] ? data[1] !== object[data[0]] : !(data[0] in object)) {
|
976 | return false;
|
977 | }
|
978 | }
|
979 | while (++index < length) {
|
980 | data = matchData[index];
|
981 | var key = data[0], objValue = object[key], srcValue = data[1];
|
982 | if (noCustomizer && data[2]) {
|
983 | if (objValue === void 0 && !(key in object)) {
|
984 | return false;
|
985 | }
|
986 | } else {
|
987 | var stack = new Stack();
|
988 | if (customizer) {
|
989 | var result = customizer(objValue, srcValue, key, object, source, stack);
|
990 | }
|
991 | if (!(result === void 0 ? baseIsEqual(srcValue, objValue, COMPARE_PARTIAL_FLAG$1 | COMPARE_UNORDERED_FLAG$1, customizer, stack) : result)) {
|
992 | return false;
|
993 | }
|
994 | }
|
995 | }
|
996 | return true;
|
997 | }
|
998 | function isStrictComparable(value) {
|
999 | return value === value && !isObject(value);
|
1000 | }
|
1001 | function getMatchData(object) {
|
1002 | var result = keys(object), length = result.length;
|
1003 | while (length--) {
|
1004 | var key = result[length], value = object[key];
|
1005 | result[length] = [key, value, isStrictComparable(value)];
|
1006 | }
|
1007 | return result;
|
1008 | }
|
1009 | function matchesStrictComparable(key, srcValue) {
|
1010 | return function(object) {
|
1011 | if (object == null) {
|
1012 | return false;
|
1013 | }
|
1014 | return object[key] === srcValue && (srcValue !== void 0 || key in Object(object));
|
1015 | };
|
1016 | }
|
1017 | function baseMatches(source) {
|
1018 | var matchData = getMatchData(source);
|
1019 | if (matchData.length == 1 && matchData[0][2]) {
|
1020 | return matchesStrictComparable(matchData[0][0], matchData[0][1]);
|
1021 | }
|
1022 | return function(object) {
|
1023 | return object === source || baseIsMatch(object, source, matchData);
|
1024 | };
|
1025 | }
|
1026 | function baseHasIn(object, key) {
|
1027 | return object != null && key in Object(object);
|
1028 | }
|
1029 | function hasPath(object, path, hasFunc) {
|
1030 | path = castPath(path, object);
|
1031 | var index = -1, length = path.length, result = false;
|
1032 | while (++index < length) {
|
1033 | var key = toKey(path[index]);
|
1034 | if (!(result = object != null && hasFunc(object, key))) {
|
1035 | break;
|
1036 | }
|
1037 | object = object[key];
|
1038 | }
|
1039 | if (result || ++index != length) {
|
1040 | return result;
|
1041 | }
|
1042 | length = object == null ? 0 : object.length;
|
1043 | return !!length && isLength(length) && isIndex(key, length) && (isArray(object) || isArguments(object));
|
1044 | }
|
1045 | function hasIn(object, path) {
|
1046 | return object != null && hasPath(object, path, baseHasIn);
|
1047 | }
|
1048 | var COMPARE_PARTIAL_FLAG = 1, COMPARE_UNORDERED_FLAG = 2;
|
1049 | function baseMatchesProperty(path, srcValue) {
|
1050 | if (isKey(path) && isStrictComparable(srcValue)) {
|
1051 | return matchesStrictComparable(toKey(path), srcValue);
|
1052 | }
|
1053 | return function(object) {
|
1054 | var objValue = get(object, path);
|
1055 | return objValue === void 0 && objValue === srcValue ? hasIn(object, path) : baseIsEqual(srcValue, objValue, COMPARE_PARTIAL_FLAG | COMPARE_UNORDERED_FLAG);
|
1056 | };
|
1057 | }
|
1058 | function baseProperty(key) {
|
1059 | return function(object) {
|
1060 | return object == null ? void 0 : object[key];
|
1061 | };
|
1062 | }
|
1063 | function basePropertyDeep(path) {
|
1064 | return function(object) {
|
1065 | return baseGet(object, path);
|
1066 | };
|
1067 | }
|
1068 | function property(path) {
|
1069 | return isKey(path) ? baseProperty(toKey(path)) : basePropertyDeep(path);
|
1070 | }
|
1071 | function baseIteratee(value) {
|
1072 | if (typeof value == "function") {
|
1073 | return value;
|
1074 | }
|
1075 | if (value == null) {
|
1076 | return identity;
|
1077 | }
|
1078 | if (typeof value == "object") {
|
1079 | return isArray(value) ? baseMatchesProperty(value[0], value[1]) : baseMatches(value);
|
1080 | }
|
1081 | return property(value);
|
1082 | }
|
1083 | function createBaseFor(fromRight) {
|
1084 | return function(object, iteratee, keysFunc) {
|
1085 | var index = -1, iterable = Object(object), props = keysFunc(object), length = props.length;
|
1086 | while (length--) {
|
1087 | var key = props[fromRight ? length : ++index];
|
1088 | if (iteratee(iterable[key], key, iterable) === false) {
|
1089 | break;
|
1090 | }
|
1091 | }
|
1092 | return object;
|
1093 | };
|
1094 | }
|
1095 | var baseFor = createBaseFor();
|
1096 | const baseFor$1 = baseFor;
|
1097 | function baseForOwn(object, iteratee) {
|
1098 | return object && baseFor$1(object, iteratee, keys);
|
1099 | }
|
1100 | function createBaseEach(eachFunc, fromRight) {
|
1101 | return function(collection, iteratee) {
|
1102 | if (collection == null) {
|
1103 | return collection;
|
1104 | }
|
1105 | if (!isArrayLike(collection)) {
|
1106 | return eachFunc(collection, iteratee);
|
1107 | }
|
1108 | var length = collection.length, index = fromRight ? length : -1, iterable = Object(collection);
|
1109 | while (fromRight ? index-- : ++index < length) {
|
1110 | if (iteratee(iterable[index], index, iterable) === false) {
|
1111 | break;
|
1112 | }
|
1113 | }
|
1114 | return collection;
|
1115 | };
|
1116 | }
|
1117 | var baseEach = createBaseEach(baseForOwn);
|
1118 | const baseEach$1 = baseEach;
|
1119 | var now = function() {
|
1120 | return root.Date.now();
|
1121 | };
|
1122 | const now$1 = now;
|
1123 | var objectProto$1 = Object.prototype;
|
1124 | var hasOwnProperty$1 = objectProto$1.hasOwnProperty;
|
1125 | var defaults = baseRest(function(object, sources) {
|
1126 | object = Object(object);
|
1127 | var index = -1;
|
1128 | var length = sources.length;
|
1129 | var guard = length > 2 ? sources[2] : void 0;
|
1130 | if (guard && isIterateeCall(sources[0], sources[1], guard)) {
|
1131 | length = 1;
|
1132 | }
|
1133 | while (++index < length) {
|
1134 | var source = sources[index];
|
1135 | var props = keysIn(source);
|
1136 | var propsIndex = -1;
|
1137 | var propsLength = props.length;
|
1138 | while (++propsIndex < propsLength) {
|
1139 | var key = props[propsIndex];
|
1140 | var value = object[key];
|
1141 | if (value === void 0 || eq(value, objectProto$1[key]) && !hasOwnProperty$1.call(object, key)) {
|
1142 | object[key] = source[key];
|
1143 | }
|
1144 | }
|
1145 | }
|
1146 | return object;
|
1147 | });
|
1148 | const defaults$1 = defaults;
|
1149 | function assignMergeValue(object, key, value) {
|
1150 | if (value !== void 0 && !eq(object[key], value) || value === void 0 && !(key in object)) {
|
1151 | baseAssignValue(object, key, value);
|
1152 | }
|
1153 | }
|
1154 | function isArrayLikeObject(value) {
|
1155 | return isObjectLike(value) && isArrayLike(value);
|
1156 | }
|
1157 | function safeGet(object, key) {
|
1158 | if (key === "constructor" && typeof object[key] === "function") {
|
1159 | return;
|
1160 | }
|
1161 | if (key == "__proto__") {
|
1162 | return;
|
1163 | }
|
1164 | return object[key];
|
1165 | }
|
1166 | function toPlainObject(value) {
|
1167 | return copyObject(value, keysIn(value));
|
1168 | }
|
1169 | function baseMergeDeep(object, source, key, srcIndex, mergeFunc, customizer, stack) {
|
1170 | var objValue = safeGet(object, key), srcValue = safeGet(source, key), stacked = stack.get(srcValue);
|
1171 | if (stacked) {
|
1172 | assignMergeValue(object, key, stacked);
|
1173 | return;
|
1174 | }
|
1175 | var newValue = customizer ? customizer(objValue, srcValue, key + "", object, source, stack) : void 0;
|
1176 | var isCommon = newValue === void 0;
|
1177 | if (isCommon) {
|
1178 | var isArr = isArray(srcValue), isBuff = !isArr && isBuffer(srcValue), isTyped = !isArr && !isBuff && isTypedArray(srcValue);
|
1179 | newValue = srcValue;
|
1180 | if (isArr || isBuff || isTyped) {
|
1181 | if (isArray(objValue)) {
|
1182 | newValue = objValue;
|
1183 | } else if (isArrayLikeObject(objValue)) {
|
1184 | newValue = copyArray(objValue);
|
1185 | } else if (isBuff) {
|
1186 | isCommon = false;
|
1187 | newValue = cloneBuffer(srcValue, true);
|
1188 | } else if (isTyped) {
|
1189 | isCommon = false;
|
1190 | newValue = cloneTypedArray(srcValue, true);
|
1191 | } else {
|
1192 | newValue = [];
|
1193 | }
|
1194 | } else if (isPlainObject(srcValue) || isArguments(srcValue)) {
|
1195 | newValue = objValue;
|
1196 | if (isArguments(objValue)) {
|
1197 | newValue = toPlainObject(objValue);
|
1198 | } else if (!isObject(objValue) || isFunction(objValue)) {
|
1199 | newValue = initCloneObject(srcValue);
|
1200 | }
|
1201 | } else {
|
1202 | isCommon = false;
|
1203 | }
|
1204 | }
|
1205 | if (isCommon) {
|
1206 | stack.set(srcValue, newValue);
|
1207 | mergeFunc(newValue, srcValue, srcIndex, customizer, stack);
|
1208 | stack["delete"](srcValue);
|
1209 | }
|
1210 | assignMergeValue(object, key, newValue);
|
1211 | }
|
1212 | function baseMerge(object, source, srcIndex, customizer, stack) {
|
1213 | if (object === source) {
|
1214 | return;
|
1215 | }
|
1216 | baseFor$1(source, function(srcValue, key) {
|
1217 | stack || (stack = new Stack());
|
1218 | if (isObject(srcValue)) {
|
1219 | baseMergeDeep(object, source, key, srcIndex, baseMerge, customizer, stack);
|
1220 | } else {
|
1221 | var newValue = customizer ? customizer(safeGet(object, key), srcValue, key + "", object, source, stack) : void 0;
|
1222 | if (newValue === void 0) {
|
1223 | newValue = srcValue;
|
1224 | }
|
1225 | assignMergeValue(object, key, newValue);
|
1226 | }
|
1227 | }, keysIn);
|
1228 | }
|
1229 | function arrayIncludesWith(array, value, comparator) {
|
1230 | var index = -1, length = array == null ? 0 : array.length;
|
1231 | while (++index < length) {
|
1232 | if (comparator(value, array[index])) {
|
1233 | return true;
|
1234 | }
|
1235 | }
|
1236 | return false;
|
1237 | }
|
1238 | function last(array) {
|
1239 | var length = array == null ? 0 : array.length;
|
1240 | return length ? array[length - 1] : void 0;
|
1241 | }
|
1242 | function castFunction(value) {
|
1243 | return typeof value == "function" ? value : identity;
|
1244 | }
|
1245 | function forEach(collection, iteratee) {
|
1246 | var func = isArray(collection) ? arrayEach : baseEach$1;
|
1247 | return func(collection, castFunction(iteratee));
|
1248 | }
|
1249 | function baseFilter(collection, predicate) {
|
1250 | var result = [];
|
1251 | baseEach$1(collection, function(value, index, collection2) {
|
1252 | if (predicate(value, index, collection2)) {
|
1253 | result.push(value);
|
1254 | }
|
1255 | });
|
1256 | return result;
|
1257 | }
|
1258 | function filter(collection, predicate) {
|
1259 | var func = isArray(collection) ? arrayFilter : baseFilter;
|
1260 | return func(collection, baseIteratee(predicate));
|
1261 | }
|
1262 | function createFind(findIndexFunc) {
|
1263 | return function(collection, predicate, fromIndex) {
|
1264 | var iterable = Object(collection);
|
1265 | if (!isArrayLike(collection)) {
|
1266 | var iteratee = baseIteratee(predicate);
|
1267 | collection = keys(collection);
|
1268 | predicate = function(key) {
|
1269 | return iteratee(iterable[key], key, iterable);
|
1270 | };
|
1271 | }
|
1272 | var index = findIndexFunc(collection, predicate, fromIndex);
|
1273 | return index > -1 ? iterable[iteratee ? collection[index] : index] : void 0;
|
1274 | };
|
1275 | }
|
1276 | var nativeMax$1 = Math.max;
|
1277 | function findIndex(array, predicate, fromIndex) {
|
1278 | var length = array == null ? 0 : array.length;
|
1279 | if (!length) {
|
1280 | return -1;
|
1281 | }
|
1282 | var index = fromIndex == null ? 0 : toInteger(fromIndex);
|
1283 | if (index < 0) {
|
1284 | index = nativeMax$1(length + index, 0);
|
1285 | }
|
1286 | return baseFindIndex(array, baseIteratee(predicate), index);
|
1287 | }
|
1288 | var find = createFind(findIndex);
|
1289 | const find$1 = find;
|
1290 | function baseMap(collection, iteratee) {
|
1291 | var index = -1, result = isArrayLike(collection) ? Array(collection.length) : [];
|
1292 | baseEach$1(collection, function(value, key, collection2) {
|
1293 | result[++index] = iteratee(value, key, collection2);
|
1294 | });
|
1295 | return result;
|
1296 | }
|
1297 | function map(collection, iteratee) {
|
1298 | var func = isArray(collection) ? arrayMap : baseMap;
|
1299 | return func(collection, baseIteratee(iteratee));
|
1300 | }
|
1301 | function forIn(object, iteratee) {
|
1302 | return object == null ? object : baseFor$1(object, castFunction(iteratee), keysIn);
|
1303 | }
|
1304 | function forOwn(object, iteratee) {
|
1305 | return object && baseForOwn(object, castFunction(iteratee));
|
1306 | }
|
1307 | function baseGt(value, other) {
|
1308 | return value > other;
|
1309 | }
|
1310 | var objectProto = Object.prototype;
|
1311 | var hasOwnProperty = objectProto.hasOwnProperty;
|
1312 | function baseHas(object, key) {
|
1313 | return object != null && hasOwnProperty.call(object, key);
|
1314 | }
|
1315 | function has(object, path) {
|
1316 | return object != null && hasPath(object, path, baseHas);
|
1317 | }
|
1318 | function baseValues(object, props) {
|
1319 | return arrayMap(props, function(key) {
|
1320 | return object[key];
|
1321 | });
|
1322 | }
|
1323 | function values(object) {
|
1324 | return object == null ? [] : baseValues(object, keys(object));
|
1325 | }
|
1326 | function isUndefined(value) {
|
1327 | return value === void 0;
|
1328 | }
|
1329 | function baseLt(value, other) {
|
1330 | return value < other;
|
1331 | }
|
1332 | function mapValues(object, iteratee) {
|
1333 | var result = {};
|
1334 | iteratee = baseIteratee(iteratee);
|
1335 | baseForOwn(object, function(value, key, object2) {
|
1336 | baseAssignValue(result, key, iteratee(value, key, object2));
|
1337 | });
|
1338 | return result;
|
1339 | }
|
1340 | function baseExtremum(array, iteratee, comparator) {
|
1341 | var index = -1, length = array.length;
|
1342 | while (++index < length) {
|
1343 | var value = array[index], current = iteratee(value);
|
1344 | if (current != null && (computed === void 0 ? current === current && !isSymbol(current) : comparator(current, computed))) {
|
1345 | var computed = current, result = value;
|
1346 | }
|
1347 | }
|
1348 | return result;
|
1349 | }
|
1350 | function max(array) {
|
1351 | return array && array.length ? baseExtremum(array, identity, baseGt) : void 0;
|
1352 | }
|
1353 | var merge = createAssigner(function(object, source, srcIndex) {
|
1354 | baseMerge(object, source, srcIndex);
|
1355 | });
|
1356 | const merge$1 = merge;
|
1357 | function min(array) {
|
1358 | return array && array.length ? baseExtremum(array, identity, baseLt) : void 0;
|
1359 | }
|
1360 | function minBy(array, iteratee) {
|
1361 | return array && array.length ? baseExtremum(array, baseIteratee(iteratee), baseLt) : void 0;
|
1362 | }
|
1363 | function baseSet(object, path, value, customizer) {
|
1364 | if (!isObject(object)) {
|
1365 | return object;
|
1366 | }
|
1367 | path = castPath(path, object);
|
1368 | var index = -1, length = path.length, lastIndex = length - 1, nested = object;
|
1369 | while (nested != null && ++index < length) {
|
1370 | var key = toKey(path[index]), newValue = value;
|
1371 | if (key === "__proto__" || key === "constructor" || key === "prototype") {
|
1372 | return object;
|
1373 | }
|
1374 | if (index != lastIndex) {
|
1375 | var objValue = nested[key];
|
1376 | newValue = customizer ? customizer(objValue, key, nested) : void 0;
|
1377 | if (newValue === void 0) {
|
1378 | newValue = isObject(objValue) ? objValue : isIndex(path[index + 1]) ? [] : {};
|
1379 | }
|
1380 | }
|
1381 | assignValue(nested, key, newValue);
|
1382 | nested = nested[key];
|
1383 | }
|
1384 | return object;
|
1385 | }
|
1386 | function basePickBy(object, paths, predicate) {
|
1387 | var index = -1, length = paths.length, result = {};
|
1388 | while (++index < length) {
|
1389 | var path = paths[index], value = baseGet(object, path);
|
1390 | if (predicate(value, path)) {
|
1391 | baseSet(result, castPath(path, object), value);
|
1392 | }
|
1393 | }
|
1394 | return result;
|
1395 | }
|
1396 | function baseSortBy(array, comparer) {
|
1397 | var length = array.length;
|
1398 | array.sort(comparer);
|
1399 | while (length--) {
|
1400 | array[length] = array[length].value;
|
1401 | }
|
1402 | return array;
|
1403 | }
|
1404 | function compareAscending(value, other) {
|
1405 | if (value !== other) {
|
1406 | var valIsDefined = value !== void 0, valIsNull = value === null, valIsReflexive = value === value, valIsSymbol = isSymbol(value);
|
1407 | var othIsDefined = other !== void 0, othIsNull = other === null, othIsReflexive = other === other, othIsSymbol = isSymbol(other);
|
1408 | if (!othIsNull && !othIsSymbol && !valIsSymbol && value > other || valIsSymbol && othIsDefined && othIsReflexive && !othIsNull && !othIsSymbol || valIsNull && othIsDefined && othIsReflexive || !valIsDefined && othIsReflexive || !valIsReflexive) {
|
1409 | return 1;
|
1410 | }
|
1411 | if (!valIsNull && !valIsSymbol && !othIsSymbol && value < other || othIsSymbol && valIsDefined && valIsReflexive && !valIsNull && !valIsSymbol || othIsNull && valIsDefined && valIsReflexive || !othIsDefined && valIsReflexive || !othIsReflexive) {
|
1412 | return -1;
|
1413 | }
|
1414 | }
|
1415 | return 0;
|
1416 | }
|
1417 | function compareMultiple(object, other, orders) {
|
1418 | var index = -1, objCriteria = object.criteria, othCriteria = other.criteria, length = objCriteria.length, ordersLength = orders.length;
|
1419 | while (++index < length) {
|
1420 | var result = compareAscending(objCriteria[index], othCriteria[index]);
|
1421 | if (result) {
|
1422 | if (index >= ordersLength) {
|
1423 | return result;
|
1424 | }
|
1425 | var order2 = orders[index];
|
1426 | return result * (order2 == "desc" ? -1 : 1);
|
1427 | }
|
1428 | }
|
1429 | return object.index - other.index;
|
1430 | }
|
1431 | function baseOrderBy(collection, iteratees, orders) {
|
1432 | if (iteratees.length) {
|
1433 | iteratees = arrayMap(iteratees, function(iteratee) {
|
1434 | if (isArray(iteratee)) {
|
1435 | return function(value) {
|
1436 | return baseGet(value, iteratee.length === 1 ? iteratee[0] : iteratee);
|
1437 | };
|
1438 | }
|
1439 | return iteratee;
|
1440 | });
|
1441 | } else {
|
1442 | iteratees = [identity];
|
1443 | }
|
1444 | var index = -1;
|
1445 | iteratees = arrayMap(iteratees, baseUnary(baseIteratee));
|
1446 | var result = baseMap(collection, function(value, key, collection2) {
|
1447 | var criteria = arrayMap(iteratees, function(iteratee) {
|
1448 | return iteratee(value);
|
1449 | });
|
1450 | return { "criteria": criteria, "index": ++index, "value": value };
|
1451 | });
|
1452 | return baseSortBy(result, function(object, other) {
|
1453 | return compareMultiple(object, other, orders);
|
1454 | });
|
1455 | }
|
1456 | function basePick(object, paths) {
|
1457 | return basePickBy(object, paths, function(value, path) {
|
1458 | return hasIn(object, path);
|
1459 | });
|
1460 | }
|
1461 | var pick = flatRest(function(object, paths) {
|
1462 | return object == null ? {} : basePick(object, paths);
|
1463 | });
|
1464 | const pick$1 = pick;
|
1465 | var nativeCeil = Math.ceil, nativeMax = Math.max;
|
1466 | function baseRange(start, end, step, fromRight) {
|
1467 | var index = -1, length = nativeMax(nativeCeil((end - start) / (step || 1)), 0), result = Array(length);
|
1468 | while (length--) {
|
1469 | result[fromRight ? length : ++index] = start;
|
1470 | start += step;
|
1471 | }
|
1472 | return result;
|
1473 | }
|
1474 | function createRange(fromRight) {
|
1475 | return function(start, end, step) {
|
1476 | if (step && typeof step != "number" && isIterateeCall(start, end, step)) {
|
1477 | end = step = void 0;
|
1478 | }
|
1479 | start = toFinite(start);
|
1480 | if (end === void 0) {
|
1481 | end = start;
|
1482 | start = 0;
|
1483 | } else {
|
1484 | end = toFinite(end);
|
1485 | }
|
1486 | step = step === void 0 ? start < end ? 1 : -1 : toFinite(step);
|
1487 | return baseRange(start, end, step, fromRight);
|
1488 | };
|
1489 | }
|
1490 | var range = createRange();
|
1491 | const range$1 = range;
|
1492 | function baseReduce(collection, iteratee, accumulator, initAccum, eachFunc) {
|
1493 | eachFunc(collection, function(value, index, collection2) {
|
1494 | accumulator = initAccum ? (initAccum = false, value) : iteratee(accumulator, value, index, collection2);
|
1495 | });
|
1496 | return accumulator;
|
1497 | }
|
1498 | function reduce(collection, iteratee, accumulator) {
|
1499 | var func = isArray(collection) ? arrayReduce : baseReduce, initAccum = arguments.length < 3;
|
1500 | return func(collection, baseIteratee(iteratee), accumulator, initAccum, baseEach$1);
|
1501 | }
|
1502 | var sortBy = baseRest(function(collection, iteratees) {
|
1503 | if (collection == null) {
|
1504 | return [];
|
1505 | }
|
1506 | var length = iteratees.length;
|
1507 | if (length > 1 && isIterateeCall(collection, iteratees[0], iteratees[1])) {
|
1508 | iteratees = [];
|
1509 | } else if (length > 2 && isIterateeCall(iteratees[0], iteratees[1], iteratees[2])) {
|
1510 | iteratees = [iteratees[0]];
|
1511 | }
|
1512 | return baseOrderBy(collection, baseFlatten(iteratees, 1), []);
|
1513 | });
|
1514 | const sortBy$1 = sortBy;
|
1515 | var INFINITY = 1 / 0;
|
1516 | var createSet = !(Set && 1 / setToArray(new Set([, -0]))[1] == INFINITY) ? noop : function(values2) {
|
1517 | return new Set(values2);
|
1518 | };
|
1519 | const createSet$1 = createSet;
|
1520 | var LARGE_ARRAY_SIZE = 200;
|
1521 | function baseUniq(array, iteratee, comparator) {
|
1522 | var index = -1, includes = arrayIncludes, length = array.length, isCommon = true, result = [], seen = result;
|
1523 | if (comparator) {
|
1524 | isCommon = false;
|
1525 | includes = arrayIncludesWith;
|
1526 | } else if (length >= LARGE_ARRAY_SIZE) {
|
1527 | var set = iteratee ? null : createSet$1(array);
|
1528 | if (set) {
|
1529 | return setToArray(set);
|
1530 | }
|
1531 | isCommon = false;
|
1532 | includes = cacheHas;
|
1533 | seen = new SetCache();
|
1534 | } else {
|
1535 | seen = iteratee ? [] : result;
|
1536 | }
|
1537 | outer:
|
1538 | while (++index < length) {
|
1539 | var value = array[index], computed = iteratee ? iteratee(value) : value;
|
1540 | value = comparator || value !== 0 ? value : 0;
|
1541 | if (isCommon && computed === computed) {
|
1542 | var seenIndex = seen.length;
|
1543 | while (seenIndex--) {
|
1544 | if (seen[seenIndex] === computed) {
|
1545 | continue outer;
|
1546 | }
|
1547 | }
|
1548 | if (iteratee) {
|
1549 | seen.push(computed);
|
1550 | }
|
1551 | result.push(value);
|
1552 | } else if (!includes(seen, computed, comparator)) {
|
1553 | if (seen !== result) {
|
1554 | seen.push(computed);
|
1555 | }
|
1556 | result.push(value);
|
1557 | }
|
1558 | }
|
1559 | return result;
|
1560 | }
|
1561 | var union = baseRest(function(arrays) {
|
1562 | return baseUniq(baseFlatten(arrays, 1, isArrayLikeObject, true));
|
1563 | });
|
1564 | const union$1 = union;
|
1565 | var idCounter = 0;
|
1566 | function uniqueId(prefix) {
|
1567 | var id = ++idCounter;
|
1568 | return toString(prefix) + id;
|
1569 | }
|
1570 | function baseZipObject(props, values2, assignFunc) {
|
1571 | var index = -1, length = props.length, valsLength = values2.length, result = {};
|
1572 | while (++index < length) {
|
1573 | var value = index < valsLength ? values2[index] : void 0;
|
1574 | assignFunc(result, props[index], value);
|
1575 | }
|
1576 | return result;
|
1577 | }
|
1578 | function zipObject(props, values2) {
|
1579 | return baseZipObject(props || [], values2 || [], assignValue);
|
1580 | }
|
1581 | var DEFAULT_EDGE_NAME = "\0";
|
1582 | var GRAPH_NODE = "\0";
|
1583 | var EDGE_KEY_DELIM = "";
|
1584 | class Graph {
|
1585 | constructor(opts = {}) {
|
1586 | this._isDirected = has(opts, "directed") ? opts.directed : true;
|
1587 | this._isMultigraph = has(opts, "multigraph") ? opts.multigraph : false;
|
1588 | this._isCompound = has(opts, "compound") ? opts.compound : false;
|
1589 | this._label = void 0;
|
1590 | this._defaultNodeLabelFn = constant(void 0);
|
1591 | this._defaultEdgeLabelFn = constant(void 0);
|
1592 | this._nodes = {};
|
1593 | if (this._isCompound) {
|
1594 | this._parent = {};
|
1595 | this._children = {};
|
1596 | this._children[GRAPH_NODE] = {};
|
1597 | }
|
1598 | this._in = {};
|
1599 | this._preds = {};
|
1600 | this._out = {};
|
1601 | this._sucs = {};
|
1602 | this._edgeObjs = {};
|
1603 | this._edgeLabels = {};
|
1604 | }
|
1605 |
|
1606 | isDirected() {
|
1607 | return this._isDirected;
|
1608 | }
|
1609 | isMultigraph() {
|
1610 | return this._isMultigraph;
|
1611 | }
|
1612 | isCompound() {
|
1613 | return this._isCompound;
|
1614 | }
|
1615 | setGraph(label) {
|
1616 | this._label = label;
|
1617 | return this;
|
1618 | }
|
1619 | graph() {
|
1620 | return this._label;
|
1621 | }
|
1622 |
|
1623 | setDefaultNodeLabel(newDefault) {
|
1624 | if (!isFunction(newDefault)) {
|
1625 | newDefault = constant(newDefault);
|
1626 | }
|
1627 | this._defaultNodeLabelFn = newDefault;
|
1628 | return this;
|
1629 | }
|
1630 | nodeCount() {
|
1631 | return this._nodeCount;
|
1632 | }
|
1633 | nodes() {
|
1634 | return keys(this._nodes);
|
1635 | }
|
1636 | sources() {
|
1637 | var self = this;
|
1638 | return filter(this.nodes(), function(v) {
|
1639 | return isEmpty(self._in[v]);
|
1640 | });
|
1641 | }
|
1642 | sinks() {
|
1643 | var self = this;
|
1644 | return filter(this.nodes(), function(v) {
|
1645 | return isEmpty(self._out[v]);
|
1646 | });
|
1647 | }
|
1648 | setNodes(vs, value) {
|
1649 | var args = arguments;
|
1650 | var self = this;
|
1651 | forEach(vs, function(v) {
|
1652 | if (args.length > 1) {
|
1653 | self.setNode(v, value);
|
1654 | } else {
|
1655 | self.setNode(v);
|
1656 | }
|
1657 | });
|
1658 | return this;
|
1659 | }
|
1660 | setNode(v, value) {
|
1661 | if (has(this._nodes, v)) {
|
1662 | if (arguments.length > 1) {
|
1663 | this._nodes[v] = value;
|
1664 | }
|
1665 | return this;
|
1666 | }
|
1667 | this._nodes[v] = arguments.length > 1 ? value : this._defaultNodeLabelFn(v);
|
1668 | if (this._isCompound) {
|
1669 | this._parent[v] = GRAPH_NODE;
|
1670 | this._children[v] = {};
|
1671 | this._children[GRAPH_NODE][v] = true;
|
1672 | }
|
1673 | this._in[v] = {};
|
1674 | this._preds[v] = {};
|
1675 | this._out[v] = {};
|
1676 | this._sucs[v] = {};
|
1677 | ++this._nodeCount;
|
1678 | return this;
|
1679 | }
|
1680 | node(v) {
|
1681 | return this._nodes[v];
|
1682 | }
|
1683 | hasNode(v) {
|
1684 | return has(this._nodes, v);
|
1685 | }
|
1686 | removeNode(v) {
|
1687 | var self = this;
|
1688 | if (has(this._nodes, v)) {
|
1689 | var removeEdge = function(e) {
|
1690 | self.removeEdge(self._edgeObjs[e]);
|
1691 | };
|
1692 | delete this._nodes[v];
|
1693 | if (this._isCompound) {
|
1694 | this._removeFromParentsChildList(v);
|
1695 | delete this._parent[v];
|
1696 | forEach(this.children(v), function(child) {
|
1697 | self.setParent(child);
|
1698 | });
|
1699 | delete this._children[v];
|
1700 | }
|
1701 | forEach(keys(this._in[v]), removeEdge);
|
1702 | delete this._in[v];
|
1703 | delete this._preds[v];
|
1704 | forEach(keys(this._out[v]), removeEdge);
|
1705 | delete this._out[v];
|
1706 | delete this._sucs[v];
|
1707 | --this._nodeCount;
|
1708 | }
|
1709 | return this;
|
1710 | }
|
1711 | setParent(v, parent) {
|
1712 | if (!this._isCompound) {
|
1713 | throw new Error("Cannot set parent in a non-compound graph");
|
1714 | }
|
1715 | if (isUndefined(parent)) {
|
1716 | parent = GRAPH_NODE;
|
1717 | } else {
|
1718 | parent += "";
|
1719 | for (var ancestor = parent; !isUndefined(ancestor); ancestor = this.parent(ancestor)) {
|
1720 | if (ancestor === v) {
|
1721 | throw new Error("Setting " + parent + " as parent of " + v + " would create a cycle");
|
1722 | }
|
1723 | }
|
1724 | this.setNode(parent);
|
1725 | }
|
1726 | this.setNode(v);
|
1727 | this._removeFromParentsChildList(v);
|
1728 | this._parent[v] = parent;
|
1729 | this._children[parent][v] = true;
|
1730 | return this;
|
1731 | }
|
1732 | _removeFromParentsChildList(v) {
|
1733 | delete this._children[this._parent[v]][v];
|
1734 | }
|
1735 | parent(v) {
|
1736 | if (this._isCompound) {
|
1737 | var parent = this._parent[v];
|
1738 | if (parent !== GRAPH_NODE) {
|
1739 | return parent;
|
1740 | }
|
1741 | }
|
1742 | }
|
1743 | children(v) {
|
1744 | if (isUndefined(v)) {
|
1745 | v = GRAPH_NODE;
|
1746 | }
|
1747 | if (this._isCompound) {
|
1748 | var children = this._children[v];
|
1749 | if (children) {
|
1750 | return keys(children);
|
1751 | }
|
1752 | } else if (v === GRAPH_NODE) {
|
1753 | return this.nodes();
|
1754 | } else if (this.hasNode(v)) {
|
1755 | return [];
|
1756 | }
|
1757 | }
|
1758 | predecessors(v) {
|
1759 | var predsV = this._preds[v];
|
1760 | if (predsV) {
|
1761 | return keys(predsV);
|
1762 | }
|
1763 | }
|
1764 | successors(v) {
|
1765 | var sucsV = this._sucs[v];
|
1766 | if (sucsV) {
|
1767 | return keys(sucsV);
|
1768 | }
|
1769 | }
|
1770 | neighbors(v) {
|
1771 | var preds = this.predecessors(v);
|
1772 | if (preds) {
|
1773 | return union$1(preds, this.successors(v));
|
1774 | }
|
1775 | }
|
1776 | isLeaf(v) {
|
1777 | var neighbors;
|
1778 | if (this.isDirected()) {
|
1779 | neighbors = this.successors(v);
|
1780 | } else {
|
1781 | neighbors = this.neighbors(v);
|
1782 | }
|
1783 | return neighbors.length === 0;
|
1784 | }
|
1785 | filterNodes(filter2) {
|
1786 | var copy = new this.constructor({
|
1787 | directed: this._isDirected,
|
1788 | multigraph: this._isMultigraph,
|
1789 | compound: this._isCompound
|
1790 | });
|
1791 | copy.setGraph(this.graph());
|
1792 | var self = this;
|
1793 | forEach(this._nodes, function(value, v) {
|
1794 | if (filter2(v)) {
|
1795 | copy.setNode(v, value);
|
1796 | }
|
1797 | });
|
1798 | forEach(this._edgeObjs, function(e) {
|
1799 | if (copy.hasNode(e.v) && copy.hasNode(e.w)) {
|
1800 | copy.setEdge(e, self.edge(e));
|
1801 | }
|
1802 | });
|
1803 | var parents = {};
|
1804 | function findParent(v) {
|
1805 | var parent = self.parent(v);
|
1806 | if (parent === void 0 || copy.hasNode(parent)) {
|
1807 | parents[v] = parent;
|
1808 | return parent;
|
1809 | } else if (parent in parents) {
|
1810 | return parents[parent];
|
1811 | } else {
|
1812 | return findParent(parent);
|
1813 | }
|
1814 | }
|
1815 | if (this._isCompound) {
|
1816 | forEach(copy.nodes(), function(v) {
|
1817 | copy.setParent(v, findParent(v));
|
1818 | });
|
1819 | }
|
1820 | return copy;
|
1821 | }
|
1822 |
|
1823 | setDefaultEdgeLabel(newDefault) {
|
1824 | if (!isFunction(newDefault)) {
|
1825 | newDefault = constant(newDefault);
|
1826 | }
|
1827 | this._defaultEdgeLabelFn = newDefault;
|
1828 | return this;
|
1829 | }
|
1830 | edgeCount() {
|
1831 | return this._edgeCount;
|
1832 | }
|
1833 | edges() {
|
1834 | return values(this._edgeObjs);
|
1835 | }
|
1836 | setPath(vs, value) {
|
1837 | var self = this;
|
1838 | var args = arguments;
|
1839 | reduce(vs, function(v, w) {
|
1840 | if (args.length > 1) {
|
1841 | self.setEdge(v, w, value);
|
1842 | } else {
|
1843 | self.setEdge(v, w);
|
1844 | }
|
1845 | return w;
|
1846 | });
|
1847 | return this;
|
1848 | }
|
1849 | |
1850 |
|
1851 |
|
1852 |
|
1853 | setEdge() {
|
1854 | var v, w, name, value;
|
1855 | var valueSpecified = false;
|
1856 | var arg0 = arguments[0];
|
1857 | if (typeof arg0 === "object" && arg0 !== null && "v" in arg0) {
|
1858 | v = arg0.v;
|
1859 | w = arg0.w;
|
1860 | name = arg0.name;
|
1861 | if (arguments.length === 2) {
|
1862 | value = arguments[1];
|
1863 | valueSpecified = true;
|
1864 | }
|
1865 | } else {
|
1866 | v = arg0;
|
1867 | w = arguments[1];
|
1868 | name = arguments[3];
|
1869 | if (arguments.length > 2) {
|
1870 | value = arguments[2];
|
1871 | valueSpecified = true;
|
1872 | }
|
1873 | }
|
1874 | v = "" + v;
|
1875 | w = "" + w;
|
1876 | if (!isUndefined(name)) {
|
1877 | name = "" + name;
|
1878 | }
|
1879 | var e = edgeArgsToId(this._isDirected, v, w, name);
|
1880 | if (has(this._edgeLabels, e)) {
|
1881 | if (valueSpecified) {
|
1882 | this._edgeLabels[e] = value;
|
1883 | }
|
1884 | return this;
|
1885 | }
|
1886 | if (!isUndefined(name) && !this._isMultigraph) {
|
1887 | throw new Error("Cannot set a named edge when isMultigraph = false");
|
1888 | }
|
1889 | this.setNode(v);
|
1890 | this.setNode(w);
|
1891 | this._edgeLabels[e] = valueSpecified ? value : this._defaultEdgeLabelFn(v, w, name);
|
1892 | var edgeObj = edgeArgsToObj(this._isDirected, v, w, name);
|
1893 | v = edgeObj.v;
|
1894 | w = edgeObj.w;
|
1895 | Object.freeze(edgeObj);
|
1896 | this._edgeObjs[e] = edgeObj;
|
1897 | incrementOrInitEntry(this._preds[w], v);
|
1898 | incrementOrInitEntry(this._sucs[v], w);
|
1899 | this._in[w][e] = edgeObj;
|
1900 | this._out[v][e] = edgeObj;
|
1901 | this._edgeCount++;
|
1902 | return this;
|
1903 | }
|
1904 | edge(v, w, name) {
|
1905 | var e = arguments.length === 1 ? edgeObjToId(this._isDirected, arguments[0]) : edgeArgsToId(this._isDirected, v, w, name);
|
1906 | return this._edgeLabels[e];
|
1907 | }
|
1908 | hasEdge(v, w, name) {
|
1909 | var e = arguments.length === 1 ? edgeObjToId(this._isDirected, arguments[0]) : edgeArgsToId(this._isDirected, v, w, name);
|
1910 | return has(this._edgeLabels, e);
|
1911 | }
|
1912 | removeEdge(v, w, name) {
|
1913 | var e = arguments.length === 1 ? edgeObjToId(this._isDirected, arguments[0]) : edgeArgsToId(this._isDirected, v, w, name);
|
1914 | var edge = this._edgeObjs[e];
|
1915 | if (edge) {
|
1916 | v = edge.v;
|
1917 | w = edge.w;
|
1918 | delete this._edgeLabels[e];
|
1919 | delete this._edgeObjs[e];
|
1920 | decrementOrRemoveEntry(this._preds[w], v);
|
1921 | decrementOrRemoveEntry(this._sucs[v], w);
|
1922 | delete this._in[w][e];
|
1923 | delete this._out[v][e];
|
1924 | this._edgeCount--;
|
1925 | }
|
1926 | return this;
|
1927 | }
|
1928 | inEdges(v, u) {
|
1929 | var inV = this._in[v];
|
1930 | if (inV) {
|
1931 | var edges = values(inV);
|
1932 | if (!u) {
|
1933 | return edges;
|
1934 | }
|
1935 | return filter(edges, function(edge) {
|
1936 | return edge.v === u;
|
1937 | });
|
1938 | }
|
1939 | }
|
1940 | outEdges(v, w) {
|
1941 | var outV = this._out[v];
|
1942 | if (outV) {
|
1943 | var edges = values(outV);
|
1944 | if (!w) {
|
1945 | return edges;
|
1946 | }
|
1947 | return filter(edges, function(edge) {
|
1948 | return edge.w === w;
|
1949 | });
|
1950 | }
|
1951 | }
|
1952 | nodeEdges(v, w) {
|
1953 | var inEdges = this.inEdges(v, w);
|
1954 | if (inEdges) {
|
1955 | return inEdges.concat(this.outEdges(v, w));
|
1956 | }
|
1957 | }
|
1958 | }
|
1959 | Graph.prototype._nodeCount = 0;
|
1960 | Graph.prototype._edgeCount = 0;
|
1961 | function incrementOrInitEntry(map2, k) {
|
1962 | if (map2[k]) {
|
1963 | map2[k]++;
|
1964 | } else {
|
1965 | map2[k] = 1;
|
1966 | }
|
1967 | }
|
1968 | function decrementOrRemoveEntry(map2, k) {
|
1969 | if (!--map2[k]) {
|
1970 | delete map2[k];
|
1971 | }
|
1972 | }
|
1973 | function edgeArgsToId(isDirected, v_, w_, name) {
|
1974 | var v = "" + v_;
|
1975 | var w = "" + w_;
|
1976 | if (!isDirected && v > w) {
|
1977 | var tmp = v;
|
1978 | v = w;
|
1979 | w = tmp;
|
1980 | }
|
1981 | return v + EDGE_KEY_DELIM + w + EDGE_KEY_DELIM + (isUndefined(name) ? DEFAULT_EDGE_NAME : name);
|
1982 | }
|
1983 | function edgeArgsToObj(isDirected, v_, w_, name) {
|
1984 | var v = "" + v_;
|
1985 | var w = "" + w_;
|
1986 | if (!isDirected && v > w) {
|
1987 | var tmp = v;
|
1988 | v = w;
|
1989 | w = tmp;
|
1990 | }
|
1991 | var edgeObj = { v, w };
|
1992 | if (name) {
|
1993 | edgeObj.name = name;
|
1994 | }
|
1995 | return edgeObj;
|
1996 | }
|
1997 | function edgeObjToId(isDirected, edgeObj) {
|
1998 | return edgeArgsToId(isDirected, edgeObj.v, edgeObj.w, edgeObj.name);
|
1999 | }
|
2000 | class List {
|
2001 | constructor() {
|
2002 | var sentinel = {};
|
2003 | sentinel._next = sentinel._prev = sentinel;
|
2004 | this._sentinel = sentinel;
|
2005 | }
|
2006 | dequeue() {
|
2007 | var sentinel = this._sentinel;
|
2008 | var entry = sentinel._prev;
|
2009 | if (entry !== sentinel) {
|
2010 | unlink(entry);
|
2011 | return entry;
|
2012 | }
|
2013 | }
|
2014 | enqueue(entry) {
|
2015 | var sentinel = this._sentinel;
|
2016 | if (entry._prev && entry._next) {
|
2017 | unlink(entry);
|
2018 | }
|
2019 | entry._next = sentinel._next;
|
2020 | sentinel._next._prev = entry;
|
2021 | sentinel._next = entry;
|
2022 | entry._prev = sentinel;
|
2023 | }
|
2024 | toString() {
|
2025 | var strs = [];
|
2026 | var sentinel = this._sentinel;
|
2027 | var curr = sentinel._prev;
|
2028 | while (curr !== sentinel) {
|
2029 | strs.push(JSON.stringify(curr, filterOutLinks));
|
2030 | curr = curr._prev;
|
2031 | }
|
2032 | return "[" + strs.join(", ") + "]";
|
2033 | }
|
2034 | }
|
2035 | function unlink(entry) {
|
2036 | entry._prev._next = entry._next;
|
2037 | entry._next._prev = entry._prev;
|
2038 | delete entry._next;
|
2039 | delete entry._prev;
|
2040 | }
|
2041 | function filterOutLinks(k, v) {
|
2042 | if (k !== "_next" && k !== "_prev") {
|
2043 | return v;
|
2044 | }
|
2045 | }
|
2046 | var DEFAULT_WEIGHT_FN = constant(1);
|
2047 | function greedyFAS(g, weightFn) {
|
2048 | if (g.nodeCount() <= 1) {
|
2049 | return [];
|
2050 | }
|
2051 | var state = buildState(g, weightFn || DEFAULT_WEIGHT_FN);
|
2052 | var results = doGreedyFAS(state.graph, state.buckets, state.zeroIdx);
|
2053 | return flatten(
|
2054 | map(results, function(e) {
|
2055 | return g.outEdges(e.v, e.w);
|
2056 | })
|
2057 | );
|
2058 | }
|
2059 | function doGreedyFAS(g, buckets, zeroIdx) {
|
2060 | var results = [];
|
2061 | var sources = buckets[buckets.length - 1];
|
2062 | var sinks = buckets[0];
|
2063 | var entry;
|
2064 | while (g.nodeCount()) {
|
2065 | while (entry = sinks.dequeue()) {
|
2066 | removeNode(g, buckets, zeroIdx, entry);
|
2067 | }
|
2068 | while (entry = sources.dequeue()) {
|
2069 | removeNode(g, buckets, zeroIdx, entry);
|
2070 | }
|
2071 | if (g.nodeCount()) {
|
2072 | for (var i = buckets.length - 2; i > 0; --i) {
|
2073 | entry = buckets[i].dequeue();
|
2074 | if (entry) {
|
2075 | results = results.concat(removeNode(g, buckets, zeroIdx, entry, true));
|
2076 | break;
|
2077 | }
|
2078 | }
|
2079 | }
|
2080 | }
|
2081 | return results;
|
2082 | }
|
2083 | function removeNode(g, buckets, zeroIdx, entry, collectPredecessors) {
|
2084 | var results = collectPredecessors ? [] : void 0;
|
2085 | forEach(g.inEdges(entry.v), function(edge) {
|
2086 | var weight = g.edge(edge);
|
2087 | var uEntry = g.node(edge.v);
|
2088 | if (collectPredecessors) {
|
2089 | results.push({ v: edge.v, w: edge.w });
|
2090 | }
|
2091 | uEntry.out -= weight;
|
2092 | assignBucket(buckets, zeroIdx, uEntry);
|
2093 | });
|
2094 | forEach(g.outEdges(entry.v), function(edge) {
|
2095 | var weight = g.edge(edge);
|
2096 | var w = edge.w;
|
2097 | var wEntry = g.node(w);
|
2098 | wEntry["in"] -= weight;
|
2099 | assignBucket(buckets, zeroIdx, wEntry);
|
2100 | });
|
2101 | g.removeNode(entry.v);
|
2102 | return results;
|
2103 | }
|
2104 | function buildState(g, weightFn) {
|
2105 | var fasGraph = new Graph();
|
2106 | var maxIn = 0;
|
2107 | var maxOut = 0;
|
2108 | forEach(g.nodes(), function(v) {
|
2109 | fasGraph.setNode(v, { v, in: 0, out: 0 });
|
2110 | });
|
2111 | forEach(g.edges(), function(e) {
|
2112 | var prevWeight = fasGraph.edge(e.v, e.w) || 0;
|
2113 | var weight = weightFn(e);
|
2114 | var edgeWeight = prevWeight + weight;
|
2115 | fasGraph.setEdge(e.v, e.w, edgeWeight);
|
2116 | maxOut = Math.max(maxOut, fasGraph.node(e.v).out += weight);
|
2117 | maxIn = Math.max(maxIn, fasGraph.node(e.w)["in"] += weight);
|
2118 | });
|
2119 | var buckets = range$1(maxOut + maxIn + 3).map(function() {
|
2120 | return new List();
|
2121 | });
|
2122 | var zeroIdx = maxIn + 1;
|
2123 | forEach(fasGraph.nodes(), function(v) {
|
2124 | assignBucket(buckets, zeroIdx, fasGraph.node(v));
|
2125 | });
|
2126 | return { graph: fasGraph, buckets, zeroIdx };
|
2127 | }
|
2128 | function assignBucket(buckets, zeroIdx, entry) {
|
2129 | if (!entry.out) {
|
2130 | buckets[0].enqueue(entry);
|
2131 | } else if (!entry["in"]) {
|
2132 | buckets[buckets.length - 1].enqueue(entry);
|
2133 | } else {
|
2134 | buckets[entry.out - entry["in"] + zeroIdx].enqueue(entry);
|
2135 | }
|
2136 | }
|
2137 | function run$2(g) {
|
2138 | var fas = g.graph().acyclicer === "greedy" ? greedyFAS(g, weightFn(g)) : dfsFAS(g);
|
2139 | forEach(fas, function(e) {
|
2140 | var label = g.edge(e);
|
2141 | g.removeEdge(e);
|
2142 | label.forwardName = e.name;
|
2143 | label.reversed = true;
|
2144 | g.setEdge(e.w, e.v, label, uniqueId("rev"));
|
2145 | });
|
2146 | function weightFn(g2) {
|
2147 | return function(e) {
|
2148 | return g2.edge(e).weight;
|
2149 | };
|
2150 | }
|
2151 | }
|
2152 | function dfsFAS(g) {
|
2153 | var fas = [];
|
2154 | var stack = {};
|
2155 | var visited = {};
|
2156 | function dfs2(v) {
|
2157 | if (has(visited, v)) {
|
2158 | return;
|
2159 | }
|
2160 | visited[v] = true;
|
2161 | stack[v] = true;
|
2162 | forEach(g.outEdges(v), function(e) {
|
2163 | if (has(stack, e.w)) {
|
2164 | fas.push(e);
|
2165 | } else {
|
2166 | dfs2(e.w);
|
2167 | }
|
2168 | });
|
2169 | delete stack[v];
|
2170 | }
|
2171 | forEach(g.nodes(), dfs2);
|
2172 | return fas;
|
2173 | }
|
2174 | function undo$2(g) {
|
2175 | forEach(g.edges(), function(e) {
|
2176 | var label = g.edge(e);
|
2177 | if (label.reversed) {
|
2178 | g.removeEdge(e);
|
2179 | var forwardName = label.forwardName;
|
2180 | delete label.reversed;
|
2181 | delete label.forwardName;
|
2182 | g.setEdge(e.w, e.v, label, forwardName);
|
2183 | }
|
2184 | });
|
2185 | }
|
2186 | function addDummyNode(g, type, attrs, name) {
|
2187 | var v;
|
2188 | do {
|
2189 | v = uniqueId(name);
|
2190 | } while (g.hasNode(v));
|
2191 | attrs.dummy = type;
|
2192 | g.setNode(v, attrs);
|
2193 | return v;
|
2194 | }
|
2195 | function simplify(g) {
|
2196 | var simplified = new Graph().setGraph(g.graph());
|
2197 | forEach(g.nodes(), function(v) {
|
2198 | simplified.setNode(v, g.node(v));
|
2199 | });
|
2200 | forEach(g.edges(), function(e) {
|
2201 | var simpleLabel = simplified.edge(e.v, e.w) || { weight: 0, minlen: 1 };
|
2202 | var label = g.edge(e);
|
2203 | simplified.setEdge(e.v, e.w, {
|
2204 | weight: simpleLabel.weight + label.weight,
|
2205 | minlen: Math.max(simpleLabel.minlen, label.minlen)
|
2206 | });
|
2207 | });
|
2208 | return simplified;
|
2209 | }
|
2210 | function asNonCompoundGraph(g) {
|
2211 | var simplified = new Graph({ multigraph: g.isMultigraph() }).setGraph(g.graph());
|
2212 | forEach(g.nodes(), function(v) {
|
2213 | if (!g.children(v).length) {
|
2214 | simplified.setNode(v, g.node(v));
|
2215 | }
|
2216 | });
|
2217 | forEach(g.edges(), function(e) {
|
2218 | simplified.setEdge(e, g.edge(e));
|
2219 | });
|
2220 | return simplified;
|
2221 | }
|
2222 | function intersectRect(rect, point) {
|
2223 | var x = rect.x;
|
2224 | var y = rect.y;
|
2225 | var dx = point.x - x;
|
2226 | var dy = point.y - y;
|
2227 | var w = rect.width / 2;
|
2228 | var h = rect.height / 2;
|
2229 | if (!dx && !dy) {
|
2230 | throw new Error("Not possible to find intersection inside of the rectangle");
|
2231 | }
|
2232 | var sx, sy;
|
2233 | if (Math.abs(dy) * w > Math.abs(dx) * h) {
|
2234 | if (dy < 0) {
|
2235 | h = -h;
|
2236 | }
|
2237 | sx = h * dx / dy;
|
2238 | sy = h;
|
2239 | } else {
|
2240 | if (dx < 0) {
|
2241 | w = -w;
|
2242 | }
|
2243 | sx = w;
|
2244 | sy = w * dy / dx;
|
2245 | }
|
2246 | return { x: x + sx, y: y + sy };
|
2247 | }
|
2248 | function buildLayerMatrix(g) {
|
2249 | var layering = map(range$1(maxRank(g) + 1), function() {
|
2250 | return [];
|
2251 | });
|
2252 | forEach(g.nodes(), function(v) {
|
2253 | var node = g.node(v);
|
2254 | var rank2 = node.rank;
|
2255 | if (!isUndefined(rank2)) {
|
2256 | layering[rank2][node.order] = v;
|
2257 | }
|
2258 | });
|
2259 | return layering;
|
2260 | }
|
2261 | function normalizeRanks(g) {
|
2262 | var min$1 = min(
|
2263 | map(g.nodes(), function(v) {
|
2264 | return g.node(v).rank;
|
2265 | })
|
2266 | );
|
2267 | forEach(g.nodes(), function(v) {
|
2268 | var node = g.node(v);
|
2269 | if (has(node, "rank")) {
|
2270 | node.rank -= min$1;
|
2271 | }
|
2272 | });
|
2273 | }
|
2274 | function removeEmptyRanks(g) {
|
2275 | var offset = min(
|
2276 | map(g.nodes(), function(v) {
|
2277 | return g.node(v).rank;
|
2278 | })
|
2279 | );
|
2280 | var layers = [];
|
2281 | forEach(g.nodes(), function(v) {
|
2282 | var rank2 = g.node(v).rank - offset;
|
2283 | if (!layers[rank2]) {
|
2284 | layers[rank2] = [];
|
2285 | }
|
2286 | layers[rank2].push(v);
|
2287 | });
|
2288 | var delta = 0;
|
2289 | var nodeRankFactor = g.graph().nodeRankFactor;
|
2290 | forEach(layers, function(vs, i) {
|
2291 | if (isUndefined(vs) && i % nodeRankFactor !== 0) {
|
2292 | --delta;
|
2293 | } else if (delta) {
|
2294 | forEach(vs, function(v) {
|
2295 | g.node(v).rank += delta;
|
2296 | });
|
2297 | }
|
2298 | });
|
2299 | }
|
2300 | function addBorderNode$1(g, prefix, rank2, order2) {
|
2301 | var node = {
|
2302 | width: 0,
|
2303 | height: 0
|
2304 | };
|
2305 | if (arguments.length >= 4) {
|
2306 | node.rank = rank2;
|
2307 | node.order = order2;
|
2308 | }
|
2309 | return addDummyNode(g, "border", node, prefix);
|
2310 | }
|
2311 | function maxRank(g) {
|
2312 | return max(
|
2313 | map(g.nodes(), function(v) {
|
2314 | var rank2 = g.node(v).rank;
|
2315 | if (!isUndefined(rank2)) {
|
2316 | return rank2;
|
2317 | }
|
2318 | })
|
2319 | );
|
2320 | }
|
2321 | function partition(collection, fn) {
|
2322 | var result = { lhs: [], rhs: [] };
|
2323 | forEach(collection, function(value) {
|
2324 | if (fn(value)) {
|
2325 | result.lhs.push(value);
|
2326 | } else {
|
2327 | result.rhs.push(value);
|
2328 | }
|
2329 | });
|
2330 | return result;
|
2331 | }
|
2332 | function time(name, fn) {
|
2333 | var start = now$1();
|
2334 | try {
|
2335 | return fn();
|
2336 | } finally {
|
2337 | console.log(name + " time: " + (now$1() - start) + "ms");
|
2338 | }
|
2339 | }
|
2340 | function notime(name, fn) {
|
2341 | return fn();
|
2342 | }
|
2343 | function addBorderSegments(g) {
|
2344 | function dfs2(v) {
|
2345 | var children = g.children(v);
|
2346 | var node = g.node(v);
|
2347 | if (children.length) {
|
2348 | forEach(children, dfs2);
|
2349 | }
|
2350 | if (has(node, "minRank")) {
|
2351 | node.borderLeft = [];
|
2352 | node.borderRight = [];
|
2353 | for (var rank2 = node.minRank, maxRank2 = node.maxRank + 1; rank2 < maxRank2; ++rank2) {
|
2354 | addBorderNode(g, "borderLeft", "_bl", v, node, rank2);
|
2355 | addBorderNode(g, "borderRight", "_br", v, node, rank2);
|
2356 | }
|
2357 | }
|
2358 | }
|
2359 | forEach(g.children(), dfs2);
|
2360 | }
|
2361 | function addBorderNode(g, prop, prefix, sg, sgNode, rank2) {
|
2362 | var label = { width: 0, height: 0, rank: rank2, borderType: prop };
|
2363 | var prev = sgNode[prop][rank2 - 1];
|
2364 | var curr = addDummyNode(g, "border", label, prefix);
|
2365 | sgNode[prop][rank2] = curr;
|
2366 | g.setParent(curr, sg);
|
2367 | if (prev) {
|
2368 | g.setEdge(prev, curr, { weight: 1 });
|
2369 | }
|
2370 | }
|
2371 | function adjust(g) {
|
2372 | var rankDir = g.graph().rankdir.toLowerCase();
|
2373 | if (rankDir === "lr" || rankDir === "rl") {
|
2374 | swapWidthHeight(g);
|
2375 | }
|
2376 | }
|
2377 | function undo$1(g) {
|
2378 | var rankDir = g.graph().rankdir.toLowerCase();
|
2379 | if (rankDir === "bt" || rankDir === "rl") {
|
2380 | reverseY(g);
|
2381 | }
|
2382 | if (rankDir === "lr" || rankDir === "rl") {
|
2383 | swapXY(g);
|
2384 | swapWidthHeight(g);
|
2385 | }
|
2386 | }
|
2387 | function swapWidthHeight(g) {
|
2388 | forEach(g.nodes(), function(v) {
|
2389 | swapWidthHeightOne(g.node(v));
|
2390 | });
|
2391 | forEach(g.edges(), function(e) {
|
2392 | swapWidthHeightOne(g.edge(e));
|
2393 | });
|
2394 | }
|
2395 | function swapWidthHeightOne(attrs) {
|
2396 | var w = attrs.width;
|
2397 | attrs.width = attrs.height;
|
2398 | attrs.height = w;
|
2399 | }
|
2400 | function reverseY(g) {
|
2401 | forEach(g.nodes(), function(v) {
|
2402 | reverseYOne(g.node(v));
|
2403 | });
|
2404 | forEach(g.edges(), function(e) {
|
2405 | var edge = g.edge(e);
|
2406 | forEach(edge.points, reverseYOne);
|
2407 | if (has(edge, "y")) {
|
2408 | reverseYOne(edge);
|
2409 | }
|
2410 | });
|
2411 | }
|
2412 | function reverseYOne(attrs) {
|
2413 | attrs.y = -attrs.y;
|
2414 | }
|
2415 | function swapXY(g) {
|
2416 | forEach(g.nodes(), function(v) {
|
2417 | swapXYOne(g.node(v));
|
2418 | });
|
2419 | forEach(g.edges(), function(e) {
|
2420 | var edge = g.edge(e);
|
2421 | forEach(edge.points, swapXYOne);
|
2422 | if (has(edge, "x")) {
|
2423 | swapXYOne(edge);
|
2424 | }
|
2425 | });
|
2426 | }
|
2427 | function swapXYOne(attrs) {
|
2428 | var x = attrs.x;
|
2429 | attrs.x = attrs.y;
|
2430 | attrs.y = x;
|
2431 | }
|
2432 | function run$1(g) {
|
2433 | g.graph().dummyChains = [];
|
2434 | forEach(g.edges(), function(edge) {
|
2435 | normalizeEdge(g, edge);
|
2436 | });
|
2437 | }
|
2438 | function normalizeEdge(g, e) {
|
2439 | var v = e.v;
|
2440 | var vRank = g.node(v).rank;
|
2441 | var w = e.w;
|
2442 | var wRank = g.node(w).rank;
|
2443 | var name = e.name;
|
2444 | var edgeLabel = g.edge(e);
|
2445 | var labelRank = edgeLabel.labelRank;
|
2446 | if (wRank === vRank + 1)
|
2447 | return;
|
2448 | g.removeEdge(e);
|
2449 | var dummy, attrs, i;
|
2450 | for (i = 0, ++vRank; vRank < wRank; ++i, ++vRank) {
|
2451 | edgeLabel.points = [];
|
2452 | attrs = {
|
2453 | width: 0,
|
2454 | height: 0,
|
2455 | edgeLabel,
|
2456 | edgeObj: e,
|
2457 | rank: vRank
|
2458 | };
|
2459 | dummy = addDummyNode(g, "edge", attrs, "_d");
|
2460 | if (vRank === labelRank) {
|
2461 | attrs.width = edgeLabel.width;
|
2462 | attrs.height = edgeLabel.height;
|
2463 | attrs.dummy = "edge-label";
|
2464 | attrs.labelpos = edgeLabel.labelpos;
|
2465 | }
|
2466 | g.setEdge(v, dummy, { weight: edgeLabel.weight }, name);
|
2467 | if (i === 0) {
|
2468 | g.graph().dummyChains.push(dummy);
|
2469 | }
|
2470 | v = dummy;
|
2471 | }
|
2472 | g.setEdge(v, w, { weight: edgeLabel.weight }, name);
|
2473 | }
|
2474 | function undo(g) {
|
2475 | forEach(g.graph().dummyChains, function(v) {
|
2476 | var node = g.node(v);
|
2477 | var origLabel = node.edgeLabel;
|
2478 | var w;
|
2479 | g.setEdge(node.edgeObj, origLabel);
|
2480 | while (node.dummy) {
|
2481 | w = g.successors(v)[0];
|
2482 | g.removeNode(v);
|
2483 | origLabel.points.push({ x: node.x, y: node.y });
|
2484 | if (node.dummy === "edge-label") {
|
2485 | origLabel.x = node.x;
|
2486 | origLabel.y = node.y;
|
2487 | origLabel.width = node.width;
|
2488 | origLabel.height = node.height;
|
2489 | }
|
2490 | v = w;
|
2491 | node = g.node(v);
|
2492 | }
|
2493 | });
|
2494 | }
|
2495 | function longestPath(g) {
|
2496 | var visited = {};
|
2497 | function dfs2(v) {
|
2498 | var label = g.node(v);
|
2499 | if (has(visited, v)) {
|
2500 | return label.rank;
|
2501 | }
|
2502 | visited[v] = true;
|
2503 | var rank2 = min(
|
2504 | map(g.outEdges(v), function(e) {
|
2505 | return dfs2(e.w) - g.edge(e).minlen;
|
2506 | })
|
2507 | );
|
2508 | if (rank2 === Number.POSITIVE_INFINITY ||
|
2509 | rank2 === void 0 ||
|
2510 | rank2 === null) {
|
2511 | rank2 = 0;
|
2512 | }
|
2513 | return label.rank = rank2;
|
2514 | }
|
2515 | forEach(g.sources(), dfs2);
|
2516 | }
|
2517 | function slack(g, e) {
|
2518 | return g.node(e.w).rank - g.node(e.v).rank - g.edge(e).minlen;
|
2519 | }
|
2520 | function feasibleTree(g) {
|
2521 | var t = new Graph({ directed: false });
|
2522 | var start = g.nodes()[0];
|
2523 | var size = g.nodeCount();
|
2524 | t.setNode(start, {});
|
2525 | var edge, delta;
|
2526 | while (tightTree(t, g) < size) {
|
2527 | edge = findMinSlackEdge(t, g);
|
2528 | delta = t.hasNode(edge.v) ? slack(g, edge) : -slack(g, edge);
|
2529 | shiftRanks(t, g, delta);
|
2530 | }
|
2531 | return t;
|
2532 | }
|
2533 | function tightTree(t, g) {
|
2534 | function dfs2(v) {
|
2535 | forEach(g.nodeEdges(v), function(e) {
|
2536 | var edgeV = e.v, w = v === edgeV ? e.w : edgeV;
|
2537 | if (!t.hasNode(w) && !slack(g, e)) {
|
2538 | t.setNode(w, {});
|
2539 | t.setEdge(v, w, {});
|
2540 | dfs2(w);
|
2541 | }
|
2542 | });
|
2543 | }
|
2544 | forEach(t.nodes(), dfs2);
|
2545 | return t.nodeCount();
|
2546 | }
|
2547 | function findMinSlackEdge(t, g) {
|
2548 | return minBy(g.edges(), function(e) {
|
2549 | if (t.hasNode(e.v) !== t.hasNode(e.w)) {
|
2550 | return slack(g, e);
|
2551 | }
|
2552 | });
|
2553 | }
|
2554 | function shiftRanks(t, g, delta) {
|
2555 | forEach(t.nodes(), function(v) {
|
2556 | g.node(v).rank += delta;
|
2557 | });
|
2558 | }
|
2559 | function CycleException() {
|
2560 | }
|
2561 | CycleException.prototype = new Error();
|
2562 | function dfs$1(g, vs, order2) {
|
2563 | if (!isArray(vs)) {
|
2564 | vs = [vs];
|
2565 | }
|
2566 | var navigation = (g.isDirected() ? g.successors : g.neighbors).bind(g);
|
2567 | var acc = [];
|
2568 | var visited = {};
|
2569 | forEach(vs, function(v) {
|
2570 | if (!g.hasNode(v)) {
|
2571 | throw new Error("Graph does not have node: " + v);
|
2572 | }
|
2573 | doDfs(g, v, order2 === "post", visited, navigation, acc);
|
2574 | });
|
2575 | return acc;
|
2576 | }
|
2577 | function doDfs(g, v, postorder2, visited, navigation, acc) {
|
2578 | if (!has(visited, v)) {
|
2579 | visited[v] = true;
|
2580 | if (!postorder2) {
|
2581 | acc.push(v);
|
2582 | }
|
2583 | forEach(navigation(v), function(w) {
|
2584 | doDfs(g, w, postorder2, visited, navigation, acc);
|
2585 | });
|
2586 | if (postorder2) {
|
2587 | acc.push(v);
|
2588 | }
|
2589 | }
|
2590 | }
|
2591 | function postorder$1(g, vs) {
|
2592 | return dfs$1(g, vs, "post");
|
2593 | }
|
2594 | function preorder(g, vs) {
|
2595 | return dfs$1(g, vs, "pre");
|
2596 | }
|
2597 | networkSimplex.initLowLimValues = initLowLimValues;
|
2598 | networkSimplex.initCutValues = initCutValues;
|
2599 | networkSimplex.calcCutValue = calcCutValue;
|
2600 | networkSimplex.leaveEdge = leaveEdge;
|
2601 | networkSimplex.enterEdge = enterEdge;
|
2602 | networkSimplex.exchangeEdges = exchangeEdges;
|
2603 | function networkSimplex(g) {
|
2604 | g = simplify(g);
|
2605 | longestPath(g);
|
2606 | var t = feasibleTree(g);
|
2607 | initLowLimValues(t);
|
2608 | initCutValues(t, g);
|
2609 | var e, f;
|
2610 | while (e = leaveEdge(t)) {
|
2611 | f = enterEdge(t, g, e);
|
2612 | exchangeEdges(t, g, e, f);
|
2613 | }
|
2614 | }
|
2615 | function initCutValues(t, g) {
|
2616 | var vs = postorder$1(t, t.nodes());
|
2617 | vs = vs.slice(0, vs.length - 1);
|
2618 | forEach(vs, function(v) {
|
2619 | assignCutValue(t, g, v);
|
2620 | });
|
2621 | }
|
2622 | function assignCutValue(t, g, child) {
|
2623 | var childLab = t.node(child);
|
2624 | var parent = childLab.parent;
|
2625 | t.edge(child, parent).cutvalue = calcCutValue(t, g, child);
|
2626 | }
|
2627 | function calcCutValue(t, g, child) {
|
2628 | var childLab = t.node(child);
|
2629 | var parent = childLab.parent;
|
2630 | var childIsTail = true;
|
2631 | var graphEdge = g.edge(child, parent);
|
2632 | var cutValue = 0;
|
2633 | if (!graphEdge) {
|
2634 | childIsTail = false;
|
2635 | graphEdge = g.edge(parent, child);
|
2636 | }
|
2637 | cutValue = graphEdge.weight;
|
2638 | forEach(g.nodeEdges(child), function(e) {
|
2639 | var isOutEdge = e.v === child, other = isOutEdge ? e.w : e.v;
|
2640 | if (other !== parent) {
|
2641 | var pointsToHead = isOutEdge === childIsTail, otherWeight = g.edge(e).weight;
|
2642 | cutValue += pointsToHead ? otherWeight : -otherWeight;
|
2643 | if (isTreeEdge(t, child, other)) {
|
2644 | var otherCutValue = t.edge(child, other).cutvalue;
|
2645 | cutValue += pointsToHead ? -otherCutValue : otherCutValue;
|
2646 | }
|
2647 | }
|
2648 | });
|
2649 | return cutValue;
|
2650 | }
|
2651 | function initLowLimValues(tree, root2) {
|
2652 | if (arguments.length < 2) {
|
2653 | root2 = tree.nodes()[0];
|
2654 | }
|
2655 | dfsAssignLowLim(tree, {}, 1, root2);
|
2656 | }
|
2657 | function dfsAssignLowLim(tree, visited, nextLim, v, parent) {
|
2658 | var low = nextLim;
|
2659 | var label = tree.node(v);
|
2660 | visited[v] = true;
|
2661 | forEach(tree.neighbors(v), function(w) {
|
2662 | if (!has(visited, w)) {
|
2663 | nextLim = dfsAssignLowLim(tree, visited, nextLim, w, v);
|
2664 | }
|
2665 | });
|
2666 | label.low = low;
|
2667 | label.lim = nextLim++;
|
2668 | if (parent) {
|
2669 | label.parent = parent;
|
2670 | } else {
|
2671 | delete label.parent;
|
2672 | }
|
2673 | return nextLim;
|
2674 | }
|
2675 | function leaveEdge(tree) {
|
2676 | return find$1(tree.edges(), function(e) {
|
2677 | return tree.edge(e).cutvalue < 0;
|
2678 | });
|
2679 | }
|
2680 | function enterEdge(t, g, edge) {
|
2681 | var v = edge.v;
|
2682 | var w = edge.w;
|
2683 | if (!g.hasEdge(v, w)) {
|
2684 | v = edge.w;
|
2685 | w = edge.v;
|
2686 | }
|
2687 | var vLabel = t.node(v);
|
2688 | var wLabel = t.node(w);
|
2689 | var tailLabel = vLabel;
|
2690 | var flip = false;
|
2691 | if (vLabel.lim > wLabel.lim) {
|
2692 | tailLabel = wLabel;
|
2693 | flip = true;
|
2694 | }
|
2695 | var candidates = filter(g.edges(), function(edge2) {
|
2696 | return flip === isDescendant(t, t.node(edge2.v), tailLabel) && flip !== isDescendant(t, t.node(edge2.w), tailLabel);
|
2697 | });
|
2698 | return minBy(candidates, function(edge2) {
|
2699 | return slack(g, edge2);
|
2700 | });
|
2701 | }
|
2702 | function exchangeEdges(t, g, e, f) {
|
2703 | var v = e.v;
|
2704 | var w = e.w;
|
2705 | t.removeEdge(v, w);
|
2706 | t.setEdge(f.v, f.w, {});
|
2707 | initLowLimValues(t);
|
2708 | initCutValues(t, g);
|
2709 | updateRanks(t, g);
|
2710 | }
|
2711 | function updateRanks(t, g) {
|
2712 | var root2 = find$1(t.nodes(), function(v) {
|
2713 | return !g.node(v).parent;
|
2714 | });
|
2715 | var vs = preorder(t, root2);
|
2716 | vs = vs.slice(1);
|
2717 | forEach(vs, function(v) {
|
2718 | var parent = t.node(v).parent, edge = g.edge(v, parent), flipped = false;
|
2719 | if (!edge) {
|
2720 | edge = g.edge(parent, v);
|
2721 | flipped = true;
|
2722 | }
|
2723 | g.node(v).rank = g.node(parent).rank + (flipped ? edge.minlen : -edge.minlen);
|
2724 | });
|
2725 | }
|
2726 | function isTreeEdge(tree, u, v) {
|
2727 | return tree.hasEdge(u, v);
|
2728 | }
|
2729 | function isDescendant(tree, vLabel, rootLabel) {
|
2730 | return rootLabel.low <= vLabel.lim && vLabel.lim <= rootLabel.lim;
|
2731 | }
|
2732 | function rank(g) {
|
2733 | switch (g.graph().ranker) {
|
2734 | case "network-simplex":
|
2735 | networkSimplexRanker(g);
|
2736 | break;
|
2737 | case "tight-tree":
|
2738 | tightTreeRanker(g);
|
2739 | break;
|
2740 | case "longest-path":
|
2741 | longestPathRanker(g);
|
2742 | break;
|
2743 | default:
|
2744 | networkSimplexRanker(g);
|
2745 | }
|
2746 | }
|
2747 | var longestPathRanker = longestPath;
|
2748 | function tightTreeRanker(g) {
|
2749 | longestPath(g);
|
2750 | feasibleTree(g);
|
2751 | }
|
2752 | function networkSimplexRanker(g) {
|
2753 | networkSimplex(g);
|
2754 | }
|
2755 | function run(g) {
|
2756 | var root2 = addDummyNode(g, "root", {}, "_root");
|
2757 | var depths = treeDepths(g);
|
2758 | var height = max(values(depths)) - 1;
|
2759 | var nodeSep = 2 * height + 1;
|
2760 | g.graph().nestingRoot = root2;
|
2761 | forEach(g.edges(), function(e) {
|
2762 | g.edge(e).minlen *= nodeSep;
|
2763 | });
|
2764 | var weight = sumWeights(g) + 1;
|
2765 | forEach(g.children(), function(child) {
|
2766 | dfs(g, root2, nodeSep, weight, height, depths, child);
|
2767 | });
|
2768 | g.graph().nodeRankFactor = nodeSep;
|
2769 | }
|
2770 | function dfs(g, root2, nodeSep, weight, height, depths, v) {
|
2771 | var children = g.children(v);
|
2772 | if (!children.length) {
|
2773 | if (v !== root2) {
|
2774 | g.setEdge(root2, v, { weight: 0, minlen: nodeSep });
|
2775 | }
|
2776 | return;
|
2777 | }
|
2778 | var top = addBorderNode$1(g, "_bt");
|
2779 | var bottom = addBorderNode$1(g, "_bb");
|
2780 | var label = g.node(v);
|
2781 | g.setParent(top, v);
|
2782 | label.borderTop = top;
|
2783 | g.setParent(bottom, v);
|
2784 | label.borderBottom = bottom;
|
2785 | forEach(children, function(child) {
|
2786 | dfs(g, root2, nodeSep, weight, height, depths, child);
|
2787 | var childNode = g.node(child);
|
2788 | var childTop = childNode.borderTop ? childNode.borderTop : child;
|
2789 | var childBottom = childNode.borderBottom ? childNode.borderBottom : child;
|
2790 | var thisWeight = childNode.borderTop ? weight : 2 * weight;
|
2791 | var minlen = childTop !== childBottom ? 1 : height - depths[v] + 1;
|
2792 | g.setEdge(top, childTop, {
|
2793 | weight: thisWeight,
|
2794 | minlen,
|
2795 | nestingEdge: true
|
2796 | });
|
2797 | g.setEdge(childBottom, bottom, {
|
2798 | weight: thisWeight,
|
2799 | minlen,
|
2800 | nestingEdge: true
|
2801 | });
|
2802 | });
|
2803 | if (!g.parent(v)) {
|
2804 | g.setEdge(root2, top, { weight: 0, minlen: height + depths[v] });
|
2805 | }
|
2806 | }
|
2807 | function treeDepths(g) {
|
2808 | var depths = {};
|
2809 | function dfs2(v, depth) {
|
2810 | var children = g.children(v);
|
2811 | if (children && children.length) {
|
2812 | forEach(children, function(child) {
|
2813 | dfs2(child, depth + 1);
|
2814 | });
|
2815 | }
|
2816 | depths[v] = depth;
|
2817 | }
|
2818 | forEach(g.children(), function(v) {
|
2819 | dfs2(v, 1);
|
2820 | });
|
2821 | return depths;
|
2822 | }
|
2823 | function sumWeights(g) {
|
2824 | return reduce(
|
2825 | g.edges(),
|
2826 | function(acc, e) {
|
2827 | return acc + g.edge(e).weight;
|
2828 | },
|
2829 | 0
|
2830 | );
|
2831 | }
|
2832 | function cleanup(g) {
|
2833 | var graphLabel = g.graph();
|
2834 | g.removeNode(graphLabel.nestingRoot);
|
2835 | delete graphLabel.nestingRoot;
|
2836 | forEach(g.edges(), function(e) {
|
2837 | var edge = g.edge(e);
|
2838 | if (edge.nestingEdge) {
|
2839 | g.removeEdge(e);
|
2840 | }
|
2841 | });
|
2842 | }
|
2843 | function addSubgraphConstraints(g, cg, vs) {
|
2844 | var prev = {}, rootPrev;
|
2845 | forEach(vs, function(v) {
|
2846 | var child = g.parent(v), parent, prevChild;
|
2847 | while (child) {
|
2848 | parent = g.parent(child);
|
2849 | if (parent) {
|
2850 | prevChild = prev[parent];
|
2851 | prev[parent] = child;
|
2852 | } else {
|
2853 | prevChild = rootPrev;
|
2854 | rootPrev = child;
|
2855 | }
|
2856 | if (prevChild && prevChild !== child) {
|
2857 | cg.setEdge(prevChild, child);
|
2858 | return;
|
2859 | }
|
2860 | child = parent;
|
2861 | }
|
2862 | });
|
2863 | }
|
2864 | function buildLayerGraph(g, rank2, relationship) {
|
2865 | var root2 = createRootNode(g), result = new Graph({ compound: true }).setGraph({ root: root2 }).setDefaultNodeLabel(function(v) {
|
2866 | return g.node(v);
|
2867 | });
|
2868 | forEach(g.nodes(), function(v) {
|
2869 | var node = g.node(v), parent = g.parent(v);
|
2870 | if (node.rank === rank2 || node.minRank <= rank2 && rank2 <= node.maxRank) {
|
2871 | result.setNode(v);
|
2872 | result.setParent(v, parent || root2);
|
2873 | forEach(g[relationship](v), function(e) {
|
2874 | var u = e.v === v ? e.w : e.v, edge = result.edge(u, v), weight = !isUndefined(edge) ? edge.weight : 0;
|
2875 | result.setEdge(u, v, { weight: g.edge(e).weight + weight });
|
2876 | });
|
2877 | if (has(node, "minRank")) {
|
2878 | result.setNode(v, {
|
2879 | borderLeft: node.borderLeft[rank2],
|
2880 | borderRight: node.borderRight[rank2]
|
2881 | });
|
2882 | }
|
2883 | }
|
2884 | });
|
2885 | return result;
|
2886 | }
|
2887 | function createRootNode(g) {
|
2888 | var v;
|
2889 | while (g.hasNode(v = uniqueId("_root")))
|
2890 | ;
|
2891 | return v;
|
2892 | }
|
2893 | function crossCount(g, layering) {
|
2894 | var cc = 0;
|
2895 | for (var i = 1; i < layering.length; ++i) {
|
2896 | cc += twoLayerCrossCount(g, layering[i - 1], layering[i]);
|
2897 | }
|
2898 | return cc;
|
2899 | }
|
2900 | function twoLayerCrossCount(g, northLayer, southLayer) {
|
2901 | var southPos = zipObject(
|
2902 | southLayer,
|
2903 | map(southLayer, function(v, i) {
|
2904 | return i;
|
2905 | })
|
2906 | );
|
2907 | var southEntries = flatten(
|
2908 | map(northLayer, function(v) {
|
2909 | return sortBy$1(
|
2910 | map(g.outEdges(v), function(e) {
|
2911 | return { pos: southPos[e.w], weight: g.edge(e).weight };
|
2912 | }),
|
2913 | "pos"
|
2914 | );
|
2915 | })
|
2916 | );
|
2917 | var firstIndex = 1;
|
2918 | while (firstIndex < southLayer.length)
|
2919 | firstIndex <<= 1;
|
2920 | var treeSize = 2 * firstIndex - 1;
|
2921 | firstIndex -= 1;
|
2922 | var tree = map(new Array(treeSize), function() {
|
2923 | return 0;
|
2924 | });
|
2925 | var cc = 0;
|
2926 | forEach(
|
2927 |
|
2928 | southEntries.forEach(function(entry) {
|
2929 | var index = entry.pos + firstIndex;
|
2930 | tree[index] += entry.weight;
|
2931 | var weightSum = 0;
|
2932 | while (index > 0) {
|
2933 | if (index % 2) {
|
2934 | weightSum += tree[index + 1];
|
2935 | }
|
2936 | index = index - 1 >> 1;
|
2937 | tree[index] += entry.weight;
|
2938 | }
|
2939 | cc += entry.weight * weightSum;
|
2940 | })
|
2941 | );
|
2942 | return cc;
|
2943 | }
|
2944 | function initOrder(g) {
|
2945 | var visited = {};
|
2946 | var simpleNodes = filter(g.nodes(), function(v) {
|
2947 | return !g.children(v).length;
|
2948 | });
|
2949 | var maxRank2 = max(
|
2950 | map(simpleNodes, function(v) {
|
2951 | return g.node(v).rank;
|
2952 | })
|
2953 | );
|
2954 | var layers = map(range$1(maxRank2 + 1), function() {
|
2955 | return [];
|
2956 | });
|
2957 | function dfs2(v) {
|
2958 | if (has(visited, v))
|
2959 | return;
|
2960 | visited[v] = true;
|
2961 | var node = g.node(v);
|
2962 | layers[node.rank].push(v);
|
2963 | forEach(g.successors(v), dfs2);
|
2964 | }
|
2965 | var orderedVs = sortBy$1(simpleNodes, function(v) {
|
2966 | return g.node(v).rank;
|
2967 | });
|
2968 | forEach(orderedVs, dfs2);
|
2969 | return layers;
|
2970 | }
|
2971 | function barycenter(g, movable) {
|
2972 | return map(movable, function(v) {
|
2973 | var inV = g.inEdges(v);
|
2974 | if (!inV.length) {
|
2975 | return { v };
|
2976 | } else {
|
2977 | var result = reduce(
|
2978 | inV,
|
2979 | function(acc, e) {
|
2980 | var edge = g.edge(e), nodeU = g.node(e.v);
|
2981 | return {
|
2982 | sum: acc.sum + edge.weight * nodeU.order,
|
2983 | weight: acc.weight + edge.weight
|
2984 | };
|
2985 | },
|
2986 | { sum: 0, weight: 0 }
|
2987 | );
|
2988 | return {
|
2989 | v,
|
2990 | barycenter: result.sum / result.weight,
|
2991 | weight: result.weight
|
2992 | };
|
2993 | }
|
2994 | });
|
2995 | }
|
2996 | function resolveConflicts(entries, cg) {
|
2997 | var mappedEntries = {};
|
2998 | forEach(entries, function(entry, i) {
|
2999 | var tmp = mappedEntries[entry.v] = {
|
3000 | indegree: 0,
|
3001 | in: [],
|
3002 | out: [],
|
3003 | vs: [entry.v],
|
3004 | i
|
3005 | };
|
3006 | if (!isUndefined(entry.barycenter)) {
|
3007 | tmp.barycenter = entry.barycenter;
|
3008 | tmp.weight = entry.weight;
|
3009 | }
|
3010 | });
|
3011 | forEach(cg.edges(), function(e) {
|
3012 | var entryV = mappedEntries[e.v];
|
3013 | var entryW = mappedEntries[e.w];
|
3014 | if (!isUndefined(entryV) && !isUndefined(entryW)) {
|
3015 | entryW.indegree++;
|
3016 | entryV.out.push(mappedEntries[e.w]);
|
3017 | }
|
3018 | });
|
3019 | var sourceSet = filter(mappedEntries, function(entry) {
|
3020 | return !entry.indegree;
|
3021 | });
|
3022 | return doResolveConflicts(sourceSet);
|
3023 | }
|
3024 | function doResolveConflicts(sourceSet) {
|
3025 | var entries = [];
|
3026 | function handleIn(vEntry) {
|
3027 | return function(uEntry) {
|
3028 | if (uEntry.merged) {
|
3029 | return;
|
3030 | }
|
3031 | if (isUndefined(uEntry.barycenter) || isUndefined(vEntry.barycenter) || uEntry.barycenter >= vEntry.barycenter) {
|
3032 | mergeEntries(vEntry, uEntry);
|
3033 | }
|
3034 | };
|
3035 | }
|
3036 | function handleOut(vEntry) {
|
3037 | return function(wEntry) {
|
3038 | wEntry["in"].push(vEntry);
|
3039 | if (--wEntry.indegree === 0) {
|
3040 | sourceSet.push(wEntry);
|
3041 | }
|
3042 | };
|
3043 | }
|
3044 | while (sourceSet.length) {
|
3045 | var entry = sourceSet.pop();
|
3046 | entries.push(entry);
|
3047 | forEach(entry["in"].reverse(), handleIn(entry));
|
3048 | forEach(entry.out, handleOut(entry));
|
3049 | }
|
3050 | return map(
|
3051 | filter(entries, function(entry2) {
|
3052 | return !entry2.merged;
|
3053 | }),
|
3054 | function(entry2) {
|
3055 | return pick$1(entry2, ["vs", "i", "barycenter", "weight"]);
|
3056 | }
|
3057 | );
|
3058 | }
|
3059 | function mergeEntries(target, source) {
|
3060 | var sum = 0;
|
3061 | var weight = 0;
|
3062 | if (target.weight) {
|
3063 | sum += target.barycenter * target.weight;
|
3064 | weight += target.weight;
|
3065 | }
|
3066 | if (source.weight) {
|
3067 | sum += source.barycenter * source.weight;
|
3068 | weight += source.weight;
|
3069 | }
|
3070 | target.vs = source.vs.concat(target.vs);
|
3071 | target.barycenter = sum / weight;
|
3072 | target.weight = weight;
|
3073 | target.i = Math.min(source.i, target.i);
|
3074 | source.merged = true;
|
3075 | }
|
3076 | function sort(entries, biasRight) {
|
3077 | var parts = partition(entries, function(entry) {
|
3078 | return has(entry, "barycenter");
|
3079 | });
|
3080 | var sortable = parts.lhs, unsortable = sortBy$1(parts.rhs, function(entry) {
|
3081 | return -entry.i;
|
3082 | }), vs = [], sum = 0, weight = 0, vsIndex = 0;
|
3083 | sortable.sort(compareWithBias(!!biasRight));
|
3084 | vsIndex = consumeUnsortable(vs, unsortable, vsIndex);
|
3085 | forEach(sortable, function(entry) {
|
3086 | vsIndex += entry.vs.length;
|
3087 | vs.push(entry.vs);
|
3088 | sum += entry.barycenter * entry.weight;
|
3089 | weight += entry.weight;
|
3090 | vsIndex = consumeUnsortable(vs, unsortable, vsIndex);
|
3091 | });
|
3092 | var result = { vs: flatten(vs) };
|
3093 | if (weight) {
|
3094 | result.barycenter = sum / weight;
|
3095 | result.weight = weight;
|
3096 | }
|
3097 | return result;
|
3098 | }
|
3099 | function consumeUnsortable(vs, unsortable, index) {
|
3100 | var last$1;
|
3101 | while (unsortable.length && (last$1 = last(unsortable)).i <= index) {
|
3102 | unsortable.pop();
|
3103 | vs.push(last$1.vs);
|
3104 | index++;
|
3105 | }
|
3106 | return index;
|
3107 | }
|
3108 | function compareWithBias(bias) {
|
3109 | return function(entryV, entryW) {
|
3110 | if (entryV.barycenter < entryW.barycenter) {
|
3111 | return -1;
|
3112 | } else if (entryV.barycenter > entryW.barycenter) {
|
3113 | return 1;
|
3114 | }
|
3115 | return !bias ? entryV.i - entryW.i : entryW.i - entryV.i;
|
3116 | };
|
3117 | }
|
3118 | function sortSubgraph(g, v, cg, biasRight) {
|
3119 | var movable = g.children(v);
|
3120 | var node = g.node(v);
|
3121 | var bl = node ? node.borderLeft : void 0;
|
3122 | var br = node ? node.borderRight : void 0;
|
3123 | var subgraphs = {};
|
3124 | if (bl) {
|
3125 | movable = filter(movable, function(w) {
|
3126 | return w !== bl && w !== br;
|
3127 | });
|
3128 | }
|
3129 | var barycenters = barycenter(g, movable);
|
3130 | forEach(barycenters, function(entry) {
|
3131 | if (g.children(entry.v).length) {
|
3132 | var subgraphResult = sortSubgraph(g, entry.v, cg, biasRight);
|
3133 | subgraphs[entry.v] = subgraphResult;
|
3134 | if (has(subgraphResult, "barycenter")) {
|
3135 | mergeBarycenters(entry, subgraphResult);
|
3136 | }
|
3137 | }
|
3138 | });
|
3139 | var entries = resolveConflicts(barycenters, cg);
|
3140 | expandSubgraphs(entries, subgraphs);
|
3141 | var result = sort(entries, biasRight);
|
3142 | if (bl) {
|
3143 | result.vs = flatten([bl, result.vs, br]);
|
3144 | if (g.predecessors(bl).length) {
|
3145 | var blPred = g.node(g.predecessors(bl)[0]), brPred = g.node(g.predecessors(br)[0]);
|
3146 | if (!has(result, "barycenter")) {
|
3147 | result.barycenter = 0;
|
3148 | result.weight = 0;
|
3149 | }
|
3150 | result.barycenter = (result.barycenter * result.weight + blPred.order + brPred.order) / (result.weight + 2);
|
3151 | result.weight += 2;
|
3152 | }
|
3153 | }
|
3154 | return result;
|
3155 | }
|
3156 | function expandSubgraphs(entries, subgraphs) {
|
3157 | forEach(entries, function(entry) {
|
3158 | entry.vs = flatten(
|
3159 | entry.vs.map(function(v) {
|
3160 | if (subgraphs[v]) {
|
3161 | return subgraphs[v].vs;
|
3162 | }
|
3163 | return v;
|
3164 | })
|
3165 | );
|
3166 | });
|
3167 | }
|
3168 | function mergeBarycenters(target, other) {
|
3169 | if (!isUndefined(target.barycenter)) {
|
3170 | target.barycenter = (target.barycenter * target.weight + other.barycenter * other.weight) / (target.weight + other.weight);
|
3171 | target.weight += other.weight;
|
3172 | } else {
|
3173 | target.barycenter = other.barycenter;
|
3174 | target.weight = other.weight;
|
3175 | }
|
3176 | }
|
3177 | function order(g) {
|
3178 | var maxRank$1 = maxRank(g), downLayerGraphs = buildLayerGraphs(g, range$1(1, maxRank$1 + 1), "inEdges"), upLayerGraphs = buildLayerGraphs(g, range$1(maxRank$1 - 1, -1, -1), "outEdges");
|
3179 | var layering = initOrder(g);
|
3180 | assignOrder(g, layering);
|
3181 | var bestCC = Number.POSITIVE_INFINITY, best;
|
3182 | for (var i = 0, lastBest = 0; lastBest < 4; ++i, ++lastBest) {
|
3183 | sweepLayerGraphs(i % 2 ? downLayerGraphs : upLayerGraphs, i % 4 >= 2);
|
3184 | layering = buildLayerMatrix(g);
|
3185 | var cc = crossCount(g, layering);
|
3186 | if (cc < bestCC) {
|
3187 | lastBest = 0;
|
3188 | best = cloneDeep(layering);
|
3189 | bestCC = cc;
|
3190 | }
|
3191 | }
|
3192 | assignOrder(g, best);
|
3193 | }
|
3194 | function buildLayerGraphs(g, ranks, relationship) {
|
3195 | return map(ranks, function(rank2) {
|
3196 | return buildLayerGraph(g, rank2, relationship);
|
3197 | });
|
3198 | }
|
3199 | function sweepLayerGraphs(layerGraphs, biasRight) {
|
3200 | var cg = new Graph();
|
3201 | forEach(layerGraphs, function(lg) {
|
3202 | var root2 = lg.graph().root;
|
3203 | var sorted = sortSubgraph(lg, root2, cg, biasRight);
|
3204 | forEach(sorted.vs, function(v, i) {
|
3205 | lg.node(v).order = i;
|
3206 | });
|
3207 | addSubgraphConstraints(lg, cg, sorted.vs);
|
3208 | });
|
3209 | }
|
3210 | function assignOrder(g, layering) {
|
3211 | forEach(layering, function(layer) {
|
3212 | forEach(layer, function(v, i) {
|
3213 | g.node(v).order = i;
|
3214 | });
|
3215 | });
|
3216 | }
|
3217 | function parentDummyChains(g) {
|
3218 | var postorderNums = postorder(g);
|
3219 | forEach(g.graph().dummyChains, function(v) {
|
3220 | var node = g.node(v);
|
3221 | var edgeObj = node.edgeObj;
|
3222 | var pathData = findPath(g, postorderNums, edgeObj.v, edgeObj.w);
|
3223 | var path = pathData.path;
|
3224 | var lca = pathData.lca;
|
3225 | var pathIdx = 0;
|
3226 | var pathV = path[pathIdx];
|
3227 | var ascending = true;
|
3228 | while (v !== edgeObj.w) {
|
3229 | node = g.node(v);
|
3230 | if (ascending) {
|
3231 | while ((pathV = path[pathIdx]) !== lca && g.node(pathV).maxRank < node.rank) {
|
3232 | pathIdx++;
|
3233 | }
|
3234 | if (pathV === lca) {
|
3235 | ascending = false;
|
3236 | }
|
3237 | }
|
3238 | if (!ascending) {
|
3239 | while (pathIdx < path.length - 1 && g.node(pathV = path[pathIdx + 1]).minRank <= node.rank) {
|
3240 | pathIdx++;
|
3241 | }
|
3242 | pathV = path[pathIdx];
|
3243 | }
|
3244 | g.setParent(v, pathV);
|
3245 | v = g.successors(v)[0];
|
3246 | }
|
3247 | });
|
3248 | }
|
3249 | function findPath(g, postorderNums, v, w) {
|
3250 | var vPath = [];
|
3251 | var wPath = [];
|
3252 | var low = Math.min(postorderNums[v].low, postorderNums[w].low);
|
3253 | var lim = Math.max(postorderNums[v].lim, postorderNums[w].lim);
|
3254 | var parent;
|
3255 | var lca;
|
3256 | parent = v;
|
3257 | do {
|
3258 | parent = g.parent(parent);
|
3259 | vPath.push(parent);
|
3260 | } while (parent && (postorderNums[parent].low > low || lim > postorderNums[parent].lim));
|
3261 | lca = parent;
|
3262 | parent = w;
|
3263 | while ((parent = g.parent(parent)) !== lca) {
|
3264 | wPath.push(parent);
|
3265 | }
|
3266 | return { path: vPath.concat(wPath.reverse()), lca };
|
3267 | }
|
3268 | function postorder(g) {
|
3269 | var result = {};
|
3270 | var lim = 0;
|
3271 | function dfs2(v) {
|
3272 | var low = lim;
|
3273 | forEach(g.children(v), dfs2);
|
3274 | result[v] = { low, lim: lim++ };
|
3275 | }
|
3276 | forEach(g.children(), dfs2);
|
3277 | return result;
|
3278 | }
|
3279 | function findType1Conflicts(g, layering) {
|
3280 | var conflicts = {};
|
3281 | function visitLayer(prevLayer, layer) {
|
3282 | var k0 = 0, scanPos = 0, prevLayerLength = prevLayer.length, lastNode = last(layer);
|
3283 | forEach(layer, function(v, i) {
|
3284 | var w = findOtherInnerSegmentNode(g, v), k1 = w ? g.node(w).order : prevLayerLength;
|
3285 | if (w || v === lastNode) {
|
3286 | forEach(layer.slice(scanPos, i + 1), function(scanNode) {
|
3287 | forEach(g.predecessors(scanNode), function(u) {
|
3288 | var uLabel = g.node(u), uPos = uLabel.order;
|
3289 | if ((uPos < k0 || k1 < uPos) && !(uLabel.dummy && g.node(scanNode).dummy)) {
|
3290 | addConflict(conflicts, u, scanNode);
|
3291 | }
|
3292 | });
|
3293 | });
|
3294 | scanPos = i + 1;
|
3295 | k0 = k1;
|
3296 | }
|
3297 | });
|
3298 | return layer;
|
3299 | }
|
3300 | reduce(layering, visitLayer);
|
3301 | return conflicts;
|
3302 | }
|
3303 | function findType2Conflicts(g, layering) {
|
3304 | var conflicts = {};
|
3305 | function scan(south, southPos, southEnd, prevNorthBorder, nextNorthBorder) {
|
3306 | var v;
|
3307 | forEach(range$1(southPos, southEnd), function(i) {
|
3308 | v = south[i];
|
3309 | if (g.node(v).dummy) {
|
3310 | forEach(g.predecessors(v), function(u) {
|
3311 | var uNode = g.node(u);
|
3312 | if (uNode.dummy && (uNode.order < prevNorthBorder || uNode.order > nextNorthBorder)) {
|
3313 | addConflict(conflicts, u, v);
|
3314 | }
|
3315 | });
|
3316 | }
|
3317 | });
|
3318 | }
|
3319 | function visitLayer(north, south) {
|
3320 | var prevNorthPos = -1, nextNorthPos, southPos = 0;
|
3321 | forEach(south, function(v, southLookahead) {
|
3322 | if (g.node(v).dummy === "border") {
|
3323 | var predecessors = g.predecessors(v);
|
3324 | if (predecessors.length) {
|
3325 | nextNorthPos = g.node(predecessors[0]).order;
|
3326 | scan(south, southPos, southLookahead, prevNorthPos, nextNorthPos);
|
3327 | southPos = southLookahead;
|
3328 | prevNorthPos = nextNorthPos;
|
3329 | }
|
3330 | }
|
3331 | scan(south, southPos, south.length, nextNorthPos, north.length);
|
3332 | });
|
3333 | return south;
|
3334 | }
|
3335 | reduce(layering, visitLayer);
|
3336 | return conflicts;
|
3337 | }
|
3338 | function findOtherInnerSegmentNode(g, v) {
|
3339 | if (g.node(v).dummy) {
|
3340 | return find$1(g.predecessors(v), function(u) {
|
3341 | return g.node(u).dummy;
|
3342 | });
|
3343 | }
|
3344 | }
|
3345 | function addConflict(conflicts, v, w) {
|
3346 | if (v > w) {
|
3347 | var tmp = v;
|
3348 | v = w;
|
3349 | w = tmp;
|
3350 | }
|
3351 | var conflictsV = conflicts[v];
|
3352 | if (!conflictsV) {
|
3353 | conflicts[v] = conflictsV = {};
|
3354 | }
|
3355 | conflictsV[w] = true;
|
3356 | }
|
3357 | function hasConflict(conflicts, v, w) {
|
3358 | if (v > w) {
|
3359 | var tmp = v;
|
3360 | v = w;
|
3361 | w = tmp;
|
3362 | }
|
3363 | return has(conflicts[v], w);
|
3364 | }
|
3365 | function verticalAlignment(g, layering, conflicts, neighborFn) {
|
3366 | var root2 = {}, align = {}, pos = {};
|
3367 | forEach(layering, function(layer) {
|
3368 | forEach(layer, function(v, order2) {
|
3369 | root2[v] = v;
|
3370 | align[v] = v;
|
3371 | pos[v] = order2;
|
3372 | });
|
3373 | });
|
3374 | forEach(layering, function(layer) {
|
3375 | var prevIdx = -1;
|
3376 | forEach(layer, function(v) {
|
3377 | var ws = neighborFn(v);
|
3378 | if (ws.length) {
|
3379 | ws = sortBy$1(ws, function(w2) {
|
3380 | return pos[w2];
|
3381 | });
|
3382 | var mp = (ws.length - 1) / 2;
|
3383 | for (var i = Math.floor(mp), il = Math.ceil(mp); i <= il; ++i) {
|
3384 | var w = ws[i];
|
3385 | if (align[v] === v && prevIdx < pos[w] && !hasConflict(conflicts, v, w)) {
|
3386 | align[w] = v;
|
3387 | align[v] = root2[v] = root2[w];
|
3388 | prevIdx = pos[w];
|
3389 | }
|
3390 | }
|
3391 | }
|
3392 | });
|
3393 | });
|
3394 | return { root: root2, align };
|
3395 | }
|
3396 | function horizontalCompaction(g, layering, root2, align, reverseSep) {
|
3397 | var xs = {}, blockG = buildBlockGraph(g, layering, root2, reverseSep), borderType = reverseSep ? "borderLeft" : "borderRight";
|
3398 | function iterate(setXsFunc, nextNodesFunc) {
|
3399 | var stack = blockG.nodes();
|
3400 | var elem = stack.pop();
|
3401 | var visited = {};
|
3402 | while (elem) {
|
3403 | if (visited[elem]) {
|
3404 | setXsFunc(elem);
|
3405 | } else {
|
3406 | visited[elem] = true;
|
3407 | stack.push(elem);
|
3408 | stack = stack.concat(nextNodesFunc(elem));
|
3409 | }
|
3410 | elem = stack.pop();
|
3411 | }
|
3412 | }
|
3413 | function pass1(elem) {
|
3414 | xs[elem] = blockG.inEdges(elem).reduce(function(acc, e) {
|
3415 | return Math.max(acc, xs[e.v] + blockG.edge(e));
|
3416 | }, 0);
|
3417 | }
|
3418 | function pass2(elem) {
|
3419 | var min2 = blockG.outEdges(elem).reduce(function(acc, e) {
|
3420 | return Math.min(acc, xs[e.w] - blockG.edge(e));
|
3421 | }, Number.POSITIVE_INFINITY);
|
3422 | var node = g.node(elem);
|
3423 | if (min2 !== Number.POSITIVE_INFINITY && node.borderType !== borderType) {
|
3424 | xs[elem] = Math.max(xs[elem], min2);
|
3425 | }
|
3426 | }
|
3427 | iterate(pass1, blockG.predecessors.bind(blockG));
|
3428 | iterate(pass2, blockG.successors.bind(blockG));
|
3429 | forEach(align, function(v) {
|
3430 | xs[v] = xs[root2[v]];
|
3431 | });
|
3432 | return xs;
|
3433 | }
|
3434 | function buildBlockGraph(g, layering, root2, reverseSep) {
|
3435 | var blockGraph = new Graph(), graphLabel = g.graph(), sepFn = sep(graphLabel.nodesep, graphLabel.edgesep, reverseSep);
|
3436 | forEach(layering, function(layer) {
|
3437 | var u;
|
3438 | forEach(layer, function(v) {
|
3439 | var vRoot = root2[v];
|
3440 | blockGraph.setNode(vRoot);
|
3441 | if (u) {
|
3442 | var uRoot = root2[u], prevMax = blockGraph.edge(uRoot, vRoot);
|
3443 | blockGraph.setEdge(uRoot, vRoot, Math.max(sepFn(g, v, u), prevMax || 0));
|
3444 | }
|
3445 | u = v;
|
3446 | });
|
3447 | });
|
3448 | return blockGraph;
|
3449 | }
|
3450 | function findSmallestWidthAlignment(g, xss) {
|
3451 | return minBy(values(xss), function(xs) {
|
3452 | var max2 = Number.NEGATIVE_INFINITY;
|
3453 | var min2 = Number.POSITIVE_INFINITY;
|
3454 | forIn(xs, function(x, v) {
|
3455 | var halfWidth = width(g, v) / 2;
|
3456 | max2 = Math.max(x + halfWidth, max2);
|
3457 | min2 = Math.min(x - halfWidth, min2);
|
3458 | });
|
3459 | return max2 - min2;
|
3460 | });
|
3461 | }
|
3462 | function alignCoordinates(xss, alignTo) {
|
3463 | var alignToVals = values(alignTo), alignToMin = min(alignToVals), alignToMax = max(alignToVals);
|
3464 | forEach(["u", "d"], function(vert) {
|
3465 | forEach(["l", "r"], function(horiz) {
|
3466 | var alignment = vert + horiz, xs = xss[alignment], delta;
|
3467 | if (xs === alignTo)
|
3468 | return;
|
3469 | var xsVals = values(xs);
|
3470 | delta = horiz === "l" ? alignToMin - min(xsVals) : alignToMax - max(xsVals);
|
3471 | if (delta) {
|
3472 | xss[alignment] = mapValues(xs, function(x) {
|
3473 | return x + delta;
|
3474 | });
|
3475 | }
|
3476 | });
|
3477 | });
|
3478 | }
|
3479 | function balance(xss, align) {
|
3480 | return mapValues(xss.ul, function(ignore, v) {
|
3481 | if (align) {
|
3482 | return xss[align.toLowerCase()][v];
|
3483 | } else {
|
3484 | var xs = sortBy$1(map(xss, v));
|
3485 | return (xs[1] + xs[2]) / 2;
|
3486 | }
|
3487 | });
|
3488 | }
|
3489 | function positionX(g) {
|
3490 | var layering = buildLayerMatrix(g);
|
3491 | var conflicts = merge$1(findType1Conflicts(g, layering), findType2Conflicts(g, layering));
|
3492 | var xss = {};
|
3493 | var adjustedLayering;
|
3494 | forEach(["u", "d"], function(vert) {
|
3495 | adjustedLayering = vert === "u" ? layering : values(layering).reverse();
|
3496 | forEach(["l", "r"], function(horiz) {
|
3497 | if (horiz === "r") {
|
3498 | adjustedLayering = map(adjustedLayering, function(inner) {
|
3499 | return values(inner).reverse();
|
3500 | });
|
3501 | }
|
3502 | var neighborFn = (vert === "u" ? g.predecessors : g.successors).bind(g);
|
3503 | var align = verticalAlignment(g, adjustedLayering, conflicts, neighborFn);
|
3504 | var xs = horizontalCompaction(g, adjustedLayering, align.root, align.align, horiz === "r");
|
3505 | if (horiz === "r") {
|
3506 | xs = mapValues(xs, function(x) {
|
3507 | return -x;
|
3508 | });
|
3509 | }
|
3510 | xss[vert + horiz] = xs;
|
3511 | });
|
3512 | });
|
3513 | var smallestWidth = findSmallestWidthAlignment(g, xss);
|
3514 | alignCoordinates(xss, smallestWidth);
|
3515 | return balance(xss, g.graph().align);
|
3516 | }
|
3517 | function sep(nodeSep, edgeSep, reverseSep) {
|
3518 | return function(g, v, w) {
|
3519 | var vLabel = g.node(v);
|
3520 | var wLabel = g.node(w);
|
3521 | var sum = 0;
|
3522 | var delta;
|
3523 | sum += vLabel.width / 2;
|
3524 | if (has(vLabel, "labelpos")) {
|
3525 | switch (vLabel.labelpos.toLowerCase()) {
|
3526 | case "l":
|
3527 | delta = -vLabel.width / 2;
|
3528 | break;
|
3529 | case "r":
|
3530 | delta = vLabel.width / 2;
|
3531 | break;
|
3532 | }
|
3533 | }
|
3534 | if (delta) {
|
3535 | sum += reverseSep ? delta : -delta;
|
3536 | }
|
3537 | delta = 0;
|
3538 | sum += (vLabel.dummy ? edgeSep : nodeSep) / 2;
|
3539 | sum += (wLabel.dummy ? edgeSep : nodeSep) / 2;
|
3540 | sum += wLabel.width / 2;
|
3541 | if (has(wLabel, "labelpos")) {
|
3542 | switch (wLabel.labelpos.toLowerCase()) {
|
3543 | case "l":
|
3544 | delta = wLabel.width / 2;
|
3545 | break;
|
3546 | case "r":
|
3547 | delta = -wLabel.width / 2;
|
3548 | break;
|
3549 | }
|
3550 | }
|
3551 | if (delta) {
|
3552 | sum += reverseSep ? delta : -delta;
|
3553 | }
|
3554 | delta = 0;
|
3555 | return sum;
|
3556 | };
|
3557 | }
|
3558 | function width(g, v) {
|
3559 | return g.node(v).width;
|
3560 | }
|
3561 | function position(g) {
|
3562 | g = asNonCompoundGraph(g);
|
3563 | positionY(g);
|
3564 | forOwn(positionX(g), function(x, v) {
|
3565 | g.node(v).x = x;
|
3566 | });
|
3567 | }
|
3568 | function positionY(g) {
|
3569 | var layering = buildLayerMatrix(g);
|
3570 | var rankSep = g.graph().ranksep;
|
3571 | var prevY = 0;
|
3572 | forEach(layering, function(layer) {
|
3573 | var maxHeight = max(
|
3574 | map(layer, function(v) {
|
3575 | return g.node(v).height;
|
3576 | })
|
3577 | );
|
3578 | forEach(layer, function(v) {
|
3579 | g.node(v).y = prevY + maxHeight / 2;
|
3580 | });
|
3581 | prevY += maxHeight + rankSep;
|
3582 | });
|
3583 | }
|
3584 | function layout(g, opts) {
|
3585 | var time$1 = opts && opts.debugTiming ? time : notime;
|
3586 | time$1("layout", function() {
|
3587 | var layoutGraph = time$1(" buildLayoutGraph", function() {
|
3588 | return buildLayoutGraph(g);
|
3589 | });
|
3590 | time$1(" runLayout", function() {
|
3591 | runLayout(layoutGraph, time$1);
|
3592 | });
|
3593 | time$1(" updateInputGraph", function() {
|
3594 | updateInputGraph(g, layoutGraph);
|
3595 | });
|
3596 | });
|
3597 | }
|
3598 | function runLayout(g, time2) {
|
3599 | time2(" makeSpaceForEdgeLabels", function() {
|
3600 | makeSpaceForEdgeLabels(g);
|
3601 | });
|
3602 | time2(" removeSelfEdges", function() {
|
3603 | removeSelfEdges(g);
|
3604 | });
|
3605 | time2(" acyclic", function() {
|
3606 | run$2(g);
|
3607 | });
|
3608 | time2(" nestingGraph.run", function() {
|
3609 | run(g);
|
3610 | });
|
3611 | time2(" rank", function() {
|
3612 | rank(asNonCompoundGraph(g));
|
3613 | });
|
3614 | time2(" injectEdgeLabelProxies", function() {
|
3615 | injectEdgeLabelProxies(g);
|
3616 | });
|
3617 | time2(" removeEmptyRanks", function() {
|
3618 | removeEmptyRanks(g);
|
3619 | });
|
3620 | time2(" nestingGraph.cleanup", function() {
|
3621 | cleanup(g);
|
3622 | });
|
3623 | time2(" normalizeRanks", function() {
|
3624 | normalizeRanks(g);
|
3625 | });
|
3626 | time2(" assignRankMinMax", function() {
|
3627 | assignRankMinMax(g);
|
3628 | });
|
3629 | time2(" removeEdgeLabelProxies", function() {
|
3630 | removeEdgeLabelProxies(g);
|
3631 | });
|
3632 | time2(" normalize.run", function() {
|
3633 | run$1(g);
|
3634 | });
|
3635 | time2(" parentDummyChains", function() {
|
3636 | parentDummyChains(g);
|
3637 | });
|
3638 | time2(" addBorderSegments", function() {
|
3639 | addBorderSegments(g);
|
3640 | });
|
3641 | time2(" order", function() {
|
3642 | order(g);
|
3643 | });
|
3644 | time2(" insertSelfEdges", function() {
|
3645 | insertSelfEdges(g);
|
3646 | });
|
3647 | time2(" adjustCoordinateSystem", function() {
|
3648 | adjust(g);
|
3649 | });
|
3650 | time2(" position", function() {
|
3651 | position(g);
|
3652 | });
|
3653 | time2(" positionSelfEdges", function() {
|
3654 | positionSelfEdges(g);
|
3655 | });
|
3656 | time2(" removeBorderNodes", function() {
|
3657 | removeBorderNodes(g);
|
3658 | });
|
3659 | time2(" normalize.undo", function() {
|
3660 | undo(g);
|
3661 | });
|
3662 | time2(" fixupEdgeLabelCoords", function() {
|
3663 | fixupEdgeLabelCoords(g);
|
3664 | });
|
3665 | time2(" undoCoordinateSystem", function() {
|
3666 | undo$1(g);
|
3667 | });
|
3668 | time2(" translateGraph", function() {
|
3669 | translateGraph(g);
|
3670 | });
|
3671 | time2(" assignNodeIntersects", function() {
|
3672 | assignNodeIntersects(g);
|
3673 | });
|
3674 | time2(" reversePoints", function() {
|
3675 | reversePointsForReversedEdges(g);
|
3676 | });
|
3677 | time2(" acyclic.undo", function() {
|
3678 | undo$2(g);
|
3679 | });
|
3680 | }
|
3681 | function updateInputGraph(inputGraph, layoutGraph) {
|
3682 | forEach(inputGraph.nodes(), function(v) {
|
3683 | var inputLabel = inputGraph.node(v);
|
3684 | var layoutLabel = layoutGraph.node(v);
|
3685 | if (inputLabel) {
|
3686 | inputLabel.x = layoutLabel.x;
|
3687 | inputLabel.y = layoutLabel.y;
|
3688 | if (layoutGraph.children(v).length) {
|
3689 | inputLabel.width = layoutLabel.width;
|
3690 | inputLabel.height = layoutLabel.height;
|
3691 | }
|
3692 | }
|
3693 | });
|
3694 | forEach(inputGraph.edges(), function(e) {
|
3695 | var inputLabel = inputGraph.edge(e);
|
3696 | var layoutLabel = layoutGraph.edge(e);
|
3697 | inputLabel.points = layoutLabel.points;
|
3698 | if (has(layoutLabel, "x")) {
|
3699 | inputLabel.x = layoutLabel.x;
|
3700 | inputLabel.y = layoutLabel.y;
|
3701 | }
|
3702 | });
|
3703 | inputGraph.graph().width = layoutGraph.graph().width;
|
3704 | inputGraph.graph().height = layoutGraph.graph().height;
|
3705 | }
|
3706 | var graphNumAttrs = ["nodesep", "edgesep", "ranksep", "marginx", "marginy"];
|
3707 | var graphDefaults = { ranksep: 50, edgesep: 20, nodesep: 50, rankdir: "tb" };
|
3708 | var graphAttrs = ["acyclicer", "ranker", "rankdir", "align"];
|
3709 | var nodeNumAttrs = ["width", "height"];
|
3710 | var nodeDefaults = { width: 0, height: 0 };
|
3711 | var edgeNumAttrs = ["minlen", "weight", "width", "height", "labeloffset"];
|
3712 | var edgeDefaults = {
|
3713 | minlen: 1,
|
3714 | weight: 1,
|
3715 | width: 0,
|
3716 | height: 0,
|
3717 | labeloffset: 10,
|
3718 | labelpos: "r"
|
3719 | };
|
3720 | var edgeAttrs = ["labelpos"];
|
3721 | function buildLayoutGraph(inputGraph) {
|
3722 | var g = new Graph({ multigraph: true, compound: true });
|
3723 | var graph = canonicalize(inputGraph.graph());
|
3724 | g.setGraph(
|
3725 | merge$1({}, graphDefaults, selectNumberAttrs(graph, graphNumAttrs), pick$1(graph, graphAttrs))
|
3726 | );
|
3727 | forEach(inputGraph.nodes(), function(v) {
|
3728 | var node = canonicalize(inputGraph.node(v));
|
3729 | g.setNode(v, defaults$1(selectNumberAttrs(node, nodeNumAttrs), nodeDefaults));
|
3730 | g.setParent(v, inputGraph.parent(v));
|
3731 | });
|
3732 | forEach(inputGraph.edges(), function(e) {
|
3733 | var edge = canonicalize(inputGraph.edge(e));
|
3734 | g.setEdge(
|
3735 | e,
|
3736 | merge$1({}, edgeDefaults, selectNumberAttrs(edge, edgeNumAttrs), pick$1(edge, edgeAttrs))
|
3737 | );
|
3738 | });
|
3739 | return g;
|
3740 | }
|
3741 | function makeSpaceForEdgeLabels(g) {
|
3742 | var graph = g.graph();
|
3743 | graph.ranksep /= 2;
|
3744 | forEach(g.edges(), function(e) {
|
3745 | var edge = g.edge(e);
|
3746 | edge.minlen *= 2;
|
3747 | if (edge.labelpos.toLowerCase() !== "c") {
|
3748 | if (graph.rankdir === "TB" || graph.rankdir === "BT") {
|
3749 | edge.width += edge.labeloffset;
|
3750 | } else {
|
3751 | edge.height += edge.labeloffset;
|
3752 | }
|
3753 | }
|
3754 | });
|
3755 | }
|
3756 | function injectEdgeLabelProxies(g) {
|
3757 | forEach(g.edges(), function(e) {
|
3758 | var edge = g.edge(e);
|
3759 | if (edge.width && edge.height) {
|
3760 | var v = g.node(e.v);
|
3761 | var w = g.node(e.w);
|
3762 | var label = { rank: (w.rank - v.rank) / 2 + v.rank, e };
|
3763 | addDummyNode(g, "edge-proxy", label, "_ep");
|
3764 | }
|
3765 | });
|
3766 | }
|
3767 | function assignRankMinMax(g) {
|
3768 | var maxRank2 = 0;
|
3769 | forEach(g.nodes(), function(v) {
|
3770 | var node = g.node(v);
|
3771 | if (node.borderTop) {
|
3772 | node.minRank = g.node(node.borderTop).rank;
|
3773 | node.maxRank = g.node(node.borderBottom).rank;
|
3774 | maxRank2 = max(maxRank2, node.maxRank);
|
3775 | }
|
3776 | });
|
3777 | g.graph().maxRank = maxRank2;
|
3778 | }
|
3779 | function removeEdgeLabelProxies(g) {
|
3780 | forEach(g.nodes(), function(v) {
|
3781 | var node = g.node(v);
|
3782 | if (node.dummy === "edge-proxy") {
|
3783 | g.edge(node.e).labelRank = node.rank;
|
3784 | g.removeNode(v);
|
3785 | }
|
3786 | });
|
3787 | }
|
3788 | function translateGraph(g) {
|
3789 | var minX = Number.POSITIVE_INFINITY;
|
3790 | var maxX = 0;
|
3791 | var minY = Number.POSITIVE_INFINITY;
|
3792 | var maxY = 0;
|
3793 | var graphLabel = g.graph();
|
3794 | var marginX = graphLabel.marginx || 0;
|
3795 | var marginY = graphLabel.marginy || 0;
|
3796 | function getExtremes(attrs) {
|
3797 | var x = attrs.x;
|
3798 | var y = attrs.y;
|
3799 | var w = attrs.width;
|
3800 | var h = attrs.height;
|
3801 | minX = Math.min(minX, x - w / 2);
|
3802 | maxX = Math.max(maxX, x + w / 2);
|
3803 | minY = Math.min(minY, y - h / 2);
|
3804 | maxY = Math.max(maxY, y + h / 2);
|
3805 | }
|
3806 | forEach(g.nodes(), function(v) {
|
3807 | getExtremes(g.node(v));
|
3808 | });
|
3809 | forEach(g.edges(), function(e) {
|
3810 | var edge = g.edge(e);
|
3811 | if (has(edge, "x")) {
|
3812 | getExtremes(edge);
|
3813 | }
|
3814 | });
|
3815 | minX -= marginX;
|
3816 | minY -= marginY;
|
3817 | forEach(g.nodes(), function(v) {
|
3818 | var node = g.node(v);
|
3819 | node.x -= minX;
|
3820 | node.y -= minY;
|
3821 | });
|
3822 | forEach(g.edges(), function(e) {
|
3823 | var edge = g.edge(e);
|
3824 | forEach(edge.points, function(p) {
|
3825 | p.x -= minX;
|
3826 | p.y -= minY;
|
3827 | });
|
3828 | if (has(edge, "x")) {
|
3829 | edge.x -= minX;
|
3830 | }
|
3831 | if (has(edge, "y")) {
|
3832 | edge.y -= minY;
|
3833 | }
|
3834 | });
|
3835 | graphLabel.width = maxX - minX + marginX;
|
3836 | graphLabel.height = maxY - minY + marginY;
|
3837 | }
|
3838 | function assignNodeIntersects(g) {
|
3839 | forEach(g.edges(), function(e) {
|
3840 | var edge = g.edge(e);
|
3841 | var nodeV = g.node(e.v);
|
3842 | var nodeW = g.node(e.w);
|
3843 | var p1, p2;
|
3844 | if (!edge.points) {
|
3845 | edge.points = [];
|
3846 | p1 = nodeW;
|
3847 | p2 = nodeV;
|
3848 | } else {
|
3849 | p1 = edge.points[0];
|
3850 | p2 = edge.points[edge.points.length - 1];
|
3851 | }
|
3852 | edge.points.unshift(intersectRect(nodeV, p1));
|
3853 | edge.points.push(intersectRect(nodeW, p2));
|
3854 | });
|
3855 | }
|
3856 | function fixupEdgeLabelCoords(g) {
|
3857 | forEach(g.edges(), function(e) {
|
3858 | var edge = g.edge(e);
|
3859 | if (has(edge, "x")) {
|
3860 | if (edge.labelpos === "l" || edge.labelpos === "r") {
|
3861 | edge.width -= edge.labeloffset;
|
3862 | }
|
3863 | switch (edge.labelpos) {
|
3864 | case "l":
|
3865 | edge.x -= edge.width / 2 + edge.labeloffset;
|
3866 | break;
|
3867 | case "r":
|
3868 | edge.x += edge.width / 2 + edge.labeloffset;
|
3869 | break;
|
3870 | }
|
3871 | }
|
3872 | });
|
3873 | }
|
3874 | function reversePointsForReversedEdges(g) {
|
3875 | forEach(g.edges(), function(e) {
|
3876 | var edge = g.edge(e);
|
3877 | if (edge.reversed) {
|
3878 | edge.points.reverse();
|
3879 | }
|
3880 | });
|
3881 | }
|
3882 | function removeBorderNodes(g) {
|
3883 | forEach(g.nodes(), function(v) {
|
3884 | if (g.children(v).length) {
|
3885 | var node = g.node(v);
|
3886 | var t = g.node(node.borderTop);
|
3887 | var b = g.node(node.borderBottom);
|
3888 | var l = g.node(last(node.borderLeft));
|
3889 | var r = g.node(last(node.borderRight));
|
3890 | node.width = Math.abs(r.x - l.x);
|
3891 | node.height = Math.abs(b.y - t.y);
|
3892 | node.x = l.x + node.width / 2;
|
3893 | node.y = t.y + node.height / 2;
|
3894 | }
|
3895 | });
|
3896 | forEach(g.nodes(), function(v) {
|
3897 | if (g.node(v).dummy === "border") {
|
3898 | g.removeNode(v);
|
3899 | }
|
3900 | });
|
3901 | }
|
3902 | function removeSelfEdges(g) {
|
3903 | forEach(g.edges(), function(e) {
|
3904 | if (e.v === e.w) {
|
3905 | var node = g.node(e.v);
|
3906 | if (!node.selfEdges) {
|
3907 | node.selfEdges = [];
|
3908 | }
|
3909 | node.selfEdges.push({ e, label: g.edge(e) });
|
3910 | g.removeEdge(e);
|
3911 | }
|
3912 | });
|
3913 | }
|
3914 | function insertSelfEdges(g) {
|
3915 | var layers = buildLayerMatrix(g);
|
3916 | forEach(layers, function(layer) {
|
3917 | var orderShift = 0;
|
3918 | forEach(layer, function(v, i) {
|
3919 | var node = g.node(v);
|
3920 | node.order = i + orderShift;
|
3921 | forEach(node.selfEdges, function(selfEdge) {
|
3922 | addDummyNode(
|
3923 | g,
|
3924 | "selfedge",
|
3925 | {
|
3926 | width: selfEdge.label.width,
|
3927 | height: selfEdge.label.height,
|
3928 | rank: node.rank,
|
3929 | order: i + ++orderShift,
|
3930 | e: selfEdge.e,
|
3931 | label: selfEdge.label
|
3932 | },
|
3933 | "_se"
|
3934 | );
|
3935 | });
|
3936 | delete node.selfEdges;
|
3937 | });
|
3938 | });
|
3939 | }
|
3940 | function positionSelfEdges(g) {
|
3941 | forEach(g.nodes(), function(v) {
|
3942 | var node = g.node(v);
|
3943 | if (node.dummy === "selfedge") {
|
3944 | var selfNode = g.node(node.e.v);
|
3945 | var x = selfNode.x + selfNode.width / 2;
|
3946 | var y = selfNode.y;
|
3947 | var dx = node.x - x;
|
3948 | var dy = selfNode.height / 2;
|
3949 | g.setEdge(node.e, node.label);
|
3950 | g.removeNode(v);
|
3951 | node.label.points = [
|
3952 | { x: x + 2 * dx / 3, y: y - dy },
|
3953 | { x: x + 5 * dx / 6, y: y - dy },
|
3954 | { x: x + dx, y },
|
3955 | { x: x + 5 * dx / 6, y: y + dy },
|
3956 | { x: x + 2 * dx / 3, y: y + dy }
|
3957 | ];
|
3958 | node.label.x = node.x;
|
3959 | node.label.y = node.y;
|
3960 | }
|
3961 | });
|
3962 | }
|
3963 | function selectNumberAttrs(obj, attrs) {
|
3964 | return mapValues(pick$1(obj, attrs), Number);
|
3965 | }
|
3966 | function canonicalize(attrs) {
|
3967 | var newAttrs = {};
|
3968 | forEach(attrs, function(v, k) {
|
3969 | newAttrs[k.toLowerCase()] = v;
|
3970 | });
|
3971 | return newAttrs;
|
3972 | }
|
3973 | export {
|
3974 | Graph as G,
|
3975 | isUndefined as a,
|
3976 | baseClone as b,
|
3977 | defaults$1 as d,
|
3978 | forEach as f,
|
3979 | has as h,
|
3980 | isPlainObject as i,
|
3981 | layout as l,
|
3982 | map as m,
|
3983 | pick$1 as p,
|
3984 | range$1 as r,
|
3985 | uniqueId as u
|
3986 | };
|