🚀 Big News: Socket Acquires Coana to Bring Reachability Analysis to Every Appsec Team.Learn more →
Socket
Book a DemoInstallSign in
Socket
Book a DemoInstallSign in

@js-sdsl/ordered-map

Package Overview
Dependencies
Maintainers
2
Versions
8
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@js-sdsl/ordered-map - npm Package Compare versions

Comparing version

4.3.0
to
4.4.0

10

CHANGELOG.md

@@ -7,2 +7,12 @@ # Change Log

## [4.4.0] - 2023.03.17
### Changed
- Optimized inOrder travel function for tree container.
- Optimized `Symbol.iterator` function.
- Optimized `TreeContainer` `erase` function.
- Optimized some details of deque.
- Change `reverse` and `sort` returned value to `this`.
## [4.3.0] - 2023.01.20

@@ -9,0 +19,0 @@

96

dist/cjs/index.d.ts

@@ -227,2 +227,35 @@ /**

}
declare const enum TreeNodeColor {
RED = 1,
BLACK = 0
}
declare class TreeNode<K, V> {
_color: TreeNodeColor;
_key: K | undefined;
_value: V | undefined;
_left: TreeNode<K, V> | undefined;
_right: TreeNode<K, V> | undefined;
_parent: TreeNode<K, V> | undefined;
constructor(key?: K, value?: V, color?: TreeNodeColor);
/**
* @description Get the pre node.
* @returns TreeNode about the pre node.
*/
_pre(): TreeNode<K, V>;
/**
* @description Get the next node.
* @returns TreeNode about the next node.
*/
_next(): TreeNode<K, V>;
/**
* @description Rotate left.
* @returns TreeNode about moved to original position after rotation.
*/
_rotateLeft(): TreeNode<K, V>;
/**
* @description Rotate right.
* @returns TreeNode about moved to original position after rotation.
*/
_rotateRight(): TreeNode<K, V>;
}
declare abstract class TreeContainer<K, V> extends Container<K | [

@@ -232,2 +265,6 @@ K,

]> {
enableIndex: boolean;
protected _inOrderTraversal(): TreeNode<K, V>[];
protected _inOrderTraversal(pos: number): TreeNode<K, V>;
protected _inOrderTraversal(callback: (node: TreeNode<K, V>, index: number, map: this) => void): TreeNode<K, V>;
clear(): void;

@@ -253,10 +290,2 @@ /**

eraseElementByIterator(iter: TreeIterator<K, V>): TreeIterator<K, V>;
forEach(callback: (element: K | [
K,
V
], index: number, tree: TreeContainer<K, V>) => void): void;
getElementByPos(pos: number): K | [
K,
V
];
/**

@@ -294,35 +323,2 @@ * @description Get the height of the tree.

}
declare const enum TreeNodeColor {
RED = 1,
BLACK = 0
}
declare class TreeNode<K, V> {
_color: TreeNodeColor;
_key: K | undefined;
_value: V | undefined;
_left: TreeNode<K, V> | undefined;
_right: TreeNode<K, V> | undefined;
_parent: TreeNode<K, V> | undefined;
constructor(key?: K, value?: V);
/**
* @description Get the pre node.
* @returns TreeNode about the pre node.
*/
_pre(): TreeNode<K, V>;
/**
* @description Get the next node.
* @returns TreeNode about the next node.
*/
_next(): TreeNode<K, V>;
/**
* @description Rotate left.
* @returns TreeNode about moved to original position after rotation.
*/
_rotateLeft(): TreeNode<K, V>;
/**
* @description Rotate right.
* @returns TreeNode about moved to original position after rotation.
*/
_rotateRight(): TreeNode<K, V>;
}
declare class OrderedMapIterator<K, V> extends TreeIterator<K, V> {

@@ -370,2 +366,6 @@ container: OrderedMap<K, V>;

reverseUpperBound(key: K): OrderedMapIterator<K, V>;
forEach(callback: (element: [
K,
V
], index: number, map: OrderedMap<K, V>) => void): void;
/**

@@ -384,2 +384,6 @@ * @description Insert a key-value pair or set value by the given key.

setElement(key: K, value: V, hint?: OrderedMapIterator<K, V>): number;
getElementByPos(pos: number): [
K,
V
];
find(key: K): OrderedMapIterator<K, V>;

@@ -400,14 +404,4 @@ /**

eraseElementByIterator(iter: OrderedMapIterator<K, V>): OrderedMapIterator<K, V>;
// @ts-ignore
forEach(callback: (element: [
K,
V
], index: number, map: OrderedMap<K, V>) => void): void;
// @ts-ignore
getElementByPos(pos: number): [
K,
V
];
}
export { OrderedMap };
export type { OrderedMapIterator, IteratorType, Container, ContainerIterator, TreeContainer };

873

dist/cjs/index.js

@@ -8,26 +8,24 @@ "use strict";

class TreeNode {
constructor(t, e) {
this.i = 1;
constructor(t, e, s = 1) {
this.i = undefined;
this.h = undefined;
this.o = undefined;
this.u = undefined;
this.l = undefined;
this.p = undefined;
this.h = t;
this.o = e;
this.u = t;
this.l = e;
this.p = s;
}
I() {
let t = this;
if (t.i === 1 && t.p.p === t) {
t = t.l;
} else if (t.u) {
t = t.u;
while (t.l) {
t = t.l;
if (t.p === 1 && t.o.o === t) {
t = t.h;
} else if (t.i) {
t = t.i;
while (t.h) {
t = t.h;
}
} else {
let e = t.p;
while (e.u === t) {
let e = t.o;
while (e.i === t) {
t = e;
e = t.p;
e = t.o;
}

@@ -38,17 +36,17 @@ t = e;

}
_() {
B() {
let t = this;
if (t.l) {
t = t.l;
while (t.u) {
t = t.u;
if (t.h) {
t = t.h;
while (t.i) {
t = t.i;
}
return t;
} else {
let e = t.p;
while (e.l === t) {
let e = t.o;
while (e.h === t) {
t = e;
e = t.p;
e = t.o;
}
if (t.l !== e) {
if (t.h !== e) {
return e;

@@ -58,24 +56,24 @@ } else return t;

}
g() {
const t = this.p;
const e = this.l;
const s = e.u;
if (t.p === this) t.p = e; else if (t.u === this) t.u = e; else t.l = e;
e.p = t;
e.u = this;
this.p = e;
this.l = s;
if (s) s.p = this;
_() {
const t = this.o;
const e = this.h;
const s = e.i;
if (t.o === this) t.o = e; else if (t.i === this) t.i = e; else t.h = e;
e.o = t;
e.i = this;
this.o = e;
this.h = s;
if (s) s.o = this;
return e;
}
B() {
const t = this.p;
const e = this.u;
const s = e.l;
if (t.p === this) t.p = e; else if (t.u === this) t.u = e; else t.l = e;
e.p = t;
e.l = this;
this.p = e;
this.u = s;
if (s) s.p = this;
g() {
const t = this.o;
const e = this.i;
const s = e.h;
if (t.o === this) t.o = e; else if (t.i === this) t.i = e; else t.h = e;
e.o = t;
e.h = this;
this.o = e;
this.i = s;
if (s) s.o = this;
return e;

@@ -90,21 +88,21 @@ }

}
_() {
const t = super._();
this.O();
t.O();
return t;
}
g() {
const t = super.g();
this.N();
t.N();
this.O();
t.O();
return t;
}
B() {
const t = super.B();
this.N();
t.N();
return t;
}
N() {
O() {
this.M = 1;
if (this.u) {
this.M += this.u.M;
if (this.i) {
this.M += this.i.M;
}
if (this.l) {
this.M += this.l.M;
if (this.h) {
this.M += this.h.M;
}

@@ -119,3 +117,3 @@ }

equals(t) {
return this.O === t.O;
return this.T === t.T;
}

@@ -126,12 +124,12 @@ }

constructor() {
this.T = 0;
this.m = 0;
}
get length() {
return this.T;
return this.m;
}
size() {
return this.T;
return this.m;
}
empty() {
return this.T === 0;
return this.m === 0;
}

@@ -153,51 +151,17 @@ }

super();
this.m = undefined;
this.A = t;
if (e) {
this.v = TreeNodeEnableIndex;
this.C = function(t, e, s) {
const i = this.P(t, e, s);
if (i) {
let t = i.p;
while (t !== this.R) {
t.M += 1;
t = t.p;
}
const e = this.k(i);
if (e) {
const {parentNode: t, grandParent: s, curNode: i} = e;
t.N();
s.N();
i.N();
}
}
return this.T;
};
this.L = function(t) {
let e = this.S(t);
while (e !== this.R) {
e.M -= 1;
e = e.p;
}
};
} else {
this.v = TreeNode;
this.C = function(t, e, s) {
const i = this.P(t, e, s);
if (i) this.k(i);
return this.T;
};
this.L = this.S;
}
this.R = new this.v;
this.v = undefined;
this.N = t;
this.enableIndex = e;
this.A = e ? TreeNodeEnableIndex : TreeNode;
this.C = new this.A;
}
K(t, e) {
let s = this.R;
R(t, e) {
let s = this.C;
while (t) {
const i = this.A(t.h, e);
const i = this.N(t.u, e);
if (i < 0) {
t = t.l;
t = t.h;
} else if (i > 0) {
s = t;
t = t.u;
t = t.i;
} else return t;

@@ -207,11 +171,11 @@ }

}
U(t, e) {
let s = this.R;
K(t, e) {
let s = this.C;
while (t) {
const i = this.A(t.h, e);
const i = this.N(t.u, e);
if (i <= 0) {
t = t.l;
t = t.h;
} else {
s = t;
t = t.u;
t = t.i;
}

@@ -221,11 +185,11 @@ }

}
j(t, e) {
let s = this.R;
L(t, e) {
let s = this.C;
while (t) {
const i = this.A(t.h, e);
const i = this.N(t.u, e);
if (i < 0) {
s = t;
t = t.l;
t = t.h;
} else if (i > 0) {
t = t.u;
t = t.i;
} else return t;

@@ -235,11 +199,11 @@ }

}
q(t, e) {
let s = this.R;
k(t, e) {
let s = this.C;
while (t) {
const i = this.A(t.h, e);
const i = this.N(t.u, e);
if (i < 0) {
s = t;
t = t.l;
t = t.h;
} else {
t = t.u;
t = t.i;
}

@@ -249,33 +213,33 @@ }

}
F(t) {
P(t) {
while (true) {
const e = t.p;
if (e === this.R) return;
if (t.i === 1) {
t.i = 0;
const e = t.o;
if (e === this.C) return;
if (t.p === 1) {
t.p = 0;
return;
}
if (t === e.u) {
const s = e.l;
if (s.i === 1) {
s.i = 0;
e.i = 1;
if (e === this.m) {
this.m = e.g();
} else e.g();
if (t === e.i) {
const s = e.h;
if (s.p === 1) {
s.p = 0;
e.p = 1;
if (e === this.v) {
this.v = e._();
} else e._();
} else {
if (s.l && s.l.i === 1) {
s.i = e.i;
e.i = 0;
s.l.i = 0;
if (e === this.m) {
this.m = e.g();
} else e.g();
if (s.h && s.h.p === 1) {
s.p = e.p;
e.p = 0;
s.h.p = 0;
if (e === this.v) {
this.v = e._();
} else e._();
return;
} else if (s.u && s.u.i === 1) {
s.i = 1;
s.u.i = 0;
s.B();
} else if (s.i && s.i.p === 1) {
s.p = 1;
s.i.p = 0;
s.g();
} else {
s.i = 1;
s.p = 1;
t = e;

@@ -285,24 +249,24 @@ }

} else {
const s = e.u;
if (s.i === 1) {
s.i = 0;
e.i = 1;
if (e === this.m) {
this.m = e.B();
} else e.B();
const s = e.i;
if (s.p === 1) {
s.p = 0;
e.p = 1;
if (e === this.v) {
this.v = e.g();
} else e.g();
} else {
if (s.u && s.u.i === 1) {
s.i = e.i;
e.i = 0;
s.u.i = 0;
if (e === this.m) {
this.m = e.B();
} else e.B();
if (s.i && s.i.p === 1) {
s.p = e.p;
e.p = 0;
s.i.p = 0;
if (e === this.v) {
this.v = e.g();
} else e.g();
return;
} else if (s.l && s.l.i === 1) {
s.i = 1;
s.l.i = 0;
s.g();
} else if (s.h && s.h.p === 1) {
s.p = 1;
s.h.p = 0;
s._();
} else {
s.i = 1;
s.p = 1;
t = e;

@@ -315,185 +279,211 @@ }

S(t) {
if (this.T === 1) {
if (this.m === 1) {
this.clear();
return this.R;
return;
}
let e = t;
while (e.u || e.l) {
if (e.l) {
e = e.l;
while (e.u) e = e.u;
while (e.i || e.h) {
if (e.h) {
e = e.h;
while (e.i) e = e.i;
} else {
e = e.u;
e = e.i;
}
[t.h, e.h] = [ e.h, t.h ];
[t.o, e.o] = [ e.o, t.o ];
const s = t.u;
t.u = e.u;
e.u = s;
const i = t.l;
t.l = e.l;
e.l = i;
t = e;
}
if (this.R.u === e) {
this.R.u = e.p;
} else if (this.R.l === e) {
this.R.l = e.p;
if (this.C.i === e) {
this.C.i = e.o;
} else if (this.C.h === e) {
this.C.h = e.o;
}
this.F(e);
const s = e.p;
if (e === s.u) {
s.u = undefined;
} else s.l = undefined;
this.T -= 1;
this.m.i = 0;
return s;
this.P(e);
let s = e.o;
if (e === s.i) {
s.i = undefined;
} else s.h = undefined;
this.m -= 1;
this.v.p = 0;
if (this.enableIndex) {
while (s !== this.C) {
s.M -= 1;
s = s.o;
}
}
}
H(t, e) {
if (t === undefined) return false;
const s = this.H(t.u, e);
if (s) return true;
if (e(t)) return true;
return this.H(t.l, e);
U(t) {
const e = typeof t === "number" ? t : undefined;
const s = typeof t === "function" ? t : undefined;
const i = typeof t === "undefined" ? [] : undefined;
let r = 0;
let n = this.v;
const h = [];
while (h.length || n) {
if (n) {
h.push(n);
n = n.i;
} else {
n = h.pop();
if (r === e) return n;
i && i.push(n);
s && s(n, r, this);
r += 1;
n = n.h;
}
}
return i;
}
k(t) {
j(t) {
while (true) {
const e = t.p;
if (e.i === 0) return;
const s = e.p;
if (e === s.u) {
const i = s.l;
if (i && i.i === 1) {
i.i = e.i = 0;
if (s === this.m) return;
s.i = 1;
const e = t.o;
if (e.p === 0) return;
const s = e.o;
if (e === s.i) {
const i = s.h;
if (i && i.p === 1) {
i.p = e.p = 0;
if (s === this.v) return;
s.p = 1;
t = s;
continue;
} else if (t === e.l) {
t.i = 0;
if (t.u) t.u.p = e;
if (t.l) t.l.p = s;
e.l = t.u;
s.u = t.l;
t.u = e;
t.l = s;
if (s === this.m) {
this.m = t;
this.R.p = t;
} else if (t === e.h) {
t.p = 0;
if (t.i) {
t.i.o = e;
}
if (t.h) {
t.h.o = s;
}
e.h = t.i;
s.i = t.h;
t.i = e;
t.h = s;
if (s === this.v) {
this.v = t;
this.C.o = t;
} else {
const e = s.p;
if (e.u === s) {
e.u = t;
} else e.l = t;
const e = s.o;
if (e.i === s) {
e.i = t;
} else e.h = t;
}
t.p = s.p;
e.p = t;
s.p = t;
s.i = 1;
return {
parentNode: e,
grandParent: s,
curNode: t
};
t.o = s.o;
e.o = t;
s.o = t;
s.p = 1;
} else {
e.i = 0;
if (s === this.m) {
this.m = s.B();
} else s.B();
s.i = 1;
e.p = 0;
if (s === this.v) {
this.v = s.g();
} else s.g();
s.p = 1;
return;
}
} else {
const i = s.u;
if (i && i.i === 1) {
i.i = e.i = 0;
if (s === this.m) return;
s.i = 1;
const i = s.i;
if (i && i.p === 1) {
i.p = e.p = 0;
if (s === this.v) return;
s.p = 1;
t = s;
continue;
} else if (t === e.u) {
t.i = 0;
if (t.u) t.u.p = s;
if (t.l) t.l.p = e;
s.l = t.u;
e.u = t.l;
t.u = s;
t.l = e;
if (s === this.m) {
this.m = t;
this.R.p = t;
} else if (t === e.i) {
t.p = 0;
if (t.i) {
t.i.o = s;
}
if (t.h) {
t.h.o = e;
}
s.h = t.i;
e.i = t.h;
t.i = s;
t.h = e;
if (s === this.v) {
this.v = t;
this.C.o = t;
} else {
const e = s.p;
if (e.u === s) {
e.u = t;
} else e.l = t;
const e = s.o;
if (e.i === s) {
e.i = t;
} else e.h = t;
}
t.p = s.p;
e.p = t;
s.p = t;
s.i = 1;
return {
parentNode: e,
grandParent: s,
curNode: t
};
t.o = s.o;
e.o = t;
s.o = t;
s.p = 1;
} else {
e.i = 0;
if (s === this.m) {
this.m = s.g();
} else s.g();
s.i = 1;
e.p = 0;
if (s === this.v) {
this.v = s._();
} else s._();
s.p = 1;
return;
}
}
if (this.enableIndex) {
e.O();
s.O();
t.O();
}
return;
}
}
P(t, e, s) {
if (this.m === undefined) {
this.T += 1;
this.m = new this.v(t, e);
this.m.i = 0;
this.m.p = this.R;
this.R.p = this.m;
this.R.u = this.m;
this.R.l = this.m;
return;
q(t, e, s) {
if (this.v === undefined) {
this.m += 1;
this.v = new this.A(t, e, 0);
this.v.o = this.C;
this.C.o = this.C.i = this.C.h = this.v;
return this.m;
}
let i;
const r = this.R.u;
const n = this.A(r.h, t);
const r = this.C.i;
const n = this.N(r.u, t);
if (n === 0) {
r.o = e;
return;
r.l = e;
return this.m;
} else if (n > 0) {
r.u = new this.v(t, e);
r.u.p = r;
i = r.u;
this.R.u = i;
r.i = new this.A(t, e);
r.i.o = r;
i = r.i;
this.C.i = i;
} else {
const r = this.R.l;
const n = this.A(r.h, t);
const r = this.C.h;
const n = this.N(r.u, t);
if (n === 0) {
r.o = e;
return;
r.l = e;
return this.m;
} else if (n < 0) {
r.l = new this.v(t, e);
r.l.p = r;
i = r.l;
this.R.l = i;
r.h = new this.A(t, e);
r.h.o = r;
i = r.h;
this.C.h = i;
} else {
if (s !== undefined) {
const r = s.O;
if (r !== this.R) {
const s = this.A(r.h, t);
const r = s.T;
if (r !== this.C) {
const s = this.N(r.u, t);
if (s === 0) {
r.o = e;
return;
r.l = e;
return this.m;
} else if (s > 0) {
const s = r.I();
const n = this.A(s.h, t);
const n = this.N(s.u, t);
if (n === 0) {
s.o = e;
return;
s.l = e;
return this.m;
} else if (n < 0) {
i = new this.v(t, e);
if (s.l === undefined) {
s.l = i;
i.p = s;
i = new this.A(t, e);
if (s.h === undefined) {
s.h = i;
i.o = s;
} else {
r.u = i;
i.p = r;
r.i = i;
i.o = r;
}

@@ -505,24 +495,24 @@ }

if (i === undefined) {
i = this.m;
i = this.v;
while (true) {
const s = this.A(i.h, t);
const s = this.N(i.u, t);
if (s > 0) {
if (i.u === undefined) {
i.u = new this.v(t, e);
i.u.p = i;
i = i.u;
if (i.i === undefined) {
i.i = new this.A(t, e);
i.i.o = i;
i = i.i;
break;
}
i = i.u;
i = i.i;
} else if (s < 0) {
if (i.l === undefined) {
i.l = new this.v(t, e);
i.l.p = i;
i = i.l;
if (i.h === undefined) {
i.h = new this.A(t, e);
i.h.o = i;
i = i.h;
break;
}
i = i.l;
i = i.h;
} else {
i.o = e;
return;
i.l = e;
return this.m;
}

@@ -533,34 +523,43 @@ }

}
this.T += 1;
return i;
if (this.enableIndex) {
let t = i.o;
while (t !== this.C) {
t.M += 1;
t = t.o;
}
}
this.j(i);
this.m += 1;
return this.m;
}
D(t, e) {
H(t, e) {
while (t) {
const s = this.A(t.h, e);
const s = this.N(t.u, e);
if (s < 0) {
t = t.l;
t = t.h;
} else if (s > 0) {
t = t.u;
t = t.i;
} else return t;
}
return t || this.R;
return t || this.C;
}
clear() {
this.T = 0;
this.m = undefined;
this.R.p = undefined;
this.R.u = this.R.l = undefined;
this.m = 0;
this.v = undefined;
this.C.o = undefined;
this.C.i = this.C.h = undefined;
}
updateKeyByIterator(t, e) {
const s = t.O;
if (s === this.R) {
const s = t.T;
if (s === this.C) {
throwIteratorAccessError();
}
if (this.T === 1) {
s.h = e;
if (this.m === 1) {
s.u = e;
return true;
}
if (s === this.R.u) {
if (this.A(s._().h, e) > 0) {
s.h = e;
const i = s.B().u;
if (s === this.C.i) {
if (this.N(i, e) > 0) {
s.u = e;
return true;

@@ -570,5 +569,6 @@ }

}
if (s === this.R.l) {
if (this.A(s.I().h, e) < 0) {
s.h = e;
const r = s.I().u;
if (s === this.C.h) {
if (this.N(r, e) < 0) {
s.u = e;
return true;

@@ -578,38 +578,27 @@ }

}
const i = s.I().h;
if (this.A(i, e) >= 0) return false;
const r = s._().h;
if (this.A(r, e) <= 0) return false;
s.h = e;
if (this.N(r, e) >= 0 || this.N(i, e) <= 0) return false;
s.u = e;
return true;
}
eraseElementByPos(t) {
if (t < 0 || t > this.T - 1) {
if (t < 0 || t > this.m - 1) {
throw new RangeError;
}
let e = 0;
const s = this;
this.H(this.m, (function(i) {
if (t === e) {
s.L(i);
return true;
}
e += 1;
return false;
}));
return this.T;
const e = this.U(t);
this.S(e);
return this.m;
}
eraseElementByKey(t) {
if (this.T === 0) return false;
const e = this.D(this.m, t);
if (e === this.R) return false;
this.L(e);
if (this.m === 0) return false;
const e = this.H(this.v, t);
if (e === this.C) return false;
this.S(e);
return true;
}
eraseElementByIterator(t) {
const e = t.O;
if (e === this.R) {
const e = t.T;
if (e === this.C) {
throwIteratorAccessError();
}
const s = e.l === undefined;
const s = e.h === undefined;
const i = t.iteratorType === 0;

@@ -619,33 +608,14 @@ if (i) {

} else {
if (!s || e.u === undefined) t.next();
if (!s || e.i === undefined) t.next();
}
this.L(e);
this.S(e);
return t;
}
forEach(t) {
let e = 0;
for (const s of this) t(s, e++, this);
}
getElementByPos(t) {
if (t < 0 || t > this.T - 1) {
throw new RangeError;
}
let e;
let s = 0;
for (const i of this) {
if (s === t) {
e = i;
break;
}
s += 1;
}
return e;
}
getHeight() {
if (this.T === 0) return 0;
const traversal = function(t) {
if (this.m === 0) return 0;
function traversal(t) {
if (!t) return 0;
return Math.max(traversal(t.u), traversal(t.l)) + 1;
};
return traversal(this.m);
return Math.max(traversal(t.i), traversal(t.h)) + 1;
}
return traversal(this.v);
}

@@ -657,17 +627,17 @@ }

super(s);
this.O = t;
this.R = e;
this.T = t;
this.C = e;
if (this.iteratorType === 0) {
this.pre = function() {
if (this.O === this.R.u) {
if (this.T === this.C.i) {
throwIteratorAccessError();
}
this.O = this.O.I();
this.T = this.T.I();
return this;
};
this.next = function() {
if (this.O === this.R) {
if (this.T === this.C) {
throwIteratorAccessError();
}
this.O = this.O._();
this.T = this.T.B();
return this;

@@ -677,13 +647,13 @@ };

this.pre = function() {
if (this.O === this.R.l) {
if (this.T === this.C.h) {
throwIteratorAccessError();
}
this.O = this.O._();
this.T = this.T.B();
return this;
};
this.next = function() {
if (this.O === this.R) {
if (this.T === this.C) {
throwIteratorAccessError();
}
this.O = this.O.I();
this.T = this.T.I();
return this;

@@ -694,5 +664,5 @@ };

get index() {
let t = this.O;
const e = this.R.p;
if (t === this.R) {
let t = this.T;
const e = this.C.o;
if (t === this.C) {
if (e) {

@@ -704,11 +674,11 @@ return e.M - 1;

let s = 0;
if (t.u) {
s += t.u.M;
if (t.i) {
s += t.i.M;
}
while (t !== e) {
const e = t.p;
if (t === e.l) {
const e = t.o;
if (t === e.h) {
s += 1;
if (e.u) {
s += e.u.M;
if (e.i) {
s += e.i.M;
}

@@ -728,3 +698,3 @@ }

get pointer() {
if (this.O === this.R) {
if (this.T === this.C) {
throwIteratorAccessError();

@@ -735,3 +705,3 @@ }

get(e, s) {
if (s === "0") return t.O.h; else if (s === "1") return t.O.o;
if (s === "0") return t.T.u; else if (s === "1") return t.T.l;
},

@@ -742,3 +712,3 @@ set(e, s, i) {

}
t.O.o = i;
t.T.l = i;
return true;

@@ -749,3 +719,3 @@ }

copy() {
return new OrderedMapIterator(this.O, this.R, this.container, this.iteratorType);
return new OrderedMapIterator(this.T, this.C, this.container, this.iteratorType);
}

@@ -762,56 +732,62 @@ }

}
* G(t) {
if (t === undefined) return;
yield* this.G(t.u);
yield [ t.h, t.o ];
yield* this.G(t.l);
}
begin() {
return new OrderedMapIterator(this.R.u || this.R, this.R, this);
return new OrderedMapIterator(this.C.i || this.C, this.C, this);
}
end() {
return new OrderedMapIterator(this.R, this.R, this);
return new OrderedMapIterator(this.C, this.C, this);
}
rBegin() {
return new OrderedMapIterator(this.R.l || this.R, this.R, this, 1);
return new OrderedMapIterator(this.C.h || this.C, this.C, this, 1);
}
rEnd() {
return new OrderedMapIterator(this.R, this.R, this, 1);
return new OrderedMapIterator(this.C, this.C, this, 1);
}
front() {
if (this.T === 0) return;
const t = this.R.u;
return [ t.h, t.o ];
if (this.m === 0) return;
const t = this.C.i;
return [ t.u, t.l ];
}
back() {
if (this.T === 0) return;
const t = this.R.l;
return [ t.h, t.o ];
if (this.m === 0) return;
const t = this.C.h;
return [ t.u, t.l ];
}
lowerBound(t) {
const e = this.K(this.m, t);
return new OrderedMapIterator(e, this.R, this);
const e = this.R(this.v, t);
return new OrderedMapIterator(e, this.C, this);
}
upperBound(t) {
const e = this.U(this.m, t);
return new OrderedMapIterator(e, this.R, this);
const e = this.K(this.v, t);
return new OrderedMapIterator(e, this.C, this);
}
reverseLowerBound(t) {
const e = this.j(this.m, t);
return new OrderedMapIterator(e, this.R, this);
const e = this.L(this.v, t);
return new OrderedMapIterator(e, this.C, this);
}
reverseUpperBound(t) {
const e = this.q(this.m, t);
return new OrderedMapIterator(e, this.R, this);
const e = this.k(this.v, t);
return new OrderedMapIterator(e, this.C, this);
}
forEach(t) {
this.U((function(e, s, i) {
t([ e.u, e.l ], s, i);
}));
}
setElement(t, e, s) {
return this.C(t, e, s);
return this.q(t, e, s);
}
getElementByPos(t) {
if (t < 0 || t > this.m - 1) {
throw new RangeError;
}
const e = this.U(t);
return [ e.u, e.l ];
}
find(t) {
const e = this.D(this.m, t);
return new OrderedMapIterator(e, this.R, this);
const e = this.H(this.v, t);
return new OrderedMapIterator(e, this.C, this);
}
getElementByKey(t) {
const e = this.D(this.m, t);
return e.o;
const e = this.H(this.v, t);
return e.l;
}

@@ -823,6 +799,11 @@ union(t) {

}));
return this.T;
return this.m;
}
[Symbol.iterator]() {
return this.G(this.m);
* [Symbol.iterator]() {
const t = this.m;
const e = this.U();
for (let s = 0; s < t; ++s) {
const t = e[s];
yield [ t.u, t.l ];
}
}

@@ -829,0 +810,0 @@ }

96

dist/esm/index.d.ts

@@ -227,2 +227,35 @@ /**

}
declare const enum TreeNodeColor {
RED = 1,
BLACK = 0
}
declare class TreeNode<K, V> {
_color: TreeNodeColor;
_key: K | undefined;
_value: V | undefined;
_left: TreeNode<K, V> | undefined;
_right: TreeNode<K, V> | undefined;
_parent: TreeNode<K, V> | undefined;
constructor(key?: K, value?: V, color?: TreeNodeColor);
/**
* @description Get the pre node.
* @returns TreeNode about the pre node.
*/
_pre(): TreeNode<K, V>;
/**
* @description Get the next node.
* @returns TreeNode about the next node.
*/
_next(): TreeNode<K, V>;
/**
* @description Rotate left.
* @returns TreeNode about moved to original position after rotation.
*/
_rotateLeft(): TreeNode<K, V>;
/**
* @description Rotate right.
* @returns TreeNode about moved to original position after rotation.
*/
_rotateRight(): TreeNode<K, V>;
}
declare abstract class TreeContainer<K, V> extends Container<K | [

@@ -232,2 +265,6 @@ K,

]> {
enableIndex: boolean;
protected _inOrderTraversal(): TreeNode<K, V>[];
protected _inOrderTraversal(pos: number): TreeNode<K, V>;
protected _inOrderTraversal(callback: (node: TreeNode<K, V>, index: number, map: this) => void): TreeNode<K, V>;
clear(): void;

@@ -253,10 +290,2 @@ /**

eraseElementByIterator(iter: TreeIterator<K, V>): TreeIterator<K, V>;
forEach(callback: (element: K | [
K,
V
], index: number, tree: TreeContainer<K, V>) => void): void;
getElementByPos(pos: number): K | [
K,
V
];
/**

@@ -294,35 +323,2 @@ * @description Get the height of the tree.

}
declare const enum TreeNodeColor {
RED = 1,
BLACK = 0
}
declare class TreeNode<K, V> {
_color: TreeNodeColor;
_key: K | undefined;
_value: V | undefined;
_left: TreeNode<K, V> | undefined;
_right: TreeNode<K, V> | undefined;
_parent: TreeNode<K, V> | undefined;
constructor(key?: K, value?: V);
/**
* @description Get the pre node.
* @returns TreeNode about the pre node.
*/
_pre(): TreeNode<K, V>;
/**
* @description Get the next node.
* @returns TreeNode about the next node.
*/
_next(): TreeNode<K, V>;
/**
* @description Rotate left.
* @returns TreeNode about moved to original position after rotation.
*/
_rotateLeft(): TreeNode<K, V>;
/**
* @description Rotate right.
* @returns TreeNode about moved to original position after rotation.
*/
_rotateRight(): TreeNode<K, V>;
}
declare class OrderedMapIterator<K, V> extends TreeIterator<K, V> {

@@ -370,2 +366,6 @@ container: OrderedMap<K, V>;

reverseUpperBound(key: K): OrderedMapIterator<K, V>;
forEach(callback: (element: [
K,
V
], index: number, map: OrderedMap<K, V>) => void): void;
/**

@@ -384,2 +384,6 @@ * @description Insert a key-value pair or set value by the given key.

setElement(key: K, value: V, hint?: OrderedMapIterator<K, V>): number;
getElementByPos(pos: number): [
K,
V
];
find(key: K): OrderedMapIterator<K, V>;

@@ -400,14 +404,4 @@ /**

eraseElementByIterator(iter: OrderedMapIterator<K, V>): OrderedMapIterator<K, V>;
// @ts-ignore
forEach(callback: (element: [
K,
V
], index: number, map: OrderedMap<K, V>) => void): void;
// @ts-ignore
getElementByPos(pos: number): [
K,
V
];
}
export { OrderedMap };
export type { OrderedMapIterator, IteratorType, Container, ContainerIterator, TreeContainer };

963

dist/esm/index.js

@@ -30,10 +30,10 @@ var extendStatics = function(e, r) {

ops: []
}, i, n, s, a;
return a = {
}, i, n, s, h;
return h = {
next: verb(0),
throw: verb(1),
return: verb(2)
}, typeof Symbol === "function" && (a[Symbol.iterator] = function() {
}, typeof Symbol === "function" && (h[Symbol.iterator] = function() {
return this;
}), a;
}), h;
function verb(e) {

@@ -44,12 +44,12 @@ return function(r) {

}
function step(u) {
function step(a) {
if (i) throw new TypeError("Generator is already executing.");
while (a && (a = 0, u[0] && (t = 0)), t) try {
if (i = 1, n && (s = u[0] & 2 ? n["return"] : u[0] ? n["throw"] || ((s = n["return"]) && s.call(n),
0) : n.next) && !(s = s.call(n, u[1])).done) return s;
if (n = 0, s) u = [ u[0] & 2, s.value ];
switch (u[0]) {
while (h && (h = 0, a[0] && (t = 0)), t) try {
if (i = 1, n && (s = a[0] & 2 ? n["return"] : a[0] ? n["throw"] || ((s = n["return"]) && s.call(n),
0) : n.next) && !(s = s.call(n, a[1])).done) return s;
if (n = 0, s) a = [ a[0] & 2, s.value ];
switch (a[0]) {
case 0:
case 1:
s = u;
s = a;
break;

@@ -60,3 +60,3 @@

return {
value: u[1],
value: a[1],
done: false

@@ -67,8 +67,8 @@ };

t.label++;
n = u[1];
u = [ 0 ];
n = a[1];
a = [ 0 ];
continue;
case 7:
u = t.ops.pop();
a = t.ops.pop();
t.trys.pop();

@@ -78,13 +78,13 @@ continue;

default:
if (!(s = t.trys, s = s.length > 0 && s[s.length - 1]) && (u[0] === 6 || u[0] === 2)) {
if (!(s = t.trys, s = s.length > 0 && s[s.length - 1]) && (a[0] === 6 || a[0] === 2)) {
t = 0;
continue;
}
if (u[0] === 3 && (!s || u[1] > s[0] && u[1] < s[3])) {
t.label = u[1];
if (a[0] === 3 && (!s || a[1] > s[0] && a[1] < s[3])) {
t.label = a[1];
break;
}
if (u[0] === 6 && t.label < s[1]) {
if (a[0] === 6 && t.label < s[1]) {
t.label = s[1];
s = u;
s = a;
break;

@@ -94,3 +94,3 @@ }

t.label = s[2];
t.ops.push(u);
t.ops.push(a);
break;

@@ -102,5 +102,5 @@ }

}
u = r.call(e, t);
a = r.call(e, t);
} catch (e) {
u = [ 6, e ];
a = [ 6, e ];
n = 0;

@@ -110,5 +110,5 @@ } finally {

}
if (u[0] & 5) throw u[1];
if (a[0] & 5) throw a[1];
return {
value: u[0] ? u[1] : void 0,
value: a[0] ? a[1] : void 0,
done: true

@@ -119,62 +119,28 @@ };

function __values(e) {
var r = typeof Symbol === "function" && Symbol.iterator, t = r && e[r], i = 0;
if (t) return t.call(e);
if (e && typeof e.length === "number") return {
next: function() {
if (e && i >= e.length) e = void 0;
return {
value: e && e[i++],
done: !e
};
var TreeNode = function() {
function TreeNode(e, r, t) {
if (t === void 0) {
t = 1;
}
};
throw new TypeError(r ? "Object is not iterable." : "Symbol.iterator is not defined.");
}
function __read(e, r) {
var t = typeof Symbol === "function" && e[Symbol.iterator];
if (!t) return e;
var i = t.call(e), n, s = [], a;
try {
while ((r === void 0 || r-- > 0) && !(n = i.next()).done) s.push(n.value);
} catch (e) {
a = {
error: e
};
} finally {
try {
if (n && !n.done && (t = i["return"])) t.call(i);
} finally {
if (a) throw a.error;
}
}
return s;
}
var TreeNode = function() {
function TreeNode(e, r) {
this.t = 1;
this.t = undefined;
this.i = undefined;
this.u = undefined;
this.h = undefined;
this.o = undefined;
this.l = undefined;
this.i = e;
this.u = r;
this.u = e;
this.o = r;
this.l = t;
}
TreeNode.prototype.v = function() {
var e = this;
if (e.t === 1 && e.l.l === e) {
e = e.o;
} else if (e.h) {
e = e.h;
while (e.o) {
e = e.o;
if (e.l === 1 && e.h.h === e) {
e = e.i;
} else if (e.t) {
e = e.t;
while (e.i) {
e = e.i;
}
} else {
var r = e.l;
while (r.h === e) {
var r = e.h;
while (r.t === e) {
e = r;
r = e.l;
r = e.h;
}

@@ -187,15 +153,15 @@ e = r;

var e = this;
if (e.o) {
e = e.o;
while (e.h) {
e = e.h;
if (e.i) {
e = e.i;
while (e.t) {
e = e.t;
}
return e;
} else {
var r = e.l;
while (r.o === e) {
var r = e.h;
while (r.i === e) {
e = r;
r = e.l;
r = e.h;
}
if (e.o !== r) {
if (e.i !== r) {
return r;

@@ -206,23 +172,23 @@ } else return e;

TreeNode.prototype.T = function() {
var e = this.l;
var r = this.o;
var t = r.h;
if (e.l === this) e.l = r; else if (e.h === this) e.h = r; else e.o = r;
r.l = e;
r.h = this;
this.l = r;
this.o = t;
if (t) t.l = this;
var e = this.h;
var r = this.i;
var t = r.t;
if (e.h === this) e.h = r; else if (e.t === this) e.t = r; else e.i = r;
r.h = e;
r.t = this;
this.h = r;
this.i = t;
if (t) t.h = this;
return r;
};
TreeNode.prototype.I = function() {
var e = this.l;
var r = this.h;
var t = r.o;
if (e.l === this) e.l = r; else if (e.h === this) e.h = r; else e.o = r;
r.l = e;
r.o = this;
this.l = r;
this.h = t;
if (t) t.l = this;
var e = this.h;
var r = this.t;
var t = r.i;
if (e.h === this) e.h = r; else if (e.t === this) e.t = r; else e.i = r;
r.h = e;
r.i = this;
this.h = r;
this.t = t;
if (t) t.h = this;
return r;

@@ -242,4 +208,4 @@ };

var r = e.prototype.T.call(this);
this._();
r._();
this.M();
r.M();
return r;

@@ -249,13 +215,13 @@ };

var r = e.prototype.I.call(this);
this._();
r._();
this.M();
r.M();
return r;
};
TreeNodeEnableIndex.prototype._ = function() {
TreeNodeEnableIndex.prototype.M = function() {
this.O = 1;
if (this.h) {
this.O += this.h.O;
if (this.t) {
this.O += this.t.O;
}
if (this.o) {
this.O += this.o.O;
if (this.i) {
this.O += this.i.O;
}

@@ -274,3 +240,3 @@ };

ContainerIterator.prototype.equals = function(e) {
return this.M === e.M;
return this.C === e.C;
};

@@ -282,7 +248,7 @@ return ContainerIterator;

function Base() {
this.C = 0;
this._ = 0;
}
Object.defineProperty(Base.prototype, "length", {
get: function() {
return this.C;
return this._;
},

@@ -293,6 +259,6 @@ enumerable: false,

Base.prototype.size = function() {
return this.C;
return this._;
};
Base.prototype.empty = function() {
return this.C === 0;
return this._ === 0;
};

@@ -330,50 +296,16 @@ return Base;

i.g = r;
if (t) {
i.m = TreeNodeEnableIndex;
i.S = function(e, r, t) {
var i = this.A(e, r, t);
if (i) {
var n = i.l;
while (n !== this.j) {
n.O += 1;
n = n.l;
}
var s = this.k(i);
if (s) {
var a = s, u = a.parentNode, f = a.grandParent, h = a.curNode;
u._();
f._();
h._();
}
}
return this.C;
};
i.B = function(e) {
var r = this.P(e);
while (r !== this.j) {
r.O -= 1;
r = r.l;
}
};
} else {
i.m = TreeNode;
i.S = function(e, r, t) {
var i = this.A(e, r, t);
if (i) this.k(i);
return this.C;
};
i.B = i.P;
}
i.j = new i.m;
i.enableIndex = t;
i.A = t ? TreeNodeEnableIndex : TreeNode;
i.m = new i.A;
return i;
}
TreeContainer.prototype.R = function(e, r) {
var t = this.j;
TreeContainer.prototype.S = function(e, r) {
var t = this.m;
while (e) {
var i = this.g(e.i, r);
var i = this.g(e.u, r);
if (i < 0) {
e = e.o;
e = e.i;
} else if (i > 0) {
t = e;
e = e.h;
e = e.t;
} else return e;

@@ -383,11 +315,11 @@ }

};
TreeContainer.prototype.G = function(e, r) {
var t = this.j;
TreeContainer.prototype.B = function(e, r) {
var t = this.m;
while (e) {
var i = this.g(e.i, r);
var i = this.g(e.u, r);
if (i <= 0) {
e = e.o;
e = e.i;
} else {
t = e;
e = e.h;
e = e.t;
}

@@ -397,11 +329,11 @@ }

};
TreeContainer.prototype.q = function(e, r) {
var t = this.j;
TreeContainer.prototype.j = function(e, r) {
var t = this.m;
while (e) {
var i = this.g(e.i, r);
var i = this.g(e.u, r);
if (i < 0) {
t = e;
e = e.o;
e = e.i;
} else if (i > 0) {
e = e.h;
e = e.t;
} else return e;

@@ -411,11 +343,11 @@ }

};
TreeContainer.prototype.D = function(e, r) {
var t = this.j;
TreeContainer.prototype.k = function(e, r) {
var t = this.m;
while (e) {
var i = this.g(e.i, r);
var i = this.g(e.u, r);
if (i < 0) {
t = e;
e = e.o;
e = e.i;
} else {
e = e.h;
e = e.t;
}

@@ -425,15 +357,15 @@ }

};
TreeContainer.prototype.F = function(e) {
TreeContainer.prototype.R = function(e) {
while (true) {
var r = e.l;
if (r === this.j) return;
if (e.t === 1) {
e.t = 0;
var r = e.h;
if (r === this.m) return;
if (e.l === 1) {
e.l = 0;
return;
}
if (e === r.h) {
var t = r.o;
if (t.t === 1) {
t.t = 0;
r.t = 1;
if (e === r.t) {
var t = r.i;
if (t.l === 1) {
t.l = 0;
r.l = 1;
if (r === this.N) {

@@ -443,6 +375,6 @@ this.N = r.T();

} else {
if (t.o && t.o.t === 1) {
t.t = r.t;
r.t = 0;
t.o.t = 0;
if (t.i && t.i.l === 1) {
t.l = r.l;
r.l = 0;
t.i.l = 0;
if (r === this.N) {

@@ -452,8 +384,8 @@ this.N = r.T();

return;
} else if (t.h && t.h.t === 1) {
t.t = 1;
t.h.t = 0;
} else if (t.t && t.t.l === 1) {
t.l = 1;
t.t.l = 0;
t.I();
} else {
t.t = 1;
t.l = 1;
e = r;

@@ -463,6 +395,6 @@ }

} else {
var t = r.h;
if (t.t === 1) {
t.t = 0;
r.t = 1;
var t = r.t;
if (t.l === 1) {
t.l = 0;
r.l = 1;
if (r === this.N) {

@@ -472,6 +404,6 @@ this.N = r.I();

} else {
if (t.h && t.h.t === 1) {
t.t = r.t;
r.t = 0;
t.h.t = 0;
if (t.t && t.t.l === 1) {
t.l = r.l;
r.l = 0;
t.t.l = 0;
if (r === this.N) {

@@ -481,8 +413,8 @@ this.N = r.I();

return;
} else if (t.o && t.o.t === 1) {
t.t = 1;
t.o.t = 0;
} else if (t.i && t.i.l === 1) {
t.l = 1;
t.i.l = 0;
t.T();
} else {
t.t = 1;
t.l = 1;
e = r;

@@ -494,187 +426,212 @@ }

};
TreeContainer.prototype.P = function(e) {
var r, t;
if (this.C === 1) {
TreeContainer.prototype.G = function(e) {
if (this._ === 1) {
this.clear();
return this.j;
return;
}
var i = e;
while (i.h || i.o) {
if (i.o) {
i = i.o;
while (i.h) i = i.h;
var r = e;
while (r.t || r.i) {
if (r.i) {
r = r.i;
while (r.t) r = r.t;
} else {
i = i.h;
r = r.t;
}
r = __read([ i.i, e.i ], 2), e.i = r[0], i.i = r[1];
t = __read([ i.u, e.u ], 2), e.u = t[0], i.u = t[1];
e = i;
var t = e.u;
e.u = r.u;
r.u = t;
var i = e.o;
e.o = r.o;
r.o = i;
e = r;
}
if (this.j.h === i) {
this.j.h = i.l;
} else if (this.j.o === i) {
this.j.o = i.l;
if (this.m.t === r) {
this.m.t = r.h;
} else if (this.m.i === r) {
this.m.i = r.h;
}
this.F(i);
var n = i.l;
if (i === n.h) {
n.h = undefined;
} else n.o = undefined;
this.C -= 1;
this.N.t = 0;
return n;
this.R(r);
var n = r.h;
if (r === n.t) {
n.t = undefined;
} else n.i = undefined;
this._ -= 1;
this.N.l = 0;
if (this.enableIndex) {
while (n !== this.m) {
n.O -= 1;
n = n.h;
}
}
};
TreeContainer.prototype.H = function(e, r) {
if (e === undefined) return false;
var t = this.H(e.h, r);
if (t) return true;
if (r(e)) return true;
return this.H(e.o, r);
TreeContainer.prototype.P = function(e) {
var r = typeof e === "number" ? e : undefined;
var t = typeof e === "function" ? e : undefined;
var i = typeof e === "undefined" ? [] : undefined;
var n = 0;
var s = this.N;
var h = [];
while (h.length || s) {
if (s) {
h.push(s);
s = s.t;
} else {
s = h.pop();
if (n === r) return s;
i && i.push(s);
t && t(s, n, this);
n += 1;
s = s.i;
}
}
return i;
};
TreeContainer.prototype.k = function(e) {
TreeContainer.prototype.q = function(e) {
while (true) {
var r = e.l;
if (r.t === 0) return;
var t = r.l;
if (r === t.h) {
var i = t.o;
if (i && i.t === 1) {
i.t = r.t = 0;
var r = e.h;
if (r.l === 0) return;
var t = r.h;
if (r === t.t) {
var i = t.i;
if (i && i.l === 1) {
i.l = r.l = 0;
if (t === this.N) return;
t.t = 1;
t.l = 1;
e = t;
continue;
} else if (e === r.o) {
e.t = 0;
if (e.h) e.h.l = r;
if (e.o) e.o.l = t;
r.o = e.h;
t.h = e.o;
e.h = r;
e.o = t;
} else if (e === r.i) {
e.l = 0;
if (e.t) {
e.t.h = r;
}
if (e.i) {
e.i.h = t;
}
r.i = e.t;
t.t = e.i;
e.t = r;
e.i = t;
if (t === this.N) {
this.N = e;
this.j.l = e;
this.m.h = e;
} else {
var n = t.l;
if (n.h === t) {
n.h = e;
} else n.o = e;
var n = t.h;
if (n.t === t) {
n.t = e;
} else n.i = e;
}
e.l = t.l;
r.l = e;
t.l = e;
t.t = 1;
return {
parentNode: r,
grandParent: t,
curNode: e
};
e.h = t.h;
r.h = e;
t.h = e;
t.l = 1;
} else {
r.t = 0;
r.l = 0;
if (t === this.N) {
this.N = t.I();
} else t.I();
t.t = 1;
t.l = 1;
return;
}
} else {
var i = t.h;
if (i && i.t === 1) {
i.t = r.t = 0;
var i = t.t;
if (i && i.l === 1) {
i.l = r.l = 0;
if (t === this.N) return;
t.t = 1;
t.l = 1;
e = t;
continue;
} else if (e === r.h) {
e.t = 0;
if (e.h) e.h.l = t;
if (e.o) e.o.l = r;
t.o = e.h;
r.h = e.o;
e.h = t;
e.o = r;
} else if (e === r.t) {
e.l = 0;
if (e.t) {
e.t.h = t;
}
if (e.i) {
e.i.h = r;
}
t.i = e.t;
r.t = e.i;
e.t = t;
e.i = r;
if (t === this.N) {
this.N = e;
this.j.l = e;
this.m.h = e;
} else {
var n = t.l;
if (n.h === t) {
n.h = e;
} else n.o = e;
var n = t.h;
if (n.t === t) {
n.t = e;
} else n.i = e;
}
e.l = t.l;
r.l = e;
t.l = e;
t.t = 1;
return {
parentNode: r,
grandParent: t,
curNode: e
};
e.h = t.h;
r.h = e;
t.h = e;
t.l = 1;
} else {
r.t = 0;
r.l = 0;
if (t === this.N) {
this.N = t.T();
} else t.T();
t.t = 1;
t.l = 1;
return;
}
}
if (this.enableIndex) {
r.M();
t.M();
e.M();
}
return;
}
};
TreeContainer.prototype.A = function(e, r, t) {
TreeContainer.prototype.D = function(e, r, t) {
if (this.N === undefined) {
this.C += 1;
this.N = new this.m(e, r);
this.N.t = 0;
this.N.l = this.j;
this.j.l = this.N;
this.j.h = this.N;
this.j.o = this.N;
return;
this._ += 1;
this.N = new this.A(e, r, 0);
this.N.h = this.m;
this.m.h = this.m.t = this.m.i = this.N;
return this._;
}
var i;
var n = this.j.h;
var s = this.g(n.i, e);
var n = this.m.t;
var s = this.g(n.u, e);
if (s === 0) {
n.u = r;
return;
n.o = r;
return this._;
} else if (s > 0) {
n.h = new this.m(e, r);
n.h.l = n;
i = n.h;
this.j.h = i;
n.t = new this.A(e, r);
n.t.h = n;
i = n.t;
this.m.t = i;
} else {
var a = this.j.o;
var u = this.g(a.i, e);
if (u === 0) {
a.u = r;
return;
} else if (u < 0) {
a.o = new this.m(e, r);
a.o.l = a;
i = a.o;
this.j.o = i;
var h = this.m.i;
var a = this.g(h.u, e);
if (a === 0) {
h.o = r;
return this._;
} else if (a < 0) {
h.i = new this.A(e, r);
h.i.h = h;
i = h.i;
this.m.i = i;
} else {
if (t !== undefined) {
var f = t.M;
if (f !== this.j) {
var h = this.g(f.i, e);
if (h === 0) {
f.u = r;
return;
} else if (h > 0) {
var o = f.v();
var d = this.g(o.i, e);
var u = t.C;
if (u !== this.m) {
var f = this.g(u.u, e);
if (f === 0) {
u.o = r;
return this._;
} else if (f > 0) {
var o = u.v();
var d = this.g(o.u, e);
if (d === 0) {
o.u = r;
return;
o.o = r;
return this._;
} else if (d < 0) {
i = new this.m(e, r);
if (o.o === undefined) {
o.o = i;
i.l = o;
i = new this.A(e, r);
if (o.i === undefined) {
o.i = i;
i.h = o;
} else {
f.h = i;
i.l = f;
u.t = i;
i.h = u;
}

@@ -688,22 +645,22 @@ }

while (true) {
var c = this.g(i.i, e);
var c = this.g(i.u, e);
if (c > 0) {
if (i.h === undefined) {
i.h = new this.m(e, r);
i.h.l = i;
i = i.h;
if (i.t === undefined) {
i.t = new this.A(e, r);
i.t.h = i;
i = i.t;
break;
}
i = i.h;
i = i.t;
} else if (c < 0) {
if (i.o === undefined) {
i.o = new this.m(e, r);
i.o.l = i;
i = i.o;
if (i.i === undefined) {
i.i = new this.A(e, r);
i.i.h = i;
i = i.i;
break;
}
i = i.o;
i = i.i;
} else {
i.u = r;
return;
i.o = r;
return this._;
}

@@ -714,34 +671,43 @@ }

}
this.C += 1;
return i;
if (this.enableIndex) {
var l = i.h;
while (l !== this.m) {
l.O += 1;
l = l.h;
}
}
this.q(i);
this._ += 1;
return this._;
};
TreeContainer.prototype.J = function(e, r) {
TreeContainer.prototype.F = function(e, r) {
while (e) {
var t = this.g(e.i, r);
var t = this.g(e.u, r);
if (t < 0) {
e = e.o;
e = e.i;
} else if (t > 0) {
e = e.h;
e = e.t;
} else return e;
}
return e || this.j;
return e || this.m;
};
TreeContainer.prototype.clear = function() {
this.C = 0;
this._ = 0;
this.N = undefined;
this.j.l = undefined;
this.j.h = this.j.o = undefined;
this.m.h = undefined;
this.m.t = this.m.i = undefined;
};
TreeContainer.prototype.updateKeyByIterator = function(e, r) {
var t = e.M;
if (t === this.j) {
var t = e.C;
if (t === this.m) {
throwIteratorAccessError();
}
if (this.C === 1) {
t.i = r;
if (this._ === 1) {
t.u = r;
return true;
}
if (t === this.j.h) {
if (this.g(t.p().i, r) > 0) {
t.i = r;
var i = t.p().u;
if (t === this.m.t) {
if (this.g(i, r) > 0) {
t.u = r;
return true;

@@ -751,5 +717,6 @@ }

}
if (t === this.j.o) {
if (this.g(t.v().i, r) < 0) {
t.i = r;
var n = t.v().u;
if (t === this.m.i) {
if (this.g(n, r) < 0) {
t.u = r;
return true;

@@ -759,38 +726,27 @@ }

}
var i = t.v().i;
if (this.g(i, r) >= 0) return false;
var n = t.p().i;
if (this.g(n, r) <= 0) return false;
t.i = r;
if (this.g(n, r) >= 0 || this.g(i, r) <= 0) return false;
t.u = r;
return true;
};
TreeContainer.prototype.eraseElementByPos = function(e) {
if (e < 0 || e > this.C - 1) {
if (e < 0 || e > this._ - 1) {
throw new RangeError;
}
var r = 0;
var t = this;
this.H(this.N, (function(i) {
if (e === r) {
t.B(i);
return true;
}
r += 1;
return false;
}));
return this.C;
var r = this.P(e);
this.G(r);
return this._;
};
TreeContainer.prototype.eraseElementByKey = function(e) {
if (this.C === 0) return false;
var r = this.J(this.N, e);
if (r === this.j) return false;
this.B(r);
if (this._ === 0) return false;
var r = this.F(this.N, e);
if (r === this.m) return false;
this.G(r);
return true;
};
TreeContainer.prototype.eraseElementByIterator = function(e) {
var r = e.M;
if (r === this.j) {
var r = e.C;
if (r === this.m) {
throwIteratorAccessError();
}
var t = r.o === undefined;
var t = r.i === undefined;
var i = e.iteratorType === 0;

@@ -800,62 +756,13 @@ if (i) {

} else {
if (!t || r.h === undefined) e.next();
if (!t || r.t === undefined) e.next();
}
this.B(r);
this.G(r);
return e;
};
TreeContainer.prototype.forEach = function(e) {
var r, t;
var i = 0;
try {
for (var n = __values(this), s = n.next(); !s.done; s = n.next()) {
var a = s.value;
e(a, i++, this);
}
} catch (e) {
r = {
error: e
};
} finally {
try {
if (s && !s.done && (t = n.return)) t.call(n);
} finally {
if (r) throw r.error;
}
}
};
TreeContainer.prototype.getElementByPos = function(e) {
var r, t;
if (e < 0 || e > this.C - 1) {
throw new RangeError;
}
var i;
var n = 0;
try {
for (var s = __values(this), a = s.next(); !a.done; a = s.next()) {
var u = a.value;
if (n === e) {
i = u;
break;
}
n += 1;
}
} catch (e) {
r = {
error: e
};
} finally {
try {
if (a && !a.done && (t = s.return)) t.call(s);
} finally {
if (r) throw r.error;
}
}
return i;
};
TreeContainer.prototype.getHeight = function() {
if (this.C === 0) return 0;
var traversal = function(e) {
if (this._ === 0) return 0;
function traversal(e) {
if (!e) return 0;
return Math.max(traversal(e.h), traversal(e.o)) + 1;
};
return Math.max(traversal(e.t), traversal(e.i)) + 1;
}
return traversal(this.N);

@@ -870,17 +777,17 @@ };

var n = e.call(this, i) || this;
n.M = r;
n.j = t;
n.C = r;
n.m = t;
if (n.iteratorType === 0) {
n.pre = function() {
if (this.M === this.j.h) {
if (this.C === this.m.t) {
throwIteratorAccessError();
}
this.M = this.M.v();
this.C = this.C.v();
return this;
};
n.next = function() {
if (this.M === this.j) {
if (this.C === this.m) {
throwIteratorAccessError();
}
this.M = this.M.p();
this.C = this.C.p();
return this;

@@ -890,13 +797,13 @@ };

n.pre = function() {
if (this.M === this.j.o) {
if (this.C === this.m.i) {
throwIteratorAccessError();
}
this.M = this.M.p();
this.C = this.C.p();
return this;
};
n.next = function() {
if (this.M === this.j) {
if (this.C === this.m) {
throwIteratorAccessError();
}
this.M = this.M.v();
this.C = this.C.v();
return this;

@@ -909,5 +816,5 @@ };

get: function() {
var e = this.M;
var r = this.j.l;
if (e === this.j) {
var e = this.C;
var r = this.m.h;
if (e === this.m) {
if (r) {

@@ -919,11 +826,11 @@ return r.O - 1;

var t = 0;
if (e.h) {
t += e.h.O;
if (e.t) {
t += e.t.O;
}
while (e !== r) {
var i = e.l;
if (e === i.o) {
var i = e.h;
if (e === i.i) {
t += 1;
if (i.h) {
t += i.h.O;
if (i.t) {
t += i.t.O;
}

@@ -950,3 +857,3 @@ }

get: function() {
if (this.M === this.j) {
if (this.C === this.m) {
throwIteratorAccessError();

@@ -957,3 +864,3 @@ }

get: function(r, t) {
if (t === "0") return e.M.i; else if (t === "1") return e.M.u;
if (t === "0") return e.C.u; else if (t === "1") return e.C.o;
},

@@ -964,3 +871,3 @@ set: function(r, t, i) {

}
e.M.u = i;
e.C.o = i;
return true;

@@ -974,3 +881,3 @@ }

OrderedMapIterator.prototype.copy = function() {
return new OrderedMapIterator(this.M, this.j, this.container, this.iteratorType);
return new OrderedMapIterator(this.C, this.m, this.container, this.iteratorType);
};

@@ -993,71 +900,62 @@ return OrderedMapIterator;

}
OrderedMap.prototype.K = function(e) {
return __generator(this, (function(r) {
switch (r.label) {
case 0:
if (e === undefined) return [ 2 ];
return [ 5, __values(this.K(e.h)) ];
case 1:
r.sent();
return [ 4, [ e.i, e.u ] ];
case 2:
r.sent();
return [ 5, __values(this.K(e.o)) ];
case 3:
r.sent();
return [ 2 ];
}
}));
};
OrderedMap.prototype.begin = function() {
return new OrderedMapIterator(this.j.h || this.j, this.j, this);
return new OrderedMapIterator(this.m.t || this.m, this.m, this);
};
OrderedMap.prototype.end = function() {
return new OrderedMapIterator(this.j, this.j, this);
return new OrderedMapIterator(this.m, this.m, this);
};
OrderedMap.prototype.rBegin = function() {
return new OrderedMapIterator(this.j.o || this.j, this.j, this, 1);
return new OrderedMapIterator(this.m.i || this.m, this.m, this, 1);
};
OrderedMap.prototype.rEnd = function() {
return new OrderedMapIterator(this.j, this.j, this, 1);
return new OrderedMapIterator(this.m, this.m, this, 1);
};
OrderedMap.prototype.front = function() {
if (this.C === 0) return;
var e = this.j.h;
return [ e.i, e.u ];
if (this._ === 0) return;
var e = this.m.t;
return [ e.u, e.o ];
};
OrderedMap.prototype.back = function() {
if (this.C === 0) return;
var e = this.j.o;
return [ e.i, e.u ];
if (this._ === 0) return;
var e = this.m.i;
return [ e.u, e.o ];
};
OrderedMap.prototype.lowerBound = function(e) {
var r = this.R(this.N, e);
return new OrderedMapIterator(r, this.j, this);
var r = this.S(this.N, e);
return new OrderedMapIterator(r, this.m, this);
};
OrderedMap.prototype.upperBound = function(e) {
var r = this.G(this.N, e);
return new OrderedMapIterator(r, this.j, this);
var r = this.B(this.N, e);
return new OrderedMapIterator(r, this.m, this);
};
OrderedMap.prototype.reverseLowerBound = function(e) {
var r = this.q(this.N, e);
return new OrderedMapIterator(r, this.j, this);
var r = this.j(this.N, e);
return new OrderedMapIterator(r, this.m, this);
};
OrderedMap.prototype.reverseUpperBound = function(e) {
var r = this.D(this.N, e);
return new OrderedMapIterator(r, this.j, this);
var r = this.k(this.N, e);
return new OrderedMapIterator(r, this.m, this);
};
OrderedMap.prototype.forEach = function(e) {
this.P((function(r, t, i) {
e([ r.u, r.o ], t, i);
}));
};
OrderedMap.prototype.setElement = function(e, r, t) {
return this.S(e, r, t);
return this.D(e, r, t);
};
OrderedMap.prototype.getElementByPos = function(e) {
if (e < 0 || e > this._ - 1) {
throw new RangeError;
}
var r = this.P(e);
return [ r.u, r.o ];
};
OrderedMap.prototype.find = function(e) {
var r = this.J(this.N, e);
return new OrderedMapIterator(r, this.j, this);
var r = this.F(this.N, e);
return new OrderedMapIterator(r, this.m, this);
};
OrderedMap.prototype.getElementByKey = function(e) {
var r = this.J(this.N, e);
return r.u;
var r = this.F(this.N, e);
return r.o;
};

@@ -1069,6 +967,31 @@ OrderedMap.prototype.union = function(e) {

}));
return this.C;
return this._;
};
OrderedMap.prototype[Symbol.iterator] = function() {
return this.K(this.N);
var e, r, t, i;
return __generator(this, (function(n) {
switch (n.label) {
case 0:
e = this._;
r = this.P();
t = 0;
n.label = 1;
case 1:
if (!(t < e)) return [ 3, 4 ];
i = r[t];
return [ 4, [ i.u, i.o ] ];
case 2:
n.sent();
n.label = 3;
case 3:
++t;
return [ 3, 1 ];
case 4:
return [ 2 ];
}
}));
};

@@ -1075,0 +998,0 @@ return OrderedMap;

344

dist/umd/ordered-map.js
/*!
* @js-sdsl/ordered-map v4.3.0
* @js-sdsl/ordered-map v4.4.0
* https://github.com/js-sdsl/js-sdsl

@@ -136,46 +136,8 @@ * (c) 2021-present ZLY201 <zilongyao1366@gmail.com>

}
function __values(o) {
var s = typeof Symbol === "function" && Symbol.iterator,
m = s && o[s],
i = 0;
if (m) return m.call(o);
if (o && typeof o.length === "number") return {
next: function () {
if (o && i >= o.length) o = void 0;
return {
value: o && o[i++],
done: !o
};
}
};
throw new TypeError(s ? "Object is not iterable." : "Symbol.iterator is not defined.");
}
function __read(o, n) {
var m = typeof Symbol === "function" && o[Symbol.iterator];
if (!m) return o;
var i = m.call(o),
r,
ar = [],
e;
try {
while ((n === void 0 || n-- > 0) && !(r = i.next()).done) ar.push(r.value);
} catch (error) {
e = {
error: error
};
} finally {
try {
if (r && !r.done && (m = i["return"])) m.call(i);
} finally {
if (e) throw e.error;
}
}
return ar;
}
var TreeNode = /** @class */function () {
function TreeNode(key, value) {
this._color = 1 /* TreeNodeColor.RED */;
this._key = undefined;
this._value = undefined;
function TreeNode(key, value, color) {
if (color === void 0) {
color = 1 /* TreeNodeColor.RED */;
}
this._left = undefined;

@@ -186,2 +148,3 @@ this._right = undefined;

this._value = value;
this._color = color;
}

@@ -407,41 +370,4 @@ /**

_this._cmp = cmp;
if (enableIndex) {
_this._TreeNodeClass = TreeNodeEnableIndex;
_this._set = function (key, value, hint) {
var curNode = this._preSet(key, value, hint);
if (curNode) {
var p = curNode._parent;
while (p !== this._header) {
p._subTreeSize += 1;
p = p._parent;
}
var nodeList = this._insertNodeSelfBalance(curNode);
if (nodeList) {
var _a = nodeList,
parentNode = _a.parentNode,
grandParent = _a.grandParent,
curNode_1 = _a.curNode;
parentNode._recount();
grandParent._recount();
curNode_1._recount();
}
}
return this._length;
};
_this._eraseNode = function (curNode) {
var p = this._preEraseNode(curNode);
while (p !== this._header) {
p._subTreeSize -= 1;
p = p._parent;
}
};
} else {
_this._TreeNodeClass = TreeNode;
_this._set = function (key, value, hint) {
var curNode = this._preSet(key, value, hint);
if (curNode) this._insertNodeSelfBalance(curNode);
return this._length;
};
_this._eraseNode = _this._preEraseNode;
}
_this.enableIndex = enableIndex;
_this._TreeNodeClass = enableIndex ? TreeNodeEnableIndex : TreeNode;
_this._header = new _this._TreeNodeClass();

@@ -583,7 +509,6 @@ return _this;

*/
TreeContainer.prototype._preEraseNode = function (curNode) {
var _a, _b;
TreeContainer.prototype._eraseNode = function (curNode) {
if (this._length === 1) {
this.clear();
return this._header;
return;
}

@@ -598,4 +523,8 @@ var swapNode = curNode;

}
_a = __read([swapNode._key, curNode._key], 2), curNode._key = _a[0], swapNode._key = _a[1];
_b = __read([swapNode._value, curNode._value], 2), curNode._value = _b[0], swapNode._value = _b[1];
var key = curNode._key;
curNode._key = swapNode._key;
swapNode._key = key;
var value = curNode._value;
curNode._value = swapNode._value;
swapNode._value = value;
curNode = swapNode;

@@ -615,3 +544,8 @@ }

this._root._color = 0 /* TreeNodeColor.BLACK */;
return _parent;
if (this.enableIndex) {
while (_parent !== this._header) {
_parent._subTreeSize -= 1;
_parent = _parent._parent;
}
}
};

@@ -621,8 +555,23 @@ /**

*/
TreeContainer.prototype._inOrderTraversal = function (curNode, callback) {
if (curNode === undefined) return false;
var ifReturn = this._inOrderTraversal(curNode._left, callback);
if (ifReturn) return true;
if (callback(curNode)) return true;
return this._inOrderTraversal(curNode._right, callback);
TreeContainer.prototype._inOrderTraversal = function (param) {
var pos = typeof param === 'number' ? param : undefined;
var callback = typeof param === 'function' ? param : undefined;
var nodeList = typeof param === 'undefined' ? [] : undefined;
var index = 0;
var curNode = this._root;
var stack = [];
while (stack.length || curNode) {
if (curNode) {
stack.push(curNode);
curNode = curNode._left;
} else {
curNode = stack.pop();
if (index === pos) return curNode;
nodeList && nodeList.push(curNode);
callback && callback(curNode, index, this);
index += 1;
curNode = curNode._right;
}
}
return nodeList;
};

@@ -647,4 +596,8 @@ /**

curNode._color = 0 /* TreeNodeColor.BLACK */;
if (curNode._left) curNode._left._parent = parentNode;
if (curNode._right) curNode._right._parent = grandParent;
if (curNode._left) {
curNode._left._parent = parentNode;
}
if (curNode._right) {
curNode._right._parent = grandParent;
}
parentNode._right = curNode._left;

@@ -667,7 +620,2 @@ grandParent._left = curNode._right;

grandParent._color = 1 /* TreeNodeColor.RED */;
return {
parentNode: parentNode,
grandParent: grandParent,
curNode: curNode
};
} else {

@@ -679,2 +627,3 @@ parentNode._color = 0 /* TreeNodeColor.BLACK */;

grandParent._color = 1 /* TreeNodeColor.RED */;
return;
}

@@ -691,4 +640,8 @@ } else {

curNode._color = 0 /* TreeNodeColor.BLACK */;
if (curNode._left) curNode._left._parent = grandParent;
if (curNode._right) curNode._right._parent = parentNode;
if (curNode._left) {
curNode._left._parent = grandParent;
}
if (curNode._right) {
curNode._right._parent = parentNode;
}
grandParent._right = curNode._left;

@@ -711,7 +664,2 @@ parentNode._left = curNode._right;

grandParent._color = 1 /* TreeNodeColor.RED */;
return {
parentNode: parentNode,
grandParent: grandParent,
curNode: curNode
};
} else {

@@ -723,5 +671,10 @@ parentNode._color = 0 /* TreeNodeColor.BLACK */;

grandParent._color = 1 /* TreeNodeColor.RED */;
return;
}
}
if (this.enableIndex) {
parentNode._recount();
grandParent._recount();
curNode._recount();
}
return;

