{"version":3,"file":"btree.cjs","sources":["../../../src/utils/btree.ts"],"sourcesContent":["// This file was copied from https://github.com/qwertie/btree-typescript/tree/master and adapted to our needs.\n// We removed methods that we don't need.\n\n// B+ tree by David Piepgrass. License: MIT\n// Informative microbenchmarks & stuff:\n// http://www.jayconrod.com/posts/52/a-tour-of-v8-object-representation (very educational)\n// https://blog.mozilla.org/luke/2012/10/02/optimizing-javascript-variable-access/ (local vars are faster than properties)\n// http://benediktmeurer.de/2017/12/13/an-introduction-to-speculative-optimization-in-v8/ (other stuff)\n// https://jsperf.com/js-in-operator-vs-alternatives (avoid 'in' operator; `.p!==undefined` faster than `hasOwnProperty('p')` in all browsers)\n// https://jsperf.com/instanceof-vs-typeof-vs-constructor-vs-member (speed of type tests varies wildly across browsers)\n// https://jsperf.com/detecting-arrays-new (a.constructor===Array is best across browsers, assuming a is an object)\n// https://jsperf.com/shallow-cloning-methods (a constructor is faster than Object.create; hand-written clone faster than Object.assign)\n// https://jsperf.com/ways-to-fill-an-array (slice-and-replace is fastest)\n// https://jsperf.com/math-min-max-vs-ternary-vs-if (Math.min/max is slow on Edge)\n// https://jsperf.com/array-vs-property-access-speed (v.x/v.y is faster than a[0]/a[1] in major browsers IF hidden class is constant)\n// https://jsperf.com/detect-not-null-or-undefined (`x==null` slightly slower than `x===null||x===undefined` on all browsers)\n// Overall, microbenchmarks suggest Firefox is the fastest browser for JavaScript and Edge is the slowest.\n// Lessons from https://v8project.blogspot.com/2017/09/elements-kinds-in-v8.html:\n//   - Avoid holes in arrays. Avoid `new Array(N)`, it will be \"holey\" permanently.\n//   - Don't read outside bounds of an array (it scans prototype chain).\n//   - Small integer arrays are stored differently from doubles\n//   - Adding non-numbers to an array deoptimizes it permanently into a general array\n//   - Objects can be used like arrays (e.g. have length property) but are slower\n//   - V8 source (NewElementsCapacity in src/objects.h): arrays grow by 50% + 16 elements\n\n/**\n * Mutable B+ tree used by BTreeIndex for sorted value buckets. Keys use the\n * supplied comparator, which must return a number that is not NaN; BTreeIndex\n * checks every comparator result. Point operations cost O(log size). This fork has\n * no copy-on-write sharing, cloning, optional-value storage, early-exit range\n * callbacks, or in-place range edits: only the operations BTreeIndex uses,\n * plus `has()` and the `get()` fallback that the Map oracle observes\n * (tests/btree-map-oracle.test.ts).\n * @author David Piepgrass\n */\nexport class BTree<K = any, V = any> {\n  private _root: BNode<K, V> = new BNode<K, V>()\n  _size = 0\n  _maxNodeSize: number\n\n  /**\n   * provides a total order over keys (and a strict partial order over the type K)\n   * @returns a negative value if a < b, 0 if a === b and a positive value if a > b\n   */\n  _compare: (a: K, b: K) => number\n\n  /**\n   * Initializes an empty B+ tree.\n   * @param compare Custom function to compare pairs of elements in the tree.\n   * @param maxNodeSize Branching factor (maximum items or children per node)\n   *   Must be in range 4..256. If undefined or <4 then default is used; if >256 then 256.\n   */\n  public constructor(compare: (a: K, b: K) => number, maxNodeSize?: number) {\n    this._maxNodeSize = maxNodeSize! >= 4 ? Math.min(maxNodeSize!, 256) : 32\n    this._compare = compare\n  }\n\n  /** Gets the number of key-value pairs in the tree. */\n  get size() {\n    return this._size\n  }\n\n  /** Releases the tree so that its size is 0. */\n  clear() {\n    this._root = new BNode<K, V>()\n    this._size = 0\n  }\n\n  /**\n   * Finds a pair in the tree and returns the associated value.\n   * @param defaultValue a value to return if the key was not found.\n   * @returns the value, or defaultValue if the key was not found.\n   * @description Computational complexity: O(log size)\n   */\n  get(key: K, defaultValue?: V): V | undefined {\n    return this._root.get(key, defaultValue, this)\n  }\n\n  /** Returns true if the key exists in the B+ tree. */\n  has(key: K): boolean {\n    const missing = {} as V\n    return this.get(key, missing) !== missing\n  }\n\n  /**\n   * Adds or overwrites a key-value pair in the B+ tree. Overwriting also\n   * replaces the stored key.\n   * @returns true if a new key-value pair was added.\n   * @description Computational complexity: O(log size)\n   */\n  set(key: K, value: V): boolean {\n    const result = this._root.set(key, value, this)\n    if (result === true || result === false) return result\n    // Root node has split, so create a new root node.\n    this._root = new BNodeInternal<K, V>([this._root, result])\n    return true\n  }\n\n  /**\n   * Removes a single key-value pair from the B+ tree.\n   * @returns true if a pair was found and removed, false otherwise.\n   * @description Computational complexity: O(log size)\n   */\n  delete(key: K): boolean {\n    const size = this._size\n    let root = this._root\n    root.forRange(key, key, true, true, this)\n    // Collapse roots left with at most one child by the deletion.\n    while (root.keys.length <= 1 && !root.isLeaf) {\n      this._root = root =\n        root.keys.length === 0\n          ? new BNode<K, V>()\n          : (root as any as BNodeInternal<K, V>).children[0]!\n    }\n    return this._size !== size\n  }\n\n  /** Gets the lowest key in the tree. Complexity: O(log size) */\n  minKey(): K | undefined {\n    return this._root.minKey()\n  }\n\n  /** Gets the highest key in the tree. Complexity: O(1) */\n  maxKey(): K | undefined {\n    return this._root.maxKey()\n  }\n\n  /** Returns the next pair whose key is larger than the specified key (or undefined if there is none).\n   * If key === undefined, this function returns the lowest pair.\n   */\n  nextHigherPair(key: K | undefined): [K, V] | undefined {\n    return key === undefined\n      ? this._root.minPair()\n      : this._root.getPairOrNextHigher(key, this._compare)\n  }\n\n  /** Returns the next pair whose key is smaller than the specified key (or undefined if there is none).\n   *  If key === undefined, this function returns the highest pair.\n   */\n  nextLowerPair(key: K | undefined): [K, V] | undefined {\n    return key === undefined\n      ? this._root.maxPair()\n      : this._root.getPairOrNextLower(key, this._compare)\n  }\n\n  /**\n   * Scans the specified range of keys, in ascending order by key.\n   * Note: the callback `onFound` must not insert or remove items in the\n   * collection. Doing so may cause incorrect data to be sent to the\n   * callback afterward.\n   * @param low The first key scanned will be greater than or equal to `low`.\n   * @param high Scanning stops when a key larger than this is reached.\n   * @param includeHigh If the `high` key is present, `onFound` is called for\n   *        that final pair if and only if this parameter is true.\n   * @description Computational complexity: O(number of items scanned + log size)\n   */\n  forRange(\n    low: K,\n    high: K,\n    includeHigh: boolean,\n    onFound: (k: K, v: V) => void,\n  ): void {\n    this._root.forRange(low, high, includeHigh, false, this, onFound)\n  }\n}\n\n/** Leaf node / base class. **************************************************/\nclass BNode<K, V> {\n  // If this is an internal node, _keys[i] is the highest key in children[i].\n  keys: Array<K>\n  values: Array<V>\n  get isLeaf() {\n    return (this as any).children === undefined\n  }\n\n  constructor(keys: Array<K> = [], values: Array<V> = []) {\n    this.keys = keys\n    this.values = values\n  }\n\n  // /////////////////////////////////////////////////////////////////////////\n  // Shared methods /////////////////////////////////////////////////////////\n\n  maxKey() {\n    return this.keys[this.keys.length - 1]\n  }\n\n  // If key not found, returns i^failXor where i is the insertion index.\n  // Callers that don't care whether there was a match will set failXor=0.\n  indexOf(key: K, failXor: number, cmp: (a: K, b: K) => number): number {\n    const keys = this.keys\n    let lo = 0,\n      hi = keys.length,\n      mid = hi >> 1\n    while (lo < hi) {\n      const c = cmp(keys[mid]!, key)\n      if (c < 0) lo = mid + 1\n      else if (c > 0)\n        // key < keys[mid]\n        hi = mid\n      else return mid\n      mid = (lo + hi) >> 1\n    }\n    return mid ^ failXor\n  }\n\n  // ///////////////////////////////////////////////////////////////////////////\n  // Leaf Node: misc //////////////////////////////////////////////////////////\n\n  minKey(): K | undefined {\n    return this.keys[0]\n  }\n\n  /** Returns the pair at index `i`, or undefined when `i` is out of range. */\n  pairAt(i: number): [K, V] | undefined {\n    return i >= 0 && i < this.keys.length\n      ? [this.keys[i]!, this.values[i]!]\n      : undefined\n  }\n\n  minPair(): [K, V] | undefined {\n    return this.pairAt(0)\n  }\n\n  maxPair(): [K, V] | undefined {\n    return this.pairAt(this.keys.length - 1)\n  }\n\n  get(key: K, defaultValue: V | undefined, tree: BTree<K, V>): V | undefined {\n    const i = this.indexOf(key, -1, tree._compare)\n    return i < 0 ? defaultValue : this.values[i]\n  }\n\n  // Strictly lower / higher neighbours of `key` within this leaf.\n  getPairOrNextLower(\n    key: K,\n    compare: (a: K, b: K) => number,\n  ): [K, V] | undefined {\n    const i = this.indexOf(key, -1, compare)\n    return this.pairAt(i < 0 ? ~i - 1 : i - 1)\n  }\n\n  getPairOrNextHigher(\n    key: K,\n    compare: (a: K, b: K) => number,\n  ): [K, V] | undefined {\n    const i = this.indexOf(key, -1, compare)\n    return this.pairAt(i < 0 ? ~i : i + 1)\n  }\n\n  // ///////////////////////////////////////////////////////////////////////////\n  // Leaf Node: set & node splitting //////////////////////////////////////////\n\n  set(key: K, value: V, tree: BTree<K, V>): boolean | BNode<K, V> {\n    let i = this.indexOf(key, -1, tree._compare)\n    if (i >= 0) {\n      // Key already exists. Overwrite both key and value.\n      this.keys[i] = key\n      this.values[i] = value\n      return false\n    }\n    i = ~i\n    tree._size++\n    let target: BNode<K, V> = this\n    let newRightSibling: BNode<K, V> | undefined\n    if (this.keys.length >= tree._maxNodeSize) {\n      // This leaf node is full and must split\n      newRightSibling = this.splitOffRightSide()\n      if (i > this.keys.length) {\n        i -= this.keys.length\n        target = newRightSibling\n      }\n    }\n    target.keys.splice(i, 0, key)\n    target.values.splice(i, 0, value)\n    return newRightSibling ?? true\n  }\n\n  takeFromRight(rhs: BNode<K, V>) {\n    // Reminder: parent node must update its copy of key for this node\n    this.values.push(rhs.values.shift()!)\n    this.keys.push(rhs.keys.shift()!)\n  }\n\n  splitOffRightSide(): BNode<K, V> {\n    // Reminder: parent node must update its copy of key for this node\n    const half = this.keys.length >> 1\n    return new BNode<K, V>(this.keys.splice(half), this.values.splice(half))\n  }\n\n  // ///////////////////////////////////////////////////////////////////////////\n  // Leaf Node: scanning & deletions //////////////////////////////////////////\n\n  // Visits [low, high] (or [low, high)) with `onFound`, or deletes that range\n  // when `deleteMode` is set.\n  forRange(\n    low: K,\n    high: K,\n    includeHigh: boolean,\n    deleteMode: boolean,\n    tree: BTree<K, V>,\n    onFound?: (k: K, v: V) => void,\n  ): void {\n    const cmp = tree._compare\n    let iLow, iHigh\n    if (high === low) {\n      // A point range (as used by delete) needs only one search.\n      if (!includeHigh) return\n      iHigh = (iLow = this.indexOf(low, -1, cmp)) + 1\n      if (iLow < 0) return\n    } else {\n      iLow = this.indexOf(low, 0, cmp)\n      iHigh = this.indexOf(high, -1, cmp)\n      if (iHigh < 0) iHigh = ~iHigh\n      else if (includeHigh) iHigh++\n    }\n    if (deleteMode) {\n      if (iHigh > iLow) {\n        this.keys.splice(iLow, iHigh - iLow)\n        this.values.splice(iLow, iHigh - iLow)\n        tree._size -= iHigh - iLow\n      }\n    } else {\n      for (let i = iLow; i < iHigh; i++)\n        onFound!(this.keys[i]!, this.values[i]!)\n    }\n  }\n\n  /** Adds entire contents of right-hand sibling (rhs is left unchanged) */\n  mergeSibling(rhs: BNode<K, V>, _: number) {\n    this.keys.push.apply(this.keys, rhs.keys)\n    this.values.push.apply(this.values, rhs.values)\n  }\n}\n\n/** Internal node (non-leaf node) ********************************************/\nclass BNodeInternal<K, V> extends BNode<K, V> {\n  // Note: conventionally B+ trees have one fewer key than the number of\n  // children, but I find it easier to keep the array lengths equal: each\n  // keys[i] caches the value of children[i].maxKey().\n  children: Array<BNode<K, V>>\n\n  constructor(children: Array<BNode<K, V>>, keys?: Array<K>) {\n    super(keys ?? children.map((child) => child.maxKey()!))\n    this.children = children\n  }\n\n  minKey() {\n    return this.children[0]!.minKey()\n  }\n\n  minPair(): [K, V] | undefined {\n    return this.children[0]!.minPair()\n  }\n\n  maxPair(): [K, V] | undefined {\n    return this.children[this.children.length - 1]!.maxPair()\n  }\n\n  get(key: K, defaultValue: V | undefined, tree: BTree<K, V>): V | undefined {\n    const i = this.indexOf(key, 0, tree._compare),\n      children = this.children\n    return i < children.length\n      ? children[i]!.get(key, defaultValue, tree)\n      : defaultValue\n  }\n\n  getPairOrNextLower(\n    key: K,\n    compare: (a: K, b: K) => number,\n  ): [K, V] | undefined {\n    const i = this.indexOf(key, 0, compare),\n      children = this.children\n    if (i >= children.length) return this.maxPair()\n    return (\n      children[i]!.getPairOrNextLower(key, compare) ??\n      (i > 0 ? children[i - 1]!.maxPair() : undefined)\n    )\n  }\n\n  getPairOrNextHigher(\n    key: K,\n    compare: (a: K, b: K) => number,\n  ): [K, V] | undefined {\n    const i = this.indexOf(key, 0, compare),\n      children = this.children\n    if (i >= children.length) return undefined\n    return (\n      children[i]!.getPairOrNextHigher(key, compare) ??\n      children[i + 1]?.minPair()\n    )\n  }\n\n  // ///////////////////////////////////////////////////////////////////////////\n  // Internal Node: set & node splitting //////////////////////////////////////\n\n  set(key: K, value: V, tree: BTree<K, V>): boolean | BNodeInternal<K, V> {\n    const c = this.children,\n      max = tree._maxNodeSize,\n      cmp = tree._compare\n    let i = Math.min(this.indexOf(key, 0, cmp), c.length - 1)\n    const child = c[i]!\n\n    if (child.keys.length >= max) {\n      // child is full; inserting anything else will cause a split.\n      // Shifting an item to the left sibling may avoid a split. We can do a\n      // shift if that sibling is not full and if the current key can still be\n      // placed in the same node after the shift. A right shift would need a\n      // key above child.maxKey(), and that only reaches the last child.\n      let other: BNode<K, V> | undefined\n      if (\n        i > 0 &&\n        (other = c[i - 1]!).keys.length < max &&\n        cmp(child.keys[0]!, key) < 0\n      ) {\n        other.takeFromRight(child)\n        this.keys[i - 1] = other.maxKey()!\n      }\n    }\n\n    const result = child.set(key, value, tree)\n    if (result === false) return false\n    this.keys[i] = child.maxKey()!\n    if (result === true) return true\n\n    // The child has split and `result` is a new right child... does it fit?\n    let target: BNodeInternal<K, V> = this\n    let newRightSibling: BNodeInternal<K, V> | undefined\n    if (this.keys.length >= max) {\n      // no, we must split also\n      newRightSibling = this.splitOffRightSide()\n      // The new child follows i; no comparison is needed after mutation.\n      if (i + 1 >= this.keys.length) {\n        target = newRightSibling\n        i -= this.keys.length\n      }\n    }\n    target.children.splice(i + 1, 0, result)\n    target.keys.splice(i + 1, 0, result.maxKey()!)\n    return newRightSibling ?? true\n  }\n\n  /**\n   * Split this node.\n   * Modifies this to remove the second half of the items, returning a separate node containing them.\n   */\n  splitOffRightSide() {\n    const half = this.children.length >> 1\n    return new BNodeInternal<K, V>(\n      this.children.splice(half),\n      this.keys.splice(half),\n    )\n  }\n\n  takeFromRight(rhs: BNode<K, V>) {\n    // Reminder: parent node must update its copy of key for this node\n    this.keys.push(rhs.keys.shift()!)\n    this.children.push((rhs as BNodeInternal<K, V>).children.shift()!)\n  }\n\n  // ///////////////////////////////////////////////////////////////////////////\n  // Internal Node: scanning & deletions //////////////////////////////////////\n\n  forRange(\n    low: K,\n    high: K,\n    includeHigh: boolean,\n    deleteMode: boolean,\n    tree: BTree<K, V>,\n    onFound?: (k: K, v: V) => void,\n  ): void {\n    const cmp = tree._compare\n    const keys = this.keys,\n      children = this.children\n    let iLow = this.indexOf(low, 0, cmp),\n      i = iLow\n    // A point range (as used by delete) needs only one search.\n    const iHigh = Math.min(\n      high === low ? iLow : this.indexOf(high, 0, cmp),\n      keys.length - 1,\n    )\n    for (; i <= iHigh; i++) {\n      children[i]!.forRange(low, high, includeHigh, deleteMode, tree, onFound)\n      // Note: if children[i] is empty then keys[i]=undefined.\n      //       This is an invalid state, but it is fixed below.\n      if (deleteMode) keys[i] = children[i]!.maxKey()!\n    }\n    if (deleteMode) {\n      // Deletions may have occurred, so look for opportunities to merge nodes.\n      const half = tree._maxNodeSize >> 1\n      if (iLow > 0) iLow--\n      for (i = iHigh; i >= iLow; i--) {\n        if (children[i]!.keys.length <= half) {\n          if (children[i]!.keys.length !== 0) {\n            this.tryMerge(i, tree._maxNodeSize)\n          } else {\n            // child is empty! delete it!\n            keys.splice(i, 1)\n            children.splice(i, 1)\n          }\n        }\n      }\n    }\n  }\n\n  /** Merges child i with child i+1 if their combined size is not too large */\n  tryMerge(i: number, maxSize: number): void {\n    const children = this.children\n    if (\n      i >= 0 &&\n      i + 1 < children.length &&\n      children[i]!.keys.length + children[i + 1]!.keys.length <= maxSize\n    ) {\n      children[i]!.mergeSibling(children[i + 1]!, maxSize)\n      children.splice(i + 1, 1)\n      this.keys.splice(i + 1, 1)\n      this.keys[i] = children[i]!.maxKey()!\n    }\n  }\n\n  /**\n   * Move children from `rhs` into this.\n   * `rhs` must be part of this tree, and be removed from it after this call.\n   */\n  mergeSibling(rhs: BNode<K, V>, maxNodeSize: number) {\n    const oldLength = this.keys.length\n    this.keys.push.apply(this.keys, rhs.keys)\n    const rhsChildren = (rhs as any as BNodeInternal<K, V>).children\n    this.children.push.apply(this.children, rhsChildren)\n\n    // If our children are themselves almost empty due to a mass-delete,\n    // they may need to be merged too (but only the oldLength-1 and its\n    // right sibling should need this).\n    this.tryMerge(oldLength - 1, maxNodeSize)\n  }\n}\n"],"names":[],"mappings":";;AAmCO,MAAM,MAAwB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAiB5B,YAAY,SAAiC,aAAsB;AAhB1E,SAAQ,QAAqB,IAAI,MAAA;AACjC,SAAA,QAAQ;AAgBN,SAAK,eAAe,eAAgB,IAAI,KAAK,IAAI,aAAc,GAAG,IAAI;AACtE,SAAK,WAAW;AAAA,EAClB;AAAA;AAAA,EAGA,IAAI,OAAO;AACT,WAAO,KAAK;AAAA,EACd;AAAA;AAAA,EAGA,QAAQ;AACN,SAAK,QAAQ,IAAI,MAAA;AACjB,SAAK,QAAQ;AAAA,EACf;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAI,KAAQ,cAAiC;AAC3C,WAAO,KAAK,MAAM,IAAI,KAAK,cAAc,IAAI;AAAA,EAC/C;AAAA;AAAA,EAGA,IAAI,KAAiB;AACnB,UAAM,UAAU,CAAA;AAChB,WAAO,KAAK,IAAI,KAAK,OAAO,MAAM;AAAA,EACpC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAI,KAAQ,OAAmB;AAC7B,UAAM,SAAS,KAAK,MAAM,IAAI,KAAK,OAAO,IAAI;AAC9C,QAAI,WAAW,QAAQ,WAAW,MAAO,QAAO;AAEhD,SAAK,QAAQ,IAAI,cAAoB,CAAC,KAAK,OAAO,MAAM,CAAC;AACzD,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,OAAO,KAAiB;AACtB,UAAM,OAAO,KAAK;AAClB,QAAI,OAAO,KAAK;AAChB,SAAK,SAAS,KAAK,KAAK,MAAM,MAAM,IAAI;AAExC,WAAO,KAAK,KAAK,UAAU,KAAK,CAAC,KAAK,QAAQ;AAC5C,WAAK,QAAQ,OACX,KAAK,KAAK,WAAW,IACjB,IAAI,MAAA,IACH,KAAoC,SAAS,CAAC;AAAA,IACvD;AACA,WAAO,KAAK,UAAU;AAAA,EACxB;AAAA;AAAA,EAGA,SAAwB;AACtB,WAAO,KAAK,MAAM,OAAA;AAAA,EACpB;AAAA;AAAA,EAGA,SAAwB;AACtB,WAAO,KAAK,MAAM,OAAA;AAAA,EACpB;AAAA;AAAA;AAAA;AAAA,EAKA,eAAe,KAAwC;AACrD,WAAO,QAAQ,SACX,KAAK,MAAM,QAAA,IACX,KAAK,MAAM,oBAAoB,KAAK,KAAK,QAAQ;AAAA,EACvD;AAAA;AAAA;AAAA;AAAA,EAKA,cAAc,KAAwC;AACpD,WAAO,QAAQ,SACX,KAAK,MAAM,QAAA,IACX,KAAK,MAAM,mBAAmB,KAAK,KAAK,QAAQ;AAAA,EACtD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAaA,SACE,KACA,MACA,aACA,SACM;AACN,SAAK,MAAM,SAAS,KAAK,MAAM,aAAa,OAAO,MAAM,OAAO;AAAA,EAClE;AACF;AAGA,MAAM,MAAY;AAAA,EAIhB,IAAI,SAAS;AACX,WAAQ,KAAa,aAAa;AAAA,EACpC;AAAA,EAEA,YAAY,OAAiB,IAAI,SAAmB,CAAA,GAAI;AACtD,SAAK,OAAO;AACZ,SAAK,SAAS;AAAA,EAChB;AAAA;AAAA;AAAA,EAKA,SAAS;AACP,WAAO,KAAK,KAAK,KAAK,KAAK,SAAS,CAAC;AAAA,EACvC;AAAA;AAAA;AAAA,EAIA,QAAQ,KAAQ,SAAiB,KAAqC;AACpE,UAAM,OAAO,KAAK;AAClB,QAAI,KAAK,GACP,KAAK,KAAK,QACV,MAAM,MAAM;AACd,WAAO,KAAK,IAAI;AACd,YAAM,IAAI,IAAI,KAAK,GAAG,GAAI,GAAG;AAC7B,UAAI,IAAI,EAAG,MAAK,MAAM;AAAA,eACb,IAAI;AAEX,aAAK;AAAA,UACF,QAAO;AACZ,YAAO,KAAK,MAAO;AAAA,IACrB;AACA,WAAO,MAAM;AAAA,EACf;AAAA;AAAA;AAAA,EAKA,SAAwB;AACtB,WAAO,KAAK,KAAK,CAAC;AAAA,EACpB;AAAA;AAAA,EAGA,OAAO,GAA+B;AACpC,WAAO,KAAK,KAAK,IAAI,KAAK,KAAK,SAC3B,CAAC,KAAK,KAAK,CAAC,GAAI,KAAK,OAAO,CAAC,CAAE,IAC/B;AAAA,EACN;AAAA,EAEA,UAA8B;AAC5B,WAAO,KAAK,OAAO,CAAC;AAAA,EACtB;AAAA,EAEA,UAA8B;AAC5B,WAAO,KAAK,OAAO,KAAK,KAAK,SAAS,CAAC;AAAA,EACzC;AAAA,EAEA,IAAI,KAAQ,cAA6B,MAAkC;AACzE,UAAM,IAAI,KAAK,QAAQ,KAAK,IAAI,KAAK,QAAQ;AAC7C,WAAO,IAAI,IAAI,eAAe,KAAK,OAAO,CAAC;AAAA,EAC7C;AAAA;AAAA,EAGA,mBACE,KACA,SACoB;AACpB,UAAM,IAAI,KAAK,QAAQ,KAAK,IAAI,OAAO;AACvC,WAAO,KAAK,OAAO,IAAI,IAAI,CAAC,IAAI,IAAI,IAAI,CAAC;AAAA,EAC3C;AAAA,EAEA,oBACE,KACA,SACoB;AACpB,UAAM,IAAI,KAAK,QAAQ,KAAK,IAAI,OAAO;AACvC,WAAO,KAAK,OAAO,IAAI,IAAI,CAAC,IAAI,IAAI,CAAC;AAAA,EACvC;AAAA;AAAA;AAAA,EAKA,IAAI,KAAQ,OAAU,MAA0C;AAC9D,QAAI,IAAI,KAAK,QAAQ,KAAK,IAAI,KAAK,QAAQ;AAC3C,QAAI,KAAK,GAAG;AAEV,WAAK,KAAK,CAAC,IAAI;AACf,WAAK,OAAO,CAAC,IAAI;AACjB,aAAO;AAAA,IACT;AACA,QAAI,CAAC;AACL,SAAK;AACL,QAAI,SAAsB;AAC1B,QAAI;AACJ,QAAI,KAAK,KAAK,UAAU,KAAK,cAAc;AAEzC,wBAAkB,KAAK,kBAAA;AACvB,UAAI,IAAI,KAAK,KAAK,QAAQ;AACxB,aAAK,KAAK,KAAK;AACf,iBAAS;AAAA,MACX;AAAA,IACF;AACA,WAAO,KAAK,OAAO,GAAG,GAAG,GAAG;AAC5B,WAAO,OAAO,OAAO,GAAG,GAAG,KAAK;AAChC,WAAO,mBAAmB;AAAA,EAC5B;AAAA,EAEA,cAAc,KAAkB;AAE9B,SAAK,OAAO,KAAK,IAAI,OAAO,OAAQ;AACpC,SAAK,KAAK,KAAK,IAAI,KAAK,OAAQ;AAAA,EAClC;AAAA,EAEA,oBAAiC;AAE/B,UAAM,OAAO,KAAK,KAAK,UAAU;AACjC,WAAO,IAAI,MAAY,KAAK,KAAK,OAAO,IAAI,GAAG,KAAK,OAAO,OAAO,IAAI,CAAC;AAAA,EACzE;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,SACE,KACA,MACA,aACA,YACA,MACA,SACM;AACN,UAAM,MAAM,KAAK;AACjB,QAAI,MAAM;AACV,QAAI,SAAS,KAAK;AAEhB,UAAI,CAAC,YAAa;AAClB,eAAS,OAAO,KAAK,QAAQ,KAAK,IAAI,GAAG,KAAK;AAC9C,UAAI,OAAO,EAAG;AAAA,IAChB,OAAO;AACL,aAAO,KAAK,QAAQ,KAAK,GAAG,GAAG;AAC/B,cAAQ,KAAK,QAAQ,MAAM,IAAI,GAAG;AAClC,UAAI,QAAQ,EAAG,SAAQ,CAAC;AAAA,eACf,YAAa;AAAA,IACxB;AACA,QAAI,YAAY;AACd,UAAI,QAAQ,MAAM;AAChB,aAAK,KAAK,OAAO,MAAM,QAAQ,IAAI;AACnC,aAAK,OAAO,OAAO,MAAM,QAAQ,IAAI;AACrC,aAAK,SAAS,QAAQ;AAAA,MACxB;AAAA,IACF,OAAO;AACL,eAAS,IAAI,MAAM,IAAI,OAAO;AAC5B,gBAAS,KAAK,KAAK,CAAC,GAAI,KAAK,OAAO,CAAC,CAAE;AAAA,IAC3C;AAAA,EACF;AAAA;AAAA,EAGA,aAAa,KAAkB,GAAW;AACxC,SAAK,KAAK,KAAK,MAAM,KAAK,MAAM,IAAI,IAAI;AACxC,SAAK,OAAO,KAAK,MAAM,KAAK,QAAQ,IAAI,MAAM;AAAA,EAChD;AACF;AAGA,MAAM,sBAA4B,MAAY;AAAA,EAM5C,YAAY,UAA8B,MAAiB;AACzD,UAAM,QAAQ,SAAS,IAAI,CAAC,UAAU,MAAM,OAAA,CAAS,CAAC;AACtD,SAAK,WAAW;AAAA,EAClB;AAAA,EAEA,SAAS;AACP,WAAO,KAAK,SAAS,CAAC,EAAG,OAAA;AAAA,EAC3B;AAAA,EAEA,UAA8B;AAC5B,WAAO,KAAK,SAAS,CAAC,EAAG,QAAA;AAAA,EAC3B;AAAA,EAEA,UAA8B;AAC5B,WAAO,KAAK,SAAS,KAAK,SAAS,SAAS,CAAC,EAAG,QAAA;AAAA,EAClD;AAAA,EAEA,IAAI,KAAQ,cAA6B,MAAkC;AACzE,UAAM,IAAI,KAAK,QAAQ,KAAK,GAAG,KAAK,QAAQ,GAC1C,WAAW,KAAK;AAClB,WAAO,IAAI,SAAS,SAChB,SAAS,CAAC,EAAG,IAAI,KAAK,cAAc,IAAI,IACxC;AAAA,EACN;AAAA,EAEA,mBACE,KACA,SACoB;AACpB,UAAM,IAAI,KAAK,QAAQ,KAAK,GAAG,OAAO,GACpC,WAAW,KAAK;AAClB,QAAI,KAAK,SAAS,OAAQ,QAAO,KAAK,QAAA;AACtC,WACE,SAAS,CAAC,EAAG,mBAAmB,KAAK,OAAO,MAC3C,IAAI,IAAI,SAAS,IAAI,CAAC,EAAG,YAAY;AAAA,EAE1C;AAAA,EAEA,oBACE,KACA,SACoB;AACpB,UAAM,IAAI,KAAK,QAAQ,KAAK,GAAG,OAAO,GACpC,WAAW,KAAK;AAClB,QAAI,KAAK,SAAS,OAAQ,QAAO;AACjC,WACE,SAAS,CAAC,EAAG,oBAAoB,KAAK,OAAO,KAC7C,SAAS,IAAI,CAAC,GAAG,QAAA;AAAA,EAErB;AAAA;AAAA;AAAA,EAKA,IAAI,KAAQ,OAAU,MAAkD;AACtE,UAAM,IAAI,KAAK,UACb,MAAM,KAAK,cACX,MAAM,KAAK;AACb,QAAI,IAAI,KAAK,IAAI,KAAK,QAAQ,KAAK,GAAG,GAAG,GAAG,EAAE,SAAS,CAAC;AACxD,UAAM,QAAQ,EAAE,CAAC;AAEjB,QAAI,MAAM,KAAK,UAAU,KAAK;AAM5B,UAAI;AACJ,UACE,IAAI,MACH,QAAQ,EAAE,IAAI,CAAC,GAAI,KAAK,SAAS,OAClC,IAAI,MAAM,KAAK,CAAC,GAAI,GAAG,IAAI,GAC3B;AACA,cAAM,cAAc,KAAK;AACzB,aAAK,KAAK,IAAI,CAAC,IAAI,MAAM,OAAA;AAAA,MAC3B;AAAA,IACF;AAEA,UAAM,SAAS,MAAM,IAAI,KAAK,OAAO,IAAI;AACzC,QAAI,WAAW,MAAO,QAAO;AAC7B,SAAK,KAAK,CAAC,IAAI,MAAM,OAAA;AACrB,QAAI,WAAW,KAAM,QAAO;AAG5B,QAAI,SAA8B;AAClC,QAAI;AACJ,QAAI,KAAK,KAAK,UAAU,KAAK;AAE3B,wBAAkB,KAAK,kBAAA;AAEvB,UAAI,IAAI,KAAK,KAAK,KAAK,QAAQ;AAC7B,iBAAS;AACT,aAAK,KAAK,KAAK;AAAA,MACjB;AAAA,IACF;AACA,WAAO,SAAS,OAAO,IAAI,GAAG,GAAG,MAAM;AACvC,WAAO,KAAK,OAAO,IAAI,GAAG,GAAG,OAAO,QAAS;AAC7C,WAAO,mBAAmB;AAAA,EAC5B;AAAA;AAAA;AAAA;AAAA;AAAA,EAMA,oBAAoB;AAClB,UAAM,OAAO,KAAK,SAAS,UAAU;AACrC,WAAO,IAAI;AAAA,MACT,KAAK,SAAS,OAAO,IAAI;AAAA,MACzB,KAAK,KAAK,OAAO,IAAI;AAAA,IAAA;AAAA,EAEzB;AAAA,EAEA,cAAc,KAAkB;AAE9B,SAAK,KAAK,KAAK,IAAI,KAAK,OAAQ;AAChC,SAAK,SAAS,KAAM,IAA4B,SAAS,OAAQ;AAAA,EACnE;AAAA;AAAA;AAAA,EAKA,SACE,KACA,MACA,aACA,YACA,MACA,SACM;AACN,UAAM,MAAM,KAAK;AACjB,UAAM,OAAO,KAAK,MAChB,WAAW,KAAK;AAClB,QAAI,OAAO,KAAK,QAAQ,KAAK,GAAG,GAAG,GACjC,IAAI;AAEN,UAAM,QAAQ,KAAK;AAAA,MACjB,SAAS,MAAM,OAAO,KAAK,QAAQ,MAAM,GAAG,GAAG;AAAA,MAC/C,KAAK,SAAS;AAAA,IAAA;AAEhB,WAAO,KAAK,OAAO,KAAK;AACtB,eAAS,CAAC,EAAG,SAAS,KAAK,MAAM,aAAa,YAAY,MAAM,OAAO;AAGvE,UAAI,WAAY,MAAK,CAAC,IAAI,SAAS,CAAC,EAAG,OAAA;AAAA,IACzC;AACA,QAAI,YAAY;AAEd,YAAM,OAAO,KAAK,gBAAgB;AAClC,UAAI,OAAO,EAAG;AACd,WAAK,IAAI,OAAO,KAAK,MAAM,KAAK;AAC9B,YAAI,SAAS,CAAC,EAAG,KAAK,UAAU,MAAM;AACpC,cAAI,SAAS,CAAC,EAAG,KAAK,WAAW,GAAG;AAClC,iBAAK,SAAS,GAAG,KAAK,YAAY;AAAA,UACpC,OAAO;AAEL,iBAAK,OAAO,GAAG,CAAC;AAChB,qBAAS,OAAO,GAAG,CAAC;AAAA,UACtB;AAAA,QACF;AAAA,MACF;AAAA,IACF;AAAA,EACF;AAAA;AAAA,EAGA,SAAS,GAAW,SAAuB;AACzC,UAAM,WAAW,KAAK;AACtB,QACE,KAAK,KACL,IAAI,IAAI,SAAS,UACjB,SAAS,CAAC,EAAG,KAAK,SAAS,SAAS,IAAI,CAAC,EAAG,KAAK,UAAU,SAC3D;AACA,eAAS,CAAC,EAAG,aAAa,SAAS,IAAI,CAAC,GAAI,OAAO;AACnD,eAAS,OAAO,IAAI,GAAG,CAAC;AACxB,WAAK,KAAK,OAAO,IAAI,GAAG,CAAC;AACzB,WAAK,KAAK,CAAC,IAAI,SAAS,CAAC,EAAG,OAAA;AAAA,IAC9B;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA,EAMA,aAAa,KAAkB,aAAqB;AAClD,UAAM,YAAY,KAAK,KAAK;AAC5B,SAAK,KAAK,KAAK,MAAM,KAAK,MAAM,IAAI,IAAI;AACxC,UAAM,cAAe,IAAmC;AACxD,SAAK,SAAS,KAAK,MAAM,KAAK,UAAU,WAAW;AAKnD,SAAK,SAAS,YAAY,GAAG,WAAW;AAAA,EAC1C;AACF;;"}