import { i as isObjectLike, a as isArray, b as isArrayLike, c as isArguments, d as isBuffer, e as isTypedArray, f as baseKeys, g as isPrototype, h as getTag, n as nodeUtil, j as baseUnary, k as isLength, S as Set, l as isEmpty } from "./mermaidAPI-6f22a815.js"; import { h as baseGetTag, S as Symbol$1, A as isObject, c as getNative, B as eq, C as memoize, L as ListCache, M as Map, D as MapCache, f as root, j as isFunction } from "./utils-872dfc50.js"; import { g as getPrototype, i as isPlainObject } from "./isPlainObject-91dd8bc9.js"; var symbolTag$3 = "[object Symbol]"; function isSymbol(value) { return typeof value == "symbol" || isObjectLike(value) && baseGetTag(value) == symbolTag$3; } function arrayMap(array, iteratee) { var index = -1, length = array == null ? 0 : array.length, result = Array(length); while (++index < length) { result[index] = iteratee(array[index], index, array); } return result; } var INFINITY$3 = 1 / 0; var symbolProto$2 = Symbol$1 ? Symbol$1.prototype : void 0, symbolToString = symbolProto$2 ? symbolProto$2.toString : void 0; function baseToString(value) { if (typeof value == "string") { return value; } if (isArray(value)) { return arrayMap(value, baseToString) + ""; } if (isSymbol(value)) { return symbolToString ? symbolToString.call(value) : ""; } var result = value + ""; return result == "0" && 1 / value == -INFINITY$3 ? "-0" : result; } var reWhitespace = /\s/; function trimmedEndIndex(string) { var index = string.length; while (index-- && reWhitespace.test(string.charAt(index))) { } return index; } var reTrimStart = /^\s+/; function baseTrim(string) { return string ? string.slice(0, trimmedEndIndex(string) + 1).replace(reTrimStart, "") : string; } var NAN = 0 / 0; var reIsBadHex = /^[-+]0x[0-9a-f]+$/i; var reIsBinary = /^0b[01]+$/i; var reIsOctal = /^0o[0-7]+$/i; var freeParseInt = parseInt; function toNumber(value) { if (typeof value == "number") { return value; } if (isSymbol(value)) { return NAN; } if (isObject(value)) { var other = typeof value.valueOf == "function" ? value.valueOf() : value; value = isObject(other) ? other + "" : other; } if (typeof value != "string") { return value === 0 ? value : +value; } value = baseTrim(value); var isBinary = reIsBinary.test(value); return isBinary || reIsOctal.test(value) ? freeParseInt(value.slice(2), isBinary ? 2 : 8) : reIsBadHex.test(value) ? NAN : +value; } var INFINITY$2 = 1 / 0, MAX_INTEGER = 17976931348623157e292; function toFinite(value) { if (!value) { return value === 0 ? value : 0; } value = toNumber(value); if (value === INFINITY$2 || value === -INFINITY$2) { var sign = value < 0 ? -1 : 1; return sign * MAX_INTEGER; } return value === value ? value : 0; } function toInteger(value) { var result = toFinite(value), remainder = result % 1; return result === result ? remainder ? result - remainder : result : 0; } function identity(value) { return value; } var objectCreate = Object.create; var baseCreate = function() { function object() { } return function(proto) { if (!isObject(proto)) { return {}; } if (objectCreate) { return objectCreate(proto); } object.prototype = proto; var result = new object(); object.prototype = void 0; return result; }; }(); const baseCreate$1 = baseCreate; function apply(func, thisArg, args) { switch (args.length) { case 0: return func.call(thisArg); case 1: return func.call(thisArg, args[0]); case 2: return func.call(thisArg, args[0], args[1]); case 3: return func.call(thisArg, args[0], args[1], args[2]); } return func.apply(thisArg, args); } function noop() { } function copyArray(source, array) { var index = -1, length = source.length; array || (array = Array(length)); while (++index < length) { array[index] = source[index]; } return array; } var HOT_COUNT = 800, HOT_SPAN = 16; var nativeNow = Date.now; function shortOut(func) { var count = 0, lastCalled = 0; return function() { var stamp = nativeNow(), remaining = HOT_SPAN - (stamp - lastCalled); lastCalled = stamp; if (remaining > 0) { if (++count >= HOT_COUNT) { return arguments[0]; } } else { count = 0; } return func.apply(void 0, arguments); }; } function constant(value) { return function() { return value; }; } var defineProperty = function() { try { var func = getNative(Object, "defineProperty"); func({}, "", {}); return func; } catch (e) { } }(); const defineProperty$1 = defineProperty; var baseSetToString = !defineProperty$1 ? identity : function(func, string) { return defineProperty$1(func, "toString", { "configurable": true, "enumerable": false, "value": constant(string), "writable": true }); }; const baseSetToString$1 = baseSetToString; var setToString = shortOut(baseSetToString$1); const setToString$1 = setToString; function arrayEach(array, iteratee) { var index = -1, length = array == null ? 0 : array.length; while (++index < length) { if (iteratee(array[index], index, array) === false) { break; } } return array; } function baseFindIndex(array, predicate, fromIndex, fromRight) { var length = array.length, index = fromIndex + (fromRight ? 1 : -1); while (fromRight ? index-- : ++index < length) { if (predicate(array[index], index, array)) { return index; } } return -1; } function baseIsNaN(value) { return value !== value; } function strictIndexOf(array, value, fromIndex) { var index = fromIndex - 1, length = array.length; while (++index < length) { if (array[index] === value) { return index; } } return -1; } function baseIndexOf(array, value, fromIndex) { return value === value ? strictIndexOf(array, value, fromIndex) : baseFindIndex(array, baseIsNaN, fromIndex); } function arrayIncludes(array, value) { var length = array == null ? 0 : array.length; return !!length && baseIndexOf(array, value, 0) > -1; } var MAX_SAFE_INTEGER = 9007199254740991; var reIsUint = /^(?:0|[1-9]\d*)$/; function isIndex(value, length) { var type = typeof value; length = length == null ? MAX_SAFE_INTEGER : length; return !!length && (type == "number" || type != "symbol" && reIsUint.test(value)) && (value > -1 && value % 1 == 0 && value < length); } function baseAssignValue(object, key, value) { if (key == "__proto__" && defineProperty$1) { defineProperty$1(object, key, { "configurable": true, "enumerable": true, "value": value, "writable": true }); } else { object[key] = value; } } var objectProto$8 = Object.prototype; var hasOwnProperty$7 = objectProto$8.hasOwnProperty; function assignValue(object, key, value) { var objValue = object[key]; if (!(hasOwnProperty$7.call(object, key) && eq(objValue, value)) || value === void 0 && !(key in object)) { baseAssignValue(object, key, value); } } function copyObject(source, props, object, customizer) { var isNew = !object; object || (object = {}); var index = -1, length = props.length; while (++index < length) { var key = props[index]; var newValue = customizer ? customizer(object[key], source[key], key, object, source) : void 0; if (newValue === void 0) { newValue = source[key]; } if (isNew) { baseAssignValue(object, key, newValue); } else { assignValue(object, key, newValue); } } return object; } var nativeMax$2 = Math.max; function overRest(func, start, transform) { start = nativeMax$2(start === void 0 ? func.length - 1 : start, 0); return function() { var args = arguments, index = -1, length = nativeMax$2(args.length - start, 0), array = Array(length); while (++index < length) { array[index] = args[start + index]; } index = -1; var otherArgs = Array(start + 1); while (++index < start) { otherArgs[index] = args[index]; } otherArgs[start] = transform(array); return apply(func, this, otherArgs); }; } function baseRest(func, start) { return setToString$1(overRest(func, start, identity), func + ""); } function isIterateeCall(value, index, object) { if (!isObject(object)) { return false; } var type = typeof index; if (type == "number" ? isArrayLike(object) && isIndex(index, object.length) : type == "string" && index in object) { return eq(object[index], value); } return false; } function createAssigner(assigner) { return baseRest(function(object, sources) { var index = -1, length = sources.length, customizer = length > 1 ? sources[length - 1] : void 0, guard = length > 2 ? sources[2] : void 0; customizer = assigner.length > 3 && typeof customizer == "function" ? (length--, customizer) : void 0; if (guard && isIterateeCall(sources[0], sources[1], guard)) { customizer = length < 3 ? void 0 : customizer; length = 1; } object = Object(object); while (++index < length) { var source = sources[index]; if (source) { assigner(object, source, index, customizer); } } return object; }); } function baseTimes(n, iteratee) { var index = -1, result = Array(n); while (++index < n) { result[index] = iteratee(index); } return result; } var objectProto$7 = Object.prototype; var hasOwnProperty$6 = objectProto$7.hasOwnProperty; function arrayLikeKeys(value, inherited) { 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; for (var key in value) { if ((inherited || hasOwnProperty$6.call(value, key)) && !(skipIndexes && // Safari 9 has enumerable `arguments.length` in strict mode. (key == "length" || // Node.js 0.10 has enumerable non-index properties on buffers. isBuff && (key == "offset" || key == "parent") || // PhantomJS 2 has enumerable non-index properties on typed arrays. isType && (key == "buffer" || key == "byteLength" || key == "byteOffset") || // Skip index properties. isIndex(key, length)))) { result.push(key); } } return result; } function keys(object) { return isArrayLike(object) ? arrayLikeKeys(object) : baseKeys(object); } function nativeKeysIn(object) { var result = []; if (object != null) { for (var key in Object(object)) { result.push(key); } } return result; } var objectProto$6 = Object.prototype; var hasOwnProperty$5 = objectProto$6.hasOwnProperty; function baseKeysIn(object) { if (!isObject(object)) { return nativeKeysIn(object); } var isProto = isPrototype(object), result = []; for (var key in object) { if (!(key == "constructor" && (isProto || !hasOwnProperty$5.call(object, key)))) { result.push(key); } } return result; } function keysIn(object) { return isArrayLike(object) ? arrayLikeKeys(object, true) : baseKeysIn(object); } var reIsDeepProp = /\.|\[(?:[^[\]]*|(["'])(?:(?!\1)[^\\]|\\.)*?\1)\]/, reIsPlainProp = /^\w*$/; function isKey(value, object) { if (isArray(value)) { return false; } var type = typeof value; if (type == "number" || type == "symbol" || type == "boolean" || value == null || isSymbol(value)) { return true; } return reIsPlainProp.test(value) || !reIsDeepProp.test(value) || object != null && value in Object(object); } var MAX_MEMOIZE_SIZE = 500; function memoizeCapped(func) { var result = memoize(func, function(key) { if (cache.size === MAX_MEMOIZE_SIZE) { cache.clear(); } return key; }); var cache = result.cache; return result; } var rePropName = /[^.[\]]+|\[(?:(-?\d+(?:\.\d+)?)|(["'])((?:(?!\2)[^\\]|\\.)*?)\2)\]|(?=(?:\.|\[\])(?:\.|\[\]|$))/g; var reEscapeChar = /\\(\\)?/g; var stringToPath = memoizeCapped(function(string) { var result = []; if (string.charCodeAt(0) === 46) { result.push(""); } string.replace(rePropName, function(match, number, quote, subString) { result.push(quote ? subString.replace(reEscapeChar, "$1") : number || match); }); return result; }); const stringToPath$1 = stringToPath; function toString(value) { return value == null ? "" : baseToString(value); } function castPath(value, object) { if (isArray(value)) { return value; } return isKey(value, object) ? [value] : stringToPath$1(toString(value)); } var INFINITY$1 = 1 / 0; function toKey(value) { if (typeof value == "string" || isSymbol(value)) { return value; } var result = value + ""; return result == "0" && 1 / value == -INFINITY$1 ? "-0" : result; } function baseGet(object, path) { path = castPath(path, object); var index = 0, length = path.length; while (object != null && index < length) { object = object[toKey(path[index++])]; } return index && index == length ? object : void 0; } function get(object, path, defaultValue) { var result = object == null ? void 0 : baseGet(object, path); return result === void 0 ? defaultValue : result; } function arrayPush(array, values2) { var index = -1, length = values2.length, offset = array.length; while (++index < length) { array[offset + index] = values2[index]; } return array; } var spreadableSymbol = Symbol$1 ? Symbol$1.isConcatSpreadable : void 0; function isFlattenable(value) { return isArray(value) || isArguments(value) || !!(spreadableSymbol && value && value[spreadableSymbol]); } function baseFlatten(array, depth, predicate, isStrict, result) { var index = -1, length = array.length; predicate || (predicate = isFlattenable); result || (result = []); while (++index < length) { var value = array[index]; if (depth > 0 && predicate(value)) { if (depth > 1) { baseFlatten(value, depth - 1, predicate, isStrict, result); } else { arrayPush(result, value); } } else if (!isStrict) { result[result.length] = value; } } return result; } function flatten(array) { var length = array == null ? 0 : array.length; return length ? baseFlatten(array, 1) : []; } function flatRest(func) { return setToString$1(overRest(func, void 0, flatten), func + ""); } function arrayReduce(array, iteratee, accumulator, initAccum) { var index = -1, length = array == null ? 0 : array.length; if (initAccum && length) { accumulator = array[++index]; } while (++index < length) { accumulator = iteratee(accumulator, array[index], index, array); } return accumulator; } function stackClear() { this.__data__ = new ListCache(); this.size = 0; } function stackDelete(key) { var data = this.__data__, result = data["delete"](key); this.size = data.size; return result; } function stackGet(key) { return this.__data__.get(key); } function stackHas(key) { return this.__data__.has(key); } var LARGE_ARRAY_SIZE$1 = 200; function stackSet(key, value) { var data = this.__data__; if (data instanceof ListCache) { var pairs = data.__data__; if (!Map || pairs.length < LARGE_ARRAY_SIZE$1 - 1) { pairs.push([key, value]); this.size = ++data.size; return this; } data = this.__data__ = new MapCache(pairs); } data.set(key, value); this.size = data.size; return this; } function Stack(entries) { var data = this.__data__ = new ListCache(entries); this.size = data.size; } Stack.prototype.clear = stackClear; Stack.prototype["delete"] = stackDelete; Stack.prototype.get = stackGet; Stack.prototype.has = stackHas; Stack.prototype.set = stackSet; function baseAssign(object, source) { return object && copyObject(source, keys(source), object); } function baseAssignIn(object, source) { return object && copyObject(source, keysIn(source), object); } var freeExports = typeof exports == "object" && exports && !exports.nodeType && exports; var freeModule = freeExports && typeof module == "object" && module && !module.nodeType && module; var moduleExports = freeModule && freeModule.exports === freeExports; var Buffer = moduleExports ? root.Buffer : void 0, allocUnsafe = Buffer ? Buffer.allocUnsafe : void 0; function cloneBuffer(buffer, isDeep) { if (isDeep) { return buffer.slice(); } var length = buffer.length, result = allocUnsafe ? allocUnsafe(length) : new buffer.constructor(length); buffer.copy(result); return result; } function arrayFilter(array, predicate) { var index = -1, length = array == null ? 0 : array.length, resIndex = 0, result = []; while (++index < length) { var value = array[index]; if (predicate(value, index, array)) { result[resIndex++] = value; } } return result; } function stubArray() { return []; } var objectProto$5 = Object.prototype; var propertyIsEnumerable = objectProto$5.propertyIsEnumerable; var nativeGetSymbols$1 = Object.getOwnPropertySymbols; var getSymbols = !nativeGetSymbols$1 ? stubArray : function(object) { if (object == null) { return []; } object = Object(object); return arrayFilter(nativeGetSymbols$1(object), function(symbol) { return propertyIsEnumerable.call(object, symbol); }); }; const getSymbols$1 = getSymbols; function copySymbols(source, object) { return copyObject(source, getSymbols$1(source), object); } var nativeGetSymbols = Object.getOwnPropertySymbols; var getSymbolsIn = !nativeGetSymbols ? stubArray : function(object) { var result = []; while (object) { arrayPush(result, getSymbols$1(object)); object = getPrototype(object); } return result; }; const getSymbolsIn$1 = getSymbolsIn; function copySymbolsIn(source, object) { return copyObject(source, getSymbolsIn$1(source), object); } function baseGetAllKeys(object, keysFunc, symbolsFunc) { var result = keysFunc(object); return isArray(object) ? result : arrayPush(result, symbolsFunc(object)); } function getAllKeys(object) { return baseGetAllKeys(object, keys, getSymbols$1); } function getAllKeysIn(object) { return baseGetAllKeys(object, keysIn, getSymbolsIn$1); } var objectProto$4 = Object.prototype; var hasOwnProperty$4 = objectProto$4.hasOwnProperty; function initCloneArray(array) { var length = array.length, result = new array.constructor(length); if (length && typeof array[0] == "string" && hasOwnProperty$4.call(array, "index")) { result.index = array.index; result.input = array.input; } return result; } var Uint8Array = root.Uint8Array; const Uint8Array$1 = Uint8Array; function cloneArrayBuffer(arrayBuffer) { var result = new arrayBuffer.constructor(arrayBuffer.byteLength); new Uint8Array$1(result).set(new Uint8Array$1(arrayBuffer)); return result; } function cloneDataView(dataView, isDeep) { var buffer = isDeep ? cloneArrayBuffer(dataView.buffer) : dataView.buffer; return new dataView.constructor(buffer, dataView.byteOffset, dataView.byteLength); } var reFlags = /\w*$/; function cloneRegExp(regexp) { var result = new regexp.constructor(regexp.source, reFlags.exec(regexp)); result.lastIndex = regexp.lastIndex; return result; } var symbolProto$1 = Symbol$1 ? Symbol$1.prototype : void 0, symbolValueOf$1 = symbolProto$1 ? symbolProto$1.valueOf : void 0; function cloneSymbol(symbol) { return symbolValueOf$1 ? Object(symbolValueOf$1.call(symbol)) : {}; } function cloneTypedArray(typedArray, isDeep) { var buffer = isDeep ? cloneArrayBuffer(typedArray.buffer) : typedArray.buffer; return new typedArray.constructor(buffer, typedArray.byteOffset, typedArray.length); } 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]"; 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]"; function initCloneByTag(object, tag, isDeep) { var Ctor = object.constructor; switch (tag) { case arrayBufferTag$2: return cloneArrayBuffer(object); case boolTag$2: case dateTag$2: return new Ctor(+object); case dataViewTag$2: return cloneDataView(object, isDeep); case float32Tag$1: case float64Tag$1: case int8Tag$1: case int16Tag$1: case int32Tag$1: case uint8Tag$1: case uint8ClampedTag$1: case uint16Tag$1: case uint32Tag$1: return cloneTypedArray(object, isDeep); case mapTag$3: return new Ctor(); case numberTag$2: case stringTag$2: return new Ctor(object); case regexpTag$2: return cloneRegExp(object); case setTag$3: return new Ctor(); case symbolTag$2: return cloneSymbol(object); } } function initCloneObject(object) { return typeof object.constructor == "function" && !isPrototype(object) ? baseCreate$1(getPrototype(object)) : {}; } var mapTag$2 = "[object Map]"; function baseIsMap(value) { return isObjectLike(value) && getTag(value) == mapTag$2; } var nodeIsMap = nodeUtil && nodeUtil.isMap; var isMap = nodeIsMap ? baseUnary(nodeIsMap) : baseIsMap; const isMap$1 = isMap; var setTag$2 = "[object Set]"; function baseIsSet(value) { return isObjectLike(value) && getTag(value) == setTag$2; } var nodeIsSet = nodeUtil && nodeUtil.isSet; var isSet = nodeIsSet ? baseUnary(nodeIsSet) : baseIsSet; const isSet$1 = isSet; var CLONE_DEEP_FLAG$1 = 1, CLONE_FLAT_FLAG = 2, CLONE_SYMBOLS_FLAG$1 = 4; 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]"; 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]"; var cloneableTags = {}; 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; cloneableTags[errorTag$1] = cloneableTags[funcTag] = cloneableTags[weakMapTag] = false; function baseClone(value, bitmask, customizer, key, object, stack) { var result, isDeep = bitmask & CLONE_DEEP_FLAG$1, isFlat = bitmask & CLONE_FLAT_FLAG, isFull = bitmask & CLONE_SYMBOLS_FLAG$1; if (customizer) { result = object ? customizer(value, key, object, stack) : customizer(value); } if (result !== void 0) { return result; } if (!isObject(value)) { return value; } var isArr = isArray(value); if (isArr) { result = initCloneArray(value); if (!isDeep) { return copyArray(value, result); } } else { var tag = getTag(value), isFunc = tag == funcTag || tag == genTag; if (isBuffer(value)) { return cloneBuffer(value, isDeep); } if (tag == objectTag$1 || tag == argsTag$1 || isFunc && !object) { result = isFlat || isFunc ? {} : initCloneObject(value); if (!isDeep) { return isFlat ? copySymbolsIn(value, baseAssignIn(result, value)) : copySymbols(value, baseAssign(result, value)); } } else { if (!cloneableTags[tag]) { return object ? value : {}; } result = initCloneByTag(value, tag, isDeep); } } stack || (stack = new Stack()); var stacked = stack.get(value); if (stacked) { return stacked; } stack.set(value, result); if (isSet$1(value)) { value.forEach(function(subValue) { result.add(baseClone(subValue, bitmask, customizer, subValue, value, stack)); }); } else if (isMap$1(value)) { value.forEach(function(subValue, key2) { result.set(key2, baseClone(subValue, bitmask, customizer, key2, value, stack)); }); } var keysFunc = isFull ? isFlat ? getAllKeysIn : getAllKeys : isFlat ? keysIn : keys; var props = isArr ? void 0 : keysFunc(value); arrayEach(props || value, function(subValue, key2) { if (props) { key2 = subValue; subValue = value[key2]; } assignValue(result, key2, baseClone(subValue, bitmask, customizer, key2, value, stack)); }); return result; } var CLONE_DEEP_FLAG = 1, CLONE_SYMBOLS_FLAG = 4; function cloneDeep(value) { return baseClone(value, CLONE_DEEP_FLAG | CLONE_SYMBOLS_FLAG); } var HASH_UNDEFINED = "__lodash_hash_undefined__"; function setCacheAdd(value) { this.__data__.set(value, HASH_UNDEFINED); return this; } function setCacheHas(value) { return this.__data__.has(value); } function SetCache(values2) { var index = -1, length = values2 == null ? 0 : values2.length; this.__data__ = new MapCache(); while (++index < length) { this.add(values2[index]); } } SetCache.prototype.add = SetCache.prototype.push = setCacheAdd; SetCache.prototype.has = setCacheHas; function arraySome(array, predicate) { var index = -1, length = array == null ? 0 : array.length; while (++index < length) { if (predicate(array[index], index, array)) { return true; } } return false; } function cacheHas(cache, key) { return cache.has(key); } var COMPARE_PARTIAL_FLAG$5 = 1, COMPARE_UNORDERED_FLAG$3 = 2; function equalArrays(array, other, bitmask, customizer, equalFunc, stack) { var isPartial = bitmask & COMPARE_PARTIAL_FLAG$5, arrLength = array.length, othLength = other.length; if (arrLength != othLength && !(isPartial && othLength > arrLength)) { return false; } var arrStacked = stack.get(array); var othStacked = stack.get(other); if (arrStacked && othStacked) { return arrStacked == other && othStacked == array; } var index = -1, result = true, seen = bitmask & COMPARE_UNORDERED_FLAG$3 ? new SetCache() : void 0; stack.set(array, other); stack.set(other, array); while (++index < arrLength) { var arrValue = array[index], othValue = other[index]; if (customizer) { var compared = isPartial ? customizer(othValue, arrValue, index, other, array, stack) : customizer(arrValue, othValue, index, array, other, stack); } if (compared !== void 0) { if (compared) { continue; } result = false; break; } if (seen) { if (!arraySome(other, function(othValue2, othIndex) { if (!cacheHas(seen, othIndex) && (arrValue === othValue2 || equalFunc(arrValue, othValue2, bitmask, customizer, stack))) { return seen.push(othIndex); } })) { result = false; break; } } else if (!(arrValue === othValue || equalFunc(arrValue, othValue, bitmask, customizer, stack))) { result = false; break; } } stack["delete"](array); stack["delete"](other); return result; } function mapToArray(map2) { var index = -1, result = Array(map2.size); map2.forEach(function(value, key) { result[++index] = [key, value]; }); return result; } function setToArray(set) { var index = -1, result = Array(set.size); set.forEach(function(value) { result[++index] = value; }); return result; } var COMPARE_PARTIAL_FLAG$4 = 1, COMPARE_UNORDERED_FLAG$2 = 2; 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]"; var arrayBufferTag = "[object ArrayBuffer]", dataViewTag = "[object DataView]"; var symbolProto = Symbol$1 ? Symbol$1.prototype : void 0, symbolValueOf = symbolProto ? symbolProto.valueOf : void 0; function equalByTag(object, other, tag, bitmask, customizer, equalFunc, stack) { switch (tag) { case dataViewTag: if (object.byteLength != other.byteLength || object.byteOffset != other.byteOffset) { return false; } object = object.buffer; other = other.buffer; case arrayBufferTag: if (object.byteLength != other.byteLength || !equalFunc(new Uint8Array$1(object), new Uint8Array$1(other))) { return false; } return true; case boolTag: case dateTag: case numberTag: return eq(+object, +other); case errorTag: return object.name == other.name && object.message == other.message; case regexpTag: case stringTag: return object == other + ""; case mapTag: var convert = mapToArray; case setTag: var isPartial = bitmask & COMPARE_PARTIAL_FLAG$4; convert || (convert = setToArray); if (object.size != other.size && !isPartial) { return false; } var stacked = stack.get(object); if (stacked) { return stacked == other; } bitmask |= COMPARE_UNORDERED_FLAG$2; stack.set(object, other); var result = equalArrays(convert(object), convert(other), bitmask, customizer, equalFunc, stack); stack["delete"](object); return result; case symbolTag: if (symbolValueOf) { return symbolValueOf.call(object) == symbolValueOf.call(other); } } return false; } var COMPARE_PARTIAL_FLAG$3 = 1; var objectProto$3 = Object.prototype; var hasOwnProperty$3 = objectProto$3.hasOwnProperty; function equalObjects(object, other, bitmask, customizer, equalFunc, stack) { var isPartial = bitmask & COMPARE_PARTIAL_FLAG$3, objProps = getAllKeys(object), objLength = objProps.length, othProps = getAllKeys(other), othLength = othProps.length; if (objLength != othLength && !isPartial) { return false; } var index = objLength; while (index--) { var key = objProps[index]; if (!(isPartial ? key in other : hasOwnProperty$3.call(other, key))) { return false; } } var objStacked = stack.get(object); var othStacked = stack.get(other); if (objStacked && othStacked) { return objStacked == other && othStacked == object; } var result = true; stack.set(object, other); stack.set(other, object); var skipCtor = isPartial; while (++index < objLength) { key = objProps[index]; var objValue = object[key], othValue = other[key]; if (customizer) { var compared = isPartial ? customizer(othValue, objValue, key, other, object, stack) : customizer(objValue, othValue, key, object, other, stack); } if (!(compared === void 0 ? objValue === othValue || equalFunc(objValue, othValue, bitmask, customizer, stack) : compared)) { result = false; break; } skipCtor || (skipCtor = key == "constructor"); } if (result && !skipCtor) { var objCtor = object.constructor, othCtor = other.constructor; if (objCtor != othCtor && ("constructor" in object && "constructor" in other) && !(typeof objCtor == "function" && objCtor instanceof objCtor && typeof othCtor == "function" && othCtor instanceof othCtor)) { result = false; } } stack["delete"](object); stack["delete"](other); return result; } var COMPARE_PARTIAL_FLAG$2 = 1; var argsTag = "[object Arguments]", arrayTag = "[object Array]", objectTag = "[object Object]"; var objectProto$2 = Object.prototype; var hasOwnProperty$2 = objectProto$2.hasOwnProperty; function baseIsEqualDeep(object, other, bitmask, customizer, equalFunc, stack) { var objIsArr = isArray(object), othIsArr = isArray(other), objTag = objIsArr ? arrayTag : getTag(object), othTag = othIsArr ? arrayTag : getTag(other); objTag = objTag == argsTag ? objectTag : objTag; othTag = othTag == argsTag ? objectTag : othTag; var objIsObj = objTag == objectTag, othIsObj = othTag == objectTag, isSameTag = objTag == othTag; if (isSameTag && isBuffer(object)) { if (!isBuffer(other)) { return false; } objIsArr = true; objIsObj = false; } if (isSameTag && !objIsObj) { stack || (stack = new Stack()); return objIsArr || isTypedArray(object) ? equalArrays(object, other, bitmask, customizer, equalFunc, stack) : equalByTag(object, other, objTag, bitmask, customizer, equalFunc, stack); } if (!(bitmask & COMPARE_PARTIAL_FLAG$2)) { var objIsWrapped = objIsObj && hasOwnProperty$2.call(object, "__wrapped__"), othIsWrapped = othIsObj && hasOwnProperty$2.call(other, "__wrapped__"); if (objIsWrapped || othIsWrapped) { var objUnwrapped = objIsWrapped ? object.value() : object, othUnwrapped = othIsWrapped ? other.value() : other; stack || (stack = new Stack()); return equalFunc(objUnwrapped, othUnwrapped, bitmask, customizer, stack); } } if (!isSameTag) { return false; } stack || (stack = new Stack()); return equalObjects(object, other, bitmask, customizer, equalFunc, stack); } function baseIsEqual(value, other, bitmask, customizer, stack) { if (value === other) { return true; } if (value == null || other == null || !isObjectLike(value) && !isObjectLike(other)) { return value !== value && other !== other; } return baseIsEqualDeep(value, other, bitmask, customizer, baseIsEqual, stack); } var COMPARE_PARTIAL_FLAG$1 = 1, COMPARE_UNORDERED_FLAG$1 = 2; function baseIsMatch(object, source, matchData, customizer) { var index = matchData.length, length = index, noCustomizer = !customizer; if (object == null) { return !length; } object = Object(object); while (index--) { var data = matchData[index]; if (noCustomizer && data[2] ? data[1] !== object[data[0]] : !(data[0] in object)) { return false; } } while (++index < length) { data = matchData[index]; var key = data[0], objValue = object[key], srcValue = data[1]; if (noCustomizer && data[2]) { if (objValue === void 0 && !(key in object)) { return false; } } else { var stack = new Stack(); if (customizer) { var result = customizer(objValue, srcValue, key, object, source, stack); } if (!(result === void 0 ? baseIsEqual(srcValue, objValue, COMPARE_PARTIAL_FLAG$1 | COMPARE_UNORDERED_FLAG$1, customizer, stack) : result)) { return false; } } } return true; } function isStrictComparable(value) { return value === value && !isObject(value); } function getMatchData(object) { var result = keys(object), length = result.length; while (length--) { var key = result[length], value = object[key]; result[length] = [key, value, isStrictComparable(value)]; } return result; } function matchesStrictComparable(key, srcValue) { return function(object) { if (object == null) { return false; } return object[key] === srcValue && (srcValue !== void 0 || key in Object(object)); }; } function baseMatches(source) { var matchData = getMatchData(source); if (matchData.length == 1 && matchData[0][2]) { return matchesStrictComparable(matchData[0][0], matchData[0][1]); } return function(object) { return object === source || baseIsMatch(object, source, matchData); }; } function baseHasIn(object, key) { return object != null && key in Object(object); } function hasPath(object, path, hasFunc) { path = castPath(path, object); var index = -1, length = path.length, result = false; while (++index < length) { var key = toKey(path[index]); if (!(result = object != null && hasFunc(object, key))) { break; } object = object[key]; } if (result || ++index != length) { return result; } length = object == null ? 0 : object.length; return !!length && isLength(length) && isIndex(key, length) && (isArray(object) || isArguments(object)); } function hasIn(object, path) { return object != null && hasPath(object, path, baseHasIn); } var COMPARE_PARTIAL_FLAG = 1, COMPARE_UNORDERED_FLAG = 2; function baseMatchesProperty(path, srcValue) { if (isKey(path) && isStrictComparable(srcValue)) { return matchesStrictComparable(toKey(path), srcValue); } return function(object) { var objValue = get(object, path); return objValue === void 0 && objValue === srcValue ? hasIn(object, path) : baseIsEqual(srcValue, objValue, COMPARE_PARTIAL_FLAG | COMPARE_UNORDERED_FLAG); }; } function baseProperty(key) { return function(object) { return object == null ? void 0 : object[key]; }; } function basePropertyDeep(path) { return function(object) { return baseGet(object, path); }; } function property(path) { return isKey(path) ? baseProperty(toKey(path)) : basePropertyDeep(path); } function baseIteratee(value) { if (typeof value == "function") { return value; } if (value == null) { return identity; } if (typeof value == "object") { return isArray(value) ? baseMatchesProperty(value[0], value[1]) : baseMatches(value); } return property(value); } function createBaseFor(fromRight) { return function(object, iteratee, keysFunc) { var index = -1, iterable = Object(object), props = keysFunc(object), length = props.length; while (length--) { var key = props[fromRight ? length : ++index]; if (iteratee(iterable[key], key, iterable) === false) { break; } } return object; }; } var baseFor = createBaseFor(); const baseFor$1 = baseFor; function baseForOwn(object, iteratee) { return object && baseFor$1(object, iteratee, keys); } function createBaseEach(eachFunc, fromRight) { return function(collection, iteratee) { if (collection == null) { return collection; } if (!isArrayLike(collection)) { return eachFunc(collection, iteratee); } var length = collection.length, index = fromRight ? length : -1, iterable = Object(collection); while (fromRight ? index-- : ++index < length) { if (iteratee(iterable[index], index, iterable) === false) { break; } } return collection; }; } var baseEach = createBaseEach(baseForOwn); const baseEach$1 = baseEach; var now = function() { return root.Date.now(); }; const now$1 = now; var objectProto$1 = Object.prototype; var hasOwnProperty$1 = objectProto$1.hasOwnProperty; var defaults = baseRest(function(object, sources) { object = Object(object); var index = -1; var length = sources.length; var guard = length > 2 ? sources[2] : void 0; if (guard && isIterateeCall(sources[0], sources[1], guard)) { length = 1; } while (++index < length) { var source = sources[index]; var props = keysIn(source); var propsIndex = -1; var propsLength = props.length; while (++propsIndex < propsLength) { var key = props[propsIndex]; var value = object[key]; if (value === void 0 || eq(value, objectProto$1[key]) && !hasOwnProperty$1.call(object, key)) { object[key] = source[key]; } } } return object; }); const defaults$1 = defaults; function assignMergeValue(object, key, value) { if (value !== void 0 && !eq(object[key], value) || value === void 0 && !(key in object)) { baseAssignValue(object, key, value); } } function isArrayLikeObject(value) { return isObjectLike(value) && isArrayLike(value); } function safeGet(object, key) { if (key === "constructor" && typeof object[key] === "function") { return; } if (key == "__proto__") { return; } return object[key]; } function toPlainObject(value) { return copyObject(value, keysIn(value)); } function baseMergeDeep(object, source, key, srcIndex, mergeFunc, customizer, stack) { var objValue = safeGet(object, key), srcValue = safeGet(source, key), stacked = stack.get(srcValue); if (stacked) { assignMergeValue(object, key, stacked); return; } var newValue = customizer ? customizer(objValue, srcValue, key + "", object, source, stack) : void 0; var isCommon = newValue === void 0; if (isCommon) { var isArr = isArray(srcValue), isBuff = !isArr && isBuffer(srcValue), isTyped = !isArr && !isBuff && isTypedArray(srcValue); newValue = srcValue; if (isArr || isBuff || isTyped) { if (isArray(objValue)) { newValue = objValue; } else if (isArrayLikeObject(objValue)) { newValue = copyArray(objValue); } else if (isBuff) { isCommon = false; newValue = cloneBuffer(srcValue, true); } else if (isTyped) { isCommon = false; newValue = cloneTypedArray(srcValue, true); } else { newValue = []; } } else if (isPlainObject(srcValue) || isArguments(srcValue)) { newValue = objValue; if (isArguments(objValue)) { newValue = toPlainObject(objValue); } else if (!isObject(objValue) || isFunction(objValue)) { newValue = initCloneObject(srcValue); } } else { isCommon = false; } } if (isCommon) { stack.set(srcValue, newValue); mergeFunc(newValue, srcValue, srcIndex, customizer, stack); stack["delete"](srcValue); } assignMergeValue(object, key, newValue); } function baseMerge(object, source, srcIndex, customizer, stack) { if (object === source) { return; } baseFor$1(source, function(srcValue, key) { stack || (stack = new Stack()); if (isObject(srcValue)) { baseMergeDeep(object, source, key, srcIndex, baseMerge, customizer, stack); } else { var newValue = customizer ? customizer(safeGet(object, key), srcValue, key + "", object, source, stack) : void 0; if (newValue === void 0) { newValue = srcValue; } assignMergeValue(object, key, newValue); } }, keysIn); } function arrayIncludesWith(array, value, comparator) { var index = -1, length = array == null ? 0 : array.length; while (++index < length) { if (comparator(value, array[index])) { return true; } } return false; } function last(array) { var length = array == null ? 0 : array.length; return length ? array[length - 1] : void 0; } function castFunction(value) { return typeof value == "function" ? value : identity; } function forEach(collection, iteratee) { var func = isArray(collection) ? arrayEach : baseEach$1; return func(collection, castFunction(iteratee)); } function baseFilter(collection, predicate) { var result = []; baseEach$1(collection, function(value, index, collection2) { if (predicate(value, index, collection2)) { result.push(value); } }); return result; } function filter(collection, predicate) { var func = isArray(collection) ? arrayFilter : baseFilter; return func(collection, baseIteratee(predicate)); } function createFind(findIndexFunc) { return function(collection, predicate, fromIndex) { var iterable = Object(collection); if (!isArrayLike(collection)) { var iteratee = baseIteratee(predicate); collection = keys(collection); predicate = function(key) { return iteratee(iterable[key], key, iterable); }; } var index = findIndexFunc(collection, predicate, fromIndex); return index > -1 ? iterable[iteratee ? collection[index] : index] : void 0; }; } var nativeMax$1 = Math.max; function findIndex(array, predicate, fromIndex) { var length = array == null ? 0 : array.length; if (!length) { return -1; } var index = fromIndex == null ? 0 : toInteger(fromIndex); if (index < 0) { index = nativeMax$1(length + index, 0); } return baseFindIndex(array, baseIteratee(predicate), index); } var find = createFind(findIndex); const find$1 = find; function baseMap(collection, iteratee) { var index = -1, result = isArrayLike(collection) ? Array(collection.length) : []; baseEach$1(collection, function(value, key, collection2) { result[++index] = iteratee(value, key, collection2); }); return result; } function map(collection, iteratee) { var func = isArray(collection) ? arrayMap : baseMap; return func(collection, baseIteratee(iteratee)); } function forIn(object, iteratee) { return object == null ? object : baseFor$1(object, castFunction(iteratee), keysIn); } function baseGt(value, other) { return value > other; } var objectProto = Object.prototype; var hasOwnProperty = objectProto.hasOwnProperty; function baseHas(object, key) { return object != null && hasOwnProperty.call(object, key); } function has(object, path) { return object != null && hasPath(object, path, baseHas); } function baseValues(object, props) { return arrayMap(props, function(key) { return object[key]; }); } function values(object) { return object == null ? [] : baseValues(object, keys(object)); } function isUndefined(value) { return value === void 0; } function baseLt(value, other) { return value < other; } function mapValues(object, iteratee) { var result = {}; iteratee = baseIteratee(iteratee); baseForOwn(object, function(value, key, object2) { baseAssignValue(result, key, iteratee(value, key, object2)); }); return result; } function baseExtremum(array, iteratee, comparator) { var index = -1, length = array.length; while (++index < length) { var value = array[index], current = iteratee(value); if (current != null && (computed === void 0 ? current === current && !isSymbol(current) : comparator(current, computed))) { var computed = current, result = value; } } return result; } function max(array) { return array && array.length ? baseExtremum(array, identity, baseGt) : void 0; } var merge = createAssigner(function(object, source, srcIndex) { baseMerge(object, source, srcIndex); }); const merge$1 = merge; function min(array) { return array && array.length ? baseExtremum(array, identity, baseLt) : void 0; } function minBy(array, iteratee) { return array && array.length ? baseExtremum(array, baseIteratee(iteratee), baseLt) : void 0; } function baseSet(object, path, value, customizer) { if (!isObject(object)) { return object; } path = castPath(path, object); var index = -1, length = path.length, lastIndex = length - 1, nested = object; while (nested != null && ++index < length) { var key = toKey(path[index]), newValue = value; if (key === "__proto__" || key === "constructor" || key === "prototype") { return object; } if (index != lastIndex) { var objValue = nested[key]; newValue = customizer ? customizer(objValue, key, nested) : void 0; if (newValue === void 0) { newValue = isObject(objValue) ? objValue : isIndex(path[index + 1]) ? [] : {}; } } assignValue(nested, key, newValue); nested = nested[key]; } return object; } function basePickBy(object, paths, predicate) { var index = -1, length = paths.length, result = {}; while (++index < length) { var path = paths[index], value = baseGet(object, path); if (predicate(value, path)) { baseSet(result, castPath(path, object), value); } } return result; } function baseSortBy(array, comparer) { var length = array.length; array.sort(comparer); while (length--) { array[length] = array[length].value; } return array; } function compareAscending(value, other) { if (value !== other) { var valIsDefined = value !== void 0, valIsNull = value === null, valIsReflexive = value === value, valIsSymbol = isSymbol(value); var othIsDefined = other !== void 0, othIsNull = other === null, othIsReflexive = other === other, othIsSymbol = isSymbol(other); if (!othIsNull && !othIsSymbol && !valIsSymbol && value > other || valIsSymbol && othIsDefined && othIsReflexive && !othIsNull && !othIsSymbol || valIsNull && othIsDefined && othIsReflexive || !valIsDefined && othIsReflexive || !valIsReflexive) { return 1; } if (!valIsNull && !valIsSymbol && !othIsSymbol && value < other || othIsSymbol && valIsDefined && valIsReflexive && !valIsNull && !valIsSymbol || othIsNull && valIsDefined && valIsReflexive || !othIsDefined && valIsReflexive || !othIsReflexive) { return -1; } } return 0; } function compareMultiple(object, other, orders) { var index = -1, objCriteria = object.criteria, othCriteria = other.criteria, length = objCriteria.length, ordersLength = orders.length; while (++index < length) { var result = compareAscending(objCriteria[index], othCriteria[index]); if (result) { if (index >= ordersLength) { return result; } var order2 = orders[index]; return result * (order2 == "desc" ? -1 : 1); } } return object.index - other.index; } function baseOrderBy(collection, iteratees, orders) { if (iteratees.length) { iteratees = arrayMap(iteratees, function(iteratee) { if (isArray(iteratee)) { return function(value) { return baseGet(value, iteratee.length === 1 ? iteratee[0] : iteratee); }; } return iteratee; }); } else { iteratees = [identity]; } var index = -1; iteratees = arrayMap(iteratees, baseUnary(baseIteratee)); var result = baseMap(collection, function(value, key, collection2) { var criteria = arrayMap(iteratees, function(iteratee) { return iteratee(value); }); return { "criteria": criteria, "index": ++index, "value": value }; }); return baseSortBy(result, function(object, other) { return compareMultiple(object, other, orders); }); } function basePick(object, paths) { return basePickBy(object, paths, function(value, path) { return hasIn(object, path); }); } var pick = flatRest(function(object, paths) { return object == null ? {} : basePick(object, paths); }); const pick$1 = pick; var nativeCeil = Math.ceil, nativeMax = Math.max; function baseRange(start, end, step, fromRight) { var index = -1, length = nativeMax(nativeCeil((end - start) / (step || 1)), 0), result = Array(length); while (length--) { result[fromRight ? length : ++index] = start; start += step; } return result; } function createRange(fromRight) { return function(start, end, step) { if (step && typeof step != "number" && isIterateeCall(start, end, step)) { end = step = void 0; } start = toFinite(start); if (end === void 0) { end = start; start = 0; } else { end = toFinite(end); } step = step === void 0 ? start < end ? 1 : -1 : toFinite(step); return baseRange(start, end, step, fromRight); }; } var range = createRange(); const range$1 = range; function baseReduce(collection, iteratee, accumulator, initAccum, eachFunc) { eachFunc(collection, function(value, index, collection2) { accumulator = initAccum ? (initAccum = false, value) : iteratee(accumulator, value, index, collection2); }); return accumulator; } function reduce(collection, iteratee, accumulator) { var func = isArray(collection) ? arrayReduce : baseReduce, initAccum = arguments.length < 3; return func(collection, baseIteratee(iteratee), accumulator, initAccum, baseEach$1); } var sortBy = baseRest(function(collection, iteratees) { if (collection == null) { return []; } var length = iteratees.length; if (length > 1 && isIterateeCall(collection, iteratees[0], iteratees[1])) { iteratees = []; } else if (length > 2 && isIterateeCall(iteratees[0], iteratees[1], iteratees[2])) { iteratees = [iteratees[0]]; } return baseOrderBy(collection, baseFlatten(iteratees, 1), []); }); const sortBy$1 = sortBy; var INFINITY = 1 / 0; var createSet = !(Set && 1 / setToArray(new Set([, -0]))[1] == INFINITY) ? noop : function(values2) { return new Set(values2); }; const createSet$1 = createSet; var LARGE_ARRAY_SIZE = 200; function baseUniq(array, iteratee, comparator) { var index = -1, includes = arrayIncludes, length = array.length, isCommon = true, result = [], seen = result; if (comparator) { isCommon = false; includes = arrayIncludesWith; } else if (length >= LARGE_ARRAY_SIZE) { var set = iteratee ? null : createSet$1(array); if (set) { return setToArray(set); } isCommon = false; includes = cacheHas; seen = new SetCache(); } else { seen = iteratee ? [] : result; } outer: while (++index < length) { var value = array[index], computed = iteratee ? iteratee(value) : value; value = comparator || value !== 0 ? value : 0; if (isCommon && computed === computed) { var seenIndex = seen.length; while (seenIndex--) { if (seen[seenIndex] === computed) { continue outer; } } if (iteratee) { seen.push(computed); } result.push(value); } else if (!includes(seen, computed, comparator)) { if (seen !== result) { seen.push(computed); } result.push(value); } } return result; } var union = baseRest(function(arrays) { return baseUniq(baseFlatten(arrays, 1, isArrayLikeObject, true)); }); const union$1 = union; var idCounter = 0; function uniqueId(prefix) { var id = ++idCounter; return toString(prefix) + id; } function baseZipObject(props, values2, assignFunc) { var index = -1, length = props.length, valsLength = values2.length, result = {}; while (++index < length) { var value = index < valsLength ? values2[index] : void 0; assignFunc(result, props[index], value); } return result; } function zipObject(props, values2) { return baseZipObject(props || [], values2 || [], assignValue); } var DEFAULT_EDGE_NAME = "\0"; var GRAPH_NODE = "\0"; var EDGE_KEY_DELIM = ""; class Graph { constructor(opts = {}) { this._isDirected = has(opts, "directed") ? opts.directed : true; this._isMultigraph = has(opts, "multigraph") ? opts.multigraph : false; this._isCompound = has(opts, "compound") ? opts.compound : false; this._label = void 0; this._defaultNodeLabelFn = constant(void 0); this._defaultEdgeLabelFn = constant(void 0); this._nodes = {}; if (this._isCompound) { this._parent = {}; this._children = {}; this._children[GRAPH_NODE] = {}; } this._in = {}; this._preds = {}; this._out = {}; this._sucs = {}; this._edgeObjs = {}; this._edgeLabels = {}; } /* === Graph functions ========= */ isDirected() { return this._isDirected; } isMultigraph() { return this._isMultigraph; } isCompound() { return this._isCompound; } setGraph(label) { this._label = label; return this; } graph() { return this._label; } /* === Node functions ========== */ setDefaultNodeLabel(newDefault) { if (!isFunction(newDefault)) { newDefault = constant(newDefault); } this._defaultNodeLabelFn = newDefault; return this; } nodeCount() { return this._nodeCount; } nodes() { return keys(this._nodes); } sources() { var self = this; return filter(this.nodes(), function(v) { return isEmpty(self._in[v]); }); } sinks() { var self = this; return filter(this.nodes(), function(v) { return isEmpty(self._out[v]); }); } setNodes(vs, value) { var args = arguments; var self = this; forEach(vs, function(v) { if (args.length > 1) { self.setNode(v, value); } else { self.setNode(v); } }); return this; } setNode(v, value) { if (has(this._nodes, v)) { if (arguments.length > 1) { this._nodes[v] = value; } return this; } this._nodes[v] = arguments.length > 1 ? value : this._defaultNodeLabelFn(v); if (this._isCompound) { this._parent[v] = GRAPH_NODE; this._children[v] = {}; this._children[GRAPH_NODE][v] = true; } this._in[v] = {}; this._preds[v] = {}; this._out[v] = {}; this._sucs[v] = {}; ++this._nodeCount; return this; } node(v) { return this._nodes[v]; } hasNode(v) { return has(this._nodes, v); } removeNode(v) { var self = this; if (has(this._nodes, v)) { var removeEdge = function(e) { self.removeEdge(self._edgeObjs[e]); }; delete this._nodes[v]; if (this._isCompound) { this._removeFromParentsChildList(v); delete this._parent[v]; forEach(this.children(v), function(child) { self.setParent(child); }); delete this._children[v]; } forEach(keys(this._in[v]), removeEdge); delete this._in[v]; delete this._preds[v]; forEach(keys(this._out[v]), removeEdge); delete this._out[v]; delete this._sucs[v]; --this._nodeCount; } return this; } setParent(v, parent) { if (!this._isCompound) { throw new Error("Cannot set parent in a non-compound graph"); } if (isUndefined(parent)) { parent = GRAPH_NODE; } else { parent += ""; for (var ancestor = parent; !isUndefined(ancestor); ancestor = this.parent(ancestor)) { if (ancestor === v) { throw new Error("Setting " + parent + " as parent of " + v + " would create a cycle"); } } this.setNode(parent); } this.setNode(v); this._removeFromParentsChildList(v); this._parent[v] = parent; this._children[parent][v] = true; return this; } _removeFromParentsChildList(v) { delete this._children[this._parent[v]][v]; } parent(v) { if (this._isCompound) { var parent = this._parent[v]; if (parent !== GRAPH_NODE) { return parent; } } } children(v) { if (isUndefined(v)) { v = GRAPH_NODE; } if (this._isCompound) { var children = this._children[v]; if (children) { return keys(children); } } else if (v === GRAPH_NODE) { return this.nodes(); } else if (this.hasNode(v)) { return []; } } predecessors(v) { var predsV = this._preds[v]; if (predsV) { return keys(predsV); } } successors(v) { var sucsV = this._sucs[v]; if (sucsV) { return keys(sucsV); } } neighbors(v) { var preds = this.predecessors(v); if (preds) { return union$1(preds, this.successors(v)); } } isLeaf(v) { var neighbors; if (this.isDirected()) { neighbors = this.successors(v); } else { neighbors = this.neighbors(v); } return neighbors.length === 0; } filterNodes(filter2) { var copy = new this.constructor({ directed: this._isDirected, multigraph: this._isMultigraph, compound: this._isCompound }); copy.setGraph(this.graph()); var self = this; forEach(this._nodes, function(value, v) { if (filter2(v)) { copy.setNode(v, value); } }); forEach(this._edgeObjs, function(e) { if (copy.hasNode(e.v) && copy.hasNode(e.w)) { copy.setEdge(e, self.edge(e)); } }); var parents = {}; function findParent(v) { var parent = self.parent(v); if (parent === void 0 || copy.hasNode(parent)) { parents[v] = parent; return parent; } else if (parent in parents) { return parents[parent]; } else { return findParent(parent); } } if (this._isCompound) { forEach(copy.nodes(), function(v) { copy.setParent(v, findParent(v)); }); } return copy; } /* === Edge functions ========== */ setDefaultEdgeLabel(newDefault) { if (!isFunction(newDefault)) { newDefault = constant(newDefault); } this._defaultEdgeLabelFn = newDefault; return this; } edgeCount() { return this._edgeCount; } edges() { return values(this._edgeObjs); } setPath(vs, value) { var self = this; var args = arguments; reduce(vs, function(v, w) { if (args.length > 1) { self.setEdge(v, w, value); } else { self.setEdge(v, w); } return w; }); return this; } /* * setEdge(v, w, [value, [name]]) * setEdge({ v, w, [name] }, [value]) */ setEdge() { var v, w, name, value; var valueSpecified = false; var arg0 = arguments[0]; if (typeof arg0 === "object" && arg0 !== null && "v" in arg0) { v = arg0.v; w = arg0.w; name = arg0.name; if (arguments.length === 2) { value = arguments[1]; valueSpecified = true; } } else { v = arg0; w = arguments[1]; name = arguments[3]; if (arguments.length > 2) { value = arguments[2]; valueSpecified = true; } } v = "" + v; w = "" + w; if (!isUndefined(name)) { name = "" + name; } var e = edgeArgsToId(this._isDirected, v, w, name); if (has(this._edgeLabels, e)) { if (valueSpecified) { this._edgeLabels[e] = value; } return this; } if (!isUndefined(name) && !this._isMultigraph) { throw new Error("Cannot set a named edge when isMultigraph = false"); } this.setNode(v); this.setNode(w); this._edgeLabels[e] = valueSpecified ? value : this._defaultEdgeLabelFn(v, w, name); var edgeObj = edgeArgsToObj(this._isDirected, v, w, name); v = edgeObj.v; w = edgeObj.w; Object.freeze(edgeObj); this._edgeObjs[e] = edgeObj; incrementOrInitEntry(this._preds[w], v); incrementOrInitEntry(this._sucs[v], w); this._in[w][e] = edgeObj; this._out[v][e] = edgeObj; this._edgeCount++; return this; } edge(v, w, name) { var e = arguments.length === 1 ? edgeObjToId(this._isDirected, arguments[0]) : edgeArgsToId(this._isDirected, v, w, name); return this._edgeLabels[e]; } hasEdge(v, w, name) { var e = arguments.length === 1 ? edgeObjToId(this._isDirected, arguments[0]) : edgeArgsToId(this._isDirected, v, w, name); return has(this._edgeLabels, e); } removeEdge(v, w, name) { var e = arguments.length === 1 ? edgeObjToId(this._isDirected, arguments[0]) : edgeArgsToId(this._isDirected, v, w, name); var edge = this._edgeObjs[e]; if (edge) { v = edge.v; w = edge.w; delete this._edgeLabels[e]; delete this._edgeObjs[e]; decrementOrRemoveEntry(this._preds[w], v); decrementOrRemoveEntry(this._sucs[v], w); delete this._in[w][e]; delete this._out[v][e]; this._edgeCount--; } return this; } inEdges(v, u) { var inV = this._in[v]; if (inV) { var edges = values(inV); if (!u) { return edges; } return filter(edges, function(edge) { return edge.v === u; }); } } outEdges(v, w) { var outV = this._out[v]; if (outV) { var edges = values(outV); if (!w) { return edges; } return filter(edges, function(edge) { return edge.w === w; }); } } nodeEdges(v, w) { var inEdges = this.inEdges(v, w); if (inEdges) { return inEdges.concat(this.outEdges(v, w)); } } } Graph.prototype._nodeCount = 0; Graph.prototype._edgeCount = 0; function incrementOrInitEntry(map2, k) { if (map2[k]) { map2[k]++; } else { map2[k] = 1; } } function decrementOrRemoveEntry(map2, k) { if (!--map2[k]) { delete map2[k]; } } function edgeArgsToId(isDirected, v_, w_, name) { var v = "" + v_; var w = "" + w_; if (!isDirected && v > w) { var tmp = v; v = w; w = tmp; } return v + EDGE_KEY_DELIM + w + EDGE_KEY_DELIM + (isUndefined(name) ? DEFAULT_EDGE_NAME : name); } function edgeArgsToObj(isDirected, v_, w_, name) { var v = "" + v_; var w = "" + w_; if (!isDirected && v > w) { var tmp = v; v = w; w = tmp; } var edgeObj = { v, w }; if (name) { edgeObj.name = name; } return edgeObj; } function edgeObjToId(isDirected, edgeObj) { return edgeArgsToId(isDirected, edgeObj.v, edgeObj.w, edgeObj.name); } class List { constructor() { var sentinel = {}; sentinel._next = sentinel._prev = sentinel; this._sentinel = sentinel; } dequeue() { var sentinel = this._sentinel; var entry = sentinel._prev; if (entry !== sentinel) { unlink(entry); return entry; } } enqueue(entry) { var sentinel = this._sentinel; if (entry._prev && entry._next) { unlink(entry); } entry._next = sentinel._next; sentinel._next._prev = entry; sentinel._next = entry; entry._prev = sentinel; } toString() { var strs = []; var sentinel = this._sentinel; var curr = sentinel._prev; while (curr !== sentinel) { strs.push(JSON.stringify(curr, filterOutLinks)); curr = curr._prev; } return "[" + strs.join(", ") + "]"; } } function unlink(entry) { entry._prev._next = entry._next; entry._next._prev = entry._prev; delete entry._next; delete entry._prev; } function filterOutLinks(k, v) { if (k !== "_next" && k !== "_prev") { return v; } } var DEFAULT_WEIGHT_FN = constant(1); function greedyFAS(g, weightFn) { if (g.nodeCount() <= 1) { return []; } var state = buildState(g, weightFn || DEFAULT_WEIGHT_FN); var results = doGreedyFAS(state.graph, state.buckets, state.zeroIdx); return flatten( map(results, function(e) { return g.outEdges(e.v, e.w); }) ); } function doGreedyFAS(g, buckets, zeroIdx) { var results = []; var sources = buckets[buckets.length - 1]; var sinks = buckets[0]; var entry; while (g.nodeCount()) { while (entry = sinks.dequeue()) { removeNode(g, buckets, zeroIdx, entry); } while (entry = sources.dequeue()) { removeNode(g, buckets, zeroIdx, entry); } if (g.nodeCount()) { for (var i = buckets.length - 2; i > 0; --i) { entry = buckets[i].dequeue(); if (entry) { results = results.concat(removeNode(g, buckets, zeroIdx, entry, true)); break; } } } } return results; } function removeNode(g, buckets, zeroIdx, entry, collectPredecessors) { var results = collectPredecessors ? [] : void 0; forEach(g.inEdges(entry.v), function(edge) { var weight = g.edge(edge); var uEntry = g.node(edge.v); if (collectPredecessors) { results.push({ v: edge.v, w: edge.w }); } uEntry.out -= weight; assignBucket(buckets, zeroIdx, uEntry); }); forEach(g.outEdges(entry.v), function(edge) { var weight = g.edge(edge); var w = edge.w; var wEntry = g.node(w); wEntry["in"] -= weight; assignBucket(buckets, zeroIdx, wEntry); }); g.removeNode(entry.v); return results; } function buildState(g, weightFn) { var fasGraph = new Graph(); var maxIn = 0; var maxOut = 0; forEach(g.nodes(), function(v) { fasGraph.setNode(v, { v, in: 0, out: 0 }); }); forEach(g.edges(), function(e) { var prevWeight = fasGraph.edge(e.v, e.w) || 0; var weight = weightFn(e); var edgeWeight = prevWeight + weight; fasGraph.setEdge(e.v, e.w, edgeWeight); maxOut = Math.max(maxOut, fasGraph.node(e.v).out += weight); maxIn = Math.max(maxIn, fasGraph.node(e.w)["in"] += weight); }); var buckets = range$1(maxOut + maxIn + 3).map(function() { return new List(); }); var zeroIdx = maxIn + 1; forEach(fasGraph.nodes(), function(v) { assignBucket(buckets, zeroIdx, fasGraph.node(v)); }); return { graph: fasGraph, buckets, zeroIdx }; } function assignBucket(buckets, zeroIdx, entry) { if (!entry.out) { buckets[0].enqueue(entry); } else if (!entry["in"]) { buckets[buckets.length - 1].enqueue(entry); } else { buckets[entry.out - entry["in"] + zeroIdx].enqueue(entry); } } function run$2(g) { var fas = g.graph().acyclicer === "greedy" ? greedyFAS(g, weightFn(g)) : dfsFAS(g); forEach(fas, function(e) { var label = g.edge(e); g.removeEdge(e); label.forwardName = e.name; label.reversed = true; g.setEdge(e.w, e.v, label, uniqueId("rev")); }); function weightFn(g2) { return function(e) { return g2.edge(e).weight; }; } } function dfsFAS(g) { var fas = []; var stack = {}; var visited = {}; function dfs2(v) { if (has(visited, v)) { return; } visited[v] = true; stack[v] = true; forEach(g.outEdges(v), function(e) { if (has(stack, e.w)) { fas.push(e); } else { dfs2(e.w); } }); delete stack[v]; } forEach(g.nodes(), dfs2); return fas; } function undo$2(g) { forEach(g.edges(), function(e) { var label = g.edge(e); if (label.reversed) { g.removeEdge(e); var forwardName = label.forwardName; delete label.reversed; delete label.forwardName; g.setEdge(e.w, e.v, label, forwardName); } }); } function addDummyNode(g, type, attrs, name) { var v; do { v = uniqueId(name); } while (g.hasNode(v)); attrs.dummy = type; g.setNode(v, attrs); return v; } function simplify(g) { var simplified = new Graph().setGraph(g.graph()); forEach(g.nodes(), function(v) { simplified.setNode(v, g.node(v)); }); forEach(g.edges(), function(e) { var simpleLabel = simplified.edge(e.v, e.w) || { weight: 0, minlen: 1 }; var label = g.edge(e); simplified.setEdge(e.v, e.w, { weight: simpleLabel.weight + label.weight, minlen: Math.max(simpleLabel.minlen, label.minlen) }); }); return simplified; } function asNonCompoundGraph(g) { var simplified = new Graph({ multigraph: g.isMultigraph() }).setGraph(g.graph()); forEach(g.nodes(), function(v) { if (!g.children(v).length) { simplified.setNode(v, g.node(v)); } }); forEach(g.edges(), function(e) { simplified.setEdge(e, g.edge(e)); }); return simplified; } function intersectRect(rect, point) { var x = rect.x; var y = rect.y; var dx = point.x - x; var dy = point.y - y; var w = rect.width / 2; var h = rect.height / 2; if (!dx && !dy) { throw new Error("Not possible to find intersection inside of the rectangle"); } var sx, sy; if (Math.abs(dy) * w > Math.abs(dx) * h) { if (dy < 0) { h = -h; } sx = h * dx / dy; sy = h; } else { if (dx < 0) { w = -w; } sx = w; sy = w * dy / dx; } return { x: x + sx, y: y + sy }; } function buildLayerMatrix(g) { var layering = map(range$1(maxRank(g) + 1), function() { return []; }); forEach(g.nodes(), function(v) { var node = g.node(v); var rank2 = node.rank; if (!isUndefined(rank2)) { layering[rank2][node.order] = v; } }); return layering; } function normalizeRanks(g) { var min$1 = min( map(g.nodes(), function(v) { return g.node(v).rank; }) ); forEach(g.nodes(), function(v) { var node = g.node(v); if (has(node, "rank")) { node.rank -= min$1; } }); } function removeEmptyRanks(g) { var offset = min( map(g.nodes(), function(v) { return g.node(v).rank; }) ); var layers = []; forEach(g.nodes(), function(v) { var rank2 = g.node(v).rank - offset; if (!layers[rank2]) { layers[rank2] = []; } layers[rank2].push(v); }); var delta = 0; var nodeRankFactor = g.graph().nodeRankFactor; forEach(layers, function(vs, i) { if (isUndefined(vs) && i % nodeRankFactor !== 0) { --delta; } else if (delta) { forEach(vs, function(v) { g.node(v).rank += delta; }); } }); } function addBorderNode$1(g, prefix, rank2, order2) { var node = { width: 0, height: 0 }; if (arguments.length >= 4) { node.rank = rank2; node.order = order2; } return addDummyNode(g, "border", node, prefix); } function maxRank(g) { return max( map(g.nodes(), function(v) { var rank2 = g.node(v).rank; if (!isUndefined(rank2)) { return rank2; } }) ); } function partition(collection, fn) { var result = { lhs: [], rhs: [] }; forEach(collection, function(value) { if (fn(value)) { result.lhs.push(value); } else { result.rhs.push(value); } }); return result; } function time(name, fn) { var start = now$1(); try { return fn(); } finally { console.log(name + " time: " + (now$1() - start) + "ms"); } } function notime(name, fn) { return fn(); } function addBorderSegments(g) { function dfs2(v) { var children = g.children(v); var node = g.node(v); if (children.length) { forEach(children, dfs2); } if (has(node, "minRank")) { node.borderLeft = []; node.borderRight = []; for (var rank2 = node.minRank, maxRank2 = node.maxRank + 1; rank2 < maxRank2; ++rank2) { addBorderNode(g, "borderLeft", "_bl", v, node, rank2); addBorderNode(g, "borderRight", "_br", v, node, rank2); } } } forEach(g.children(), dfs2); } function addBorderNode(g, prop, prefix, sg, sgNode, rank2) { var label = { width: 0, height: 0, rank: rank2, borderType: prop }; var prev = sgNode[prop][rank2 - 1]; var curr = addDummyNode(g, "border", label, prefix); sgNode[prop][rank2] = curr; g.setParent(curr, sg); if (prev) { g.setEdge(prev, curr, { weight: 1 }); } } function adjust(g) { var rankDir = g.graph().rankdir.toLowerCase(); if (rankDir === "lr" || rankDir === "rl") { swapWidthHeight(g); } } function undo$1(g) { var rankDir = g.graph().rankdir.toLowerCase(); if (rankDir === "bt" || rankDir === "rl") { reverseY(g); } if (rankDir === "lr" || rankDir === "rl") { swapXY(g); swapWidthHeight(g); } } function swapWidthHeight(g) { forEach(g.nodes(), function(v) { swapWidthHeightOne(g.node(v)); }); forEach(g.edges(), function(e) { swapWidthHeightOne(g.edge(e)); }); } function swapWidthHeightOne(attrs) { var w = attrs.width; attrs.width = attrs.height; attrs.height = w; } function reverseY(g) { forEach(g.nodes(), function(v) { reverseYOne(g.node(v)); }); forEach(g.edges(), function(e) { var edge = g.edge(e); forEach(edge.points, reverseYOne); if (has(edge, "y")) { reverseYOne(edge); } }); } function reverseYOne(attrs) { attrs.y = -attrs.y; } function swapXY(g) { forEach(g.nodes(), function(v) { swapXYOne(g.node(v)); }); forEach(g.edges(), function(e) { var edge = g.edge(e); forEach(edge.points, swapXYOne); if (has(edge, "x")) { swapXYOne(edge); } }); } function swapXYOne(attrs) { var x = attrs.x; attrs.x = attrs.y; attrs.y = x; } function run$1(g) { g.graph().dummyChains = []; forEach(g.edges(), function(edge) { normalizeEdge(g, edge); }); } function normalizeEdge(g, e) { var v = e.v; var vRank = g.node(v).rank; var w = e.w; var wRank = g.node(w).rank; var name = e.name; var edgeLabel = g.edge(e); var labelRank = edgeLabel.labelRank; if (wRank === vRank + 1) return; g.removeEdge(e); var dummy, attrs, i; for (i = 0, ++vRank; vRank < wRank; ++i, ++vRank) { edgeLabel.points = []; attrs = { width: 0, height: 0, edgeLabel, edgeObj: e, rank: vRank }; dummy = addDummyNode(g, "edge", attrs, "_d"); if (vRank === labelRank) { attrs.width = edgeLabel.width; attrs.height = edgeLabel.height; attrs.dummy = "edge-label"; attrs.labelpos = edgeLabel.labelpos; } g.setEdge(v, dummy, { weight: edgeLabel.weight }, name); if (i === 0) { g.graph().dummyChains.push(dummy); } v = dummy; } g.setEdge(v, w, { weight: edgeLabel.weight }, name); } function undo(g) { forEach(g.graph().dummyChains, function(v) { var node = g.node(v); var origLabel = node.edgeLabel; var w; g.setEdge(node.edgeObj, origLabel); while (node.dummy) { w = g.successors(v)[0]; g.removeNode(v); origLabel.points.push({ x: node.x, y: node.y }); if (node.dummy === "edge-label") { origLabel.x = node.x; origLabel.y = node.y; origLabel.width = node.width; origLabel.height = node.height; } v = w; node = g.node(v); } }); } function longestPath(g) { var visited = {}; function dfs2(v) { var label = g.node(v); if (has(visited, v)) { return label.rank; } visited[v] = true; var rank2 = min( map(g.outEdges(v), function(e) { return dfs2(e.w) - g.edge(e).minlen; }) ); if (rank2 === Number.POSITIVE_INFINITY || // return value of _.map([]) for Lodash 3 rank2 === void 0 || // return value of _.map([]) for Lodash 4 rank2 === null) { rank2 = 0; } return label.rank = rank2; } forEach(g.sources(), dfs2); } function slack(g, e) { return g.node(e.w).rank - g.node(e.v).rank - g.edge(e).minlen; } function feasibleTree(g) { var t = new Graph({ directed: false }); var start = g.nodes()[0]; var size = g.nodeCount(); t.setNode(start, {}); var edge, delta; while (tightTree(t, g) < size) { edge = findMinSlackEdge(t, g); delta = t.hasNode(edge.v) ? slack(g, edge) : -slack(g, edge); shiftRanks(t, g, delta); } return t; } function tightTree(t, g) { function dfs2(v) { forEach(g.nodeEdges(v), function(e) { var edgeV = e.v, w = v === edgeV ? e.w : edgeV; if (!t.hasNode(w) && !slack(g, e)) { t.setNode(w, {}); t.setEdge(v, w, {}); dfs2(w); } }); } forEach(t.nodes(), dfs2); return t.nodeCount(); } function findMinSlackEdge(t, g) { return minBy(g.edges(), function(e) { if (t.hasNode(e.v) !== t.hasNode(e.w)) { return slack(g, e); } }); } function shiftRanks(t, g, delta) { forEach(t.nodes(), function(v) { g.node(v).rank += delta; }); } function CycleException() { } CycleException.prototype = new Error(); function dfs$1(g, vs, order2) { if (!isArray(vs)) { vs = [vs]; } var navigation = (g.isDirected() ? g.successors : g.neighbors).bind(g); var acc = []; var visited = {}; forEach(vs, function(v) { if (!g.hasNode(v)) { throw new Error("Graph does not have node: " + v); } doDfs(g, v, order2 === "post", visited, navigation, acc); }); return acc; } function doDfs(g, v, postorder2, visited, navigation, acc) { if (!has(visited, v)) { visited[v] = true; if (!postorder2) { acc.push(v); } forEach(navigation(v), function(w) { doDfs(g, w, postorder2, visited, navigation, acc); }); if (postorder2) { acc.push(v); } } } function postorder$1(g, vs) { return dfs$1(g, vs, "post"); } function preorder(g, vs) { return dfs$1(g, vs, "pre"); } networkSimplex.initLowLimValues = initLowLimValues; networkSimplex.initCutValues = initCutValues; networkSimplex.calcCutValue = calcCutValue; networkSimplex.leaveEdge = leaveEdge; networkSimplex.enterEdge = enterEdge; networkSimplex.exchangeEdges = exchangeEdges; function networkSimplex(g) { g = simplify(g); longestPath(g); var t = feasibleTree(g); initLowLimValues(t); initCutValues(t, g); var e, f; while (e = leaveEdge(t)) { f = enterEdge(t, g, e); exchangeEdges(t, g, e, f); } } function initCutValues(t, g) { var vs = postorder$1(t, t.nodes()); vs = vs.slice(0, vs.length - 1); forEach(vs, function(v) { assignCutValue(t, g, v); }); } function assignCutValue(t, g, child) { var childLab = t.node(child); var parent = childLab.parent; t.edge(child, parent).cutvalue = calcCutValue(t, g, child); } function calcCutValue(t, g, child) { var childLab = t.node(child); var parent = childLab.parent; var childIsTail = true; var graphEdge = g.edge(child, parent); var cutValue = 0; if (!graphEdge) { childIsTail = false; graphEdge = g.edge(parent, child); } cutValue = graphEdge.weight; forEach(g.nodeEdges(child), function(e) { var isOutEdge = e.v === child, other = isOutEdge ? e.w : e.v; if (other !== parent) { var pointsToHead = isOutEdge === childIsTail, otherWeight = g.edge(e).weight; cutValue += pointsToHead ? otherWeight : -otherWeight; if (isTreeEdge(t, child, other)) { var otherCutValue = t.edge(child, other).cutvalue; cutValue += pointsToHead ? -otherCutValue : otherCutValue; } } }); return cutValue; } function initLowLimValues(tree, root2) { if (arguments.length < 2) { root2 = tree.nodes()[0]; } dfsAssignLowLim(tree, {}, 1, root2); } function dfsAssignLowLim(tree, visited, nextLim, v, parent) { var low = nextLim; var label = tree.node(v); visited[v] = true; forEach(tree.neighbors(v), function(w) { if (!has(visited, w)) { nextLim = dfsAssignLowLim(tree, visited, nextLim, w, v); } }); label.low = low; label.lim = nextLim++; if (parent) { label.parent = parent; } else { delete label.parent; } return nextLim; } function leaveEdge(tree) { return find$1(tree.edges(), function(e) { return tree.edge(e).cutvalue < 0; }); } function enterEdge(t, g, edge) { var v = edge.v; var w = edge.w; if (!g.hasEdge(v, w)) { v = edge.w; w = edge.v; } var vLabel = t.node(v); var wLabel = t.node(w); var tailLabel = vLabel; var flip = false; if (vLabel.lim > wLabel.lim) { tailLabel = wLabel; flip = true; } var candidates = filter(g.edges(), function(edge2) { return flip === isDescendant(t, t.node(edge2.v), tailLabel) && flip !== isDescendant(t, t.node(edge2.w), tailLabel); }); return minBy(candidates, function(edge2) { return slack(g, edge2); }); } function exchangeEdges(t, g, e, f) { var v = e.v; var w = e.w; t.removeEdge(v, w); t.setEdge(f.v, f.w, {}); initLowLimValues(t); initCutValues(t, g); updateRanks(t, g); } function updateRanks(t, g) { var root2 = find$1(t.nodes(), function(v) { return !g.node(v).parent; }); var vs = preorder(t, root2); vs = vs.slice(1); forEach(vs, function(v) { var parent = t.node(v).parent, edge = g.edge(v, parent), flipped = false; if (!edge) { edge = g.edge(parent, v); flipped = true; } g.node(v).rank = g.node(parent).rank + (flipped ? edge.minlen : -edge.minlen); }); } function isTreeEdge(tree, u, v) { return tree.hasEdge(u, v); } function isDescendant(tree, vLabel, rootLabel) { return rootLabel.low <= vLabel.lim && vLabel.lim <= rootLabel.lim; } function rank(g) { switch (g.graph().ranker) { case "network-simplex": networkSimplexRanker(g); break; case "tight-tree": tightTreeRanker(g); break; case "longest-path": longestPathRanker(g); break; default: networkSimplexRanker(g); } } var longestPathRanker = longestPath; function tightTreeRanker(g) { longestPath(g); feasibleTree(g); } function networkSimplexRanker(g) { networkSimplex(g); } function run(g) { var root2 = addDummyNode(g, "root", {}, "_root"); var depths = treeDepths(g); var height = max(values(depths)) - 1; var nodeSep = 2 * height + 1; g.graph().nestingRoot = root2; forEach(g.edges(), function(e) { g.edge(e).minlen *= nodeSep; }); var weight = sumWeights(g) + 1; forEach(g.children(), function(child) { dfs(g, root2, nodeSep, weight, height, depths, child); }); g.graph().nodeRankFactor = nodeSep; } function dfs(g, root2, nodeSep, weight, height, depths, v) { var children = g.children(v); if (!children.length) { if (v !== root2) { g.setEdge(root2, v, { weight: 0, minlen: nodeSep }); } return; } var top = addBorderNode$1(g, "_bt"); var bottom = addBorderNode$1(g, "_bb"); var label = g.node(v); g.setParent(top, v); label.borderTop = top; g.setParent(bottom, v); label.borderBottom = bottom; forEach(children, function(child) { dfs(g, root2, nodeSep, weight, height, depths, child); var childNode = g.node(child); var childTop = childNode.borderTop ? childNode.borderTop : child; var childBottom = childNode.borderBottom ? childNode.borderBottom : child; var thisWeight = childNode.borderTop ? weight : 2 * weight; var minlen = childTop !== childBottom ? 1 : height - depths[v] + 1; g.setEdge(top, childTop, { weight: thisWeight, minlen, nestingEdge: true }); g.setEdge(childBottom, bottom, { weight: thisWeight, minlen, nestingEdge: true }); }); if (!g.parent(v)) { g.setEdge(root2, top, { weight: 0, minlen: height + depths[v] }); } } function treeDepths(g) { var depths = {}; function dfs2(v, depth) { var children = g.children(v); if (children && children.length) { forEach(children, function(child) { dfs2(child, depth + 1); }); } depths[v] = depth; } forEach(g.children(), function(v) { dfs2(v, 1); }); return depths; } function sumWeights(g) { return reduce( g.edges(), function(acc, e) { return acc + g.edge(e).weight; }, 0 ); } function cleanup(g) { var graphLabel = g.graph(); g.removeNode(graphLabel.nestingRoot); delete graphLabel.nestingRoot; forEach(g.edges(), function(e) { var edge = g.edge(e); if (edge.nestingEdge) { g.removeEdge(e); } }); } function addSubgraphConstraints(g, cg, vs) { var prev = {}, rootPrev; forEach(vs, function(v) { var child = g.parent(v), parent, prevChild; while (child) { parent = g.parent(child); if (parent) { prevChild = prev[parent]; prev[parent] = child; } else { prevChild = rootPrev; rootPrev = child; } if (prevChild && prevChild !== child) { cg.setEdge(prevChild, child); return; } child = parent; } }); } function buildLayerGraph(g, rank2, relationship) { var root2 = createRootNode(g), result = new Graph({ compound: true }).setGraph({ root: root2 }).setDefaultNodeLabel(function(v) { return g.node(v); }); forEach(g.nodes(), function(v) { var node = g.node(v), parent = g.parent(v); if (node.rank === rank2 || node.minRank <= rank2 && rank2 <= node.maxRank) { result.setNode(v); result.setParent(v, parent || root2); forEach(g[relationship](v), function(e) { var u = e.v === v ? e.w : e.v, edge = result.edge(u, v), weight = !isUndefined(edge) ? edge.weight : 0; result.setEdge(u, v, { weight: g.edge(e).weight + weight }); }); if (has(node, "minRank")) { result.setNode(v, { borderLeft: node.borderLeft[rank2], borderRight: node.borderRight[rank2] }); } } }); return result; } function createRootNode(g) { var v; while (g.hasNode(v = uniqueId("_root"))) ; return v; } function crossCount(g, layering) { var cc = 0; for (var i = 1; i < layering.length; ++i) { cc += twoLayerCrossCount(g, layering[i - 1], layering[i]); } return cc; } function twoLayerCrossCount(g, northLayer, southLayer) { var southPos = zipObject( southLayer, map(southLayer, function(v, i) { return i; }) ); var southEntries = flatten( map(northLayer, function(v) { return sortBy$1( map(g.outEdges(v), function(e) { return { pos: southPos[e.w], weight: g.edge(e).weight }; }), "pos" ); }) ); var firstIndex = 1; while (firstIndex < southLayer.length) firstIndex <<= 1; var treeSize = 2 * firstIndex - 1; firstIndex -= 1; var tree = map(new Array(treeSize), function() { return 0; }); var cc = 0; forEach( // @ts-expect-error southEntries.forEach(function(entry) { var index = entry.pos + firstIndex; tree[index] += entry.weight; var weightSum = 0; while (index > 0) { if (index % 2) { weightSum += tree[index + 1]; } index = index - 1 >> 1; tree[index] += entry.weight; } cc += entry.weight * weightSum; }) ); return cc; } function initOrder(g) { var visited = {}; var simpleNodes = filter(g.nodes(), function(v) { return !g.children(v).length; }); var maxRank2 = max( map(simpleNodes, function(v) { return g.node(v).rank; }) ); var layers = map(range$1(maxRank2 + 1), function() { return []; }); function dfs2(v) { if (has(visited, v)) return; visited[v] = true; var node = g.node(v); layers[node.rank].push(v); forEach(g.successors(v), dfs2); } var orderedVs = sortBy$1(simpleNodes, function(v) { return g.node(v).rank; }); forEach(orderedVs, dfs2); return layers; } function barycenter(g, movable) { return map(movable, function(v) { var inV = g.inEdges(v); if (!inV.length) { return { v }; } else { var result = reduce( inV, function(acc, e) { var edge = g.edge(e), nodeU = g.node(e.v); return { sum: acc.sum + edge.weight * nodeU.order, weight: acc.weight + edge.weight }; }, { sum: 0, weight: 0 } ); return { v, barycenter: result.sum / result.weight, weight: result.weight }; } }); } function resolveConflicts(entries, cg) { var mappedEntries = {}; forEach(entries, function(entry, i) { var tmp = mappedEntries[entry.v] = { indegree: 0, in: [], out: [], vs: [entry.v], i }; if (!isUndefined(entry.barycenter)) { tmp.barycenter = entry.barycenter; tmp.weight = entry.weight; } }); forEach(cg.edges(), function(e) { var entryV = mappedEntries[e.v]; var entryW = mappedEntries[e.w]; if (!isUndefined(entryV) && !isUndefined(entryW)) { entryW.indegree++; entryV.out.push(mappedEntries[e.w]); } }); var sourceSet = filter(mappedEntries, function(entry) { return !entry.indegree; }); return doResolveConflicts(sourceSet); } function doResolveConflicts(sourceSet) { var entries = []; function handleIn(vEntry) { return function(uEntry) { if (uEntry.merged) { return; } if (isUndefined(uEntry.barycenter) || isUndefined(vEntry.barycenter) || uEntry.barycenter >= vEntry.barycenter) { mergeEntries(vEntry, uEntry); } }; } function handleOut(vEntry) { return function(wEntry) { wEntry["in"].push(vEntry); if (--wEntry.indegree === 0) { sourceSet.push(wEntry); } }; } while (sourceSet.length) { var entry = sourceSet.pop(); entries.push(entry); forEach(entry["in"].reverse(), handleIn(entry)); forEach(entry.out, handleOut(entry)); } return map( filter(entries, function(entry2) { return !entry2.merged; }), function(entry2) { return pick$1(entry2, ["vs", "i", "barycenter", "weight"]); } ); } function mergeEntries(target, source) { var sum = 0; var weight = 0; if (target.weight) { sum += target.barycenter * target.weight; weight += target.weight; } if (source.weight) { sum += source.barycenter * source.weight; weight += source.weight; } target.vs = source.vs.concat(target.vs); target.barycenter = sum / weight; target.weight = weight; target.i = Math.min(source.i, target.i); source.merged = true; } function sort(entries, biasRight) { var parts = partition(entries, function(entry) { return has(entry, "barycenter"); }); var sortable = parts.lhs, unsortable = sortBy$1(parts.rhs, function(entry) { return -entry.i; }), vs = [], sum = 0, weight = 0, vsIndex = 0; sortable.sort(compareWithBias(!!biasRight)); vsIndex = consumeUnsortable(vs, unsortable, vsIndex); forEach(sortable, function(entry) { vsIndex += entry.vs.length; vs.push(entry.vs); sum += entry.barycenter * entry.weight; weight += entry.weight; vsIndex = consumeUnsortable(vs, unsortable, vsIndex); }); var result = { vs: flatten(vs) }; if (weight) { result.barycenter = sum / weight; result.weight = weight; } return result; } function consumeUnsortable(vs, unsortable, index) { var last$1; while (unsortable.length && (last$1 = last(unsortable)).i <= index) { unsortable.pop(); vs.push(last$1.vs); index++; } return index; } function compareWithBias(bias) { return function(entryV, entryW) { if (entryV.barycenter < entryW.barycenter) { return -1; } else if (entryV.barycenter > entryW.barycenter) { return 1; } return !bias ? entryV.i - entryW.i : entryW.i - entryV.i; }; } function sortSubgraph(g, v, cg, biasRight) { var movable = g.children(v); var node = g.node(v); var bl = node ? node.borderLeft : void 0; var br = node ? node.borderRight : void 0; var subgraphs = {}; if (bl) { movable = filter(movable, function(w) { return w !== bl && w !== br; }); } var barycenters = barycenter(g, movable); forEach(barycenters, function(entry) { if (g.children(entry.v).length) { var subgraphResult = sortSubgraph(g, entry.v, cg, biasRight); subgraphs[entry.v] = subgraphResult; if (has(subgraphResult, "barycenter")) { mergeBarycenters(entry, subgraphResult); } } }); var entries = resolveConflicts(barycenters, cg); expandSubgraphs(entries, subgraphs); var result = sort(entries, biasRight); if (bl) { result.vs = flatten([bl, result.vs, br]); if (g.predecessors(bl).length) { var blPred = g.node(g.predecessors(bl)[0]), brPred = g.node(g.predecessors(br)[0]); if (!has(result, "barycenter")) { result.barycenter = 0; result.weight = 0; } result.barycenter = (result.barycenter * result.weight + blPred.order + brPred.order) / (result.weight + 2); result.weight += 2; } } return result; } function expandSubgraphs(entries, subgraphs) { forEach(entries, function(entry) { entry.vs = flatten( entry.vs.map(function(v) { if (subgraphs[v]) { return subgraphs[v].vs; } return v; }) ); }); } function mergeBarycenters(target, other) { if (!isUndefined(target.barycenter)) { target.barycenter = (target.barycenter * target.weight + other.barycenter * other.weight) / (target.weight + other.weight); target.weight += other.weight; } else { target.barycenter = other.barycenter; target.weight = other.weight; } } function order(g) { 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"); var layering = initOrder(g); assignOrder(g, layering); var bestCC = Number.POSITIVE_INFINITY, best; for (var i = 0, lastBest = 0; lastBest < 4; ++i, ++lastBest) { sweepLayerGraphs(i % 2 ? downLayerGraphs : upLayerGraphs, i % 4 >= 2); layering = buildLayerMatrix(g); var cc = crossCount(g, layering); if (cc < bestCC) { lastBest = 0; best = cloneDeep(layering); bestCC = cc; } } assignOrder(g, best); } function buildLayerGraphs(g, ranks, relationship) { return map(ranks, function(rank2) { return buildLayerGraph(g, rank2, relationship); }); } function sweepLayerGraphs(layerGraphs, biasRight) { var cg = new Graph(); forEach(layerGraphs, function(lg) { var root2 = lg.graph().root; var sorted = sortSubgraph(lg, root2, cg, biasRight); forEach(sorted.vs, function(v, i) { lg.node(v).order = i; }); addSubgraphConstraints(lg, cg, sorted.vs); }); } function assignOrder(g, layering) { forEach(layering, function(layer) { forEach(layer, function(v, i) { g.node(v).order = i; }); }); } function parentDummyChains(g) { var postorderNums = postorder(g); forEach(g.graph().dummyChains, function(v) { var node = g.node(v); var edgeObj = node.edgeObj; var pathData = findPath(g, postorderNums, edgeObj.v, edgeObj.w); var path = pathData.path; var lca = pathData.lca; var pathIdx = 0; var pathV = path[pathIdx]; var ascending = true; while (v !== edgeObj.w) { node = g.node(v); if (ascending) { while ((pathV = path[pathIdx]) !== lca && g.node(pathV).maxRank < node.rank) { pathIdx++; } if (pathV === lca) { ascending = false; } } if (!ascending) { while (pathIdx < path.length - 1 && g.node(pathV = path[pathIdx + 1]).minRank <= node.rank) { pathIdx++; } pathV = path[pathIdx]; } g.setParent(v, pathV); v = g.successors(v)[0]; } }); } function findPath(g, postorderNums, v, w) { var vPath = []; var wPath = []; var low = Math.min(postorderNums[v].low, postorderNums[w].low); var lim = Math.max(postorderNums[v].lim, postorderNums[w].lim); var parent; var lca; parent = v; do { parent = g.parent(parent); vPath.push(parent); } while (parent && (postorderNums[parent].low > low || lim > postorderNums[parent].lim)); lca = parent; parent = w; while ((parent = g.parent(parent)) !== lca) { wPath.push(parent); } return { path: vPath.concat(wPath.reverse()), lca }; } function postorder(g) { var result = {}; var lim = 0; function dfs2(v) { var low = lim; forEach(g.children(v), dfs2); result[v] = { low, lim: lim++ }; } forEach(g.children(), dfs2); return result; } function findType1Conflicts(g, layering) { var conflicts = {}; function visitLayer(prevLayer, layer) { var k0 = 0, scanPos = 0, prevLayerLength = prevLayer.length, lastNode = last(layer); forEach(layer, function(v, i) { var w = findOtherInnerSegmentNode(g, v), k1 = w ? g.node(w).order : prevLayerLength; if (w || v === lastNode) { forEach(layer.slice(scanPos, i + 1), function(scanNode) { forEach(g.predecessors(scanNode), function(u) { var uLabel = g.node(u), uPos = uLabel.order; if ((uPos < k0 || k1 < uPos) && !(uLabel.dummy && g.node(scanNode).dummy)) { addConflict(conflicts, u, scanNode); } }); }); scanPos = i + 1; k0 = k1; } }); return layer; } reduce(layering, visitLayer); return conflicts; } function findType2Conflicts(g, layering) { var conflicts = {}; function scan(south, southPos, southEnd, prevNorthBorder, nextNorthBorder) { var v; forEach(range$1(southPos, southEnd), function(i) { v = south[i]; if (g.node(v).dummy) { forEach(g.predecessors(v), function(u) { var uNode = g.node(u); if (uNode.dummy && (uNode.order < prevNorthBorder || uNode.order > nextNorthBorder)) { addConflict(conflicts, u, v); } }); } }); } function visitLayer(north, south) { var prevNorthPos = -1, nextNorthPos, southPos = 0; forEach(south, function(v, southLookahead) { if (g.node(v).dummy === "border") { var predecessors = g.predecessors(v); if (predecessors.length) { nextNorthPos = g.node(predecessors[0]).order; scan(south, southPos, southLookahead, prevNorthPos, nextNorthPos); southPos = southLookahead; prevNorthPos = nextNorthPos; } } scan(south, southPos, south.length, nextNorthPos, north.length); }); return south; } reduce(layering, visitLayer); return conflicts; } function findOtherInnerSegmentNode(g, v) { if (g.node(v).dummy) { return find$1(g.predecessors(v), function(u) { return g.node(u).dummy; }); } } function addConflict(conflicts, v, w) { if (v > w) { var tmp = v; v = w; w = tmp; } var conflictsV = conflicts[v]; if (!conflictsV) { conflicts[v] = conflictsV = {}; } conflictsV[w] = true; } function hasConflict(conflicts, v, w) { if (v > w) { var tmp = v; v = w; w = tmp; } return has(conflicts[v], w); } function verticalAlignment(g, layering, conflicts, neighborFn) { var root2 = {}, align = {}, pos = {}; forEach(layering, function(layer) { forEach(layer, function(v, order2) { root2[v] = v; align[v] = v; pos[v] = order2; }); }); forEach(layering, function(layer) { var prevIdx = -1; forEach(layer, function(v) { var ws = neighborFn(v); if (ws.length) { ws = sortBy$1(ws, function(w2) { return pos[w2]; }); var mp = (ws.length - 1) / 2; for (var i = Math.floor(mp), il = Math.ceil(mp); i <= il; ++i) { var w = ws[i]; if (align[v] === v && prevIdx < pos[w] && !hasConflict(conflicts, v, w)) { align[w] = v; align[v] = root2[v] = root2[w]; prevIdx = pos[w]; } } } }); }); return { root: root2, align }; } function horizontalCompaction(g, layering, root2, align, reverseSep) { var xs = {}, blockG = buildBlockGraph(g, layering, root2, reverseSep), borderType = reverseSep ? "borderLeft" : "borderRight"; function iterate(setXsFunc, nextNodesFunc) { var stack = blockG.nodes(); var elem = stack.pop(); var visited = {}; while (elem) { if (visited[elem]) { setXsFunc(elem); } else { visited[elem] = true; stack.push(elem); stack = stack.concat(nextNodesFunc(elem)); } elem = stack.pop(); } } function pass1(elem) { xs[elem] = blockG.inEdges(elem).reduce(function(acc, e) { return Math.max(acc, xs[e.v] + blockG.edge(e)); }, 0); } function pass2(elem) { var min2 = blockG.outEdges(elem).reduce(function(acc, e) { return Math.min(acc, xs[e.w] - blockG.edge(e)); }, Number.POSITIVE_INFINITY); var node = g.node(elem); if (min2 !== Number.POSITIVE_INFINITY && node.borderType !== borderType) { xs[elem] = Math.max(xs[elem], min2); } } iterate(pass1, blockG.predecessors.bind(blockG)); iterate(pass2, blockG.successors.bind(blockG)); forEach(align, function(v) { xs[v] = xs[root2[v]]; }); return xs; } function buildBlockGraph(g, layering, root2, reverseSep) { var blockGraph = new Graph(), graphLabel = g.graph(), sepFn = sep(graphLabel.nodesep, graphLabel.edgesep, reverseSep); forEach(layering, function(layer) { var u; forEach(layer, function(v) { var vRoot = root2[v]; blockGraph.setNode(vRoot); if (u) { var uRoot = root2[u], prevMax = blockGraph.edge(uRoot, vRoot); blockGraph.setEdge(uRoot, vRoot, Math.max(sepFn(g, v, u), prevMax || 0)); } u = v; }); }); return blockGraph; } function findSmallestWidthAlignment(g, xss) { return minBy(values(xss), function(xs) { var max2 = Number.NEGATIVE_INFINITY; var min2 = Number.POSITIVE_INFINITY; forIn(xs, function(x, v) { var halfWidth = width(g, v) / 2; max2 = Math.max(x + halfWidth, max2); min2 = Math.min(x - halfWidth, min2); }); return max2 - min2; }); } function alignCoordinates(xss, alignTo) { var alignToVals = values(alignTo), alignToMin = min(alignToVals), alignToMax = max(alignToVals); forEach(["u", "d"], function(vert) { forEach(["l", "r"], function(horiz) { var alignment = vert + horiz, xs = xss[alignment], delta; if (xs === alignTo) return; var xsVals = values(xs); delta = horiz === "l" ? alignToMin - min(xsVals) : alignToMax - max(xsVals); if (delta) { xss[alignment] = mapValues(xs, function(x) { return x + delta; }); } }); }); } function balance(xss, align) { return mapValues(xss.ul, function(ignore, v) { if (align) { return xss[align.toLowerCase()][v]; } else { var xs = sortBy$1(map(xss, v)); return (xs[1] + xs[2]) / 2; } }); } function positionX(g) { var layering = buildLayerMatrix(g); var conflicts = merge$1(findType1Conflicts(g, layering), findType2Conflicts(g, layering)); var xss = {}; var adjustedLayering; forEach(["u", "d"], function(vert) { adjustedLayering = vert === "u" ? layering : values(layering).reverse(); forEach(["l", "r"], function(horiz) { if (horiz === "r") { adjustedLayering = map(adjustedLayering, function(inner) { return values(inner).reverse(); }); } var neighborFn = (vert === "u" ? g.predecessors : g.successors).bind(g); var align = verticalAlignment(g, adjustedLayering, conflicts, neighborFn); var xs = horizontalCompaction(g, adjustedLayering, align.root, align.align, horiz === "r"); if (horiz === "r") { xs = mapValues(xs, function(x) { return -x; }); } xss[vert + horiz] = xs; }); }); var smallestWidth = findSmallestWidthAlignment(g, xss); alignCoordinates(xss, smallestWidth); return balance(xss, g.graph().align); } function sep(nodeSep, edgeSep, reverseSep) { return function(g, v, w) { var vLabel = g.node(v); var wLabel = g.node(w); var sum = 0; var delta; sum += vLabel.width / 2; if (has(vLabel, "labelpos")) { switch (vLabel.labelpos.toLowerCase()) { case "l": delta = -vLabel.width / 2; break; case "r": delta = vLabel.width / 2; break; } } if (delta) { sum += reverseSep ? delta : -delta; } delta = 0; sum += (vLabel.dummy ? edgeSep : nodeSep) / 2; sum += (wLabel.dummy ? edgeSep : nodeSep) / 2; sum += wLabel.width / 2; if (has(wLabel, "labelpos")) { switch (wLabel.labelpos.toLowerCase()) { case "l": delta = wLabel.width / 2; break; case "r": delta = -wLabel.width / 2; break; } } if (delta) { sum += reverseSep ? delta : -delta; } delta = 0; return sum; }; } function width(g, v) { return g.node(v).width; } function position(g) { g = asNonCompoundGraph(g); positionY(g); forEach(positionX(g), function(x, v) { g.node(v).x = x; }); } function positionY(g) { var layering = buildLayerMatrix(g); var rankSep = g.graph().ranksep; var prevY = 0; forEach(layering, function(layer) { var maxHeight = max( map(layer, function(v) { return g.node(v).height; }) ); forEach(layer, function(v) { g.node(v).y = prevY + maxHeight / 2; }); prevY += maxHeight + rankSep; }); } function layout(g, opts) { var time$1 = opts && opts.debugTiming ? time : notime; time$1("layout", function() { var layoutGraph = time$1(" buildLayoutGraph", function() { return buildLayoutGraph(g); }); time$1(" runLayout", function() { runLayout(layoutGraph, time$1); }); time$1(" updateInputGraph", function() { updateInputGraph(g, layoutGraph); }); }); } function runLayout(g, time2) { time2(" makeSpaceForEdgeLabels", function() { makeSpaceForEdgeLabels(g); }); time2(" removeSelfEdges", function() { removeSelfEdges(g); }); time2(" acyclic", function() { run$2(g); }); time2(" nestingGraph.run", function() { run(g); }); time2(" rank", function() { rank(asNonCompoundGraph(g)); }); time2(" injectEdgeLabelProxies", function() { injectEdgeLabelProxies(g); }); time2(" removeEmptyRanks", function() { removeEmptyRanks(g); }); time2(" nestingGraph.cleanup", function() { cleanup(g); }); time2(" normalizeRanks", function() { normalizeRanks(g); }); time2(" assignRankMinMax", function() { assignRankMinMax(g); }); time2(" removeEdgeLabelProxies", function() { removeEdgeLabelProxies(g); }); time2(" normalize.run", function() { run$1(g); }); time2(" parentDummyChains", function() { parentDummyChains(g); }); time2(" addBorderSegments", function() { addBorderSegments(g); }); time2(" order", function() { order(g); }); time2(" insertSelfEdges", function() { insertSelfEdges(g); }); time2(" adjustCoordinateSystem", function() { adjust(g); }); time2(" position", function() { position(g); }); time2(" positionSelfEdges", function() { positionSelfEdges(g); }); time2(" removeBorderNodes", function() { removeBorderNodes(g); }); time2(" normalize.undo", function() { undo(g); }); time2(" fixupEdgeLabelCoords", function() { fixupEdgeLabelCoords(g); }); time2(" undoCoordinateSystem", function() { undo$1(g); }); time2(" translateGraph", function() { translateGraph(g); }); time2(" assignNodeIntersects", function() { assignNodeIntersects(g); }); time2(" reversePoints", function() { reversePointsForReversedEdges(g); }); time2(" acyclic.undo", function() { undo$2(g); }); } function updateInputGraph(inputGraph, layoutGraph) { forEach(inputGraph.nodes(), function(v) { var inputLabel = inputGraph.node(v); var layoutLabel = layoutGraph.node(v); if (inputLabel) { inputLabel.x = layoutLabel.x; inputLabel.y = layoutLabel.y; if (layoutGraph.children(v).length) { inputLabel.width = layoutLabel.width; inputLabel.height = layoutLabel.height; } } }); forEach(inputGraph.edges(), function(e) { var inputLabel = inputGraph.edge(e); var layoutLabel = layoutGraph.edge(e); inputLabel.points = layoutLabel.points; if (has(layoutLabel, "x")) { inputLabel.x = layoutLabel.x; inputLabel.y = layoutLabel.y; } }); inputGraph.graph().width = layoutGraph.graph().width; inputGraph.graph().height = layoutGraph.graph().height; } var graphNumAttrs = ["nodesep", "edgesep", "ranksep", "marginx", "marginy"]; var graphDefaults = { ranksep: 50, edgesep: 20, nodesep: 50, rankdir: "tb" }; var graphAttrs = ["acyclicer", "ranker", "rankdir", "align"]; var nodeNumAttrs = ["width", "height"]; var nodeDefaults = { width: 0, height: 0 }; var edgeNumAttrs = ["minlen", "weight", "width", "height", "labeloffset"]; var edgeDefaults = { minlen: 1, weight: 1, width: 0, height: 0, labeloffset: 10, labelpos: "r" }; var edgeAttrs = ["labelpos"]; function buildLayoutGraph(inputGraph) { var g = new Graph({ multigraph: true, compound: true }); var graph = canonicalize(inputGraph.graph()); g.setGraph( merge$1({}, graphDefaults, selectNumberAttrs(graph, graphNumAttrs), pick$1(graph, graphAttrs)) ); forEach(inputGraph.nodes(), function(v) { var node = canonicalize(inputGraph.node(v)); g.setNode(v, defaults$1(selectNumberAttrs(node, nodeNumAttrs), nodeDefaults)); g.setParent(v, inputGraph.parent(v)); }); forEach(inputGraph.edges(), function(e) { var edge = canonicalize(inputGraph.edge(e)); g.setEdge( e, merge$1({}, edgeDefaults, selectNumberAttrs(edge, edgeNumAttrs), pick$1(edge, edgeAttrs)) ); }); return g; } function makeSpaceForEdgeLabels(g) { var graph = g.graph(); graph.ranksep /= 2; forEach(g.edges(), function(e) { var edge = g.edge(e); edge.minlen *= 2; if (edge.labelpos.toLowerCase() !== "c") { if (graph.rankdir === "TB" || graph.rankdir === "BT") { edge.width += edge.labeloffset; } else { edge.height += edge.labeloffset; } } }); } function injectEdgeLabelProxies(g) { forEach(g.edges(), function(e) { var edge = g.edge(e); if (edge.width && edge.height) { var v = g.node(e.v); var w = g.node(e.w); var label = { rank: (w.rank - v.rank) / 2 + v.rank, e }; addDummyNode(g, "edge-proxy", label, "_ep"); } }); } function assignRankMinMax(g) { var maxRank2 = 0; forEach(g.nodes(), function(v) { var node = g.node(v); if (node.borderTop) { node.minRank = g.node(node.borderTop).rank; node.maxRank = g.node(node.borderBottom).rank; maxRank2 = max(maxRank2, node.maxRank); } }); g.graph().maxRank = maxRank2; } function removeEdgeLabelProxies(g) { forEach(g.nodes(), function(v) { var node = g.node(v); if (node.dummy === "edge-proxy") { g.edge(node.e).labelRank = node.rank; g.removeNode(v); } }); } function translateGraph(g) { var minX = Number.POSITIVE_INFINITY; var maxX = 0; var minY = Number.POSITIVE_INFINITY; var maxY = 0; var graphLabel = g.graph(); var marginX = graphLabel.marginx || 0; var marginY = graphLabel.marginy || 0; function getExtremes(attrs) { var x = attrs.x; var y = attrs.y; var w = attrs.width; var h = attrs.height; minX = Math.min(minX, x - w / 2); maxX = Math.max(maxX, x + w / 2); minY = Math.min(minY, y - h / 2); maxY = Math.max(maxY, y + h / 2); } forEach(g.nodes(), function(v) { getExtremes(g.node(v)); }); forEach(g.edges(), function(e) { var edge = g.edge(e); if (has(edge, "x")) { getExtremes(edge); } }); minX -= marginX; minY -= marginY; forEach(g.nodes(), function(v) { var node = g.node(v); node.x -= minX; node.y -= minY; }); forEach(g.edges(), function(e) { var edge = g.edge(e); forEach(edge.points, function(p) { p.x -= minX; p.y -= minY; }); if (has(edge, "x")) { edge.x -= minX; } if (has(edge, "y")) { edge.y -= minY; } }); graphLabel.width = maxX - minX + marginX; graphLabel.height = maxY - minY + marginY; } function assignNodeIntersects(g) { forEach(g.edges(), function(e) { var edge = g.edge(e); var nodeV = g.node(e.v); var nodeW = g.node(e.w); var p1, p2; if (!edge.points) { edge.points = []; p1 = nodeW; p2 = nodeV; } else { p1 = edge.points[0]; p2 = edge.points[edge.points.length - 1]; } edge.points.unshift(intersectRect(nodeV, p1)); edge.points.push(intersectRect(nodeW, p2)); }); } function fixupEdgeLabelCoords(g) { forEach(g.edges(), function(e) { var edge = g.edge(e); if (has(edge, "x")) { if (edge.labelpos === "l" || edge.labelpos === "r") { edge.width -= edge.labeloffset; } switch (edge.labelpos) { case "l": edge.x -= edge.width / 2 + edge.labeloffset; break; case "r": edge.x += edge.width / 2 + edge.labeloffset; break; } } }); } function reversePointsForReversedEdges(g) { forEach(g.edges(), function(e) { var edge = g.edge(e); if (edge.reversed) { edge.points.reverse(); } }); } function removeBorderNodes(g) { forEach(g.nodes(), function(v) { if (g.children(v).length) { var node = g.node(v); var t = g.node(node.borderTop); var b = g.node(node.borderBottom); var l = g.node(last(node.borderLeft)); var r = g.node(last(node.borderRight)); node.width = Math.abs(r.x - l.x); node.height = Math.abs(b.y - t.y); node.x = l.x + node.width / 2; node.y = t.y + node.height / 2; } }); forEach(g.nodes(), function(v) { if (g.node(v).dummy === "border") { g.removeNode(v); } }); } function removeSelfEdges(g) { forEach(g.edges(), function(e) { if (e.v === e.w) { var node = g.node(e.v); if (!node.selfEdges) { node.selfEdges = []; } node.selfEdges.push({ e, label: g.edge(e) }); g.removeEdge(e); } }); } function insertSelfEdges(g) { var layers = buildLayerMatrix(g); forEach(layers, function(layer) { var orderShift = 0; forEach(layer, function(v, i) { var node = g.node(v); node.order = i + orderShift; forEach(node.selfEdges, function(selfEdge) { addDummyNode( g, "selfedge", { width: selfEdge.label.width, height: selfEdge.label.height, rank: node.rank, order: i + ++orderShift, e: selfEdge.e, label: selfEdge.label }, "_se" ); }); delete node.selfEdges; }); }); } function positionSelfEdges(g) { forEach(g.nodes(), function(v) { var node = g.node(v); if (node.dummy === "selfedge") { var selfNode = g.node(node.e.v); var x = selfNode.x + selfNode.width / 2; var y = selfNode.y; var dx = node.x - x; var dy = selfNode.height / 2; g.setEdge(node.e, node.label); g.removeNode(v); node.label.points = [ { x: x + 2 * dx / 3, y: y - dy }, { x: x + 5 * dx / 6, y: y - dy }, { x: x + dx, y }, { x: x + 5 * dx / 6, y: y + dy }, { x: x + 2 * dx / 3, y: y + dy } ]; node.label.x = node.x; node.label.y = node.y; } }); } function selectNumberAttrs(obj, attrs) { return mapValues(pick$1(obj, attrs), Number); } function canonicalize(attrs) { var newAttrs = {}; forEach(attrs, function(v, k) { newAttrs[k.toLowerCase()] = v; }); return newAttrs; } export { Graph as G, baseClone as b, defaults$1 as d, forEach as f, has as h, isUndefined as i, layout as l, map as m, pick$1 as p, range$1 as r, uniqueId as u }; //# sourceMappingURL=layout-4663fc19.js.map