@@ -733,12 +686,9 @@ }

*/
TreeContainer.prototype._preSet = function (key, value, hint) {
TreeContainer.prototype._set = function (key, value, hint) {
if (this._root === undefined) {
this._length += 1;
this._root = new this._TreeNodeClass(key, value);
this._root._color = 0 /* TreeNodeColor.BLACK */;
this._root = new this._TreeNodeClass(key, value, 0 /* TreeNodeColor.BLACK */);
this._root._parent = this._header;
this._header._parent = this._root;
this._header._left = this._root;
this._header._right = this._root;
return;
this._header._parent = this._header._left = this._header._right = this._root;
return this._length;
}

@@ -750,3 +700,3 @@ var curNode;

minNode._value = value;
return;
return this._length;
} else if (compareToMin > 0) {

@@ -762,3 +712,3 @@ minNode._left = new this._TreeNodeClass(key, value);

maxNode._value = value;
return;
return this._length;
} else if (compareToMax < 0) {

@@ -776,3 +726,3 @@ maxNode._right = new this._TreeNodeClass(key, value);

iterNode._value = value;
return;
return this._length;
} else /* istanbul ignore else */if (iterCmpRes > 0) {

@@ -783,3 +733,3 @@ var preNode = iterNode._pre();

preNode._value = value;
return;
return this._length;
} else if (preCmpRes < 0) {

@@ -820,3 +770,3 @@ curNode = new this._TreeNodeClass(key, value);

curNode._value = value;
return;
return this._length;
}

@@ -827,4 +777,12 @@ }

}
if (this.enableIndex) {
var parent_1 = curNode._parent;
while (parent_1 !== this._header) {
parent_1._subTreeSize += 1;
parent_1 = parent_1._parent;
}
}
this._insertNodeSelfBalance(curNode);
this._length += 1;
return curNode;
return this._length;
};

