{"version":3,"file":"polygon-clipping.umd.min.js","sources":["../src/bbox.js","../src/flp.js","../src/rounder.js","../src/vector.js","../src/sweep-event.js","../src/segment.js","../src/geom-in.js","../src/geom-out.js","../src/sweep-line.js","../src/operation.js","../src/index.js"],"sourcesContent":["/**\n * A bounding box has the format:\n *\n *  { ll: { x: xmin, y: ymin }, ur: { x: xmax, y: ymax } }\n *\n */\n\nexport const isInBbox = (bbox, point) => {\n  return (\n    (bbox.ll.x <= point.x) &&\n    (point.x <= bbox.ur.x) &&\n    (bbox.ll.y <= point.y) &&\n    (point.y <= bbox.ur.y)\n  )\n}\n\n/* Returns either null, or a bbox (aka an ordered pair of points)\n * If there is only one point of overlap, a bbox with identical points\n * will be returned */\nexport const getBboxOverlap = (b1, b2) => {\n  // check if the bboxes overlap at all\n  if (\n    b2.ur.x < b1.ll.x ||\n    b1.ur.x < b2.ll.x ||\n    b2.ur.y < b1.ll.y ||\n    b1.ur.y < b2.ll.y\n  ) return null\n\n  // find the middle two X values\n  const lowerX = b1.ll.x < b2.ll.x ? b2.ll.x : b1.ll.x\n  const upperX = b1.ur.x < b2.ur.x ? b1.ur.x : b2.ur.x\n\n  // find the middle two Y values\n  const lowerY = b1.ll.y < b2.ll.y ? b2.ll.y : b1.ll.y\n  const upperY = b1.ur.y < b2.ur.y ? b1.ur.y : b2.ur.y\n\n  // put those middle values together to get the overlap\n  return { ll: { x: lowerX, y: lowerY }, ur: { x: upperX, y: upperY } }\n}\n","/* Javascript doesn't do integer math. Everything is\n * floating point with percision Number.EPSILON.\n *\n * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/EPSILON\n */\n\nlet epsilon = Number.EPSILON\n\n// IE Polyfill\nif (epsilon === undefined) epsilon = Math.pow(2, -52)\n\nconst EPSILON_SQ = epsilon * epsilon\n\n/* FLP comparator */\nexport const cmp = (a, b) => {\n  // check if they're both 0\n  if (-epsilon < a && a < epsilon) {\n    if (-epsilon < b && b < epsilon) {\n      return 0\n    }\n  }\n\n  // check if they're flp equal\n  const ab = a - b\n  if (ab * ab < EPSILON_SQ * a * b) {\n    return 0\n  }\n\n  // normal comparison\n  return a < b ? -1 : 1\n}\n","import { cmp } from './flp'\nimport SplayTree from 'splaytree'\n\n/**\n * This class rounds incoming values sufficiently so that\n * floating points problems are, for the most part, avoided.\n *\n * Incoming points are have their x & y values tested against\n * all previously seen x & y values. If either is 'too close'\n * to a previously seen value, it's value is 'snapped' to the\n * previously seen value.\n *\n * All points should be rounded by this class before being\n * stored in any data structures in the rest of this algorithm.\n */\n\nclass PtRounder {\n  constructor () {\n    this.reset()\n  }\n\n  reset () {\n    this.xRounder = new CoordRounder()\n    this.yRounder = new CoordRounder()\n  }\n\n  round (x, y) {\n    return {\n      x: this.xRounder.round(x),\n      y: this.yRounder.round(y),\n    }\n  }\n}\n\nclass CoordRounder {\n  constructor () {\n    this.tree = new SplayTree()\n    // preseed with 0 so we don't end up with values < Number.EPSILON\n    this.round(0)\n  }\n\n  // Note: this can rounds input values backwards or forwards.\n  //       You might ask, why not restrict this to just rounding\n  //       forwards? Wouldn't that allow left endpoints to always\n  //       remain left endpoints during splitting (never change to\n  //       right). No - it wouldn't, because we snap intersections\n  //       to endpoints (to establish independence from the segment\n  //       angle for t-intersections).\n  round (coord) {\n    const node = this.tree.add(coord)\n\n    const prevNode = this.tree.prev(node)\n    if (prevNode !== null && cmp(node.key, prevNode.key) === 0) {\n      this.tree.remove(coord)\n      return prevNode.key\n    }\n\n    const nextNode = this.tree.next(node)\n    if (nextNode !== null && cmp(node.key, nextNode.key) === 0) {\n      this.tree.remove(coord)\n      return nextNode.key\n    }\n\n    return coord\n  }\n}\n\n// singleton available by import\nconst rounder = new PtRounder()\n\nexport default rounder\n","import { cmp } from './flp'\n\n/* Cross Product of two vectors with first point at origin */\nexport const crossProduct = (a, b) => a.x * b.y - a.y * b.x\n\n/* Dot Product of two vectors with first point at origin */\nexport const dotProduct = (a, b) => a.x * b.x + a.y * b.y\n\n/* Comparator for two vectors with same starting point */\nexport const compareVectorAngles = (basePt, endPt1, endPt2) => {\n  const v1 = { x: endPt1.x - basePt.x, y: endPt1.y - basePt.y }\n  const v2 = { x: endPt2.x - basePt.x, y: endPt2.y - basePt.y }\n  const kross = crossProduct(v1, v2)\n  return cmp(kross, 0)\n}\n\nexport const length = v => Math.sqrt(dotProduct(v, v))\n\n/* Get the sine of the angle from pShared -> pAngle to pShaed -> pBase */\nexport const sineOfAngle = (pShared, pBase, pAngle) => {\n  const vBase = { x: pBase.x - pShared.x, y: pBase.y - pShared.y }\n  const vAngle = { x: pAngle.x - pShared.x, y: pAngle.y - pShared.y }\n  return crossProduct(vAngle, vBase) / length(vAngle) / length(vBase)\n}\n\n/* Get the cosine of the angle from pShared -> pAngle to pShaed -> pBase */\nexport const cosineOfAngle = (pShared, pBase, pAngle) => {\n  const vBase = { x: pBase.x - pShared.x, y: pBase.y - pShared.y }\n  const vAngle = { x: pAngle.x - pShared.x, y: pAngle.y - pShared.y }\n  return dotProduct(vAngle, vBase) / length(vAngle) / length(vBase)\n}\n\n/* Get the closest point on an line (defined by two points)\n * to another point. */\nexport const closestPoint = (ptA1, ptA2, ptB) => {\n  if (ptA1.x === ptA2.x) return { x: ptA1.x, y: ptB.y } // vertical vector\n  if (ptA1.y === ptA2.y) return { x: ptB.x, y: ptA1.y } // horizontal vector\n\n  // determinne which point is further away\n  // we use the further point as our base in the calculation, so that the\n  // vectors are more parallel, providing more accurate dot product\n  const v1 = { x: ptB.x - ptA1.x, y: ptB.y - ptA1.y }\n  const v2 = { x: ptB.x - ptA2.x, y: ptB.y - ptA2.y }\n  let vFar, vA, farPt\n  if (dotProduct(v1, v1) > dotProduct(v2, v2)) {\n    vFar = v1\n    vA = { x: ptA2.x - ptA1.x, y: ptA2.y - ptA1.y }\n    farPt = ptA1\n  }\n  else {\n    vFar = v2\n    vA = { x: ptA1.x - ptA2.x, y: ptA1.y - ptA2.y }\n    farPt = ptA2\n  }\n\n  // manually test if the current point can be considered to be on the line\n  // If the X coordinate was on the line, would the Y coordinate be as well?\n  const xDist = (ptB.x - farPt.x) / vA.x\n  if (ptB.y === farPt.y + xDist * vA.y) return ptB\n\n  // If the Y coordinate was on the line, would the X coordinate be as well?\n  const yDist = (ptB.y - farPt.y) / vA.y\n  if (ptB.x === farPt.x + yDist * vA.x) return ptB\n\n  // current point isn't exactly on line, so return closest point\n  const dist = dotProduct(vA, vFar) / dotProduct(vA, vA)\n  return { x: farPt.x + dist * vA.x, y: farPt.y + dist * vA.y }\n}\n\n/* Get the x coordinate where the given line (defined by a point and vector)\n * crosses the horizontal line with the given y coordiante.\n * In the case of parrallel lines (including overlapping ones) returns null. */\nexport const horizontalIntersection = (pt, v, y) => {\n  if (v.y === 0) return null\n  return { x: pt.x + v.x / v.y * ( y - pt.y ), y: y }\n}\n\n/* Get the y coordinate where the given line (defined by a point and vector)\n * crosses the vertical line with the given x coordiante.\n * In the case of parrallel lines (including overlapping ones) returns null. */\nexport const verticalIntersection = (pt, v, x) => {\n  if (v.x === 0) return null\n  return { x: x, y: pt.y + v.y / v.x * ( x - pt.x ) }\n}\n\n/* Get the intersection of two lines, each defined by a base point and a vector.\n * In the case of parrallel lines (including overlapping ones) returns null. */\nexport const intersection = (pt1, v1, pt2, v2) => {\n  // take some shortcuts for vertical and horizontal lines\n  // this also ensures we don't calculate an intersection and then discover\n  // it's actually outside the bounding box of the line\n  if (v1.x === 0) return verticalIntersection(pt2, v2, pt1.x)\n  if (v2.x === 0) return verticalIntersection(pt1, v1, pt2.x)\n  if (v1.y === 0) return horizontalIntersection(pt2, v2, pt1.y)\n  if (v2.y === 0) return horizontalIntersection(pt1, v1, pt2.y)\n\n  // General case for non-overlapping segments.\n  // This algorithm is based on Schneider and Eberly.\n  // http://www.cimec.org.ar/~ncalvo/Schneider_Eberly.pdf - pg 244\n\n  const kross = crossProduct(v1, v2)\n  if (kross == 0) return null\n\n  const ve = { x: pt2.x - pt1.x, y: pt2.y - pt1.y }\n  const d1 = crossProduct(ve, v1) / kross\n  const d2 = crossProduct(ve, v2) / kross\n\n  // take the average of the two calculations to minimize rounding error\n  const x1 = pt1.x + d2 * v1.x, x2 = pt2.x + d1 * v2.x\n  const y1 = pt1.y + d2 * v1.y, y2 = pt2.y + d1 * v2.y\n  const x = (x1 + x2) / 2\n  const y = (y1 + y2) / 2\n  return { x: x, y: y }\n}\n\n/* Given a vector, return one that is perpendicular */\nexport const perpendicular = (v) => {\n  return { x: -v.y, y: v.x }\n}\n","import Segment from './segment'\nimport { cosineOfAngle, sineOfAngle } from './vector'\n\nexport default class SweepEvent {\n\n  // for ordering sweep events in the sweep event queue\n  static compare (a, b) {\n\n    // favor event with a point that the sweep line hits first\n    const ptCmp = SweepEvent.comparePoints(a.point, b.point)\n    if (ptCmp !== 0) return ptCmp\n\n    // the points are the same, so link them if needed\n    if (a.point !== b.point) a.link(b)\n\n    // favor right events over left\n    if (a.isLeft !== b.isLeft) return a.isLeft ? 1 : -1\n\n    // we have two matching left or right endpoints\n    // ordering of this case is the same as for their segments\n    return Segment.compare(a.segment, b.segment)\n  }\n\n  // for ordering points in sweep line order\n  static comparePoints (aPt, bPt) {\n    if (aPt.x < bPt.x) return -1\n    if (aPt.x > bPt.x) return 1\n\n    if (aPt.y < bPt.y) return -1\n    if (aPt.y > bPt.y) return 1\n\n    return 0\n  }\n\n  // Warning: 'point' input will be modified and re-used (for performance)\n  constructor (point, isLeft) {\n    if (point.events === undefined) point.events = [this]\n    else point.events.push(this)\n    this.point = point\n    this.isLeft = isLeft\n    // this.segment, this.otherSE set by factory\n  }\n\n  link (other) {\n    if (other.point === this.point) {\n      throw new Error('Tried to link already linked events')\n    }\n    const otherEvents = other.point.events\n    for (let i = 0, iMax = otherEvents.length; i < iMax; i++) {\n      const evt = otherEvents[i]\n      this.point.events.push(evt)\n      evt.point = this.point\n    }\n    this.checkForConsuming()\n  }\n\n  /* Do a pass over our linked events and check to see if any pair\n   * of segments match, and should be consumed. */\n  checkForConsuming () {\n    // FIXME: The loops in this method run O(n^2) => no good.\n    //        Maintain little ordered sweep event trees?\n    //        Can we maintaining an ordering that avoids the need\n    //        for the re-sorting with getLeftmostComparator in geom-out?\n\n    // Compare each pair of events to see if other events also match\n    const numEvents = this.point.events.length\n    for (let i = 0; i < numEvents; i++) {\n      const evt1 = this.point.events[i]\n      if (evt1.segment.consumedBy !== undefined) continue\n      for (let j = i + 1; j < numEvents; j++) {\n        const evt2 = this.point.events[j]\n        if (evt2.consumedBy !== undefined) continue\n        if (evt1.otherSE.point.events !== evt2.otherSE.point.events) continue\n        evt1.segment.consume(evt2.segment)\n      }\n    }\n  }\n\n  getAvailableLinkedEvents () {\n    // point.events is always of length 2 or greater\n    const events = []\n    for (let i = 0, iMax = this.point.events.length; i < iMax; i++) {\n      const evt = this.point.events[i]\n      if (evt !== this && !evt.segment.ringOut && evt.segment.isInResult()) {\n        events.push(evt)\n      }\n    }\n    return events\n  }\n\n  /**\n   * Returns a comparator function for sorting linked events that will\n   * favor the event that will give us the smallest left-side angle.\n   * All ring construction starts as low as possible heading to the right,\n   * so by always turning left as sharp as possible we'll get polygons\n   * without uncessary loops & holes.\n   *\n   * The comparator function has a compute cache such that it avoids\n   * re-computing already-computed values.\n   */\n  getLeftmostComparator (baseEvent) {\n    const cache = new Map()\n\n    const fillCache = linkedEvent => {\n      const nextEvent = linkedEvent.otherSE\n      cache.set(linkedEvent, {\n        sine: sineOfAngle(this.point, baseEvent.point, nextEvent.point),\n        cosine: cosineOfAngle(this.point, baseEvent.point, nextEvent.point)\n      })\n    }\n\n    return (a, b) => {\n      if (!cache.has(a)) fillCache(a)\n      if (!cache.has(b)) fillCache(b)\n\n      const { sine: asine, cosine: acosine } = cache.get(a)\n      const { sine: bsine, cosine: bcosine } = cache.get(b)\n\n      // both on or above x-axis\n      if (asine >= 0 && bsine >= 0) {\n        if (acosine < bcosine) return 1\n        if (acosine > bcosine) return -1\n        return 0\n      }\n\n      // both below x-axis\n      if (asine < 0 && bsine < 0) {\n        if (acosine < bcosine) return -1\n        if (acosine > bcosine) return 1\n        return 0\n      }\n\n      // one above x-axis, one below\n      if (bsine < asine) return -1\n      if (bsine > asine) return 1\n      return 0\n    }\n  }\n}\n","import operation from './operation'\nimport SweepEvent from './sweep-event'\nimport { isInBbox, getBboxOverlap } from './bbox'\nimport { intersection } from './vector'\nimport rounder from './rounder'\n\n// Give segments unique ID's to get consistent sorting of\n// segments and sweep events when all else is identical\nlet segmentId = 0\n\nexport default class Segment {\n\n  /* This compare() function is for ordering segments in the sweep\n   * line tree, and does so according to the following criteria:\n   *\n   * Consider the vertical line that lies an infinestimal step to the\n   * right of the right-more of the two left endpoints of the input\n   * segments. Imagine slowly moving a point up from negative infinity\n   * in the increasing y direction. Which of the two segments will that\n   * point intersect first? That segment comes 'before' the other one.\n   *\n   * If neither segment would be intersected by such a line, (if one\n   * or more of the segments are vertical) then the line to be considered\n   * is directly on the right-more of the two left inputs.\n   */\n  static compare (a, b) {\n\n    const alx = a.leftSE.point.x\n    const blx = b.leftSE.point.x\n    const arx = a.rightSE.point.x\n    const brx = b.rightSE.point.x\n\n    // check if they're even in the same vertical plane\n    if (brx < alx) return 1\n    if (arx < blx) return -1\n\n    const aly = a.leftSE.point.y\n    const bly = b.leftSE.point.y\n    const ary = a.rightSE.point.y\n    const bry = b.rightSE.point.y\n\n    // is left endpoint of segment B the right-more?\n    if (alx < blx) {\n      // are the two segments in the same horizontal plane?\n      if (bly < aly && bly < ary) return 1\n      if (bly > aly && bly > ary) return -1\n\n      // is the B left endpoint colinear to segment A?\n      const aCmpBLeft = a.comparePoint(b.leftSE.point)\n      if (aCmpBLeft < 0) return 1\n      if (aCmpBLeft > 0) return -1\n\n      // is the A right endpoint colinear to segment B ?\n      const bCmpARight = b.comparePoint(a.rightSE.point)\n      if (bCmpARight !== 0) return bCmpARight\n\n      // colinear segments, consider the one with left-more\n      // left endpoint to be first (arbitrary?)\n      return -1\n    }\n\n    // is left endpoint of segment A the right-more?\n    if (alx > blx) {\n      if (aly < bly && aly < bry) return -1\n      if (aly > bly && aly > bry) return 1\n\n      // is the A left endpoint colinear to segment B?\n      const bCmpALeft = b.comparePoint(a.leftSE.point)\n      if (bCmpALeft !== 0) return bCmpALeft\n\n      // is the B right endpoint colinear to segment A?\n      const aCmpBRight = a.comparePoint(b.rightSE.point)\n      if (aCmpBRight < 0) return 1\n      if (aCmpBRight > 0) return -1\n\n      // colinear segments, consider the one with left-more\n      // left endpoint to be first (arbitrary?)\n      return 1\n    }\n\n    // if we get here, the two left endpoints are in the same\n    // vertical plane, ie alx === blx\n\n    // consider the lower left-endpoint to come first\n    if (aly < bly) return -1\n    if (aly > bly) return 1\n\n    // left endpoints are identical\n    // check for colinearity by using the left-more right endpoint\n\n    // is the A right endpoint more left-more?\n    if (arx < brx) {\n      const bCmpARight = b.comparePoint(a.rightSE.point)\n      if (bCmpARight !== 0) return bCmpARight\n    }\n\n    // is the B right endpoint more left-more?\n    if (arx > brx) {\n      const aCmpBRight = a.comparePoint(b.rightSE.point)\n      if (aCmpBRight < 0) return 1\n      if (aCmpBRight > 0) return -1\n    }\n\n    if (arx !== brx)  {\n      // are these two [almost] vertical segments with opposite orientation?\n      // if so, the one with the lower right endpoint comes first\n      const ay = ary - aly\n      const ax = arx - alx\n      const by = bry - bly\n      const bx = brx - blx\n      if (ay > ax && by < bx) return 1\n      if (ay < ax && by > bx) return -1\n    }\n\n    // we have colinear segments with matching orientation\n    // consider the one with more left-more right endpoint to be first\n    if (arx > brx) return 1\n    if (arx < brx) return -1\n\n    // if we get here, two two right endpoints are in the same\n    // vertical plane, ie arx === brx\n\n    // consider the lower right-endpoint to come first\n    if (ary < bry) return -1\n    if (ary > bry) return 1\n\n    // right endpoints identical as well, so the segments are idential\n    // fall back on creation order as consistent tie-breaker\n    if (a.id < b.id) return -1\n    if (a.id > b.id) return 1\n\n    // identical segment, ie a === b\n    return 0\n  }\n\n  /* Warning: a reference to ringWindings input will be stored,\n   *  and possibly will be later modified */\n  constructor (leftSE, rightSE, rings, windings) {\n    this.id = ++segmentId\n    this.leftSE = leftSE\n    leftSE.segment = this\n    leftSE.otherSE = rightSE\n    this.rightSE = rightSE\n    rightSE.segment = this\n    rightSE.otherSE = leftSE\n    this.rings = rings\n    this.windings = windings\n    // left unset for performance, set later in algorithm\n    // this.ringOut, this.consumedBy, this.prev\n  }\n\n  static fromRing(pt1, pt2, ring) {\n    let leftPt, rightPt, winding\n\n    // ordering the two points according to sweep line ordering\n    const cmpPts = SweepEvent.comparePoints(pt1, pt2)\n    if (cmpPts < 0) {\n      leftPt = pt1\n      rightPt = pt2\n      winding = 1\n    }\n    else if (cmpPts > 0) {\n      leftPt = pt2\n      rightPt = pt1\n      winding = -1\n    }\n    else throw new Error(\n      `Tried to create degenerate segment at [${pt1.x}, ${pt1.y}]`\n    )\n\n    const leftSE = new SweepEvent(leftPt, true)\n    const rightSE = new SweepEvent(rightPt, false)\n    return new Segment(leftSE, rightSE, [ring], [winding])\n  }\n\n  /* When a segment is split, the rightSE is replaced with a new sweep event */\n  replaceRightSE (newRightSE) {\n    this.rightSE = newRightSE\n    this.rightSE.segment = this\n    this.rightSE.otherSE = this.leftSE\n    this.leftSE.otherSE = this.rightSE\n  }\n\n  bbox () {\n    const y1 = this.leftSE.point.y\n    const y2 = this.rightSE.point.y\n    return {\n      ll: { x: this.leftSE.point.x, y: y1 < y2 ? y1 : y2 },\n      ur: { x: this.rightSE.point.x, y: y1 > y2 ? y1 : y2 }\n    }\n  }\n\n  /* A vector from the left point to the right */\n  vector () {\n    return {\n      x: this.rightSE.point.x - this.leftSE.point.x,\n      y: this.rightSE.point.y - this.leftSE.point.y\n    }\n  }\n\n  isAnEndpoint (pt) {\n    return (\n      (pt.x === this.leftSE.point.x && pt.y === this.leftSE.point.y) ||\n      (pt.x === this.rightSE.point.x && pt.y === this.rightSE.point.y)\n    )\n  }\n\n  /* Compare this segment with a point.\n   *\n   * A point P is considered to be colinear to a segment if there\n   * exists a distance D such that if we travel along the segment\n   * from one * endpoint towards the other a distance D, we find\n   * ourselves at point P.\n   *\n   * Return value indicates:\n   *\n   *   1: point lies above the segment (to the left of vertical)\n   *   0: point is colinear to segment\n   *  -1: point lies below the segment (to the right of vertical)\n   */\n  comparePoint (point) {\n    if (this.isAnEndpoint(point)) return 0\n\n    const lPt = this.leftSE.point\n    const rPt = this.rightSE.point\n    const v = this.vector()\n\n    // Exactly vertical segments.\n    if (lPt.x === rPt.x) {\n      if (point.x === lPt.x) return 0\n      return point.x < lPt.x ? 1 : -1\n    }\n\n    // Nearly vertical segments with an intersection.\n    // Check to see where a point on the line with matching Y coordinate is.\n    const yDist = (point.y - lPt.y) / v.y\n    const xFromYDist = lPt.x + yDist * v.x\n    if (point.x === xFromYDist) return 0\n\n    // General case.\n    // Check to see where a point on the line with matching X coordinate is.\n    const xDist =  (point.x - lPt.x) / v.x\n    const yFromXDist = lPt.y + xDist * v.y\n    if (point.y === yFromXDist) return 0\n    return point.y < yFromXDist ? -1 : 1\n  }\n\n  /**\n   * Given another segment, returns the first non-trivial intersection\n   * between the two segments (in terms of sweep line ordering), if it exists.\n   *\n   * A 'non-trivial' intersection is one that will cause one or both of the\n   * segments to be split(). As such, 'trivial' vs. 'non-trivial' intersection:\n   *\n   *   * endpoint of segA with endpoint of segB --> trivial\n   *   * endpoint of segA with point along segB --> non-trivial\n   *   * endpoint of segB with point along segA --> non-trivial\n   *   * point along segA with point along segB --> non-trivial\n   *\n   * If no non-trivial intersection exists, return null\n   * Else, return null.\n   */\n  getIntersection (other) {\n    // If bboxes don't overlap, there can't be any intersections\n    const tBbox = this.bbox()\n    const oBbox = other.bbox()\n    const bboxOverlap = getBboxOverlap(tBbox, oBbox)\n    if (bboxOverlap === null) return null\n\n    // We first check to see if the endpoints can be considered intersections.\n    // This will 'snap' intersections to endpoints if possible, and will\n    // handle cases of colinearity.\n\n    const tlp = this.leftSE.point\n    const trp = this.rightSE.point\n    const olp = other.leftSE.point\n    const orp = other.rightSE.point\n\n    // does each endpoint touch the other segment?\n    // note that we restrict the 'touching' definition to only allow segments\n    // to touch endpoints that lie forward from where we are in the sweep line pass\n    const touchesOtherLSE = isInBbox(tBbox, olp) && this.comparePoint(olp) === 0\n    const touchesThisLSE = isInBbox(oBbox, tlp) && other.comparePoint(tlp) === 0\n    const touchesOtherRSE = isInBbox(tBbox, orp) && this.comparePoint(orp) === 0\n    const touchesThisRSE = isInBbox(oBbox, trp) && other.comparePoint(trp) === 0\n\n    // do left endpoints match?\n    if (touchesThisLSE && touchesOtherLSE) {\n      // these two cases are for colinear segments with matching left\n      // endpoints, and one segment being longer than the other\n      if (touchesThisRSE && !touchesOtherRSE) return trp\n      if (!touchesThisRSE && touchesOtherRSE) return orp\n      // either the two segments match exactly (two trival intersections)\n      // or just on their left endpoint (one trivial intersection\n      return null\n    }\n\n    // does this left endpoint matches (other doesn't)\n    if (touchesThisLSE) {\n      // check for segments that just intersect on opposing endpoints\n      if (touchesOtherRSE) {\n        if (tlp.x === orp.x && tlp.y === orp.y) return null\n      }\n      // t-intersection on left endpoint\n      return tlp\n    }\n\n    // does other left endpoint matches (this doesn't)\n    if (touchesOtherLSE) {\n      // check for segments that just intersect on opposing endpoints\n      if (touchesThisRSE) {\n        if (trp.x === olp.x && trp.y === olp.y) return null\n      }\n      // t-intersection on left endpoint\n      return olp\n    }\n\n    // trivial intersection on right endpoints\n    if (touchesThisRSE && touchesOtherRSE) return null\n\n    // t-intersections on just one right endpoint\n    if (touchesThisRSE) return trp\n    if (touchesOtherRSE) return orp\n\n    // None of our endpoints intersect. Look for a general intersection between\n    // infinite lines laid over the segments\n    const pt = intersection(tlp, this.vector(), olp, other.vector())\n\n    // are the segments parrallel? Note that if they were colinear with overlap,\n    // they would have an endpoint intersection and that case was already handled above\n    if (pt === null) return null\n\n    // is the intersection found between the lines not on the segments?\n    if (!isInBbox(bboxOverlap, pt)) return null\n\n    // round the the computed point if needed\n    return rounder.round(pt.x, pt.y)\n  }\n\n  /**\n   * Split the given segment into multiple segments on the given points.\n   *  * Each existing segment will retain its leftSE and a new rightSE will be\n   *    generated for it.\n   *  * A new segment will be generated which will adopt the original segment's\n   *    rightSE, and a new leftSE will be generated for it.\n   *  * If there are more than two points given to split on, new segments\n   *    in the middle will be generated with new leftSE and rightSE's.\n   *  * An array of the newly generated SweepEvents will be returned.\n   *\n   * Warning: input array of points is modified\n   */\n  split (point) {\n    const newEvents = []\n    const alreadyLinked = point.events !== undefined\n\n    const newLeftSE = new SweepEvent(point, true)\n    const newRightSE = new SweepEvent(point, false)\n    const oldRightSE = this.rightSE\n    this.replaceRightSE(newRightSE)\n    newEvents.push(newRightSE)\n    newEvents.push(newLeftSE)\n    const newSeg = new Segment(\n      newLeftSE, oldRightSE, this.rings.slice(), this.windings.slice()\n    )\n\n    // when splitting a nearly vertical downward-facing segment,\n    // sometimes one of the resulting new segments is vertical, in which\n    // case its left and right events may need to be swapped\n    if (SweepEvent.comparePoints(newSeg.leftSE.point, newSeg.rightSE.point) > 0) {\n      newSeg.swapEvents()\n    }\n    if (SweepEvent.comparePoints(this.leftSE.point, this.rightSE.point) > 0) {\n      this.swapEvents()\n    }\n\n    // in the point we just used to create new sweep events with was already\n    // linked to other events, we need to check if either of the affected\n    // segments should be consumed\n    if (alreadyLinked) {\n      newLeftSE.checkForConsuming()\n      newRightSE.checkForConsuming()\n    }\n\n    return newEvents\n  }\n\n  /* Swap which event is left and right */\n  swapEvents () {\n    const tmpEvt = this.rightSE\n    this.rightSE = this.leftSE\n    this.leftSE = tmpEvt\n    this.leftSE.isLeft = true\n    this.rightSE.isLeft = false\n    for (let i = 0, iMax = this.windings.length; i < iMax; i++) {\n      this.windings[i] *= -1\n    }\n  }\n\n  /* Consume another segment. We take their rings under our wing\n   * and mark them as consumed. Use for perfectly overlapping segments */\n  consume (other) {\n    let consumer = this\n    let consumee = other\n    while (consumer.consumedBy) consumer = consumer.consumedBy\n    while (consumee.consumedBy) consumee = consumee.consumedBy\n\n    const cmp = Segment.compare(consumer, consumee)\n    if (cmp === 0) return  // already consumed\n    // the winner of the consumption is the earlier segment\n    // according to sweep line ordering\n    if (cmp  > 0) {\n      const tmp = consumer\n      consumer = consumee\n      consumee = tmp\n    }\n\n    // make sure a segment doesn't consume it's prev\n    if (consumer.prev === consumee) {\n      const tmp = consumer\n      consumer = consumee\n      consumee = tmp\n    }\n\n    for (let i = 0, iMax = consumee.rings.length; i < iMax; i++) {\n      const ring = consumee.rings[i]\n      const winding = consumee.windings[i]\n      const index = consumer.rings.indexOf(ring)\n      if (index === -1) {\n        consumer.rings.push(ring)\n        consumer.windings.push(winding)\n      }\n      else consumer.windings[index] += winding\n    }\n    consumee.rings = null\n    consumee.windings = null\n    consumee.consumedBy = consumer\n\n    // mark sweep events consumed as to maintain ordering in sweep event queue\n    consumee.leftSE.consumedBy = consumer.leftSE\n    consumee.rightSE.consumedBy = consumer.rightSE\n  }\n\n  /* The first segment previous segment chain that is in the result */\n  prevInResult () {\n    if (this._prevInResult !== undefined) return this._prevInResult\n    if (! this.prev) this._prevInResult = null\n    else if (this.prev.isInResult()) this._prevInResult = this.prev\n    else this._prevInResult = this.prev.prevInResult()\n    return this._prevInResult\n  }\n\n  beforeState() {\n    if (this._beforeState !== undefined) return this._beforeState\n    if (! this.prev) this._beforeState = {\n      rings: [],\n      windings: [],\n      multiPolys: [],\n    }\n    else {\n      const seg = this.prev.consumedBy || this.prev\n      this._beforeState = seg.afterState()\n    }\n    return this._beforeState\n  }\n\n  afterState () {\n    if (this._afterState !== undefined) return this._afterState\n\n    const beforeState = this.beforeState()\n    this._afterState = {\n      rings: beforeState.rings.slice(0),\n      windings: beforeState.windings.slice(0),\n      multiPolys: []\n    }\n    const ringsAfter = this._afterState.rings\n    const windingsAfter = this._afterState.windings\n    const mpsAfter = this._afterState.multiPolys\n\n    // calculate ringsAfter, windingsAfter\n    for (let i = 0, iMax = this.rings.length; i < iMax; i++) {\n      const ring = this.rings[i]\n      const winding = this.windings[i]\n      const index = ringsAfter.indexOf(ring)\n      if (index === -1) {\n        ringsAfter.push(ring)\n        windingsAfter.push(winding)\n      }\n      else windingsAfter[index] += winding\n    }\n\n    // calcualte polysAfter\n    const polysAfter = []\n    const polysExclude = []\n    for (let i = 0, iMax = ringsAfter.length; i < iMax; i++) {\n      if (windingsAfter[i] === 0) continue // non-zero rule\n      const ring = ringsAfter[i]\n      const poly = ring.poly\n      if (polysExclude.indexOf(poly) !== -1) continue\n      if (ring.isExterior) polysAfter.push(poly)\n      else {\n        if (polysExclude.indexOf(poly) === -1) polysExclude.push(poly)\n        const index = polysAfter.indexOf(ring.poly)\n        if (index !== -1) polysAfter.splice(index, 1)\n      }\n    }\n\n    // calculate multiPolysAfter\n    for (let i = 0, iMax = polysAfter.length; i < iMax; i++) {\n      const mp = polysAfter[i].multiPoly\n      if (mpsAfter.indexOf(mp) === -1) mpsAfter.push(mp)\n    }\n\n    return this._afterState\n  }\n\n  /* Is this segment part of the final result? */\n  isInResult () {\n    // if we've been consumed, we're not in the result\n    if (this.consumedBy) return false\n\n    if (this._isInResult !== undefined) return this._isInResult\n\n    const mpsBefore = this.beforeState().multiPolys\n    const mpsAfter = this.afterState().multiPolys\n\n    switch (operation.type) {\n      case 'union': {\n        // UNION - included iff:\n        //  * On one side of us there is 0 poly interiors AND\n        //  * On the other side there is 1 or more.\n        const noBefores = mpsBefore.length === 0\n        const noAfters = mpsAfter.length === 0\n        this._isInResult = noBefores !== noAfters\n        break\n      }\n\n      case 'intersection': {\n        // INTERSECTION - included iff:\n        //  * on one side of us all multipolys are rep. with poly interiors AND\n        //  * on the other side of us, not all multipolys are repsented\n        //    with poly interiors\n        let least\n        let most\n        if (mpsBefore.length < mpsAfter.length) {\n          least = mpsBefore.length\n          most = mpsAfter.length\n        } else {\n          least = mpsAfter.length\n          most = mpsBefore.length\n        }\n        this._isInResult = most === operation.numMultiPolys && least < most\n        break\n      }\n\n      case 'xor': {\n        // XOR - included iff:\n        //  * the difference between the number of multipolys represented\n        //    with poly interiors on our two sides is an odd number\n        const diff = Math.abs(mpsBefore.length - mpsAfter.length)\n        this._isInResult = diff % 2 === 1\n        break\n      }\n\n      case 'difference': {\n        // DIFFERENCE included iff:\n        //  * on exactly one side, we have just the subject\n        const isJustSubject = mps => mps.length === 1 && mps[0].isSubject\n        this._isInResult = isJustSubject(mpsBefore) !== isJustSubject(mpsAfter)\n        break\n      }\n\n      default:\n        throw new Error(`Unrecognized operation type found ${operation.type}`)\n    }\n\n    return this._isInResult\n  }\n\n}\n","import rounder from './rounder'\nimport Segment from './segment'\n\nexport class RingIn {\n  constructor (geomRing, poly, isExterior) {\n    if (!Array.isArray(geomRing) || geomRing.length === 0) {\n      throw new Error('Input geometry is not a valid Polygon or MultiPolygon')\n    }\n\n    this.poly = poly\n    this.isExterior = isExterior\n    this.segments = []\n\n    if (typeof geomRing[0][0] !== 'number' || typeof geomRing[0][1] !== 'number') {\n      throw new Error('Input geometry is not a valid Polygon or MultiPolygon')\n    }\n\n    const firstPoint = rounder.round(geomRing[0][0], geomRing[0][1])\n    this.bbox = {\n      ll: { x: firstPoint.x, y: firstPoint.y },\n      ur: { x: firstPoint.x, y: firstPoint.y },\n    }\n\n    let prevPoint = firstPoint\n    for (let i = 1, iMax = geomRing.length; i < iMax; i++) {\n      if (typeof geomRing[i][0] !== 'number' || typeof geomRing[i][1] !== 'number') {\n        throw new Error('Input geometry is not a valid Polygon or MultiPolygon')\n      }\n      let point = rounder.round(geomRing[i][0], geomRing[i][1])\n      // skip repeated points\n      if (point.x === prevPoint.x && point.y === prevPoint.y) continue\n      this.segments.push(Segment.fromRing(prevPoint, point, this))\n      if (point.x < this.bbox.ll.x) this.bbox.ll.x = point.x\n      if (point.y < this.bbox.ll.y) this.bbox.ll.y = point.y\n      if (point.x > this.bbox.ur.x) this.bbox.ur.x = point.x\n      if (point.y > this.bbox.ur.y) this.bbox.ur.y = point.y\n      prevPoint = point\n    }\n    // add segment from last to first if last is not the same as first\n    if (firstPoint.x !== prevPoint.x || firstPoint.y !== prevPoint.y) {\n      this.segments.push(Segment.fromRing(prevPoint, firstPoint, this))\n    }\n  }\n\n  getSweepEvents () {\n    const sweepEvents = []\n    for (let i = 0, iMax = this.segments.length; i < iMax; i++) {\n      const segment = this.segments[i]\n      sweepEvents.push(segment.leftSE)\n      sweepEvents.push(segment.rightSE)\n    }\n    return sweepEvents\n  }\n}\n\nexport class PolyIn {\n  constructor (geomPoly, multiPoly) {\n    if (!Array.isArray(geomPoly)) {\n      throw new Error('Input geometry is not a valid Polygon or MultiPolygon')\n    }\n    this.exteriorRing = new RingIn(geomPoly[0], this, true)\n    // copy by value\n    this.bbox = {\n      ll: { x: this.exteriorRing.bbox.ll.x, y: this.exteriorRing.bbox.ll.y },\n      ur: { x: this.exteriorRing.bbox.ur.x, y: this.exteriorRing.bbox.ur.y },\n    }\n    this.interiorRings = []\n    for (let i = 1, iMax = geomPoly.length; i < iMax; i++) {\n      const ring = new RingIn(geomPoly[i], this, false)\n      if (ring.bbox.ll.x < this.bbox.ll.x) this.bbox.ll.x = ring.bbox.ll.x\n      if (ring.bbox.ll.y < this.bbox.ll.y) this.bbox.ll.y = ring.bbox.ll.y\n      if (ring.bbox.ur.x > this.bbox.ur.x) this.bbox.ur.x = ring.bbox.ur.x\n      if (ring.bbox.ur.y > this.bbox.ur.y) this.bbox.ur.y = ring.bbox.ur.y\n      this.interiorRings.push(ring)\n    }\n    this.multiPoly = multiPoly\n  }\n\n  getSweepEvents () {\n    const sweepEvents = this.exteriorRing.getSweepEvents()\n    for (let i = 0, iMax = this.interiorRings.length; i < iMax; i++) {\n      const ringSweepEvents = this.interiorRings[i].getSweepEvents()\n      for (let j = 0, jMax = ringSweepEvents.length; j < jMax; j++) {\n        sweepEvents.push(ringSweepEvents[j])\n      }\n    }\n    return sweepEvents\n  }\n}\n\nexport class MultiPolyIn {\n  constructor (geom, isSubject) {\n    if (!Array.isArray(geom)) {\n      throw new Error('Input geometry is not a valid Polygon or MultiPolygon')\n    }\n\n    try {\n      // if the input looks like a polygon, convert it to a multipolygon\n      if (typeof geom[0][0][0] === 'number') geom = [geom]\n    } catch (ex) {\n      // The input is either malformed or has empty arrays.\n      // In either case, it will be handled later on.\n    }\n\n    this.polys = []\n    this.bbox = {\n      ll: { x: Number.POSITIVE_INFINITY, y: Number.POSITIVE_INFINITY },\n      ur: { x: Number.NEGATIVE_INFINITY, y: Number.NEGATIVE_INFINITY },\n    }\n    for (let i = 0, iMax = geom.length; i < iMax; i++) {\n      const poly = new PolyIn(geom[i], this)\n      if (poly.bbox.ll.x < this.bbox.ll.x) this.bbox.ll.x = poly.bbox.ll.x\n      if (poly.bbox.ll.y < this.bbox.ll.y) this.bbox.ll.y = poly.bbox.ll.y\n      if (poly.bbox.ur.x > this.bbox.ur.x) this.bbox.ur.x = poly.bbox.ur.x\n      if (poly.bbox.ur.y > this.bbox.ur.y) this.bbox.ur.y = poly.bbox.ur.y\n      this.polys.push(poly)\n    }\n    this.isSubject = isSubject\n  }\n\n  getSweepEvents () {\n    const sweepEvents = []\n    for (let i = 0, iMax = this.polys.length; i < iMax; i++) {\n      const polySweepEvents = this.polys[i].getSweepEvents()\n      for (let j = 0, jMax = polySweepEvents.length; j < jMax; j++) {\n        sweepEvents.push(polySweepEvents[j])\n      }\n    }\n    return sweepEvents\n  }\n}\n","import { compareVectorAngles } from './vector'\nimport SweepEvent from './sweep-event'\n\nexport class RingOut {\n  /* Given the segments from the sweep line pass, compute & return a series\n   * of closed rings from all the segments marked to be part of the result */\n  static factory (allSegments) {\n    const ringsOut = []\n\n    for (let i = 0, iMax = allSegments.length; i < iMax; i++) {\n      const segment = allSegments[i]\n      if (!segment.isInResult() || segment.ringOut) continue\n\n      let prevEvent = null\n      let event = segment.leftSE\n      let nextEvent = segment.rightSE\n      const events = [event]\n\n      const startingPoint = event.point\n      const intersectionLEs = []\n\n      /* Walk the chain of linked events to form a closed ring */\n      while (true) {\n        prevEvent = event\n        event = nextEvent\n        events.push(event)\n\n        /* Is the ring complete? */\n        if (event.point === startingPoint) break\n\n        while (true) {\n          const availableLEs = event.getAvailableLinkedEvents()\n\n          /* Did we hit a dead end? This shouldn't happen. Indicates some earlier\n           * part of the algorithm malfunctioned... please file a bug report. */\n          if (availableLEs.length === 0) {\n            const firstPt = events[0].point\n            const lastPt = events[events.length - 1].point\n            throw new Error(\n              `Unable to complete output ring starting at [${firstPt.x},` +\n                ` ${firstPt.y}]. Last matching segment found ends at` +\n                ` [${lastPt.x}, ${lastPt.y}].`\n            )\n          }\n\n          /* Only one way to go, so cotinue on the path */\n          if (availableLEs.length === 1) {\n            nextEvent = availableLEs[0].otherSE\n            break\n          }\n\n          /* We must have an intersection. Check for a completed loop */\n          let indexLE = null\n          for (let j = 0, jMax = intersectionLEs.length; j < jMax; j++) {\n            if (intersectionLEs[j].point === event.point) {\n              indexLE = j\n              break\n            }\n          }\n          /* Found a completed loop. Cut that off and make a ring */\n          if (indexLE !== null) {\n            const intersectionLE = intersectionLEs.splice(indexLE)[0]\n            const ringEvents = events.splice(intersectionLE.index)\n            ringEvents.unshift(ringEvents[0].otherSE)\n            ringsOut.push(new RingOut(ringEvents.reverse()))\n            continue\n          }\n          /* register the intersection */\n          intersectionLEs.push({\n            index: events.length,\n            point: event.point,\n          })\n          /* Choose the left-most option to continue the walk */\n          const comparator = event.getLeftmostComparator(prevEvent)\n          nextEvent = availableLEs.sort(comparator)[0].otherSE\n          break\n        }\n      }\n\n      ringsOut.push(new RingOut(events))\n    }\n    return ringsOut\n  }\n\n  constructor (events) {\n    this.events = events\n    for (let i = 0, iMax = events.length; i < iMax; i++) {\n      events[i].segment.ringOut = this\n    }\n    this.poly = null\n  }\n\n  getGeom () {\n    // Remove superfluous points (ie extra points along a straight line),\n    let prevPt = this.events[0].point\n    const points = [prevPt]\n    for (let i = 1, iMax = this.events.length - 1; i < iMax; i++) {\n      const pt = this.events[i].point\n      const nextPt = this.events[i + 1].point\n      if (compareVectorAngles(pt, prevPt, nextPt) === 0) continue\n      points.push(pt)\n      prevPt = pt\n    }\n\n    // ring was all (within rounding error of angle calc) colinear points\n    if (points.length === 1) return null\n\n    // check if the starting point is necessary\n    const pt = points[0]\n    const nextPt = points[1]\n    if (compareVectorAngles(pt, prevPt, nextPt) === 0) points.shift()\n\n    points.push(points[0])\n    const step = this.isExteriorRing() ? 1 : -1\n    const iStart = this.isExteriorRing() ? 0 : points.length - 1\n    const iEnd = this.isExteriorRing() ? points.length : -1\n    const orderedPoints = []\n    for (let i = iStart; i != iEnd; i += step) orderedPoints.push([points[i].x, points[i].y])\n    return orderedPoints\n  }\n\n  isExteriorRing () {\n    if (this._isExteriorRing === undefined) {\n      const enclosing = this.enclosingRing()\n      this._isExteriorRing = enclosing ? ! enclosing.isExteriorRing() : true\n    }\n    return this._isExteriorRing\n  }\n\n  enclosingRing () {\n    if (this._enclosingRing === undefined) {\n      this._enclosingRing = this._calcEnclosingRing()\n    }\n    return this._enclosingRing\n  }\n\n  /* Returns the ring that encloses this one, if any */\n  _calcEnclosingRing () {\n    // start with the ealier sweep line event so that the prevSeg\n    // chain doesn't lead us inside of a loop of ours\n    let leftMostEvt = this.events[0]\n    for (let i = 1, iMax = this.events.length; i < iMax; i++) {\n      const evt = this.events[i]\n      if (SweepEvent.compare(leftMostEvt, evt) > 0) leftMostEvt = evt\n    }\n\n    let prevSeg = leftMostEvt.segment.prevInResult()\n    let prevPrevSeg = prevSeg ? prevSeg.prevInResult() : null\n\n    while (true) {\n      // no segment found, thus no ring can enclose us\n      if (!prevSeg) return null\n\n      // no segments below prev segment found, thus the ring of the prev\n      // segment must loop back around and enclose us\n      if (!prevPrevSeg) return prevSeg.ringOut\n\n      // if the two segments are of different rings, the ring of the prev\n      // segment must either loop around us or the ring of the prev prev\n      // seg, which would make us and the ring of the prev peers\n      if (prevPrevSeg.ringOut !== prevSeg.ringOut) {\n        if (prevPrevSeg.ringOut.enclosingRing() !== prevSeg.ringOut) {\n          return prevSeg.ringOut\n        } else return prevSeg.ringOut.enclosingRing()\n      }\n\n      // two segments are from the same ring, so this was a penisula\n      // of that ring. iterate downward, keep searching\n      prevSeg = prevPrevSeg.prevInResult()\n      prevPrevSeg = prevSeg ? prevSeg.prevInResult() : null\n    }\n  }\n}\n\nexport class PolyOut {\n  constructor (exteriorRing) {\n    this.exteriorRing = exteriorRing\n    exteriorRing.poly = this\n    this.interiorRings = []\n  }\n\n  addInterior (ring) {\n    this.interiorRings.push(ring)\n    ring.poly = this\n  }\n\n  getGeom () {\n    const geom = [this.exteriorRing.getGeom()]\n    // exterior ring was all (within rounding error of angle calc) colinear points\n    if (geom[0] === null) return null\n    for (let i = 0, iMax = this.interiorRings.length; i < iMax; i++) {\n      const ringGeom = this.interiorRings[i].getGeom()\n      // interior ring was all (within rounding error of angle calc) colinear points\n      if (ringGeom === null) continue\n      geom.push(ringGeom)\n    }\n    return geom\n  }\n}\n\nexport class MultiPolyOut {\n  constructor (rings) {\n    this.rings = rings\n    this.polys = this._composePolys(rings)\n  }\n\n  getGeom () {\n    const geom = []\n    for (let i = 0, iMax = this.polys.length; i < iMax; i++) {\n      const polyGeom = this.polys[i].getGeom()\n      // exterior ring was all (within rounding error of angle calc) colinear points\n      if (polyGeom === null) continue\n      geom.push(polyGeom)\n    }\n    return geom\n  }\n\n  _composePolys (rings) {\n    const polys = []\n    for (let i = 0, iMax = rings.length; i < iMax; i++) {\n      const ring = rings[i]\n      if (ring.poly) continue\n      if (ring.isExteriorRing()) polys.push(new PolyOut(ring))\n      else {\n        const enclosingRing = ring.enclosingRing()\n        if (!enclosingRing.poly) polys.push(new PolyOut(enclosingRing))\n        enclosingRing.poly.addInterior(ring)\n      }\n    }\n    return polys\n  }\n}\n","import SplayTree from 'splaytree'\nimport Segment from './segment'\nimport SweepEvent from './sweep-event'\n\n/**\n * NOTE:  We must be careful not to change any segments while\n *        they are in the SplayTree. AFAIK, there's no way to tell\n *        the tree to rebalance itself - thus before splitting\n *        a segment that's in the tree, we remove it from the tree,\n *        do the split, then re-insert it. (Even though splitting a\n *        segment *shouldn't* change its correct position in the\n *        sweep line tree, the reality is because of rounding errors,\n *        it sometimes does.)\n */\n\nexport default class SweepLine {\n  constructor (queue, comparator = Segment.compare) {\n    this.queue = queue\n    this.tree = new SplayTree(comparator)\n    this.segments = []\n  }\n\n  process (event) {\n    const segment = event.segment\n    const newEvents = []\n\n    // if we've already been consumed by another segment,\n    // clean up our body parts and get out\n    if (event.consumedBy) {\n      if (event.isLeft) this.queue.remove(event.otherSE)\n      else this.tree.remove(segment)\n      return newEvents\n    }\n\n    const node = event.isLeft\n      ? this.tree.insert(segment)\n      : this.tree.find(segment)\n\n    if (! node) throw new Error(\n      `Unable to find segment #${segment.id} ` +\n      `[${segment.leftSE.point.x}, ${segment.leftSE.point.y}] -> ` +\n      `[${segment.rightSE.point.x}, ${segment.rightSE.point.y}] ` +\n      'in SweepLine tree. Please submit a bug report.'\n    )\n\n    let prevNode = node\n    let nextNode = node\n    let prevSeg = undefined\n    let nextSeg = undefined\n\n    // skip consumed segments still in tree\n    while (prevSeg === undefined) {\n      prevNode = this.tree.prev(prevNode)\n      if (prevNode === null) prevSeg = null\n      else if (prevNode.key.consumedBy === undefined) prevSeg = prevNode.key\n    }\n\n    // skip consumed segments still in tree\n    while (nextSeg === undefined) {\n      nextNode = this.tree.next(nextNode)\n      if (nextNode === null) nextSeg = null\n      else if (nextNode.key.consumedBy === undefined) nextSeg = nextNode.key\n    }\n\n    if (event.isLeft) {\n\n      // Check for intersections against the previous segment in the sweep line\n      let prevMySplitter = null\n      if (prevSeg) {\n        const prevInter = prevSeg.getIntersection(segment)\n        if (prevInter !== null) {\n          if (!segment.isAnEndpoint(prevInter)) prevMySplitter = prevInter\n          if (!prevSeg.isAnEndpoint(prevInter)) {\n            const newEventsFromSplit = this._splitSafely(prevSeg, prevInter)\n            for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) {\n              newEvents.push(newEventsFromSplit[i])\n            }\n          }\n        }\n      }\n\n      // Check for intersections against the next segment in the sweep line\n      let nextMySplitter = null\n      if (nextSeg) {\n        const nextInter = nextSeg.getIntersection(segment)\n        if (nextInter !== null) {\n          if (!segment.isAnEndpoint(nextInter)) nextMySplitter = nextInter\n          if (!nextSeg.isAnEndpoint(nextInter))  {\n            const newEventsFromSplit = this._splitSafely(nextSeg, nextInter)\n            for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) {\n              newEvents.push(newEventsFromSplit[i])\n            }\n          }\n        }\n      }\n\n      // For simplicity, even if we find more than one intersection we only\n      // spilt on the 'earliest' (sweep-line style) of the intersections.\n      // The other intersection will be handled in a future process().\n      if (prevMySplitter !== null || nextMySplitter !== null) {\n\n        let mySplitter = null\n        if (prevMySplitter === null) mySplitter = nextMySplitter\n        else if (nextMySplitter === null) mySplitter = prevMySplitter\n        else {\n          const cmpSplitters = SweepEvent.comparePoints(prevMySplitter, nextMySplitter)\n          mySplitter = cmpSplitters <= 0 ? prevMySplitter : nextMySplitter\n        }\n\n        // Rounding errors can cause changes in ordering,\n        // so remove afected segments and right sweep events before splitting\n        this.queue.remove(segment.rightSE)\n        newEvents.push(segment.rightSE)\n\n        const newEventsFromSplit = segment.split(mySplitter)\n        for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) {\n          newEvents.push(newEventsFromSplit[i])\n        }\n      }\n\n      if (newEvents.length > 0) {\n        // We found some intersections, so re-do the current event to\n        // make sure sweep line ordering is totally consistent for later\n        // use with the segment 'prev' pointers\n        this.tree.remove(segment)\n        newEvents.push(event)\n\n      } else {\n        // done with left event\n        this.segments.push(segment)\n        segment.prev = prevSeg\n      }\n\n    } else {\n      // event.isRight\n\n      // since we're about to be removed from the sweep line, check for\n      // intersections between our previous and next segments\n      if (prevSeg && nextSeg) {\n        const inter = prevSeg.getIntersection(nextSeg)\n        if (inter !== null) {\n          if (!prevSeg.isAnEndpoint(inter))  {\n            const newEventsFromSplit = this._splitSafely(prevSeg, inter)\n            for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) {\n              newEvents.push(newEventsFromSplit[i])\n            }\n          }\n          if (!nextSeg.isAnEndpoint(inter))  {\n            const newEventsFromSplit = this._splitSafely(nextSeg, inter)\n            for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) {\n              newEvents.push(newEventsFromSplit[i])\n            }\n          }\n        }\n      }\n\n      this.tree.remove(segment)\n    }\n\n    return newEvents\n  }\n\n  /* Safely split a segment that is currently in the datastructures\n   * IE - a segment other than the one that is currently being processed. */\n  _splitSafely(seg, pt) {\n    // Rounding errors can cause changes in ordering,\n    // so remove afected segments and right sweep events before splitting\n    // removeNode() doesn't work, so have re-find the seg\n    // https://github.com/w8r/splay-tree/pull/5\n    this.tree.remove(seg)\n    const rightSE = seg.rightSE\n    this.queue.remove(rightSE)\n    const newEvents = seg.split(pt)\n    newEvents.push(rightSE)\n    // splitting can trigger consumption\n    if (seg.consumedBy === undefined) this.tree.insert(seg)\n    return newEvents\n  }\n}\n","import SplayTree from 'splaytree'\nimport { getBboxOverlap } from './bbox'\nimport * as geomIn from './geom-in'\nimport * as geomOut from './geom-out'\nimport rounder from './rounder'\nimport SweepEvent from './sweep-event'\nimport SweepLine from './sweep-line'\n\n// Limits on iterative processes to prevent infinite loops - usually caused by floating-point math round-off errors.\nconst POLYGON_CLIPPING_MAX_QUEUE_SIZE =\n  (typeof process !== 'undefined' &&\n    process.env.POLYGON_CLIPPING_MAX_QUEUE_SIZE) ||\n  1000000\nconst POLYGON_CLIPPING_MAX_SWEEPLINE_SEGMENTS =\n  (typeof process !== 'undefined' &&\n    process.env.POLYGON_CLIPPING_MAX_SWEEPLINE_SEGMENTS) ||\n  1000000\n\nexport class Operation {\n  run (type, geom, moreGeoms) {\n    operation.type = type\n    rounder.reset()\n\n    /* Convert inputs to MultiPoly objects */\n    const multipolys = [new geomIn.MultiPolyIn(geom, true)]\n    for (let i = 0, iMax = moreGeoms.length; i < iMax; i++) {\n      multipolys.push(new geomIn.MultiPolyIn(moreGeoms[i], false))\n    }\n    operation.numMultiPolys = multipolys.length\n\n    /* BBox optimization for difference operation\n     * If the bbox of a multipolygon that's part of the clipping doesn't\n     * intersect the bbox of the subject at all, we can just drop that\n     * multiploygon. */\n    if (operation.type === 'difference') {\n      // in place removal\n      const subject = multipolys[0]\n      let i = 1\n      while (i < multipolys.length) {\n        if (getBboxOverlap(multipolys[i].bbox, subject.bbox) !== null) i++\n        else multipolys.splice(i, 1)\n      }\n    }\n\n    /* BBox optimization for intersection operation\n     * If we can find any pair of multipolygons whose bbox does not overlap,\n     * then the result will be empty. */\n    if (operation.type === 'intersection') {\n      // TODO: this is O(n^2) in number of polygons. By sorting the bboxes,\n      //       it could be optimized to O(n * ln(n))\n      for (let i = 0, iMax = multipolys.length; i < iMax; i++) {\n        const mpA = multipolys[i]\n        for (let j = i + 1, jMax = multipolys.length; j < jMax; j++) {\n          if (getBboxOverlap(mpA.bbox, multipolys[j].bbox) === null) return []\n        }\n      }\n    }\n\n    /* Put segment endpoints in a priority queue */\n    const queue = new SplayTree(SweepEvent.compare)\n    for (let i = 0, iMax = multipolys.length; i < iMax; i++) {\n      const sweepEvents = multipolys[i].getSweepEvents()\n      for (let j = 0, jMax = sweepEvents.length; j < jMax; j++) {\n        queue.insert(sweepEvents[j])\n\n        if (queue.size > POLYGON_CLIPPING_MAX_QUEUE_SIZE) {\n          // prevents an infinite loop, an otherwise common manifestation of bugs\n          throw new Error(\n            'Infinite loop when putting segment endpoints in a priority queue ' +\n            '(queue size too big). Please file a bug report.'\n          )\n        }\n      }\n    }\n\n    /* Pass the sweep line over those endpoints */\n    const sweepLine = new SweepLine(queue)\n    let prevQueueSize = queue.size\n    let node = queue.pop()\n    while (node) {\n      const evt = node.key\n      if (queue.size === prevQueueSize) {\n        // prevents an infinite loop, an otherwise common manifestation of bugs\n        const seg = evt.segment\n        throw new Error(\n          `Unable to pop() ${evt.isLeft ? 'left' : 'right'} SweepEvent ` +\n          `[${evt.point.x}, ${evt.point.y}] from segment #${seg.id} ` +\n          `[${seg.leftSE.point.x}, ${seg.leftSE.point.y}] -> ` +\n          `[${seg.rightSE.point.x}, ${seg.rightSE.point.y}] from queue. ` +\n          'Please file a bug report.'\n        )\n      }\n\n      if (queue.size > POLYGON_CLIPPING_MAX_QUEUE_SIZE) {\n        // prevents an infinite loop, an otherwise common manifestation of bugs\n        throw new Error(\n          'Infinite loop when passing sweep line over endpoints ' +\n          '(queue size too big). Please file a bug report.'\n        )\n      }\n\n      if (sweepLine.segments.length > POLYGON_CLIPPING_MAX_SWEEPLINE_SEGMENTS) {\n        // prevents an infinite loop, an otherwise common manifestation of bugs\n        throw new Error(\n          'Infinite loop when passing sweep line over endpoints ' +\n          '(too many sweep line segments). Please file a bug report.'\n        )\n      }\n\n      const newEvents = sweepLine.process(evt)\n      for (let i = 0, iMax = newEvents.length; i < iMax; i++) {\n        const evt = newEvents[i]\n        if (evt.consumedBy === undefined) queue.insert(evt)\n      }\n      prevQueueSize = queue.size\n      node = queue.pop()\n    }\n\n    // free some memory we don't need anymore\n    rounder.reset()\n\n    /* Collect and compile segments we're keeping into a multipolygon */\n    const ringsOut = geomOut.RingOut.factory(sweepLine.segments)\n    const result = new geomOut.MultiPolyOut(ringsOut)\n    return result.getGeom()\n  }\n}\n\n// singleton available by import\nconst operation = new Operation()\n\nexport default operation\n","import operation from './operation'\n\nconst union = (geom, ...moreGeoms) =>\n  operation.run('union', geom, moreGeoms)\n\nconst intersection = (geom, ...moreGeoms) =>\n  operation.run('intersection', geom, moreGeoms)\n\nconst xor = (geom, ...moreGeoms) =>\n  operation.run('xor', geom, moreGeoms)\n\nconst difference = (subjectGeom, ...clippingGeoms) =>\n  operation.run('difference', subjectGeom, clippingGeoms)\n\nexport default {\n  union: union,\n  intersection: intersection,\n  xor: xor,\n  difference: difference,\n}\n"],"names":["isInBbox","bbox","point","ll","x","ur","y","getBboxOverlap","b1","b2","lowerX","upperX","epsilon","Number","EPSILON","undefined","Math","pow","EPSILON_SQ","cmp","a","b","ab","PtRounder","reset","xRounder","CoordRounder","yRounder","this","round","tree","SplayTree","coord","node","add","prevNode","prev","key","remove","nextNode","next","rounder","crossProduct","dotProduct","compareVectorAngles","basePt","endPt1","endPt2","v1","v2","kross","length","v","sqrt","cosineOfAngle","pShared","pBase","pAngle","vBase","vAngle","horizontalIntersection","pt","verticalIntersection","SweepEvent","isLeft","events","push","ptCmp","comparePoints","link","Segment","compare","segment","aPt","bPt","other","Error","otherEvents","i","iMax","evt","checkForConsuming","numEvents","evt1","consumedBy","j","evt2","otherSE","consume","ringOut","isInResult","baseEvent","cache","Map","fillCache","linkedEvent","nextEvent","set","sine","_this","cosine","has","get","asine","acosine","bsine","bcosine","segmentId","leftSE","rightSE","rings","windings","id","alx","blx","arx","brx","aly","bly","ary","bry","aCmpBLeft","comparePoint","bCmpARight","bCmpALeft","aCmpBRight","ay","ax","by","bx","newRightSE","y1","y2","isAnEndpoint","lPt","rPt","vector","yDist","xFromYDist","xDist","yFromXDist","tBbox","oBbox","bboxOverlap","tlp","trp","olp","orp","touchesOtherLSE","touchesThisLSE","touchesOtherRSE","touchesThisRSE","pt1","pt2","ve","d1","d2","intersection","newEvents","alreadyLinked","newLeftSE","oldRightSE","replaceRightSE","newSeg","slice","swapEvents","tmpEvt","consumer","consumee","tmp","ring","winding","index","indexOf","_prevInResult","prevInResult","_beforeState","seg","afterState","multiPolys","_afterState","beforeState","ringsAfter","windingsAfter","mpsAfter","polysAfter","polysExclude","poly","isExterior","splice","mp","multiPoly","_isInResult","mpsBefore","operation","type","noBefores","noAfters","least","most","numMultiPolys","diff","abs","isJustSubject","mps","isSubject","leftPt","rightPt","cmpPts","RingIn","geomRing","Array","isArray","segments","firstPoint","prevPoint","fromRing","sweepEvents","PolyIn","geomPoly","exteriorRing","interiorRings","getSweepEvents","ringSweepEvents","jMax","MultiPolyIn","geom","ex","polys","POSITIVE_INFINITY","NEGATIVE_INFINITY","polySweepEvents","RingOut","allSegments","ringsOut","prevEvent","event","startingPoint","intersectionLEs","availableLEs","getAvailableLinkedEvents","firstPt","lastPt","indexLE","comparator","getLeftmostComparator","sort","intersectionLE","ringEvents","unshift","reverse","prevPt","points","nextPt","shift","step","isExteriorRing","iStart","iEnd","orderedPoints","_isExteriorRing","enclosing","enclosingRing","_enclosingRing","_calcEnclosingRing","leftMostEvt","prevSeg","prevPrevSeg","PolyOut","getGeom","ringGeom","MultiPolyOut","_composePolys","polyGeom","addInterior","SweepLine","queue","insert","find","nextSeg","prevMySplitter","prevInter","getIntersection","newEventsFromSplit","_splitSafely","nextMySplitter","nextInter","mySplitter","split","inter","POLYGON_CLIPPING_MAX_QUEUE_SIZE","process","env","POLYGON_CLIPPING_MAX_SWEEPLINE_SEGMENTS","moreGeoms","multipolys","geomIn","subject","mpA","size","sweepLine","prevQueueSize","pop","geomOut","factory","union","run","xor","difference","subjectGeom","clippingGeoms"],"mappings":";;;;;;;;kkMAOO,IAAMA,EAAW,SAACC,EAAMC,UAE1BD,EAAKE,GAAGC,GAAKF,EAAME,GACnBF,EAAME,GAAKH,EAAKI,GAAGD,GACnBH,EAAKE,GAAGG,GAAKJ,EAAMI,GACnBJ,EAAMI,GAAKL,EAAKI,GAAGC,GAOXC,EAAiB,SAACC,EAAIC,MAG/BA,EAAGJ,GAAGD,EAAII,EAAGL,GAAGC,GAChBI,EAAGH,GAAGD,EAAIK,EAAGN,GAAGC,GAChBK,EAAGJ,GAAGC,EAAIE,EAAGL,GAAGG,GAChBE,EAAGH,GAAGC,EAAIG,EAAGN,GAAGG,EAChB,OAAO,SAGHI,EAASF,EAAGL,GAAGC,EAAIK,EAAGN,GAAGC,EAAIK,EAAGN,GAAGC,EAAII,EAAGL,GAAGC,EAC7CO,EAASH,EAAGH,GAAGD,EAAIK,EAAGJ,GAAGD,EAAII,EAAGH,GAAGD,EAAIK,EAAGJ,GAAGD,QAO5C,CAAED,GAAI,CAAEC,EAAGM,EAAQJ,EAJXE,EAAGL,GAAGG,EAAIG,EAAGN,GAAGG,EAAIG,EAAGN,GAAGG,EAAIE,EAAGL,GAAGG,GAIZD,GAAI,CAAED,EAAGO,EAAQL,EAHzCE,EAAGH,GAAGC,EAAIG,EAAGJ,GAAGC,EAAIE,EAAGH,GAAGC,EAAIG,EAAGJ,GAAGC,KC5BjDM,EAAUC,OAAOC,aAGLC,IAAZH,IAAuBA,EAAUI,KAAKC,IAAI,GAAI,KAElD,IAAMC,EAAaN,EAAUA,EAGhBO,EAAM,SAACC,EAAGC,OAEhBT,EAAUQ,GAAKA,EAAIR,IACjBA,EAAUS,GAAKA,EAAIT,SACf,MAKLU,EAAKF,EAAIC,SACXC,EAAKA,EAAKJ,EAAaE,EAAIC,EACtB,EAIFD,EAAIC,GAAK,EAAI,GCbhBE,yCAEGC,uDAIAC,SAAW,IAAIC,OACfC,SAAW,IAAID,gCAGftB,EAAGE,SACD,CACLF,EAAGwB,KAAKH,SAASI,MAAMzB,GACvBE,EAAGsB,KAAKD,SAASE,MAAMvB,aAKvBoB,yCAEGI,KAAO,IAAIC,OAEXF,MAAM,2CAUNG,OACCC,EAAOL,KAAKE,KAAKI,IAAIF,GAErBG,EAAWP,KAAKE,KAAKM,KAAKH,MACf,OAAbE,GAAqD,IAAhChB,EAAIc,EAAKI,IAAKF,EAASE,iBACzCP,KAAKQ,OAAON,GACVG,EAASE,QAGZE,EAAWX,KAAKE,KAAKU,KAAKP,UACf,OAAbM,GAAqD,IAAhCpB,EAAIc,EAAKI,IAAKE,EAASF,WACzCP,KAAKQ,OAAON,GACVO,EAASF,KAGXL,WAKLS,EAAU,IAAIlB,ECjEPmB,EAAe,SAACtB,EAAGC,UAAMD,EAAEhB,EAAIiB,EAAEf,EAAIc,EAAEd,EAAIe,EAAEjB,GAG7CuC,EAAa,SAACvB,EAAGC,UAAMD,EAAEhB,EAAIiB,EAAEjB,EAAIgB,EAAEd,EAAIe,EAAEf,GAG3CsC,EAAsB,SAACC,EAAQC,EAAQC,OAC5CC,EAAK,CAAE5C,EAAG0C,EAAO1C,EAAIyC,EAAOzC,EAAGE,EAAGwC,EAAOxC,EAAIuC,EAAOvC,GACpD2C,EAAK,CAAE7C,EAAG2C,EAAO3C,EAAIyC,EAAOzC,EAAGE,EAAGyC,EAAOzC,EAAIuC,EAAOvC,GACpD4C,EAAQR,EAAaM,EAAIC,UACxB9B,EAAI+B,EAAO,IAGPC,EAAS,SAAAC,UAAKpC,KAAKqC,KAAKV,EAAWS,EAAGA,KAUtCE,EAAgB,SAACC,EAASC,EAAOC,OACtCC,EAAQ,CAAEtD,EAAGoD,EAAMpD,EAAImD,EAAQnD,EAAGE,EAAGkD,EAAMlD,EAAIiD,EAAQjD,GACvDqD,EAAS,CAAEvD,EAAGqD,EAAOrD,EAAImD,EAAQnD,EAAGE,EAAGmD,EAAOnD,EAAIiD,EAAQjD,UACzDqC,EAAWgB,EAAQD,GAASP,EAAOQ,GAAUR,EAAOO,IA2ChDE,EAAyB,SAACC,EAAIT,EAAG9C,UAChC,IAAR8C,EAAE9C,EAAgB,KACf,CAAEF,EAAGyD,EAAGzD,EAAIgD,EAAEhD,EAAIgD,EAAE9C,GAAMA,EAAIuD,EAAGvD,GAAKA,EAAGA,IAMrCwD,EAAuB,SAACD,EAAIT,EAAGhD,UAC9B,IAARgD,EAAEhD,EAAgB,KACf,CAAEA,EAAGA,EAAGE,EAAGuD,EAAGvD,EAAI8C,EAAE9C,EAAI8C,EAAEhD,GAAMA,EAAIyD,EAAGzD,KC/E3B2D,wBAgCN7D,EAAO8D,kBACGjD,IAAjBb,EAAM+D,OAAsB/D,EAAM+D,OAAS,CAACrC,MAC3C1B,EAAM+D,OAAOC,KAAKtC,WAClB1B,MAAQA,OACR8D,OAASA,iDAjCA5C,EAAGC,OAGX8C,EAAQJ,EAAWK,cAAchD,EAAElB,MAAOmB,EAAEnB,cACpC,IAAViE,EAAoBA,GAGpB/C,EAAElB,QAAUmB,EAAEnB,OAAOkB,EAAEiD,KAAKhD,GAG5BD,EAAE4C,SAAW3C,EAAE2C,OAAe5C,EAAE4C,OAAS,GAAK,EAI3CM,EAAQC,QAAQnD,EAAEoD,QAASnD,EAAEmD,gDAIhBC,EAAKC,UACrBD,EAAIrE,EAAIsE,EAAItE,GAAW,EACvBqE,EAAIrE,EAAIsE,EAAItE,EAAU,EAEtBqE,EAAInE,EAAIoE,EAAIpE,GAAW,EACvBmE,EAAInE,EAAIoE,EAAIpE,EAAU,EAEnB,sCAYHqE,MACAA,EAAMzE,QAAU0B,KAAK1B,YACjB,IAAI0E,MAAM,+CAEZC,EAAcF,EAAMzE,MAAM+D,OACvBa,EAAI,EAAGC,EAAOF,EAAY1B,OAAQ2B,EAAIC,EAAMD,IAAK,KAClDE,EAAMH,EAAYC,QACnB5E,MAAM+D,OAAOC,KAAKc,GACvBA,EAAI9E,MAAQ0B,KAAK1B,WAEd+E,wEAYCC,EAAYtD,KAAK1B,MAAM+D,OAAOd,OAC3B2B,EAAI,EAAGA,EAAII,EAAWJ,IAAK,KAC5BK,EAAOvD,KAAK1B,MAAM+D,OAAOa,WACC/D,IAA5BoE,EAAKX,QAAQY,eACZ,IAAIC,EAAIP,EAAI,EAAGO,EAAIH,EAAWG,IAAK,KAChCC,EAAO1D,KAAK1B,MAAM+D,OAAOoB,QACPtE,IAApBuE,EAAKF,aACLD,EAAKI,QAAQrF,MAAM+D,SAAWqB,EAAKC,QAAQrF,MAAM+D,QACrDkB,EAAKX,QAAQgB,QAAQF,EAAKd,uEAOxBP,EAAS,GACNa,EAAI,EAAGC,EAAOnD,KAAK1B,MAAM+D,OAAOd,OAAQ2B,EAAIC,EAAMD,IAAK,KACxDE,EAAMpD,KAAK1B,MAAM+D,OAAOa,GAC1BE,IAAQpD,OAASoD,EAAIR,QAAQiB,SAAWT,EAAIR,QAAQkB,cACtDzB,EAAOC,KAAKc,UAGTf,gDAac0B,cACfC,EAAQ,IAAIC,IAEZC,EAAY,SAAAC,ODpFMxC,EAASC,EAAOC,EACpCC,EACAC,ECmFIqC,EAAYD,EAAYR,QAC9BK,EAAMK,IAAIF,EAAa,CACrBG,MDvFoB3C,ECuFF4C,EAAKjG,MDvFMsD,ECuFCmC,EAAUzF,MDvFJuD,ECuFWuC,EAAU9F,MDtFzDwD,EAAQ,CAAEtD,EAAGoD,EAAMpD,EAAImD,EAAQnD,EAAGE,EAAGkD,EAAMlD,EAAIiD,EAAQjD,GACvDqD,EAAS,CAAEvD,EAAGqD,EAAOrD,EAAImD,EAAQnD,EAAGE,EAAGmD,EAAOnD,EAAIiD,EAAQjD,GACzDoC,EAAaiB,EAAQD,GAASP,EAAOQ,GAAUR,EAAOO,ICqFvD0C,OAAQ9C,EAAc6C,EAAKjG,MAAOyF,EAAUzF,MAAO8F,EAAU9F,iBAI1D,SAACkB,EAAGC,GACJuE,EAAMS,IAAIjF,IAAI0E,EAAU1E,GACxBwE,EAAMS,IAAIhF,IAAIyE,EAAUzE,SAEYuE,EAAMU,IAAIlF,GAArCmF,IAANL,KAAqBM,IAARJ,SACoBR,EAAMU,IAAIjF,GAArCoF,IAANP,KAAqBQ,IAARN,cAGjBG,GAAS,GAAKE,GAAS,EACrBD,EAAUE,EAAgB,EAC1BF,EAAUE,GAAiB,EACxB,EAILH,EAAQ,GAAKE,EAAQ,EACnBD,EAAUE,GAAiB,EAC3BF,EAAUE,EAAgB,EACvB,EAILD,EAAQF,GAAe,EACvBE,EAAQF,EAAc,EACnB,YC/HTI,EAAY,EAEKrC,wBA+HNsC,EAAQC,EAASC,EAAOC,kBAC9BC,KAAOL,OACPC,OAASA,EACdA,EAAOpC,QAAU5C,KACjBgF,EAAOrB,QAAUsB,OACZA,QAAUA,EACfA,EAAQrC,QAAU5C,KAClBiF,EAAQtB,QAAUqB,OACbE,MAAQA,OACRC,SAAWA,iDAzHF3F,EAAGC,OAEX4F,EAAM7F,EAAEwF,OAAO1G,MAAME,EACrB8G,EAAM7F,EAAEuF,OAAO1G,MAAME,EACrB+G,EAAM/F,EAAEyF,QAAQ3G,MAAME,EACtBgH,EAAM/F,EAAEwF,QAAQ3G,MAAME,KAGxBgH,EAAMH,EAAK,OAAO,KAClBE,EAAMD,EAAK,OAAQ,MAEjBG,EAAMjG,EAAEwF,OAAO1G,MAAMI,EACrBgH,EAAMjG,EAAEuF,OAAO1G,MAAMI,EACrBiH,EAAMnG,EAAEyF,QAAQ3G,MAAMI,EACtBkH,EAAMnG,EAAEwF,QAAQ3G,MAAMI,KAGxB2G,EAAMC,EAAK,IAETI,EAAMD,GAAOC,EAAMC,EAAK,OAAO,KAC/BD,EAAMD,GAAOC,EAAMC,EAAK,OAAQ,MAG9BE,EAAYrG,EAAEsG,aAAarG,EAAEuF,OAAO1G,UACtCuH,EAAY,EAAG,OAAO,KACtBA,EAAY,EAAG,OAAQ,MAGrBE,EAAatG,EAAEqG,aAAatG,EAAEyF,QAAQ3G,cACzB,IAAfyH,EAAyBA,GAIrB,KAINV,EAAMC,EAAK,IACTG,EAAMC,GAAOD,EAAMG,EAAK,OAAQ,KAChCH,EAAMC,GAAOD,EAAMG,EAAK,OAAO,MAG7BI,EAAYvG,EAAEqG,aAAatG,EAAEwF,OAAO1G,UACxB,IAAd0H,EAAiB,OAAOA,MAGtBC,EAAazG,EAAEsG,aAAarG,EAAEwF,QAAQ3G,cACxC2H,EAAa,EAAU,EACvBA,EAAa,GAAW,EAIrB,KAOLR,EAAMC,EAAK,OAAQ,KACnBD,EAAMC,EAAK,OAAO,KAMlBH,EAAMC,EAAK,KACPO,EAAatG,EAAEqG,aAAatG,EAAEyF,QAAQ3G,UACzB,IAAfyH,EAAkB,OAAOA,KAI3BR,EAAMC,EAAK,KACPS,EAAazG,EAAEsG,aAAarG,EAAEwF,QAAQ3G,UACxC2H,EAAa,EAAG,OAAO,KACvBA,EAAa,EAAG,OAAQ,KAG1BV,IAAQC,EAAM,KAGVU,EAAKP,EAAMF,EACXU,EAAKZ,EAAMF,EACXe,EAAKR,EAAMF,EACXW,EAAKb,EAAMF,KACbY,EAAKC,GAAMC,EAAKC,EAAI,OAAO,KAC3BH,EAAKC,GAAMC,EAAKC,EAAI,OAAQ,SAK9Bd,EAAMC,EAAY,EAClBD,EAAMC,GAMNG,EAAMC,GANa,EAOnBD,EAAMC,EAAY,EAIlBpG,EAAE4F,GAAK3F,EAAE2F,IAAY,EACrB5F,EAAE4F,GAAK3F,EAAE2F,GAAW,EAGjB,gDA4COkB,QACTrB,QAAUqB,OACVrB,QAAQrC,QAAU5C,UAClBiF,QAAQtB,QAAU3D,KAAKgF,YACvBA,OAAOrB,QAAU3D,KAAKiF,2CAIrBsB,EAAKvG,KAAKgF,OAAO1G,MAAMI,EACvB8H,EAAKxG,KAAKiF,QAAQ3G,MAAMI,QACvB,CACLH,GAAI,CAAEC,EAAGwB,KAAKgF,OAAO1G,MAAME,EAAGE,EAAG6H,EAAKC,EAAKD,EAAKC,GAChD/H,GAAI,CAAED,EAAGwB,KAAKiF,QAAQ3G,MAAME,EAAGE,EAAG6H,EAAKC,EAAKD,EAAKC,2CAM5C,CACLhI,EAAGwB,KAAKiF,QAAQ3G,MAAME,EAAIwB,KAAKgF,OAAO1G,MAAME,EAC5CE,EAAGsB,KAAKiF,QAAQ3G,MAAMI,EAAIsB,KAAKgF,OAAO1G,MAAMI,wCAIlCuD,UAETA,EAAGzD,IAAMwB,KAAKgF,OAAO1G,MAAME,GAAKyD,EAAGvD,IAAMsB,KAAKgF,OAAO1G,MAAMI,GAC3DuD,EAAGzD,IAAMwB,KAAKiF,QAAQ3G,MAAME,GAAKyD,EAAGvD,IAAMsB,KAAKiF,QAAQ3G,MAAMI,uCAiBpDJ,MACR0B,KAAKyG,aAAanI,GAAQ,OAAO,MAE/BoI,EAAM1G,KAAKgF,OAAO1G,MAClBqI,EAAM3G,KAAKiF,QAAQ3G,MACnBkD,EAAIxB,KAAK4G,YAGXF,EAAIlI,IAAMmI,EAAInI,SACZF,EAAME,IAAMkI,EAAIlI,EAAU,EACvBF,EAAME,EAAIkI,EAAIlI,EAAI,GAAK,MAK1BqI,GAASvI,EAAMI,EAAIgI,EAAIhI,GAAK8C,EAAE9C,EAC9BoI,EAAaJ,EAAIlI,EAAIqI,EAAQrF,EAAEhD,KACjCF,EAAME,IAAMsI,EAAY,OAAO,MAI7BC,GAAUzI,EAAME,EAAIkI,EAAIlI,GAAKgD,EAAEhD,EAC/BwI,EAAaN,EAAIhI,EAAIqI,EAAQvF,EAAE9C,SACjCJ,EAAMI,IAAMsI,EAAmB,EAC5B1I,EAAMI,EAAIsI,GAAc,EAAI,0CAkBpBjE,OAETkE,EAAQjH,KAAK3B,OACb6I,EAAQnE,EAAM1E,OACd8I,EAAcxI,EAAesI,EAAOC,MACtB,OAAhBC,EAAsB,OAAO,SAM3BC,EAAMpH,KAAKgF,OAAO1G,MAClB+I,EAAMrH,KAAKiF,QAAQ3G,MACnBgJ,EAAMvE,EAAMiC,OAAO1G,MACnBiJ,EAAMxE,EAAMkC,QAAQ3G,MAKpBkJ,EAAkBpJ,EAAS6I,EAAOK,IAAmC,IAA3BtH,KAAK8F,aAAawB,GAC5DG,EAAiBrJ,EAAS8I,EAAOE,IAAoC,IAA5BrE,EAAM+C,aAAasB,GAC5DM,EAAkBtJ,EAAS6I,EAAOM,IAAmC,IAA3BvH,KAAK8F,aAAayB,GAC5DI,EAAiBvJ,EAAS8I,EAAOG,IAAoC,IAA5BtE,EAAM+C,aAAauB,MAG9DI,GAAkBD,SAGhBG,IAAmBD,EAAwBL,GAC1CM,GAAkBD,EAAwBH,EAGxC,QAILE,SAEEC,GACEN,EAAI5I,IAAM+I,EAAI/I,GAAK4I,EAAI1I,IAAM6I,EAAI7I,EAAU,KAG1C0I,KAILI,SAEEG,GACEN,EAAI7I,IAAM8I,EAAI9I,GAAK6I,EAAI3I,IAAM4I,EAAI5I,EAAU,KAG1C4I,KAILK,GAAkBD,EAAiB,OAAO,QAG1CC,EAAgB,OAAON,KACvBK,EAAiB,OAAOH,MAItBtF,EF/OkB,SAAC2F,EAAKxG,EAAIyG,EAAKxG,MAI5B,IAATD,EAAG5C,EAAS,OAAO0D,EAAqB2F,EAAKxG,EAAIuG,EAAIpJ,MAC5C,IAAT6C,EAAG7C,EAAS,OAAO0D,EAAqB0F,EAAKxG,EAAIyG,EAAIrJ,MAC5C,IAAT4C,EAAG1C,EAAS,OAAOsD,EAAuB6F,EAAKxG,EAAIuG,EAAIlJ,MAC9C,IAAT2C,EAAG3C,EAAS,OAAOsD,EAAuB4F,EAAKxG,EAAIyG,EAAInJ,OAMrD4C,EAAQR,EAAaM,EAAIC,MAClB,GAATC,EAAY,OAAO,SAEjBwG,EAAK,CAAEtJ,EAAGqJ,EAAIrJ,EAAIoJ,EAAIpJ,EAAGE,EAAGmJ,EAAInJ,EAAIkJ,EAAIlJ,GACxCqJ,EAAKjH,EAAagH,EAAI1G,GAAME,EAC5B0G,EAAKlH,EAAagH,EAAIzG,GAAMC,QAO3B,CAAE9C,GAJEoJ,EAAIpJ,EAAIwJ,EAAK5G,EAAG5C,GAAQqJ,EAAIrJ,EAAIuJ,EAAK1G,EAAG7C,IAE7B,EAEPE,GAHJkJ,EAAIlJ,EAAIsJ,EAAK5G,EAAG1C,GAAQmJ,EAAInJ,EAAIqJ,EAAK1G,EAAG3C,IAE7B,GEuNTuJ,CAAab,EAAKpH,KAAK4G,SAAUU,EAAKvE,EAAM6D,iBAI5C,OAAP3E,EAAoB,KAGnB7D,EAAS+I,EAAalF,GAGpBpB,EAAQZ,MAAMgC,EAAGzD,EAAGyD,EAAGvD,GAHS,mCAkBlCJ,OACC4J,EAAY,GACZC,OAAiChJ,IAAjBb,EAAM+D,OAEtB+F,EAAY,IAAIjG,EAAW7D,GAAO,GAClCgI,EAAa,IAAInE,EAAW7D,GAAO,GACnC+J,EAAarI,KAAKiF,aACnBqD,eAAehC,GACpB4B,EAAU5F,KAAKgE,GACf4B,EAAU5F,KAAK8F,OACTG,EAAS,IAAI7F,EACjB0F,EAAWC,EAAYrI,KAAKkF,MAAMsD,QAASxI,KAAKmF,SAASqD,gBAMvDrG,EAAWK,cAAc+F,EAAOvD,OAAO1G,MAAOiK,EAAOtD,QAAQ3G,OAAS,GACxEiK,EAAOE,aAELtG,EAAWK,cAAcxC,KAAKgF,OAAO1G,MAAO0B,KAAKiF,QAAQ3G,OAAS,QAC/DmK,aAMHN,IACFC,EAAU/E,oBACViD,EAAWjD,qBAGN6E,2CAKDQ,EAAS1I,KAAKiF,aACfA,QAAUjF,KAAKgF,YACfA,OAAS0D,OACT1D,OAAO5C,QAAS,OAChB6C,QAAQ7C,QAAS,MACjB,IAAIc,EAAI,EAAGC,EAAOnD,KAAKmF,SAAS5D,OAAQ2B,EAAIC,EAAMD,SAChDiC,SAASjC,KAAO,kCAMhBH,WACH4F,EAAW3I,KACX4I,EAAW7F,EACR4F,EAASnF,YAAYmF,EAAWA,EAASnF,gBACzCoF,EAASpF,YAAYoF,EAAWA,EAASpF,eAE1CjE,EAAMmD,EAAQC,QAAQgG,EAAUC,MAC1B,IAARrJ,MAGAA,EAAO,EAAG,KACNsJ,EAAMF,EACZA,EAAWC,EACXA,EAAWC,KAITF,EAASnI,OAASoI,EAAU,KACxBC,EAAMF,EACZA,EAAWC,EACXA,EAAWC,MAGR,IAAI3F,EAAI,EAAGC,EAAOyF,EAAS1D,MAAM3D,OAAQ2B,EAAIC,EAAMD,IAAK,KACrD4F,EAAOF,EAAS1D,MAAMhC,GACtB6F,EAAUH,EAASzD,SAASjC,GAC5B8F,EAAQL,EAASzD,MAAM+D,QAAQH,IACtB,IAAXE,GACFL,EAASzD,MAAM5C,KAAKwG,GACpBH,EAASxD,SAAS7C,KAAKyG,IAEpBJ,EAASxD,SAAS6D,IAAUD,EAEnCH,EAAS1D,MAAQ,KACjB0D,EAASzD,SAAW,KACpByD,EAASpF,WAAamF,EAGtBC,EAAS5D,OAAOxB,WAAamF,EAAS3D,OACtC4D,EAAS3D,QAAQzB,WAAamF,EAAS1D,4DAKZ9F,IAAvBa,KAAKkJ,gBACHlJ,KAAKQ,KACFR,KAAKQ,KAAKsD,aAAc9D,KAAKkJ,cAAgBlJ,KAAKQ,KACtDR,KAAKkJ,cAAgBlJ,KAAKQ,KAAK2I,eAFnBnJ,KAAKkJ,cAAgB,MADOlJ,KAAKkJ,4DAQxB/J,IAAtBa,KAAKoJ,aAA4B,OAAOpJ,KAAKoJ,gBAC3CpJ,KAAKQ,KAKN,KACG6I,EAAMrJ,KAAKQ,KAAKgD,YAAcxD,KAAKQ,UACpC4I,aAAeC,EAAIC,kBAPTtJ,KAAKoJ,aAAe,CACnClE,MAAO,GACPC,SAAU,GACVoE,WAAY,WAMPvJ,KAAKoJ,0DAIajK,IAArBa,KAAKwJ,YAA2B,OAAOxJ,KAAKwJ,gBAE1CC,EAAczJ,KAAKyJ,mBACpBD,YAAc,CACjBtE,MAAOuE,EAAYvE,MAAMsD,MAAM,GAC/BrD,SAAUsE,EAAYtE,SAASqD,MAAM,GACrCe,WAAY,YAERG,EAAa1J,KAAKwJ,YAAYtE,MAC9ByE,EAAgB3J,KAAKwJ,YAAYrE,SACjCyE,EAAW5J,KAAKwJ,YAAYD,WAGzBrG,EAAI,EAAGC,EAAOnD,KAAKkF,MAAM3D,OAAQ2B,EAAIC,EAAMD,IAAK,KACjD4F,EAAO9I,KAAKkF,MAAMhC,GAClB6F,EAAU/I,KAAKmF,SAASjC,GACxB8F,EAAQU,EAAWT,QAAQH,IAClB,IAAXE,GACFU,EAAWpH,KAAKwG,GAChBa,EAAcrH,KAAKyG,IAEhBY,EAAcX,IAAUD,UAIzBc,EAAa,GACbC,EAAe,GACZ5G,EAAI,EAAGC,EAAOuG,EAAWnI,OAAQ2B,EAAIC,EAAMD,OACzB,IAArByG,EAAczG,QACZ4F,EAAOY,EAAWxG,GAClB6G,EAAOjB,EAAKiB,SACkB,IAAhCD,EAAab,QAAQc,MACrBjB,EAAKkB,WAAYH,EAAWvH,KAAKyH,OAChC,EACiC,IAAhCD,EAAab,QAAQc,IAAcD,EAAaxH,KAAKyH,OACnDf,EAAQa,EAAWZ,QAAQH,EAAKiB,OACvB,IAAXf,GAAca,EAAWI,OAAOjB,EAAO,QAK1C,IAAI9F,EAAI,EAAGC,EAAO0G,EAAWtI,OAAQ2B,EAAIC,EAAMD,IAAK,KACjDgH,EAAKL,EAAW3G,GAAGiH,WACK,IAA1BP,EAASX,QAAQiB,IAAYN,EAAStH,KAAK4H,UAG1ClK,KAAKwJ,oDAMRxJ,KAAKwD,WAAY,OAAO,UAEHrE,IAArBa,KAAKoK,YAA2B,OAAOpK,KAAKoK,gBAE1CC,EAAYrK,KAAKyJ,cAAcF,WAC/BK,EAAW5J,KAAKsJ,aAAaC,kBAE3Be,EAAUC,UACX,YAIGC,EAAiC,IAArBH,EAAU9I,OACtBkJ,EAA+B,IAApBb,EAASrI,YACrB6I,YAAcI,IAAcC,YAI9B,mBAKCC,EACAC,EACAN,EAAU9I,OAASqI,EAASrI,QAC9BmJ,EAAQL,EAAU9I,OAClBoJ,EAAOf,EAASrI,SAEhBmJ,EAAQd,EAASrI,OACjBoJ,EAAON,EAAU9I,aAEd6I,YAAcO,IAASL,EAAUM,eAAiBF,EAAQC,YAI5D,UAIGE,EAAOzL,KAAK0L,IAAIT,EAAU9I,OAASqI,EAASrI,aAC7C6I,YAAcS,EAAO,GAAM,YAI7B,iBAGGE,EAAgB,SAAAC,UAAsB,IAAfA,EAAIzJ,QAAgByJ,EAAI,GAAGC,gBACnDb,YAAcW,EAAcV,KAAeU,EAAcnB,uBAKxD,IAAI5G,kDAA2CsH,EAAUC,cAG5DvK,KAAKoK,+CAxaExC,EAAKC,EAAKiB,OACpBoC,EAAQC,EAASpC,EAGfqC,EAASjJ,EAAWK,cAAcoF,EAAKC,MACzCuD,EAAS,EACXF,EAAStD,EACTuD,EAAUtD,EACVkB,EAAU,MAEP,CAAA,KAAIqC,EAAS,GAKb,MAAM,IAAIpI,uDAC6B4E,EAAIpJ,eAAMoJ,EAAIlJ,QALxDwM,EAASrD,EACTsD,EAAUvD,EACVmB,GAAW,SAQN,IAAIrG,EAFI,IAAIP,EAAW+I,GAAQ,GACtB,IAAI/I,EAAWgJ,GAAS,GACJ,CAACrC,GAAO,CAACC,aCzKpCsC,wBACEC,EAAUvB,EAAMC,iBACtBuB,MAAMC,QAAQF,IAAiC,IAApBA,EAAS/J,aACjC,IAAIyB,MAAM,iEAGb+G,KAAOA,OACPC,WAAaA,OACbyB,SAAW,GAEc,iBAAnBH,EAAS,GAAG,IAA6C,iBAAnBA,EAAS,GAAG,SACrD,IAAItI,MAAM,6DAGZ0I,EAAa7K,EAAQZ,MAAMqL,EAAS,GAAG,GAAIA,EAAS,GAAG,SACxDjN,KAAO,CACVE,GAAI,CAAEC,EAAGkN,EAAWlN,EAAGE,EAAGgN,EAAWhN,GACrCD,GAAI,CAAED,EAAGkN,EAAWlN,EAAGE,EAAGgN,EAAWhN,YAGnCiN,EAAYD,EACPxI,EAAI,EAAGC,EAAOmI,EAAS/J,OAAQ2B,EAAIC,EAAMD,IAAK,IACvB,iBAAnBoI,EAASpI,GAAG,IAA6C,iBAAnBoI,EAASpI,GAAG,SACrD,IAAIF,MAAM,6DAEd1E,EAAQuC,EAAQZ,MAAMqL,EAASpI,GAAG,GAAIoI,EAASpI,GAAG,IAElD5E,EAAME,IAAMmN,EAAUnN,GAAKF,EAAMI,IAAMiN,EAAUjN,SAChD+M,SAASnJ,KAAKI,EAAQkJ,SAASD,EAAWrN,EAAO0B,OAClD1B,EAAME,EAAIwB,KAAK3B,KAAKE,GAAGC,IAAGwB,KAAK3B,KAAKE,GAAGC,EAAIF,EAAME,GACjDF,EAAMI,EAAIsB,KAAK3B,KAAKE,GAAGG,IAAGsB,KAAK3B,KAAKE,GAAGG,EAAIJ,EAAMI,GACjDJ,EAAME,EAAIwB,KAAK3B,KAAKI,GAAGD,IAAGwB,KAAK3B,KAAKI,GAAGD,EAAIF,EAAME,GACjDF,EAAMI,EAAIsB,KAAK3B,KAAKI,GAAGC,IAAGsB,KAAK3B,KAAKI,GAAGC,EAAIJ,EAAMI,GACrDiN,EAAYrN,GAGVoN,EAAWlN,IAAMmN,EAAUnN,GAAKkN,EAAWhN,IAAMiN,EAAUjN,QACxD+M,SAASnJ,KAAKI,EAAQkJ,SAASD,EAAWD,EAAY1L,kEAKvD6L,EAAc,GACX3I,EAAI,EAAGC,EAAOnD,KAAKyL,SAASlK,OAAQ2B,EAAIC,EAAMD,IAAK,KACpDN,EAAU5C,KAAKyL,SAASvI,GAC9B2I,EAAYvJ,KAAKM,EAAQoC,QACzB6G,EAAYvJ,KAAKM,EAAQqC,gBAEpB4G,WAIEC,wBACEC,EAAU5B,iBAChBoB,MAAMC,QAAQO,SACX,IAAI/I,MAAM,8DAEbgJ,aAAe,IAAIX,EAAOU,EAAS,GAAI/L,MAAM,QAE7C3B,KAAO,CACVE,GAAI,CAAEC,EAAGwB,KAAKgM,aAAa3N,KAAKE,GAAGC,EAAGE,EAAGsB,KAAKgM,aAAa3N,KAAKE,GAAGG,GACnED,GAAI,CAAED,EAAGwB,KAAKgM,aAAa3N,KAAKI,GAAGD,EAAGE,EAAGsB,KAAKgM,aAAa3N,KAAKI,GAAGC,SAEhEuN,cAAgB,OAChB,IAAI/I,EAAI,EAAGC,EAAO4I,EAASxK,OAAQ2B,EAAIC,EAAMD,IAAK,KAC/C4F,EAAO,IAAIuC,EAAOU,EAAS7I,GAAIlD,MAAM,GACvC8I,EAAKzK,KAAKE,GAAGC,EAAIwB,KAAK3B,KAAKE,GAAGC,IAAGwB,KAAK3B,KAAKE,GAAGC,EAAIsK,EAAKzK,KAAKE,GAAGC,GAC/DsK,EAAKzK,KAAKE,GAAGG,EAAIsB,KAAK3B,KAAKE,GAAGG,IAAGsB,KAAK3B,KAAKE,GAAGG,EAAIoK,EAAKzK,KAAKE,GAAGG,GAC/DoK,EAAKzK,KAAKI,GAAGD,EAAIwB,KAAK3B,KAAKI,GAAGD,IAAGwB,KAAK3B,KAAKI,GAAGD,EAAIsK,EAAKzK,KAAKI,GAAGD,GAC/DsK,EAAKzK,KAAKI,GAAGC,EAAIsB,KAAK3B,KAAKI,GAAGC,IAAGsB,KAAK3B,KAAKI,GAAGC,EAAIoK,EAAKzK,KAAKI,GAAGC,QAC9DuN,cAAc3J,KAAKwG,QAErBqB,UAAYA,6DAIX0B,EAAc7L,KAAKgM,aAAaE,iBAC7BhJ,EAAI,EAAGC,EAAOnD,KAAKiM,cAAc1K,OAAQ2B,EAAIC,EAAMD,YACpDiJ,EAAkBnM,KAAKiM,cAAc/I,GAAGgJ,iBACrCzI,EAAI,EAAG2I,EAAOD,EAAgB5K,OAAQkC,EAAI2I,EAAM3I,IACvDoI,EAAYvJ,KAAK6J,EAAgB1I,WAG9BoI,WAIEQ,wBACEC,EAAMrB,iBACZM,MAAMC,QAAQc,SACX,IAAItJ,MAAM,6DAKa,iBAAlBsJ,EAAK,GAAG,GAAG,KAAiBA,EAAO,CAACA,IAC/C,MAAOC,SAKJC,MAAQ,QACRnO,KAAO,CACVE,GAAI,CAAEC,EAAGS,OAAOwN,kBAAmB/N,EAAGO,OAAOwN,mBAC7ChO,GAAI,CAAED,EAAGS,OAAOyN,kBAAmBhO,EAAGO,OAAOyN,wBAE1C,IAAIxJ,EAAI,EAAGC,EAAOmJ,EAAK/K,OAAQ2B,EAAIC,EAAMD,IAAK,KAC3C6G,EAAO,IAAI+B,EAAOQ,EAAKpJ,GAAIlD,MAC7B+J,EAAK1L,KAAKE,GAAGC,EAAIwB,KAAK3B,KAAKE,GAAGC,IAAGwB,KAAK3B,KAAKE,GAAGC,EAAIuL,EAAK1L,KAAKE,GAAGC,GAC/DuL,EAAK1L,KAAKE,GAAGG,EAAIsB,KAAK3B,KAAKE,GAAGG,IAAGsB,KAAK3B,KAAKE,GAAGG,EAAIqL,EAAK1L,KAAKE,GAAGG,GAC/DqL,EAAK1L,KAAKI,GAAGD,EAAIwB,KAAK3B,KAAKI,GAAGD,IAAGwB,KAAK3B,KAAKI,GAAGD,EAAIuL,EAAK1L,KAAKI,GAAGD,GAC/DuL,EAAK1L,KAAKI,GAAGC,EAAIsB,KAAK3B,KAAKI,GAAGC,IAAGsB,KAAK3B,KAAKI,GAAGC,EAAIqL,EAAK1L,KAAKI,GAAGC,QAC9D8N,MAAMlK,KAAKyH,QAEbkB,UAAYA,6DAIXY,EAAc,GACX3I,EAAI,EAAGC,EAAOnD,KAAKwM,MAAMjL,OAAQ2B,EAAIC,EAAMD,YAC5CyJ,EAAkB3M,KAAKwM,MAAMtJ,GAAGgJ,iBAC7BzI,EAAI,EAAG2I,EAAOO,EAAgBpL,OAAQkC,EAAI2I,EAAM3I,IACvDoI,EAAYvJ,KAAKqK,EAAgBlJ,WAG9BoI,WC7HEe,wBAiFEvK,kBACNA,OAASA,MACT,IAAIa,EAAI,EAAGC,EAAOd,EAAOd,OAAQ2B,EAAIC,EAAMD,IAC9Cb,EAAOa,GAAGN,QAAQiB,QAAU7D,UAEzB+J,KAAO,oDAnFE8C,WACRC,EAAW,GAER5J,EAAI,EAAGC,EAAO0J,EAAYtL,OAAQ2B,EAAIC,EAAMD,IAAK,KAClDN,EAAUiK,EAAY3J,MACvBN,EAAQkB,eAAgBlB,EAAQiB,iBAEjCkJ,EAAY,KACZC,EAAQpK,EAAQoC,OAChBZ,EAAYxB,EAAQqC,QAClB5C,EAAS,CAAC2K,GAEVC,EAAgBD,EAAM1O,MACtB4O,EAAkB,GAItBH,EAAYC,EACZA,EAAQ5I,EACR/B,EAAOC,KAAK0K,GAGRA,EAAM1O,QAAU2O,UAEP,KACLE,EAAeH,EAAMI,8BAIC,IAAxBD,EAAa5L,OAAc,KACvB8L,EAAUhL,EAAO,GAAG/D,MACpBgP,EAASjL,EAAOA,EAAOd,OAAS,GAAGjD,YACnC,IAAI0E,MACR,sDAA+CqK,EAAQ7O,kBACjD6O,EAAQ3O,wDACP4O,EAAO9O,eAAM8O,EAAO5O,YAKH,IAAxByO,EAAa5L,OAAc,CAC7B6C,EAAY+I,EAAa,GAAGxJ,sBAK1B4J,EAAU,KACL9J,EAAI,EAAG2I,EAAOc,EAAgB3L,OAAQkC,EAAI2I,EAAM3I,OACnDyJ,EAAgBzJ,GAAGnF,QAAU0O,EAAM1O,MAAO,CAC5CiP,EAAU9J,WAKE,OAAZ8J,GAQJL,EAAgB5K,KAAK,CACnB0G,MAAO3G,EAAOd,OACdjD,MAAO0O,EAAM1O,YAGTkP,EAAaR,EAAMS,sBAAsBV,GAC/C3I,EAAY+I,EAAaO,KAAKF,GAAY,GAAG7J,kBAbrCgK,EAAiBT,EAAgBjD,OAAOsD,GAAS,GACjDK,EAAavL,EAAO4H,OAAO0D,EAAe3E,OAChD4E,EAAWC,QAAQD,EAAW,GAAGjK,SACjCmJ,EAASxK,KAAK,IAAIsK,EAAQgB,EAAWE,YAe3ChB,EAASxK,KAAK,IAAIsK,EAAQvK,YAErByK,mDAaHiB,EAAS/N,KAAKqC,OAAO,GAAG/D,MACtB0P,EAAS,CAACD,GACP7K,EAAI,EAAGC,EAAOnD,KAAKqC,OAAOd,OAAS,EAAG2B,EAAIC,EAAMD,IAAK,KACtDjB,EAAKjC,KAAKqC,OAAOa,GAAG5E,MACpB2P,EAASjO,KAAKqC,OAAOa,EAAI,GAAG5E,MACc,IAA5C0C,EAAoBiB,EAAI8L,EAAQE,KACpCD,EAAO1L,KAAKL,GACZ8L,EAAS9L,MAIW,IAAlB+L,EAAOzM,OAAc,OAAO,SAG1BU,EAAK+L,EAAO,GACZC,EAASD,EAAO,GAC0B,IAA5ChN,EAAoBiB,EAAI8L,EAAQE,IAAeD,EAAOE,QAE1DF,EAAO1L,KAAK0L,EAAO,YACbG,EAAOnO,KAAKoO,iBAAmB,GAAK,EACpCC,EAASrO,KAAKoO,iBAAmB,EAAIJ,EAAOzM,OAAS,EACrD+M,EAAOtO,KAAKoO,iBAAmBJ,EAAOzM,QAAU,EAChDgN,EAAgB,GACbrL,EAAImL,EAAQnL,GAAKoL,EAAMpL,GAAKiL,EAAMI,EAAcjM,KAAK,CAAC0L,EAAO9K,GAAG1E,EAAGwP,EAAO9K,GAAGxE,WAC/E6P,mDAIsBpP,IAAzBa,KAAKwO,gBAA+B,KAChCC,EAAYzO,KAAK0O,qBAClBF,iBAAkBC,IAAcA,EAAUL,wBAE1CpO,KAAKwO,oEAIgBrP,IAAxBa,KAAK2O,sBACFA,eAAiB3O,KAAK4O,sBAEtB5O,KAAK2O,oEAORE,EAAc7O,KAAKqC,OAAO,GACrBa,EAAI,EAAGC,EAAOnD,KAAKqC,OAAOd,OAAQ2B,EAAIC,EAAMD,IAAK,KAClDE,EAAMpD,KAAKqC,OAAOa,GACpBf,EAAWQ,QAAQkM,EAAazL,GAAO,IAAGyL,EAAczL,WAG1D0L,EAAUD,EAAYjM,QAAQuG,eAC9B4F,EAAcD,EAAUA,EAAQ3F,eAAiB,OAExC,KAEN2F,EAAS,OAAO,SAIhBC,EAAa,OAAOD,EAAQjL,WAK7BkL,EAAYlL,UAAYiL,EAAQjL,eAC9BkL,EAAYlL,QAAQ6K,kBAAoBI,EAAQjL,QAC3CiL,EAAQjL,QACHiL,EAAQjL,QAAQ6K,gBAKhCI,EAAUC,EAAY5F,eACtB4F,EAAcD,EAAUA,EAAQ3F,eAAiB,eAK1C6F,wBACEhD,kBACNA,aAAeA,EACpBA,EAAajC,KAAO/J,UACfiM,cAAgB,iDAGVnD,QACNmD,cAAc3J,KAAKwG,GACxBA,EAAKiB,KAAO/J,2CAINsM,EAAO,CAACtM,KAAKgM,aAAaiD,cAEhB,OAAZ3C,EAAK,GAAa,OAAO,SACxB,IAAIpJ,EAAI,EAAGC,EAAOnD,KAAKiM,cAAc1K,OAAQ2B,EAAIC,EAAMD,IAAK,KACzDgM,EAAWlP,KAAKiM,cAAc/I,GAAG+L,UAEtB,OAAbC,GACJ5C,EAAKhK,KAAK4M,UAEL5C,WAIE6C,wBACEjK,kBACNA,MAAQA,OACRsH,MAAQxM,KAAKoP,cAAclK,uDAI1BoH,EAAO,GACJpJ,EAAI,EAAGC,EAAOnD,KAAKwM,MAAMjL,OAAQ2B,EAAIC,EAAMD,IAAK,KACjDmM,EAAWrP,KAAKwM,MAAMtJ,GAAG+L,UAEd,OAAbI,GACJ/C,EAAKhK,KAAK+M,UAEL/C,wCAGMpH,WACPsH,EAAQ,GACLtJ,EAAI,EAAGC,EAAO+B,EAAM3D,OAAQ2B,EAAIC,EAAMD,IAAK,KAC5C4F,EAAO5D,EAAMhC,OACf4F,EAAKiB,QACLjB,EAAKsF,iBAAkB5B,EAAMlK,KAAK,IAAI0M,EAAQlG,QAC7C,KACG4F,EAAgB5F,EAAK4F,gBACtBA,EAAc3E,MAAMyC,EAAMlK,KAAK,IAAI0M,EAAQN,IAChDA,EAAc3E,KAAKuF,YAAYxG,WAG5B0D,WCtNU+C,wBACNC,OAAOhC,yDAAa9K,EAAQC,uBAClC6M,MAAQA,OACRtP,KAAO,IAAIC,EAAUqN,QACrB/B,SAAW,6CAGTuB,OACDpK,EAAUoK,EAAMpK,QAChBsF,EAAY,MAId8E,EAAMxJ,kBACJwJ,EAAM5K,OAAQpC,KAAKwP,MAAM9O,OAAOsM,EAAMrJ,SACrC3D,KAAKE,KAAKQ,OAAOkC,GACfsF,MAGH7H,EAAO2M,EAAM5K,OACfpC,KAAKE,KAAKuP,OAAO7M,GACjB5C,KAAKE,KAAKwP,KAAK9M,OAEbvC,EAAM,MAAM,IAAI2C,MACpB,kCAA2BJ,EAAQwC,mBAC/BxC,EAAQoC,OAAO1G,MAAME,eAAMoE,EAAQoC,OAAO1G,MAAMI,sBAChDkE,EAAQqC,QAAQ3G,MAAME,eAAMoE,EAAQqC,QAAQ3G,MAAMI,QACtD,0DAGE6B,EAAWF,EACXM,EAAWN,EACXyO,OAAU3P,EACVwQ,OAAUxQ,OAGKA,IAAZ2P,GAEY,QADjBvO,EAAWP,KAAKE,KAAKM,KAAKD,IACHuO,EAAU,UACI3P,IAA5BoB,EAASE,IAAI+C,aAA0BsL,EAAUvO,EAASE,eAIlDtB,IAAZwQ,GAEY,QADjBhP,EAAWX,KAAKE,KAAKU,KAAKD,IACHgP,EAAU,UACIxQ,IAA5BwB,EAASF,IAAI+C,aAA0BmM,EAAUhP,EAASF,QAGjEuM,EAAM5K,OAAQ,KAGZwN,EAAiB,QACjBd,EAAS,KACLe,EAAYf,EAAQgB,gBAAgBlN,MACxB,OAAdiN,IACGjN,EAAQ6D,aAAaoJ,KAAYD,EAAiBC,IAClDf,EAAQrI,aAAaoJ,YAClBE,EAAqB/P,KAAKgQ,aAAalB,EAASe,GAC7C3M,EAAI,EAAGC,EAAO4M,EAAmBxO,OAAQ2B,EAAIC,EAAMD,IAC1DgF,EAAU5F,KAAKyN,EAAmB7M,QAOtC+M,EAAiB,QACjBN,EAAS,KACLO,EAAYP,EAAQG,gBAAgBlN,MACxB,OAAdsN,IACGtN,EAAQ6D,aAAayJ,KAAYD,EAAiBC,IAClDP,EAAQlJ,aAAayJ,YAClBH,EAAqB/P,KAAKgQ,aAAaL,EAASO,GAC7ChN,EAAI,EAAGC,EAAO4M,EAAmBxO,OAAQ2B,EAAIC,EAAMD,IAC1DgF,EAAU5F,KAAKyN,EAAmB7M,OASnB,OAAnB0M,GAA8C,OAAnBK,EAAyB,KAElDE,EAAa,QACM,OAAnBP,EAAyBO,EAAaF,OACrC,GAAuB,OAAnBA,EAAyBE,EAAaP,MAC1C,CAEHO,EADqBhO,EAAWK,cAAcoN,EAAgBK,IACjC,EAAIL,EAAiBK,OAK/CT,MAAM9O,OAAOkC,EAAQqC,SAC1BiD,EAAU5F,KAAKM,EAAQqC,iBAEjB8K,EAAqBnN,EAAQwN,MAAMD,GAChCjN,EAAI,EAAGC,EAAO4M,EAAmBxO,OAAQ2B,EAAIC,EAAMD,IAC1DgF,EAAU5F,KAAKyN,EAAmB7M,IAIlCgF,EAAU3G,OAAS,QAIhBrB,KAAKQ,OAAOkC,GACjBsF,EAAU5F,KAAK0K,UAIVvB,SAASnJ,KAAKM,GACnBA,EAAQpC,KAAOsO,OAGZ,IAKDA,GAAWa,EAAS,KAChBU,EAAQvB,EAAQgB,gBAAgBH,MACxB,OAAVU,EAAgB,KACbvB,EAAQrI,aAAa4J,WAClBN,EAAqB/P,KAAKgQ,aAAalB,EAASuB,GAC7CnN,EAAI,EAAGC,EAAO4M,EAAmBxO,OAAQ2B,EAAIC,EAAMD,IAC1DgF,EAAU5F,KAAKyN,EAAmB7M,QAGjCyM,EAAQlJ,aAAa4J,WAClBN,EAAqB/P,KAAKgQ,aAAaL,EAASU,GAC7CnN,EAAI,EAAGC,EAAO4M,EAAmBxO,OAAQ2B,EAAIC,EAAMD,IAC1DgF,EAAU5F,KAAKyN,EAAmB7M,UAMrChD,KAAKQ,OAAOkC,UAGZsF,uCAKImB,EAAKpH,QAKX/B,KAAKQ,OAAO2I,OACXpE,EAAUoE,EAAIpE,aACfuK,MAAM9O,OAAOuE,OACZiD,EAAYmB,EAAI+G,MAAMnO,UAC5BiG,EAAU5F,KAAK2C,QAEQ9F,IAAnBkK,EAAI7F,YAA0BxD,KAAKE,KAAKuP,OAAOpG,GAC5CnB,WCvKLoI,EACgB,oBAAZC,SACNA,QAAQC,IAAIF,iCACd,IACIG,EACgB,oBAAZF,SACNA,QAAQC,IAAIC,yCACd,IAiHInG,EAAY,4EA9GXC,EAAM+B,EAAMoE,GACfpG,EAAUC,KAAOA,EACjB1J,EAAQjB,gBAGF+Q,EAAa,CAAC,IAAIC,EAAmBtE,GAAM,IACxCpJ,EAAI,EAAGC,EAAOuN,EAAUnP,OAAQ2B,EAAIC,EAAMD,IACjDyN,EAAWrO,KAAK,IAAIsO,EAAmBF,EAAUxN,IAAI,OAEvDoH,EAAUM,cAAgB+F,EAAWpP,OAMd,eAAnB+I,EAAUC,aAENsG,EAAUF,EAAW,GACvBzN,EAAI,EACDA,EAAIyN,EAAWpP,QACqC,OAArD5C,EAAegS,EAAWzN,GAAG7E,KAAMwS,EAAQxS,MAAgB6E,IAC1DyN,EAAW1G,OAAO/G,EAAG,MAOP,iBAAnBoH,EAAUC,SAGP,IAAIrH,EAAI,EAAGC,EAAOwN,EAAWpP,OAAQ2B,EAAIC,EAAMD,YAC5C4N,EAAMH,EAAWzN,GACdO,EAAIP,EAAI,EAAGkJ,EAAOuE,EAAWpP,OAAQkC,EAAI2I,EAAM3I,OACD,OAAjD9E,EAAemS,EAAIzS,KAAMsS,EAAWlN,GAAGpF,MAAgB,MAAO,WAMlEmR,EAAQ,IAAIrP,EAAUgC,EAAWQ,SAC9BO,EAAI,EAAGC,EAAOwN,EAAWpP,OAAQ2B,EAAIC,EAAMD,YAC5C2I,EAAc8E,EAAWzN,GAAGgJ,iBACzBzI,EAAI,EAAG2I,EAAOP,EAAYtK,OAAQkC,EAAI2I,EAAM3I,OACnD+L,EAAMC,OAAO5D,EAAYpI,IAErB+L,EAAMuB,KAAOT,QAET,IAAItN,MACR,4HAQFgO,EAAY,IAAIzB,EAAUC,GAC5ByB,EAAgBzB,EAAMuB,KACtB1Q,EAAOmP,EAAM0B,MACV7Q,GAAM,KACL+C,EAAM/C,EAAKI,OACb+O,EAAMuB,OAASE,EAAe,KAE1B5H,EAAMjG,EAAIR,cACV,IAAII,MACR,0BAAmBI,EAAIhB,OAAS,OAAS,mCACrCgB,EAAI9E,MAAME,eAAM4E,EAAI9E,MAAMI,6BAAoB2K,EAAIjE,mBAClDiE,EAAIrE,OAAO1G,MAAME,eAAM6K,EAAIrE,OAAO1G,MAAMI,sBACxC2K,EAAIpE,QAAQ3G,MAAME,eAAM6K,EAAIpE,QAAQ3G,MAAMI,oBAC9C,gCAIA8Q,EAAMuB,KAAOT,QAET,IAAItN,MACR,2GAKAgO,EAAUvF,SAASlK,OAASkP,QAExB,IAAIzN,MACR,0HAKEkF,EAAY8I,EAAUT,QAAQnN,GAC3BF,EAAI,EAAGC,EAAO+E,EAAU3G,OAAQ2B,EAAIC,EAAMD,IAAK,KAChDE,EAAM8E,EAAUhF,QACC/D,IAAnBiE,EAAII,YAA0BgM,EAAMC,OAAOrM,GAEjD6N,EAAgBzB,EAAMuB,KACtB1Q,EAAOmP,EAAM0B,MAIfrQ,EAAQjB,YAGFkN,EAAWqE,EAAgBC,QAAQJ,EAAUvF,iBACpC,IAAI0F,EAAqBrE,GAC1BmC,0BC9GH,CACboC,MAbY,SAAC/E,8BAASoE,mCAAAA,2BACtBpG,EAAUgH,IAAI,QAAShF,EAAMoE,IAa7BzI,aAXmB,SAACqE,8BAASoE,mCAAAA,2BAC7BpG,EAAUgH,IAAI,eAAgBhF,EAAMoE,IAWpCa,IATU,SAACjF,8BAASoE,mCAAAA,2BACpBpG,EAAUgH,IAAI,MAAOhF,EAAMoE,IAS3Bc,WAPiB,SAACC,8BAAgBC,mCAAAA,2BAClCpH,EAAUgH,IAAI,aAAcG,EAAaC"}