interface Item < K , V > { previous : Item < K , V > | undefined ; next : Item < K , V > | undefined ; key : K ; value : V ; } export const enum Touch { None = 0 , AsOld = 1 , AsNew = 2 } export class LinkedMap < K , V > { private _map : Map < K , Item < K , V > > ; private _head : Item < K , V > | undefined ; private _tail : Item < K , V > | undefined ; private _size : number ; constructor ( ) { this . _map = new Map < K , Item < K , V > > ( ) ; this . _head = undefined ; this . _tail = undefined ; this . _size = 0 ; } public clear ( ) { this . _map . clear ( ) ; this . _head = undefined ; this . _tail = undefined ; this . _size = 0 ; } public isEmpty ( ) { return ! this . _head && ! this . _tail ; } public get size ( ) : number { return this . _size ; } public has ( key ) { return this . _map . has ( key ) ; } public get ( key , touch = Touch . None ) { const item = this . _map . get ( key ) ; if ( ! item ) { return undefined ; } if ( touch !== Touch . None ) { this . touch ( item , touch ) ; } return item . value ; } public set ( key , value , touch = Touch . None ) { let item = this . _map . get ( key ) ; if ( item ) { item . value = value ; if ( touch !== Touch . None ) { this . touch ( item , touch ) ; } } else { item = { key , value , next : undefined , previous : undefined } ; switch ( touch ) { case Touch . None : this . addItemLast ( item ) ; break ; case Touch . AsOld : this . addItemFirst ( item ) ; break ; case Touch . AsNew : this . addItemLast ( item ) ; break ; default : this . addItemLast ( item ) ; break ; } this . _map . set ( key , item ) ; this . _size ++ ; } } public delete ( key ) { return ! ! this . remove ( key ) ; } public remove ( key ) { const item = this . _map . get ( key ) ; if ( ! item ) { return undefined ; } this . _map . delete ( key ) ; this . removeItem ( item ) ; this . _size -- ; return item . value ; } public shift ( ) { if ( ! this . _head && ! this . _tail ) { return undefined ; } if ( ! this . _head || ! this . _tail ) { throw new Error ( 'Invalid list' ) ; } const item = this . _head ; this . _map . delete ( item . key ) ; this . removeItem ( item ) ; this . _size -- ; return item . value ; } public forEach ( callbackfn , thisArg ? ) { let current = this . _head ; while ( current ) { if ( thisArg ) { callbackfn . bind ( thisArg ) ( current . value , current . key , this ) ; } else { callbackfn ( current . value , current . key , this ) ; } current = current . next ; } } public values ( ) { let result = [ ] ; let current = this . _head ; while ( current ) { result . push ( current . value ) ; current = current . next ; } return result ; } public keys ( ) { let result = [ ] ; let current = this . _head ; while ( current ) { result . push ( current . key ) ; current = current . next ; } return result ; } protected trimOld ( newSize ) { if ( newSize >= this . size ) { return ; } if ( newSize === 0 ) { this . clear ( ) ; return ; } let current = this . _head ; let currentSize = this . size ; while ( current && currentSize > newSize ) { this . _map . delete ( current . key ) ; current = current . next ; currentSize -- ; } this . _head = current ; this . _size = currentSize ; if ( current ) { current . previous = void 0 ; } } private addItemFirst ( item ) { if ( ! this . _head && ! this . _tail ) { this . _tail = item ; } else if ( ! this . _head ) { throw new Error ( 'Invalid list' ) ; } else { item . next = this . _head ; this . _head . previous = item ; } this . _head = item ; } private addItemLast ( item ) { if ( ! this . _head && ! this . _tail ) { this . _head = item ; } else if ( ! this . _tail ) { throw new Error ( 'Invalid list' ) ; } else { item . previous = this . _tail ; this . _tail . next = item ; } this . _tail = item ; } private removeItem ( item ) { if ( item === this . _head && item === this . _tail ) { this . _head = void 0 ; this . _tail = void 0 ; } else if ( item === this . _head ) { this . _head = item . next ; } else if ( item === this . _tail ) { this . _tail = item . previous ; } else { const next = item . next ; const previous = item . previous ; if ( ! next || ! previous ) { throw new Error ( 'Invalid list' ) ; } next . previous = previous ; previous . next = next ; } } private touch ( item , touch ) { if ( ! this . _head || ! this . _tail ) { throw new Error ( 'Invalid list' ) ; } if ( ( touch !== Touch . AsOld && touch !== Touch . AsNew ) ) { return ; } if ( touch === Touch . AsOld ) { if ( item === this . _head ) { return ; } const next = item . next ; const previous = item . previous ; if ( item === this . _tail ) { previous ! . next = void 0 ; this . _tail = previous ; } else { next ! . previous = previous ; previous ! . next = next ; } item . previous = void 0 ; item . next = this . _head ; this . _head . previous = item ; this . _head = item ; } else if ( touch === Touch . AsNew ) { if ( item === this . _tail ) { return ; } const next = item . next ; const previous = item . previous ; if ( item === this . _head ) { next ! . previous = void 0 ; this . _head = next ; } else { next ! . previous = previous ; previous ! . next = next ; } item . next = void 0 ; item . previous = this . _tail ; this . _tail . next = item ; this . _tail = item ; } } public toJSON ( ) { const data = [ ] ; this . forEach ( ( value , key ) => { data . push ( [ key , value ] ) ; } ) ; return data ; } public fromJSON ( data ) { this . clear ( ) ; for ( const [ key , value ] of data ) { this . set ( key , value ) ; } } } export class LRUCache < K , V > extends LinkedMap < K , V > { private _limit : number ; private _ratio : number ; constructor ( limit , ratio = 1 ) { super ( ) ; this . _limit = limit ; this . _ratio = Math . min ( Math . max ( 0 , ratio ) , 1 ) ; } public get limit ( ) : number { return this . _limit ; } public set limit ( limit ) { this . _limit = limit ; this . checkTrim ( ) ; } public get ratio ( ) : number { return this . _ratio ; } public set ratio ( ratio ) { this . _ratio = Math . min ( Math . max ( 0 , ratio ) , 1 ) ; this . checkTrim ( ) ; } public get ( key ) { return super . get ( key , Touch . AsNew ) ; } public peek ( key ) { return super . get ( key , Touch . None ) ; } public set ( key , value ) { super . set ( key , value , Touch . AsNew ) ; this . checkTrim ( ) ; } private checkTrim ( ) { if ( this . size > this . _limit ) { this . trimOld ( Math . round ( this . _limit * this . _ratio ) ) ; } } }