@@ -834,3 +792,3 @@ /**

*/
TreeContainer.prototype._findElementNode = function (curNode, key) {
TreeContainer.prototype._getTreeNodeByKey = function (curNode, key) {
while (curNode) {

@@ -871,4 +829,5 @@ var cmpResult = this._cmp(curNode._key, key);

}
var nextKey = node._next()._key;
if (node === this._header._left) {
if (this._cmp(node._next()._key, key) > 0) {
if (this._cmp(nextKey, key) > 0) {
node._key = key;

@@ -879,4 +838,5 @@ return true;

}
var preKey = node._pre()._key;
if (node === this._header._right) {
if (this._cmp(node._pre()._key, key) < 0) {
if (this._cmp(preKey, key) < 0) {
node._key = key;

@@ -887,6 +847,3 @@ return true;

}
var preKey = node._pre()._key;
if (this._cmp(preKey, key) >= 0) return false;
var nextKey = node._next()._key;
if (this._cmp(nextKey, key) <= 0) return false;
if (this._cmp(preKey, key) >= 0 || this._cmp(nextKey, key) <= 0) return false;
node._key = key;

@@ -899,12 +856,4 @@ return true;

}
var index = 0;
var self = this;
this._inOrderTraversal(this._root, function (curNode) {
if (pos === index) {
self._eraseNode(curNode);
return true;
}
index += 1;
return false;
});
var node = this._inOrderTraversal(pos);
this._eraseNode(node);
return this._length;

@@ -919,3 +868,3 @@ };

if (this._length === 0) return false;
var curNode = this._findElementNode(this._root, key);
var curNode = this._getTreeNodeByKey(this._root, key);
if (curNode === this._header) return false;

@@ -944,51 +893,2 @@ this._eraseNode(curNode);

};
TreeContainer.prototype.forEach = function (callback) {
var e_1, _a;
var index = 0;
try {
for (var _b = __values(this), _c = _b.next(); !_c.done; _c = _b.next()) {
var element = _c.value;
callback(element, index++, this);
}
} catch (e_1_1) {
e_1 = {
error: e_1_1
};
} finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
} finally {
if (e_1) throw e_1.error;
}
}
};
TreeContainer.prototype.getElementByPos = function (pos) {
var e_2, _a;
if (pos < 0 || pos > this._length - 1) {
throw new RangeError();
}
var res;
var index = 0;
try {
for (var _b = __values(this), _c = _b.next(); !_c.done; _c = _b.next()) {
var element = _c.value;
if (index === pos) {
res = element;
break;
}
index += 1;
}
} catch (e_2_1) {
e_2 = {
error: e_2_1
};
} finally {
try {
if (_c && !_c.done && (_a = _b.return)) _a.call(_b);
} finally {
if (e_2) throw e_2.error;
}
}
return res;
};
/**

@@ -1000,6 +900,6 @@ * @description Get the height of the tree.

if (this._length === 0) return 0;
var traversal = function (curNode) {
function traversal(curNode) {
if (!curNode) return 0;
return Math.max(traversal(curNode._left), traversal(curNode._right)) + 1;
};
}
return traversal(this._root);

@@ -1150,24 +1050,2 @@ };

}
/**
* @internal
*/
OrderedMap.prototype._iterationFunc = function (curNode) {
return __generator(this, function (_a) {
switch (_a.label) {
case 0:
if (curNode === undefined) return [2 /*return*/];
return [5 /*yield**/, __values(this._iterationFunc(curNode._left))];
case 1:
_a.sent();
return [4 /*yield*/, [curNode._key, curNode._value]];
case 2:
_a.sent();
return [5 /*yield**/, __values(this._iterationFunc(curNode._right))];
case 3:
_a.sent();
return [2 /*return*/];
}
});
};
OrderedMap.prototype.begin = function () {

@@ -1213,2 +1091,7 @@ return new OrderedMapIterator(this._header._left || this._header, this._header, this);

};
OrderedMap.prototype.forEach = function (callback) {
this._inOrderTraversal(function (node, index, map) {
callback([node._key, node._value], index, map);
});
};
/**

@@ -1229,4 +1112,11 @@ * @description Insert a key-value pair or set value by the given key.

};
OrderedMap.prototype.getElementByPos = function (pos) {
if (pos < 0 || pos > this._length - 1) {
throw new RangeError();
}
var node = this._inOrderTraversal(pos);
return [node._key, node._value];
};
OrderedMap.prototype.find = function (key) {
var curNode = this._findElementNode(this._root, key);
var curNode = this._getTreeNodeByKey(this._root, key);
return new OrderedMapIterator(curNode, this._header, this);

@@ -1241,3 +1131,3 @@ };

OrderedMap.prototype.getElementByKey = function (key) {
var curNode = this._findElementNode(this._root, key);
var curNode = this._getTreeNodeByKey(this._root, key);
return curNode._value;

@@ -1253,4 +1143,26 @@ };

OrderedMap.prototype[Symbol.iterator] = function () {
return this._iterationFunc(this._root);
var length, nodeList, i, node;
return __generator(this, function (_a) {
switch (_a.label) {
case 0:
length = this._length;
nodeList = this._inOrderTraversal();
i = 0;
_a.label = 1;
case 1:
if (!(i < length)) return [3 /*break*/, 4];
node = nodeList[i];
return [4 /*yield*/, [node._key, node._value]];
case 2:
_a.sent();
_a.label = 3;
case 3:
++i;
return [3 /*break*/, 1];
case 4:
return [2 /*return*/];
}
});
};
return OrderedMap;

