File Explorer

1"use strict";2/*3 * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.4 * SPDX-License-Identifier: Apache-2.0.5 */6Object.defineProperty(exports, "__esModule", { value: true });7exports.MinHeap = void 0;8var error_1 = require("./error");9/**10 * A generic array-based min-heap implementation for priority queue usage.  Used to track operation timeouts.11 */12var MinHeap = /** @class */ (function () {13    function MinHeap(lessThanOperator) {14        this.lessThanOperator = lessThanOperator;15        this.heap = [undefined];16        this.currentSize = 0;17    }18    /**19     * Push a value into the min-heap20     *21     * @param value value to add22     */23    MinHeap.prototype.push = function (value) {24        this.currentSize++;25        this.heap[this.currentSize] = value;26        this.heapifyUp(this.currentSize);27    };28    /**29     * Gets the minimum value of the heap.  Returns undefined if the heap is empty.30     */31    MinHeap.prototype.peek = function () {32        if (this.currentSize == 0) {33            return undefined;34        }35        // guaranteed to be a T36        return this.heap[1];37    };38    /**39     * Pops the minimum value from the heap.  Throws an exception if the heap is empty.40     */41    MinHeap.prototype.pop = function () {42        if (this.empty()) {43            throw new error_1.CrtError("Heap is empty");44        }45        var returnValue = this.heap[1];46        var lastElement = this.heap[this.currentSize];47        this.heap[this.currentSize--] = undefined; // erase the reference; unclear if this is overkill rather than simply removing from an array (or an indexed map for that matter)48        this.heap[1] = lastElement;49        this.heapifyDown(1);50        // @ts-ignore - guaranteed to be a T51        return returnValue;52    };53    /**54     * Checks if the min-heap is empty or not55     */56    MinHeap.prototype.empty = function () {57        return this.currentSize == 0;58    };59    /**60     * Removes all values from the min-heap61     */62    MinHeap.prototype.clear = function () {63        this.heap = [undefined];64        this.currentSize = 0;65    };66    MinHeap.prototype.swapElements = function (index1, index2) {67        var temp = this.heap[index1];68        this.heap[index1] = this.heap[index2];69        this.heap[index2] = temp;70    };71    MinHeap.prototype.heapifyDown = function (startIndex) {72        var currentIndex = startIndex;73        while (true) {74            var leftIndex = currentIndex << 1;75            var rightIndex = leftIndex + 1;76            var swapIndex = undefined;77            // @ts-ignore - heap elements guaranteed to be a T78            if (leftIndex <= this.currentSize && this.lessThanOperator(this.heap[leftIndex], this.heap[currentIndex])) {79                swapIndex = leftIndex;80            }81            // @ts-ignore - heap elements guaranteed to be a T82            if (rightIndex <= this.currentSize && this.lessThanOperator(this.heap[rightIndex], this.heap[currentIndex])) {83                // @ts-ignore - heap elements guaranteed to be a T84                if (!swapIndex || this.lessThanOperator(this.heap[rightIndex], this.heap[leftIndex])) {85                    // if current is greater than both left and right children, we must swap with the smallest child86                    // since it will become the parent of both current and the other child87                    swapIndex = rightIndex;88                }89            }90            if (!swapIndex) {91                break;92            }93            this.swapElements(currentIndex, swapIndex);94            currentIndex = swapIndex;95        }96    };97    MinHeap.prototype.heapifyUp = function (index) {98        var parentIndex = index >> 1;99        // @ts-ignore - heap element guaranteed to be a T100        while (parentIndex > 0 && this.lessThanOperator(this.heap[index], this.heap[parentIndex])) {101            this.swapElements(index, parentIndex);102            index = parentIndex;103            parentIndex = parentIndex >> 1;104        }105    };106    return MinHeap;107}());108exports.MinHeap = MinHeap;109//# sourceMappingURL=heap.js.map