1 line
26 KiB
Plaintext
1 line
26 KiB
Plaintext
{"version":3,"file":"splaytree.umd.cjs","sources":["../src/node.ts","../src/index.ts"],"sourcesContent":["\nexport default class Node<Key, Value> {\n public key:Key;\n public data:any;\n public left:Node<Key, Value>|null;\n public right:Node<Key, Value>|null;\n public next:Node<Key, Value>|null = null;\n\n constructor (key:Key, data?:any) {\n this.key = key;\n this.data = data;\n this.left = null;\n this.right = null;\n }\n}","import Node from \"./node\";\nimport { Key, Value } from \"./types\";\n\nexport type Comparator<Key> = (a: Key, b: Key) => number;\nexport type Visitor<Key, Value> = (\n node: Node<Key, Value>\n) => undefined | boolean | void;\nexport type NodePrinter<Key, Value> = (node: Node<Key, Value>) => string;\n\n/* follows \"An implementation of top-down splaying\"\n * by D. Sleator <sleator@cs.cmu.edu> March 1992\n */\n\nfunction DEFAULT_COMPARE(a: Key, b: Key): number {\n return a > b ? 1 : a < b ? -1 : 0;\n}\n\ntype TreeNodeList<Key, Value> = { head: Node<Key, Value> | null };\n\n/**\n * Simple top down splay, not requiring i to be in the tree t.\n */\nfunction splay(\n i: Key,\n t: Node<Key, Value>,\n comparator: Comparator<Key>\n): Node<Key, Value> {\n const N = new Node(null, null);\n let l = N;\n let r = N;\n\n while (true) {\n const cmp = comparator(i, t!.key);\n //if (i < t.key) {\n if (cmp < 0) {\n if (t!.left === null) break;\n //if (i < t.left.key) {\n if (comparator(i, t.left.key) < 0) {\n const y = t.left; /* rotate right */\n t.left = y.right;\n y.right = t;\n t = y;\n if (t.left === null) break;\n }\n r.left = t; /* link right */\n r = t;\n t = t.left;\n //} else if (i > t.key) {\n } else if (cmp > 0) {\n if (t.right === null) break;\n //if (i > t.right.key) {\n if (comparator(i, t.right.key) > 0) {\n const y = t.right; /* rotate left */\n t.right = y.left;\n y.left = t;\n t = y;\n if (t.right === null) break;\n }\n l.right = t; /* link left */\n l = t;\n t = t.right;\n } else break;\n }\n /* assemble */\n l.right = t.left;\n r.left = t.right;\n t.left = N.right;\n t.right = N.left;\n return t;\n}\n\nfunction insert(\n i: Key,\n data: Value,\n t: Node<Key, Value>,\n comparator: Comparator<Key>\n): Node<Key, Value> {\n const node = new Node(i, data);\n\n if (t === null) {\n node.left = node.right = null;\n return node;\n }\n\n t = splay(i, t, comparator);\n const cmp = comparator(i, t.key);\n if (cmp < 0) {\n node.left = t.left;\n node.right = t;\n t.left = null;\n } else if (cmp >= 0) {\n node.right = t.right;\n node.left = t;\n t.right = null;\n }\n return node;\n}\n\nfunction split(\n key: Key,\n v: Node<Key, Value>,\n comparator: Comparator<Key>\n): {\n left: Node<Key, Value> | null;\n right: Node<Key, Value> | null;\n} {\n let left = null;\n let right = null;\n if (v) {\n v = splay(key, v, comparator);\n\n const cmp = comparator(v.key, key);\n if (cmp === 0) {\n left = v.left;\n right = v.right;\n } else if (cmp < 0) {\n right = v.right;\n v.right = null;\n left = v;\n } else {\n left = v.left;\n v.left = null;\n right = v;\n }\n }\n return { left, right };\n}\n\nfunction merge(\n left: Node<Key, Value> | null,\n right: Node<Key, Value> | null,\n comparator: Comparator<Key>\n) {\n if (right === null) return left;\n if (left === null) return right;\n\n right = splay(left.key, right, comparator);\n right.left = left;\n return right;\n}\n\ntype StringCollector = (s: string) => void;\n\n/**\n * Prints level of the tree\n */\nfunction printRow(\n root: Node<Key, Value>,\n prefix: string,\n isTail: boolean,\n out: StringCollector,\n printNode: NodePrinter<Key, Value>\n) {\n if (root) {\n out(`${prefix}${isTail ? \"└── \" : \"├── \"}${printNode(root)}\\n`);\n const indent = prefix + (isTail ? \" \" : \"│ \");\n if (root.left) printRow(root.left, indent, false, out, printNode);\n if (root.right) printRow(root.right, indent, true, out, printNode);\n }\n}\n\nexport default class Tree<Key = number, Value = any> {\n private _comparator: Comparator<Key>;\n private _root: Node<Key, Value> | null = null;\n private _size: number = 0;\n\n constructor(comparator = DEFAULT_COMPARE) {\n this._comparator = comparator;\n }\n\n /**\n * Inserts a key, allows duplicates\n */\n public insert(key: Key, data?: Value): Node<Key, Value> {\n this._size++;\n return (this._root = insert(key, data, this._root!, this._comparator));\n }\n\n /**\n * Adds a key, if it is not present in the tree\n */\n public add(key: Key, data?: Value): Node<Key, Value> {\n const node = new Node(key, data);\n\n if (this._root === null) {\n node.left = node.right = null;\n this._size++;\n this._root = node;\n }\n\n const comparator = this._comparator;\n const t = splay(key, this._root, comparator);\n const cmp = comparator(key, t.key);\n if (cmp === 0) this._root = t;\n else {\n if (cmp < 0) {\n node.left = t.left;\n node.right = t;\n t.left = null;\n } else if (cmp > 0) {\n node.right = t.right;\n node.left = t;\n t.right = null;\n }\n this._size++;\n this._root = node;\n }\n\n return this._root;\n }\n\n /**\n * @param {Key} key\n * @return {Node|null}\n */\n public remove(key: Key): void {\n this._root = this._remove(key, this._root!, this._comparator);\n }\n\n /**\n * Deletes i from the tree if it's there\n */\n private _remove(i: Key, t: Node<Key, Value>, comparator: Comparator<Key>) {\n let x;\n if (t === null) return null;\n t = splay(i, t, comparator);\n const cmp = comparator(i, t.key);\n if (cmp === 0) {\n /* found it */\n if (t.left === null) {\n x = t.right!;\n } else {\n x = splay(i, t.left, comparator);\n x.right = t.right;\n }\n this._size--;\n return x;\n }\n return t; /* It wasn't there */\n }\n\n /**\n * Removes and returns the node with smallest key\n */\n public pop(): { key: Key; data: Value } | null {\n let node = this._root;\n if (node) {\n while (node.left) node = node.left;\n this._root = splay(node.key, this._root!, this._comparator);\n this._root = this._remove(node.key, this._root, this._comparator);\n return { key: node.key, data: node.data };\n }\n return null;\n }\n\n /**\n * Find without splaying\n */\n public findStatic(key: Key): Node<Key, Value> | null {\n let current = this._root;\n const compare = this._comparator;\n while (current) {\n const cmp = compare(key, current.key);\n if (cmp === 0) return current;\n else if (cmp < 0) current = current.left;\n else current = current.right;\n }\n return null;\n }\n\n public find(key: Key): Node<Key, Value> | null {\n if (this._root) {\n this._root = splay(key, this._root, this._comparator);\n if (this._comparator(key, this._root.key) !== 0) return null;\n }\n return this._root;\n }\n\n public contains(key: Key): boolean {\n let current = this._root;\n const compare = this._comparator;\n while (current) {\n const cmp = compare(key, current.key);\n if (cmp === 0) return true;\n else if (cmp < 0) current = current.left;\n else current = current.right;\n }\n return false;\n }\n\n public forEach(visitor: Visitor<Key, Value>, ctx?: any): Tree<Key, Value> {\n let current = this._root;\n const Q = []; /* Initialize stack s */\n let done = false;\n\n while (!done) {\n if (current !== null) {\n Q.push(current);\n current = current.left;\n } else {\n if (Q.length !== 0) {\n current = Q.pop()!;\n visitor.call(ctx, current);\n\n current = current.right;\n } else done = true;\n }\n }\n return this;\n }\n\n /**\n * Walk key range from `low` to `high`. Stops if `fn` returns a value.\n */\n public range(\n low: Key,\n high: Key,\n fn: Visitor<Key, Value>,\n ctx?: any\n ): Tree<Key, Value> {\n const Q = [];\n const compare = this._comparator;\n let node = this._root;\n let cmp;\n\n while (Q.length !== 0 || node) {\n if (node) {\n Q.push(node);\n node = node.left;\n } else {\n node = Q.pop()!;\n cmp = compare(node.key, high);\n if (cmp > 0) {\n break;\n } else if (compare(node.key, low) >= 0) {\n if (fn.call(ctx, node)) return this; // stop if smth is returned\n }\n node = node.right;\n }\n }\n return this;\n }\n\n /**\n * Returns array of keys\n */\n public keys(): Key[] {\n const keys: Key[] = [];\n this.forEach(({ key }) => {\n keys.push(key);\n });\n return keys;\n }\n\n /**\n * Returns array of all the data in the nodes\n */\n public values(): Value[] {\n const values: Value[] = [];\n this.forEach(({ data }) => {\n values.push(data);\n });\n return values;\n }\n\n public min(): Key | null {\n if (this._root) return this.minNode(this._root)!.key;\n return null;\n }\n\n public max(): Key | null {\n if (this._root) return this.maxNode(this._root)!.key;\n return null;\n }\n\n public minNode(t = this._root): Node<Key, Value> | null {\n if (t) while (t.left) t = t.left;\n return t;\n }\n\n public maxNode(t = this._root): Node<Key, Value> | null {\n if (t) while (t.right) t = t.right;\n return t;\n }\n\n /**\n * Returns node at given index\n */\n public at(index: number): Node<Key, Value> | null {\n let current = this._root;\n let done = false;\n let i = 0;\n const Q = [];\n\n while (!done) {\n if (current) {\n Q.push(current);\n current = current.left;\n } else {\n if (Q.length > 0) {\n current = Q.pop()!;\n if (i === index) return current;\n i++;\n current = current.right!;\n } else done = true;\n }\n }\n return null;\n }\n\n public next(d: Node<Key, Value>): Node<Key, Value> | null {\n let root = this._root;\n let successor = null;\n\n if (d.right) {\n successor = d.right;\n while (successor.left) successor = successor.left;\n return successor;\n }\n\n const comparator = this._comparator;\n while (root) {\n const cmp = comparator(d.key, root.key);\n if (cmp === 0) break;\n else if (cmp < 0) {\n successor = root;\n root = root.left;\n } else root = root.right;\n }\n\n return successor;\n }\n\n public prev(d: Node<Key, Value>): Node<Key, Value> | null {\n let root = this._root;\n let predecessor = null;\n\n if (d.left !== null) {\n predecessor = d.left;\n while (predecessor.right) predecessor = predecessor.right;\n return predecessor;\n }\n\n const comparator = this._comparator;\n while (root) {\n const cmp = comparator(d.key, root.key);\n if (cmp === 0) break;\n else if (cmp < 0) root = root.left;\n else {\n predecessor = root;\n root = root.right;\n }\n }\n return predecessor;\n }\n\n public clear(): Tree<Key, Value> {\n this._root = null;\n this._size = 0;\n return this;\n }\n\n public toList() {\n return toList(this._root!);\n }\n\n /**\n * Bulk-load items. Both array have to be same size\n */\n public load(keys: Key[], values: Value[] = [], presort: boolean = false) {\n let size = keys.length;\n const comparator = this._comparator;\n\n // sort if needed\n if (presort) sort(keys, values, 0, size - 1, comparator);\n\n if (this._root === null) {\n // empty tree\n this._root = loadRecursive(keys, values, 0, size);\n this._size = size;\n } else {\n // that re-builds the whole tree from two in-order traversals\n const mergedList = mergeLists(\n this.toList(),\n createList(keys, values),\n comparator\n );\n size = this._size + size;\n this._root = sortedListToBST({ head: mergedList }, 0, size);\n }\n return this;\n }\n\n public isEmpty(): boolean {\n return this._root === null;\n }\n\n get size(): number {\n return this._size;\n }\n get root(): Node<Key, Value> | null {\n return this._root;\n }\n\n public toString(\n printNode: NodePrinter<Key, Value> = (n) => String(n.key)\n ): string {\n const out: string[] = [];\n printRow(this._root!, \"\", true, (v) => out.push(v), printNode);\n return out.join(\"\");\n }\n\n public update(key: Key, newKey: Key, newData?: Value): void {\n const comparator = this._comparator;\n let { left, right } = split(key, this._root!, comparator);\n if (comparator(key, newKey) < 0) {\n right = insert(newKey, newData, right!, comparator);\n } else {\n left = insert(newKey, newData, left!, comparator);\n }\n this._root = merge(left, right, comparator);\n }\n\n public split(key: Key) {\n return split(key, this._root!, this._comparator);\n }\n\n *[Symbol.iterator]() {\n let current = this._root;\n const Q: Node<Key, Value>[] = []; /* Initialize stack s */\n let done = false;\n\n while (!done) {\n if (current !== null) {\n Q.push(current);\n current = current.left;\n } else {\n if (Q.length !== 0) {\n current = Q.pop()!;\n yield current;\n\n current = current.right;\n } else done = true;\n }\n }\n }\n}\n\nfunction loadRecursive(\n keys: Key[],\n values: Value[],\n start: number,\n end: number\n): Node<Key, Value> | null {\n const size = end - start;\n if (size > 0) {\n const middle = start + Math.floor(size / 2);\n const key = keys[middle];\n const data = values[middle];\n const node = new Node(key, data);\n node.left = loadRecursive(keys, values, start, middle);\n node.right = loadRecursive(keys, values, middle + 1, end);\n return node;\n }\n return null;\n}\n\nfunction createList(keys: Key[], values: Value[]): Node<Key, Value> {\n const head = new Node<Key, Value>(null, null);\n let p: Node<Key, Value> = head;\n for (let i = 0; i < keys.length; i++) {\n p = p.next = new Node(keys[i], values[i]);\n }\n p.next = null;\n return head.next!;\n}\n\nfunction toList(root: Node<Key, Value>): Node<Key, Value> {\n let current = root;\n const Q = [];\n let done = false;\n\n const head = new Node<Key, Value>(null, null);\n let p = head;\n\n while (!done) {\n if (current) {\n Q.push(current);\n current = current.left!;\n } else {\n if (Q.length > 0) {\n current = p = p.next = Q.pop()!;\n current = current.right!;\n } else done = true;\n }\n }\n p.next = null; // that'll work even if the tree was empty\n return head.next!;\n}\n\nfunction sortedListToBST(\n list: TreeNodeList<Key, Value>,\n start: number,\n end: number\n) {\n const size = end - start;\n if (size > 0) {\n const middle = start + Math.floor(size / 2);\n const left = sortedListToBST(list, start, middle);\n\n const root = list.head;\n root!.left = left;\n\n list.head = list.head!.next;\n\n root!.right = sortedListToBST(list, middle + 1, end);\n return root!;\n }\n return null;\n}\n\nfunction mergeLists<Key, Value>(\n l1: Node<Key, Value>,\n l2: Node<Key, Value>,\n compare: Comparator<Key>\n): Node<Key, Value> {\n const head: Node<Key, Value> = new Node<Key, Value>(null as Key, null); // dummy\n let p = head;\n\n let p1: Node<Key, Value> = l1;\n let p2: Node<Key, Value> = l2;\n\n while (p1 !== null && p2 !== null) {\n if (compare(p1.key, p2.key) < 0) {\n p.next = p1;\n p1 = p1.next!;\n } else {\n p.next = p2;\n p2 = p2.next!;\n }\n p = p.next;\n }\n\n if (p1 !== null) {\n p.next = p1;\n } else if (p2 !== null) {\n p.next = p2;\n }\n\n return head.next!;\n}\n\nfunction sort(\n keys: Key[],\n values: Value[],\n left: number,\n right: number,\n compare: Comparator<Key>\n) {\n if (left >= right) return;\n\n const pivot = keys[(left + right) >> 1];\n let i = left - 1;\n let j = right + 1;\n\n while (true) {\n do i++;\n while (compare(keys[i], pivot) < 0);\n do j--;\n while (compare(keys[j], pivot) > 0);\n if (i >= j) break;\n\n let tmp = keys[i];\n keys[i] = keys[j];\n keys[j] = tmp;\n\n tmp = values[i];\n values[i] = values[j];\n values[j] = tmp;\n }\n\n sort(keys, values, left, j, compare);\n sort(keys, values, j + 1, right, compare);\n}\n"],"names":["Node","key","data","DEFAULT_COMPARE","a","b","splay","i","comparator","N","l","r","cmp","y","insert","t","node","split","v","left","right","merge","printRow","root","prefix","isTail","out","printNode","indent","Tree","x","current","compare","visitor","ctx","Q","done","low","high","fn","keys","values","index","d","successor","predecessor","toList","presort","size","sort","loadRecursive","mergedList","mergeLists","createList","sortedListToBST","n","newKey","newData","start","end","middle","head","p","list","l1","l2","p1","p2","pivot","j","tmp"],"mappings":"2NACA,MAAqBA,CAAiB,CAOpC,YAAaC,EAASC,EAAW,CAFjC,KAAO,KAA6B,KAGlC,KAAK,IAASD,EACd,KAAK,KAASC,EACd,KAAK,KAAS,KACd,KAAK,MAAS,IAChB,CACF,CCDA,SAASC,EAAgBC,EAAQC,EAAgB,CAC/C,OAAOD,EAAIC,EAAI,EAAID,EAAIC,EAAI,GAAK,CAClC,CAOA,SAASC,EACPC,EACA,EACAC,EACkB,CAClB,MAAMC,EAAI,IAAIT,EAAK,KAAM,IAAI,EAC7B,IAAIU,EAAID,EACJE,EAAIF,EAER,OAAa,CACX,MAAMG,EAAMJ,EAAWD,EAAG,EAAG,GAAG,EAEhC,GAAIK,EAAM,EAAG,CACX,GAAI,EAAG,OAAS,KAAM,MAEtB,GAAIJ,EAAWD,EAAG,EAAE,KAAK,GAAG,EAAI,EAAG,CACjC,MAAMM,EAAI,EAAE,KAIZ,GAHA,EAAE,KAAOA,EAAE,MACXA,EAAE,MAAQ,EACV,EAAIA,EACA,EAAE,OAAS,KAAM,KACvB,CACAF,EAAE,KAAO,EACTA,EAAI,EACJ,EAAI,EAAE,IAER,SAAWC,EAAM,EAAG,CAClB,GAAI,EAAE,QAAU,KAAM,MAEtB,GAAIJ,EAAWD,EAAG,EAAE,MAAM,GAAG,EAAI,EAAG,CAClC,MAAMM,EAAI,EAAE,MAIZ,GAHA,EAAE,MAAQA,EAAE,KACZA,EAAE,KAAO,EACT,EAAIA,EACA,EAAE,QAAU,KAAM,KACxB,CACAH,EAAE,MAAQ,EACVA,EAAI,EACJ,EAAI,EAAE,KACR,KAAO,MACT,CAEA,OAAAA,EAAE,MAAQ,EAAE,KACZC,EAAE,KAAO,EAAE,MACX,EAAE,KAAOF,EAAE,MACX,EAAE,MAAQA,EAAE,KACL,CACT,CAEA,SAASK,EACPP,EACAL,EACAa,EACAP,EACkB,CAClB,MAAMQ,EAAO,IAAIhB,EAAKO,EAAGL,CAAI,EAE7B,GAAIa,IAAM,KACR,OAAAC,EAAK,KAAOA,EAAK,MAAQ,KAClBA,EAGTD,EAAIT,EAAMC,EAAGQ,EAAGP,CAAU,EAC1B,MAAMI,EAAMJ,EAAWD,EAAGQ,EAAE,GAAG,EAC/B,OAAIH,EAAM,GACRI,EAAK,KAAOD,EAAE,KACdC,EAAK,MAAQD,EACbA,EAAE,KAAO,MACAH,GAAO,IAChBI,EAAK,MAAQD,EAAE,MACfC,EAAK,KAAOD,EACZA,EAAE,MAAQ,MAELC,CACT,CAEA,SAASC,EACPhB,EACAiB,EACAV,EAIA,CACA,IAAIW,EAAO,KACPC,EAAQ,KACZ,GAAIF,EAAG,CACLA,EAAIZ,EAAML,EAAKiB,EAAGV,CAAU,EAE5B,MAAMI,EAAMJ,EAAWU,EAAE,IAAKjB,CAAG,EAC7BW,IAAQ,GACVO,EAAOD,EAAE,KACTE,EAAQF,EAAE,OACDN,EAAM,GACfQ,EAAQF,EAAE,MACVA,EAAE,MAAQ,KACVC,EAAOD,IAEPC,EAAOD,EAAE,KACTA,EAAE,KAAO,KACTE,EAAQF,EAEZ,CACA,MAAO,CAAE,KAAAC,EAAM,MAAAC,CAAA,CACjB,CAEA,SAASC,EACPF,EACAC,EACAZ,EACA,CACA,OAAIY,IAAU,KAAaD,GACvBA,IAAS,OAEbC,EAAQd,EAAMa,EAAK,IAAKC,EAAOZ,CAAU,EACzCY,EAAM,KAAOD,GACNC,EACT,CAOA,SAASE,EACPC,EACAC,EACAC,EACAC,EACAC,EACA,CACA,GAAIJ,EAAM,CACRG,EAAI,GAAGF,CAAM,GAAGC,EAAS,OAAS,MAAM,GAAGE,EAAUJ,CAAI,CAAC;AAAA,CAAI,EAC9D,MAAMK,EAASJ,GAAUC,EAAS,OAAS,QACvCF,EAAK,MAAMD,EAASC,EAAK,KAAMK,EAAQ,GAAOF,EAAKC,CAAS,EAC5DJ,EAAK,OAAOD,EAASC,EAAK,MAAOK,EAAQ,GAAMF,EAAKC,CAAS,CACnE,CACF,CAEA,MAAqBE,CAAgC,CAKnD,YAAYrB,EAAaL,EAAiB,CAH1C,KAAQ,MAAiC,KACzC,KAAQ,MAAgB,EAGtB,KAAK,YAAcK,CACrB,CAKO,OAAOP,EAAUC,EAAgC,CACtD,YAAK,QACG,KAAK,MAAQY,EAAOb,EAAKC,EAAM,KAAK,MAAQ,KAAK,WAAW,CACtE,CAKO,IAAID,EAAUC,EAAgC,CACnD,MAAMc,EAAO,IAAIhB,EAAKC,EAAKC,CAAI,EAE3B,KAAK,QAAU,OACjBc,EAAK,KAAOA,EAAK,MAAQ,KACzB,KAAK,QACL,KAAK,MAAQA,GAGf,MAAMR,EAAa,KAAK,YAClBO,EAAIT,EAAML,EAAK,KAAK,MAAOO,CAAU,EACrCI,EAAMJ,EAAWP,EAAKc,EAAE,GAAG,EACjC,OAAIH,IAAQ,EAAG,KAAK,MAAQG,GAEtBH,EAAM,GACRI,EAAK,KAAOD,EAAE,KACdC,EAAK,MAAQD,EACbA,EAAE,KAAO,MACAH,EAAM,IACfI,EAAK,MAAQD,EAAE,MACfC,EAAK,KAAOD,EACZA,EAAE,MAAQ,MAEZ,KAAK,QACL,KAAK,MAAQC,GAGR,KAAK,KACd,CAMO,OAAOf,EAAgB,CAC5B,KAAK,MAAQ,KAAK,QAAQA,EAAK,KAAK,MAAQ,KAAK,WAAW,CAC9D,CAKQ,QAAQM,EAAQQ,EAAqBP,EAA6B,CACxE,IAAIsB,EACJ,OAAIf,IAAM,KAAa,MACvBA,EAAIT,EAAMC,EAAGQ,EAAGP,CAAU,EACdA,EAAWD,EAAGQ,EAAE,GAAG,IACnB,GAENA,EAAE,OAAS,KACbe,EAAIf,EAAE,OAENe,EAAIxB,EAAMC,EAAGQ,EAAE,KAAMP,CAAU,EAC/BsB,EAAE,MAAQf,EAAE,OAEd,KAAK,QACEe,GAEFf,EACT,CAKO,KAAwC,CAC7C,IAAIC,EAAO,KAAK,MAChB,GAAIA,EAAM,CACR,KAAOA,EAAK,MAAMA,EAAOA,EAAK,KAC9B,YAAK,MAAQV,EAAMU,EAAK,IAAK,KAAK,MAAQ,KAAK,WAAW,EAC1D,KAAK,MAAQ,KAAK,QAAQA,EAAK,IAAK,KAAK,MAAO,KAAK,WAAW,EACzD,CAAE,IAAKA,EAAK,IAAK,KAAMA,EAAK,IAAA,CACrC,CACA,OAAO,IACT,CAKO,WAAWf,EAAmC,CACnD,IAAI8B,EAAU,KAAK,MACnB,MAAMC,EAAU,KAAK,YACrB,KAAOD,GAAS,CACd,MAAMnB,EAAMoB,EAAQ/B,EAAK8B,EAAQ,GAAG,EACpC,GAAInB,IAAQ,EAAG,OAAOmB,EACbnB,EAAM,EAAGmB,EAAUA,EAAQ,OACrBA,EAAQ,KACzB,CACA,OAAO,IACT,CAEO,KAAK9B,EAAmC,CAC7C,OAAI,KAAK,QACP,KAAK,MAAQK,EAAML,EAAK,KAAK,MAAO,KAAK,WAAW,EAChD,KAAK,YAAYA,EAAK,KAAK,MAAM,GAAG,IAAM,GAAU,KAEnD,KAAK,KACd,CAEO,SAASA,EAAmB,CACjC,IAAI8B,EAAU,KAAK,MACnB,MAAMC,EAAU,KAAK,YACrB,KAAOD,GAAS,CACd,MAAMnB,EAAMoB,EAAQ/B,EAAK8B,EAAQ,GAAG,EACpC,GAAInB,IAAQ,EAAG,MAAO,GACbA,EAAM,EAAGmB,EAAUA,EAAQ,OACrBA,EAAQ,KACzB,CACA,MAAO,EACT,CAEO,QAAQE,EAA8BC,EAA6B,CACxE,IAAIH,EAAU,KAAK,MACnB,MAAMI,EAAI,CAAA,EACV,IAAIC,EAAO,GAEX,KAAO,CAACA,GACFL,IAAY,MACdI,EAAE,KAAKJ,CAAO,EACdA,EAAUA,EAAQ,MAEdI,EAAE,SAAW,GACfJ,EAAUI,EAAE,IAAA,EACZF,EAAQ,KAAKC,EAAKH,CAAO,EAEzBA,EAAUA,EAAQ,OACbK,EAAO,GAGlB,OAAO,IACT,CAKO,MACLC,EACAC,EACAC,EACAL,EACkB,CAClB,MAAMC,EAAI,CAAA,EACJH,EAAU,KAAK,YACrB,IAAIhB,EAAO,KAAK,MACZJ,EAEJ,KAAOuB,EAAE,SAAW,GAAKnB,GACvB,GAAIA,EACFmB,EAAE,KAAKnB,CAAI,EACXA,EAAOA,EAAK,SACP,CAGL,GAFAA,EAAOmB,EAAE,IAAA,EACTvB,EAAMoB,EAAQhB,EAAK,IAAKsB,CAAI,EACxB1B,EAAM,EACR,SACSoB,EAAQhB,EAAK,IAAKqB,CAAG,GAAK,GAC/BE,EAAG,KAAKL,EAAKlB,CAAI,EAAG,OAAO,KAEjCA,EAAOA,EAAK,KACd,CAEF,OAAO,IACT,CAKO,MAAc,CACnB,MAAMwB,EAAc,CAAA,EACpB,YAAK,QAAQ,CAAC,CAAE,IAAAvC,KAAU,CACxBuC,EAAK,KAAKvC,CAAG,CACf,CAAC,EACMuC,CACT,CAKO,QAAkB,CACvB,MAAMC,EAAkB,CAAA,EACxB,YAAK,QAAQ,CAAC,CAAE,KAAAvC,KAAW,CACzBuC,EAAO,KAAKvC,CAAI,CAClB,CAAC,EACMuC,CACT,CAEO,KAAkB,CACvB,OAAI,KAAK,MAAc,KAAK,QAAQ,KAAK,KAAK,EAAG,IAC1C,IACT,CAEO,KAAkB,CACvB,OAAI,KAAK,MAAc,KAAK,QAAQ,KAAK,KAAK,EAAG,IAC1C,IACT,CAEO,QAAQ,EAAI,KAAK,MAAgC,CACtD,GAAI,EAAG,KAAO,EAAE,QAAU,EAAE,KAC5B,OAAO,CACT,CAEO,QAAQ,EAAI,KAAK,MAAgC,CACtD,GAAI,EAAG,KAAO,EAAE,SAAW,EAAE,MAC7B,OAAO,CACT,CAKO,GAAGC,EAAwC,CAChD,IAAIX,EAAU,KAAK,MACfK,EAAO,GACP,EAAI,EACR,MAAMD,EAAI,CAAA,EAEV,KAAO,CAACC,GACN,GAAIL,EACFI,EAAE,KAAKJ,CAAO,EACdA,EAAUA,EAAQ,aAEdI,EAAE,OAAS,EAAG,CAEhB,GADAJ,EAAUI,EAAE,IAAA,EACR,IAAMO,EAAO,OAAOX,EACxB,IACAA,EAAUA,EAAQ,KACpB,MAAOK,EAAO,GAGlB,OAAO,IACT,CAEO,KAAKO,EAA8C,CACxD,IAAIpB,EAAO,KAAK,MACZqB,EAAY,KAEhB,GAAID,EAAE,MAAO,CAEX,IADAC,EAAYD,EAAE,MACPC,EAAU,MAAMA,EAAYA,EAAU,KAC7C,OAAOA,CACT,CAEA,MAAMpC,EAAa,KAAK,YACxB,KAAOe,GAAM,CACX,MAAMX,EAAMJ,EAAWmC,EAAE,IAAKpB,EAAK,GAAG,EACtC,GAAIX,IAAQ,EAAG,MACNA,EAAM,GACbgC,EAAYrB,EACZA,EAAOA,EAAK,QACAA,EAAK,KACrB,CAEA,OAAOqB,CACT,CAEO,KAAKD,EAA8C,CACxD,IAAIpB,EAAO,KAAK,MACZsB,EAAc,KAElB,GAAIF,EAAE,OAAS,KAAM,CAEnB,IADAE,EAAcF,EAAE,KACTE,EAAY,OAAOA,EAAcA,EAAY,MACpD,OAAOA,CACT,CAEA,MAAMrC,EAAa,KAAK,YACxB,KAAOe,GAAM,CACX,MAAMX,EAAMJ,EAAWmC,EAAE,IAAKpB,EAAK,GAAG,EACtC,GAAIX,IAAQ,EAAG,MACNA,EAAM,EAAGW,EAAOA,EAAK,MAE5BsB,EAActB,EACdA,EAAOA,EAAK,MAEhB,CACA,OAAOsB,CACT,CAEO,OAA0B,CAC/B,YAAK,MAAQ,KACb,KAAK,MAAQ,EACN,IACT,CAEO,QAAS,CACd,OAAOC,EAAO,KAAK,KAAM,CAC3B,CAKO,KAAKN,EAAaC,EAAkB,CAAA,EAAIM,EAAmB,GAAO,CACvE,IAAIC,EAAOR,EAAK,OAChB,MAAMhC,EAAa,KAAK,YAKxB,GAFIuC,GAASE,EAAKT,EAAMC,EAAQ,EAAGO,EAAO,EAAGxC,CAAU,EAEnD,KAAK,QAAU,KAEjB,KAAK,MAAQ0C,EAAcV,EAAMC,EAAQ,EAAGO,CAAI,EAChD,KAAK,MAAQA,MACR,CAEL,MAAMG,EAAaC,EACjB,KAAK,OAAA,EACLC,EAAWb,EAAMC,CAAM,EACvBjC,CAAA,EAEFwC,EAAO,KAAK,MAAQA,EACpB,KAAK,MAAQM,EAAgB,CAAE,KAAMH,CAAA,EAAc,EAAGH,CAAI,CAC5D,CACA,OAAO,IACT,CAEO,SAAmB,CACxB,OAAO,KAAK,QAAU,IACxB,CAEA,IAAI,MAAe,CACjB,OAAO,KAAK,KACd,CACA,IAAI,MAAgC,CAClC,OAAO,KAAK,KACd,CAEO,SACLrB,EAAsC4B,GAAM,OAAOA,EAAE,GAAG,EAChD,CACR,MAAM7B,EAAgB,CAAA,EACtB,OAAAJ,EAAS,KAAK,MAAQ,GAAI,GAAOJ,GAAMQ,EAAI,KAAKR,CAAC,EAAGS,CAAS,EACtDD,EAAI,KAAK,EAAE,CACpB,CAEO,OAAOzB,EAAUuD,EAAaC,EAAuB,CAC1D,MAAMjD,EAAa,KAAK,YACxB,GAAI,CAAE,KAAAW,EAAM,MAAAC,GAAUH,EAAMhB,EAAK,KAAK,MAAQO,CAAU,EACpDA,EAAWP,EAAKuD,CAAM,EAAI,EAC5BpC,EAAQN,EAAO0C,EAAQC,EAASrC,EAAQZ,CAAU,EAElDW,EAAOL,EAAO0C,EAAQC,EAAStC,EAAOX,CAAU,EAElD,KAAK,MAAQa,EAAMF,EAAMC,EAAOZ,CAAU,CAC5C,CAEO,MAAMP,EAAU,CACrB,OAAOgB,EAAMhB,EAAK,KAAK,MAAQ,KAAK,WAAW,CACjD,CAEA,EAAE,OAAO,QAAQ,GAAI,CACnB,IAAI8B,EAAU,KAAK,MACnB,MAAMI,EAAwB,CAAA,EAC9B,IAAIC,EAAO,GAEX,KAAO,CAACA,GACFL,IAAY,MACdI,EAAE,KAAKJ,CAAO,EACdA,EAAUA,EAAQ,MAEdI,EAAE,SAAW,GACfJ,EAAUI,EAAE,IAAA,EACZ,MAAMJ,EAENA,EAAUA,EAAQ,OACbK,EAAO,EAGpB,CACF,CAEA,SAASc,EACPV,EACAC,EACAiB,EACAC,EACyB,CACzB,MAAMX,EAAOW,EAAMD,EACnB,GAAIV,EAAO,EAAG,CACZ,MAAMY,EAASF,EAAQ,KAAK,MAAMV,EAAO,CAAC,EACpC/C,EAAMuC,EAAKoB,CAAM,EACjB1D,EAAOuC,EAAOmB,CAAM,EACpB5C,EAAO,IAAIhB,EAAKC,EAAKC,CAAI,EAC/B,OAAAc,EAAK,KAAOkC,EAAcV,EAAMC,EAAQiB,EAAOE,CAAM,EACrD5C,EAAK,MAAQkC,EAAcV,EAAMC,EAAQmB,EAAS,EAAGD,CAAG,EACjD3C,CACT,CACA,OAAO,IACT,CAEA,SAASqC,EAAWb,EAAaC,EAAmC,CAClE,MAAMoB,EAAO,IAAI7D,EAAiB,KAAM,IAAI,EAC5C,IAAI8D,EAAsBD,EAC1B,QAAS,EAAI,EAAG,EAAIrB,EAAK,OAAQ,IAC/BsB,EAAIA,EAAE,KAAO,IAAI9D,EAAKwC,EAAK,CAAC,EAAGC,EAAO,CAAC,CAAC,EAE1C,OAAAqB,EAAE,KAAO,KACFD,EAAK,IACd,CAEA,SAASf,EAAOvB,EAA0C,CACxD,IAAIQ,EAAUR,EACd,MAAMY,EAAI,CAAA,EACV,IAAIC,EAAO,GAEX,MAAMyB,EAAO,IAAI7D,EAAiB,KAAM,IAAI,EAC5C,IAAI8D,EAAID,EAER,KAAO,CAACzB,GACFL,GACFI,EAAE,KAAKJ,CAAO,EACdA,EAAUA,EAAQ,MAEdI,EAAE,OAAS,GACbJ,EAAU+B,EAAIA,EAAE,KAAO3B,EAAE,IAAA,EACzBJ,EAAUA,EAAQ,OACbK,EAAO,GAGlB,OAAA0B,EAAE,KAAO,KACFD,EAAK,IACd,CAEA,SAASP,EACPS,EACAL,EACAC,EACA,CACA,MAAMX,EAAOW,EAAMD,EACnB,GAAIV,EAAO,EAAG,CACZ,MAAMY,EAASF,EAAQ,KAAK,MAAMV,EAAO,CAAC,EACpC7B,EAAOmC,EAAgBS,EAAML,EAAOE,CAAM,EAE1CrC,EAAOwC,EAAK,KAClB,OAAAxC,EAAM,KAAOJ,EAEb4C,EAAK,KAAOA,EAAK,KAAM,KAEvBxC,EAAM,MAAQ+B,EAAgBS,EAAMH,EAAS,EAAGD,CAAG,EAC5CpC,CACT,CACA,OAAO,IACT,CAEA,SAAS6B,EACPY,EACAC,EACAjC,EACkB,CAClB,MAAM6B,EAAyB,IAAI7D,EAAiB,KAAa,IAAI,EACrE,IAAI8D,EAAID,EAEJK,EAAuBF,EACvBG,EAAuBF,EAE3B,KAAOC,IAAO,MAAQC,IAAO,MACvBnC,EAAQkC,EAAG,IAAKC,EAAG,GAAG,EAAI,GAC5BL,EAAE,KAAOI,EACTA,EAAKA,EAAG,OAERJ,EAAE,KAAOK,EACTA,EAAKA,EAAG,MAEVL,EAAIA,EAAE,KAGR,OAAII,IAAO,KACTJ,EAAE,KAAOI,EACAC,IAAO,OAChBL,EAAE,KAAOK,GAGJN,EAAK,IACd,CAEA,SAASZ,EACPT,EACAC,EACAtB,EACAC,EACAY,EACA,CACA,GAAIb,GAAQC,EAAO,OAEnB,MAAMgD,EAAQ5B,EAAMrB,EAAOC,GAAU,CAAC,EACtC,IAAIb,EAAIY,EAAO,EACXkD,EAAIjD,EAAQ,EAEhB,OAAa,CACX,GAAGb,UACIyB,EAAQQ,EAAKjC,CAAC,EAAG6D,CAAK,EAAI,GACjC,GAAGC,UACIrC,EAAQQ,EAAK6B,CAAC,EAAGD,CAAK,EAAI,GACjC,GAAI7D,GAAK8D,EAAG,MAEZ,IAAIC,EAAM9B,EAAKjC,CAAC,EAChBiC,EAAKjC,CAAC,EAAIiC,EAAK6B,CAAC,EAChB7B,EAAK6B,CAAC,EAAIC,EAEVA,EAAM7B,EAAOlC,CAAC,EACdkC,EAAOlC,CAAC,EAAIkC,EAAO4B,CAAC,EACpB5B,EAAO4B,CAAC,EAAIC,CACd,CAEArB,EAAKT,EAAMC,EAAQtB,EAAMkD,EAAGrC,CAAO,EACnCiB,EAAKT,EAAMC,EAAQ4B,EAAI,EAAGjD,EAAOY,CAAO,CAC1C"} |