/* @internal */
namespace ts {
    type GetIteratorCallback = <I extends readonly any[] | ReadonlySetShim<any> | ReadonlyMapShim<any, any> | undefined>(iterable: I) => IteratorShim<
        I extends ReadonlyMapShim<infer K, infer V> ? [K, V] :
        I extends ReadonlySetShim<infer T> ? T :
        I extends readonly (infer T)[] ? T :
        I extends undefined ? undefined :
        never>;

    type IteratorResultShim<T> =
        | { value: T, done?: false }
        | { value: void, done: true };

    interface IteratorShim<T> {
        next(): IteratorResultShim<T>;
    }

    interface ReadonlyMapShim<K, V> {
        readonly size: number;
        get(key: K): V | undefined;
        has(key: K): boolean;
        keys(): IteratorShim<K>;
        values(): IteratorShim<V>;
        entries(): IteratorShim<[K, V]>;
        forEach(action: (value: V, key: K) => void): void;
    }

    interface MapShim<K, V> extends ReadonlyMapShim<K, V> {
        set(key: K, value: V): this;
        delete(key: K): boolean;
        clear(): void;
    }

    type MapShimConstructor = new <K, V>(iterable?: readonly (readonly [K, V])[] | ReadonlyMapShim<K, V>) => MapShim<K, V>;

    interface ReadonlySetShim<T> {
        readonly size: number;
        has(value: T): boolean;
        keys(): IteratorShim<T>;
        values(): IteratorShim<T>;
        entries(): IteratorShim<[T, T]>;
        forEach(action: (value: T, key: T) => void): void;
    }

    interface SetShim<T> extends ReadonlySetShim<T> {
        add(value: T): this;
        delete(value: T): boolean;
        clear(): void;
    }

    type SetShimConstructor = new <T>(iterable?: readonly T[] | ReadonlySetShim<T>) => SetShim<T>;

    interface MapData<K, V> {
        size: number;
        readonly head: MapEntry<K, V>;
        tail: MapEntry<K, V>;
    }

    interface MapEntry<K, V> {
        readonly key?: K;
        value?: V;
        /**
         * Specifies the next entry in the linked list.
         */
        next?: MapEntry<K, V>;
        /**
         * Specifies the previous entry in the linked list.
         * Must be set when the entry is part of a Map/Set.
         * When 'undefined', iterators should skip the next entry.
         * This will be set to 'undefined' when an entry is deleted.
         * See https://github.com/Microsoft/TypeScript/pull/27292 for more information.
         */
        prev?: MapEntry<K, V>;
    }

    interface IteratorData<K, V, U extends (K | V | [K, V])> {
        current?: MapEntry<K, V>;
        selector: (key: K, value: V) => U;
    }

    function createMapData<K, V>(): MapData<K, V> {
        const sentinel: MapEntry<K, V> = {};
        sentinel.prev = sentinel;
        return { head: sentinel, tail: sentinel, size: 0 };
    }

    function createMapEntry<K, V>(key: K, value: V): MapEntry<K, V> {
        return { key, value, next: undefined, prev: undefined };
    }

    function sameValueZero(x: unknown, y: unknown) {
        // Treats -0 === 0 and NaN === NaN
        return x === y || x !== x && y !== y;
    }

    function getPrev<K, V>(entry: MapEntry<K, V>) {
        const prev = entry.prev;
        // Entries without a 'prev' have been removed from the map.
        // An entry whose 'prev' points to itself is the head of the list and is invalid here.
        if (!prev || prev === entry) throw new Error("Illegal state");
        return prev;
    }

    function getNext<K, V>(entry: MapEntry<K, V> | undefined) {
        while (entry) {
            // Entries without a 'prev' have been removed from the map. Their 'next'
            // pointer should point to the previous entry prior to deletion and
            // that entry should be skipped to resume iteration.
            const skipNext = !entry.prev;
            entry = entry.next;
            if (skipNext) {
                continue;
            }
            return entry;
        }
    }

    function getEntry<K, V>(data: MapData<K, V>, key: K): MapEntry<K, V> | undefined {
        // We walk backwards from 'tail' to prioritize recently added entries.
        // We skip 'head' because it is an empty entry used to track iteration start.
        for (let entry = data.tail; entry !== data.head; entry = getPrev(entry)) {
            if (sameValueZero(entry.key, key)) {
                return entry;
            }
        }
    }

    function addOrUpdateEntry<K, V>(data: MapData<K, V>, key: K, value: V): MapEntry<K, V> | undefined {
        const existing = getEntry(data, key);
        if (existing) {
            existing.value = value;
            return;
        }

        const entry = createMapEntry(key, value);
        entry.prev = data.tail;
        data.tail.next = entry;
        data.tail = entry;
        data.size++;
        return entry;
    }

