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.  * @author Sebastian Hönel <development@hoenel.net>
  179.  */
  180. class Cache extends Dictionary {
  181. 	/**
  182. 	 * Used to assign a running number to new cache items.
  183. 	 * @private
  184. 	 * @type {Number}
  185. 	 */
  186. 	static get __counter() {
  187. 		return __counter++;
  188. 	};
  191. 	/**
  192. 	 * Creates a new, empty Cache<T>, using the specified @see {EvictionPolicy} and
  193. 	 * an initial capacity.
  194. 	 * 
  195. 	 * @param {EvictionPolicy|Number} [evictPolicy] Optional. Specify the eviction policy that is
  196. 	 * applied, if the cache has no more space left.
  197. 	 * @param {Number} [capacity] Optional. Specify the initial capacity of this cache. The capacity
  198. 	 * can be increased and decreased later.
  199. 	 * @param {EqualityComparer<TVal>} [eqComparer] Optional. Defaults To EqualityComparer<TVal>.default.
  200. 	 */
  201. 	constructor(evictPolicy = EvictionPolicy.None, capacity = Number.MAX_SAFE_INTEGER, eqComparer = EqualityComparer.default) {
  202. 		super(eqComparer);
  203. 		
  204. 		/**
  205. 		 * @type {EvictionPolicy|Number}
  206. 		 * @protected
  207. 		 */
  208. 		this._evictPolicy = EvictionPolicy.None;
  209. 		this.evictionPolicy = evictPolicy;
  211. 		/**
  212. 		 * @type {Number}
  213. 		 * @protected
  214. 		 */
  215. 		this._capacity = capacity;
  216. 		this.capacity = capacity;
  218. 		/**
  219. 		 * @type {Object<String|Symbol, CacheItem<T>>}
  220. 		 * @protected
  221. 		 */
  222. 		this._dict = {};
  223. 	};
  224. 	
  225. 	/**
  226. 	 * @param {EvictionPolicy|Number} policy An @see {EvictionPolicy}
  227. 	 * @throws {Error} If the given policy is not one of @see {EvictionPolicy}.
  228. 	 * @protected
  229. 	 */
  230. 	_validateEvictionPolicy(policy) {
  231. 		switch (policy) {
  232. 			case EvictionPolicy.LRU:
  233. 			case EvictionPolicy.MRU:
  234. 			case EvictionPolicy.LFU:
  235. 			case EvictionPolicy.MFU:
  236. 			case EvictionPolicy.None:
  237. 			case EvictionPolicy.FIFO:
  238. 			case EvictionPolicy.LIFO:
  239. 			case EvictionPolicy.Random:
  240. 			case EvictionPolicy.Undetermined:
  241. 				break;
  242. 			default:
  243. 				throw new Error(`The eviction policy '${policy}' is not supported.`);
  244. 		}
  245. 	};
  247. 	/**
  248. 	 * Get the current @see {EvictionPolicy}.
  249. 	 * 
  250. 	 * @type {EvictionPolicy|Number}
  251. 	 */
  252. 	get evictionPolicy() {
  253. 		return this._evictPolicy;
  254. 	};
  256. 	/**
  257. 	 * Set the current @see {EvictionPolicy}.
  258. 	 * 
  259. 	 * @param {EvictionPolicy|Number} policy The new policy to use for evicting items.
  260. 	 * @type {void}
  261. 	 */
  262. 	set evictionPolicy(policy) {
  263. 		this._validateEvictionPolicy(policy);
  264. 		this._evictPolicy = policy;
  265. 	};
  267. 	/**
  268. 	 * @param {Number} capacity The capacity to check. Must be a positive integer.
  269. 	 * @throws {Error} If the given capacity is not an integer or less than zero.
  270. 	 * @protected
  271. 	 */
  272. 	_validateCapacity(capacity) {
  273. 		if (!Resolve.isTypeOf(capacity, Number) || !Number.isInteger(capacity)) {
  274. 			throw new Error(`The value given for capacity is not a number.`);
  275. 		}
  276. 		if (capacity < 0) {
  277. 			throw new Error(`The capacity given is less than 0: ${capacity}`);
  278. 		}
  279. 	};
  281. 	/**
  282. 	 * Returns the current capacity of this cache.
  283. 	 * 
  284. 	 * @type {Number}
  285. 	 */
  286. 	get capacity() {
  287. 		return this._capacity;
  288. 	};
  290. 	/**
  291. 	 * Returns true, if the cache's capacity is all used up.
  292. 	 * 
  293. 	 * @type {Boolean}
  294. 	 */
  295. 	get isFull() {
  296. 		return this.size === this.capacity;
  297. 	};
  299. 	/**
  300. 	 * @param {Number} capacity The new capacity of this cache. Must be a positive
  301. 	 * integer (0 is allowed). Note that setting a capacity that undercuts the amount
  302. 	 * of items currently held in the cache, will lead to the eviction of enough
  303. 	 * items to meet the new capacity constraint.
  304. 	 * @type {void}
  305. 	 */
  306. 	set capacity(capacity) {
  307. 		this._validateCapacity(capacity);
  309. 		let toEvict = this.size - capacity;
  310. 		if (toEvict > 0 && this.evictionPolicy === EvictionPolicy.None) {
  311. 			throw new Error('Cannot decrease capacity and automatically evict items with policy set to None.');
  312. 		}
  313. 		while (toEvict > 0) {
  314. 			this.evict();
  315. 			toEvict--;
  316. 		}
  318. 		this._capacity = capacity;
  319. 	};
  321. 	/**
  322. 	 * @returns {T} the evicted item.
  323. 	 */
  324. 	evict() {
  325. 		if (this.isEmpty) {
  326. 			throw new Error('The cache is empty, cannot evict any more items.');
  327. 		}
  328. 		return this.evictMany(1)[0];
  329. 	};
  331. 	/**
  332. 	 * @param {Number} count
  333. 	 * @returns {Array<T>} The evicted items in an array.
  334. 	 */
  335. 	evictMany(count) {
  336. 		let howMany = Math.min(count, this.size);
  337. 		/** @type {Array<T>} */
  338. 		const items = [];
  340. 		for (const item of this._evictNext()) {
  341. 			items.push(this.remove(item.key));
  342. 			if (--howMany === 0) {
  343. 				break;
  344. 			}
  345. 		}
  347. 		return items;
  348. 	};
  350. 	/**
  351. 	 * Allows to peek at the next n items that will be evited next, without removing
  352. 	 * them. Returns the items with as key/value pair.
  353. 	 * 
  354. 	 * @param {Number} amount
  355. 	 * @returns {Array<Object<String|Symbol, T>>}
  356. 	 */
  357. 	peekEvict(amount) {
  358. 		if (!Resolve.isTypeOf(amount, Number) || !Number.isInteger(amount) || amount < 1) {
  359. 			throw new Error('You must peek an mount larger than 0.');
  360. 		}
  362. 		amount = Math.min(amount, this.size);
  363. 		const iter = this._evictNext();
  364. 		return Array.from(Array(amount), iter.next, iter).map(o => {
  365. 			const obj = {};
  366. 			obj[o.value.key] = o.value.item;
  367. 			return obj;
  368. 		});
  369. 	};
  371. 	/**
  372. 	 * Returns items in the order they will be evicted, according to the policy.
  373. 	 * 
  374. 	 * @protected
  375. 	 * @returns {IterableIterator<CacheItem<T>>}
  376. 	 */
  377. 	*_evictNext() {
  378. 		/** @type {Array<CacheItem<T>>} */
  379. 		const wrappers = [];
  381. 		switch (this.evictionPolicy) {
  382. 			case EvictionPolicy.LRU:
  383. 			case EvictionPolicy.MRU:
  384. 				// Order items by their access date:
  385. 				const mru = this.evictionPolicy === EvictionPolicy.MRU ? -1 : 1;
  386. 					this.evictionPolicy === EvictionPolicy.MRU ? -1 : 1;
  387. 				wrappers.unshift(
  388. 					...Array.from(super.values()).sort((w1, w2) => {
  389. 						return mru * (JSBI.lessThan(w1.timeStamp, w2.timeStamp) ? -1 : 1);
  390. 					})
  391. 				);
  392. 				break;
  393. 			case EvictionPolicy.LFU:
  394. 			case EvictionPolicy.MFU:
  395. 				// Order items by access count and select least/most recently used items first.
  396. 				const mfu = this.evictionPolicy === EvictionPolicy.MFU ? -1 : 1;
  397. 				wrappers.unshift(
  398. 					...Array.from(super.values()).sort((w1, w2) => {
  399. 						return mfu * (w1.accessCount - w2.accessCount);
  400. 					})
  401. 				);
  402. 				break;
  403. 			case EvictionPolicy.FIFO:
  404. 			case EvictionPolicy.LIFO:
  405. 				// Remove the item inserted first/last.
  406. 				const lifo = this.evictionPolicy === EvictionPolicy.LIFO ? -1 : 1;
  407. 				wrappers.unshift(
  408. 					...Array.from(super.values()).sort((w1, w2) => {
  409. 						return lifo * (w1.order - w2.order);
  410. 					})
  411. 				);
  412. 				break;
  413. 			case EvictionPolicy.Undetermined:
  414. 				// No specific/deterministic order.
  415. 				yield* super.values();
  416. 				break;
  417. 			case EvictionPolicy.Random:
  418. 				// Randomly select items to evict:
  419. 				wrappers.unshift(
  420. 					...Array.from(super.values()).sort(() => {
  421. 						return Math.random() < .5 ? 1 : -1;
  422. 					})
  423. 				);
  424. 				break;
  425. 			case EvictionPolicy.None:
  426. 				// Eviction not allowed, must use ::remove()
  427. 				throw new Error('Eviction not allowed.');
  428. 		}
  430. 		for (const wrap of wrappers) {
  431. 			yield wrap;
  432. 		}
  433. 	};
  435. 	/**
  436. 	 * @override
  437. 	 * @inheritdoc
  438. 	 * @param {Number} [expireAfterMsecs] Optional. if given a positive integer, then it
  439. 	 * will be used as the amount of milliseconds this entry will expire and remove itself
  440. 	 * from the cache.
  441. 	 * @throws {Error} If this cache is full and no automatic eviction policy was set.
  442. 	 * @type {void}
  443. 	 */
  444. 	set(key, val, expireAfterMsecs = void 0) {
  445. 		const isFull = this.size === this.capacity;
  446. 		if (isFull) {
  447. 			if (this.evictionPolicy === EvictionPolicy.None) {
  448. 				throw new Error(`The Cache is full and no automatic eviction policy is set.`);
  449. 			}
  451. 			this.evict(); // Remove one item according to an automatic policy.
  452. 		}
  454. 		if (!Resolve.isNumber(expireAfterMsecs) || !Number.isSafeInteger(expireAfterMsecs) || expireAfterMsecs < 0) {
  455. 			expireAfterMsecs = -1;
  456. 		}
  458. 		const wrap = new CacheItem(this, key, val, Cache.__counter, expireAfterMsecs);
  460. 		return super.set(key, wrap);
  461. 	};
  463. 	/**
  464. 	 * @override
  465. 	 * @inheritdoc
  466. 	 */
  467. 	get(key) {
  468. 		/** @type {CacheItem<T>} */
  469. 		const wrap = super.get(key);
  470. 		wrap.updateAccessTime();
  471. 		wrap.increaseAccessCount();
  472. 		return wrap.item;
  473. 	};
  475. 	/**
  476. 	 * @override
  477. 	 * @inheritdoc
  478. 	 */
  479. 	remove(key) {
  480. 		/** @type {CacheItem<T>} */
  481. 		const wrap = super.remove(key);
  482. 		wrap.clearTimeout();
  483. 		return wrap.item;
  484. 	};
  486. 	/**
  487. 	 * @override
  488. 	 * @inheritdoc
  489. 	 */
  490. 	*values() {
  491. 		for (const val of super.values()) {
  492. 			yield val.item;
  493. 		}
  494. 	};
  496. 	/**
  497. 	 * @override
  498. 	 * @inheritdoc
  499. 	 * @protected
  500. 	 */
  501. 	*_entries(reverse = false) {
  502. 		for (const entry of super._entries(reverse)) {
  503. 			const key = Object.keys(entry).concat(Object.getOwnPropertySymbols(entry))[0];
  504. 			entry[key] = entry[key].item; // unwrap
  505. 			yield entry;
  506. 		}
  507. 	};
  508. };
  512. let __counterCb = 0;
  514. /**
  515.  * @template TKey
  516.  * @template TVal
  517.  * @author Sebastian Hönel <development@hoenel.net>
  518.  */
  519. class CacheMapBased extends DictionaryMapBased {
  520. 	/**
  521. 	 * Used to assign a running number to new cache items.
  522. 	 * @private
  523. 	 * @type {Number}
  524. 	 */
  525. 	static get __counter() {
  526. 		return __counterCb++;
  527. 	};
  530. 	/**
  531. 	 * Creates a new, empty CacheMapBased<TKey, TVal>, using the specified @see {EvictionPolicy} and
  532. 	 * an initial capacity.
  533. 	 * 
  534. 	 * @param {EvictionPolicy|Number} [evictPolicy] Optional. Specify the eviction policy that is
  535. 	 * applied, if the cache has no more space left.
  536. 	 * @param {Number} [capacity] Optional. Specify the initial capacity of this cache. The capacity
  537. 	 * can be increased and decreased later.
  538. 	 * @param {EqualityComparer<TVal>} [eqComparer] Optional. Defaults To EqualityComparer<TVal>.default.
  539. 	 */
  540. 	constructor(evictPolicy = EvictionPolicy.None, capacity = Number.MAX_SAFE_INTEGER, eqComparer = EqualityComparer.default) {
  541. 		super(eqComparer);
  542. 		
  543. 		/**
  544. 		 * @type {EvictionPolicy|Number}
  545. 		 * @protected
  546. 		 */
  547. 		this._evictPolicy = EvictionPolicy.None;
  548. 		this.evictionPolicy = evictPolicy;
  550. 		/**
  551. 		 * @type {Number}
  552. 		 * @protected
  553. 		 */
  554. 		this._capacity = capacity;
  555. 		this.capacity = capacity;
  557. 		/**
  558. 		 * @type {Map<TKey, CacheItem<TVal>>}
  559. 		 * @protected
  560. 		 */
  561. 		this._map = new Map();
  563. 		/** @type {Observable<CollectionEvent<Array<TVal>>>} */
  564. 		this.observableEvict = Object.freeze(fromEvent(this, symbolCacheEvict));
  565. 	};
  566. 	
  567. 	/**
  568. 	 * @param {EvictionPolicy|Number} policy An @see {EvictionPolicy}
  569. 	 * @throws {Error} If the given policy is not one of @see {EvictionPolicy}.
  570. 	 * @protected
  571. 	 */
  572. 	_validateEvictionPolicy(policy) {
  573. 		switch (policy) {
  574. 			case EvictionPolicy.LRU:
  575. 			case EvictionPolicy.MRU:
  576. 			case EvictionPolicy.LFU:
  577. 			case EvictionPolicy.MFU:
  578. 			case EvictionPolicy.None:
  579. 			case EvictionPolicy.FIFO:
  580. 			case EvictionPolicy.LIFO:
  581. 			case EvictionPolicy.Random:
  582. 			case EvictionPolicy.Undetermined:
  583. 				break;
  584. 			default:
  585. 				throw new Error(`The eviction policy '${policy}' is not supported.`);
  586. 		}
  587. 	};
  589. 	/**
  590. 	 * @type {EvictionPolicy|Number}
  591. 	 */
  592. 	get evictionPolicy() {
  593. 		return this._evictPolicy;
  594. 	};
  596. 	/**
  597. 	 * @param {EvictionPolicy|Number} policy The new policy to use for evicting items.
  598. 	 */
  599. 	set evictionPolicy(policy) {
  600. 		this._validateEvictionPolicy(policy);
  601. 		this._evictPolicy = policy;
  602. 	};
  604. 	/**
  605. 	 * @param {Number} capacity The capacity to check. Must be a positive integer.
  606. 	 * @throws {Error} If the given capacity is not an integer or less than zero.
  607. 	 * @protected
  608. 	 */
  609. 	_validateCapacity(capacity) {
  610. 		if (!Resolve.isTypeOf(capacity, Number) || !Number.isInteger(capacity)) {
  611. 			throw new Error(`The value given for capacity is not a number.`);
  612. 		}
  613. 		if (capacity < 0) {
  614. 			throw new Error(`The capacity given is less than 0: ${capacity}`);
  615. 		}
  616. 	};
  618. 	/**
  619. 	 * Returns the current capacity of this cache.
  620. 	 * 
  621. 	 * @type {Number}
  622. 	 */
  623. 	get capacity() {
  624. 		return this._capacity;
  625. 	};
  627. 	/**
  628. 	 * Returns true, if the cache's capacity is all used up.
  629. 	 * 
  630. 	 * @type {Boolean}
  631. 	 */
  632. 	get isFull() {
  633. 		return this.size === this.capacity;
  634. 	};
  636. 	/**
  637. 	 * @param {Number} capacity The new capacity of this cache. Must be a positive
  638. 	 * integer (0 is allowed). Note that setting a capacity that undercuts the amount
  639. 	 * of items currently held in the cache, will lead to the eviction of enough
  640. 	 * items to meet the new capacity constraint.
  641. 	 * @type {void}
  642. 	 */
  643. 	set capacity(capacity) {
  644. 		this._validateCapacity(capacity);
  646. 		let toEvict = this.size - capacity;
  647. 		if (toEvict > 0 && this.evictionPolicy === EvictionPolicy.None) {
  648. 			throw new Error('Cannot decrease capacity and automatically evict items with policy set to None.');
  649. 		}
  650. 		while (toEvict > 0) {
  651. 			this.evict();
  652. 			toEvict--;
  653. 		}
  655. 		this._capacity = capacity;
  656. 	};
  658. 	/**
  659. 	 * @returns {T} the evicted item.
  660. 	 */
  661. 	evict() {
  662. 		if (this.isEmpty) {
  663. 			throw new Error('The cache is empty, cannot evict any more items.');
  664. 		}
  665. 		return this.evictMany(1)[0];
  666. 	};
  668. 	/**
  669. 	 * @param {Number} count
  670. 	 * @returns {Array<T>} The evicted items in an array.
  671. 	 */
  672. 	evictMany(count) {
  673. 		let howMany = Math.min(count, this.size);
  674. 		/** @type {Array<T>} */
  675. 		const items = [];
  677. 		for (const item of this._evictNext()) {
  678. 			items.push(this.delete(item.key));
  679. 			if (--howMany === 0) {
  680. 				break;
  681. 			}
  682. 		}
  684. 		this.emit(symbolCacheEvict, new CollectionEvent(items.slice(0)));
  686. 		return items;
  687. 	};
  689. 	/**
  690. 	 * Allows to peek at the next n items that will be evicted next, without
  691. 	 * removing them. Returns the items as key/value pair.
  692. 	 * 
  693. 	 * @param {Number} amount
  694. 	 * @returns {Array<[TKey, TVal]>}
  695. 	 */
  696. 	peekEvict(amount) {
  697. 		if (!Resolve.isTypeOf(amount, Number) || !Number.isInteger(amount) || amount < 1) {
  698. 			throw new Error('You must peek an mount larger than 0.');
  699. 		}
  701. 		amount = Math.min(amount, this.size);
  702. 		const iter = this._evictNext();
  703. 		return Array.from(Array(amount), iter.next, iter).map(o => {
  704. 			return [o.value.key, o.value.item];
  705. 		});
  706. 	};
  708. 	/**
  709. 	 * Returns items in the order they will be evicted, according to the policy.
  710. 	 * 
  711. 	 * @protected
  712. 	 * @returns {IterableIterator<CacheItem<T>>}
  713. 	 */
  714. 	*_evictNext() {
  715. 		/** @type {Array<CacheItem<T>>} */
  716. 		const wrappers = [];
  718. 		switch (this.evictionPolicy) {
  719. 			case EvictionPolicy.LRU:
  720. 			case EvictionPolicy.MRU:
  721. 				// Order items by their access date:
  722. 				const mru = this.evictionPolicy === EvictionPolicy.MRU ? -1 : 1;
  723. 					this.evictionPolicy === EvictionPolicy.MRU ? -1 : 1;
  724. 				wrappers.unshift(
  725. 					...Array.from(super.values()).sort((w1, w2) => {
  726. 						return mru * (JSBI.lessThan(w1.timeStamp, w2.timeStamp) ? -1 : 1);
  727. 					})
  728. 				);
  729. 				break;
  730. 			case EvictionPolicy.LFU:
  731. 			case EvictionPolicy.MFU:
  732. 				// Order items by access count and select least/most recently used items first.
  733. 				const mfu = this.evictionPolicy === EvictionPolicy.MFU ? -1 : 1;
  734. 				wrappers.unshift(
  735. 					...Array.from(super.values()).sort((w1, w2) => {
  736. 						return mfu * (w1.accessCount - w2.accessCount);
  737. 					})
  738. 				);
  739. 				break;
  740. 			case EvictionPolicy.FIFO:
  741. 			case EvictionPolicy.LIFO:
  742. 				// Remove the item inserted first/last.
  743. 				const lifo = this.evictionPolicy === EvictionPolicy.LIFO ? -1 : 1;
  744. 				wrappers.unshift(
  745. 					...Array.from(super.values()).sort((w1, w2) => {
  746. 						return lifo * (w1.order - w2.order);
  747. 					})
  748. 				);
  749. 				break;
  750. 			case EvictionPolicy.Undetermined:
  751. 				// No specific/deterministic order.
  752. 				yield* super.values();
  753. 				break;
  754. 			case EvictionPolicy.Random:
  755. 				// Randomly select items to evict:
  756. 				wrappers.unshift(
  757. 					...Array.from(super.values()).sort(() => {
  758. 						return Math.random() < .5 ? 1 : -1;
  759. 					})
  760. 				);
  761. 				break;
  762. 			case EvictionPolicy.None:
  763. 				// Eviction not allowed, must use ::remove()
  764. 				throw new Error('Eviction not allowed.');
  765. 		}
  767. 		for (const wrap of wrappers) {
  768. 			yield wrap;
  769. 		}
  770. 	};
  772. 	/**
  773. 	 * @override
  774. 	 * @inheritdoc
  775. 	 * @param {Number} [expireAfterMsecs] Optional. if given a positive integer, then it
  776. 	 * will be used as the amount of milliseconds this entry will expire and remove itself
  777. 	 * from the cache.
  778. 	 * @throws {Error} If this cache is full and no automatic eviction policy was set.
  779. 	 */
  780. 	set(key, val, expireAfterMsecs = void 0) {
  781. 		const isFull = this.size === this.capacity;
  782. 		if (isFull) {
  783. 			if (this.evictionPolicy === EvictionPolicy.None) {
  784. 				throw new Error(`The Cache is full and no automatic eviction policy is set.`);
  785. 			}
  787. 			this.evict(); // Remove one item according to an automatic policy.
  788. 		}
  790. 		if (!Resolve.isNumber(expireAfterMsecs) || !Number.isSafeInteger(expireAfterMsecs) || expireAfterMsecs < 0) {
  791. 			expireAfterMsecs = -1;
  792. 		}
  794. 		const wrap = new CacheItem(this, key, val, CacheMapBased.__counter, expireAfterMsecs);
  796. 		return super.set(key, wrap);
  797. 	};
  799. 	/**
  800. 	 * @override
  801. 	 * @inheritdoc
  802. 	 */
  803. 	get(key) {
  804. 		const wrap = this._map.get(key);
  805. 		wrap.updateAccessTime();
  806. 		wrap.increaseAccessCount();
  808. 		const value = this.__unwrapValue(wrap);
  809. 		this.emit(symbolDictionaryGet, new CollectionEvent([key, value]));
  810. 		return value;
  811. 	};
  813. 	/**
  814. 	 * @override
  815. 	 * @inheritdoc
  816. 	 */
  817. 	*values() {
  818. 		for (const val of super.values()) {
  819. 			yield this.__unwrapValue(val);
  820. 		}
  821. 	};
  823. 	/**
  824. 	 * @override
  825. 	 * @inheritdoc
  826. 	 */
  827. 	*entries() {
  828. 		for (const entry of super.entries()) {
  829. 			yield [entry[0], this.__unwrapValue(entry[1])];
  830. 		}
  831. 	};
  833. 	/**
  834. 	 * @private
  835. 	 * @override
  836. 	 * @inheritdoc
  837. 	 * @param {CacheItem<TVal>} value
  838. 	 * @returns {TVal} The wrapped value
  839. 	 */
  840. 	__unwrapValue(value) {
  841. 		return value.item;
  842. 	};
  843. };
  847. /**
  848.  * @template T
  849.  * @author Sebastian Hönel <development@hoenel.net>
  850.  */
  851. class CacheItemWithLoad extends CacheItem {
  852. 	/**
  853. 	 * @inheritdoc
  854. 	 * @param {Number} load 
  855. 	 */
  856. 	constructor(cache, key, item, order, expireAfterMsecs, load) {
  857. 		super(cache, key, item, order, expireAfterMsecs);
  859. 		/** @protected */
  860. 		this._load = load;
  861. 	};
  863. 	/**
  864. 	 * @type {Number}
  865. 	 */
  866. 	get load() {
  867. 		return this._load;
  868. 	};
  869. };
  872. /**
  873.  * A CacheWithLoad introduces a second concept to constrain the capacity
  874.  * of it. This second concept of load is useful for when the size of the
  875.  * items to cache is not known, and when the sheer amount of items does
  876.  * not allow to estimate the load. The CacheWithLoad evicts items when
  877.  * either its capacity is exhausted or the maximum load is exceeded.
  878.  * 
  879.  * @template TKey
  880.  * @template TVal
  881.  * @author Sebastian Hönel <development@hoenel.net>
  882.  */
  883. class CacheWithLoad extends CacheMapBased {
  884. 	/**
  885. 	 * @inheritdoc
  886. 	 * @param {EvictionPolicy|Number} evictPolicy
  887. 	 * @param {Number} capacity
  888. 	 * @param {Number} maxLoad The maximum load, expressed as a positive number.
  889. 	 * @param {EqualityComparer<TVal>} eqComparer
  890. 	 */
  891. 	constructor(evictPolicy = EvictionPolicy.None, capacity = Number.MAX_SAFE_INTEGER, maxLoad = Number.MAX_VALUE, eqComparer = EqualityComparer.default) {
  892. 		super(evictPolicy, capacity, eqComparer);
  894. 		/** @protected */
  895. 		this._maxLoad = maxLoad;
  896. 		this.maxLoad = maxLoad;
  898. 		/**
  899. 		 * @type {Object<String|Symbol, CacheItemWithLoad<T>>}
  900. 		 * @protected
  901. 		 */
  902. 		this._dict = {};
  903. 	};
  905. 	/**
  906. 	 * @protected
  907. 	 * @param {Number} load
  908. 	 */
  909. 	_validateLoad(load) {
  910. 		if (!Resolve.isTypeOf(load, Number) || !Number.isFinite(load)) {
  911. 			throw new Error(`The value given for load is not a number.`);
  912. 		}
  913. 		if (load <= 0) {
  914. 			throw new Error(`The value given for load must be greater than zero.`);
  915. 		}
  916. 	};
  918. 	/**
  919. 	 * Returns the current load.
  920. 	 * 
  921. 	 * @type {Number}
  922. 	 */
  923. 	get load() {
  924. 		return Array.from(
  925. 			// To avoid unwrapping:
  926. 			DictionaryMapBased.prototype.values.call(this)
  927. 		).map(ci => ci.load).reduce((a, b) => a + b, 0);
  928. 	};
  930. 	/**
  931. 	 * Returns the current free load (maximum load - current load).
  932. 	 * 
  933. 	 * @type {Number}
  934. 	 */
  935. 	get loadFree() {
  936. 		return this.maxLoad - this.load;
  937. 	};
  939. 	/**
  940. 	 * Set the maximum load.
  941. 	 * 
  942. 	 * @param {Number} maxLoad
  943. 	 * @type {void}
  944. 	 */
  945. 	set maxLoad(maxLoad) {
  946. 		this._validateLoad(maxLoad);
  948. 		if (maxLoad < this.load && this.evictionPolicy === EvictionPolicy.None) {
  949. 			throw new Error('Cannot decrease the maximum load and automatically evict items with policy set to None.');
  950. 		}
  952. 		while (this.load > maxLoad) {
  953. 			this.evict();
  954. 		}
  956. 		this._maxLoad = maxLoad;
  957. 	};
  959. 	/**
  960. 	 * Returns the maximum load.
  961. 	 * 
  962. 	 * @type {Number}
  963. 	 */
  964. 	get maxLoad() {
  965. 		return this._maxLoad;
  966. 	};
  968. 	/**
  969. 	 * @override
  970. 	 * @inheritdoc
  971. 	 * @param {TKey} key
  972. 	 * @param {TVal} val
  973. 	 * @param {Number} load
  974. 	 * @param {Number} [expireAfterMsecs] defaults to undefined. Only used if given
  975. 	 * as a positive integer.
  976. 	 */
  977. 	set(key, val, load, expireAfterMsecs = void 0) {
  978. 		this._validateLoad(load);
  980. 		if (load > this.maxLoad) {
  981. 			throw new Error(`The specified load exceeds this cache's maximum load.`);
  982. 		}
  984. 		const isFull = this.size === this.capacity;
  985. 		if (isFull) {
  986. 			if (this.evictionPolicy === EvictionPolicy.None) {
  987. 				throw new Error(`The Cache is full and no automatic eviction policy is set.`);
  988. 			}
  990. 			this.evict(); // Remove one item according to an automatic policy.
  991. 		}
  993. 		if (load + this.load > this.maxLoad) {
  994. 			if (this.evictionPolicy === EvictionPolicy.None) {
  995. 				throw new Error(`The Cache's load is too high and no automatic eviction policy is set.`);
  996. 			}
  998. 			while (load + this.load > this.maxLoad) {
  999. 				this.evict();
  1000. 			}
  1001. 		}
  1003. 		if (!Resolve.isNumber(expireAfterMsecs) || !Number.isSafeInteger(expireAfterMsecs) || expireAfterMsecs < 0) {
  1004. 			expireAfterMsecs = -1;
  1005. 		}
  1007. 		const wrap = new CacheItemWithLoad(
  1008. 			this, key, val, CacheMapBased.__counter, expireAfterMsecs, load);
  1010. 		return DictionaryMapBased.prototype.set.call(this, key, wrap);
  1011. 	};
  1012. };
  1015. module.exports = Object.freeze({
  1016. 	EvictionPolicy,
  1017. 	Cache,
  1018. 	CacheMapBased,
  1019. 	CacheItem,
  1020. 	CacheWithLoad,
  1021. 	CacheItemWithLoad
  1022. });