LinkedList.js

"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
const LinkedListItem_1 = require("./LinkedListItem");
/**
 * Implements a linked list structure
 * @typeparam T Type of values within this LinkedList
 */
class LinkedList {
    /**
     * @param values Values to be added upfront into list
     */
    constructor(values) {
        /**
         * Current length of this LinkedList.
         * Note that this does not work anymore if you for some reason add your own LinkedListItems to LinkedList by hand
         */
        this.length = 0;
        /**
         * Given to own LinkedListItem's for following jobs regarding an unlink:
         * - If item is first item, set the next item as first item
         * - If item is last item, set the previous item as last item
         * - Decrease length
         * @param item Item that has been unlinked
         */
        this.unlinkCleanup = (item) => {
            if (this.first === item) {
                this.first = this.first.behind;
            }
            if (this.last === item) {
                this.last = this.last.before;
            }
            this.length--;
        };
        if (values) {
            if (values instanceof LinkedList)
                values = values.values();
            for (const value of values) {
                this.push(value);
            }
        }
    }
    /**
     * Clears this LinkedList.
     * The default complexity is O(1), because it only removes links to the first and last item and resets the length.
     * Note that if any LinkedListItem is still referenced outside the LinkedList, their before and behind fields might
     * still reference the chain, not freeing space.
     * You can set the unchain parameter to true, so every item in the linked list will be unchained,
     * meaning all references to before and behind items will be removed.
     * This increases complexity to O(n), but removes accidental outside references to the full chain.
     * @param unchain If `true`, remove link info from every item. Changes complexity to O(n)!
     */
    clear(unchain = false) {
        if (unchain) {
            while (this.first) {
                this.first.unlink(true);
            }
        }
        this.first = this.last = undefined;
        this.length = 0;
    }
    /**
     * As Array#every() given callback is called for every element until one call returns falsy or all elements had been processed
     * @returns `false` if there was a falsy response from the callback, `true` if all elements have been processed "falselesly"
     * @see Array#every
     */
    every(callback, thisArg) {
        if (thisArg) {
            callback = callback.bind(thisArg);
        }
        for (const item of this.keys()) {
            if (!callback(item.value, item, this)) {
                return false;
            }
        }
        return true;
    }
    /**
     * Filters values into a new LinkedList
     * @param callback decides wether given element should be part of new LinkedList
     * @see Array#filter
     */
    filter(callback, thisArg) {
        if (thisArg) {
            callback = callback.bind(thisArg);
        }
        const newList = new LinkedList();
        for (const [item, value] of this) {
            if (callback(value, item, this)) {
                newList.push(value);
            }
        }
        return newList;
    }
    /**
     * Returns value for which given callback returns truthy
     * @param callback runs for every value in LinkedList. If it returns truthy, current value is returned.
     * @see Array#find
     */
    find(callback, thisArg) {
        if (thisArg) {
            callback = callback.bind(thisArg);
        }
        for (const [item, value] of this) {
            if (callback(value, item, this)) {
                return value;
            }
        }
    }
    /**
     * Returns the LinkedListItem for which given callback returns truthy
     * @param callback runs for every LinkedListItem in LinkedList. If it returns truthy, current LinkedListItem is returned.
     * @see Array#findIndex
     */
    findItem(callback, thisArg) {
        if (thisArg) {
            callback = callback.bind(thisArg);
        }
        for (const [item, value] of this) {
            if (callback(value, item, this)) {
                return item;
            }
        }
    }
    /**
     * Iterates this LinkedList's items and values
     * @param callback Gets every value in LinkedList once with corresponding LinkedListItem and LinkedList
     * @param thisArg If given, callback will be bound here
     * @see Array#forEach
     */
    forEach(callback, thisArg) {
        if (thisArg) {
            callback = callback.bind(thisArg);
        }
        for (const [item, value] of this) {
            callback(value, item, this);
        }
    }
    /**
     * Checks if value can be found within LinkedList, starting from fromIndex, if given.
     * @param value value to be found in this
     * @param fromIndex Starting index. Supports negative values for which `this.size - 1 + fromIndex` will be used as starting point.
     * @returns true if value could be found in LinkedList (respecting fromIndex), false otherwhise
     * @see Array#includes
     */
    includes(value, fromIndex = 0) {
        let current = this.getItemByIndex(fromIndex);
        while (current) {
            if (current.value === value) {
                return true;
            }
            current = current.behind;
        }
        return false;
    }
    /**
     * Searches forward for given value and returns the first corresponding LinkedListItem found
     * @param searchedValue Value to be found
     * @param fromIndex Index to start from
     * @see Array#indexOf
     */
    itemOf(searchedValue, fromIndex = 0) {
        let current = this.getItemByIndex(fromIndex);
        while (current) {
            if (current.value === searchedValue) {
                return current;
            }
            current = current.behind;
        }
        return;
    }
    /**
     * Searches backwards for given value and returns the first corresponding LinkedListItem found
     * @param searchedValue Value to be found
     * @param fromIndex Index to start from
     * @see Array#indexOf
     */
    lastItemOf(searchedValue, fromIndex = -1) {
        let current = this.getItemByIndex(fromIndex);
        while (current) {
            if (current.value === searchedValue) {
                return current;
            }
            current = current.before;
        }
        return;
    }
    /**
     * Creates a new LinkedList with each of its itesm representing the output of the callback with each item in current LinkedList.
     * @param callback Gets value, LinkedListeItem and LinkedList. The response will be used as value in the new LinkedList
     * @param thisArg If given, callback is bound to thisArg
     * @see Array#map
     */
    map(callback, thisArg) {
        if (thisArg) {
            callback = callback.bind(thisArg);
        }
        const newList = new LinkedList();
        for (const [item, value] of this) {
            newList.push(callback(value, item, this));
        }
        return newList;
    }
    reduce(callback, initialValue) {
        let current = this.first;
        if (!current) {
            if (!initialValue) {
                throw new TypeError("Empty accumulator on empty LinkedList is not allowed.");
            }
            return initialValue;
        }
        if (initialValue === undefined) {
            initialValue = current.value;
            if (!current.behind) {
                return initialValue;
            }
            current = current.behind;
        }
        do {
            initialValue = callback(initialValue, current.value, current, this);
            current = current.behind;
        } while (current);
        return initialValue;
    }
    reduceRight(callback, initialValue) {
        let current = this.last;
        if (!current) {
            if (!initialValue) {
                throw new TypeError("Empty accumulator on empty LinkedList is not allowed.");
            }
            return initialValue;
        }
        // let accumulator: V | T;
        if (initialValue === undefined) {
            initialValue = current.value;
            if (!current.before) {
                return initialValue;
            }
            current = current.before;
        }
        do {
            initialValue = callback(initialValue, current.value, current, this);
            current = current.before;
        } while (current);
        return initialValue;
    }
    /**
     * Runs callback for every entry and returns true immediately if call of callback returns truthy.
     * @param callback called for every element. If response is truthy, iteration
     * @param thisArg If set, callback is bound to this
     * @returns `true` once a callback call returns truthy, `false` if none returned truthy.
     */
    some(callback, thisArg) {
        if (thisArg) {
            callback = callback.bind(thisArg);
        }
        for (const [item, value] of this) {
            if (callback(value, item, this)) {
                return true;
            }
        }
        return false;
    }
    /**
     * Joins values within this by given separator. Uses Array#join directly.
     * @param separator separator to be used
     * @see Array#join
     */
    join(separator) {
        return [...this.values()].join(separator);
    }
    /**
     * Concats given values and returns a new LinkedList with all given values.
     * If LinkedList's are given, they will be spread.
     * @param others Other values or lists to be concat'ed together
     * @see Array#concat
     */
    concat(...others) {
        const newList = new LinkedList(this);
        for (const other of others) {
            if (other instanceof LinkedList) {
                newList.push(...other.values());
            }
            else {
                newList.push(other);
            }
        }
        return newList;
    }
    /**
     * Removes the last LinkedListItem and returns its inner value
     */
    pop() {
        if (!this.last) {
            return;
        }
        const item = this.last;
        item.unlink();
        return item.value;
    }
    /**
     * Adds given values on the end of this LinkedList
     * @param values Values to be added
     */
    push(...values) {
        for (const value of values) {
            const item = new LinkedListItem_1.LinkedListItem(value, this.unlinkCleanup);
            if (!this.first || !this.last) {
                this.first = this.last = item;
            }
            else {
                this.last.insertBehind(item);
                this.last = item;
            }
            this.length++;
        }
        return this.length;
    }
    /**
     * Adds given values to the beginning of this LinkedList
     * @param values Values to be added
     */
    unshift(...values) {
        for (const value of values) {
            const item = new LinkedListItem_1.LinkedListItem(value, this.unlinkCleanup);
            if (!this.last || !this.first) {
                this.first = this.last = item;
            }
            else {
                item.insertBehind(this.first);
                this.first = item;
            }
            this.length++;
        }
        return this.length;
    }
    /**
     * Removes first occurrence of value found.
     * @param value value to remove from LinkedList
     */
    remove(value) {
        for (const item of this.keys()) {
            if (item.value === value) {
                item.unlink();
                return true;
            }
        }
        return false;
    }
    /**
     * Removes every occurrance of value within this.
     * @param value value to remove from LinkedList
     */
    removeAllOccurrences(value) {
        let foundSomethingToDelete = false;
        for (const item of this.keys()) {
            if (item.value === value) {
                item.unlink();
                foundSomethingToDelete = true;
            }
        }
        return foundSomethingToDelete;
    }
    /**
     * Returns and removes first element from LinkedList
     */
    shift() {
        if (!this.first) {
            return;
        }
        const item = this.first;
        item.unlink();
        return item.value;
    }
    /**
     * Returns LinkedListItem and value for every entry of this LinkedList
     */
    *[Symbol.iterator]() {
        let current = this.first;
        if (!current) {
            return;
        }
        do {
            yield [current, current.value];
            current = current.behind;
        } while (current);
    }
    /**
     * Returns LinkedListItem and value for every entry of this LinkedList
     * @see LinkedList#Symbol.iterator
     */
    entries() {
        return this[Symbol.iterator]();
    }
    /**
     * Iterates the LinkedListItem's of this LinkedList
     */
    *keys() {
        let current = this.first;
        if (!current) {
            return;
        }
        do {
            yield current;
            current = current.behind;
        } while (current);
    }
    /**
     * Returns a value for every entry of this LinkedList
     */
    *values() {
        let current = this.first;
        if (!current) {
            return;
        }
        do {
            yield current.value;
            current = current.behind;
        } while (current);
    }
    /**
     * Returns the item by given index.
     * Supports negative values and will return the item at `LinkedList.size - 1 + index` in that case.
     * @param index Index of item to get from list
     */
    getItemByIndex(index) {
        if (index === undefined) {
            throw new Error("index must be a number!");
        }
        if (!this.first) {
            return;
        }
        let current;
        if (index > 0) {
            current = this.first;
            while (current && index--) {
                current = current.behind;
            }
        }
        else if (index < 0) {
            current = this.last;
            while (current && ++index) {
                current = current.before;
            }
        }
        else {
            return this.first;
        }
        return current;
    }
}
exports.LinkedList = LinkedList;
//# sourceMappingURL=LinkedList.js.map