1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042 |
- var _a, _b;
- import { compare, compareIgnoreCase, compareSubstring, compareSubstringIgnoreCase } from './strings.js';
- export class StringIterator {
- constructor() {
- this._value = '';
- this._pos = 0;
- }
- reset(key) {
- this._value = key;
- this._pos = 0;
- return this;
- }
- next() {
- this._pos += 1;
- return this;
- }
- hasNext() {
- return this._pos < this._value.length - 1;
- }
- cmp(a) {
- const aCode = a.charCodeAt(0);
- const thisCode = this._value.charCodeAt(this._pos);
- return aCode - thisCode;
- }
- value() {
- return this._value[this._pos];
- }
- }
- export class ConfigKeysIterator {
- constructor(_caseSensitive = true) {
- this._caseSensitive = _caseSensitive;
- }
- reset(key) {
- this._value = key;
- this._from = 0;
- this._to = 0;
- return this.next();
- }
- hasNext() {
- return this._to < this._value.length;
- }
- next() {
- // this._data = key.split(/[\\/]/).filter(s => !!s);
- this._from = this._to;
- let justSeps = true;
- for (; this._to < this._value.length; this._to++) {
- const ch = this._value.charCodeAt(this._to);
- if (ch === 46 /* Period */) {
- if (justSeps) {
- this._from++;
- }
- else {
- break;
- }
- }
- else {
- justSeps = false;
- }
- }
- return this;
- }
- cmp(a) {
- return this._caseSensitive
- ? compareSubstring(a, this._value, 0, a.length, this._from, this._to)
- : compareSubstringIgnoreCase(a, this._value, 0, a.length, this._from, this._to);
- }
- value() {
- return this._value.substring(this._from, this._to);
- }
- }
- export class PathIterator {
- constructor(_splitOnBackslash = true, _caseSensitive = true) {
- this._splitOnBackslash = _splitOnBackslash;
- this._caseSensitive = _caseSensitive;
- }
- reset(key) {
- this._value = key.replace(/\\$|\/$/, '');
- this._from = 0;
- this._to = 0;
- return this.next();
- }
- hasNext() {
- return this._to < this._value.length;
- }
- next() {
- // this._data = key.split(/[\\/]/).filter(s => !!s);
- this._from = this._to;
- let justSeps = true;
- for (; this._to < this._value.length; this._to++) {
- const ch = this._value.charCodeAt(this._to);
- if (ch === 47 /* Slash */ || this._splitOnBackslash && ch === 92 /* Backslash */) {
- if (justSeps) {
- this._from++;
- }
- else {
- break;
- }
- }
- else {
- justSeps = false;
- }
- }
- return this;
- }
- cmp(a) {
- return this._caseSensitive
- ? compareSubstring(a, this._value, 0, a.length, this._from, this._to)
- : compareSubstringIgnoreCase(a, this._value, 0, a.length, this._from, this._to);
- }
- value() {
- return this._value.substring(this._from, this._to);
- }
- }
- export class UriIterator {
- constructor(_ignorePathCasing) {
- this._ignorePathCasing = _ignorePathCasing;
- this._states = [];
- this._stateIdx = 0;
- }
- reset(key) {
- this._value = key;
- this._states = [];
- if (this._value.scheme) {
- this._states.push(1 /* Scheme */);
- }
- if (this._value.authority) {
- this._states.push(2 /* Authority */);
- }
- if (this._value.path) {
- this._pathIterator = new PathIterator(false, !this._ignorePathCasing(key));
- this._pathIterator.reset(key.path);
- if (this._pathIterator.value()) {
- this._states.push(3 /* Path */);
- }
- }
- if (this._value.query) {
- this._states.push(4 /* Query */);
- }
- if (this._value.fragment) {
- this._states.push(5 /* Fragment */);
- }
- this._stateIdx = 0;
- return this;
- }
- next() {
- if (this._states[this._stateIdx] === 3 /* Path */ && this._pathIterator.hasNext()) {
- this._pathIterator.next();
- }
- else {
- this._stateIdx += 1;
- }
- return this;
- }
- hasNext() {
- return (this._states[this._stateIdx] === 3 /* Path */ && this._pathIterator.hasNext())
- || this._stateIdx < this._states.length - 1;
- }
- cmp(a) {
- if (this._states[this._stateIdx] === 1 /* Scheme */) {
- return compareIgnoreCase(a, this._value.scheme);
- }
- else if (this._states[this._stateIdx] === 2 /* Authority */) {
- return compareIgnoreCase(a, this._value.authority);
- }
- else if (this._states[this._stateIdx] === 3 /* Path */) {
- return this._pathIterator.cmp(a);
- }
- else if (this._states[this._stateIdx] === 4 /* Query */) {
- return compare(a, this._value.query);
- }
- else if (this._states[this._stateIdx] === 5 /* Fragment */) {
- return compare(a, this._value.fragment);
- }
- throw new Error();
- }
- value() {
- if (this._states[this._stateIdx] === 1 /* Scheme */) {
- return this._value.scheme;
- }
- else if (this._states[this._stateIdx] === 2 /* Authority */) {
- return this._value.authority;
- }
- else if (this._states[this._stateIdx] === 3 /* Path */) {
- return this._pathIterator.value();
- }
- else if (this._states[this._stateIdx] === 4 /* Query */) {
- return this._value.query;
- }
- else if (this._states[this._stateIdx] === 5 /* Fragment */) {
- return this._value.fragment;
- }
- throw new Error();
- }
- }
- class TernarySearchTreeNode {
- constructor() {
- this.height = 1;
- }
- rotateLeft() {
- const tmp = this.right;
- this.right = tmp.left;
- tmp.left = this;
- this.updateHeight();
- tmp.updateHeight();
- return tmp;
- }
- rotateRight() {
- const tmp = this.left;
- this.left = tmp.right;
- tmp.right = this;
- this.updateHeight();
- tmp.updateHeight();
- return tmp;
- }
- updateHeight() {
- this.height = 1 + Math.max(this.heightLeft, this.heightRight);
- }
- balanceFactor() {
- return this.heightRight - this.heightLeft;
- }
- get heightLeft() {
- var _c, _d;
- return (_d = (_c = this.left) === null || _c === void 0 ? void 0 : _c.height) !== null && _d !== void 0 ? _d : 0;
- }
- get heightRight() {
- var _c, _d;
- return (_d = (_c = this.right) === null || _c === void 0 ? void 0 : _c.height) !== null && _d !== void 0 ? _d : 0;
- }
- }
- export class TernarySearchTree {
- constructor(segments) {
- this._iter = segments;
- }
- static forUris(ignorePathCasing = () => false) {
- return new TernarySearchTree(new UriIterator(ignorePathCasing));
- }
- static forStrings() {
- return new TernarySearchTree(new StringIterator());
- }
- static forConfigKeys() {
- return new TernarySearchTree(new ConfigKeysIterator());
- }
- clear() {
- this._root = undefined;
- }
- set(key, element) {
- const iter = this._iter.reset(key);
- let node;
- if (!this._root) {
- this._root = new TernarySearchTreeNode();
- this._root.segment = iter.value();
- }
- const stack = [];
- // find insert_node
- node = this._root;
- while (true) {
- const val = iter.cmp(node.segment);
- if (val > 0) {
- // left
- if (!node.left) {
- node.left = new TernarySearchTreeNode();
- node.left.segment = iter.value();
- }
- stack.push([-1 /* Left */, node]);
- node = node.left;
- }
- else if (val < 0) {
- // right
- if (!node.right) {
- node.right = new TernarySearchTreeNode();
- node.right.segment = iter.value();
- }
- stack.push([1 /* Right */, node]);
- node = node.right;
- }
- else if (iter.hasNext()) {
- // mid
- iter.next();
- if (!node.mid) {
- node.mid = new TernarySearchTreeNode();
- node.mid.segment = iter.value();
- }
- stack.push([0 /* Mid */, node]);
- node = node.mid;
- }
- else {
- break;
- }
- }
- // set value
- const oldElement = node.value;
- node.value = element;
- node.key = key;
- // balance
- for (let i = stack.length - 1; i >= 0; i--) {
- const node = stack[i][1];
- node.updateHeight();
- const bf = node.balanceFactor();
- if (bf < -1 || bf > 1) {
- // needs rotate
- const d1 = stack[i][0];
- const d2 = stack[i + 1][0];
- if (d1 === 1 /* Right */ && d2 === 1 /* Right */) {
- //right, right -> rotate left
- stack[i][1] = node.rotateLeft();
- }
- else if (d1 === -1 /* Left */ && d2 === -1 /* Left */) {
- // left, left -> rotate right
- stack[i][1] = node.rotateRight();
- }
- else if (d1 === 1 /* Right */ && d2 === -1 /* Left */) {
- // right, left -> double rotate right, left
- node.right = stack[i + 1][1] = stack[i + 1][1].rotateRight();
- stack[i][1] = node.rotateLeft();
- }
- else if (d1 === -1 /* Left */ && d2 === 1 /* Right */) {
- // left, right -> double rotate left, right
- node.left = stack[i + 1][1] = stack[i + 1][1].rotateLeft();
- stack[i][1] = node.rotateRight();
- }
- else {
- throw new Error();
- }
- // patch path to parent
- if (i > 0) {
- switch (stack[i - 1][0]) {
- case -1 /* Left */:
- stack[i - 1][1].left = stack[i][1];
- break;
- case 1 /* Right */:
- stack[i - 1][1].right = stack[i][1];
- break;
- case 0 /* Mid */:
- stack[i - 1][1].mid = stack[i][1];
- break;
- }
- }
- else {
- this._root = stack[0][1];
- }
- }
- }
- return oldElement;
- }
- get(key) {
- var _c;
- return (_c = this._getNode(key)) === null || _c === void 0 ? void 0 : _c.value;
- }
- _getNode(key) {
- const iter = this._iter.reset(key);
- let node = this._root;
- while (node) {
- const val = iter.cmp(node.segment);
- if (val > 0) {
- // left
- node = node.left;
- }
- else if (val < 0) {
- // right
- node = node.right;
- }
- else if (iter.hasNext()) {
- // mid
- iter.next();
- node = node.mid;
- }
- else {
- break;
- }
- }
- return node;
- }
- has(key) {
- const node = this._getNode(key);
- return !((node === null || node === void 0 ? void 0 : node.value) === undefined && (node === null || node === void 0 ? void 0 : node.mid) === undefined);
- }
- delete(key) {
- return this._delete(key, false);
- }
- deleteSuperstr(key) {
- return this._delete(key, true);
- }
- _delete(key, superStr) {
- var _c;
- const iter = this._iter.reset(key);
- const stack = [];
- let node = this._root;
- // find node
- while (node) {
- const val = iter.cmp(node.segment);
- if (val > 0) {
- // left
- stack.push([-1 /* Left */, node]);
- node = node.left;
- }
- else if (val < 0) {
- // right
- stack.push([1 /* Right */, node]);
- node = node.right;
- }
- else if (iter.hasNext()) {
- // mid
- iter.next();
- stack.push([0 /* Mid */, node]);
- node = node.mid;
- }
- else {
- break;
- }
- }
- if (!node) {
- // node not found
- return;
- }
- if (superStr) {
- // removing children, reset height
- node.left = undefined;
- node.mid = undefined;
- node.right = undefined;
- node.height = 1;
- }
- else {
- // removing element
- node.key = undefined;
- node.value = undefined;
- }
- // BST node removal
- if (!node.mid && !node.value) {
- if (node.left && node.right) {
- // full node
- const min = this._min(node.right);
- const { key, value, segment } = min;
- this._delete(min.key, false);
- node.key = key;
- node.value = value;
- node.segment = segment;
- }
- else {
- // empty or half empty
- const newChild = (_c = node.left) !== null && _c !== void 0 ? _c : node.right;
- if (stack.length > 0) {
- const [dir, parent] = stack[stack.length - 1];
- switch (dir) {
- case -1 /* Left */:
- parent.left = newChild;
- break;
- case 0 /* Mid */:
- parent.mid = newChild;
- break;
- case 1 /* Right */:
- parent.right = newChild;
- break;
- }
- }
- else {
- this._root = newChild;
- }
- }
- }
- // AVL balance
- for (let i = stack.length - 1; i >= 0; i--) {
- const node = stack[i][1];
- node.updateHeight();
- const bf = node.balanceFactor();
- if (bf > 1) {
- // right heavy
- if (node.right.balanceFactor() >= 0) {
- // right, right -> rotate left
- stack[i][1] = node.rotateLeft();
- }
- else {
- // right, left -> double rotate
- node.right = stack[i + 1][1] = stack[i + 1][1].rotateRight();
- stack[i][1] = node.rotateLeft();
- }
- }
- else if (bf < -1) {
- // left heavy
- if (node.left.balanceFactor() <= 0) {
- // left, left -> rotate right
- stack[i][1] = node.rotateRight();
- }
- else {
- // left, right -> double rotate
- node.left = stack[i + 1][1] = stack[i + 1][1].rotateLeft();
- stack[i][1] = node.rotateRight();
- }
- }
- // patch path to parent
- if (i > 0) {
- switch (stack[i - 1][0]) {
- case -1 /* Left */:
- stack[i - 1][1].left = stack[i][1];
- break;
- case 1 /* Right */:
- stack[i - 1][1].right = stack[i][1];
- break;
- case 0 /* Mid */:
- stack[i - 1][1].mid = stack[i][1];
- break;
- }
- }
- else {
- this._root = stack[0][1];
- }
- }
- }
- _min(node) {
- while (node.left) {
- node = node.left;
- }
- return node;
- }
- findSubstr(key) {
- const iter = this._iter.reset(key);
- let node = this._root;
- let candidate = undefined;
- while (node) {
- const val = iter.cmp(node.segment);
- if (val > 0) {
- // left
- node = node.left;
- }
- else if (val < 0) {
- // right
- node = node.right;
- }
- else if (iter.hasNext()) {
- // mid
- iter.next();
- candidate = node.value || candidate;
- node = node.mid;
- }
- else {
- break;
- }
- }
- return node && node.value || candidate;
- }
- findSuperstr(key) {
- const iter = this._iter.reset(key);
- let node = this._root;
- while (node) {
- const val = iter.cmp(node.segment);
- if (val > 0) {
- // left
- node = node.left;
- }
- else if (val < 0) {
- // right
- node = node.right;
- }
- else if (iter.hasNext()) {
- // mid
- iter.next();
- node = node.mid;
- }
- else {
- // collect
- if (!node.mid) {
- return undefined;
- }
- else {
- return this._entries(node.mid);
- }
- }
- }
- return undefined;
- }
- forEach(callback) {
- for (const [key, value] of this) {
- callback(value, key);
- }
- }
- *[Symbol.iterator]() {
- yield* this._entries(this._root);
- }
- *_entries(node) {
- // DFS
- if (!node) {
- return;
- }
- if (node.left) {
- yield* this._entries(node.left);
- }
- if (node.value) {
- yield [node.key, node.value];
- }
- if (node.mid) {
- yield* this._entries(node.mid);
- }
- if (node.right) {
- yield* this._entries(node.right);
- }
- }
- }
- class ResourceMapEntry {
- constructor(uri, value) {
- this.uri = uri;
- this.value = value;
- }
- }
- export class ResourceMap {
- constructor(mapOrKeyFn, toKey) {
- this[_a] = 'ResourceMap';
- if (mapOrKeyFn instanceof ResourceMap) {
- this.map = new Map(mapOrKeyFn.map);
- this.toKey = toKey !== null && toKey !== void 0 ? toKey : ResourceMap.defaultToKey;
- }
- else {
- this.map = new Map();
- this.toKey = mapOrKeyFn !== null && mapOrKeyFn !== void 0 ? mapOrKeyFn : ResourceMap.defaultToKey;
- }
- }
- set(resource, value) {
- this.map.set(this.toKey(resource), new ResourceMapEntry(resource, value));
- return this;
- }
- get(resource) {
- var _c;
- return (_c = this.map.get(this.toKey(resource))) === null || _c === void 0 ? void 0 : _c.value;
- }
- has(resource) {
- return this.map.has(this.toKey(resource));
- }
- get size() {
- return this.map.size;
- }
- clear() {
- this.map.clear();
- }
- delete(resource) {
- return this.map.delete(this.toKey(resource));
- }
- forEach(clb, thisArg) {
- if (typeof thisArg !== 'undefined') {
- clb = clb.bind(thisArg);
- }
- for (let [_, entry] of this.map) {
- clb(entry.value, entry.uri, this);
- }
- }
- *values() {
- for (let entry of this.map.values()) {
- yield entry.value;
- }
- }
- *keys() {
- for (let entry of this.map.values()) {
- yield entry.uri;
- }
- }
- *entries() {
- for (let entry of this.map.values()) {
- yield [entry.uri, entry.value];
- }
- }
- *[(_a = Symbol.toStringTag, Symbol.iterator)]() {
- for (let [, entry] of this.map) {
- yield [entry.uri, entry.value];
- }
- }
- }
- ResourceMap.defaultToKey = (resource) => resource.toString();
- export class LinkedMap {
- constructor() {
- this[_b] = 'LinkedMap';
- this._map = new Map();
- this._head = undefined;
- this._tail = undefined;
- this._size = 0;
- this._state = 0;
- }
- clear() {
- this._map.clear();
- this._head = undefined;
- this._tail = undefined;
- this._size = 0;
- this._state++;
- }
- isEmpty() {
- return !this._head && !this._tail;
- }
- get size() {
- return this._size;
- }
- get first() {
- var _c;
- return (_c = this._head) === null || _c === void 0 ? void 0 : _c.value;
- }
- get last() {
- var _c;
- return (_c = this._tail) === null || _c === void 0 ? void 0 : _c.value;
- }
- has(key) {
- return this._map.has(key);
- }
- get(key, touch = 0 /* None */) {
- const item = this._map.get(key);
- if (!item) {
- return undefined;
- }
- if (touch !== 0 /* None */) {
- this.touch(item, touch);
- }
- return item.value;
- }
- set(key, value, touch = 0 /* None */) {
- let item = this._map.get(key);
- if (item) {
- item.value = value;
- if (touch !== 0 /* None */) {
- this.touch(item, touch);
- }
- }
- else {
- item = { key, value, next: undefined, previous: undefined };
- switch (touch) {
- case 0 /* None */:
- this.addItemLast(item);
- break;
- case 1 /* AsOld */:
- this.addItemFirst(item);
- break;
- case 2 /* AsNew */:
- this.addItemLast(item);
- break;
- default:
- this.addItemLast(item);
- break;
- }
- this._map.set(key, item);
- this._size++;
- }
- return this;
- }
- delete(key) {
- return !!this.remove(key);
- }
- remove(key) {
- const item = this._map.get(key);
- if (!item) {
- return undefined;
- }
- this._map.delete(key);
- this.removeItem(item);
- this._size--;
- return item.value;
- }
- shift() {
- if (!this._head && !this._tail) {
- return undefined;
- }
- if (!this._head || !this._tail) {
- throw new Error('Invalid list');
- }
- const item = this._head;
- this._map.delete(item.key);
- this.removeItem(item);
- this._size--;
- return item.value;
- }
- forEach(callbackfn, thisArg) {
- const state = this._state;
- let current = this._head;
- while (current) {
- if (thisArg) {
- callbackfn.bind(thisArg)(current.value, current.key, this);
- }
- else {
- callbackfn(current.value, current.key, this);
- }
- if (this._state !== state) {
- throw new Error(`LinkedMap got modified during iteration.`);
- }
- current = current.next;
- }
- }
- keys() {
- const map = this;
- const state = this._state;
- let current = this._head;
- const iterator = {
- [Symbol.iterator]() {
- return iterator;
- },
- next() {
- if (map._state !== state) {
- throw new Error(`LinkedMap got modified during iteration.`);
- }
- if (current) {
- const result = { value: current.key, done: false };
- current = current.next;
- return result;
- }
- else {
- return { value: undefined, done: true };
- }
- }
- };
- return iterator;
- }
- values() {
- const map = this;
- const state = this._state;
- let current = this._head;
- const iterator = {
- [Symbol.iterator]() {
- return iterator;
- },
- next() {
- if (map._state !== state) {
- throw new Error(`LinkedMap got modified during iteration.`);
- }
- if (current) {
- const result = { value: current.value, done: false };
- current = current.next;
- return result;
- }
- else {
- return { value: undefined, done: true };
- }
- }
- };
- return iterator;
- }
- entries() {
- const map = this;
- const state = this._state;
- let current = this._head;
- const iterator = {
- [Symbol.iterator]() {
- return iterator;
- },
- next() {
- if (map._state !== state) {
- throw new Error(`LinkedMap got modified during iteration.`);
- }
- if (current) {
- const result = { value: [current.key, current.value], done: false };
- current = current.next;
- return result;
- }
- else {
- return { value: undefined, done: true };
- }
- }
- };
- return iterator;
- }
- [(_b = Symbol.toStringTag, Symbol.iterator)]() {
- return this.entries();
- }
- trimOld(newSize) {
- if (newSize >= this.size) {
- return;
- }
- if (newSize === 0) {
- this.clear();
- return;
- }
- let current = this._head;
- let currentSize = this.size;
- while (current && currentSize > newSize) {
- this._map.delete(current.key);
- current = current.next;
- currentSize--;
- }
- this._head = current;
- this._size = currentSize;
- if (current) {
- current.previous = undefined;
- }
- this._state++;
- }
- addItemFirst(item) {
- // First time Insert
- if (!this._head && !this._tail) {
- this._tail = item;
- }
- else if (!this._head) {
- throw new Error('Invalid list');
- }
- else {
- item.next = this._head;
- this._head.previous = item;
- }
- this._head = item;
- this._state++;
- }
- addItemLast(item) {
- // First time Insert
- if (!this._head && !this._tail) {
- this._head = item;
- }
- else if (!this._tail) {
- throw new Error('Invalid list');
- }
- else {
- item.previous = this._tail;
- this._tail.next = item;
- }
- this._tail = item;
- this._state++;
- }
- removeItem(item) {
- if (item === this._head && item === this._tail) {
- this._head = undefined;
- this._tail = undefined;
- }
- else if (item === this._head) {
- // This can only happen if size === 1 which is handled
- // by the case above.
- if (!item.next) {
- throw new Error('Invalid list');
- }
- item.next.previous = undefined;
- this._head = item.next;
- }
- else if (item === this._tail) {
- // This can only happen if size === 1 which is handled
- // by the case above.
- if (!item.previous) {
- throw new Error('Invalid list');
- }
- item.previous.next = undefined;
- this._tail = item.previous;
- }
- else {
- const next = item.next;
- const previous = item.previous;
- if (!next || !previous) {
- throw new Error('Invalid list');
- }
- next.previous = previous;
- previous.next = next;
- }
- item.next = undefined;
- item.previous = undefined;
- this._state++;
- }
- touch(item, touch) {
- if (!this._head || !this._tail) {
- throw new Error('Invalid list');
- }
- if ((touch !== 1 /* AsOld */ && touch !== 2 /* AsNew */)) {
- return;
- }
- if (touch === 1 /* AsOld */) {
- if (item === this._head) {
- return;
- }
- const next = item.next;
- const previous = item.previous;
- // Unlink the item
- if (item === this._tail) {
- // previous must be defined since item was not head but is tail
- // So there are more than on item in the map
- previous.next = undefined;
- this._tail = previous;
- }
- else {
- // Both next and previous are not undefined since item was neither head nor tail.
- next.previous = previous;
- previous.next = next;
- }
- // Insert the node at head
- item.previous = undefined;
- item.next = this._head;
- this._head.previous = item;
- this._head = item;
- this._state++;
- }
- else if (touch === 2 /* AsNew */) {
- if (item === this._tail) {
- return;
- }
- const next = item.next;
- const previous = item.previous;
- // Unlink the item.
- if (item === this._head) {
- // next must be defined since item was not tail but is head
- // So there are more than on item in the map
- next.previous = undefined;
- this._head = next;
- }
- else {
- // Both next and previous are not undefined since item was neither head nor tail.
- next.previous = previous;
- previous.next = next;
- }
- item.next = undefined;
- item.previous = this._tail;
- this._tail.next = item;
- this._tail = item;
- this._state++;
- }
- }
- toJSON() {
- const data = [];
- this.forEach((value, key) => {
- data.push([key, value]);
- });
- return data;
- }
- fromJSON(data) {
- this.clear();
- for (const [key, value] of data) {
- this.set(key, value);
- }
- }
- }
- export class LRUCache extends LinkedMap {
- constructor(limit, ratio = 1) {
- super();
- this._limit = limit;
- this._ratio = Math.min(Math.max(0, ratio), 1);
- }
- get limit() {
- return this._limit;
- }
- set limit(limit) {
- this._limit = limit;
- this.checkTrim();
- }
- get(key, touch = 2 /* AsNew */) {
- return super.get(key, touch);
- }
- peek(key) {
- return super.get(key, 0 /* None */);
- }
- set(key, value) {
- super.set(key, value, 2 /* AsNew */);
- this.checkTrim();
- return this;
- }
- checkTrim() {
- if (this.size > this._limit) {
- this.trimOld(Math.round(this._limit * this._ratio));
- }
- }
- }
|