StackedCacheMap.js 3.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142
  1. /*
  2. MIT License http://www.opensource.org/licenses/mit-license.php
  3. Author Tobias Koppers @sokra
  4. */
  5. "use strict";
  6. new Map().entries();
  7. /**
  8. * The StackedCacheMap is a data structure designed as an alternative to a Map
  9. * in situations where you need to handle multiple item additions and
  10. * frequently access the largest map.
  11. *
  12. * It is particularly optimized for efficiently adding multiple items
  13. * at once, which can be achieved using the `addAll` method.
  14. *
  15. * It has a fallback Map that is used when the map to be added is mutable.
  16. *
  17. * Note: `delete` and `has` are not supported for performance reasons.
  18. * @example
  19. * ```js
  20. * const map = new StackedCacheMap();
  21. * map.addAll(new Map([["a", 1], ["b", 2]]), true);
  22. * map.addAll(new Map([["c", 3], ["d", 4]]), true);
  23. * map.get("a"); // 1
  24. * map.get("d"); // 4
  25. * for (const [key, value] of map) {
  26. * console.log(key, value);
  27. * }
  28. * ```
  29. * @template K
  30. * @template V
  31. */
  32. class StackedCacheMap {
  33. constructor() {
  34. /** @type {Map<K, V>} */
  35. this.map = new Map();
  36. /** @type {ReadonlyMap<K, V>[]} */
  37. this.stack = [];
  38. }
  39. /**
  40. * If `immutable` is true, the map can be referenced by the StackedCacheMap
  41. * and should not be changed afterwards. If the map is mutable, all items
  42. * are copied into a fallback Map.
  43. * @param {ReadonlyMap<K, V>} map map to add
  44. * @param {boolean=} immutable if 'map' is immutable and StackedCacheMap can keep referencing it
  45. */
  46. addAll(map, immutable) {
  47. if (immutable) {
  48. this.stack.push(map);
  49. // largest map should go first
  50. for (let i = this.stack.length - 1; i > 0; i--) {
  51. const beforeLast = this.stack[i - 1];
  52. if (beforeLast.size >= map.size) break;
  53. this.stack[i] = beforeLast;
  54. this.stack[i - 1] = map;
  55. }
  56. } else {
  57. for (const [key, value] of map) {
  58. this.map.set(key, value);
  59. }
  60. }
  61. }
  62. /**
  63. * @param {K} item the key of the element to add
  64. * @param {V} value the value of the element to add
  65. * @returns {void}
  66. */
  67. set(item, value) {
  68. this.map.set(item, value);
  69. }
  70. /**
  71. * @param {K} item the item to delete
  72. * @returns {void}
  73. */
  74. delete(item) {
  75. throw new Error("Items can't be deleted from a StackedCacheMap");
  76. }
  77. /**
  78. * @param {K} item the item to test
  79. * @returns {boolean} true if the item exists in this set
  80. */
  81. has(item) {
  82. throw new Error(
  83. "Checking StackedCacheMap.has before reading is inefficient, use StackedCacheMap.get and check for undefined"
  84. );
  85. }
  86. /**
  87. * @param {K} item the key of the element to return
  88. * @returns {V | undefined} the value of the element
  89. */
  90. get(item) {
  91. for (const map of this.stack) {
  92. const value = map.get(item);
  93. if (value !== undefined) return value;
  94. }
  95. return this.map.get(item);
  96. }
  97. clear() {
  98. this.stack.length = 0;
  99. this.map.clear();
  100. }
  101. /**
  102. * @returns {number} size of the map
  103. */
  104. get size() {
  105. let size = this.map.size;
  106. for (const map of this.stack) {
  107. size += map.size;
  108. }
  109. return size;
  110. }
  111. /**
  112. * @returns {Iterator<[K, V]>} iterator
  113. */
  114. [Symbol.iterator]() {
  115. const iterators = this.stack.map(map => map[Symbol.iterator]());
  116. let current = this.map[Symbol.iterator]();
  117. return {
  118. next() {
  119. let result = current.next();
  120. while (result.done && iterators.length > 0) {
  121. current = /** @type {MapIterator<[K, V]>} */ (iterators.pop());
  122. result = current.next();
  123. }
  124. return result;
  125. }
  126. };
  127. }
  128. }
  129. module.exports = StackedCacheMap;