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 ) : V | undefined ; has ( key ) : boolean ; keys ( ) : IteratorShim < K > ; values ( ) : IteratorShim < V > ; entries ( ) : IteratorShim < [ K , V ] > ; forEach ( action ) : void ; } interface MapShim < K , V > extends ReadonlyMapShim < K , V > { set ( key , value ) : this ; delete ( key ) : boolean ; clear ( ) : void ; } type MapShimConstructor = new < K , V > ( iterable ? ) => MapShim < K , V > ; interface ReadonlySetShim < T > { readonly size : number ; has ( value ) : boolean ; keys ( ) : IteratorShim < T > ; values ( ) : IteratorShim < T > ; entries ( ) : IteratorShim < [ T , T ] > ; forEach ( action ) : void ; } interface SetShim < T > extends ReadonlySetShim < T > { add ( value ) : this ; delete ( value ) : boolean ; clear ( ) : void ; } type SetShimConstructor = new < T > ( iterable ? ) => 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 > ( ) { const sentinel = { } ; sentinel . prev = sentinel ; return { head : sentinel , tail : sentinel , size : 0 } ; } function createMapEntry < K , V > ( key , value ) { return { key , value , next : undefined , prev : undefined } ; } function sameValueZero ( x , y ) { return x === y || x !== x && y !== y ; } function getPrev < K , V > ( entry ) { const prev = entry . prev ; if ( ! prev || prev === entry ) throw new Error ( "Illegal state" ) ; return prev ; } function getNext < K , V > ( entry ) { while ( entry ) { const skipNext = ! entry . prev ; entry = entry . next ; if ( skipNext ) { continue ; } return entry ; } } function getEntry < K , V > ( data , key ) { for ( let entry = data . tail ; entry !== data . head ; entry = getPrev ( entry ) ) { if ( sameValueZero ( entry . key , key ) ) { return entry ; } } } function addOrUpdateEntry < K , V > ( data , key , value ) { 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 , key ) { for ( let entry = data . tail ; entry !== data . head ; entry = getPrev ( entry ) ) { if ( entry . prev === undefined ) throw new Error ( "Illegal state" ) ; if ( sameValueZero ( entry . key , key ) ) { if ( entry . next ) { entry . next . prev = entry . prev ; } else { 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 ) { 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 , action ) { let entry = data . head ; while ( entry ) { entry = getNext ( entry ) ; if ( entry ) { action ( entry . value ! , entry . key ! ) ; } } } function forEachIteration < T > ( iterator , action ) { 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 , selector ) { return { current : data . head , selector } ; } function iteratorNext < K , V , U extends ( K | V | [ K , V ] ) > ( data ) { 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 } ; } } export namespace ShimCollections { export function createMapShim ( getIterator ) { class MapIterator < K , V , U extends ( K | V | [ K , V ] ) > { private _data : IteratorData < K , V , U > ; constructor ( data , selector ) { 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 ? ) { forEachIteration ( getIterator ( iterable ) , ( [ key , value ] ) => this . set ( key , value ) ) ; } get size ( ) { return this . _mapData . size ; } get ( key ) { return getEntry ( this . _mapData , key ) ?. value ; } set ( key , value ) { return addOrUpdateEntry ( this . _mapData , key , value ) , this ; } has ( key ) { return ! ! getEntry ( this . _mapData , key ) ; } delete ( key ) { return ! ! deleteEntry ( this . _mapData , key ) ; } clear ( ) { clearEntries ( this . _mapData ) ; } keys ( ) { return new MapIterator ( this . _mapData , ( key , _value ) => key ) ; } values ( ) { return new MapIterator ( this . _mapData , ( _key , value ) => value ) ; } entries ( ) { return new MapIterator ( this . _mapData , ( key , value ) => [ key , value ] ) ; } forEach ( action ) { forEachEntry ( this . _mapData , action ) ; } } ; } export function createSetShim ( getIterator ) { class SetIterator < K , V , U extends ( K | V | [ K , V ] ) > { private _data : IteratorData < K , V , U > ; constructor ( data , selector ) { this . _data = createIteratorData ( data , selector ) ; } next ( ) { return iteratorNext ( this . _data ) ; } } return class Set < T > implements SetShim < T > { private _mapData = createMapData < T , T > ( ) ; constructor ( iterable ? ) { forEachIteration ( getIterator ( iterable ) , value => this . add ( value ) ) ; } get size ( ) { return this . _mapData . size ; } add ( value ) { return addOrUpdateEntry ( this . _mapData , value , value ) , this ; } has ( value ) { return ! ! getEntry ( this . _mapData , value ) ; } delete ( value ) { return ! ! deleteEntry ( this . _mapData , value ) ; } clear ( ) { clearEntries ( this . _mapData ) ; } keys ( ) { return new SetIterator ( this . _mapData , ( key , _value ) => key ) ; } values ( ) { return new SetIterator ( this . _mapData , ( _key , value ) => value ) ; } entries ( ) { return new SetIterator ( this . _mapData , ( key , value ) => [ key , value ] ) ; } forEach ( action ) { forEachEntry ( this . _mapData , action ) ; } } ; } } }