Source: collections/Cache.js

  1. const { Dictionary, DictionaryMapBased, symbolDictionaryGet } = require('./Dictionary')
  2. , { EqualityComparer } = require('./EqualityComparer')
  3. , { Resolve } = require('../tools/Resolve')
  4. , { CollectionEvent } = require('./Collection')
  5. , { Observable, fromEvent } = require('rxjs')
  6. , symbolCacheEvict = Symbol('cacheEvict')
  7. , JSBI = require('jsbi');
  10. /**
  11.  * This enumeration holds supported eviction policies by some of collections.
  12.  * 
  13.  * @readonly
  14.  * @enum {Number}
  15.  */
  16. const EvictionPolicy = {
  17. 	/**
  18. 	 * Do not evict. Requires manually freeing space in the underlying collection.
  19. 	 */
  20. 	None: 0,
  21. 	/**
  22. 	 * The underlying collection may evict elements indeterministically.
  23. 	 */
  24. 	Undetermined: 1,
  25. 	/**
  26. 	 * The underlying collection evicts the least recently used elements first.
  27. 	 */
  28. 	LRU: 2,
  29. 	/**
  30. 	 * The underlying collection evicts the most recently used elements first.
  31. 	 */
  32. 	MRU: 3,
  33. 	/**
  34. 	 * The underlying collection evicts the least frequently used elements first.
  35. 	 */
  36. 	LFU: 4,
  37. 	/**
  38. 	 * The underlying collection evicts the most frequently used elements first.
  39. 	 */
  40. 	MFU: 5,
  41. 	/**
  42. 	 * The underlying collection evicts the items inserted first (like a queue).
  43. 	 */
  44. 	FIFO: 6,
  45. 	/**
  46. 	 * The underlying collection evicts the items inserted last (like a stack).
  47. 	 */
  48. 	LIFO: 7,
  49. 	/**
  50. 	 * The underlying collection evicts the items inserted in a random order.
  51. 	 */
  52. 	Random: 8
  53. };
  56. /**
  57.  * @template T
  58.  * @author Sebastian Hönel <development@hoenel.net>
  59.  */
  60. class CacheItem {
  61. 	/**
  62. 	 * @param {Cache<any, T>|CacheMapBased<any, T>|CacheWithLoad<any, T>} cache The cache this item belongs to.
  63. 	 * @param {TKey} key
  64. 	 * @param {T} item
  65. 	 * @param {Number} order An integer used to order this item, assigned by the cache.
  66. 	 * @param {Number} expireAfterMsecs An integer, in milliseconds, to expire this
  67. 	 * item after. Only used if > 0. This item then sets a timeout and upon elapse,
  68. 	 * evicts itself from the cache.
  69. 	 */
  70. 	constructor(cache, key, item, order, expireAfterMsecs) {
  71. 		/** @protected */
  72. 		this._cache = cache;
  73. 		/** @protected */
  74. 		this._key = key;
  75. 		/** @protected */
  76. 		this._item = item;
  77. 		// initialize with order, so that newer items w/o last access have larger values.
  78. 		/**
  79. 		 * @type {JSBI.BigInt}
  80. 		 * @protected
  81. 		 */
  82. 		this._timeStamp = JSBI.BigInt(order);
  83. 		/** @protected */
  84. 		this._order = order;
  85. 		/** @protected */
  86. 		this._accessCount = 0;
  88. 		/**
  89. 		 * @type {NodeJS.Timeout}
  90. 		 * @protected
  91. 		 */
  92. 		this._expireTimeout = null;
  93. 		if (expireAfterMsecs > 0) {
  94. 			this._expireTimeout = setTimeout(() => {
  95. 				this._cache.delete(key);
  96. 			}, expireAfterMsecs);
  97. 		}
  98. 	};
  100. 	/**
  101. 	 * Clears the internal eviction timeout.
  102. 	 * 
  103. 	 * @returns {this}
  104. 	 */
  105. 	clearTimeout() {
  106. 		clearTimeout(this._expireTimeout);
  107. 		this._expireTimeout = null;
  108. 		return this;
  109. 	};
  111. 	/**
  112. 	 * @type {String|Symbol}
  113. 	 */
  114. 	get key() {
  115. 		return this._key;
  116. 	};
  117. 	
  118. 	/**
  119. 	 * @type {T}
  120. 	 */
  121. 	get item() {
  122. 		return this._item;
  123. 	};
  125. 	/**
  126. 	 * @type {JSBI.BigInt}
  127. 	 */
  128. 	get timeStamp() {
  129. 		return this._timeStamp;
  130. 	};
  132. 	/**
  133. 	 * @returns {void}
  134. 	 */
  135. 	updateAccessTime() {
  136. 		const hrTime = process.hrtime()
  137. 		, secsAsNano = JSBI.multiply(JSBI.BigInt(hrTime[0]), JSBI.BigInt(1e9))
  138. 		, withNs = JSBI.add(secsAsNano, JSBI.BigInt(hrTime[1]));
  140. 		this._timeStamp = withNs;
  141. 	};
  143. 	/**
  144. 	 * @type {Number}
  145. 	 */
  146. 	get order() {
  147. 		return this._order;
  148. 	};
  150. 	/**
  151. 	 * @type {Number}
  152. 	 */
  153. 	get accessCount() {
  154. 		return this._accessCount;
  155. 	};
  157. 	/**
  158. 	 * @returns {this}
  159. 	 */
  160. 	increaseAccessCount() {
  161. 		this._accessCount++;
  162. 		return this;
  163. 	};
  164. };
  168. let __counter = 0;
  170. /**
  171.  * @deprecated Use @see {CacheMapBased} instead. This class will be
  172.  * removed from Version v3.0.
  173.  * A Cache is similar to a @see {DictionaryMapBased}, and also allows to manually and automatically
  174.  * evict items stored in it. A Cache's capacity is constrained.
  175.  * 
  176.  * @template TKey
  177.  * @template TVal
  178.  * @extends {Dictionary<TKey, TVal>}
  179.  * @author Sebastian Hönel <development@hoenel.net>
  180.  */
  181. class Cache extends Dictionary {
  182. 	/**
  183. 	 * Used to assign a running number to new cache items.
  184. 	 * @private
  185. 	 * @type {Number}
  186. 	 */
  187. 	static get __counter() {
  188. 		return __counter++;
  189. 	};
  192. 	/**
  193. 	 * Creates a new, empty Cache<T>, using the specified @see {EvictionPolicy} and
  194. 	 * an initial capacity.
  195. 	 * 
  196. 	 * @param {EvictionPolicy|Number} [evictPolicy] Optional. Specify the eviction policy that is
  197. 	 * applied, if the cache has no more space left.
  198. 	 * @param {Number} [capacity] Optional. Specify the initial capacity of this cache. The capacity
  199. 	 * can be increased and decreased later.
  200. 	 * @param {EqualityComparer<TVal>} [eqComparer] Optional. Defaults To EqualityComparer<TVal>.default.
  201. 	 */
  202. 	constructor(evictPolicy = EvictionPolicy.None, capacity = Number.MAX_SAFE_INTEGER, eqComparer = EqualityComparer.default) {
  203. 		super(eqComparer);
  204. 		
  205. 		/**
  206. 		 * @type {EvictionPolicy|Number}
  207. 		 * @protected
  208. 		 */
  209. 		this._evictPolicy = EvictionPolicy.None;
  210. 		this.evictionPolicy = evictPolicy;
  212. 		/**
  213. 		 * @type {Number}
  214. 		 * @protected
  215. 		 */
  216. 		this._capacity = capacity;
  217. 		this.capacity = capacity;
  219. 		/**
  220. 		 * @type {Object<String|Symbol, CacheItem<T>>}
  221. 		 * @protected
  222. 		 */
  223. 		this._dict = {};
  224. 	};
  225. 	
  226. 	/**
  227. 	 * @param {EvictionPolicy|Number} policy An @see {EvictionPolicy}
  228. 	 * @throws {Error} If the given policy is not one of @see {EvictionPolicy}.
  229. 	 * @protected
  230. 	 */
  231. 	_validateEvictionPolicy(policy) {
  232. 		switch (policy) {
  233. 			case EvictionPolicy.LRU:
  234. 			case EvictionPolicy.MRU:
  235. 			case EvictionPolicy.LFU:
  236. 			case EvictionPolicy.MFU:
  237. 			case EvictionPolicy.None:
  238. 			case EvictionPolicy.FIFO:
  239. 			case EvictionPolicy.LIFO:
  240. 			case EvictionPolicy.Random:
  241. 			case EvictionPolicy.Undetermined:
  242. 				break;
  243. 			default:
  244. 				throw new Error(`The eviction policy '${policy}' is not supported.`);
  245. 		}
  246. 	};
  248. 	/**
  249. 	 * Get the current @see {EvictionPolicy}.
  250. 	 * 
  251. 	 * @type {EvictionPolicy|Number}
  252. 	 */
  253. 	get evictionPolicy() {
  254. 		return this._evictPolicy;
  255. 	};
  257. 	/**
  258. 	 * Set the current @see {EvictionPolicy}.
  259. 	 * 
  260. 	 * @param {EvictionPolicy|Number} policy The new policy to use for evicting items.
  261. 	 * @type {void}
  262. 	 */
  263. 	set evictionPolicy(policy) {
  264. 		this._validateEvictionPolicy(policy);
  265. 		this._evictPolicy = policy;
  266. 	};
  268. 	/**
  269. 	 * @param {Number} capacity The capacity to check. Must be a positive integer.
  270. 	 * @throws {Error} If the given capacity is not an integer or less than zero.
  271. 	 * @protected
  272. 	 */
  273. 	_validateCapacity(capacity) {
  274. 		if (!Resolve.isTypeOf(capacity, Number) || !Number.isInteger(capacity)) {
  275. 			throw new Error(`The value given for capacity is not a number.`);
  276. 		}
  277. 		if (capacity < 0) {
  278. 			throw new Error(`The capacity given is less than 0: ${capacity}`);
  279. 		}
  280. 	};
  282. 	/**
  283. 	 * Returns the current capacity of this cache.
  284. 	 * 
  285. 	 * @type {Number}
  286. 	 */
  287. 	get capacity() {
  288. 		return this._capacity;
  289. 	};
  291. 	/**
  292. 	 * Returns true, if the cache's capacity is all used up.
  293. 	 * 
  294. 	 * @type {Boolean}
  295. 	 */
  296. 	get isFull() {
  297. 		return this.size === this.capacity;
  298. 	};
  300. 	/**
  301. 	 * @param {Number} capacity The new capacity of this cache. Must be a positive
  302. 	 * integer (0 is allowed). Note that setting a capacity that undercuts the amount
  303. 	 * of items currently held in the cache, will lead to the eviction of enough
  304. 	 * items to meet the new capacity constraint.
  305. 	 * @type {void}
  306. 	 */
  307. 	set capacity(capacity) {
  308. 		this._validateCapacity(capacity);
  310. 		let toEvict = this.size - capacity;
  311. 		if (toEvict > 0 && this.evictionPolicy === EvictionPolicy.None) {
  312. 			throw new Error('Cannot decrease capacity and automatically evict items with policy set to None.');
  313. 		}
  314. 		while (toEvict > 0) {
  315. 			this.evict();
  316. 			toEvict--;
  317. 		}
  319. 		this._capacity = capacity;
  320. 	};
  322. 	/**
  323. 	 * @returns {T} the evicted item.
  324. 	 */
  325. 	evict() {
  326. 		if (this.isEmpty) {
  327. 			throw new Error('The cache is empty, cannot evict any more items.');
  328. 		}
  329. 		return this.evictMany(1)[0];
  330. 	};
  332. 	/**
  333. 	 * @param {Number} count
  334. 	 * @returns {Array<T>} The evicted items in an array.
  335. 	 */
  336. 	evictMany(count) {
  337. 		let howMany = Math.min(count, this.size);
  338. 		/** @type {Array<T>} */
  339. 		const items = [];
  341. 		for (const item of this._evictNext()) {
  342. 			items.push(this.remove(item.key));
  343. 			if (--howMany === 0) {
  344. 				break;
  345. 			}
  346. 		}
  348. 		return items;
  349. 	};
  351. 	/**
  352. 	 * Allows to peek at the next n items that will be evited next, without removing
  353. 	 * them. Returns the items with as key/value pair.
  354. 	 * 
  355. 	 * @param {Number} amount
  356. 	 * @returns {Array<Object<String|Symbol, T>>}
  357. 	 */
  358. 	peekEvict(amount) {
  359. 		if (!Resolve.isTypeOf(amount, Number) || !Number.isInteger(amount) || amount < 1) {
  360. 			throw new Error('You must peek an mount larger than 0.');
  361. 		}
  363. 		amount = Math.min(amount, this.size);
  364. 		const iter = this._evictNext();
  365. 		return Array.from(Array(amount), iter.next, iter).map(o => {
  366. 			const obj = {};
  367. 			obj[o.value.key] = o.value.item;
  368. 			return obj;
  369. 		});
  370. 	};
  372. 	/**
  373. 	 * Returns items in the order they will be evicted, according to the policy.
  374. 	 * 
  375. 	 * @protected
  376. 	 * @returns {IterableIterator<CacheItem<T>>}
  377. 	 */
  378. 	*_evictNext() {
  379. 		/** @type {Array<CacheItem<T>>} */
  380. 		const wrappers = [];
  382. 		switch (this.evictionPolicy) {
  383. 			case EvictionPolicy.LRU:
  384. 			case EvictionPolicy.MRU:
  385. 				// Order items by their access date:
  386. 				const mru = this.evictionPolicy === EvictionPolicy.MRU ? -1 : 1;
  387. 				this.evictionPolicy === EvictionPolicy.MRU ? -1 : 1;
  388. 				wrappers.unshift(
  389. 					...Array.from(super.values()).sort((w1, w2) => {
  390. 						return mru * (JSBI.lessThan(w1.timeStamp, w2.timeStamp) ? -1 : 1);
  391. 					})
  392. 				);
  393. 				break;
  394. 			case EvictionPolicy.LFU:
  395. 			case EvictionPolicy.MFU:
  396. 				// Order items by access count and select least/most recently used items first.
  397. 				const mfu = this.evictionPolicy === EvictionPolicy.MFU ? -1 : 1;
  398. 				wrappers.unshift(
  399. 					...Array.from(super.values()).sort((w1, w2) => {
  400. 						return mfu * (w1.accessCount - w2.accessCount);
  401. 					})
  402. 				);
  403. 				break;
  404. 			case EvictionPolicy.FIFO:
  405. 			case EvictionPolicy.LIFO:
  406. 				// Remove the item inserted first/last.
  407. 				const lifo = this.evictionPolicy === EvictionPolicy.LIFO ? -1 : 1;
  408. 				wrappers.unshift(
  409. 					...Array.from(super.values()).sort((w1, w2) => {
  410. 						return lifo * (w1.order - w2.order);
  411. 					})
  412. 				);
  413. 				break;
  414. 			case EvictionPolicy.Undetermined:
  415. 				// No specific/deterministic order.
  416. 				yield* super.values();
  417. 				break;
  418. 			case EvictionPolicy.Random:
  419. 				// Randomly select items to evict:
  420. 				wrappers.unshift(
  421. 					...Array.from(super.values()).sort(() => {
  422. 						return Math.random() < .5 ? 1 : -1;
  423. 					})
  424. 				);
  425. 				break;
  426. 			case EvictionPolicy.None:
  427. 				// Eviction not allowed, must use ::remove()
  428. 				throw new Error('Eviction not allowed.');
  429. 		}
  431. 		for (const wrap of wrappers) {
  432. 			yield wrap;
  433. 		}
  434. 	};
  436. 	/**
  437. 	 * @override
  438. 	 * @inheritdoc
  439. 	 * @param {Number} [expireAfterMsecs] Optional. if given a positive integer, then it
  440. 	 * will be used as the amount of milliseconds this entry will expire and remove itself
  441. 	 * from the cache.
  442. 	 * @throws {Error} If this cache is full and no automatic eviction policy was set.
  443. 	 * @type {void}
  444. 	 */
  445. 	set(key, val, expireAfterMsecs = void 0) {
  446. 		const isFull = this.size === this.capacity;
  447. 		if (isFull) {
  448. 			if (this.evictionPolicy === EvictionPolicy.None) {
  449. 				throw new Error(`The Cache is full and no automatic eviction policy is set.`);
  450. 			}
  452. 			this.evict(); // Remove one item according to an automatic policy.
  453. 		}
  455. 		if (!Resolve.isNumber(expireAfterMsecs) || !Number.isSafeInteger(expireAfterMsecs) || expireAfterMsecs < 0) {
  456. 			expireAfterMsecs = -1;
  457. 		}
  459. 		const wrap = new CacheItem(this, key, val, Cache.__counter, expireAfterMsecs);
  461. 		return super.set(key, wrap);
  462. 	};
  464. 	/**
  465. 	 * @override
  466. 	 * @inheritdoc
  467. 	 */
  468. 	get(key) {
  469. 		/** @type {CacheItem<T>} */
  470. 		const wrap = super.get(key);
  471. 		wrap.updateAccessTime();
  472. 		wrap.increaseAccessCount();
  473. 		return wrap.item;
  474. 	};
  476. 	/**
  477. 	 * @override
  478. 	 * @inheritdoc
  479. 	 */
  480. 	remove(key) {
  481. 		/** @type {CacheItem<T>} */
  482. 		const wrap = super.remove(key);
  483. 		wrap.clearTimeout();
  484. 		return wrap.item;
  485. 	};
  487. 	/**
  488. 	 * @override
  489. 	 * @inheritdoc
  490. 	 */
  491. 	*values() {
  492. 		for (const val of super.values()) {
  493. 			yield val.item;
  494. 		}
  495. 	};
  497. 	/**
  498. 	 * @override
  499. 	 * @inheritdoc
  500. 	 * @protected
  501. 	 */
  502. 	*_entries(reverse = false) {
  503. 		for (const entry of super._entries(reverse)) {
  504. 			const key = Object.keys(entry).concat(Object.getOwnPropertySymbols(entry))[0];
  505. 			entry[key] = entry[key].item; // unwrap
  506. 			yield entry;
  507. 		}
  508. 	};
  509. };
  513. let __counterCb = 0;
  515. /**
  516.  * @template TKey
  517.  * @template TVal
  518.  * @extends {DictionaryMapBased<TKey, TVal>}
  519.  * @author Sebastian Hönel <development@hoenel.net>
  520.  */
  521. class CacheMapBased extends DictionaryMapBased {
  522. 	/**
  523. 	 * Used to assign a running number to new cache items.
  524. 	 * @private
  525. 	 * @type {Number}
  526. 	 */
  527. 	static get __counter() {
  528. 		return __counterCb++;
  529. 	};
  532. 	/**
  533. 	 * Creates a new, empty CacheMapBased<TKey, TVal>, using the specified @see {EvictionPolicy} and
  534. 	 * an initial capacity.
  535. 	 * 
  536. 	 * @param {EvictionPolicy|Number} [evictPolicy] Optional. Specify the eviction policy that is
  537. 	 * applied, if the cache has no more space left.
  538. 	 * @param {Number} [capacity] Optional. Specify the initial capacity of this cache. The capacity
  539. 	 * can be increased and decreased later.
  540. 	 * @param {EqualityComparer<TVal>} [eqComparer] Optional. Defaults To EqualityComparer<TVal>.default.
  541. 	 */
  542. 	constructor(evictPolicy = EvictionPolicy.None, capacity = Number.MAX_SAFE_INTEGER, eqComparer = EqualityComparer.default) {
  543. 		super(eqComparer);
  544. 		
  545. 		/**
  546. 		 * @type {EvictionPolicy|Number}
  547. 		 * @protected
  548. 		 */
  549. 		this._evictPolicy = EvictionPolicy.None;
  550. 		this.evictionPolicy = evictPolicy;
  552. 		/**
  553. 		 * @type {Number}
  554. 		 * @protected
  555. 		 */
  556. 		this._capacity = capacity;
  557. 		this.capacity = capacity;
  559. 		/**
  560. 		 * @type {Map<TKey, CacheItem<TVal>>}
  561. 		 * @protected
  562. 		 */
  563. 		this._map = new Map();
  565. 		/** @type {Observable<CollectionEvent<Array<TVal>>>} */
  566. 		this.observableEvict = Object.freeze(fromEvent(this, symbolCacheEvict));
  567. 	};
  568. 	
  569. 	/**
  570. 	 * @param {EvictionPolicy|Number} policy An @see {EvictionPolicy}
  571. 	 * @throws {Error} If the given policy is not one of @see {EvictionPolicy}.
  572. 	 * @protected
  573. 	 */
  574. 	_validateEvictionPolicy(policy) {
  575. 		switch (policy) {
  576. 			case EvictionPolicy.LRU:
  577. 			case EvictionPolicy.MRU:
  578. 			case EvictionPolicy.LFU:
  579. 			case EvictionPolicy.MFU:
  580. 			case EvictionPolicy.None:
  581. 			case EvictionPolicy.FIFO:
  582. 			case EvictionPolicy.LIFO:
  583. 			case EvictionPolicy.Random:
  584. 			case EvictionPolicy.Undetermined:
  585. 				break;
  586. 			default:
  587. 				throw new Error(`The eviction policy '${policy}' is not supported.`);
  588. 		}
  589. 	};
  591. 	/**
  592. 	 * @type {EvictionPolicy|Number}
  593. 	 */
  594. 	get evictionPolicy() {
  595. 		return this._evictPolicy;
  596. 	};
  598. 	/**
  599. 	 * @param {EvictionPolicy|Number} policy The new policy to use for evicting items.
  600. 	 */
  601. 	set evictionPolicy(policy) {
  602. 		this._validateEvictionPolicy(policy);
  603. 		this._evictPolicy = policy;
  604. 	};
  606. 	/**
  607. 	 * @param {Number} capacity The capacity to check. Must be a positive integer.
  608. 	 * @throws {Error} If the given capacity is not an integer or less than zero.
  609. 	 * @protected
  610. 	 */
  611. 	_validateCapacity(capacity) {
  612. 		if (!Resolve.isTypeOf(capacity, Number) || !Number.isInteger(capacity)) {
  613. 			throw new Error(`The value given for capacity is not a number.`);
  614. 		}
  615. 		if (capacity < 0) {
  616. 			throw new Error(`The capacity given is less than 0: ${capacity}`);
  617. 		}
  618. 	};
  620. 	/**
  621. 	 * Returns the current capacity of this cache.
  622. 	 * 
  623. 	 * @type {Number}
  624. 	 */
  625. 	get capacity() {
  626. 		return this._capacity;
  627. 	};
  629. 	/**
  630. 	 * Returns true, if the cache's capacity is all used up.
  631. 	 * 
  632. 	 * @type {Boolean}
  633. 	 */
  634. 	get isFull() {
  635. 		return this.size === this.capacity;
  636. 	};
  638. 	/**
  639. 	 * @param {Number} capacity The new capacity of this cache. Must be a positive
  640. 	 * integer (0 is allowed). Note that setting a capacity that undercuts the amount
  641. 	 * of items currently held in the cache, will lead to the eviction of enough
  642. 	 * items to meet the new capacity constraint.
  643. 	 * @type {void}
  644. 	 */
  645. 	set capacity(capacity) {
  646. 		this._validateCapacity(capacity);
  648. 		let toEvict = this.size - capacity;
  649. 		if (toEvict > 0 && this.evictionPolicy === EvictionPolicy.None) {
  650. 			throw new Error('Cannot decrease capacity and automatically evict items with policy set to None.');
  651. 		}
  652. 		while (toEvict > 0) {
  653. 			this.evict();
  654. 			toEvict--;
  655. 		}
  657. 		this._capacity = capacity;
  658. 	};
  660. 	/**
  661. 	 * @returns {T} the evicted item.
  662. 	 */
  663. 	evict() {
  664. 		if (this.isEmpty) {
  665. 			throw new Error('The cache is empty, cannot evict any more items.');
  666. 		}
  667. 		return this.evictMany(1)[0];
  668. 	};
  670. 	/**
  671. 	 * @param {Number} count
  672. 	 * @returns {Array<T>} The evicted items in an array.
  673. 	 */
  674. 	evictMany(count) {
  675. 		let howMany = Math.min(count, this.size);
  676. 		/** @type {Array<T>} */
  677. 		const items = [];
  679. 		for (const item of this._evictNext()) {
  680. 			items.push(this.delete(item.key));
  681. 			if (--howMany === 0) {
  682. 				break;
  683. 			}
  684. 		}
  686. 		this.emit(symbolCacheEvict, new CollectionEvent(items.slice(0)));
  688. 		return items;
  689. 	};
  691. 	/**
  692. 	 * Allows to peek at the next n items that will be evicted next, without
  693. 	 * removing them. Returns the items as key/value pair.
  694. 	 * 
  695. 	 * @param {Number} amount
  696. 	 * @returns {Array<[TKey, TVal]>}
  697. 	 */
  698. 	peekEvict(amount) {
  699. 		if (!Resolve.isTypeOf(amount, Number) || !Number.isInteger(amount) || amount < 1) {
  700. 			throw new Error('You must peek an mount larger than 0.');
  701. 		}
  703. 		amount = Math.min(amount, this.size);
  704. 		const iter = this._evictNext();
  705. 		return Array.from(Array(amount), iter.next, iter).map(o => {
  706. 			return [o.value.key, o.value.item];
  707. 		});
  708. 	};
  710. 	/**
  711. 	 * Returns items in the order they will be evicted, according to the policy.
  712. 	 * 
  713. 	 * @protected
  714. 	 * @returns {IterableIterator<CacheItem<TVal>>}
  715. 	 */
  716. 	*_evictNext() {
  717. 		/** @type {Array<CacheItem<TVal>>} */
  718. 		const wrappers = [];
  720. 		switch (this.evictionPolicy) {
  721. 			case EvictionPolicy.LRU:
  722. 			case EvictionPolicy.MRU:
  723. 				// Order items by their access date:
  724. 				const mru = this.evictionPolicy === EvictionPolicy.MRU ? -1 : 1;
  725. 					this.evictionPolicy === EvictionPolicy.MRU ? -1 : 1;
  726. 				wrappers.unshift(
  727. 					...Array.from(super.values()).sort((w1, w2) => {
  728. 						return mru * (JSBI.lessThan(w1.timeStamp, w2.timeStamp) ? -1 : 1);
  729. 					})
  730. 				);
  731. 				break;
  732. 			case EvictionPolicy.LFU:
  733. 			case EvictionPolicy.MFU:
  734. 				// Order items by access count and select least/most recently used items first.
  735. 				const mfu = this.evictionPolicy === EvictionPolicy.MFU ? -1 : 1;
  736. 				wrappers.unshift(
  737. 					...Array.from(super.values()).sort((w1, w2) => {
  738. 						return mfu * (w1.accessCount - w2.accessCount);
  739. 					})
  740. 				);
  741. 				break;
  742. 			case EvictionPolicy.FIFO:
  743. 			case EvictionPolicy.LIFO:
  744. 				// Remove the item inserted first/last.
  745. 				const lifo = this.evictionPolicy === EvictionPolicy.LIFO ? -1 : 1;
  746. 				wrappers.unshift(
  747. 					...Array.from(super.values()).sort((w1, w2) => {
  748. 						return lifo * (w1.order - w2.order);
  749. 					})
  750. 				);
  751. 				break;
  752. 			case EvictionPolicy.Undetermined:
  753. 				// No specific/deterministic order.
  754. 				yield* super.values();
  755. 				break;
  756. 			case EvictionPolicy.Random:
  757. 				// Randomly select items to evict:
  758. 				wrappers.unshift(
  759. 					...Array.from(super.values()).sort(() => {
  760. 						return Math.random() < .5 ? 1 : -1;
  761. 					})
  762. 				);
  763. 				break;
  764. 			case EvictionPolicy.None:
  765. 				// Eviction not allowed, must use ::remove()
  766. 				throw new Error('Eviction not allowed.');
  767. 		}
  769. 		for (const wrap of wrappers) {
  770. 			yield wrap;
  771. 		}
  772. 	};
  774. 	/**
  775. 	 * @override
  776. 	 * @inheritdoc
  777. 	 * @param {Number} [expireAfterMsecs] Optional. if given a positive integer, then it
  778. 	 * will be used as the amount of milliseconds this entry will expire and remove itself
  779. 	 * from the cache.
  780. 	 * @throws {Error} If this cache is full and no automatic eviction policy was set.
  781. 	 */
  782. 	set(key, val, expireAfterMsecs = void 0) {
  783. 		const isFull = this.size === this.capacity;
  784. 		if (isFull) {
  785. 			if (this.evictionPolicy === EvictionPolicy.None) {
  786. 				throw new Error(`The Cache is full and no automatic eviction policy is set.`);
  787. 			}
  789. 			this.evict(); // Remove one item according to an automatic policy.
  790. 		}
  792. 		if (!Resolve.isNumber(expireAfterMsecs) || !Number.isSafeInteger(expireAfterMsecs) || expireAfterMsecs < 0) {
  793. 			expireAfterMsecs = -1;
  794. 		}
  796. 		const wrap = new CacheItem(this, key, val, CacheMapBased.__counter, expireAfterMsecs);
  798. 		return super.set(key, wrap);
  799. 	};
  801. 	/**
  802. 	 * @override
  803. 	 * @inheritdoc
  804. 	 */
  805. 	get(key) {
  806. 		const wrap = this._map.get(key);
  807. 		wrap.updateAccessTime();
  808. 		wrap.increaseAccessCount();
  810. 		const value = this.__unwrapValue(wrap);
  811. 		this.emit(symbolDictionaryGet, new CollectionEvent([key, value]));
  812. 		return value;
  813. 	};
  815. 	/**
  816. 	 * @override
  817. 	 * @inheritdoc
  818. 	 */
  819. 	*values() {
  820. 		for (const val of super.values()) {
  821. 			yield this.__unwrapValue(val);
  822. 		}
  823. 	};
  825. 	/**
  826. 	 * @override
  827. 	 * @inheritdoc
  828. 	 */
  829. 	*entries() {
  830. 		for (const entry of super.entries()) {
  831. 			yield [entry[0], this.__unwrapValue(entry[1])];
  832. 		}
  833. 	};
  835. 	/**
  836. 	 * @private
  837. 	 * @override
  838. 	 * @inheritdoc
  839. 	 * @param {CacheItem<TVal>} value
  840. 	 * @returns {TVal} The wrapped value
  841. 	 */
  842. 	__unwrapValue(value) {
  843. 		return value.item;
  844. 	};
  845. };
  849. /**
  850.  * @template T
  851.  * @extends {CacheItem<T>}
  852.  * @author Sebastian Hönel <development@hoenel.net>
  853.  */
  854. class CacheItemWithLoad extends CacheItem {
  855. 	/**
  856. 	 * @inheritdoc
  857. 	 * @param {T} item
  858. 	 * @param {Number} load 
  859. 	 */
  860. 	constructor(cache, key, item, order, expireAfterMsecs, load) {
  861. 		super(cache, key, item, order, expireAfterMsecs);
  863. 		/** @protected */
  864. 		this._load = load;
  865. 	};
  867. 	/**
  868. 	 * @type {Number}
  869. 	 */
  870. 	get load() {
  871. 		return this._load;
  872. 	};
  873. };
  876. /**
  877.  * A CacheWithLoad introduces a second concept to constrain the capacity
  878.  * of it. This second concept of load is useful for when the size of the
  879.  * items to cache is not known, and when the sheer amount of items does
  880.  * not allow to estimate the load. The CacheWithLoad evicts items when
  881.  * either its capacity is exhausted or the maximum load is exceeded.
  882.  * 
  883.  * @template TKey
  884.  * @template TVal
  885.  * @extends {CacheMapBased<TKey, TVal>}
  886.  * @author Sebastian Hönel <development@hoenel.net>
  887.  */
  888. class CacheWithLoad extends CacheMapBased {
  889. 	/**
  890. 	 * @inheritdoc
  891. 	 * @param {EvictionPolicy|Number} evictPolicy
  892. 	 * @param {Number} capacity
  893. 	 * @param {Number} maxLoad The maximum load, expressed as a positive number.
  894. 	 * @param {EqualityComparer<TVal>} eqComparer
  895. 	 */
  896. 	constructor(evictPolicy = EvictionPolicy.None, capacity = Number.MAX_SAFE_INTEGER, maxLoad = Number.MAX_VALUE, eqComparer = EqualityComparer.default) {
  897. 		super(evictPolicy, capacity, eqComparer);
  899. 		/** @protected */
  900. 		this._maxLoad = maxLoad;
  901. 		this.maxLoad = maxLoad;
  903. 		/**
  904. 		 * @type {Object<String|Symbol, CacheItemWithLoad<T>>}
  905. 		 * @protected
  906. 		 */
  907. 		this._dict = {};
  908. 	};
  910. 	/**
  911. 	 * @protected
  912. 	 * @param {Number} load
  913. 	 */
  914. 	_validateLoad(load) {
  915. 		if (!Resolve.isTypeOf(load, Number) || !Number.isFinite(load)) {
  916. 			throw new Error(`The value given for load is not a number.`);
  917. 		}
  918. 		if (load <= 0) {
  919. 			throw new Error(`The value given for load must be greater than zero.`);
  920. 		}
  921. 	};
  923. 	/**
  924. 	 * Returns the current load.
  925. 	 * 
  926. 	 * @type {Number}
  927. 	 */
  928. 	get load() {
  929. 		return Array.from(
  930. 			// To avoid unwrapping:
  931. 			DictionaryMapBased.prototype.values.call(this)
  932. 		).map(ci => ci.load).reduce((a, b) => a + b, 0);
  933. 	};
  935. 	/**
  936. 	 * Returns the current free load (maximum load - current load).
  937. 	 * 
  938. 	 * @type {Number}
  939. 	 */
  940. 	get loadFree() {
  941. 		return this.maxLoad - this.load;
  942. 	};
  944. 	/**
  945. 	 * Set the maximum load.
  946. 	 * 
  947. 	 * @param {Number} maxLoad
  948. 	 * @type {void}
  949. 	 */
  950. 	set maxLoad(maxLoad) {
  951. 		this._validateLoad(maxLoad);
  953. 		if (maxLoad < this.load && this.evictionPolicy === EvictionPolicy.None) {
  954. 			throw new Error('Cannot decrease the maximum load and automatically evict items with policy set to None.');
  955. 		}
  957. 		while (this.load > maxLoad) {
  958. 			this.evict();
  959. 		}
  961. 		this._maxLoad = maxLoad;
  962. 	};
  964. 	/**
  965. 	 * Returns the maximum load.
  966. 	 * 
  967. 	 * @type {Number}
  968. 	 */
  969. 	get maxLoad() {
  970. 		return this._maxLoad;
  971. 	};
  973. 	/**
  974. 	 * @override
  975. 	 * @inheritdoc
  976. 	 * @param {TKey} key
  977. 	 * @param {TVal} val
  978. 	 * @param {Number} load
  979. 	 * @param {Number} [expireAfterMsecs] defaults to undefined. Only used if given
  980. 	 * as a positive integer.
  981. 	 * @returns {this}
  982. 	 */
  983. 	set(key, val, load, expireAfterMsecs = void 0) {
  984. 		this._validateLoad(load);
  986. 		if (load > this.maxLoad) {
  987. 			throw new Error(`The specified load exceeds this cache's maximum load.`);
  988. 		}
  990. 		const isFull = this.size === this.capacity;
  991. 		if (isFull) {
  992. 			if (this.evictionPolicy === EvictionPolicy.None) {
  993. 				throw new Error(`The Cache is full and no automatic eviction policy is set.`);
  994. 			}
  996. 			this.evict(); // Remove one item according to an automatic policy.
  997. 		}
  999. 		if (load + this.load > this.maxLoad) {
  1000. 			if (this.evictionPolicy === EvictionPolicy.None) {
  1001. 				throw new Error(`The Cache's load is too high and no automatic eviction policy is set.`);
  1002. 			}
  1004. 			while (load + this.load > this.maxLoad) {
  1005. 				this.evict();
  1006. 			}
  1007. 		}
  1009. 		if (!Resolve.isNumber(expireAfterMsecs) || !Number.isSafeInteger(expireAfterMsecs) || expireAfterMsecs < 0) {
  1010. 			expireAfterMsecs = -1;
  1011. 		}
  1013. 		const wrap = new CacheItemWithLoad(
  1014. 			this, key, val, CacheMapBased.__counter, expireAfterMsecs, load);
  1016. 		return DictionaryMapBased.prototype.set.call(this, key, wrap);
  1017. 	};
  1018. };
  1021. module.exports = Object.freeze({
  1022. 	EvictionPolicy,
  1023. 	Cache,
  1024. 	CacheMapBased,
  1025. 	CacheItem,
  1026. 	CacheWithLoad,
  1027. 	CacheItemWithLoad
  1028. });