Brunobkr/llama.cpp_AlgMor24_github

1"use strict";2 3Object.defineProperty(exports, "__esModule", {4    value: true5});6// Binary min-heap implementation used for priority queue.7// Implementation is stable, i.e. push time is considered for equal priorities8class Heap {9    constructor() {10        this.heap = [];11        this.pushCount = Number.MIN_SAFE_INTEGER;12    }13 14    get length() {15        return this.heap.length;16    }17 18    empty() {19        this.heap = [];20        return this;21    }22 23    percUp(index) {24        let p;25 26        while (index > 0 && smaller(this.heap[index], this.heap[p = parent(index)])) {27            let t = this.heap[index];28            this.heap[index] = this.heap[p];29            this.heap[p] = t;30 31            index = p;32        }33    }34 35    percDown(index) {36        let l;37 38        while ((l = leftChi(index)) < this.heap.length) {39            if (l + 1 < this.heap.length && smaller(this.heap[l + 1], this.heap[l])) {40                l = l + 1;41            }42 43            if (smaller(this.heap[index], this.heap[l])) {44                break;45            }46 47            let t = this.heap[index];48            this.heap[index] = this.heap[l];49            this.heap[l] = t;50 51            index = l;52        }53    }54 55    push(node) {56        node.pushCount = ++this.pushCount;57        this.heap.push(node);58        this.percUp(this.heap.length - 1);59    }60 61    unshift(node) {62        return this.heap.push(node);63    }64 65    shift() {66        let [top] = this.heap;67 68        this.heap[0] = this.heap[this.heap.length - 1];69        this.heap.pop();70        this.percDown(0);71 72        return top;73    }74 75    toArray() {76        return [...this];77    }78 79    *[Symbol.iterator]() {80        for (let i = 0; i < this.heap.length; i++) {81            yield this.heap[i].data;82        }83    }84 85    remove(testFn) {86        let j = 0;87        for (let i = 0; i < this.heap.length; i++) {88            if (!testFn(this.heap[i])) {89                this.heap[j] = this.heap[i];90                j++;91            }92        }93 94        this.heap.splice(j);95 96        for (let i = parent(this.heap.length - 1); i >= 0; i--) {97            this.percDown(i);98        }99 100        return this;101    }102}103 104exports.default = Heap;105function leftChi(i) {106    return (i << 1) + 1;107}108 109function parent(i) {110    return (i + 1 >> 1) - 1;111}112 113function smaller(x, y) {114    if (x.priority !== y.priority) {115        return x.priority < y.priority;116    } else {117        return x.pushCount < y.pushCount;118    }119}120module.exports = exports.default;