{"version":3,"file":"order-by-x.cjs","sources":["../../../../components/data-view/utils/order-by-x.tsx"],"sourcesContent":["/** Anything placed on the timeline's x axis. */\nexport interface XPositioned {\n  x: number;\n}\n\n/**\n * Below this the counting sort's setup (three passes plus two typed arrays)\n * costs more than a comparison sort. `packLanes` runs per group section, so\n * most calls are small.\n */\nconst BUCKET_SORT_MIN_ITEMS = 64;\n\n/**\n * A bucket deeper than this would drag insertion sort towards O(m²) (thousands\n * of cards landing in one pixel column), so it hands off to a comparison sort\n * instead — bounding the pathological case at O(n log n).\n */\nconst INSERTION_SORT_MAX_BUCKET = 32;\n\n/**\n * Item indices ordered ascending by `x`, ties broken by input order.\n *\n * Counting sort over uniform x buckets. `x` is affine in time, so cards spread\n * near-uniformly across the domain and buckets stay ~1 deep — O(n) at the\n * sizes that matter, where a comparison sort is O(n log n). Clustered input\n * degrades gracefully rather than falling off a cliff (see the two constants\n * above).\n *\n * Returns indices rather than sorted items so callers can reuse one ordering\n * for several parallel arrays without copying the items themselves.\n */\nexport function orderByX(items: readonly XPositioned[]): Int32Array {\n  const n = items.length;\n  const order = new Int32Array(n);\n  if (n === 0) return order;\n\n  if (n < BUCKET_SORT_MIN_ITEMS) {\n    const plain = new Array<number>(n);\n    for (let i = 0; i < n; i++) plain[i] = i;\n    plain.sort((a, b) => items[a].x - items[b].x || a - b);\n    order.set(plain);\n    return order;\n  }\n\n  let minX = Infinity;\n  let maxX = -Infinity;\n  for (let i = 0; i < n; i++) {\n    const { x } = items[i];\n    if (x < minX) minX = x;\n    if (x > maxX) maxX = x;\n  }\n\n  const span = maxX - minX;\n  // Every item at the same x (or a non-finite extent): input order already is\n  // the tie-break order.\n  if (!(span > 0)) {\n    for (let i = 0; i < n; i++) order[i] = i;\n    return order;\n  }\n\n  // One bucket per item — the density that keeps buckets ~1 deep.\n  const bucketCount = n;\n  const scale = bucketCount / span;\n  const bucketOf = new Int32Array(n);\n  // `starts` is counts shifted by one, prefix-summed in place: after the sum,\n  // starts[b] is bucket b's first slot and starts[b + 1] its end.\n  const starts = new Int32Array(bucketCount + 1);\n  for (let i = 0; i < n; i++) {\n    let bucket = Math.floor((items[i].x - minX) * scale);\n    // Negated rather than `bucket < 0` so a NaN lands in bucket 0 too. `x` is\n    // finite in practice, but an unguarded NaN corrupts the whole ordering\n    // rather than misplacing one item: `bucketOf` is an Int32Array, so NaN\n    // stores as 0, while `starts[NaN + 1]++` is a silent no-op on a typed\n    // array. Bucket 0 then receives an item it never reserved a slot for and\n    // the scatter overwrites its neighbour — one index duplicated, one lost,\n    // which downstream means one card packed twice and another left unplaced.\n    if (!(bucket >= 0)) bucket = 0;\n    else if (bucket >= bucketCount) bucket = bucketCount - 1;\n    bucketOf[i] = bucket;\n    starts[bucket + 1]++;\n  }\n  for (let bucket = 0; bucket < bucketCount; bucket++) {\n    starts[bucket + 1] += starts[bucket];\n  }\n\n  // Stable scatter — within a bucket, items stay in input order, which is the\n  // tie-break the comparison path applies for equal x.\n  const cursor = Int32Array.from(starts.subarray(0, bucketCount));\n  for (let i = 0; i < n; i++) order[cursor[bucketOf[i]]++] = i;\n\n  for (let bucket = 0; bucket < bucketCount; bucket++) {\n    const from = starts[bucket];\n    const to = starts[bucket + 1];\n    const size = to - from;\n    if (size < 2) continue;\n    if (size <= INSERTION_SORT_MAX_BUCKET) {\n      // Insertion sort with a strict `>` shift is stable, so equal-x items\n      // keep the input order the scatter gave them.\n      for (let i = from + 1; i < to; i++) {\n        const index = order[i];\n        const { x } = items[index];\n        let j = i - 1;\n        while (j >= from && items[order[j]].x > x) {\n          order[j + 1] = order[j];\n          j--;\n        }\n        order[j + 1] = index;\n      }\n    } else {\n      const slice = Array.from(order.subarray(from, to));\n      slice.sort((a, b) => items[a].x - items[b].x || a - b);\n      order.set(slice, from);\n    }\n  }\n\n  return order;\n}\n"],"names":[],"mappings":";;AAKA;;;;AAIG;AACH,MAAM,qBAAqB,GAAG,EAAE,CAAC;AAEjC;;;;AAIG;AACH,MAAM,yBAAyB,GAAG,EAAE,CAAC;AAErC;;;;;;;;;;;AAWG;AACG,SAAU,QAAQ,CAAC,KAA6B,EAAA;AACpD,IAAA,MAAM,CAAC,GAAG,KAAK,CAAC,MAAM,CAAC;AACvB,IAAA,MAAM,KAAK,GAAG,IAAI,UAAU,CAAC,CAAC,CAAC,CAAC;IAChC,IAAI,CAAC,KAAK,CAAC;AAAE,QAAA,OAAO,KAAK,CAAC;AAE1B,IAAA,IAAI,CAAC,GAAG,qBAAqB,EAAE;AAC7B,QAAA,MAAM,KAAK,GAAG,IAAI,KAAK,CAAS,CAAC,CAAC,CAAC;QACnC,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,CAAC,EAAE;AAAE,YAAA,KAAK,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC;AACzC,QAAA,KAAK,CAAC,IAAI,CAAC,CAAC,CAAC,EAAE,CAAC,KAAK,KAAK,CAAC,CAAC,CAAC,CAAC,CAAC,GAAG,KAAK,CAAC,CAAC,CAAC,CAAC,CAAC,IAAI,CAAC,GAAG,CAAC,CAAC,CAAC;AACvD,QAAA,KAAK,CAAC,GAAG,CAAC,KAAK,CAAC,CAAC;AACjB,QAAA,OAAO,KAAK,CAAC;KACd;IAED,IAAI,IAAI,GAAG,QAAQ,CAAC;AACpB,IAAA,IAAI,IAAI,GAAG,CAAC,QAAQ,CAAC;AACrB,IAAA,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,CAAC,EAAE,EAAE;QAC1B,MAAM,EAAE,CAAC,EAAE,GAAG,KAAK,CAAC,CAAC,CAAC,CAAC;QACvB,IAAI,CAAC,GAAG,IAAI;YAAE,IAAI,GAAG,CAAC,CAAC;QACvB,IAAI,CAAC,GAAG,IAAI;YAAE,IAAI,GAAG,CAAC,CAAC;KACxB;AAED,IAAA,MAAM,IAAI,GAAG,IAAI,GAAG,IAAI,CAAC;;;AAGzB,IAAA,IAAI,EAAE,IAAI,GAAG,CAAC,CAAC,EAAE;QACf,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,CAAC,EAAE;AAAE,YAAA,KAAK,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC;AACzC,QAAA,OAAO,KAAK,CAAC;KACd;;IAGD,MAAM,WAAW,GAAG,CAAC,CAAC;AACtB,IAAA,MAAM,KAAK,GAAG,WAAW,GAAG,IAAI,CAAC;AACjC,IAAA,MAAM,QAAQ,GAAG,IAAI,UAAU,CAAC,CAAC,CAAC,CAAC;;;IAGnC,MAAM,MAAM,GAAG,IAAI,UAAU,CAAC,WAAW,GAAG,CAAC,CAAC,CAAC;AAC/C,IAAA,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,CAAC,EAAE,EAAE;AAC1B,QAAA,IAAI,MAAM,GAAG,IAAI,CAAC,KAAK,CAAC,CAAC,KAAK,CAAC,CAAC,CAAC,CAAC,CAAC,GAAG,IAAI,IAAI,KAAK,CAAC,CAAC;;;;;;;;AAQrD,QAAA,IAAI,EAAE,MAAM,IAAI,CAAC,CAAC;YAAE,MAAM,GAAG,CAAC,CAAC;aAC1B,IAAI,MAAM,IAAI,WAAW;AAAE,YAAA,MAAM,GAAG,WAAW,GAAG,CAAC,CAAC;AACzD,QAAA,QAAQ,CAAC,CAAC,CAAC,GAAG,MAAM,CAAC;AACrB,QAAA,MAAM,CAAC,MAAM,GAAG,CAAC,CAAC,EAAE,CAAC;KACtB;AACD,IAAA,KAAK,IAAI,MAAM,GAAG,CAAC,EAAE,MAAM,GAAG,WAAW,EAAE,MAAM,EAAE,EAAE;QACnD,MAAM,CAAC,MAAM,GAAG,CAAC,CAAC,IAAI,MAAM,CAAC,MAAM,CAAC,CAAC;KACtC;;;AAID,IAAA,MAAM,MAAM,GAAG,UAAU,CAAC,IAAI,CAAC,MAAM,CAAC,QAAQ,CAAC,CAAC,EAAE,WAAW,CAAC,CAAC,CAAC;IAChE,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,CAAC,EAAE;AAAE,QAAA,KAAK,CAAC,MAAM,CAAC,QAAQ,CAAC,CAAC,CAAC,CAAC,EAAE,CAAC,GAAG,CAAC,CAAC;AAE7D,IAAA,KAAK,IAAI,MAAM,GAAG,CAAC,EAAE,MAAM,GAAG,WAAW,EAAE,MAAM,EAAE,EAAE;AACnD,QAAA,MAAM,IAAI,GAAG,MAAM,CAAC,MAAM,CAAC,CAAC;QAC5B,MAAM,EAAE,GAAG,MAAM,CAAC,MAAM,GAAG,CAAC,CAAC,CAAC;AAC9B,QAAA,MAAM,IAAI,GAAG,EAAE,GAAG,IAAI,CAAC;QACvB,IAAI,IAAI,GAAG,CAAC;YAAE,SAAS;AACvB,QAAA,IAAI,IAAI,IAAI,yBAAyB,EAAE;;;AAGrC,YAAA,KAAK,IAAI,CAAC,GAAG,IAAI,GAAG,CAAC,EAAE,CAAC,GAAG,EAAE,EAAE,CAAC,EAAE,EAAE;AAClC,gBAAA,MAAM,KAAK,GAAG,KAAK,CAAC,CAAC,CAAC,CAAC;gBACvB,MAAM,EAAE,CAAC,EAAE,GAAG,KAAK,CAAC,KAAK,CAAC,CAAC;AAC3B,gBAAA,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,CAAC;AACd,gBAAA,OAAO,CAAC,IAAI,IAAI,IAAI,KAAK,CAAC,KAAK,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC,EAAE;oBACzC,KAAK,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,KAAK,CAAC,CAAC,CAAC,CAAC;AACxB,oBAAA,CAAC,EAAE,CAAC;iBACL;AACD,gBAAA,KAAK,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,KAAK,CAAC;aACtB;SACF;aAAM;AACL,YAAA,MAAM,KAAK,GAAG,KAAK,CAAC,IAAI,CAAC,KAAK,CAAC,QAAQ,CAAC,IAAI,EAAE,EAAE,CAAC,CAAC,CAAC;AACnD,YAAA,KAAK,CAAC,IAAI,CAAC,CAAC,CAAC,EAAE,CAAC,KAAK,KAAK,CAAC,CAAC,CAAC,CAAC,CAAC,GAAG,KAAK,CAAC,CAAC,CAAC,CAAC,CAAC,IAAI,CAAC,GAAG,CAAC,CAAC,CAAC;AACvD,YAAA,KAAK,CAAC,GAAG,CAAC,KAAK,EAAE,IAAI,CAAC,CAAC;SACxB;KACF;AAED,IAAA,OAAO,KAAK,CAAC;AACf;;;;"}