@@ -1257,0 +1169,0 @@ }(TreeContainer);

4

dist/umd/ordered-map.min.js
/*!
* @js-sdsl/ordered-map v4.3.0
* @js-sdsl/ordered-map v4.4.0
* https://github.com/js-sdsl/js-sdsl

@@ -7,3 +7,3 @@ * (c) 2021-present ZLY201 <zilongyao1366@gmail.com>

*/
!function(t,i){"object"==typeof exports&&"undefined"!=typeof module?i(exports):"function"==typeof define&&define.amd?define(["exports"],i):i((t="undefined"!=typeof globalThis?globalThis:t||self).sdsl={})}(this,function(t){"use strict";var e=function(t,i){return(e=Object.setPrototypeOf||({__proto__:[]}instanceof Array?function(t,i){t.__proto__=i}:function(t,i){for(var r in i)Object.prototype.hasOwnProperty.call(i,r)&&(t[r]=i[r])}))(t,i)};function i(t,i){if("function"!=typeof i&&null!==i)throw new TypeError("Class extends value "+String(i)+" is not a constructor or null");function r(){this.constructor=t}e(t,i),t.prototype=null===i?Object.create(i):(r.prototype=i.prototype,new r)}function r(e,o){var n,h,s,u={label:0,sent:function(){if(1&s[0])throw s[1];return s[1]},trys:[],ops:[]},f={next:t(0),throw:t(1),return:t(2)};return"function"==typeof Symbol&&(f[Symbol.iterator]=function(){return this}),f;function t(r){return function(t){var i=[r,t];if(n)throw new TypeError("Generator is already executing.");for(;u=f&&i[f=0]?0:u;)try{if(n=1,h&&(s=2&i[0]?h.return:i[0]?h.throw||((s=h.return)&&s.call(h),0):h.next)&&!(s=s.call(h,i[1])).done)return s;switch(h=0,(i=s?[2&i[0],s.value]:i)[0]){case 0:case 1:s=i;break;case 4:return u.label++,{value:i[1],done:!1};case 5:u.label++,h=i[1],i=[0];continue;case 7:i=u.ops.pop(),u.trys.pop();continue;default:if(!(s=0<(s=u.trys).length&&s[s.length-1])&&(6===i[0]||2===i[0])){u=0;continue}if(3===i[0]&&(!s||i[1]>s[0]&&i[1]<s[3]))u.label=i[1];else if(6===i[0]&&u.label<s[1])u.label=s[1],s=i;else{if(!(s&&u.label<s[2])){s[2]&&u.ops.pop(),u.trys.pop();continue}u.label=s[2],u.ops.push(i)}}i=o.call(e,u)}catch(t){i=[6,t],h=0}finally{n=s=0}if(5&i[0])throw i[1];return{value:i[0]?i[1]:void 0,done:!0}}}}function u(t){var i="function"==typeof Symbol&&Symbol.iterator,r=i&&t[i],e=0;if(r)return r.call(t);if(t&&"number"==typeof t.length)return{next:function(){return{value:(t=t&&e>=t.length?void 0:t)&&t[e++],done:!t}}};throw new TypeError(i?"Object is not iterable.":"Symbol.iterator is not defined.")}function o(t,i){var r="function"==typeof Symbol&&t[Symbol.iterator];if(!r)return t;var e,o,n=r.call(t),h=[];try{for(;(void 0===i||0<i--)&&!(e=n.next()).done;)h.push(e.value)}catch(t){o={error:t}}finally{try{e&&!e.done&&(r=n.return)&&r.call(n)}finally{if(o)throw o.error}}return h}h.prototype.v=function(){var t=this;if(1===t.t&&t.l.l===t)t=t.o;else if(t.h)for(t=t.h;t.o;)t=t.o;else{for(var i=t.l;i.h===t;)i=(t=i).l;t=i}return t},h.prototype.p=function(){var t=this;if(t.o){for(t=t.o;t.h;)t=t.h;return t}for(var i=t.l;i.o===t;)i=(t=i).l;return t.o!==i?i:t},h.prototype._=function(){var t=this.l,i=this.o,r=i.h;return t.l===this?t.l=i:t.h===this?t.h=i:t.o=i,i.l=t,(i.h=this).l=i,(this.o=r)&&(r.l=this),i},h.prototype.T=function(){var t=this.l,i=this.h,r=i.o;return t.l===this?t.l=i:t.h===this?t.h=i:t.o=i,i.l=t,(i.o=this).l=i,(this.h=r)&&(r.l=this),i};var n=h;function h(t,i){this.t=1,this.i=void 0,this.u=void 0,this.h=void 0,this.o=void 0,this.l=void 0,this.i=t,this.u=i}i(l,s=n),l.prototype._=function(){var t=s.prototype._.call(this);return this.C(),t.C(),t},l.prototype.T=function(){var t=s.prototype.T.call(this);return this.C(),t.C(),t},l.prototype.C=function(){this.O=1,this.h&&(this.O+=this.h.O),this.o&&(this.O+=this.o.O)};var s,f=l;function l(){var t=null!==s&&s.apply(this,arguments)||this;return t.O=1,t}p.prototype.equals=function(t){return this.I===t.I};var a=p;function p(t){this.iteratorType=t=void 0===t?0:t}function c(){this.M=0}Object.defineProperty(c.prototype,"length",{get:function(){return this.M},enumerable:!1,configurable:!0}),c.prototype.size=function(){return this.M},c.prototype.empty=function(){return 0===this.M};i(d,y=c);var y,v=d;function d(){return null!==y&&y.apply(this,arguments)||this}function S(){throw new RangeError("Iterator access denied!")}i(w,g=v),w.prototype.R=function(t,i){for(var r=this.S;t;){var e=this.N(t.i,i);if(e<0)t=t.o;else{if(!(0<e))return t;t=(r=t).h}}return r},w.prototype.G=function(t,i){for(var r=this.S;t;)t=this.N(t.i,i)<=0?t.o:(r=t).h;return r},w.prototype.q=function(t,i){for(var r=this.S;t;){var e=this.N(t.i,i);if(e<0)t=(r=t).o;else{if(!(0<e))return t;t=t.h}}return r},w.prototype.D=function(t,i){for(var r=this.S;t;)t=this.N(t.i,i)<0?(r=t).o:t.h;return r},w.prototype.F=function(t){for(;;){var i,r=t.l;if(r===this.S)return;if(1===t.t)return void(t.t=0);if(t===r.h)if(1===(i=r.o).t)i.t=0,r.t=1,r===this.g?this.g=r._():r._();else{if(i.o&&1===i.o.t)return i.t=r.t,r.t=0,i.o.t=0,void(r===this.g?this.g=r._():r._());i.h&&1===i.h.t?(i.t=1,i.h.t=0,i.T()):(i.t=1,t=r)}else if(1===(i=r.h).t)i.t=0,r.t=1,r===this.g?this.g=r.T():r.T();else{if(i.h&&1===i.h.t)return i.t=r.t,r.t=0,i.h.t=0,void(r===this.g?this.g=r.T():r.T());i.o&&1===i.o.t?(i.t=1,i.o.t=0,i._()):(i.t=1,t=r)}}},w.prototype.P=function(t){var i;if(1===this.M)return this.clear(),this.S;for(var r=t;r.h||r.o;){if(r.o)for(r=r.o;r.h;)r=r.h;else r=r.h;i=o([r.i,t.i],2),t.i=i[0],r.i=i[1],i=o([r.u,t.u],2),t.u=i[0],r.u=i[1],t=r}this.S.h===r?this.S.h=r.l:this.S.o===r&&(this.S.o=r.l),this.F(r);var e=r.l;return r===e.h?e.h=void 0:e.o=void 0,--this.M,this.g.t=0,e},w.prototype.H=function(t,i){return void 0!==t&&(!!this.H(t.h,i)||!!i(t)||this.H(t.o,i))},w.prototype.k=function(t){for(;;){var i=t.l;if(0===i.t)return;var r,e,o=i.l;if(i===o.h){if((r=o.o)&&1===r.t){if(r.t=i.t=0,o===this.g)return;o.t=1,t=o;continue}if(t===i.o)return t.t=0,t.h&&(t.h.l=i),t.o&&(t.o.l=o),i.o=t.h,o.h=t.o,t.h=i,(t.o=o)===this.g?(this.g=t,this.S.l=t):(e=o.l).h===o?e.h=t:e.o=t,t.l=o.l,i.l=t,o.l=t,o.t=1,{parentNode:i,grandParent:o,curNode:t};i.t=0,o===this.g?this.g=o.T():o.T()}else{if((r=o.h)&&1===r.t){if(r.t=i.t=0,o===this.g)return;o.t=1,t=o;continue}if(t===i.h)return t.t=0,t.h&&(t.h.l=o),t.o&&(t.o.l=i),o.o=t.h,i.h=t.o,t.h=o,t.o=i,o===this.g?(this.g=t,this.S.l=t):(e=o.l).h===o?e.h=t:e.o=t,t.l=o.l,i.l=t,o.l=t,o.t=1,{parentNode:i,grandParent:o,curNode:t};i.t=0,o===this.g?this.g=o._():o._()}return void(o.t=1)}},w.prototype.A=function(t,i,r){if(void 0===this.g)this.M+=1,this.g=new this.m(t,i),this.g.t=0,this.g.l=this.S,this.S.l=this.g,this.S.h=this.g,this.S.o=this.g;else{var e,o=this.S.h,n=this.N(o.i,t);if(0!==n){if(0<n)o.h=new this.m(t,i),e=(o.h.l=o).h,this.S.h=e;else{var n=this.S.o,h=this.N(n.i,t);if(0===h)return void(n.u=i);if(h<0)n.o=new this.m(t,i),e=(n.o.l=n).o,this.S.o=e;else{if(void 0!==r){h=r.I;if(h!==this.S){n=this.N(h.i,t);if(0===n)return void(h.u=i);if(0<n){r=h.v(),n=this.N(r.i,t);if(0===n)return void(r.u=i);n<0&&(e=new this.m(t,i),void 0===r.o?(r.o=e).l=r:(h.h=e).l=h)}}}if(void 0===e)for(e=this.g;;){var s=this.N(e.i,t);if(0<s){if(void 0===e.h){e.h=new this.m(t,i),e=(e.h.l=e).h;break}e=e.h}else{if(!(s<0))return void(e.u=i);if(void 0===e.o){e.o=new this.m(t,i),e=(e.o.l=e).o;break}e=e.o}}}}return this.M+=1,e}o.u=i}},w.prototype.J=function(t,i){for(;t;){var r=this.N(t.i,i);if(r<0)t=t.o;else{if(!(0<r))return t;t=t.h}}return t||this.S},w.prototype.clear=function(){this.M=0,this.g=void 0,this.S.l=void 0,this.S.h=this.S.o=void 0},w.prototype.updateKeyByIterator=function(t,i){t=t.I;if(t===this.S&&S(),1!==this.M){if(t===this.S.h)return 0<this.N(t.p().i,i)&&(t.i=i,!0);if(t===this.S.o)return this.N(t.v().i,i)<0&&(t.i=i,!0);var r=t.v().i;if(0<=this.N(r,i))return!1;if(r=t.p().i,this.N(r,i)<=0)return!1}return t.i=i,!0},w.prototype.eraseElementByPos=function(i){if(i<0||i>this.M-1)throw new RangeError;var r=0,e=this;return this.H(this.g,function(t){return i===r?(e.B(t),!0):(r+=1,!1)}),this.M},w.prototype.eraseElementByKey=function(t){return 0!==this.M&&(t=this.J(this.g,t))!==this.S&&(this.B(t),!0)},w.prototype.eraseElementByIterator=function(t){var i=t.I,r=(i===this.S&&S(),void 0===i.o);return 0===t.iteratorType?r&&t.next():r&&void 0!==i.h||t.next(),this.B(i),t},w.prototype.forEach=function(t){var i,r,e=0;try{for(var o=u(this),n=o.next();!n.done;n=o.next())t(n.value,e++,this)}catch(t){i={error:t}}finally{try{n&&!n.done&&(r=o.return)&&r.call(o)}finally{if(i)throw i.error}}},w.prototype.getElementByPos=function(t){var i,r,e;if(t<0||t>this.M-1)throw new RangeError;var o=0;try{for(var n=u(this),h=n.next();!h.done;h=n.next()){var s=h.value;if(o===t){e=s;break}o+=1}}catch(t){i={error:t}}finally{try{h&&!h.done&&(r=n.return)&&r.call(n)}finally{if(i)throw i.error}}return e},w.prototype.getHeight=function(){var i;return 0===this.M?0:(i=function(t){return t?Math.max(i(t.h),i(t.o))+1:0})(this.g)};var g,v=w;function w(t,i){void 0===t&&(t=function(t,i){return t<i?-1:i<t?1:0}),void 0===i&&(i=!1);var r=g.call(this)||this;return r.g=void 0,r.N=t,i?(r.m=f,r.j=function(t,i,r){t=this.A(t,i,r);if(t){for(var e=t.l;e!==this.S;)e.O+=1,e=e.l;var i=this.k(t);i&&(r=i.parentNode,t=i.grandParent,i=i.curNode,r.C(),t.C(),i.C())}return this.M},r.B=function(t){for(var i=this.P(t);i!==this.S;)--i.O,i=i.l}):(r.m=n,r.j=function(t,i,r){t=this.A(t,i,r);return t&&this.k(t),this.M},r.B=r.P),r.S=new r.m,r}i(m,b=a),Object.defineProperty(m.prototype,"index",{get:function(){var t=this.I,i=this.S.l;if(t===this.S)return i?i.O-1:0;var r=0;for(t.h&&(r+=t.h.O);t!==i;){var e=t.l;t===e.o&&(r+=1,e.h)&&(r+=e.h.O),t=e}return r},enumerable:!1,configurable:!0});var b,a=m;function m(t,i,r){r=b.call(this,r)||this;return r.I=t,r.S=i,0===r.iteratorType?(r.pre=function(){return this.I===this.S.h&&S(),this.I=this.I.v(),this},r.next=function(){return this.I===this.S&&S(),this.I=this.I.p(),this}):(r.pre=function(){return this.I===this.S.o&&S(),this.I=this.I.p(),this},r.next=function(){return this.I===this.S&&S(),this.I=this.I.v(),this}),r}i(O,I=a),Object.defineProperty(O.prototype,"pointer",{get:function(){this.I===this.S&&S();var e=this;return new Proxy([],{get:function(t,i){return"0"===i?e.I.i:"1"===i?e.I.u:void 0},set:function(t,i,r){if("1"!==i)throw new TypeError("props must be 1");return e.I.u=r,!0}})},enumerable:!1,configurable:!0}),O.prototype.copy=function(){return new O(this.I,this.S,this.container,this.iteratorType)};var I,M=O;function O(t,i,r,e){t=I.call(this,t,i,e)||this;return t.container=r,t}i(x,N=v),x.prototype.K=function(i){return r(this,function(t){switch(t.label){case 0:return void 0===i?[2]:[5,u(this.K(i.h))];case 1:return t.sent(),[4,[i.i,i.u]];case 2:return t.sent(),[5,u(this.K(i.o))];case 3:return t.sent(),[2]}})},x.prototype.begin=function(){return new M(this.S.h||this.S,this.S,this)},x.prototype.end=function(){return new M(this.S,this.S,this)},x.prototype.rBegin=function(){return new M(this.S.o||this.S,this.S,this,1)},x.prototype.rEnd=function(){return new M(this.S,this.S,this,1)},x.prototype.front=function(){var t;if(0!==this.M)return[(t=this.S.h).i,t.u]},x.prototype.back=function(){var t;if(0!==this.M)return[(t=this.S.o).i,t.u]},x.prototype.lowerBound=function(t){t=this.R(this.g,t);return new M(t,this.S,this)},x.prototype.upperBound=function(t){t=this.G(this.g,t);return new M(t,this.S,this)},x.prototype.reverseLowerBound=function(t){t=this.q(this.g,t);return new M(t,this.S,this)},x.prototype.reverseUpperBound=function(t){t=this.D(this.g,t);return new M(t,this.S,this)},x.prototype.setElement=function(t,i,r){return this.j(t,i,r)},x.prototype.find=function(t){t=this.J(this.g,t);return new M(t,this.S,this)},x.prototype.getElementByKey=function(t){return this.J(this.g,t).u},x.prototype.union=function(t){var i=this;return t.forEach(function(t){i.setElement(t[0],t[1])}),this.M},x.prototype[Symbol.iterator]=function(){return this.K(this.g)};var N,a=x;function x(t,i,r){void 0===t&&(t=[]);var i=N.call(this,i,r)||this,e=i;return t.forEach(function(t){e.setElement(t[0],t[1])}),i}t.OrderedMap=a,Object.defineProperty(t,"L",{value:!0})});
!function(t,i){"object"==typeof exports&&"undefined"!=typeof module?i(exports):"function"==typeof define&&define.amd?define(["exports"],i):i((t="undefined"!=typeof globalThis?globalThis:t||self).sdsl={})}(this,function(t){"use strict";var r=function(t,i){return(r=Object.setPrototypeOf||({__proto__:[]}instanceof Array?function(t,i){t.__proto__=i}:function(t,i){for(var e in i)Object.prototype.hasOwnProperty.call(i,e)&&(t[e]=i[e])}))(t,i)};function i(t,i){if("function"!=typeof i&&null!==i)throw new TypeError("Class extends value "+String(i)+" is not a constructor or null");function e(){this.constructor=t}r(t,i),t.prototype=null===i?Object.create(i):(e.prototype=i.prototype,new e)}function o(r,n){var o,s,h,u={label:0,sent:function(){if(1&h[0])throw h[1];return h[1]},trys:[],ops:[]},f={next:t(0),throw:t(1),return:t(2)};return"function"==typeof Symbol&&(f[Symbol.iterator]=function(){return this}),f;function t(e){return function(t){var i=[e,t];if(o)throw new TypeError("Generator is already executing.");for(;u=f&&i[f=0]?0:u;)try{if(o=1,s&&(h=2&i[0]?s.return:i[0]?s.throw||((h=s.return)&&h.call(s),0):s.next)&&!(h=h.call(s,i[1])).done)return h;switch(s=0,(i=h?[2&i[0],h.value]:i)[0]){case 0:case 1:h=i;break;case 4:return u.label++,{value:i[1],done:!1};case 5:u.label++,s=i[1],i=[0];continue;case 7:i=u.ops.pop(),u.trys.pop();continue;default:if(!(h=0<(h=u.trys).length&&h[h.length-1])&&(6===i[0]||2===i[0])){u=0;continue}if(3===i[0]&&(!h||i[1]>h[0]&&i[1]<h[3]))u.label=i[1];else if(6===i[0]&&u.label<h[1])u.label=h[1],h=i;else{if(!(h&&u.label<h[2])){h[2]&&u.ops.pop(),u.trys.pop();continue}u.label=h[2],u.ops.push(i)}}i=n.call(r,u)}catch(t){i=[6,t],s=0}finally{o=h=0}if(5&i[0])throw i[1];return{value:i[0]?i[1]:void 0,done:!0}}}}e.prototype.v=function(){var t=this;if(1===t.l&&t.h.h===t)t=t.i;else if(t.t)for(t=t.t;t.i;)t=t.i;else{for(var i=t.h;i.t===t;)i=(t=i).h;t=i}return t},e.prototype.p=function(){var t=this;if(t.i){for(t=t.i;t.t;)t=t.t;return t}for(var i=t.h;i.i===t;)i=(t=i).h;return t.i!==i?i:t},e.prototype.T=function(){var t=this.h,i=this.i,e=i.t;return t.h===this?t.h=i:t.t===this?t.t=i:t.i=i,i.h=t,(i.t=this).h=i,(this.i=e)&&(e.h=this),i},e.prototype.O=function(){var t=this.h,i=this.t,e=i.i;return t.h===this?t.h=i:t.t===this?t.t=i:t.i=i,i.h=t,(i.i=this).h=i,(this.t=e)&&(e.h=this),i};var n=e;function e(t,i,e){void 0===e&&(e=1),this.t=void 0,this.i=void 0,this.h=void 0,this.u=t,this.o=i,this.l=e}i(u,s=n),u.prototype.T=function(){var t=s.prototype.T.call(this);return this.I(),t.I(),t},u.prototype.O=function(){var t=s.prototype.O.call(this);return this.I(),t.I(),t},u.prototype.I=function(){this._=1,this.t&&(this._+=this.t._),this.i&&(this._+=this.i._)};var s,h=u;function u(){var t=null!==s&&s.apply(this,arguments)||this;return t._=1,t}p.prototype.equals=function(t){return this.M===t.M};var f=p;function p(t){this.iteratorType=t=void 0===t?0:t}function l(){this.C=0}Object.defineProperty(l.prototype,"length",{get:function(){return this.C},enumerable:!1,configurable:!0}),l.prototype.size=function(){return this.C},l.prototype.empty=function(){return 0===this.C};i(y,a=l);var a,c=y;function y(){return null!==a&&a.apply(this,arguments)||this}function v(){throw new RangeError("Iterator access denied!")}i(g,d=c),g.prototype.j=function(t,i){for(var e=this.A;t;){var r=this.N(t.u,i);if(r<0)t=t.i;else{if(!(0<r))return t;t=(e=t).t}}return e},g.prototype.k=function(t,i){for(var e=this.A;t;)t=this.N(t.u,i)<=0?t.i:(e=t).t;return e},g.prototype.B=function(t,i){for(var e=this.A;t;){var r=this.N(t.u,i);if(r<0)t=(e=t).i;else{if(!(0<r))return t;t=t.t}}return e},g.prototype.S=function(t,i){for(var e=this.A;t;)t=this.N(t.u,i)<0?(e=t).i:t.t;return e},g.prototype.R=function(t){for(;;){var i,e=t.h;if(e===this.A)return;if(1===t.l)return void(t.l=0);if(t===e.t)if(1===(i=e.i).l)i.l=0,e.l=1,e===this.g?this.g=e.T():e.T();else{if(i.i&&1===i.i.l)return i.l=e.l,e.l=0,i.i.l=0,void(e===this.g?this.g=e.T():e.T());i.t&&1===i.t.l?(i.l=1,i.t.l=0,i.O()):(i.l=1,t=e)}else if(1===(i=e.t).l)i.l=0,e.l=1,e===this.g?this.g=e.O():e.O();else{if(i.t&&1===i.t.l)return i.l=e.l,e.l=0,i.t.l=0,void(e===this.g?this.g=e.O():e.O());i.i&&1===i.i.l?(i.l=1,i.i.l=0,i.T()):(i.l=1,t=e)}}},g.prototype.G=function(t){if(1===this.C)this.clear();else{for(var i=t;i.t||i.i;){if(i.i)for(i=i.i;i.t;)i=i.t;else i=i.t;var e=t.u,e=(t.u=i.u,i.u=e,t.o);t.o=i.o,i.o=e,t=i}this.A.t===i?this.A.t=i.h:this.A.i===i&&(this.A.i=i.h),this.R(i);var r=i.h;if(i===r.t?r.t=void 0:r.i=void 0,--this.C,this.g.l=0,this.enableIndex)for(;r!==this.A;)--r._,r=r.h}},g.prototype.P=function(t){for(var i="number"==typeof t?t:void 0,e="function"==typeof t?t:void 0,r=void 0===t?[]:void 0,n=0,o=this.g,s=[];s.length||o;)if(o)s.push(o),o=o.t;else{if(o=s.pop(),n===i)return o;r&&r.push(o),e&&e(o,n,this),n+=1,o=o.i}return r},g.prototype.q=function(t){for(;;){var i=t.h;if(0===i.l)return;var e,r,n=i.h;if(i===n.t){if((e=n.i)&&1===e.l){if(e.l=i.l=0,n===this.g)return;n.l=1,t=n;continue}if(t!==i.i)return i.l=0,n===this.g?this.g=n.O():n.O(),void(n.l=1);t.l=0,t.t&&(t.t.h=i),t.i&&(t.i.h=n),i.i=t.t,n.t=t.i,t.t=i,(t.i=n)===this.g?(this.g=t,this.A.h=t):(r=n.h).t===n?r.t=t:r.i=t}else{if((e=n.t)&&1===e.l){if(e.l=i.l=0,n===this.g)return;n.l=1,t=n;continue}if(t!==i.t)return i.l=0,n===this.g?this.g=n.T():n.T(),void(n.l=1);t.l=0,t.t&&(t.t.h=n),t.i&&(t.i.h=i),n.i=t.t,i.t=t.i,t.t=n,t.i=i,n===this.g?(this.g=t,this.A.h=t):(r=n.h).t===n?r.t=t:r.i=t}return t.h=n.h,i.h=t,n.h=t,n.l=1,void(this.enableIndex&&(i.I(),n.I(),t.I()))}},g.prototype.D=function(t,i,e){if(void 0===this.g)this.C+=1,this.g=new this.m(t,i,0),this.g.h=this.A,this.A.h=this.A.t=this.A.i=this.g;else{var r,n=this.A.t,o=this.N(n.u,t);if(0===o)n.o=i;else{if(0<o)n.t=new this.m(t,i),r=(n.t.h=n).t,this.A.t=r;else{o=this.A.i,n=this.N(o.u,t);if(0===n)return o.o=i,this.C;if(n<0)o.i=new this.m(t,i),r=(o.i.h=o).i,this.A.i=r;else{if(void 0!==e){n=e.M;if(n!==this.A){o=this.N(n.u,t);if(0===o)return n.o=i,this.C;if(0<o){e=n.v(),o=this.N(e.u,t);if(0===o)return e.o=i,this.C;o<0&&(r=new this.m(t,i),void 0===e.i?(e.i=r).h=e:(n.t=r).h=n)}}}if(void 0===r)for(r=this.g;;){var s=this.N(r.u,t);if(0<s){if(void 0===r.t){r.t=new this.m(t,i),r=(r.t.h=r).t;break}r=r.t}else{if(!(s<0))return r.o=i,this.C;if(void 0===r.i){r.i=new this.m(t,i),r=(r.i.h=r).i;break}r=r.i}}}}if(this.enableIndex)for(var h=r.h;h!==this.A;)h._+=1,h=h.h;this.q(r),this.C+=1}}return this.C},g.prototype.F=function(t,i){for(;t;){var e=this.N(t.u,i);if(e<0)t=t.i;else{if(!(0<e))return t;t=t.t}}return t||this.A},g.prototype.clear=function(){this.C=0,this.g=void 0,this.A.h=void 0,this.A.t=this.A.i=void 0},g.prototype.updateKeyByIterator=function(t,i){t=t.M;if(t===this.A&&v(),1!==this.C){var e=t.p().u;if(t===this.A.t)return 0<this.N(e,i)&&(t.u=i,!0);var r=t.v().u;if(t===this.A.i)return this.N(r,i)<0&&(t.u=i,!0);if(0<=this.N(r,i)||this.N(e,i)<=0)return!1}return t.u=i,!0},g.prototype.eraseElementByPos=function(t){if(t<0||t>this.C-1)throw new RangeError;t=this.P(t);return this.G(t),this.C},g.prototype.eraseElementByKey=function(t){return 0!==this.C&&(t=this.F(this.g,t))!==this.A&&(this.G(t),!0)},g.prototype.eraseElementByIterator=function(t){var i=t.M,e=(i===this.A&&v(),void 0===i.i);return 0===t.iteratorType?e&&t.next():e&&void 0!==i.t||t.next(),this.G(i),t},g.prototype.getHeight=function(){return 0===this.C?0:function t(i){return i?Math.max(t(i.t),t(i.i))+1:0}(this.g)};var d,c=g;function g(t,i){void 0===t&&(t=function(t,i){return t<i?-1:i<t?1:0}),void 0===i&&(i=!1);var e=d.call(this)||this;return e.g=void 0,e.N=t,e.enableIndex=i,e.m=i?h:n,e.A=new e.m,e}i(b,A=f),Object.defineProperty(b.prototype,"index",{get:function(){var t=this.M,i=this.A.h;if(t===this.A)return i?i._-1:0;var e=0;for(t.t&&(e+=t.t._);t!==i;){var r=t.h;t===r.i&&(e+=1,r.t)&&(e+=r.t._),t=r}return e},enumerable:!1,configurable:!0});var A,f=b;function b(t,i,e){e=A.call(this,e)||this;return e.M=t,e.A=i,0===e.iteratorType?(e.pre=function(){return this.M===this.A.t&&v(),this.M=this.M.v(),this},e.next=function(){return this.M===this.A&&v(),this.M=this.M.p(),this}):(e.pre=function(){return this.M===this.A.i&&v(),this.M=this.M.p(),this},e.next=function(){return this.M===this.A&&v(),this.M=this.M.v(),this}),e}i(M,w=f),Object.defineProperty(M.prototype,"pointer",{get:function(){this.M===this.A&&v();var r=this;return new Proxy([],{get:function(t,i){return"0"===i?r.M.u:"1"===i?r.M.o:void 0},set:function(t,i,e){if("1"!==i)throw new TypeError("props must be 1");return r.M.o=e,!0}})},enumerable:!1,configurable:!0}),M.prototype.copy=function(){return new M(this.M,this.A,this.container,this.iteratorType)};var w,m=M;function M(t,i,e,r){t=w.call(this,t,i,r)||this;return t.container=e,t}i(O,C=c),O.prototype.begin=function(){return new m(this.A.t||this.A,this.A,this)},O.prototype.end=function(){return new m(this.A,this.A,this)},O.prototype.rBegin=function(){return new m(this.A.i||this.A,this.A,this,1)},O.prototype.rEnd=function(){return new m(this.A,this.A,this,1)},O.prototype.front=function(){var t;if(0!==this.C)return[(t=this.A.t).u,t.o]},O.prototype.back=function(){var t;if(0!==this.C)return[(t=this.A.i).u,t.o]},O.prototype.lowerBound=function(t){t=this.j(this.g,t);return new m(t,this.A,this)},O.prototype.upperBound=function(t){t=this.k(this.g,t);return new m(t,this.A,this)},O.prototype.reverseLowerBound=function(t){t=this.B(this.g,t);return new m(t,this.A,this)},O.prototype.reverseUpperBound=function(t){t=this.S(this.g,t);return new m(t,this.A,this)},O.prototype.forEach=function(r){this.P(function(t,i,e){r([t.u,t.o],i,e)})},O.prototype.setElement=function(t,i,e){return this.D(t,i,e)},O.prototype.getElementByPos=function(t){if(t<0||t>this.C-1)throw new RangeError;t=this.P(t);return[t.u,t.o]},O.prototype.find=function(t){t=this.F(this.g,t);return new m(t,this.A,this)},O.prototype.getElementByKey=function(t){return this.F(this.g,t).o},O.prototype.union=function(t){var i=this;return t.forEach(function(t){i.setElement(t[0],t[1])}),this.C},O.prototype[Symbol.iterator]=function(){var i,e,r,n;return o(this,function(t){switch(t.label){case 0:i=this.C,e=this.P(),r=0,t.label=1;case 1:return r<i?[4,[(n=e[r]).u,n.o]]:[3,4];case 2:t.sent(),t.label=3;case 3:return++r,[3,1];case 4:return[2]}})};var C,f=O;function O(t,i,e){void 0===t&&(t=[]);var i=C.call(this,i,e)||this,r=i;return t.forEach(function(t){r.setElement(t[0],t[1])}),i}t.OrderedMap=f,Object.defineProperty(t,"H",{value:!0})});
//# sourceMappingURL=ordered-map.min.js.map

