ts-api/dist/core/adt/tree/MinHeap.js

"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.cast_de_nrw_schule_svws_core_adt_tree_MinHeap = exports.MinHeap = void 0;
const IllegalStateException_1 = require("../../../java/lang/IllegalStateException");
const MinHeapIterator_1 = require("../../../core/adt/tree/MinHeapIterator");
const StringBuilder_1 = require("../../../java/lang/StringBuilder");
const System_1 = require("../../../java/lang/System");
const Comparator_1 = require("../../../java/util/Comparator");
const NullPointerException_1 = require("../../../java/lang/NullPointerException");
const JavaObject_1 = require("../../../java/lang/JavaObject");
const Arrays_1 = require("../../../java/util/Arrays");
const IllegalArgumentException_1 = require("../../../java/lang/IllegalArgumentException");
const NoSuchElementException_1 = require("../../../java/util/NoSuchElementException");
class MinHeap extends JavaObject_1.JavaObject {
    _size = 0;
    _nodes = Array(0).fill(null);
    _comparator;
    _initialCapacity;
    _modCount = 0;
    /**
     * Implementation for method overloads of 'constructor'
     */
    constructor(__param0, __param1) {
        super();
        if (((typeof __param0 !== "undefined") && ((typeof __param0 !== 'undefined') && (__param0 instanceof Object) && (__param0 !== null) && ('compare' in __param0) && (typeof __param0.compare === 'function')) || (__param0 === null)) && ((typeof __param1 !== "undefined") && typeof __param1 === "number")) {
            let comparator = (0, Comparator_1.cast_java_util_Comparator)(__param0);
            let initialCapacity = __param1;
            if (initialCapacity <= 0)
                throw new IllegalArgumentException_1.IllegalArgumentException("Die initiale Kapazität muss größer als 0 sein.");
            this._comparator = comparator;
            this._initialCapacity = initialCapacity;
            this._modCount = 0;
        }
        else if (((typeof __param0 !== "undefined") && ((typeof __param0 !== 'undefined') && (__param0 instanceof Object) && (__param0 !== null) && ('compare' in __param0) && (typeof __param0.compare === 'function')) || (__param0 === null)) && (typeof __param1 === "undefined")) {
            let comparator = (0, Comparator_1.cast_java_util_Comparator)(__param0);
            this._comparator = comparator;
            this._initialCapacity = 63;
            this._modCount = 0;
        }
        else if (((typeof __param0 !== "undefined") && ((__param0 instanceof JavaObject_1.JavaObject) && (__param0.isTranspiledInstanceOf('de.nrw.schule.svws.core.adt.tree.MinHeap'))) || (__param0 === null)) && (typeof __param1 === "undefined")) {
            let original = cast_de_nrw_schule_svws_core_adt_tree_MinHeap(__param0);
            this._comparator = original._comparator;
            this._initialCapacity = original._initialCapacity;
            this._nodes = Arrays_1.Arrays.copyOf(original._nodes, original._nodes.length);
            this._size = original._size;
            this._modCount = original._modCount;
        }
        else
            throw new Error('invalid method overload');
    }
    add(e) {
        if (e === null)
            return false;
        if (this._nodes.length === 0)
            this._nodes = this.newArray(e, this._initialCapacity);
        if (this._size === this._nodes.length)
            this.grow();
        this._nodes[this._size] = e;
        this.heapifyUp(this._size++);
        this._modCount++;
        return true;
    }
    element() {
        if ((this._size === 0) || (this._nodes[0] === null))
            throw new NoSuchElementException_1.NoSuchElementException();
        return this._nodes[0];
    }
    offer(e) {
        return this.add(e);
    }
    peek() {
        return this._nodes.length === 0 ? null : this._nodes[0];
    }
    poll() {
        if (this._size === 0)
            return null;
        let elem = this._nodes[0];
        this._nodes[0] = this._nodes[--this._size];
        this._nodes[this._size] = null;
        this.heapifyDown(0);
        this._modCount++;
        return elem;
    }
    /**
     * Implementation for method overloads of 'remove'
     */
    remove(__param0) {
        if ((typeof __param0 === "undefined")) {
            let result = this.poll();
            if (result === null)
                throw new NoSuchElementException_1.NoSuchElementException();
            return result;
        }
        else if (((typeof __param0 !== "undefined") && ((__param0 instanceof Object) || ((__param0 instanceof JavaObject_1.JavaObject) && (__param0.isTranspiledInstanceOf('java.lang.Object')))) || (__param0 === null))) {
            let o = (__param0 instanceof JavaObject_1.JavaObject) ? (0, JavaObject_1.cast_java_lang_Object)(__param0) : __param0;
            if (o === null)
                return false;
            let index = this.findIndex(o);
            if (index === -1)
                return false;
            this._size--;
            this._modCount++;
            if (index === this._size)
                return true;
            this._nodes[index] = this._nodes[this._size];
            this._nodes[this._size] = null;
            this.heapifyUp(index);
            this.heapifyDown(index);
            return true;
        }
        else
            throw new Error('invalid method overload');
    }
    size() {
        return this._size;
    }
    isEmpty() {
        return this._size === 0;
    }
    contains(o) {
        if (o === null)
            return false;
        for (let i = 0; i < this._size; i++) {
            if (JavaObject_1.JavaObject.equalsTranspiler(this._nodes[i], (o)))
                return true;
        }
        return false;
    }
    containsAll(c) {
        if (c === null)
            return true;
        if (this === c)
            return true;
        for (let o of c)
            if (!this.contains(o))
                return false;
        return true;
    }
    addAll(c) {
        if (c === null)
            return false;
        if (this === c) {
            if (this._size === 0)
                return false;
            let tmp = Arrays_1.Arrays.copyOf(this._nodes, this._size);
            for (let t of tmp)
                if (t !== null)
                    this.add(t);
            return true;
        }
        let result = false;
        for (let t of c) {
            if (this.add(t))
                result = true;
        }
        return result;
    }
    removeAll(c) {
        if (c === null)
            return false;
        if (this === c) {
            if (this.size() === 0)
                return false;
            this.clear();
            return true;
        }
        let result = false;
        for (let o of c) {
            if (this.remove(o)) {
                result = true;
                while (this.remove(o))
                    ;
            }
        }
        return result;
    }
    retainAll(c) {
        if (this._size === 0)
            return false;
        if (c === null) {
            this.clear();
            return true;
        }
        if (this === c)
            return false;
        let tmp = this.newArray(this._nodes[0], this._nodes.length);
        if (tmp === null)
            return false;
        let i = 0;
        let elem;
        let changed = false;
        while ((elem = this.poll()) !== null) {
            if (c.contains(elem))
                tmp[i++] = elem;
            else
                changed = true;
        }
        this._nodes = tmp;
        this._size = i;
        this._modCount++;
        return changed;
    }
    clear() {
        this._nodes = Array(0).fill(null);
        this._size = 0;
        this._modCount++;
    }
    /**
     * Implementation for method overloads of 'toArray'
     */
    toArray(__param0) {
        if ((typeof __param0 === "undefined")) {
            return this.copyNodes();
        }
        else if (((typeof __param0 !== "undefined") && Array.isArray(__param0))) {
            let a = __param0;
            if (a.length < this._size)
                return this.copyNodes();
            System_1.System.arraycopy(this._nodes, 0, a, 0, this._size);
            Arrays_1.Arrays.fill(a, this._size, a.length, null);
            return a;
        }
        else
            throw new Error('invalid method overload');
    }
    iterator() {
        return new MinHeapIterator_1.MinHeapIterator(this._nodes, this);
    }
    clone() {
        return new MinHeap(this);
    }
    /**
     * Gibt den {@link Comparator} des Minimum Heaps zurück.
     *
     * @return der Comparator
     */
    comparator() {
        return this._comparator;
    }
    /**
     * Gibt die aktuelle Kapazität des Arrays zurück.
     *
     * @return die aktuelle Kapazität des Arrays zurück
     */
    capacity() {
        return (this._nodes.length === 0) ? this._initialCapacity : this._nodes.length;
    }
    /**
     * Gibt den Inhalt des Minimum Heaps in einem sortierten Array zurück.
     *
     * @return ein sortiertes Array mit den Elementen des Minimum Heaps.
     */
    toSortedArray() {
        if (this._size === 0)
            return Array(0).fill(null);
        let copy = new MinHeap(this);
        let tmp = this.newArray(this._nodes[0], this._size);
        let current;
        let i = 0;
        while ((current = copy.poll()) !== null)
            tmp[i++] = current;
        return tmp;
    }
    /**
     * Gibt den Inhalt des Heaps als Array-Repräsentation aus.
     *
     * @return der Inhalt des Heaps
     */
    toString() {
        let sb = new StringBuilder_1.StringBuilder();
        for (let i = 0; i < this._size; i++) {
            sb.append(this._nodes[i]);
            if (i !== this._size - 1)
                sb.append(", ");
        }
        return sb.toString();
    }
    /**
     * Ermittelt eine Hash-Code für dieses Objekt basierend auf den gespeicherten
     * Daten im Heap (die konkrete Ordnung des Baumes wird nicht unterschieden).
     *
     * @return der Hashcode des Minimum Heaps
     */
    hashCode() {
        return Arrays_1.Arrays.deepHashCode(this.toSortedArray());
    }
    /**
     * Prüft, ob das übergebene Objekt ein Minimum-Heap ist, der
     * die gleichen Elemente mit der gleichen Ordnung beinhaltet.
     *
     * @param obj   das zu vergleichende Objekt
     */
    equals(obj) {
        if (this === obj)
            return true;
        if (obj === null)
            return false;
        if (((obj instanceof JavaObject_1.JavaObject) && (obj.isTranspiledInstanceOf('de.nrw.schule.svws.core.adt.tree.MinHeap')))) {
            let other = cast_de_nrw_schule_svws_core_adt_tree_MinHeap(obj);
            return Arrays_1.Arrays.deepEquals(this.toSortedArray(), other.toSortedArray());
        }
        return false;
    }
    /**
     * Liefert zum Index i den Index des Elter zurück.
     *
     * @param i
     *
     * @return den Index des Elter
     */
    static getParentIndex(i) {
        return (i <= 0) ? -1 : Math.trunc((i - 1) / 2);
    }
    /**
     * Liefert zum Index i den Index des linken Kindes zurück.
     *
     * @param i
     *
     * @return den Index des linken Kindes
     */
    static getLeftChildIndex(i) {
        return 2 * i + 1;
    }
    /**
     * Liefert zum Index i den Index des rechten Kindes zurück.
     *
     * @param i
     *
     * @return den Index des rechten Kindes
     */
    static getRightChildIndex(i) {
        return 2 * i + 2;
    }
    /**
     * Tauscht die Elemente an den Stellen i und j im Array
     *
     * @param i
     * @param j
     */
    swap(i, j) {
        let elem = this._nodes[i];
        this._nodes[i] = this._nodes[j];
        this._nodes[j] = elem;
    }
    /**
     * Stellt die Minimum Heap Eigenschaft vom Index i aus im Baum abwärts her.
     *
     * @param i   ab diesem Index wird im Baum abwärts geprüft.
     */
    heapifyDown(i) {
        let left = MinHeap.getLeftChildIndex(i);
        let right = MinHeap.getRightChildIndex(i);
        if (left >= this._size)
            return;
        let child = right;
        if (right === this._size) {
            child = left;
        }
        else {
            let nodeLeft = this._nodes[left];
            let nodeRight = this._nodes[right];
            if ((nodeLeft === null) || (nodeRight === null))
                return;
            if (this._comparator.compare(nodeLeft, nodeRight) < 0)
                child = left;
        }
        let nodeCurrent = this._nodes[i];
        let nodeChild = this._nodes[child];
        if ((nodeCurrent === null) || (nodeChild === null))
            throw new NullPointerException_1.NullPointerException();
        if (this._comparator.compare(nodeCurrent, nodeChild) <= 0)
            return;
        this.swap(i, child);
        this.heapifyDown(child);
    }
    /**
     * Stellt die Minimum-Heap-Eigenschaft des Arrays ab Position i aufwärts wieder her.
     *
     * @param i   ab diesem Index wird überprüft
     */
    heapifyUp(i) {
        let parentIndex = MinHeap.getParentIndex(i);
        if (parentIndex < 0)
            return;
        let nodeCurrent = this._nodes[i];
        let nodeParent = this._nodes[parentIndex];
        if ((nodeCurrent === null) || (nodeParent === null) || (this._comparator.compare(nodeCurrent, nodeParent) >= 0))
            return;
        this.swap(i, parentIndex);
        this.heapifyUp(parentIndex);
    }
    /**
     * Erstellt ein neues Array vom Typ T mit der angegebenen Länge.
     *
     * @param elem     Ein Element vom Typ T, welches als Vorlage für die Elemente des Arrays dient
     * @param length   die Länge des neuen Arrays
     *
     * @return das neue Array
     */
    newArray(elem, length) {
        if (elem === null)
            return Array(length).fill(null);
        return Array(length).fill(null);
    }
    /**
     * Erzeugt eine Kopie des internen Arrays _nodes.
     *
     * @return die Kopie des _nodes-Array.
     */
    copyNodes() {
        let result = this.newArray(this._size <= 0 ? null : this._nodes[0], this._size);
        System_1.System.arraycopy(this._nodes, 0, result, 0, this._size);
        return result;
    }
    /**
     * Lässt den dem Baum zu Grunde liegenden Baum wachsen. Verdoppelt die Menge der Elemente, die im Heap
     * gespeichert werden können.
     *
     * Falls der Heap durch das Wachsen auf mehr als {@link Integer.MAX_VALUE} Elemente ansteigen würde,
     * wird eine IllegalStateException geworfen.
     *
     * @throws IllegalStateException
     */
    grow() {
        if (this._nodes.length === Number.MAX_VALUE)
            throw new IllegalStateException_1.IllegalStateException("Der Minimum-Heap kann nicht mehr als " + Number.MAX_VALUE + " Elemente beinhalten.");
        let newLength = this._nodes.length * 2 + 1;
        if (newLength < 0)
            newLength = Number.MAX_VALUE;
        let tmp = this.newArray(this._nodes[0], newLength);
        System_1.System.arraycopy(this._nodes, 0, tmp, 0, this._size);
        this._nodes = tmp;
    }
    /**
     * Findet den Index an dem das Element t im dem dem Heap zu Grunde liegendem Array gespeichert ist.
     * Gibt -1 zurück, falls das Element nicht vorhanden ist.
     *
     * @param t   zu diesem Element soll der Index gefunden werden
     *
     * @return  der Index, falls das Element enthalten ist, ansonsten -1
     */
    findIndex(obj) {
        if (obj === null)
            return -1;
        for (let i = 0; i < this._size; i++) {
            if (JavaObject_1.JavaObject.equalsTranspiler(this._nodes[i], (obj)))
                return i;
        }
        return -1;
    }
    /**
     * Gibt die Anzahl der Operationen zurück, die diese Datenstruktur
     * verändert haben.
     *
     * @return die Anzahl der Operationen
     */
    getModCount() {
        return this._modCount;
    }
    isTranspiledInstanceOf(name) {
        return ['java.lang.Cloneable', 'de.nrw.schule.svws.core.adt.tree.MinHeap', 'java.util.Collection', 'java.util.Queue', 'java.lang.Iterable'].includes(name);
    }
    [Symbol.iterator]() {
        let iter = this.iterator();
        const result = {
            next() {
                if (iter.hasNext())
                    return { value: iter.next(), done: false };
                return { value: null, done: true };
            }
        };
        return result;
    }
}
exports.MinHeap = MinHeap;
function cast_de_nrw_schule_svws_core_adt_tree_MinHeap(obj) {
    return obj;
}
exports.cast_de_nrw_schule_svws_core_adt_tree_MinHeap = cast_de_nrw_schule_svws_core_adt_tree_MinHeap;
//# sourceMappingURL=MinHeap.js.map