map.js 31 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042
  1. var _a, _b;
  2. import { compare, compareIgnoreCase, compareSubstring, compareSubstringIgnoreCase } from './strings.js';
  3. export class StringIterator {
  4. constructor() {
  5. this._value = '';
  6. this._pos = 0;
  7. }
  8. reset(key) {
  9. this._value = key;
  10. this._pos = 0;
  11. return this;
  12. }
  13. next() {
  14. this._pos += 1;
  15. return this;
  16. }
  17. hasNext() {
  18. return this._pos < this._value.length - 1;
  19. }
  20. cmp(a) {
  21. const aCode = a.charCodeAt(0);
  22. const thisCode = this._value.charCodeAt(this._pos);
  23. return aCode - thisCode;
  24. }
  25. value() {
  26. return this._value[this._pos];
  27. }
  28. }
  29. export class ConfigKeysIterator {
  30. constructor(_caseSensitive = true) {
  31. this._caseSensitive = _caseSensitive;
  32. }
  33. reset(key) {
  34. this._value = key;
  35. this._from = 0;
  36. this._to = 0;
  37. return this.next();
  38. }
  39. hasNext() {
  40. return this._to < this._value.length;
  41. }
  42. next() {
  43. // this._data = key.split(/[\\/]/).filter(s => !!s);
  44. this._from = this._to;
  45. let justSeps = true;
  46. for (; this._to < this._value.length; this._to++) {
  47. const ch = this._value.charCodeAt(this._to);
  48. if (ch === 46 /* Period */) {
  49. if (justSeps) {
  50. this._from++;
  51. }
  52. else {
  53. break;
  54. }
  55. }
  56. else {
  57. justSeps = false;
  58. }
  59. }
  60. return this;
  61. }
  62. cmp(a) {
  63. return this._caseSensitive
  64. ? compareSubstring(a, this._value, 0, a.length, this._from, this._to)
  65. : compareSubstringIgnoreCase(a, this._value, 0, a.length, this._from, this._to);
  66. }
  67. value() {
  68. return this._value.substring(this._from, this._to);
  69. }
  70. }
  71. export class PathIterator {
  72. constructor(_splitOnBackslash = true, _caseSensitive = true) {
  73. this._splitOnBackslash = _splitOnBackslash;
  74. this._caseSensitive = _caseSensitive;
  75. }
  76. reset(key) {
  77. this._value = key.replace(/\\$|\/$/, '');
  78. this._from = 0;
  79. this._to = 0;
  80. return this.next();
  81. }
  82. hasNext() {
  83. return this._to < this._value.length;
  84. }
  85. next() {
  86. // this._data = key.split(/[\\/]/).filter(s => !!s);
  87. this._from = this._to;
  88. let justSeps = true;
  89. for (; this._to < this._value.length; this._to++) {
  90. const ch = this._value.charCodeAt(this._to);
  91. if (ch === 47 /* Slash */ || this._splitOnBackslash && ch === 92 /* Backslash */) {
  92. if (justSeps) {
  93. this._from++;
  94. }
  95. else {
  96. break;
  97. }
  98. }
  99. else {
  100. justSeps = false;
  101. }
  102. }
  103. return this;
  104. }
  105. cmp(a) {
  106. return this._caseSensitive
  107. ? compareSubstring(a, this._value, 0, a.length, this._from, this._to)
  108. : compareSubstringIgnoreCase(a, this._value, 0, a.length, this._from, this._to);
  109. }
  110. value() {
  111. return this._value.substring(this._from, this._to);
  112. }
  113. }
  114. export class UriIterator {
  115. constructor(_ignorePathCasing) {
  116. this._ignorePathCasing = _ignorePathCasing;
  117. this._states = [];
  118. this._stateIdx = 0;
  119. }
  120. reset(key) {
  121. this._value = key;
  122. this._states = [];
  123. if (this._value.scheme) {
  124. this._states.push(1 /* Scheme */);
  125. }
  126. if (this._value.authority) {
  127. this._states.push(2 /* Authority */);
  128. }
  129. if (this._value.path) {
  130. this._pathIterator = new PathIterator(false, !this._ignorePathCasing(key));
  131. this._pathIterator.reset(key.path);
  132. if (this._pathIterator.value()) {
  133. this._states.push(3 /* Path */);
  134. }
  135. }
  136. if (this._value.query) {
  137. this._states.push(4 /* Query */);
  138. }
  139. if (this._value.fragment) {
  140. this._states.push(5 /* Fragment */);
  141. }
  142. this._stateIdx = 0;
  143. return this;
  144. }
  145. next() {
  146. if (this._states[this._stateIdx] === 3 /* Path */ && this._pathIterator.hasNext()) {
  147. this._pathIterator.next();
  148. }
  149. else {
  150. this._stateIdx += 1;
  151. }
  152. return this;
  153. }
  154. hasNext() {
  155. return (this._states[this._stateIdx] === 3 /* Path */ && this._pathIterator.hasNext())
  156. || this._stateIdx < this._states.length - 1;
  157. }
  158. cmp(a) {
  159. if (this._states[this._stateIdx] === 1 /* Scheme */) {
  160. return compareIgnoreCase(a, this._value.scheme);
  161. }
  162. else if (this._states[this._stateIdx] === 2 /* Authority */) {
  163. return compareIgnoreCase(a, this._value.authority);
  164. }
  165. else if (this._states[this._stateIdx] === 3 /* Path */) {
  166. return this._pathIterator.cmp(a);
  167. }
  168. else if (this._states[this._stateIdx] === 4 /* Query */) {
  169. return compare(a, this._value.query);
  170. }
  171. else if (this._states[this._stateIdx] === 5 /* Fragment */) {
  172. return compare(a, this._value.fragment);
  173. }
  174. throw new Error();
  175. }
  176. value() {
  177. if (this._states[this._stateIdx] === 1 /* Scheme */) {
  178. return this._value.scheme;
  179. }
  180. else if (this._states[this._stateIdx] === 2 /* Authority */) {
  181. return this._value.authority;
  182. }
  183. else if (this._states[this._stateIdx] === 3 /* Path */) {
  184. return this._pathIterator.value();
  185. }
  186. else if (this._states[this._stateIdx] === 4 /* Query */) {
  187. return this._value.query;
  188. }
  189. else if (this._states[this._stateIdx] === 5 /* Fragment */) {
  190. return this._value.fragment;
  191. }
  192. throw new Error();
  193. }
  194. }
  195. class TernarySearchTreeNode {
  196. constructor() {
  197. this.height = 1;
  198. }
  199. rotateLeft() {
  200. const tmp = this.right;
  201. this.right = tmp.left;
  202. tmp.left = this;
  203. this.updateHeight();
  204. tmp.updateHeight();
  205. return tmp;
  206. }
  207. rotateRight() {
  208. const tmp = this.left;
  209. this.left = tmp.right;
  210. tmp.right = this;
  211. this.updateHeight();
  212. tmp.updateHeight();
  213. return tmp;
  214. }
  215. updateHeight() {
  216. this.height = 1 + Math.max(this.heightLeft, this.heightRight);
  217. }
  218. balanceFactor() {
  219. return this.heightRight - this.heightLeft;
  220. }
  221. get heightLeft() {
  222. var _c, _d;
  223. return (_d = (_c = this.left) === null || _c === void 0 ? void 0 : _c.height) !== null && _d !== void 0 ? _d : 0;
  224. }
  225. get heightRight() {
  226. var _c, _d;
  227. return (_d = (_c = this.right) === null || _c === void 0 ? void 0 : _c.height) !== null && _d !== void 0 ? _d : 0;
  228. }
  229. }
  230. export class TernarySearchTree {
  231. constructor(segments) {
  232. this._iter = segments;
  233. }
  234. static forUris(ignorePathCasing = () => false) {
  235. return new TernarySearchTree(new UriIterator(ignorePathCasing));
  236. }
  237. static forStrings() {
  238. return new TernarySearchTree(new StringIterator());
  239. }
  240. static forConfigKeys() {
  241. return new TernarySearchTree(new ConfigKeysIterator());
  242. }
  243. clear() {
  244. this._root = undefined;
  245. }
  246. set(key, element) {
  247. const iter = this._iter.reset(key);
  248. let node;
  249. if (!this._root) {
  250. this._root = new TernarySearchTreeNode();
  251. this._root.segment = iter.value();
  252. }
  253. const stack = [];
  254. // find insert_node
  255. node = this._root;
  256. while (true) {
  257. const val = iter.cmp(node.segment);
  258. if (val > 0) {
  259. // left
  260. if (!node.left) {
  261. node.left = new TernarySearchTreeNode();
  262. node.left.segment = iter.value();
  263. }
  264. stack.push([-1 /* Left */, node]);
  265. node = node.left;
  266. }
  267. else if (val < 0) {
  268. // right
  269. if (!node.right) {
  270. node.right = new TernarySearchTreeNode();
  271. node.right.segment = iter.value();
  272. }
  273. stack.push([1 /* Right */, node]);
  274. node = node.right;
  275. }
  276. else if (iter.hasNext()) {
  277. // mid
  278. iter.next();
  279. if (!node.mid) {
  280. node.mid = new TernarySearchTreeNode();
  281. node.mid.segment = iter.value();
  282. }
  283. stack.push([0 /* Mid */, node]);
  284. node = node.mid;
  285. }
  286. else {
  287. break;
  288. }
  289. }
  290. // set value
  291. const oldElement = node.value;
  292. node.value = element;
  293. node.key = key;
  294. // balance
  295. for (let i = stack.length - 1; i >= 0; i--) {
  296. const node = stack[i][1];
  297. node.updateHeight();
  298. const bf = node.balanceFactor();
  299. if (bf < -1 || bf > 1) {
  300. // needs rotate
  301. const d1 = stack[i][0];
  302. const d2 = stack[i + 1][0];
  303. if (d1 === 1 /* Right */ && d2 === 1 /* Right */) {
  304. //right, right -> rotate left
  305. stack[i][1] = node.rotateLeft();
  306. }
  307. else if (d1 === -1 /* Left */ && d2 === -1 /* Left */) {
  308. // left, left -> rotate right
  309. stack[i][1] = node.rotateRight();
  310. }
  311. else if (d1 === 1 /* Right */ && d2 === -1 /* Left */) {
  312. // right, left -> double rotate right, left
  313. node.right = stack[i + 1][1] = stack[i + 1][1].rotateRight();
  314. stack[i][1] = node.rotateLeft();
  315. }
  316. else if (d1 === -1 /* Left */ && d2 === 1 /* Right */) {
  317. // left, right -> double rotate left, right
  318. node.left = stack[i + 1][1] = stack[i + 1][1].rotateLeft();
  319. stack[i][1] = node.rotateRight();
  320. }
  321. else {
  322. throw new Error();
  323. }
  324. // patch path to parent
  325. if (i > 0) {
  326. switch (stack[i - 1][0]) {
  327. case -1 /* Left */:
  328. stack[i - 1][1].left = stack[i][1];
  329. break;
  330. case 1 /* Right */:
  331. stack[i - 1][1].right = stack[i][1];
  332. break;
  333. case 0 /* Mid */:
  334. stack[i - 1][1].mid = stack[i][1];
  335. break;
  336. }
  337. }
  338. else {
  339. this._root = stack[0][1];
  340. }
  341. }
  342. }
  343. return oldElement;
  344. }
  345. get(key) {
  346. var _c;
  347. return (_c = this._getNode(key)) === null || _c === void 0 ? void 0 : _c.value;
  348. }
  349. _getNode(key) {
  350. const iter = this._iter.reset(key);
  351. let node = this._root;
  352. while (node) {
  353. const val = iter.cmp(node.segment);
  354. if (val > 0) {
  355. // left
  356. node = node.left;
  357. }
  358. else if (val < 0) {
  359. // right
  360. node = node.right;
  361. }
  362. else if (iter.hasNext()) {
  363. // mid
  364. iter.next();
  365. node = node.mid;
  366. }
  367. else {
  368. break;
  369. }
  370. }
  371. return node;
  372. }
  373. has(key) {
  374. const node = this._getNode(key);
  375. return !((node === null || node === void 0 ? void 0 : node.value) === undefined && (node === null || node === void 0 ? void 0 : node.mid) === undefined);
  376. }
  377. delete(key) {
  378. return this._delete(key, false);
  379. }
  380. deleteSuperstr(key) {
  381. return this._delete(key, true);
  382. }
  383. _delete(key, superStr) {
  384. var _c;
  385. const iter = this._iter.reset(key);
  386. const stack = [];
  387. let node = this._root;
  388. // find node
  389. while (node) {
  390. const val = iter.cmp(node.segment);
  391. if (val > 0) {
  392. // left
  393. stack.push([-1 /* Left */, node]);
  394. node = node.left;
  395. }
  396. else if (val < 0) {
  397. // right
  398. stack.push([1 /* Right */, node]);
  399. node = node.right;
  400. }
  401. else if (iter.hasNext()) {
  402. // mid
  403. iter.next();
  404. stack.push([0 /* Mid */, node]);
  405. node = node.mid;
  406. }
  407. else {
  408. break;
  409. }
  410. }
  411. if (!node) {
  412. // node not found
  413. return;
  414. }
  415. if (superStr) {
  416. // removing children, reset height
  417. node.left = undefined;
  418. node.mid = undefined;
  419. node.right = undefined;
  420. node.height = 1;
  421. }
  422. else {
  423. // removing element
  424. node.key = undefined;
  425. node.value = undefined;
  426. }
  427. // BST node removal
  428. if (!node.mid && !node.value) {
  429. if (node.left && node.right) {
  430. // full node
  431. const min = this._min(node.right);
  432. const { key, value, segment } = min;
  433. this._delete(min.key, false);
  434. node.key = key;
  435. node.value = value;
  436. node.segment = segment;
  437. }
  438. else {
  439. // empty or half empty
  440. const newChild = (_c = node.left) !== null && _c !== void 0 ? _c : node.right;
  441. if (stack.length > 0) {
  442. const [dir, parent] = stack[stack.length - 1];
  443. switch (dir) {
  444. case -1 /* Left */:
  445. parent.left = newChild;
  446. break;
  447. case 0 /* Mid */:
  448. parent.mid = newChild;
  449. break;
  450. case 1 /* Right */:
  451. parent.right = newChild;
  452. break;
  453. }
  454. }
  455. else {
  456. this._root = newChild;
  457. }
  458. }
  459. }
  460. // AVL balance
  461. for (let i = stack.length - 1; i >= 0; i--) {
  462. const node = stack[i][1];
  463. node.updateHeight();
  464. const bf = node.balanceFactor();
  465. if (bf > 1) {
  466. // right heavy
  467. if (node.right.balanceFactor() >= 0) {
  468. // right, right -> rotate left
  469. stack[i][1] = node.rotateLeft();
  470. }
  471. else {
  472. // right, left -> double rotate
  473. node.right = stack[i + 1][1] = stack[i + 1][1].rotateRight();
  474. stack[i][1] = node.rotateLeft();
  475. }
  476. }
  477. else if (bf < -1) {
  478. // left heavy
  479. if (node.left.balanceFactor() <= 0) {
  480. // left, left -> rotate right
  481. stack[i][1] = node.rotateRight();
  482. }
  483. else {
  484. // left, right -> double rotate
  485. node.left = stack[i + 1][1] = stack[i + 1][1].rotateLeft();
  486. stack[i][1] = node.rotateRight();
  487. }
  488. }
  489. // patch path to parent
  490. if (i > 0) {
  491. switch (stack[i - 1][0]) {
  492. case -1 /* Left */:
  493. stack[i - 1][1].left = stack[i][1];
  494. break;
  495. case 1 /* Right */:
  496. stack[i - 1][1].right = stack[i][1];
  497. break;
  498. case 0 /* Mid */:
  499. stack[i - 1][1].mid = stack[i][1];
  500. break;
  501. }
  502. }
  503. else {
  504. this._root = stack[0][1];
  505. }
  506. }
  507. }
  508. _min(node) {
  509. while (node.left) {
  510. node = node.left;
  511. }
  512. return node;
  513. }
  514. findSubstr(key) {
  515. const iter = this._iter.reset(key);
  516. let node = this._root;
  517. let candidate = undefined;
  518. while (node) {
  519. const val = iter.cmp(node.segment);
  520. if (val > 0) {
  521. // left
  522. node = node.left;
  523. }
  524. else if (val < 0) {
  525. // right
  526. node = node.right;
  527. }
  528. else if (iter.hasNext()) {
  529. // mid
  530. iter.next();
  531. candidate = node.value || candidate;
  532. node = node.mid;
  533. }
  534. else {
  535. break;
  536. }
  537. }
  538. return node && node.value || candidate;
  539. }
  540. findSuperstr(key) {
  541. const iter = this._iter.reset(key);
  542. let node = this._root;
  543. while (node) {
  544. const val = iter.cmp(node.segment);
  545. if (val > 0) {
  546. // left
  547. node = node.left;
  548. }
  549. else if (val < 0) {
  550. // right
  551. node = node.right;
  552. }
  553. else if (iter.hasNext()) {
  554. // mid
  555. iter.next();
  556. node = node.mid;
  557. }
  558. else {
  559. // collect
  560. if (!node.mid) {
  561. return undefined;
  562. }
  563. else {
  564. return this._entries(node.mid);
  565. }
  566. }
  567. }
  568. return undefined;
  569. }
  570. forEach(callback) {
  571. for (const [key, value] of this) {
  572. callback(value, key);
  573. }
  574. }
  575. *[Symbol.iterator]() {
  576. yield* this._entries(this._root);
  577. }
  578. *_entries(node) {
  579. // DFS
  580. if (!node) {
  581. return;
  582. }
  583. if (node.left) {
  584. yield* this._entries(node.left);
  585. }
  586. if (node.value) {
  587. yield [node.key, node.value];
  588. }
  589. if (node.mid) {
  590. yield* this._entries(node.mid);
  591. }
  592. if (node.right) {
  593. yield* this._entries(node.right);
  594. }
  595. }
  596. }
  597. class ResourceMapEntry {
  598. constructor(uri, value) {
  599. this.uri = uri;
  600. this.value = value;
  601. }
  602. }
  603. export class ResourceMap {
  604. constructor(mapOrKeyFn, toKey) {
  605. this[_a] = 'ResourceMap';
  606. if (mapOrKeyFn instanceof ResourceMap) {
  607. this.map = new Map(mapOrKeyFn.map);
  608. this.toKey = toKey !== null && toKey !== void 0 ? toKey : ResourceMap.defaultToKey;
  609. }
  610. else {
  611. this.map = new Map();
  612. this.toKey = mapOrKeyFn !== null && mapOrKeyFn !== void 0 ? mapOrKeyFn : ResourceMap.defaultToKey;
  613. }
  614. }
  615. set(resource, value) {
  616. this.map.set(this.toKey(resource), new ResourceMapEntry(resource, value));
  617. return this;
  618. }
  619. get(resource) {
  620. var _c;
  621. return (_c = this.map.get(this.toKey(resource))) === null || _c === void 0 ? void 0 : _c.value;
  622. }
  623. has(resource) {
  624. return this.map.has(this.toKey(resource));
  625. }
  626. get size() {
  627. return this.map.size;
  628. }
  629. clear() {
  630. this.map.clear();
  631. }
  632. delete(resource) {
  633. return this.map.delete(this.toKey(resource));
  634. }
  635. forEach(clb, thisArg) {
  636. if (typeof thisArg !== 'undefined') {
  637. clb = clb.bind(thisArg);
  638. }
  639. for (let [_, entry] of this.map) {
  640. clb(entry.value, entry.uri, this);
  641. }
  642. }
  643. *values() {
  644. for (let entry of this.map.values()) {
  645. yield entry.value;
  646. }
  647. }
  648. *keys() {
  649. for (let entry of this.map.values()) {
  650. yield entry.uri;
  651. }
  652. }
  653. *entries() {
  654. for (let entry of this.map.values()) {
  655. yield [entry.uri, entry.value];
  656. }
  657. }
  658. *[(_a = Symbol.toStringTag, Symbol.iterator)]() {
  659. for (let [, entry] of this.map) {
  660. yield [entry.uri, entry.value];
  661. }
  662. }
  663. }
  664. ResourceMap.defaultToKey = (resource) => resource.toString();
  665. export class LinkedMap {
  666. constructor() {
  667. this[_b] = 'LinkedMap';
  668. this._map = new Map();
  669. this._head = undefined;
  670. this._tail = undefined;
  671. this._size = 0;
  672. this._state = 0;
  673. }
  674. clear() {
  675. this._map.clear();
  676. this._head = undefined;
  677. this._tail = undefined;
  678. this._size = 0;
  679. this._state++;
  680. }
  681. isEmpty() {
  682. return !this._head && !this._tail;
  683. }
  684. get size() {
  685. return this._size;
  686. }
  687. get first() {
  688. var _c;
  689. return (_c = this._head) === null || _c === void 0 ? void 0 : _c.value;
  690. }
  691. get last() {
  692. var _c;
  693. return (_c = this._tail) === null || _c === void 0 ? void 0 : _c.value;
  694. }
  695. has(key) {
  696. return this._map.has(key);
  697. }
  698. get(key, touch = 0 /* None */) {
  699. const item = this._map.get(key);
  700. if (!item) {
  701. return undefined;
  702. }
  703. if (touch !== 0 /* None */) {
  704. this.touch(item, touch);
  705. }
  706. return item.value;
  707. }
  708. set(key, value, touch = 0 /* None */) {
  709. let item = this._map.get(key);
  710. if (item) {
  711. item.value = value;
  712. if (touch !== 0 /* None */) {
  713. this.touch(item, touch);
  714. }
  715. }
  716. else {
  717. item = { key, value, next: undefined, previous: undefined };
  718. switch (touch) {
  719. case 0 /* None */:
  720. this.addItemLast(item);
  721. break;
  722. case 1 /* AsOld */:
  723. this.addItemFirst(item);
  724. break;
  725. case 2 /* AsNew */:
  726. this.addItemLast(item);
  727. break;
  728. default:
  729. this.addItemLast(item);
  730. break;
  731. }
  732. this._map.set(key, item);
  733. this._size++;
  734. }
  735. return this;
  736. }
  737. delete(key) {
  738. return !!this.remove(key);
  739. }
  740. remove(key) {
  741. const item = this._map.get(key);
  742. if (!item) {
  743. return undefined;
  744. }
  745. this._map.delete(key);
  746. this.removeItem(item);
  747. this._size--;
  748. return item.value;
  749. }
  750. shift() {
  751. if (!this._head && !this._tail) {
  752. return undefined;
  753. }
  754. if (!this._head || !this._tail) {
  755. throw new Error('Invalid list');
  756. }
  757. const item = this._head;
  758. this._map.delete(item.key);
  759. this.removeItem(item);
  760. this._size--;
  761. return item.value;
  762. }
  763. forEach(callbackfn, thisArg) {
  764. const state = this._state;
  765. let current = this._head;
  766. while (current) {
  767. if (thisArg) {
  768. callbackfn.bind(thisArg)(current.value, current.key, this);
  769. }
  770. else {
  771. callbackfn(current.value, current.key, this);
  772. }
  773. if (this._state !== state) {
  774. throw new Error(`LinkedMap got modified during iteration.`);
  775. }
  776. current = current.next;
  777. }
  778. }
  779. keys() {
  780. const map = this;
  781. const state = this._state;
  782. let current = this._head;
  783. const iterator = {
  784. [Symbol.iterator]() {
  785. return iterator;
  786. },
  787. next() {
  788. if (map._state !== state) {
  789. throw new Error(`LinkedMap got modified during iteration.`);
  790. }
  791. if (current) {
  792. const result = { value: current.key, done: false };
  793. current = current.next;
  794. return result;
  795. }
  796. else {
  797. return { value: undefined, done: true };
  798. }
  799. }
  800. };
  801. return iterator;
  802. }
  803. values() {
  804. const map = this;
  805. const state = this._state;
  806. let current = this._head;
  807. const iterator = {
  808. [Symbol.iterator]() {
  809. return iterator;
  810. },
  811. next() {
  812. if (map._state !== state) {
  813. throw new Error(`LinkedMap got modified during iteration.`);
  814. }
  815. if (current) {
  816. const result = { value: current.value, done: false };
  817. current = current.next;
  818. return result;
  819. }
  820. else {
  821. return { value: undefined, done: true };
  822. }
  823. }
  824. };
  825. return iterator;
  826. }
  827. entries() {
  828. const map = this;
  829. const state = this._state;
  830. let current = this._head;
  831. const iterator = {
  832. [Symbol.iterator]() {
  833. return iterator;
  834. },
  835. next() {
  836. if (map._state !== state) {
  837. throw new Error(`LinkedMap got modified during iteration.`);
  838. }
  839. if (current) {
  840. const result = { value: [current.key, current.value], done: false };
  841. current = current.next;
  842. return result;
  843. }
  844. else {
  845. return { value: undefined, done: true };
  846. }
  847. }
  848. };
  849. return iterator;
  850. }
  851. [(_b = Symbol.toStringTag, Symbol.iterator)]() {
  852. return this.entries();
  853. }
  854. trimOld(newSize) {
  855. if (newSize >= this.size) {
  856. return;
  857. }
  858. if (newSize === 0) {
  859. this.clear();
  860. return;
  861. }
  862. let current = this._head;
  863. let currentSize = this.size;
  864. while (current && currentSize > newSize) {
  865. this._map.delete(current.key);
  866. current = current.next;
  867. currentSize--;
  868. }
  869. this._head = current;
  870. this._size = currentSize;
  871. if (current) {
  872. current.previous = undefined;
  873. }
  874. this._state++;
  875. }
  876. addItemFirst(item) {
  877. // First time Insert
  878. if (!this._head && !this._tail) {
  879. this._tail = item;
  880. }
  881. else if (!this._head) {
  882. throw new Error('Invalid list');
  883. }
  884. else {
  885. item.next = this._head;
  886. this._head.previous = item;
  887. }
  888. this._head = item;
  889. this._state++;
  890. }
  891. addItemLast(item) {
  892. // First time Insert
  893. if (!this._head && !this._tail) {
  894. this._head = item;
  895. }
  896. else if (!this._tail) {
  897. throw new Error('Invalid list');
  898. }
  899. else {
  900. item.previous = this._tail;
  901. this._tail.next = item;
  902. }
  903. this._tail = item;
  904. this._state++;
  905. }
  906. removeItem(item) {
  907. if (item === this._head && item === this._tail) {
  908. this._head = undefined;
  909. this._tail = undefined;
  910. }
  911. else if (item === this._head) {
  912. // This can only happen if size === 1 which is handled
  913. // by the case above.
  914. if (!item.next) {
  915. throw new Error('Invalid list');
  916. }
  917. item.next.previous = undefined;
  918. this._head = item.next;
  919. }
  920. else if (item === this._tail) {
  921. // This can only happen if size === 1 which is handled
  922. // by the case above.
  923. if (!item.previous) {
  924. throw new Error('Invalid list');
  925. }
  926. item.previous.next = undefined;
  927. this._tail = item.previous;
  928. }
  929. else {
  930. const next = item.next;
  931. const previous = item.previous;
  932. if (!next || !previous) {
  933. throw new Error('Invalid list');
  934. }
  935. next.previous = previous;
  936. previous.next = next;
  937. }
  938. item.next = undefined;
  939. item.previous = undefined;
  940. this._state++;
  941. }
  942. touch(item, touch) {
  943. if (!this._head || !this._tail) {
  944. throw new Error('Invalid list');
  945. }
  946. if ((touch !== 1 /* AsOld */ && touch !== 2 /* AsNew */)) {
  947. return;
  948. }
  949. if (touch === 1 /* AsOld */) {
  950. if (item === this._head) {
  951. return;
  952. }
  953. const next = item.next;
  954. const previous = item.previous;
  955. // Unlink the item
  956. if (item === this._tail) {
  957. // previous must be defined since item was not head but is tail
  958. // So there are more than on item in the map
  959. previous.next = undefined;
  960. this._tail = previous;
  961. }
  962. else {
  963. // Both next and previous are not undefined since item was neither head nor tail.
  964. next.previous = previous;
  965. previous.next = next;
  966. }
  967. // Insert the node at head
  968. item.previous = undefined;
  969. item.next = this._head;
  970. this._head.previous = item;
  971. this._head = item;
  972. this._state++;
  973. }
  974. else if (touch === 2 /* AsNew */) {
  975. if (item === this._tail) {
  976. return;
  977. }
  978. const next = item.next;
  979. const previous = item.previous;
  980. // Unlink the item.
  981. if (item === this._head) {
  982. // next must be defined since item was not tail but is head
  983. // So there are more than on item in the map
  984. next.previous = undefined;
  985. this._head = next;
  986. }
  987. else {
  988. // Both next and previous are not undefined since item was neither head nor tail.
  989. next.previous = previous;
  990. previous.next = next;
  991. }
  992. item.next = undefined;
  993. item.previous = this._tail;
  994. this._tail.next = item;
  995. this._tail = item;
  996. this._state++;
  997. }
  998. }
  999. toJSON() {
  1000. const data = [];
  1001. this.forEach((value, key) => {
  1002. data.push([key, value]);
  1003. });
  1004. return data;
  1005. }
  1006. fromJSON(data) {
  1007. this.clear();
  1008. for (const [key, value] of data) {
  1009. this.set(key, value);
  1010. }
  1011. }
  1012. }
  1013. export class LRUCache extends LinkedMap {
  1014. constructor(limit, ratio = 1) {
  1015. super();
  1016. this._limit = limit;
  1017. this._ratio = Math.min(Math.max(0, ratio), 1);
  1018. }
  1019. get limit() {
  1020. return this._limit;
  1021. }
  1022. set limit(limit) {
  1023. this._limit = limit;
  1024. this.checkTrim();
  1025. }
  1026. get(key, touch = 2 /* AsNew */) {
  1027. return super.get(key, touch);
  1028. }
  1029. peek(key) {
  1030. return super.get(key, 0 /* None */);
  1031. }
  1032. set(key, value) {
  1033. super.set(key, value, 2 /* AsNew */);
  1034. this.checkTrim();
  1035. return this;
  1036. }
  1037. checkTrim() {
  1038. if (this.size > this._limit) {
  1039. this.trimOld(Math.round(this._limit * this._ratio));
  1040. }
  1041. }
  1042. }