import { assert } from "@here/harp-utils" ; hidden export class Entry < Key , Value > { constructor ( public key , public value , public size , public newer , public older ) { } } /**
 * Fixed size cache that evicts its entries in least-recently-used order when it overflows.
 * Modeled after standard JavaScript `Map` otherwise.
 */ export class LRUCache < Key , Value > { /**
     * Optional callback that is called on every item that is evicted from the cache.
     *
     * **Note**: This callback is not called when an item is explicitly deleted from the map via
     * [[delete]] or [[clear]].
     */ evictionCallback ? : ( key : Key , value : Value ) => void ; /**
     * Optional callback that is called on every item that should be evicted from the cache to
     * determine if it can be removed, or should be locked in the cache.
     *
     * It returns `true` if the item can be removed from cache, `false` otherwise. Locking items in
     * the cache should be a temporary measure, since if the cache is filled with non-evictable
     * items only, it may grow beyond its capacity.
     *
     * **Note**: This callback is not called when an item is explicitly deleted from the map via
     * [[delete]] or [[clear]].
     */ canEvict ? : ( key : Key , value : Value ) => boolean ; private m_capacity : number ; private m_size = 0 ; /**
     * The internal map object that keeps the key-value pairs and their order.
     */ private readonly m_map = new Map < Key , Entry < Key , Value > > ( ) ; /**
     * The newest entry, i.e. the most recently used item.
     */ private m_newest : Entry < Key , Value > | null = null ; /**
     * The oldest entry, i.e. the least recently used item.
     */ private m_oldest : Entry < Key , Value > | null = null ; /**
     * A function determining the size per element.
     */ private m_sizeFunction : ( v : Value ) => number ; param cacheCapacity param sizeFunction constructor ( cacheCapacity , sizeFunction = ( ) => 1 ) { this . m_capacity = cacheCapacity ; this . m_sizeFunction = sizeFunction ; } param callbackfn param thisArg forEach ( callbackfn , thisArg ? ) { let entry = this . m_newest ; while ( entry !== null ) { const older = entry . older ; callbackfn . call ( thisArg , entry . value , entry . key , this ) ; entry = older ; } } returns get size ( ) : number { return this . m_size ; } returns get capacity ( ) : number { return this . m_capacity ; } deprecated returns get map ( ) : Map < Key , Entry < Key , Value > > { return this . m_map ; } returns get newest ( ) : Entry < Key , Value > | null { return this . m_newest ; } returns get oldest ( ) : Entry < Key , Value > | null { return this . m_oldest ; } param newCapacity setCapacity ( newCapacity ) { this . m_capacity = newCapacity ; this . evict ( ) ; } param newCapacity param sizeMeasure setCapacityAndMeasure ( newCapacity , sizeMeasure = ( ) => 1 ) { this . m_capacity = newCapacity ; this . m_sizeFunction = sizeMeasure ; this . shrinkToCapacity ( ) ; } /**
     * Updates the size of all elements in this cache. If their aggregated size is larger than the
     * capacity, items will be evicted until the cache shrinks to fit the capacity.
     */ shrinkToCapacity ( ) { let size = 0 ; const sizeFunction = this . m_sizeFunction ; let entry = this . m_newest ; while ( entry !== null ) { const entrySize = sizeFunction ( entry . value ) ; entry . size = entrySize ; size += entrySize ; entry = entry . older ; } this . m_size = size ; this . evict ( ) ; } param key param value set ( key , value ) { const valueSize = this . m_sizeFunction ( value ) ; let entry = this . m_map . get ( key ) ; if ( entry !== undefined ) { this . m_size = this . m_size - entry . size + valueSize ; entry . value = value ; entry . size = valueSize ; this . promoteEntry ( entry ) ; this . evict ( ) ; } else { if ( valueSize > this . m_capacity ) { return ; } entry = new Entry < Key , Value > ( key , value , valueSize , null , null ) ; if ( this . m_map . size === 0 ) { this . m_newest = this . m_oldest = entry ; } else { assert ( this . m_newest !== null ) ; const newest = this . m_newest ! ; entry . older = this . m_newest ; newest . newer = entry ; this . m_newest = entry ; } this . m_map . set ( key , entry ) ; this . m_size += valueSize ; this . evict ( ) ; } } param key returns get ( key ) { const entry = this . m_map . get ( key ) ; if ( entry === undefined ) { return undefined ; } this . promoteEntry ( entry ) ; return entry . value ; } param key returns has ( key ) { return this . m_map . has ( key ) ; } /**
     * Clears the cache and removes all stored key-value pairs.
     *
     * Does not call the eviction callback. Use [[evictAll]] to clear the cache and call the
     * eviction callback.
     */ clear ( ) { this . m_newest = this . m_oldest = null ; this . m_size = 0 ; this . m_map . clear ( ) ; } /**
     * Evicts all items from the cache, calling the eviction callback on each item.
     *
     * Use [[clear]] to remove all items without calling the eviction callback.
     */ evictAll ( ) { const cb = this . evictionCallback ; if ( cb !== undefined ) { this . forEach ( ( value , key ) => cb ( key , value ) ) ; } this . clear ( ) ; } param selector param thisArg evictSelected ( selector , thisArg ? ) { const cb = this . evictionCallback ; let entry = this . m_newest ; while ( entry !== null ) { const entryOlder = entry . older ; if ( selector . call ( thisArg , entry . value , entry . key ) ) { if ( cb !== undefined ) { cb ( entry . key , entry . value ) ; } this . deleteEntry ( entry ) ; this . m_map . delete ( entry . key ) ; } entry = entryOlder ; } } param key returns delete ( key ) { const entry = this . m_map . get ( key ) ; if ( entry === undefined ) { return false ; } this . deleteEntry ( entry ) ; return this . m_map . delete ( key ) ; } protected evict ( ) { while ( this . m_oldest !== null && this . m_size > this . m_capacity ) { const evicted = this . evictOldest ( ) ; if ( evicted === undefined ) { return ; } } } protected evictOldest ( ) { assert ( this . m_oldest !== null ) ; const oldest = this . m_oldest ! ; assert ( oldest . older === null ) ; let itemToRemove = oldest ; if ( this . canEvict !== undefined ) { while ( ! this . canEvict ( itemToRemove . key , itemToRemove . value ) ) { if ( itemToRemove . newer === null ) { return undefined ; } itemToRemove = itemToRemove . newer ; } } if ( itemToRemove === oldest ) { this . m_oldest = itemToRemove . newer ; if ( itemToRemove . newer !== null ) { assert ( itemToRemove . newer . older === itemToRemove ) ; itemToRemove . newer . older = null ; } } else { if ( itemToRemove . newer !== null ) { assert ( itemToRemove . newer . older === itemToRemove ) ; itemToRemove . newer . older = itemToRemove . older ; if ( itemToRemove . older !== null ) { itemToRemove . older . newer = itemToRemove . newer ; } } else { return undefined ; } } const isOk = this . m_map . delete ( itemToRemove . key ) ; assert ( isOk === true ) ; if ( isOk && this . evictionCallback !== undefined ) { this . evictionCallback ( itemToRemove . key , itemToRemove . value ) ; } this . m_size -= itemToRemove . size ; return itemToRemove ; } private deleteEntry ( entry ) { if ( entry === this . m_newest ) { this . m_newest = entry . older ; } else if ( entry . newer ) { entry . newer . older = entry . older ; } else { assert ( false ) ; } if ( entry === this . m_oldest ) { this . m_oldest = entry . newer ; } else if ( entry . older ) { entry . older . newer = entry . newer ; } else { assert ( false ) ; } this . m_size -= entry . size ; } private promoteEntry ( entry ) { if ( entry === this . m_newest ) { return ; } if ( entry . newer ) { assert ( entry . newer . older === entry ) ; entry . newer . older = entry . older ; } if ( entry . older ) { assert ( entry . older . newer === entry ) ; entry . older . newer = entry . newer ; } if ( entry === this . m_oldest ) { this . m_oldest = entry . newer ; } entry . newer = null ; entry . older = this . m_newest ; assert ( this . m_newest !== null ) ; const newest = this . m_newest ! ; assert ( newest . newer === null ) ; newest . newer = entry ; this . m_newest = entry ; } }