{"version":3,"sources":["jsdelivr-header.js","/npm/kdb-tree@1.1.2/index.js"],"names":[],"mappings":"AAAA;AACA;AACA;AACA;AACA;AACA;AACA,ACNA,IAAI,OAAS,QAAQ,UACjB,OAAS,EAAG,OAAS,EAIzB,SAAS,IAAK,GACZ,KAAM,gBAAgB,KAAM,OAAO,IAAI,IAAI,GAC3C,KAAK,EAAI,EAAK,GAAK,EACnB,KAAK,EAAI,EAAK,GAAK,EACnB,KAAK,IAAM,EAAK,IAChB,KAAK,KAAO,CACV,KAAM,OACN,QAAS,CACP,CACE,MAAO,GACP,KAAM,CACJ,KAAM,OACN,OAAQ,OAKhB,IAAK,IAAI,EAAI,EAAG,EAAI,KAAK,IAAK,IAC5B,KAAK,KAAK,QAAQ,GAAG,MAAM,KAAK,EAAE,IAAS,KAE/C,CA+IA,SAAS,iBAAkB,EAAG,GAC5B,IAAK,IAAI,EAAI,EAAG,EAAI,EAAE,OAAQ,IAC5B,IAAK,cAAc,EAAE,GAAG,GAAI,EAAE,GAAG,GAAI,EAAE,GAAI,EAAE,IAAK,OAAO,EAE3D,OAAO,CACT,CAEA,SAAS,cAAe,EAAM,EAAM,EAAM,GACxC,OAAQ,GAAQ,GAAQ,GAAQ,GAC1B,GAAQ,GAAQ,GAAQ,GACxB,EAAO,GAAQ,EAAO,CAC9B,CAEA,SAAS,iBAAkB,EAAG,GAC5B,IAAK,IAAI,EAAI,EAAG,EAAI,EAAE,OAAQ,IAC5B,IAAK,YAAY,EAAE,GAAI,EAAE,IAAK,OAAO,EAEvC,OAAO,CACT,CAEA,SAAS,YAAa,EAAG,GACvB,OAAQ,EAAE,IAAM,EAAE,IAAM,EAAE,IAAM,EAAE,IAC5B,EAAE,IAAM,EAAE,IAAM,EAAE,IAAM,EAAE,IAC1B,EAAE,GAAK,EAAE,IAAM,EAAE,GAAK,EAAE,EAChC,CAEA,SAAS,MAAO,GACd,OAAO,EAAG,KAAI,SAAU,GAAK,OAAO,EAAE,OAAQ,GAChD,CAEA,SAAS,YAAa,EAAK,GAEzB,IADA,IAAI,EAAQ,GACH,EAAI,EAAG,EAAI,EAAK,IAAK,CAC5B,IAAI,EAAwB,IAAnB,EAAQ,OACb,EAAE,IAAS,KACX,EAAQ,GAAG,MAAM,GACrB,EAAM,GAAK,CAAC,EAAG,GAAG,EAAG,IACrB,IAAK,IAAI,EAAI,EAAG,EAAI,EAAQ,OAAQ,IAAK,CACvC,IAAI,EAAI,EAAQ,GAAG,MACf,EAAE,GAAG,GAAK,EAAM,GAAG,KAAI,EAAM,GAAG,GAAK,EAAE,GAAG,IAC1C,EAAE,GAAG,GAAK,EAAM,GAAG,KAAI,EAAM,GAAG,GAAK,EAAE,GAAG,GAChD,CACF,CACA,OAAO,CACT,CAjNA,OAAO,QAAU,IAwBjB,IAAI,UAAU,MAAQ,SAAU,GAE9B,OADK,MAAM,QAAQ,EAAE,MAAK,EAAI,EAAE,KAAI,SAAU,GAAK,MAAO,CAAC,EAAE,EAAG,KACzD,SAAU,EAAO,GACtB,IAAI,EAAU,GACd,GAAI,EAAK,OAAS,OAChB,IAAK,IAAI,EAAI,EAAG,EAAI,EAAK,QAAQ,OAAQ,IAAK,CAC5C,IAAI,EAAI,EAAK,QAAQ,GACjB,iBAAiB,EAAG,EAAE,QACxB,EAAQ,KAAK,MAAM,EAAS,EAAM,EAAE,MAExC,MACK,GAAI,EAAK,OAAS,OACvB,IAAS,EAAI,EAAG,EAAI,EAAK,OAAO,OAAQ,IAAK,CAC3C,IAAI,EAAI,EAAK,OAAO,GAChB,iBAAiB,EAAG,EAAE,QAAQ,EAAQ,KAAK,EACjD,CAEF,OAAO,CACR,CAhBM,CAgBJ,KAAK,KACV,EAEA,IAAI,UAAU,OAAS,SAAU,EAAI,GAGnC,IAFA,IAAI,EAAO,KACP,EAAI,GACC,EAAI,EAAG,EAAI,EAAG,OAAQ,IAAK,EAAE,KAAK,CAAC,EAAG,GAAG,EAAG,KACrD,OAEA,SAAS,EAAQ,EAAM,GACrB,GAAI,EAAK,OAAS,OAAQ,CACxB,IAAK,IAAI,EAAI,EAAG,EAAI,EAAK,QAAQ,OAAQ,IAAK,CAC5C,IAAI,EAAI,EAAK,QAAQ,GACrB,GAAI,iBAAiB,EAAG,EAAE,OAExB,OADA,EAAE,KAAK,OAAS,CAAE,KAAM,EAAM,MAAO,GAC9B,EAAO,EAAE,KAAM,EAAQ,EAElC,CACA,MAAM,IAAI,MAAM,gBAClB,CAAO,GAAI,EAAK,OAAS,OAAQ,CAC/B,GAAI,EAAK,OAAO,OAAS,EAAK,EAE5B,YADA,EAAK,OAAO,KAAK,CAAE,MAAO,EAAI,MAAO,IAGvC,IAAI,EAAS,GACT,GAAQ,EAAQ,GAAK,EAAG,OAC5B,IAAS,EAAI,EAAG,EAAI,EAAK,OAAO,OAAQ,IACtC,EAAO,KAAK,EAAK,OAAO,GAAG,MAAM,IAEnC,IAAI,EAAQ,OAAO,GACnB,IAAK,EAAK,OACR,MAAM,IAAI,MAAM,gBACX,GAAI,EAAK,OAAO,KAAK,QAAQ,QAAU,EAAK,EAAI,EAAG,CAExD,IADA,IAAI,EAAI,EAAK,OACN,EAAE,KAAK,QAAQ,QAAU,EAAK,EAAI,GAAG,CAC1C,IAAI,EAAQ,EAAgB,EAAG,EAAO,GACtC,GAAI,EAAE,OAAS,EAAK,KAMlB,OALA,EAAE,MAAQ,YAAY,EAAK,IAAK,EAAE,KAAK,SACvC,EAAK,KAAO,CACV,KAAM,OACN,QAAS,CAAE,EAAG,IAET,EAAO,EAAK,KAAM,GAEzB,EAAE,KAAK,QAAQ,KAAK,GACpB,EAAI,EAAE,KAAK,MAEf,CACA,EAAO,EAAE,KAAM,EAAM,EACvB,KAAO,CACD,EAAQ,EAAe,EAAM,EAAO,GAAxC,IACI,EAAQ,EAAK,OAAO,KACpB,EAAM,EAAK,OAAO,MAClB,EAAS,MAAM,EAAM,QAAQ,GAAK,OAClC,EAAS,MAAM,EAAM,QAAQ,GAAK,OACtC,EAAO,GAAM,GAAK,EAClB,EAAO,GAAM,GAAK,EAClB,IAAI,EAAU,CAAE,MAAO,EAAQ,KAAM,GACjC,EAAU,CAAE,MAAO,EAAQ,KAAM,GACrC,EAAM,QAAQ,GAAO,EACrB,EAAM,QAAQ,KAAK,GACnB,EAAO,EAAO,EAAM,EACtB,CACF,CACF,CAzDO,CAAO,KAAK,KAAM,GA2DzB,SAAS,EAAgB,EAAM,EAAO,GAEpC,IADA,IAAI,EAAQ,CAAE,KAAM,OAAQ,OAAQ,IAC3B,EAAI,EAAG,EAAI,EAAK,OAAO,OAAQ,IAAK,CAC3C,IAAI,EAAI,EAAK,OAAO,GAChB,EAAE,MAAM,IAAS,IACnB,EAAM,OAAO,KAAK,GAClB,EAAK,OAAO,OAAO,EAAG,GACtB,IAEJ,CACA,OAAO,CACT,CACA,SAAS,EAAiB,EAAM,EAAO,GACrC,IAAI,EAAS,YAAY,EAAK,IAAK,EAAK,KAAK,SAC7C,EAAO,GAAM,GAAK,EAWlB,IATA,IAAI,EAAQ,CACV,MAAO,EACP,KAAM,CACJ,KAAM,OACN,QAAS,KAGT,EAAO,EAEF,EAAI,EAAG,EAAI,EAAK,KAAK,QAAQ,OAAQ,IAAK,CACjD,IAAI,EAAI,EAAK,KAAK,QAAQ,GAC1B,GAAI,EAAE,MAAM,GAAM,IAAM,QAEjB,GAAI,EAAE,MAAM,GAAM,IAAM,EAC7B,EAAM,KAAK,QAAQ,KAAK,GACxB,EAAK,KAAK,QAAQ,OAAO,EAAG,GAC5B,QACK,CACL,IAAI,EAAS,CACX,MAAO,MAAM,EAAE,QAQjB,GANA,EAAO,MAAM,GAAM,GAAK,EACxB,EAAM,KAAK,QAAQ,KAAK,GAEZ,EACN,MAAM,GAAM,GAAK,EAEnB,EAAE,KAAK,OAAS,OAClB,EAAO,KAAO,EAAe,EAAE,KAAM,EAAO,OACvC,IAAI,EAAE,KAAK,OAAS,OAKpB,MAAM,IAAI,MAAM,iBAAmB,EAAE,KAAK,MAJ/C,EAAO,KAAO,CACZ,KAAM,OACN,QAAS,CAAE,EAAgB,EAAG,EAAO,IAEY,CACvD,CACF,CACA,OAAO,CACT,CACF","file":"/npm/kdb-tree@1.1.2/index.js","sourceRoot":"","sourcesContent":["/**\n * Minified by jsDelivr using Terser v5.39.0.\n * Original file: /npm/kdb-tree@1.1.2/index.js\n *\n * Do NOT use SRI with dynamically generated files! More information: https://www.jsdelivr.com/using-sri-with-dynamic-files\n */\n","var median = require('median')\nvar REGION = 0, POINTS = 1\n\nmodule.exports = KDB\n\nfunction KDB (opts) {\n  if (!(this instanceof KDB)) return new KDB(opts)\n  this.a = opts.a || 4 // points\n  this.b = opts.b || 3 // regions\n  this.dim = opts.dim\n  this.root = {\n    type: REGION,\n    regions: [\n      {\n        range: [],\n        node: {\n          type: POINTS,\n          points: []\n        }\n      }\n    ]\n  }\n  for (var i = 0; i < this.dim; i++) {\n    this.root.regions[0].range.push([-Infinity,Infinity])\n  }\n}\n\nKDB.prototype.query = function (q) {\n  if (!Array.isArray(q[0])) q = q.map(function (x) { return [x,x] })\n  return (function query (node) {\n    var results = []\n    if (node.type === REGION) {\n      for (var i = 0; i < node.regions.length; i++) {\n        var r = node.regions[i]\n        if (overlappingRange(q, r.range)) {\n          results.push.apply(results, query(r.node))\n        }\n      }\n    } else if (node.type === POINTS) {\n      for (var i = 0; i < node.points.length; i++) {\n        var p = node.points[i]\n        if (overlappingPoint(q, p.point)) results.push(p)\n      }\n    }\n    return results\n  })(this.root)\n}\n\nKDB.prototype.insert = function (pt, value) {\n  var self = this\n  var q = [], rec = { point: pt, value: value }\n  for (var i = 0; i < pt.length; i++) q.push([pt[i],pt[i]])\n  return insert(this.root, 0)\n\n  function insert (node, depth) {\n    if (node.type === REGION) {\n      for (var i = 0; i < node.regions.length; i++) {\n        var r = node.regions[i]\n        if (overlappingRange(q, r.range)) {\n          r.node.parent = { node: node, index: i }\n          return insert(r.node, depth + 1)\n        }\n      }\n      throw new Error('INVALID STATE')\n    } else if (node.type === POINTS) {\n      if (node.points.length < self.a) {\n        node.points.push({ point: pt, value: value })\n        return\n      }\n      var coords = []\n      var axis = (depth + 1) % pt.length\n      for (var i = 0; i < node.points.length; i++) {\n        coords.push(node.points[i].point[axis])\n      }\n      var pivot = median(coords)\n      if (!node.parent) {\n        throw new Error('at the root!')\n      } else if (node.parent.node.regions.length >= self.b - 1) {\n        var p = node.parent\n        while (p.node.regions.length >= self.b - 1) {\n          var right = splitRegionNode(p, pivot, axis)\n          if (p.node === self.root) {\n            p.range = regionRange(self.dim, p.node.regions)\n            self.root = {\n              type: REGION,\n              regions: [ p, right ]\n            }\n            return insert(self.root, 0)\n          } else {\n            p.node.regions.push(right)\n            p = p.node.parent\n          }\n        }\n        insert(p.node, depth+1)\n      } else {\n        var right = splitPointNode(node, pivot, axis)\n        var pnode = node.parent.node\n        var pix = node.parent.index\n        var lrange = clone(pnode.regions[pix].range)\n        var rrange = clone(pnode.regions[pix].range)\n        lrange[axis][1] = pivot\n        rrange[axis][0] = pivot\n        var lregion = { range: lrange, node: node }\n        var rregion = { range: rrange, node: right }\n        pnode.regions[pix] = lregion\n        pnode.regions.push(rregion)\n        insert(pnode, depth+1)\n      }\n    }\n  }\n\n  function splitPointNode (node, pivot, axis) {\n    var right = { type: POINTS, points: [] }\n    for (var i = 0; i < node.points.length; i++) {\n      var p = node.points[i]\n      if (p.point[axis] >= pivot) {\n        right.points.push(p)\n        node.points.splice(i, 1)\n        i--\n      }\n    }\n    return right\n  }\n  function splitRegionNode (node, pivot, axis) {\n    var rrange = regionRange(self.dim, node.node.regions)\n    rrange[axis][0] = pivot\n\n    var right = {\n      range: rrange,\n      node: {\n        type: REGION,\n        regions: []\n      }\n    }\n    var left = node\n\n    for (var i = 0; i < node.node.regions.length; i++) {\n      var r = node.node.regions[i]\n      if (r.range[axis][1] <= pivot) {\n        // already in the right place\n      } else if (r.range[axis][0] >= pivot) {\n        right.node.regions.push(r)\n        left.node.regions.splice(i, 1)\n        i--\n      } else {\n        var rright = {\n          range: clone(r.range)\n        }\n        rright.range[axis][0] = pivot\n        right.node.regions.push(rright)\n\n        var rleft = r\n        rleft.range[axis][1] = pivot\n\n        if (r.node.type === POINTS) {\n          rright.node = splitPointNode(r.node, pivot, axis)\n        } else if (r.node.type === REGION) {\n          rright.node = {\n            type: REGION,\n            regions: [ splitRegionNode(r, pivot, axis) ]\n          }\n        } else throw new Error('unknown type: ' + r.node.type)\n      }\n    }\n    return right\n  }\n}\n\nfunction overlappingPoint (a, p) {\n  for (var i = 0; i < a.length; i++) {\n    if (!overlappingmm(a[i][0], a[i][1], p[i], p[i])) return false\n  }\n  return true\n}\n\nfunction overlappingmm (amin, amax, bmin, bmax) {\n  return (amin >= bmin && amin <= bmax)\n    || (amax >= bmin && amax <= bmax)\n    || (amin < bmin && amax > bmax)\n}\n\nfunction overlappingRange (a, b) {\n  for (var i = 0; i < a.length; i++) {\n    if (!overlapping(a[i], b[i])) return false\n  }\n  return true\n}\n\nfunction overlapping (a, b) {\n  return (a[0] >= b[0] && a[0] <= b[1])\n    || (a[1] >= b[0] && a[1] <= b[1])\n    || (a[0] < b[0] && a[1] > b[1])\n}\n\nfunction clone (xs) {\n  return xs.map(function (x) { return x.slice() })\n}\n\nfunction regionRange (dim, regions) {\n  var range = []\n  for (var j = 0; j < dim; j++) {\n    var r0 = regions.length === 0\n      ? [-Infinity,Infinity]\n      : regions[0].range[j]\n    range[j] = [r0[0],r0[1]]\n    for (var i = 1; i < regions.length; i++) {\n      var r = regions[i].range\n      if (r[j][0] < range[j][0]) range[j][0] = r[j][0]\n      if (r[j][1] > range[j][1]) range[j][1] = r[j][1]\n    }\n  }\n  return range\n}\n"]}