    function deleteEntry<K, V>(data: MapData<K, V>, key: K): MapEntry<K, V> | undefined {
        // We walk backwards from 'tail' to prioritize recently added entries.
        // We skip 'head' because it is an empty entry used to track iteration start.
        for (let entry = data.tail; entry !== data.head; entry = getPrev(entry)) {
            // all entries in the map should have a 'prev' pointer.
            if (entry.prev === undefined) throw new Error("Illegal state");
            if (sameValueZero(entry.key, key)) {
                if (entry.next) {
                    entry.next.prev = entry.prev;
                }
                else {
                    // an entry in the map without a 'next' pointer must be the 'tail'.
                    if (data.tail !== entry) throw new Error("Illegal state");
                    data.tail = entry.prev;
                }

                entry.prev.next = entry.next;
                entry.next = entry.prev;
                entry.prev = undefined;
                data.size--;
                return entry;
            }
        }
    }

    function clearEntries<K, V>(data: MapData<K, V>) {
        let node = data.tail;
        while (node !== data.head) {
            const prev = getPrev(node);
            node.next = data.head;
            node.prev = undefined;
            node = prev;
        }
        data.head.next = undefined;
        data.tail = data.head;
        data.size = 0;
    }

    function forEachEntry<K, V>(data: MapData<K, V>, action: (value: V, key: K) => void) {
        let entry: MapEntry<K, V> | undefined = data.head;
        while (entry) {
            entry = getNext(entry);
            if (entry) {
                action(entry.value!, entry.key!);
            }
        }
    }

    function forEachIteration<T>(iterator: IteratorShim<T> | undefined, action: (value: any) => void) {
        if (iterator) {
            for (let step = iterator.next(); !step.done; step = iterator.next()) {
                action(step.value);
            }
        }
    }

    function createIteratorData<K, V, U extends (K | V | [K, V])>(data: MapData<K, V>, selector: (key: K, value: V) => U): IteratorData<K, V, U> {
        return { current: data.head, selector };
    }

    function iteratorNext<K, V, U extends (K | V | [K, V])>(data: IteratorData<K, V, U>): IteratorResultShim<U> {
        // Navigate to the next entry.
        data.current = getNext(data.current);
        if (data.current) {
            return { value: data.selector(data.current.key!, data.current.value!), done: false };
        }
        else {
            return { value: undefined as never, done: true };
        }
    }

    /* @internal */
    export namespace ShimCollections {
        export function createMapShim(getIterator: GetIteratorCallback): MapShimConstructor {
            class MapIterator<K, V, U extends (K | V | [K, V])> {
                private _data: IteratorData<K, V, U>;
                constructor(data: MapData<K, V>, selector: (key: K, value: V) => U) {
                    this._data = createIteratorData(data, selector);
                }
                next() { return iteratorNext(this._data); }
            }
            return class Map<K, V> implements MapShim<K, V> {
                private _mapData = createMapData<K, V>();
                constructor(iterable?: readonly (readonly [K, V])[] | ReadonlyMapShim<K, V>) {
                    forEachIteration(getIterator(iterable), ([key, value]) => this.set(key, value));
                }
                get size() { return this._mapData.size; }
                get(key: K): V | undefined { return getEntry(this._mapData, key)?.value; }
                set(key: K, value: V): this { return addOrUpdateEntry(this._mapData, key, value), this; }
                has(key: K): boolean { return !!getEntry(this._mapData, key); }
                delete(key: K): boolean { return !!deleteEntry(this._mapData, key); }
                clear(): void { clearEntries(this._mapData); }
                keys(): IteratorShim<K> { return new MapIterator(this._mapData, (key, _value) => key); }
                values(): IteratorShim<V> { return new MapIterator(this._mapData, (_key, value) => value); }
                entries(): IteratorShim<[K, V]> { return new MapIterator(this._mapData, (key, value) => [key, value]); }
                forEach(action: (value: V, key: K) => void): void { forEachEntry(this._mapData, action); }
            };
        }

        export function createSetShim(getIterator: GetIteratorCallback): SetShimConstructor {
            class SetIterator<K, V, U extends (K | V | [K, V])> {
                private _data: IteratorData<K, V, U>;
                constructor(data: MapData<K, V>, selector: (key: K, value: V) => U) {
                    this._data = createIteratorData(data, selector);
                }
                next() { return iteratorNext(this._data); }
            }
            return class Set<T> implements SetShim<T> {
                private _mapData = createMapData<T, T>();
                constructor(iterable?: readonly T[] | ReadonlySetShim<T>) {
                    forEachIteration(getIterator(iterable), value => this.add(value));
                }
                get size() { return this._mapData.size; }
                add(value: T): this { return addOrUpdateEntry(this._mapData, value, value), this; }
                has(value: T): boolean { return !!getEntry(this._mapData, value); }
                delete(value: T): boolean { return !!deleteEntry(this._mapData, value); }
                clear(): void { clearEntries(this._mapData); }
                keys(): IteratorShim<T> { return new SetIterator(this._mapData, (key, _value) => key); }
                values(): IteratorShim<T> { return new SetIterator(this._mapData, (_key, value) => value); }
                entries(): IteratorShim<[T, T]> { return new SetIterator(this._mapData, (key, value) => [key, value]); }
                forEach(action: (value: T, key: T) => void): void { forEachEntry(this._mapData, action); }
            };
        }
    }
}