{"version":3,"sources":["../src/utils.ts","../src/heapify.ts","../src/heapPop.ts","../src/heapPush.ts","../src/heapPushPop.ts","../src/heapReplace.ts","../src/merge.ts","../src/nLargest.ts","../src/nSmallest.ts"],"names":["_defaultMinHeapComparator","a","b","_getLeftChildIndex","index","_getRightChildIndex","_getParentIndex","_siftDown","heap","cmp","length","value","left","smallest","right","_siftUp","parentIndex","_swapIndicesInPlace","indexOne","indexTwo","heapify","options","i","heapPop","heapPush","heapPushPop","returnValue","heapReplace","merge","iterables","sourceIndex","iterator","result","entry","nextResult","nLargest","iterable","n","size","item","heapTop","nSmallest"],"mappings":"aAEO,SAASA,EAA6BC,CAAAA,CAAMC,CAAAA,CAAe,CAC9D,OAAOD,CAAAA,CAAIC,CACf,CAEO,SAASC,EAAmBC,CAAAA,CAAuB,CACtD,QAAQA,CAAAA,EAAS,CAAA,EAAK,CAC1B,CAEO,SAASC,EAAoBD,CAAAA,CAAuB,CACvD,OAAA,CAAQA,CAAAA,EAAS,GAAK,CAC1B,CAEO,SAASE,CAAAA,CAAgBF,CAAAA,CAAuB,CACnD,OAAQA,CAAAA,CAAQ,GAAM,CAC1B,CAEO,SAASG,CAAAA,CACZC,CAAAA,CACAJ,EACAK,CAAAA,CACI,CACJ,IAAMC,CAAAA,CAASF,CAAAA,CAAK,MAAA,CACdG,CAAAA,CAAQH,EAAKJ,CAAK,CAAA,CAExB,OAAa,CACT,IAAMQ,EAAOT,CAAAA,CAAmBC,CAAK,EACrC,GAAIQ,CAAAA,EAAQF,EACR,MAGJ,IAAIG,EAAWD,CAAAA,CACTE,CAAAA,CAAQT,EAAoBD,CAAK,CAAA,CAMvC,GAJIU,CAAAA,CAAQJ,GAAUD,CAAAA,CAAID,CAAAA,CAAKM,CAAK,CAAA,CAAIN,CAAAA,CAAKI,CAAI,CAAE,CAAA,GAC/CC,EAAWC,CAAAA,CAAAA,CAGX,CAACL,EAAID,CAAAA,CAAKK,CAAQ,EAAIF,CAAM,CAAA,CAC5B,MAGJH,CAAAA,CAAKJ,CAAK,CAAA,CAAKI,CAAAA,CAAKK,CAAQ,CAAA,CAC5BT,CAAAA,CAAQS,EACZ,CAEAL,CAAAA,CAAKJ,CAAK,CAAA,CAAKO,EACnB,CAEO,SAASI,CAAAA,CAAWP,EAAWJ,CAAAA,CAAeK,CAAAA,CAA0B,CAC3E,KAAOL,CAAAA,CAAQ,GAAG,CACd,IAAMY,CAAAA,CAAcV,CAAAA,CAAgBF,CAAK,CAAA,CAEzC,GAAIK,EAAID,CAAAA,CAAKQ,CAAW,EAAIR,CAAAA,CAAKJ,CAAK,CAAE,CAAA,CACpC,MAGJa,EAAoBT,CAAAA,CAAMJ,CAAAA,CAAOY,CAAW,CAAA,CAC5CZ,CAAAA,CAAQY,EACZ,CACJ,CAEO,SAASC,CAAAA,CACZT,EACAU,CAAAA,CACAC,CAAAA,CACI,CACJ,CAACX,CAAAA,CAAKU,CAAQ,CAAA,CAAIV,CAAAA,CAAKW,CAAQ,CAAE,CAAA,CAAI,CAACX,CAAAA,CAAKW,CAAQ,EAAIX,CAAAA,CAAKU,CAAQ,CAAE,EAC1E,CCjEO,SAASE,CAAAA,CAAWZ,CAAAA,CAAWa,EAA2B,CAC7D,IAAMZ,EAAMY,CAAAA,EAAS,UAAA,EAAcrB,EAEnC,IAAA,IAASsB,CAAAA,CAAAA,CAAKd,EAAK,MAAA,EAAU,CAAA,EAAK,EAAGc,CAAAA,EAAK,CAAA,CAAGA,IACzCf,CAAAA,CAAUC,CAAAA,CAAMc,EAAGb,CAAG,CAAA,CAG1B,OAAOD,CACX,CCRO,SAASe,CAAAA,CAAWf,EAAWa,CAAAA,CAAgC,CAClE,GAAIb,CAAAA,CAAK,MAAA,GAAW,EAChB,OAEJ,GAAIA,EAAK,MAAA,GAAW,CAAA,CAChB,OAAOA,CAAAA,CAAK,GAAA,GAGhB,IAAMC,CAAAA,CAAMY,CAAAA,EAAS,UAAA,EAAcrB,EAE7BW,CAAAA,CAAQH,CAAAA,CAAK,CAAC,CAAA,CACpB,OAAAA,EAAK,CAAC,CAAA,CAAKA,EAAKA,CAAAA,CAAK,MAAA,CAAS,CAAC,CAAA,CAC/BA,CAAAA,CAAK,KAAI,CACTD,CAAAA,CAAUC,EAAM,CAAA,CAAGC,CAAG,CAAA,CAEfE,CACX,CChBO,SAASa,CAAAA,CAAYhB,EAAWG,CAAAA,CAAUU,CAAAA,CAA2B,CACxE,IAAMZ,CAAAA,CAAMY,GAAS,UAAA,EAAcrB,CAAAA,CAEnC,OAAAQ,CAAAA,CAAK,IAAA,CAAKG,CAAK,CAAA,CACfI,CAAAA,CAAQP,EAAMA,CAAAA,CAAK,MAAA,CAAS,EAAGC,CAAG,CAAA,CAE3BD,CACX,CCPO,SAASiB,EACZjB,CAAAA,CACAG,CAAAA,CACAU,EACQ,CACR,IAAMZ,EAAMY,CAAAA,EAAS,UAAA,EAAcrB,EAEnC,GAAIQ,CAAAA,CAAK,OAAS,CAAA,EAAKC,CAAAA,CAAID,EAAK,CAAC,CAAA,CAAIG,CAAK,CAAA,CAAG,CACzC,IAAMe,CAAAA,CAAclB,EAAK,CAAC,CAAA,CAC1B,OAAAA,CAAAA,CAAK,CAAC,EAAIG,CAAAA,CACVJ,CAAAA,CAAUC,EAAM,CAAA,CAAGC,CAAG,EAEfiB,CACX,CAEA,OAAOf,CACX,CCfO,SAASgB,CAAAA,CACZnB,EACAG,CAAAA,CACAU,CAAAA,CACQ,CACR,IAAMZ,CAAAA,CAAMY,GAAS,UAAA,EAAcrB,CAAAA,CAEnC,GAAIQ,CAAAA,CAAK,MAAA,GAAW,EAAG,CACnBgB,CAAAA,CAAShB,EAAMG,CAAAA,CAAOU,CAAO,EAC7B,MACJ,CAEA,IAAMK,CAAAA,CAAclB,EAAK,CAAC,CAAA,CAC1B,OAAAA,CAAAA,CAAK,CAAC,EAAIG,CAAAA,CACVJ,CAAAA,CAAUC,EAAM,CAAA,CAAGC,CAAG,EAEfiB,CACX,CCVO,SAAUE,CAAAA,CACbC,CAAAA,CACAR,EAC6B,CAC7B,IAAMZ,EAAMY,CAAAA,EAAS,UAAA,EAAcrB,EAC7BQ,CAAAA,CAAuB,GAE7B,IAAA,IAASsB,CAAAA,CAAc,EAAGA,CAAAA,CAAcD,CAAAA,CAAU,OAAQC,CAAAA,EAAAA,CAAe,CACrE,IAAMC,CAAAA,CAAWF,CAAAA,CAAUC,CAAW,CAAA,CAAG,MAAA,CAAO,QAAQ,CAAA,EAAE,CACpDE,CAAAA,CAASD,CAAAA,CAAS,MAAK,CAExBC,CAAAA,CAAO,MACRxB,CAAAA,CAAK,IAAA,CAAK,CACN,KAAA,CAAOwB,CAAAA,CAAO,MACd,WAAA,CAAAF,CAAAA,CACA,SAAAC,CACJ,CAAC,EAET,CAIA,IAFAX,EAAQZ,CAAAA,CAAM,CAAE,UAAA,CAAY,CAACP,EAAGC,CAAAA,GAAMO,CAAAA,CAAIR,EAAE,KAAA,CAAOC,CAAAA,CAAE,KAAK,CAAE,CAAC,EAEtDM,CAAAA,CAAK,MAAA,CAAS,GAAG,CACpB,GAAIA,EAAK,MAAA,GAAW,CAAA,CAAG,CACnB,IAAMyB,CAAAA,CAAQzB,CAAAA,CAAK,CAAC,EACpB,MAAMyB,CAAAA,CAAM,MAEZ,IAAID,CAAAA,CAASC,EAAM,QAAA,CAAS,IAAA,GAC5B,KAAO,CAACD,EAAO,IAAA,EACX,MAAMA,EAAO,KAAA,CACbA,CAAAA,CAASC,EAAM,QAAA,CAAS,IAAA,EAAK,CAEjC,KACJ,CAEA,IAAMpB,CAAAA,CAAWU,EAAQf,CAAAA,CAAM,CAC3B,WAAY,CAACP,CAAAA,CAAGC,IAAMO,CAAAA,CAAIR,CAAAA,CAAE,MAAOC,CAAAA,CAAE,KAAK,CAC9C,CAAC,CAAA,CAED,GAAIW,CAAAA,GAAa,MAAA,CACb,MAGJ,MAAMA,EAAS,KAAA,CAEf,IAAMqB,EAAarB,CAAAA,CAAS,QAAA,CAAS,MAAK,CAErCqB,CAAAA,CAAW,OACZ1B,CAAAA,CAAK,IAAA,CAAK,CACN,KAAA,CAAO0B,CAAAA,CAAW,MAClB,WAAA,CAAarB,CAAAA,CAAS,YACtB,QAAA,CAAUA,CAAAA,CAAS,QACvB,CAAC,EACDO,CAAAA,CAAQZ,CAAAA,CAAM,CAAE,UAAA,CAAY,CAACP,EAAGC,CAAAA,GAAMO,CAAAA,CAAIR,EAAE,KAAA,CAAOC,CAAAA,CAAE,KAAK,CAAE,CAAC,GAErE,CACJ,CC/DO,SAASiC,CAAAA,CACZC,CAAAA,CACAC,CAAAA,CACAhB,CAAAA,CACG,CACH,IAAMiB,CAAAA,CAAOF,EAAS,MAAA,CAChB3B,CAAAA,CAAMY,GAAS,UAAA,EAAcrB,CAAAA,CAEnC,GAAIqC,CAAAA,EAAK,CAAA,CACL,OAAO,EAAC,CAGZ,GAAIA,CAAAA,EAAKC,CAAAA,CAAM,CACX,IAAMN,CAAAA,CAASI,EAAS,KAAA,EAAM,CAC9B,OAAAJ,CAAAA,CAAO,IAAA,CAAK,CAAC/B,CAAAA,CAAGC,CAAAA,GACRO,EAAIR,CAAAA,CAAGC,CAAC,EAAU,CAAA,CAClBO,CAAAA,CAAIP,EAAGD,CAAC,CAAA,CAAU,GACf,CACV,CAAA,CACM+B,CACX,CAEA,IAAMxB,CAAAA,CAAY4B,CAAAA,CAAS,MAAM,CAAA,CAAGC,CAAC,EACrCjB,CAAAA,CAAQZ,CAAAA,CAAM,CAAE,UAAA,CAAYC,CAAI,CAAC,CAAA,CAEjC,IAAA,IAASa,EAAIe,CAAAA,CAAGf,CAAAA,CAAIgB,EAAMhB,CAAAA,EAAAA,CAAK,CAC3B,IAAMiB,CAAAA,CAAOH,CAAAA,CAASd,CAAC,CAAA,CACjBkB,EAAUhC,CAAAA,CAAK,CAAC,EAEjBC,CAAAA,CAAI8B,CAAAA,CAAMC,CAAO,CAAA,EAClBb,CAAAA,CAAYnB,EAAM+B,CAAAA,CAAM,CAAE,WAAY9B,CAAI,CAAC,EAEnD,CAEA,OAAAD,EAAK,IAAA,CAAK,CAACP,CAAAA,CAAGC,CAAAA,GACNO,EAAIR,CAAAA,CAAGC,CAAC,EAAU,CAAA,CAClBO,CAAAA,CAAIP,EAAGD,CAAC,CAAA,CAAU,GACf,CACV,CAAA,CAEMO,CACX,CCzCO,SAASiC,EACZL,CAAAA,CACAC,CAAAA,CACAhB,EACG,CACH,IAAMiB,EAAOF,CAAAA,CAAS,MAAA,CAChB3B,EAAM,CAACR,CAAAA,CAAMC,IACXmB,CAAAA,EAAS,UAAA,CACFA,EAAQ,UAAA,CAAWpB,CAAAA,CAAGC,CAAC,CAAA,CAG3B,CAACF,EAA6BC,CAAAA,CAAGC,CAAC,EAG7C,GAAImC,CAAAA,EAAK,EACL,OAAO,EAAC,CAGZ,GAAIA,GAAKC,CAAAA,CAAM,CACX,IAAMN,CAAAA,CAASI,CAAAA,CAAS,OAAM,CAC9B,OAAAJ,EAAO,IAAA,CAAK,CAAC/B,EAAGC,CAAAA,GACRO,CAAAA,CAAIR,EAAGC,CAAC,CAAA,CAAU,EAClBO,CAAAA,CAAIP,CAAAA,CAAGD,CAAC,CAAA,CAAU,GACf,CACV,CAAA,CACM+B,CACX,CAEA,IAAMxB,EAAY4B,CAAAA,CAAS,KAAA,CAAM,EAAGC,CAAC,CAAA,CACrCjB,EAAQZ,CAAAA,CAAM,CAAE,WAAYC,CAAI,CAAC,EAEjC,IAAA,IAASa,CAAAA,CAAIe,CAAAA,CAAGf,CAAAA,CAAIgB,EAAMhB,CAAAA,EAAAA,CAAK,CAC3B,IAAMiB,CAAAA,CAAOH,CAAAA,CAASd,CAAC,CAAA,CACjBkB,CAAAA,CAAUhC,EAAK,CAAC,CAAA,CAEjBC,EAAI8B,CAAAA,CAAMC,CAAO,GAClBb,CAAAA,CAAYnB,CAAAA,CAAM+B,EAAM,CAAE,UAAA,CAAY9B,CAAI,CAAC,EAEnD,CAEA,OAAAD,CAAAA,CAAK,KAAK,CAACP,CAAAA,CAAGC,IACNO,CAAAA,CAAIR,CAAAA,CAAGC,CAAC,CAAA,CAAU,CAAA,CAClBO,EAAIP,CAAAA,CAAGD,CAAC,EAAU,EAAA,CACf,CACV,EAEMO,CACX","file":"index.cjs","sourcesContent":["import type { Comparator } from \"./types\";\n\nexport function _defaultMinHeapComparator<T>(a: T, b: T): boolean {\n    return a < b;\n}\n\nexport function _getLeftChildIndex(index: number): number {\n    return (index << 1) + 1;\n}\n\nexport function _getRightChildIndex(index: number): number {\n    return (index << 1) + 2;\n}\n\nexport function _getParentIndex(index: number): number {\n    return (index - 1) >> 1;\n}\n\nexport function _siftDown<T>(\n    heap: T[],\n    index: number,\n    cmp: Comparator<T>,\n): void {\n    const length = heap.length;\n    const value = heap[index];\n\n    while (true) {\n        const left = _getLeftChildIndex(index);\n        if (left >= length) {\n            break;\n        }\n\n        let smallest = left;\n        const right = _getRightChildIndex(index);\n\n        if (right < length && cmp(heap[right]!, heap[left]!)) {\n            smallest = right;\n        }\n\n        if (!cmp(heap[smallest]!, value!)) {\n            break;\n        }\n\n        heap[index]! = heap[smallest]!;\n        index = smallest;\n    }\n\n    heap[index]! = value!;\n}\n\nexport function _siftUp<T>(heap: T[], index: number, cmp: Comparator<T>): void {\n    while (index > 0) {\n        const parentIndex = _getParentIndex(index);\n\n        if (cmp(heap[parentIndex]!, heap[index]!)) {\n            break;\n        }\n\n        _swapIndicesInPlace(heap, index, parentIndex);\n        index = parentIndex;\n    }\n}\n\nexport function _swapIndicesInPlace<T>(\n    heap: T[],\n    indexOne: number,\n    indexTwo: number,\n): void {\n    [heap[indexOne]!, heap[indexTwo]!] = [heap[indexTwo]!, heap[indexOne]!];\n}\n","import { _defaultMinHeapComparator, _siftDown } from \"./utils\";\n\nimport type { Options } from \"./types\";\n\nexport function heapify<T>(heap: T[], options?: Options<T>): T[] {\n    const cmp = options?.comparator ?? _defaultMinHeapComparator<T>;\n\n    for (let i = (heap.length >> 1) - 1; i >= 0; i--) {\n        _siftDown(heap, i, cmp);\n    }\n\n    return heap;\n}\n","import { _defaultMinHeapComparator, _siftDown } from \"./utils\";\n\nimport type { Options } from \"./types\";\n\nexport function heapPop<T>(heap: T[], options?: Options<T>): T | void {\n    if (heap.length === 0) {\n        return;\n    }\n    if (heap.length === 1) {\n        return heap.pop();\n    }\n\n    const cmp = options?.comparator ?? _defaultMinHeapComparator<T>;\n\n    const value = heap[0]!;\n    heap[0]! = heap[heap.length - 1]!;\n    heap.pop();\n    _siftDown(heap, 0, cmp);\n\n    return value;\n}\n","import { _defaultMinHeapComparator, _siftUp } from \"./utils\";\n\nimport type { Options } from \"./types\";\n\nexport function heapPush<T>(heap: T[], value: T, options?: Options<T>): T[] {\n    const cmp = options?.comparator ?? _defaultMinHeapComparator<T>;\n\n    heap.push(value);\n    _siftUp(heap, heap.length - 1, cmp);\n\n    return heap;\n}\n","import { _defaultMinHeapComparator, _siftDown } from \"./utils\";\n\nimport type { Options } from \"./types\";\n\nexport function heapPushPop<T>(\n    heap: T[],\n    value: T,\n    options?: Options<T>,\n): T | void {\n    const cmp = options?.comparator ?? _defaultMinHeapComparator<T>;\n\n    if (heap.length > 0 && cmp(heap[0]!, value)) {\n        const returnValue = heap[0];\n        heap[0] = value;\n        _siftDown(heap, 0, cmp);\n\n        return returnValue!;\n    }\n\n    return value;\n}\n","import { _defaultMinHeapComparator, _siftDown } from \"./utils\";\nimport { heapPush } from \"./heapPush\";\n\nimport type { Options } from \"./types\";\n\nexport function heapReplace<T>(\n    heap: T[],\n    value: T,\n    options?: Options<T>,\n): T | void {\n    const cmp = options?.comparator ?? _defaultMinHeapComparator<T>;\n\n    if (heap.length === 0) {\n        heapPush(heap, value, options);\n        return;\n    }\n\n    const returnValue = heap[0];\n    heap[0] = value;\n    _siftDown(heap, 0, cmp);\n\n    return returnValue;\n}\n","import { heapPop } from \"./heapPop\";\nimport { heapify } from \"./heapify\";\nimport { _defaultMinHeapComparator } from \"./utils\";\n\nimport type { Options } from \"./types\";\n\ntype HeapEntry<T> = {\n    value: T;\n    sourceIndex: number;\n    iterator: Iterator<T>;\n};\n\nexport function* merge<T>(\n    iterables: Iterable<T>[],\n    options?: Options<T>,\n): Generator<T, void, undefined> {\n    const cmp = options?.comparator ?? _defaultMinHeapComparator<T>;\n    const heap: HeapEntry<T>[] = [];\n\n    for (let sourceIndex = 0; sourceIndex < iterables.length; sourceIndex++) {\n        const iterator = iterables[sourceIndex]![Symbol.iterator]();\n        const result = iterator.next();\n\n        if (!result.done) {\n            heap.push({\n                value: result.value,\n                sourceIndex,\n                iterator,\n            });\n        }\n    }\n\n    heapify(heap, { comparator: (a, b) => cmp(a.value, b.value) });\n\n    while (heap.length > 0) {\n        if (heap.length === 1) {\n            const entry = heap[0]!;\n            yield entry.value;\n\n            let result = entry.iterator.next();\n            while (!result.done) {\n                yield result.value;\n                result = entry.iterator.next();\n            }\n            break;\n        }\n\n        const smallest = heapPop(heap, {\n            comparator: (a, b) => cmp(a.value, b.value),\n        });\n\n        if (smallest === undefined) {\n            break;\n        }\n\n        yield smallest.value;\n\n        const nextResult = smallest.iterator.next();\n\n        if (!nextResult.done) {\n            heap.push({\n                value: nextResult.value,\n                sourceIndex: smallest.sourceIndex,\n                iterator: smallest.iterator,\n            });\n            heapify(heap, { comparator: (a, b) => cmp(a.value, b.value) });\n        }\n    }\n}\n","import { heapReplace } from \"./heapReplace\";\nimport { heapify } from \"./heapify\";\nimport type { Options } from \"./types\";\nimport { _defaultMinHeapComparator } from \"./utils\";\n\nexport function nLargest<T>(\n    iterable: T[],\n    n: number,\n    options?: Options<T>,\n): T[] {\n    const size = iterable.length;\n    const cmp = options?.comparator ?? _defaultMinHeapComparator<T>;\n\n    if (n <= 0) {\n        return [];\n    }\n\n    if (n >= size) {\n        const result = iterable.slice();\n        result.sort((a, b) => {\n            if (cmp(a, b)) return 1;\n            if (cmp(b, a)) return -1;\n            return 0;\n        });\n        return result;\n    }\n\n    const heap: T[] = iterable.slice(0, n);\n    heapify(heap, { comparator: cmp });\n\n    for (let i = n; i < size; i++) {\n        const item = iterable[i]!;\n        const heapTop = heap[0]!;\n\n        if (!cmp(item, heapTop)) {\n            heapReplace(heap, item, { comparator: cmp });\n        }\n    }\n\n    heap.sort((a, b) => {\n        if (cmp(a, b)) return 1;\n        if (cmp(b, a)) return -1;\n        return 0;\n    });\n\n    return heap;\n}\n","import type { Options } from \"./types\";\nimport { _defaultMinHeapComparator } from \"./utils\";\nimport { heapReplace } from \"./heapReplace\";\nimport { heapify } from \"./heapify\";\n\nexport function nSmallest<T>(\n    iterable: T[],\n    n: number,\n    options?: Options<T>,\n): T[] {\n    const size = iterable.length;\n    const cmp = (a: T, b: T) => {\n        if (options?.comparator) {\n            return options.comparator(a, b);\n        }\n\n        return !_defaultMinHeapComparator<T>(a, b);\n    };\n\n    if (n <= 0) {\n        return [];\n    }\n\n    if (n >= size) {\n        const result = iterable.slice();\n        result.sort((a, b) => {\n            if (cmp(a, b)) return 1;\n            if (cmp(b, a)) return -1;\n            return 0;\n        });\n        return result;\n    }\n\n    const heap: T[] = iterable.slice(0, n);\n    heapify(heap, { comparator: cmp });\n\n    for (let i = n; i < size; i++) {\n        const item = iterable[i]!;\n        const heapTop = heap[0]!;\n\n        if (!cmp(item, heapTop)) {\n            heapReplace(heap, item, { comparator: cmp });\n        }\n    }\n\n    heap.sort((a, b) => {\n        if (cmp(a, b)) return 1;\n        if (cmp(b, a)) return -1;\n        return 0;\n    });\n\n    return heap;\n}\n"]}