2

package.json
{
"name": "@js-sdsl/ordered-map",
"version": "4.3.0",
"version": "4.4.0",
"description": "javascript standard data structure library which benchmark against C++ STL",

@@ -5,0 +5,0 @@ "main": "./dist/cjs/index.js",

46

README.md

@@ -42,38 +42,5 @@ <p align="center">

<table>
<tr align="center">
<td>
<img alt="IE / Edge" src="https://js-sdsl.org/assets/image/platform/edge.png" />
<div>IE / Edge</div>
</td>
<td>
<img alt="Firefox" src="https://js-sdsl.org/assets/image/platform/firefox.png" />
<div>Firefox</div>
</td>
<td>
<img alt="Chrome" src="https://js-sdsl.org/assets/image/platform/chrome.png" />
<div>Chrome</div>
</td>
<td>
<img alt="Safari" src="https://js-sdsl.org/assets/image/platform/safari.png" />
<div>Safari</div>
</td>
<td>
<img alt="Opera" src="https://js-sdsl.org/assets/image/platform/opera.png" />
<div>Opera</div>
</td>
<td>
<img alt="NodeJs" src="https://js-sdsl.org/assets/image/platform/nodejs.png" />
<div>NodeJs</div>
</td>
</tr>
<tr align="center">
<td>Edge 12</td>
<td>31</td>
<td>49</td>
<td>10</td>
<td>36</td>
<td>10</td>
</tr>
</table>
| ![][Edge-Icon]<br/>IE / Edge | ![][Firefox-Icon]<br/>Firefox | ![][Chrome-Icon]<br/>Chrome | ![][Safari-Icon]<br/>Safari | ![][Opera-Icon]<br/>Opera | ![][NodeJs-Icon]<br/>NodeJs |
|:----------------------------:|:-----------------------------:|:---------------------------:|:---------------------------:|:-------------------------:|:---------------------------:|
| Edge 12 | 36 | 49 | 10 | 36 | 10 |

@@ -229,2 +196,9 @@ ## 📦 Download

[Edge-Icon]: https://js-sdsl.org/assets/image/platform/edge.png
[Firefox-Icon]: https://js-sdsl.org/assets/image/platform/firefox.png
[Chrome-Icon]: https://js-sdsl.org/assets/image/platform/chrome.png
[Safari-Icon]: https://js-sdsl.org/assets/image/platform/safari.png
[Opera-Icon]: https://js-sdsl.org/assets/image/platform/opera.png
[NodeJs-Icon]: https://js-sdsl.org/assets/image/platform/nodejs.png
[stack-package]: https://github.com/js-sdsl/js-sdsl/blob/main/src/container/OtherContainer/Stack.ts

@@ -231,0 +205,0 @@ [stack-npm-version]: https://img.shields.io/npm/v/@js-sdsl/stack

46

README.zh-CN.md

@@ -44,38 +44,5 @@ <p align="center">

<table>
<tr align="center">
<td>
<img alt="IE / Edge" src="https://js-sdsl.org/assets/image/platform/edge.png" />
<div>IE / Edge</div>
</td>
<td>
<img alt="Firefox" src="https://js-sdsl.org/assets/image/platform/firefox.png" />
<div>Firefox</div>
</td>
<td>
<img alt="Chrome" src="https://js-sdsl.org/assets/image/platform/chrome.png" />
<div>Chrome</div>
</td>
<td>
<img alt="Safari" src="https://js-sdsl.org/assets/image/platform/safari.png" />
<div>Safari</div>
</td>
<td>
<img alt="Opera" src="https://js-sdsl.org/assets/image/platform/opera.png" />
<div>Opera</div>
</td>
<td>
<img alt="NodeJs" src="https://js-sdsl.org/assets/image/platform/nodejs.png" />
<div>NodeJs</div>
</td>
</tr>
<tr align="center">
<td>Edge 12</td>
<td>31</td>
<td>49</td>
<td>10</td>
<td>36</td>
<td>10</td>
</tr>
</table>
| ![][Edge-Icon]<br/>IE / Edge | ![][Firefox-Icon]<br/>Firefox | ![][Chrome-Icon]<br/>Chrome | ![][Safari-Icon]<br/>Safari | ![][Opera-Icon]<br/>Opera | ![][NodeJs-Icon]<br/>NodeJs |
|:----------------------------:|:-----------------------------:|:---------------------------:|:---------------------------:|:-------------------------:|:---------------------------:|
| Edge 12 | 36 | 49 | 10 | 36 | 10 |

@@ -231,2 +198,9 @@ ## 📦 下载

[Edge-Icon]: https://js-sdsl.org/assets/image/platform/edge.png
[Firefox-Icon]: https://js-sdsl.org/assets/image/platform/firefox.png
[Chrome-Icon]: https://js-sdsl.org/assets/image/platform/chrome.png
[Safari-Icon]: https://js-sdsl.org/assets/image/platform/safari.png
[Opera-Icon]: https://js-sdsl.org/assets/image/platform/opera.png
[NodeJs-Icon]: https://js-sdsl.org/assets/image/platform/nodejs.png
[stack-package]: https://github.com/js-sdsl/js-sdsl/blob/main/src/container/OtherContainer/Stack.ts

@@ -233,0 +207,0 @@ [stack-npm-version]: https://img.shields.io/npm/v/@js-sdsl/stack

dist/cjs/index.js.map

Sorry, the diff of this file is not supported yet

dist/esm/index.js.map

Sorry, the diff of this file is not supported yet

dist/umd/ordered-map.min.js.map

Sorry, the diff of this file is not supported yet