/*!
    \brief HashSet container.

    Set-like (\see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set) container with equal by value semantics.

    \todo Investigate usage of buckets instead object-like.
*/

import { create } from '../core/object';
import { isIterable, isArrayLike } from '../core/traits';

type Node<V> = {
    value: V;
    next: Node<V> | undefined;
};

export type Hash<V> = (key: V) => number;

export type Equal<V> = (lhs: V, rhs: V) => boolean;

export class HashSet<V> {
    protected _entries = create<Node<V> | undefined>();
    protected _size = 0;
    protected _hash: Hash<V>;
    protected _equal: Equal<V>;

    constructor(hashfn: Hash<V>, equalfn: Equal<V>, entries?: ArrayLike<V> | Iterable<V>) {
        this._hash = hashfn;
        this._equal = equalfn;
        if (isIterable(entries)) {
            for (const value of entries)
                this.add(value);
        }
        else if (isArrayLike(entries)) {
            const length = entries.length;
            for (let i = 0; i < length; i++)
                this.add(entries[i]);
        }
    }

    get size() {
        return this._size;
    }

    add(value: V) {
        const hash = this._hash(value);
        const head = this._entries[hash];
        if (head === undefined) {
            this._entries[hash] = {
                value,
                next: undefined
            };
            this._size++;
            return this;
        }
        for (let node = head; true;) {
            if (this._equal(value, node.value))
                return this;
            const next = node.next;
            if (next === undefined) {
                node.next = {
                    value,
                    next: undefined
                };
                this._size++;
                return this;
            }
            node = next;
        }
    }

    has(value: V) {
        for (let node = this._entries[this._hash(value)]; node !== undefined; node = node.next)
            if (this._equal(value, node.value))
                return true;
        return false;
    }

    delete(value: V) {
        const hash = this._hash(value);
        const entries = this._entries;
        for (let node = entries[hash], prev: Node<V> | undefined; node !== undefined;) {
            const next = node.next;
            if (this._equal(value, node.value)) {
                if (prev === undefined) {
                    if (next === undefined)
                        delete entries[hash];
                    else
                        entries[hash] = next;
                }
                else
                    prev.next = next;
                this._size--;
                return true;
            }
            prev = node;
            node = next;
        }
        return false;
    }

    clear() {
        for (const value of this.values())
            this.delete(value);
    }

    *values() {
        const entries = this._entries;
        for (const key in entries)
            for (let node = entries[key]; node !== undefined; node = node.next)
                yield node.value;
    }

    *entries() {
        const entries = this._entries;
        for (const key in entries)
            for (let node = entries[key]; node !== undefined; node = node.next) {
                const value = node.value;
                yield [value, value] as [V, V];
            }
    }

    forEach(callbackfn: (value: V, key: V, set: HashSet<V>) => void, thisArg?: any) {
        const entries = this._entries;
        for (const key in entries)
            for (let node = entries[key]; node !== undefined; node = node.next) {
                const value = node.value;
                callbackfn.call(thisArg, value, value, this);
            }
    }

    [Symbol.iterator]() {
        return this.values();
    }
}