🚀 Big News: Socket Acquires Coana to Bring Reachability Analysis to Every Appsec Team.Learn more →
Socket
DemoInstallSign in
Socket
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.2.0-beta.1
to
4.2.0

22

CHANGELOG.md

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

## [4.2.0] - 2022.11.20
### Changed
- Optimized the structure of class `TreeNodeEnableIndex`.
- Change the `iterator access denied` error message to reduce the packing size.
- Change the internal storage of the hash container to the form of a linked list, traversing in insertion order.
- Standardize hash container. Make it extends from `Container` and add general functions.
- Refactor `LinkList` to do optimization.
### Added
- Add public `length` property to all the container.
- Add returned value to `pop` function including `popBack` and `popFront` to all the container which has such function.
- Add returned value to `eraseElementByKey` which means whether erase successfully.
- Add returned value to `push` or `insert` function which means the size of the container.
### Fixed
- Fixed wrong error type when `updateKeyByIterator`.
- Fixed wrong iterator was returned when erase tree reverse iterator.
## [4.2.0-beta.1] - 2022.11.06

@@ -9,0 +31,0 @@

221

dist/cjs/index.d.ts

@@ -0,1 +1,4 @@

/**
* @description The iterator type including `NORMAL` and `REVERSE`.
*/
declare const enum IteratorType {

@@ -8,10 +11,18 @@ NORMAL = 0,

* @description Iterator's type.
* @example console.log(container.end().iteratorType === IteratorType.NORMAL); // true
* @example
* console.log(container.end().iteratorType === IteratorType.NORMAL); // true
*/
readonly iteratorType: IteratorType;
protected constructor(iteratorType?: IteratorType);
/**
* @param iter - The other iterator you want to compare.
* @returns Whether this equals to obj.
* @example
* container.find(1).equals(container.end());
*/
equals(iter: ContainerIterator<T>): boolean;
/**
* @description Pointers to element.
* @return The value of the pointer's element.
* @example const val = container.begin().pointer;
* @returns The value of the pointer's element.
* @example
* const val = container.begin().pointer;
*/

@@ -21,4 +32,5 @@ abstract get pointer(): T;

* @description Set pointer's value (some containers are unavailable).
* @param newValue The new value you want to set.
* @example (<LinkList<number>>container).begin().pointer = 1;
* @param newValue - The new value you want to set.
* @example
* (<LinkList<number>>container).begin().pointer = 1;
*/

@@ -28,2 +40,3 @@ abstract set pointer(newValue: T);

* @description Move `this` iterator to pre.
* @returns The iterator's self.
* @example

@@ -39,2 +52,3 @@ * const iter = container.find(1); // container = [0, 1]

* @description Move `this` iterator to next.
* @returns The iterator's self.
* @example

@@ -49,10 +63,4 @@ * const iter = container.find(1); // container = [1, 2]

/**
* @param obj The other iterator you want to compare.
* @return Boolean about if this equals to obj.
* @example container.find(1).equals(container.end());
*/
abstract equals(obj: ContainerIterator<T>): boolean;
/**
* @description Get a copy of itself.
* @return The copy of self.
* @returns The copy of self.
* @example

@@ -69,5 +77,12 @@ * const iter = container.find(1); // container = [1, 2]

/**
* @return The size of the container.
* @returns The size of the container.
* @example
* const container = new Vector([1, 2]);
* console.log(container.length); // 2
*/
get length(): number;
/**
* @returns The size of the container.
* @example
* const container = new Vector([1, 2]);
* console.log(container.size()); // 2

@@ -77,3 +92,3 @@ */

/**
* @return Boolean about if the container is empty.
* @returns Whether the container is empty.
* @example

@@ -94,3 +109,3 @@ * container.clear();

/**
* @return Iterator pointing to the beginning element.
* @returns Iterator pointing to the beginning element.
* @example

@@ -105,3 +120,3 @@ * const begin = container.begin();

/**
* @return Iterator pointing to the super end like c++.
* @returns Iterator pointing to the super end like c++.
* @example

@@ -116,3 +131,3 @@ * const begin = container.begin();

/**
* @return Iterator pointing to the end element.
* @returns Iterator pointing to the end element.
* @example

@@ -127,3 +142,3 @@ * const rBegin = container.rBegin();

/**
* @return Iterator pointing to the super begin like c++.
* @returns Iterator pointing to the super begin like c++.
* @example

@@ -138,22 +153,24 @@ * const rBegin = container.rBegin();

/**
* @return The first element of the container.
* @returns The first element of the container.
*/
abstract front(): T | undefined;
/**
* @return The last element of the container.
* @returns The last element of the container.
*/
abstract back(): T | undefined;
/**
* @param element - The element you want to find.
* @returns An iterator pointing to the element if found, or super end if not found.
* @example
* container.find(1).equals(container.end());
*/
abstract find(element: T): ContainerIterator<T>;
/**
* @description Iterate over all elements in the container.
* @param callback Callback function like Array.forEach.
* @example container.forEach((element, index) => console.log(element, index));
* @param callback - Callback function like Array.forEach.
* @example
* container.forEach((element, index) => console.log(element, index));
*/
abstract forEach(callback: (element: T, index: number, container: Container<T>) => void): void;
/**
* @param element The element you want to find.
* @return An iterator pointing to the element if found, or super end if not found.
* @example container.find(1).equals(container.end());
*/
abstract find(element: T): ContainerIterator<T>;
/**
* @description Gets the value of the element at the specified position.

@@ -166,9 +183,12 @@ * @example

* @description Removes the element at the specified position.
* @param pos The element's position you want to remove.
* @param pos - The element's position you want to remove.
* @returns The container length after erasing.
* @example
* container.eraseElementByPos(-1); // throw a RangeError
*/
abstract eraseElementByPos(pos: number): void;
abstract eraseElementByPos(pos: number): number;
/**
* @description Removes element by iterator and move `iter` to next.
* @param iter The iterator you want to erase.
* @param iter - The iterator you want to erase.
* @returns The next iterator.
* @example

@@ -186,4 +206,7 @@ * container.eraseElementByIterator(container.begin());

*/
abstract [Symbol.iterator](): Generator<T, void, undefined>;
abstract [Symbol.iterator](): Generator<T, void>;
}
/**
* @description The initial data type passed in when initializing the container.
*/
type initContainer<T> = ({

@@ -202,10 +225,7 @@ size: number;

]> {
pre: () => this;
next: () => this;
/**
* @description Get the sequential index of the iterator in the tree container.<br/>
* <strong>
* Note:
* </strong>
* <strong>Note:</strong>
* This function only takes effect when the specified tree container `enableIndex = true`.
* @returns The index subscript of the node in the tree.
* @example

@@ -216,3 +236,6 @@ * const st = new OrderedSet([1, 2, 3], true);

get index(): number;
equals(obj: TreeIterator<K, V>): boolean;
// @ts-ignore
pre(): this;
// @ts-ignore
next(): this;
}

@@ -223,56 +246,61 @@ declare abstract class TreeContainer<K, V> extends Container<K | [

]> {
clear(): void;
/**
* @param cmp The compare function.
* @param enableIndex Whether to enable iterator indexing function.
* @description Update node's key by iterator.
* @param iter - The iterator you want to change.
* @param key - The key you want to update.
* @returns Whether the modification is successful.
* @example
* const st = new orderedSet([1, 2, 5]);
* const iter = st.find(2);
* st.updateKeyByIterator(iter, 3); // then st will become [1, 3, 5]
*/
protected constructor(cmp?: (x: K, y: K) => number, enableIndex?: boolean);
updateKeyByIterator(iter: TreeIterator<K, V>, key: K): boolean;
eraseElementByPos(pos: number): number;
/**
* @param key The given key you want to compare.
* @return An iterator to the first element not less than the given key.
* @description Remove the element of the specified key.
* @param key - The key you want to remove.
* @returns Whether erase successfully.
*/
abstract lowerBound(key: K): TreeIterator<K, V>;
eraseElementByKey(key: K): boolean;
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
];
/**
* @param key The given key you want to compare.
* @return An iterator to the first element greater than the given key.
* @description Get the height of the tree.
* @returns Number about the height of the RB-tree.
*/
abstract upperBound(key: K): TreeIterator<K, V>;
getHeight(): number;
/**
* @param key The given key you want to compare.
* @return An iterator to the first element not greater than the given key.
* @param key - The given key you want to compare.
* @returns An iterator to the first element less than the given key.
*/
abstract reverseLowerBound(key: K): TreeIterator<K, V>;
/**
* @param key The given key you want to compare.
* @return An iterator to the first element less than the given key.
*/
abstract reverseUpperBound(key: K): TreeIterator<K, V>;
/**
* @description Union the other tree to self.
* @param other The other tree container you want to merge.
* @param other - The other tree container you want to merge.
* @returns The size of the tree after union.
*/
abstract union(other: TreeContainer<K, V>): void;
clear(): void;
abstract union(other: TreeContainer<K, V>): number;
/**
* @description Update node's key by iterator.
* @param iter The iterator you want to change.
* @param key The key you want to update.
* @return Boolean about if the modification is successful.
* @example
* const st = new orderedSet([1, 2, 5]);
* const iter = st.find(2);
* st.updateKeyByIterator(iter, 3); // then st will become [1, 3, 5]
* @param key - The given key you want to compare.
* @returns An iterator to the first element not greater than the given key.
*/
updateKeyByIterator(iter: TreeIterator<K, V>, key: K): boolean;
eraseElementByPos(pos: number): void;
abstract reverseLowerBound(key: K): TreeIterator<K, V>;
/**
* @description Remove the element of the specified key.
* @param key The key you want to remove.
* @param key - The given key you want to compare.
* @returns An iterator to the first element not less than the given key.
*/
eraseElementByKey(key: K): void;
eraseElementByIterator(iter: TreeIterator<K, V>): TreeIterator<K, V>;
abstract lowerBound(key: K): TreeIterator<K, V>;
/**
* @description Get the height of the tree.
* @return Number about the height of the RB-tree.
* @param key - The given key you want to compare.
* @returns An iterator to the first element greater than the given key.
*/
getHeight(): number;
abstract upperBound(key: K): TreeIterator<K, V>;
}

@@ -285,8 +313,10 @@ declare class OrderedMapIterator<K, V> extends TreeIterator<K, V> {

copy(): OrderedMapIterator<K, V>;
// @ts-ignore
equals(iter: OrderedMapIterator<K, V>): boolean;
}
declare class OrderedMap<K, V> extends TreeContainer<K, V> {
/**
* @param container The initialization container.
* @param cmp The compare function.
* @param enableIndex Whether to enable iterator indexing function.
* @param container - The initialization container.
* @param cmp - The compare function.
* @param enableIndex - Whether to enable iterator indexing function.
* @example

@@ -314,6 +344,2 @@ * new OrderedMap();

] | undefined;
forEach(callback: (element: [
K,
V
], index: number, map: OrderedMap<K, V>) => void): void;
lowerBound(key: K): OrderedMapIterator<K, V>;

@@ -325,5 +351,6 @@ upperBound(key: K): OrderedMapIterator<K, V>;

* @description Insert a key-value pair or set value by the given key.
* @param key The key want to insert.
* @param value The value want to set.
* @param hint You can give an iterator hint to improve insertion efficiency.
* @param key - The key want to insert.
* @param value - The value want to set.
* @param hint - You can give an iterator hint to improve insertion efficiency.
* @return The size of container after setting.
* @example

@@ -335,9 +362,24 @@ * const mp = new OrderedMap([[2, 0], [4, 0], [5, 0]]);

*/
setElement(key: K, value: V, hint?: OrderedMapIterator<K, V>): void;
setElement(key: K, value: V, hint?: OrderedMapIterator<K, V>): number;
find(key: K): OrderedMapIterator<K, V>;
/**
* @description Get the value of the element of the specified key.
* @example const val = container.getElementByKey(1);
* @param key - The specified key you want to get.
* @example
* const val = container.getElementByKey(1);
*/
getElementByKey(key: K): V | undefined;
union(other: OrderedMap<K, V>): number;
[Symbol.iterator](): Generator<[
K,
V
], void, unknown>;
// @ts-ignore
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): [

@@ -347,9 +389,4 @@ K,

];
union(other: OrderedMap<K, V>): void;
[Symbol.iterator](): Generator<[
K,
V
], void, undefined>;
}
export { OrderedMap };
export type { OrderedMapIterator, IteratorType, Container, ContainerIterator, TreeContainer };

1048

dist/cjs/index.js

@@ -8,3 +8,3 @@ "use strict";

class TreeNode {
constructor(e, t) {
constructor(t, e) {
this.i = 1;

@@ -16,66 +16,66 @@ this.h = undefined;

this.p = undefined;
this.h = e;
this.o = t;
this.h = t;
this.o = e;
}
pre() {
let e = this;
if (e.i === 1 && e.p.p === e) {
e = e.l;
} else if (e.u) {
e = e.u;
while (e.l) {
e = e.l;
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;
}
} else {
let t = e.p;
while (t.u === e) {
e = t;
t = e.p;
let e = t.p;
while (e.u === t) {
t = e;
e = t.p;
}
e = t;
t = e;
}
return e;
return t;
}
next() {
let e = this;
if (e.l) {
e = e.l;
while (e.u) {
e = e.u;
_() {
let t = this;
if (t.l) {
t = t.l;
while (t.u) {
t = t.u;
}
return e;
return t;
} else {
let t = e.p;
while (t.l === e) {
e = t;
t = e.p;
let e = t.p;
while (e.l === t) {
t = e;
e = t.p;
}
if (e.l !== t) {
return t;
} else return e;
if (t.l !== e) {
return e;
} else return t;
}
}
rotateLeft() {
const e = this.p;
const t = this.l;
const i = t.u;
if (e.p === this) e.p = t; else if (e.u === this) e.u = t; else e.l = t;
t.p = e;
t.u = this;
this.p = t;
this.l = i;
if (i) i.p = this;
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;
return e;
}
rotateRight() {
const e = this.p;
const t = this.u;
const i = t.l;
if (e.p === this) e.p = t; else if (e.u === this) e.u = t; else e.l = t;
t.p = e;
t.l = this;
this.p = t;
this.u = i;
if (i) i.p = this;
return t;
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;
return e;
}

@@ -87,23 +87,24 @@ }

super(...arguments);
this.u = undefined;
this.l = undefined;
this.p = undefined;
this.g = 1;
this.M = 1;
}
rotateLeft() {
const e = super.rotateLeft();
this.recount();
e.recount();
return e;
g() {
const t = super.g();
this.N();
t.N();
return t;
}
rotateRight() {
const e = super.rotateRight();
this.recount();
e.recount();
return e;
B() {
const t = super.B();
this.N();
t.N();
return t;
}
recount() {
this.g = 1;
if (this.u) this.g += this.u.g;
if (this.l) this.g += this.l.g;
N() {
this.M = 1;
if (this.u) {
this.M += this.u.M;
}
if (this.l) {
this.M += this.l.M;
}
}

@@ -113,5 +114,8 @@ }

class ContainerIterator {
constructor(e = 0) {
this.iteratorType = e;
constructor(t = 0) {
this.iteratorType = t;
}
equals(t) {
return this.O === t.O;
}
}

@@ -121,9 +125,12 @@

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

@@ -134,157 +141,163 @@ }

function throwIteratorAccessError() {
throw new RangeError("Iterator access denied!");
}
class TreeContainer extends Container {
constructor(e = function(e, t) {
if (e < t) return -1;
if (e > t) return 1;
constructor(t = function(t, e) {
if (t < e) return -1;
if (t > e) return 1;
return 0;
}, t = false) {
}, e = false) {
super();
this.B = undefined;
this.M = e;
if (t) {
this.O = TreeNodeEnableIndex;
this.T = function(e, t, i) {
const s = this.N(e, t, i);
if (s) {
let e = s.p;
while (e !== this._) {
e.g += 1;
e = e.p;
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 t = this.m(s);
if (t) {
const {parentNode: e, grandParent: i, curNode: s} = t;
e.recount();
i.recount();
s.recount();
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.R = function(e) {
let t = this.v(e);
while (t !== this._) {
t.g -= 1;
t = t.p;
this.L = function(t) {
let e = this.S(t);
while (e !== this.R) {
e.M -= 1;
e = e.p;
}
};
} else {
this.O = TreeNode;
this.T = function(e, t, i) {
const s = this.N(e, t, i);
if (s) this.m(s);
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.R = this.v;
this.L = this.S;
}
this._ = new this.O;
this.R = new this.v;
}
C(e, t) {
let i;
while (e) {
const s = this.M(e.h, t);
if (s < 0) {
e = e.l;
} else if (s > 0) {
i = e;
e = e.u;
} else return e;
K(t, e) {
let s = this.R;
while (t) {
const i = this.A(t.h, e);
if (i < 0) {
t = t.l;
} else if (i > 0) {
s = t;
t = t.u;
} else return t;
}
return i === undefined ? this._ : i;
return s;
}
P(e, t) {
let i;
while (e) {
const s = this.M(e.h, t);
if (s <= 0) {
e = e.l;
U(t, e) {
let s = this.R;
while (t) {
const i = this.A(t.h, e);
if (i <= 0) {
t = t.l;
} else {
i = e;
e = e.u;
s = t;
t = t.u;
}
}
return i === undefined ? this._ : i;
return s;
}
k(e, t) {
let i;
while (e) {
const s = this.M(e.h, t);
if (s < 0) {
i = e;
e = e.l;
} else if (s > 0) {
e = e.u;
} else return e;
j(t, e) {
let s = this.R;
while (t) {
const i = this.A(t.h, e);
if (i < 0) {
s = t;
t = t.l;
} else if (i > 0) {
t = t.u;
} else return t;
}
return i === undefined ? this._ : i;
return s;
}
L(e, t) {
let i;
while (e) {
const s = this.M(e.h, t);
if (s < 0) {
i = e;
e = e.l;
q(t, e) {
let s = this.R;
while (t) {
const i = this.A(t.h, e);
if (i < 0) {
s = t;
t = t.l;
} else {
e = e.u;
t = t.u;
}
}
return i === undefined ? this._ : i;
return s;
}
S(e) {
F(t) {
while (true) {
const t = e.p;
if (t === this._) return;
if (e.i === 1) {
e.i = 0;
const e = t.p;
if (e === this.R) return;
if (t.i === 1) {
t.i = 0;
return;
}
if (e === t.u) {
const i = t.l;
if (i.i === 1) {
i.i = 0;
t.i = 1;
if (t === this.B) {
this.B = t.rotateLeft();
} else t.rotateLeft();
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();
} else {
if (i.l && i.l.i === 1) {
i.i = t.i;
t.i = 0;
i.l.i = 0;
if (t === this.B) {
this.B = t.rotateLeft();
} else t.rotateLeft();
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();
return;
} else if (i.u && i.u.i === 1) {
i.i = 1;
i.u.i = 0;
i.rotateRight();
} else if (s.u && s.u.i === 1) {
s.i = 1;
s.u.i = 0;
s.B();
} else {
i.i = 1;
e = t;
s.i = 1;
t = e;
}
}
} else {
const i = t.u;
if (i.i === 1) {
i.i = 0;
t.i = 1;
if (t === this.B) {
this.B = t.rotateRight();
} else t.rotateRight();
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();
} else {
if (i.u && i.u.i === 1) {
i.i = t.i;
t.i = 0;
i.u.i = 0;
if (t === this.B) {
this.B = t.rotateRight();
} else t.rotateRight();
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();
return;
} else if (i.l && i.l.i === 1) {
i.i = 1;
i.l.i = 0;
i.rotateLeft();
} else if (s.l && s.l.i === 1) {
s.i = 1;
s.l.i = 0;
s.g();
} else {
i.i = 1;
e = t;
s.i = 1;
t = e;
}

@@ -295,126 +308,126 @@ }

}
v(e) {
if (this.I === 1) {
S(t) {
if (this.T === 1) {
this.clear();
return this._;
return this.R;
}
let t = e;
while (t.u || t.l) {
if (t.l) {
t = t.l;
while (t.u) t = t.u;
let e = t;
while (e.u || e.l) {
if (e.l) {
e = e.l;
while (e.u) e = e.u;
} else {
t = t.u;
e = e.u;
}
[e.h, t.h] = [ t.h, e.h ];
[e.o, t.o] = [ t.o, e.o ];
e = t;
[t.h, e.h] = [ e.h, t.h ];
[t.o, e.o] = [ e.o, t.o ];
t = e;
}
if (this._.u === t) {
this._.u = t.p;
} else if (this._.l === t) {
this._.l = t.p;
if (this.R.u === e) {
this.R.u = e.p;
} else if (this.R.l === e) {
this.R.l = e.p;
}
this.S(t);
const i = t.p;
if (t === i.u) {
i.u = undefined;
} else i.l = undefined;
this.I -= 1;
this.B.i = 0;
return i;
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;
}
K(e, t) {
if (e === undefined) return false;
const i = this.K(e.u, t);
if (i) return true;
if (t(e)) return true;
return this.K(e.l, t);
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);
}
m(e) {
k(t) {
while (true) {
const t = e.p;
if (t.i === 0) return;
const i = t.p;
if (t === i.u) {
const s = i.l;
if (s && s.i === 1) {
s.i = t.i = 0;
if (i === this.B) return;
i.i = 1;
e = i;
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;
t = s;
continue;
} else if (e === t.l) {
e.i = 0;
if (e.u) e.u.p = t;
if (e.l) e.l.p = i;
t.l = e.u;
i.u = e.l;
e.u = t;
e.l = i;
if (i === this.B) {
this.B = e;
this._.p = e;
} 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 {
const t = i.p;
if (t.u === i) {
t.u = e;
} else t.l = e;
const e = s.p;
if (e.u === s) {
e.u = t;
} else e.l = t;
}
e.p = i.p;
t.p = e;
i.p = e;
i.i = 1;
t.p = s.p;
e.p = t;
s.p = t;
s.i = 1;
return {
parentNode: t,
grandParent: i,
curNode: e
parentNode: e,
grandParent: s,
curNode: t
};
} else {
t.i = 0;
if (i === this.B) {
this.B = i.rotateRight();
} else i.rotateRight();
i.i = 1;
e.i = 0;
if (s === this.m) {
this.m = s.B();
} else s.B();
s.i = 1;
}
} else {
const s = i.u;
if (s && s.i === 1) {
s.i = t.i = 0;
if (i === this.B) return;
i.i = 1;
e = i;
const i = s.u;
if (i && i.i === 1) {
i.i = e.i = 0;
if (s === this.m) return;
s.i = 1;
t = s;
continue;
} else if (e === t.u) {
e.i = 0;
if (e.u) e.u.p = i;
if (e.l) e.l.p = t;
i.l = e.u;
t.u = e.l;
e.u = i;
e.l = t;
if (i === this.B) {
this.B = e;
this._.p = e;
} 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 {
const t = i.p;
if (t.u === i) {
t.u = e;
} else t.l = e;
const e = s.p;
if (e.u === s) {
e.u = t;
} else e.l = t;
}
e.p = i.p;
t.p = e;
i.p = e;
i.i = 1;
t.p = s.p;
e.p = t;
s.p = t;
s.i = 1;
return {
parentNode: t,
grandParent: i,
curNode: e
parentNode: e,
grandParent: s,
curNode: t
};
} else {
t.i = 0;
if (i === this.B) {
this.B = i.rotateLeft();
} else i.rotateLeft();
i.i = 1;
e.i = 0;
if (s === this.m) {
this.m = s.g();
} else s.g();
s.i = 1;
}

@@ -425,57 +438,57 @@ }

}
N(e, t, i) {
if (this.B === undefined) {
this.I += 1;
this.B = new this.O(e, t);
this.B.i = 0;
this.B.p = this._;
this._.p = this.B;
this._.u = this.B;
this._.l = this.B;
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;
}
let s;
const r = this._.u;
const n = this.M(r.h, e);
let i;
const r = this.R.u;
const n = this.A(r.h, t);
if (n === 0) {
r.o = t;
r.o = e;
return;
} else if (n > 0) {
r.u = new this.O(e, t);
r.u = new this.v(t, e);
r.u.p = r;
s = r.u;
this._.u = s;
i = r.u;
this.R.u = i;
} else {
const r = this._.l;
const n = this.M(r.h, e);
const r = this.R.l;
const n = this.A(r.h, t);
if (n === 0) {
r.o = t;
r.o = e;
return;
} else if (n < 0) {
r.l = new this.O(e, t);
r.l = new this.v(t, e);
r.l.p = r;
s = r.l;
this._.l = s;
i = r.l;
this.R.l = i;
} else {
if (i !== undefined) {
const r = i.U;
if (r !== this._) {
const i = this.M(r.h, e);
if (i === 0) {
r.o = t;
if (s !== undefined) {
const r = s.O;
if (r !== this.R) {
const s = this.A(r.h, t);
if (s === 0) {
r.o = e;
return;
} else if (i > 0) {
const i = r.pre();
const n = this.M(i.h, e);
} else if (s > 0) {
const s = r.I();
const n = this.A(s.h, t);
if (n === 0) {
i.o = t;
s.o = e;
return;
} else if (n < 0) {
s = new this.O(e, t);
if (i.l === undefined) {
i.l = s;
s.p = i;
i = new this.v(t, e);
if (s.l === undefined) {
s.l = i;
i.p = s;
} else {
r.u = s;
s.p = r;
r.u = i;
i.p = r;
}

@@ -486,24 +499,24 @@ }

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

@@ -515,23 +528,34 @@ }

}
this.I += 1;
return s;
this.T += 1;
return i;
}
D(t, e) {
while (t) {
const s = this.A(t.h, e);
if (s < 0) {
t = t.l;
} else if (s > 0) {
t = t.u;
} else return t;
}
return t || this.R;
}
clear() {
this.I = 0;
this.B = undefined;
this._.p = undefined;
this._.u = this._.l = undefined;
this.T = 0;
this.m = undefined;
this.R.p = undefined;
this.R.u = this.R.l = undefined;
}
updateKeyByIterator(e, t) {
const i = e.U;
if (i === this._) {
throw new TypeError("Invalid iterator!");
updateKeyByIterator(t, e) {
const s = t.O;
if (s === this.R) {
throwIteratorAccessError();
}
if (this.I === 1) {
i.h = t;
if (this.T === 1) {
s.h = e;
return true;
}
if (i === this._.u) {
if (this.M(i.next().h, t) > 0) {
i.h = t;
if (s === this.R.u) {
if (this.A(s._().h, e) > 0) {
s.h = e;
return true;

@@ -541,5 +565,5 @@ }

}
if (i === this._.l) {
if (this.M(i.pre().h, t) < 0) {
i.h = t;
if (s === this.R.l) {
if (this.A(s.I().h, e) < 0) {
s.h = e;
return true;

@@ -549,59 +573,73 @@ }

}
const s = i.pre().h;
if (this.M(s, t) >= 0) return false;
const r = i.next().h;
if (this.M(r, t) <= 0) return false;
i.h = t;
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;
return true;
}
eraseElementByPos(e) {
if (e < 0 || e > this.I - 1) {
eraseElementByPos(t) {
if (t < 0 || t > this.T - 1) {
throw new RangeError;
}
let t = 0;
const i = this;
this.K(this.B, (function(s) {
if (e === t) {
i.R(s);
let e = 0;
const s = this;
this.H(this.m, (function(i) {
if (t === e) {
s.L(i);
return true;
}
t += 1;
e += 1;
return false;
}));
return this.T;
}
j(e, t) {
while (e) {
const i = this.M(e.h, t);
if (i < 0) {
e = e.l;
} else if (i > 0) {
e = e.u;
} else return e;
eraseElementByKey(t) {
if (this.T === 0) return false;
const e = this.D(this.m, t);
if (e === this.R) return false;
this.L(e);
return true;
}
eraseElementByIterator(t) {
const e = t.O;
if (e === this.R) {
throwIteratorAccessError();
}
return e;
const s = e.l === undefined;
const i = t.iteratorType === 0;
if (i) {
if (s) t.next();
} else {
if (!s || e.u === undefined) t.next();
}
this.L(e);
return t;
}
eraseElementByKey(e) {
if (!this.I) return;
const t = this.j(this.B, e);
if (t === undefined) return;
this.R(t);
forEach(t) {
let e = 0;
for (const s of this) t(s, e++, this);
}
eraseElementByIterator(e) {
const t = e.U;
if (t === this._) {
throw new RangeError("Invalid iterator");
getElementByPos(t) {
if (t < 0 || t > this.T - 1) {
throw new RangeError;
}
if (t.l === undefined) {
e = e.next();
let e;
let s = 0;
for (const i of this) {
if (s === t) {
e = i;
break;
}
s += 1;
}
this.R(t);
return e;
}
getHeight() {
if (!this.I) return 0;
const traversal = function(e) {
if (!e) return 0;
return Math.max(traversal(e.u), traversal(e.l)) + 1;
if (this.T === 0) return 0;
const traversal = function(t) {
if (!t) return 0;
return Math.max(traversal(t.u), traversal(t.l)) + 1;
};
return traversal(this.B);
return traversal(this.m);
}

@@ -611,19 +649,19 @@ }

class TreeIterator extends ContainerIterator {
constructor(e, t, i) {
super(i);
this.U = e;
this._ = t;
constructor(t, e, s) {
super(s);
this.O = t;
this.R = e;
if (this.iteratorType === 0) {
this.pre = function() {
if (this.U === this._.u) {
throw new RangeError("Tree iterator access denied!");
if (this.O === this.R.u) {
throwIteratorAccessError();
}
this.U = this.U.pre();
this.O = this.O.I();
return this;
};
this.next = function() {
if (this.U === this._) {
throw new RangeError("Tree iterator access denied!");
if (this.O === this.R) {
throwIteratorAccessError();
}
this.U = this.U.next();
this.O = this.O._();
return this;

@@ -633,13 +671,13 @@ };

this.pre = function() {
if (this.U === this._.l) {
throw new RangeError("Tree iterator access denied!");
if (this.O === this.R.l) {
throwIteratorAccessError();
}
this.U = this.U.next();
this.O = this.O._();
return this;
};
this.next = function() {
if (this.U === this._) {
throw new RangeError("Tree iterator access denied!");
if (this.O === this.R) {
throwIteratorAccessError();
}
this.U = this.U.pre();
this.O = this.O.I();
return this;

@@ -650,29 +688,26 @@ };

get index() {
let e = this.U;
const t = this._.p;
if (e === this._) {
if (t) {
return t.g - 1;
let t = this.O;
const e = this.R.p;
if (t === this.R) {
if (e) {
return e.M - 1;
}
return 0;
}
let i = 0;
if (e.u) {
i += e.u.g;
let s = 0;
if (t.u) {
s += t.u.M;
}
while (e !== t) {
const t = e.p;
if (e === t.l) {
i += 1;
if (t.u) {
i += t.u.g;
while (t !== e) {
const e = t.p;
if (t === e.l) {
s += 1;
if (e.u) {
s += e.u.M;
}
}
e = t;
t = e;
}
return i;
return s;
}
equals(e) {
return this.U === e.U;
}
}

@@ -682,15 +717,15 @@

get pointer() {
if (this.U === this._) {
throw new RangeError("OrderedMap iterator access denied");
if (this.O === this.R) {
throwIteratorAccessError();
}
const e = this;
const t = this;
return new Proxy([], {
get(t, i) {
if (i === "0") return e.U.h; else if (i === "1") return e.U.o;
get(e, s) {
if (s === "0") return t.O.h; else if (s === "1") return t.O.o;
},
set(t, i, s) {
if (i !== "1") {
set(e, s, i) {
if (s !== "1") {
throw new TypeError("props must be 1");
}
e.U.o = s;
t.O.o = i;
return true;

@@ -701,3 +736,3 @@ }

copy() {
return new OrderedMapIterator(this.U, this._, this.iteratorType);
return new OrderedMapIterator(this.O, this.R, this.iteratorType);
}

@@ -707,94 +742,73 @@ }

class OrderedMap extends TreeContainer {
constructor(e = [], t, i) {
super(t, i);
const s = this;
e.forEach((function(e) {
s.setElement(e[0], e[1]);
constructor(t = [], e, s) {
super(e, s);
const i = this;
t.forEach((function(t) {
i.setElement(t[0], t[1]);
}));
}
* q(e) {
if (e === undefined) return;
yield* this.q(e.u);
yield [ e.h, e.o ];
yield* this.q(e.l);
* 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._.u || this._, this._);
return new OrderedMapIterator(this.R.u || this.R, this.R);
}
end() {
return new OrderedMapIterator(this._, this._);
return new OrderedMapIterator(this.R, this.R);
}
rBegin() {
return new OrderedMapIterator(this._.l || this._, this._, 1);
return new OrderedMapIterator(this.R.l || this.R, this.R, 1);
}
rEnd() {
return new OrderedMapIterator(this._, this._, 1);
return new OrderedMapIterator(this.R, this.R, 1);
}
front() {
if (!this.I) return undefined;
const e = this._.u;
return [ e.h, e.o ];
if (this.T === 0) return;
const t = this.R.u;
return [ t.h, t.o ];
}
back() {
if (!this.I) return undefined;
const e = this._.l;
return [ e.h, e.o ];
if (this.T === 0) return;
const t = this.R.l;
return [ t.h, t.o ];
}
forEach(e) {
let t = 0;
for (const i of this) e(i, t++, this);
lowerBound(t) {
const e = this.K(this.m, t);
return new OrderedMapIterator(e, this.R);
}
lowerBound(e) {
const t = this.C(this.B, e);
return new OrderedMapIterator(t, this._);
upperBound(t) {
const e = this.U(this.m, t);
return new OrderedMapIterator(e, this.R);
}
upperBound(e) {
const t = this.P(this.B, e);
return new OrderedMapIterator(t, this._);
reverseLowerBound(t) {
const e = this.j(this.m, t);
return new OrderedMapIterator(e, this.R);
}
reverseLowerBound(e) {
const t = this.k(this.B, e);
return new OrderedMapIterator(t, this._);
reverseUpperBound(t) {
const e = this.q(this.m, t);
return new OrderedMapIterator(e, this.R);
}
reverseUpperBound(e) {
const t = this.L(this.B, e);
return new OrderedMapIterator(t, this._);
setElement(t, e, s) {
return this.C(t, e, s);
}
setElement(e, t, i) {
this.T(e, t, i);
find(t) {
const e = this.D(this.m, t);
return new OrderedMapIterator(e, this.R);
}
find(e) {
const t = this.j(this.B, e);
if (t !== undefined) {
return new OrderedMapIterator(t, this._);
}
return this.end();
getElementByKey(t) {
const e = this.D(this.m, t);
return e.o;
}
getElementByKey(e) {
const t = this.j(this.B, e);
return t ? t.o : undefined;
}
getElementByPos(e) {
if (e < 0 || e > this.I - 1) {
throw new RangeError;
}
let t;
let i = 0;
for (const s of this) {
if (i === e) {
t = s;
break;
}
i += 1;
}
return t;
}
union(e) {
const t = this;
e.forEach((function(e) {
t.setElement(e[0], e[1]);
union(t) {
const e = this;
t.forEach((function(t) {
e.setElement(t[0], t[1]);
}));
return this.T;
}
[Symbol.iterator]() {
return this.q(this.B);
return this.G(this.m);
}

@@ -801,0 +815,0 @@ }

221

dist/esm/index.d.ts

@@ -0,1 +1,4 @@

/**
* @description The iterator type including `NORMAL` and `REVERSE`.
*/
declare const enum IteratorType {

@@ -8,10 +11,18 @@ NORMAL = 0,

* @description Iterator's type.
* @example console.log(container.end().iteratorType === IteratorType.NORMAL); // true
* @example
* console.log(container.end().iteratorType === IteratorType.NORMAL); // true
*/
readonly iteratorType: IteratorType;
protected constructor(iteratorType?: IteratorType);
/**
* @param iter - The other iterator you want to compare.
* @returns Whether this equals to obj.
* @example
* container.find(1).equals(container.end());
*/
equals(iter: ContainerIterator<T>): boolean;
/**
* @description Pointers to element.
* @return The value of the pointer's element.
* @example const val = container.begin().pointer;
* @returns The value of the pointer's element.
* @example
* const val = container.begin().pointer;
*/

@@ -21,4 +32,5 @@ abstract get pointer(): T;

* @description Set pointer's value (some containers are unavailable).
* @param newValue The new value you want to set.
* @example (<LinkList<number>>container).begin().pointer = 1;
* @param newValue - The new value you want to set.
* @example
* (<LinkList<number>>container).begin().pointer = 1;
*/

@@ -28,2 +40,3 @@ abstract set pointer(newValue: T);

* @description Move `this` iterator to pre.
* @returns The iterator's self.
* @example

@@ -39,2 +52,3 @@ * const iter = container.find(1); // container = [0, 1]

* @description Move `this` iterator to next.
* @returns The iterator's self.
* @example

@@ -49,10 +63,4 @@ * const iter = container.find(1); // container = [1, 2]

/**
* @param obj The other iterator you want to compare.
* @return Boolean about if this equals to obj.
* @example container.find(1).equals(container.end());
*/
abstract equals(obj: ContainerIterator<T>): boolean;
/**
* @description Get a copy of itself.
* @return The copy of self.
* @returns The copy of self.
* @example

@@ -69,5 +77,12 @@ * const iter = container.find(1); // container = [1, 2]

/**
* @return The size of the container.
* @returns The size of the container.
* @example
* const container = new Vector([1, 2]);
* console.log(container.length); // 2
*/
get length(): number;
/**
* @returns The size of the container.
* @example
* const container = new Vector([1, 2]);
* console.log(container.size()); // 2

@@ -77,3 +92,3 @@ */

/**
* @return Boolean about if the container is empty.
* @returns Whether the container is empty.
* @example

@@ -94,3 +109,3 @@ * container.clear();

/**
* @return Iterator pointing to the beginning element.
* @returns Iterator pointing to the beginning element.
* @example

@@ -105,3 +120,3 @@ * const begin = container.begin();

/**
* @return Iterator pointing to the super end like c++.
* @returns Iterator pointing to the super end like c++.
* @example

@@ -116,3 +131,3 @@ * const begin = container.begin();

/**
* @return Iterator pointing to the end element.
* @returns Iterator pointing to the end element.
* @example

@@ -127,3 +142,3 @@ * const rBegin = container.rBegin();

/**
* @return Iterator pointing to the super begin like c++.
* @returns Iterator pointing to the super begin like c++.
* @example

@@ -138,22 +153,24 @@ * const rBegin = container.rBegin();

/**
* @return The first element of the container.
* @returns The first element of the container.
*/
abstract front(): T | undefined;
/**
* @return The last element of the container.
* @returns The last element of the container.
*/
abstract back(): T | undefined;
/**
* @param element - The element you want to find.
* @returns An iterator pointing to the element if found, or super end if not found.
* @example
* container.find(1).equals(container.end());
*/
abstract find(element: T): ContainerIterator<T>;
/**
* @description Iterate over all elements in the container.
* @param callback Callback function like Array.forEach.
* @example container.forEach((element, index) => console.log(element, index));
* @param callback - Callback function like Array.forEach.
* @example
* container.forEach((element, index) => console.log(element, index));
*/
abstract forEach(callback: (element: T, index: number, container: Container<T>) => void): void;
/**
* @param element The element you want to find.
* @return An iterator pointing to the element if found, or super end if not found.
* @example container.find(1).equals(container.end());
*/
abstract find(element: T): ContainerIterator<T>;
/**
* @description Gets the value of the element at the specified position.

@@ -166,9 +183,12 @@ * @example

* @description Removes the element at the specified position.
* @param pos The element's position you want to remove.
* @param pos - The element's position you want to remove.
* @returns The container length after erasing.
* @example
* container.eraseElementByPos(-1); // throw a RangeError
*/
abstract eraseElementByPos(pos: number): void;
abstract eraseElementByPos(pos: number): number;
/**
* @description Removes element by iterator and move `iter` to next.
* @param iter The iterator you want to erase.
* @param iter - The iterator you want to erase.
* @returns The next iterator.
* @example

@@ -186,4 +206,7 @@ * container.eraseElementByIterator(container.begin());

*/
abstract [Symbol.iterator](): Generator<T, void, undefined>;
abstract [Symbol.iterator](): Generator<T, void>;
}
/**
* @description The initial data type passed in when initializing the container.
*/
type initContainer<T> = ({

@@ -202,10 +225,7 @@ size: number;

]> {
pre: () => this;
next: () => this;
/**
* @description Get the sequential index of the iterator in the tree container.<br/>
* <strong>
* Note:
* </strong>
* <strong>Note:</strong>
* This function only takes effect when the specified tree container `enableIndex = true`.
* @returns The index subscript of the node in the tree.
* @example

@@ -216,3 +236,6 @@ * const st = new OrderedSet([1, 2, 3], true);

get index(): number;
equals(obj: TreeIterator<K, V>): boolean;
// @ts-ignore
pre(): this;
// @ts-ignore
next(): this;
}

@@ -223,56 +246,61 @@ declare abstract class TreeContainer<K, V> extends Container<K | [

]> {
clear(): void;
/**
* @param cmp The compare function.
* @param enableIndex Whether to enable iterator indexing function.
* @description Update node's key by iterator.
* @param iter - The iterator you want to change.
* @param key - The key you want to update.
* @returns Whether the modification is successful.
* @example
* const st = new orderedSet([1, 2, 5]);
* const iter = st.find(2);
* st.updateKeyByIterator(iter, 3); // then st will become [1, 3, 5]
*/
protected constructor(cmp?: (x: K, y: K) => number, enableIndex?: boolean);
updateKeyByIterator(iter: TreeIterator<K, V>, key: K): boolean;
eraseElementByPos(pos: number): number;
/**
* @param key The given key you want to compare.
* @return An iterator to the first element not less than the given key.
* @description Remove the element of the specified key.
* @param key - The key you want to remove.
* @returns Whether erase successfully.
*/
abstract lowerBound(key: K): TreeIterator<K, V>;
eraseElementByKey(key: K): boolean;
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
];
/**
* @param key The given key you want to compare.
* @return An iterator to the first element greater than the given key.
* @description Get the height of the tree.
* @returns Number about the height of the RB-tree.
*/
abstract upperBound(key: K): TreeIterator<K, V>;
getHeight(): number;
/**
* @param key The given key you want to compare.
* @return An iterator to the first element not greater than the given key.
* @param key - The given key you want to compare.
* @returns An iterator to the first element less than the given key.
*/
abstract reverseLowerBound(key: K): TreeIterator<K, V>;
/**
* @param key The given key you want to compare.
* @return An iterator to the first element less than the given key.
*/
abstract reverseUpperBound(key: K): TreeIterator<K, V>;
/**
* @description Union the other tree to self.
* @param other The other tree container you want to merge.
* @param other - The other tree container you want to merge.
* @returns The size of the tree after union.
*/
abstract union(other: TreeContainer<K, V>): void;
clear(): void;
abstract union(other: TreeContainer<K, V>): number;
/**
* @description Update node's key by iterator.
* @param iter The iterator you want to change.
* @param key The key you want to update.
* @return Boolean about if the modification is successful.
* @example
* const st = new orderedSet([1, 2, 5]);
* const iter = st.find(2);
* st.updateKeyByIterator(iter, 3); // then st will become [1, 3, 5]
* @param key - The given key you want to compare.
* @returns An iterator to the first element not greater than the given key.
*/
updateKeyByIterator(iter: TreeIterator<K, V>, key: K): boolean;
eraseElementByPos(pos: number): void;
abstract reverseLowerBound(key: K): TreeIterator<K, V>;
/**
* @description Remove the element of the specified key.
* @param key The key you want to remove.
* @param key - The given key you want to compare.
* @returns An iterator to the first element not less than the given key.
*/
eraseElementByKey(key: K): void;
eraseElementByIterator(iter: TreeIterator<K, V>): TreeIterator<K, V>;
abstract lowerBound(key: K): TreeIterator<K, V>;
/**
* @description Get the height of the tree.
* @return Number about the height of the RB-tree.
* @param key - The given key you want to compare.
* @returns An iterator to the first element greater than the given key.
*/
getHeight(): number;
abstract upperBound(key: K): TreeIterator<K, V>;
}

@@ -285,8 +313,10 @@ declare class OrderedMapIterator<K, V> extends TreeIterator<K, V> {

copy(): OrderedMapIterator<K, V>;
// @ts-ignore
equals(iter: OrderedMapIterator<K, V>): boolean;
}
declare class OrderedMap<K, V> extends TreeContainer<K, V> {
/**
* @param container The initialization container.
* @param cmp The compare function.
* @param enableIndex Whether to enable iterator indexing function.
* @param container - The initialization container.
* @param cmp - The compare function.
* @param enableIndex - Whether to enable iterator indexing function.
* @example

@@ -314,6 +344,2 @@ * new OrderedMap();

] | undefined;
forEach(callback: (element: [
K,
V
], index: number, map: OrderedMap<K, V>) => void): void;
lowerBound(key: K): OrderedMapIterator<K, V>;

@@ -325,5 +351,6 @@ upperBound(key: K): OrderedMapIterator<K, V>;

* @description Insert a key-value pair or set value by the given key.
* @param key The key want to insert.
* @param value The value want to set.
* @param hint You can give an iterator hint to improve insertion efficiency.
* @param key - The key want to insert.
* @param value - The value want to set.
* @param hint - You can give an iterator hint to improve insertion efficiency.
* @return The size of container after setting.
* @example

@@ -335,9 +362,24 @@ * const mp = new OrderedMap([[2, 0], [4, 0], [5, 0]]);

*/
setElement(key: K, value: V, hint?: OrderedMapIterator<K, V>): void;
setElement(key: K, value: V, hint?: OrderedMapIterator<K, V>): number;
find(key: K): OrderedMapIterator<K, V>;
/**
* @description Get the value of the element of the specified key.
* @example const val = container.getElementByKey(1);
* @param key - The specified key you want to get.
* @example
* const val = container.getElementByKey(1);
*/
getElementByKey(key: K): V | undefined;
union(other: OrderedMap<K, V>): number;
[Symbol.iterator](): Generator<[
K,
V
], void, unknown>;
// @ts-ignore
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): [

@@ -347,9 +389,4 @@ K,

];
union(other: OrderedMap<K, V>): void;
[Symbol.iterator](): Generator<[
K,
V
], void, undefined>;
}
export { OrderedMap };
export type { OrderedMapIterator, IteratorType, Container, ContainerIterator, TreeContainer };

630

dist/esm/index.js

@@ -43,12 +43,12 @@ var extendStatics = function(e, r) {

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

@@ -59,3 +59,3 @@

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

@@ -66,8 +66,8 @@ };

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

@@ -77,13 +77,13 @@ continue;

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

@@ -93,3 +93,3 @@ }

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

@@ -101,5 +101,5 @@ }

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

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

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

@@ -164,3 +164,3 @@ };

}
TreeNode.prototype.pre = function() {
TreeNode.prototype.v = function() {
var e = this;

@@ -184,3 +184,3 @@ if (e.t === 1 && e.l.l === e) {

};
TreeNode.prototype.next = function() {
TreeNode.prototype.p = function() {
var e = this;

@@ -204,3 +204,3 @@ if (e.o) {

};
TreeNode.prototype.rotateLeft = function() {
TreeNode.prototype.T = function() {
var e = this.l;

@@ -217,3 +217,3 @@ var r = this.o;

};
TreeNode.prototype.rotateRight = function() {
TreeNode.prototype.I = function() {
var e = this.l;

@@ -237,24 +237,25 @@ var r = this.h;

var r = e !== null && e.apply(this, arguments) || this;
r.h = undefined;
r.o = undefined;
r.l = undefined;
r.v = 1;
r.O = 1;
return r;
}
TreeNodeEnableIndex.prototype.rotateLeft = function() {
var r = e.prototype.rotateLeft.call(this);
this.recount();
r.recount();
TreeNodeEnableIndex.prototype.T = function() {
var r = e.prototype.T.call(this);
this._();
r._();
return r;
};
TreeNodeEnableIndex.prototype.rotateRight = function() {
var r = e.prototype.rotateRight.call(this);
this.recount();
r.recount();
TreeNodeEnableIndex.prototype.I = function() {
var r = e.prototype.I.call(this);
this._();
r._();
return r;
};
TreeNodeEnableIndex.prototype.recount = function() {
this.v = 1;
if (this.h) this.v += this.h.v;
if (this.o) this.v += this.o.v;
TreeNodeEnableIndex.prototype._ = function() {
this.O = 1;
if (this.h) {
this.O += this.h.O;
}
if (this.o) {
this.O += this.o.O;
}
};

@@ -271,2 +272,5 @@ return TreeNodeEnableIndex;

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

@@ -277,9 +281,16 @@ }();

function Base() {
this.p = 0;
this.C = 0;
}
Object.defineProperty(Base.prototype, "length", {
get: function() {
return this.C;
},
enumerable: false,
configurable: true
});
Base.prototype.size = function() {
return this.p;
return this.C;
};
Base.prototype.empty = function() {
return this.p === 0;
return this.C === 0;
};

@@ -297,2 +308,6 @@ return Base;

function throwIteratorAccessError() {
throw new RangeError("Iterator access denied!");
}
var TreeContainer = function(e) {

@@ -312,27 +327,28 @@ __extends(TreeContainer, e);

var i = e.call(this) || this;
i.T = undefined;
i.O = r;
i.N = undefined;
i.g = r;
if (t) {
i._ = TreeNodeEnableIndex;
i.M = function(e, r, t) {
var i = this.I(e, r, 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.C) {
n.v += 1;
while (n !== this.j) {
n.O += 1;
n = n.l;
}
var s = this.N(i);
var s = this.k(i);
if (s) {
var a = s, f = a.parentNode, u = a.grandParent, h = a.curNode;
f.recount();
u.recount();
h.recount();
var a = s, u = a.parentNode, f = a.grandParent, h = a.curNode;
u._();
f._();
h._();
}
}
return this.C;
};
i.g = function(e) {
var r = this.S(e);
while (r !== this.C) {
r.v -= 1;
i.B = function(e) {
var r = this.P(e);
while (r !== this.j) {
r.O -= 1;
r = r.l;

@@ -342,16 +358,17 @@ }

} else {
i._ = TreeNode;
i.M = function(e, r, t) {
var i = this.I(e, r, t);
if (i) this.N(i);
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.g = i.S;
i.B = i.P;
}
i.C = new i._;
i.j = new i.m;
return i;
}
TreeContainer.prototype.m = function(e, r) {
var t;
TreeContainer.prototype.R = function(e, r) {
var t = this.j;
while (e) {
var i = this.O(e.i, r);
var i = this.g(e.i, r);
if (i < 0) {

@@ -364,8 +381,8 @@ e = e.o;

}
return t === undefined ? this.C : t;
return t;
};
TreeContainer.prototype.R = function(e, r) {
var t;
TreeContainer.prototype.G = function(e, r) {
var t = this.j;
while (e) {
var i = this.O(e.i, r);
var i = this.g(e.i, r);
if (i <= 0) {

@@ -378,8 +395,8 @@ e = e.o;

}
return t === undefined ? this.C : t;
return t;
};
TreeContainer.prototype.k = function(e, r) {
var t;
TreeContainer.prototype.q = function(e, r) {
var t = this.j;
while (e) {
var i = this.O(e.i, r);
var i = this.g(e.i, r);
if (i < 0) {

@@ -392,8 +409,8 @@ t = e;

}
return t === undefined ? this.C : t;
return t;
};
TreeContainer.prototype.j = function(e, r) {
var t;
TreeContainer.prototype.D = function(e, r) {
var t = this.j;
while (e) {
var i = this.O(e.i, r);
var i = this.g(e.i, r);
if (i < 0) {

@@ -406,8 +423,8 @@ t = e;

}
return t === undefined ? this.C : t;
return t;
};
TreeContainer.prototype.B = function(e) {
TreeContainer.prototype.F = function(e) {
while (true) {
var r = e.l;
if (r === this.C) return;
if (r === this.j) return;
if (e.t === 1) {

@@ -422,5 +439,5 @@ e.t = 0;

r.t = 1;
if (r === this.T) {
this.T = r.rotateLeft();
} else r.rotateLeft();
if (r === this.N) {
this.N = r.T();
} else r.T();
} else {

@@ -431,5 +448,5 @@ if (t.o && t.o.t === 1) {

t.o.t = 0;
if (r === this.T) {
this.T = r.rotateLeft();
} else r.rotateLeft();
if (r === this.N) {
this.N = r.T();
} else r.T();
return;

@@ -439,3 +456,3 @@ } else if (t.h && t.h.t === 1) {

t.h.t = 0;
t.rotateRight();
t.I();
} else {

@@ -451,5 +468,5 @@ t.t = 1;

r.t = 1;
if (r === this.T) {
this.T = r.rotateRight();
} else r.rotateRight();
if (r === this.N) {
this.N = r.I();
} else r.I();
} else {

@@ -460,5 +477,5 @@ if (t.h && t.h.t === 1) {

t.h.t = 0;
if (r === this.T) {
this.T = r.rotateRight();
} else r.rotateRight();
if (r === this.N) {
this.N = r.I();
} else r.I();
return;

@@ -468,3 +485,3 @@ } else if (t.o && t.o.t === 1) {

t.o.t = 0;
t.rotateLeft();
t.T();
} else {

@@ -478,7 +495,7 @@ t.t = 1;

};
TreeContainer.prototype.S = function(e) {
TreeContainer.prototype.P = function(e) {
var r, t;
if (this.p === 1) {
if (this.C === 1) {
this.clear();
return this.C;
return this.j;
}

@@ -497,8 +514,8 @@ var i = e;

}
if (this.C.h === i) {
this.C.h = i.l;
} else if (this.C.o === i) {
this.C.o = i.l;
if (this.j.h === i) {
this.j.h = i.l;
} else if (this.j.o === i) {
this.j.o = i.l;
}
this.B(i);
this.F(i);
var n = i.l;

@@ -508,14 +525,14 @@ if (i === n.h) {

} else n.o = undefined;
this.p -= 1;
this.T.t = 0;
this.C -= 1;
this.N.t = 0;
return n;
};
TreeContainer.prototype.P = function(e, r) {
TreeContainer.prototype.H = function(e, r) {
if (e === undefined) return false;
var t = this.P(e.h, r);
var t = this.H(e.h, r);
if (t) return true;
if (r(e)) return true;
return this.P(e.o, r);
return this.H(e.o, r);
};
TreeContainer.prototype.N = function(e) {
TreeContainer.prototype.k = function(e) {
while (true) {

@@ -529,3 +546,3 @@ var r = e.l;

i.t = r.t = 0;
if (t === this.T) return;
if (t === this.N) return;
t.t = 1;

@@ -542,5 +559,5 @@ e = t;

e.o = t;
if (t === this.T) {
this.T = e;
this.C.l = e;
if (t === this.N) {
this.N = e;
this.j.l = e;
} else {

@@ -563,5 +580,5 @@ var n = t.l;

r.t = 0;
if (t === this.T) {
this.T = t.rotateRight();
} else t.rotateRight();
if (t === this.N) {
this.N = t.I();
} else t.I();
t.t = 1;

@@ -573,3 +590,3 @@ }

i.t = r.t = 0;
if (t === this.T) return;
if (t === this.N) return;
t.t = 1;

@@ -586,5 +603,5 @@ e = t;

e.o = r;
if (t === this.T) {
this.T = e;
this.C.l = e;
if (t === this.N) {
this.N = e;
this.j.l = e;
} else {

@@ -607,5 +624,5 @@ var n = t.l;

r.t = 0;
if (t === this.T) {
this.T = t.rotateLeft();
} else t.rotateLeft();
if (t === this.N) {
this.N = t.T();
} else t.T();
t.t = 1;

@@ -617,16 +634,16 @@ }

};
TreeContainer.prototype.I = function(e, r, t) {
if (this.T === undefined) {
this.p += 1;
this.T = new this._(e, r);
this.T.t = 0;
this.T.l = this.C;
this.C.l = this.T;
this.C.h = this.T;
this.C.o = this.T;
TreeContainer.prototype.A = 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;
}
var i;
var n = this.C.h;
var s = this.O(n.i, e);
var n = this.j.h;
var s = this.g(n.i, e);
if (s === 0) {

@@ -636,28 +653,28 @@ n.u = r;

} else if (s > 0) {
n.h = new this._(e, r);
n.h = new this.m(e, r);
n.h.l = n;
i = n.h;
this.C.h = i;
this.j.h = i;
} else {
var a = this.C.o;
var f = this.O(a.i, e);
if (f === 0) {
var a = this.j.o;
var u = this.g(a.i, e);
if (u === 0) {
a.u = r;
return;
} else if (f < 0) {
a.o = new this._(e, r);
} else if (u < 0) {
a.o = new this.m(e, r);
a.o.l = a;
i = a.o;
this.C.o = i;
this.j.o = i;
} else {
if (t !== undefined) {
var u = t.A;
if (u !== this.C) {
var h = this.O(u.i, e);
var f = t.M;
if (f !== this.j) {
var h = this.g(f.i, e);
if (h === 0) {
u.u = r;
f.u = r;
return;
} else if (h > 0) {
var o = u.pre();
var d = this.O(o.i, e);
var o = f.v();
var d = this.g(o.i, e);
if (d === 0) {

@@ -667,3 +684,3 @@ o.u = r;

} else if (d < 0) {
i = new this._(e, r);
i = new this.m(e, r);
if (o.o === undefined) {

@@ -673,4 +690,4 @@ o.o = i;

} else {
u.h = i;
i.l = u;
f.h = i;
i.l = f;
}

@@ -682,8 +699,8 @@ }

if (i === undefined) {
i = this.T;
i = this.N;
while (true) {
var c = this.O(i.i, e);
var c = this.g(i.i, e);
if (c > 0) {
if (i.h === undefined) {
i.h = new this._(e, r);
i.h = new this.m(e, r);
i.h.l = i;

@@ -696,3 +713,3 @@ i = i.h;

if (i.o === undefined) {
i.o = new this._(e, r);
i.o = new this.m(e, r);
i.o.l = i;

@@ -711,22 +728,33 @@ i = i.o;

}
this.p += 1;
this.C += 1;
return i;
};
TreeContainer.prototype.J = function(e, r) {
while (e) {
var t = this.g(e.i, r);
if (t < 0) {
e = e.o;
} else if (t > 0) {
e = e.h;
} else return e;
}
return e || this.j;
};
TreeContainer.prototype.clear = function() {
this.p = 0;
this.T = undefined;
this.C.l = undefined;
this.C.h = this.C.o = undefined;
this.C = 0;
this.N = undefined;
this.j.l = undefined;
this.j.h = this.j.o = undefined;
};
TreeContainer.prototype.updateKeyByIterator = function(e, r) {
var t = e.A;
if (t === this.C) {
throw new TypeError("Invalid iterator!");
var t = e.M;
if (t === this.j) {
throwIteratorAccessError();
}
if (this.p === 1) {
if (this.C === 1) {
t.i = r;
return true;
}
if (t === this.C.h) {
if (this.O(t.next().i, r) > 0) {
if (t === this.j.h) {
if (this.g(t.p().i, r) > 0) {
t.i = r;

@@ -737,4 +765,4 @@ return true;

}
if (t === this.C.o) {
if (this.O(t.pre().i, r) < 0) {
if (t === this.j.o) {
if (this.g(t.v().i, r) < 0) {
t.i = r;

@@ -745,6 +773,6 @@ return true;

}
var i = t.pre().i;
if (this.O(i, r) >= 0) return false;
var n = t.next().i;
if (this.O(n, r) <= 0) return false;
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;

@@ -754,3 +782,3 @@ return true;

TreeContainer.prototype.eraseElementByPos = function(e) {
if (e < 0 || e > this.p - 1) {
if (e < 0 || e > this.C - 1) {
throw new RangeError;

@@ -760,5 +788,5 @@ }

var t = this;
this.P(this.T, (function(i) {
this.H(this.N, (function(i) {
if (e === r) {
t.g(i);
t.B(i);
return true;

@@ -769,33 +797,77 @@ }

}));
return this.C;
};
TreeContainer.prototype.G = function(e, r) {
while (e) {
var t = this.O(e.i, r);
if (t < 0) {
e = e.o;
} else if (t > 0) {
e = e.h;
} else return e;
}
return e;
};
TreeContainer.prototype.eraseElementByKey = function(e) {
if (!this.p) return;
var r = this.G(this.T, e);
if (r === undefined) return;
this.g(r);
if (this.C === 0) return false;
var r = this.J(this.N, e);
if (r === this.j) return false;
this.B(r);
return true;
};
TreeContainer.prototype.eraseElementByIterator = function(e) {
var r = e.A;
if (r === this.C) {
throw new RangeError("Invalid iterator");
var r = e.M;
if (r === this.j) {
throwIteratorAccessError();
}
if (r.o === undefined) {
e = e.next();
var t = r.o === undefined;
var i = e.iteratorType === 0;
if (i) {
if (t) e.next();
} else {
if (!t || r.h === undefined) e.next();
}
this.g(r);
this.B(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.p) return 0;
if (this.C === 0) return 0;
var traversal = function(e) {

@@ -805,3 +877,3 @@ if (!e) return 0;

};
return traversal(this.T);
return traversal(this.N);
};

@@ -815,17 +887,17 @@ return TreeContainer;

var n = e.call(this, i) || this;
n.A = r;
n.C = t;
n.M = r;
n.j = t;
if (n.iteratorType === 0) {
n.pre = function() {
if (this.A === this.C.h) {
throw new RangeError("Tree iterator access denied!");
if (this.M === this.j.h) {
throwIteratorAccessError();
}
this.A = this.A.pre();
this.M = this.M.v();
return this;
};
n.next = function() {
if (this.A === this.C) {
throw new RangeError("Tree iterator access denied!");
if (this.M === this.j) {
throwIteratorAccessError();
}
this.A = this.A.next();
this.M = this.M.p();
return this;

@@ -835,13 +907,13 @@ };

n.pre = function() {
if (this.A === this.C.o) {
throw new RangeError("Tree iterator access denied!");
if (this.M === this.j.o) {
throwIteratorAccessError();
}
this.A = this.A.next();
this.M = this.M.p();
return this;
};
n.next = function() {
if (this.A === this.C) {
throw new RangeError("Tree iterator access denied!");
if (this.M === this.j) {
throwIteratorAccessError();
}
this.A = this.A.pre();
this.M = this.M.v();
return this;

@@ -854,7 +926,7 @@ };

get: function() {
var e = this.A;
var r = this.C.l;
if (e === this.C) {
var e = this.M;
var r = this.j.l;
if (e === this.j) {
if (r) {
return r.v - 1;
return r.O - 1;
}

@@ -865,3 +937,3 @@ return 0;

if (e.h) {
t += e.h.v;
t += e.h.O;
}

@@ -873,3 +945,3 @@ while (e !== r) {

if (i.h) {
t += i.h.v;
t += i.h.O;
}

@@ -884,5 +956,2 @@ }

});
TreeIterator.prototype.equals = function(e) {
return this.A === e.A;
};
return TreeIterator;

@@ -898,4 +967,4 @@ }(ContainerIterator);

get: function() {
if (this.A === this.C) {
throw new RangeError("OrderedMap iterator access denied");
if (this.M === this.j) {
throwIteratorAccessError();
}

@@ -905,3 +974,3 @@ var e = this;

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

@@ -912,3 +981,3 @@ set: function(r, t, i) {

}
e.A.u = i;
e.M.u = i;
return true;

@@ -922,3 +991,3 @@ }

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

@@ -941,3 +1010,3 @@ return OrderedMapIterator;

}
OrderedMap.prototype.q = function(e) {
OrderedMap.prototype.K = function(e) {
return __generator(this, (function(r) {

@@ -947,3 +1016,3 @@ switch (r.label) {

if (e === undefined) return [ 2 ];
return [ 5, __values(this.q(e.h)) ];
return [ 5, __values(this.K(e.h)) ];

@@ -956,3 +1025,3 @@ case 1:

r.sent();
return [ 5, __values(this.q(e.o)) ];
return [ 5, __values(this.K(e.o)) ];

@@ -966,102 +1035,50 @@ case 3:

OrderedMap.prototype.begin = function() {
return new OrderedMapIterator(this.C.h || this.C, this.C);
return new OrderedMapIterator(this.j.h || this.j, this.j);
};
OrderedMap.prototype.end = function() {
return new OrderedMapIterator(this.C, this.C);
return new OrderedMapIterator(this.j, this.j);
};
OrderedMap.prototype.rBegin = function() {
return new OrderedMapIterator(this.C.o || this.C, this.C, 1);
return new OrderedMapIterator(this.j.o || this.j, this.j, 1);
};
OrderedMap.prototype.rEnd = function() {
return new OrderedMapIterator(this.C, this.C, 1);
return new OrderedMapIterator(this.j, this.j, 1);
};
OrderedMap.prototype.front = function() {
if (!this.p) return undefined;
var e = this.C.h;
if (this.C === 0) return;
var e = this.j.h;
return [ e.i, e.u ];
};
OrderedMap.prototype.back = function() {
if (!this.p) return undefined;
var e = this.C.o;
if (this.C === 0) return;
var e = this.j.o;
return [ e.i, e.u ];
};
OrderedMap.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;
}
}
};
OrderedMap.prototype.lowerBound = function(e) {
var r = this.m(this.T, e);
return new OrderedMapIterator(r, this.C);
var r = this.R(this.N, e);
return new OrderedMapIterator(r, this.j);
};
OrderedMap.prototype.upperBound = function(e) {
var r = this.R(this.T, e);
return new OrderedMapIterator(r, this.C);
var r = this.G(this.N, e);
return new OrderedMapIterator(r, this.j);
};
OrderedMap.prototype.reverseLowerBound = function(e) {
var r = this.k(this.T, e);
return new OrderedMapIterator(r, this.C);
var r = this.q(this.N, e);
return new OrderedMapIterator(r, this.j);
};
OrderedMap.prototype.reverseUpperBound = function(e) {
var r = this.j(this.T, e);
return new OrderedMapIterator(r, this.C);
var r = this.D(this.N, e);
return new OrderedMapIterator(r, this.j);
};
OrderedMap.prototype.setElement = function(e, r, t) {
this.M(e, r, t);
return this.S(e, r, t);
};
OrderedMap.prototype.find = function(e) {
var r = this.G(this.T, e);
if (r !== undefined) {
return new OrderedMapIterator(r, this.C);
}
return this.end();
var r = this.J(this.N, e);
return new OrderedMapIterator(r, this.j);
};
OrderedMap.prototype.getElementByKey = function(e) {
var r = this.G(this.T, e);
return r ? r.u : undefined;
var r = this.J(this.N, e);
return r.u;
};
OrderedMap.prototype.getElementByPos = function(e) {
var r, t;
if (e < 0 || e > this.p - 1) {
throw new RangeError;
}
var i;
var n = 0;
try {
for (var s = __values(this), a = s.next(); !a.done; a = s.next()) {
var f = a.value;
if (n === e) {
i = f;
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;
};
OrderedMap.prototype.union = function(e) {

@@ -1072,5 +1089,6 @@ var r = this;

}));
return this.C;
};
OrderedMap.prototype[Symbol.iterator] = function() {
return this.q(this.T);
return this.K(this.N);
};

@@ -1077,0 +1095,0 @@ return OrderedMap;

425

dist/umd/ordered-map.js
/*!
* @js-sdsl/ordered-map v4.2.0-beta.1
* @js-sdsl/ordered-map v4.2.0
* https://github.com/js-sdsl/js-sdsl

@@ -175,27 +175,12 @@ * (c) 2021-present ZLY201 <zilongyao1366@gmail.com>

/**
* @internal
*/
var TreeNode = /** @class */function () {
function TreeNode(key, value) {
/**
* @internal
*/
this._color = 1 /* TreeNodeColor.RED */;
/**
* @internal
*/
this._key = undefined;
/**
* @internal
*/
this._value = undefined;
/**
* @internal
*/
this._left = undefined;
/**
* @internal
*/
this._right = undefined;
/**
* @internal
*/
this._parent = undefined;

@@ -207,5 +192,5 @@ this._key = key;

* @description Get the pre node.
* @return TreeNode about the pre node.
* @returns TreeNode about the pre node.
*/
TreeNode.prototype.pre = function () {
TreeNode.prototype._pre = function () {
var preNode = this;

@@ -231,5 +216,5 @@ if (preNode._color === 1 /* TreeNodeColor.RED */ && preNode._parent._parent === preNode) {

* @description Get the next node.
* @return TreeNode about the next node.
* @returns TreeNode about the next node.
*/
TreeNode.prototype.next = function () {
TreeNode.prototype._next = function () {
var nextNode = this;

@@ -255,5 +240,5 @@ if (nextNode._right) {

* @description Rotate left.
* @return TreeNode about moved to original position after rotation.
* @returns TreeNode about moved to original position after rotation.
*/
TreeNode.prototype.rotateLeft = function () {
TreeNode.prototype._rotateLeft = function () {
var PP = this._parent;

@@ -272,5 +257,5 @@ var V = this._right;

* @description Rotate right.
* @return TreeNode about moved to original position after rotation.
* @returns TreeNode about moved to original position after rotation.
*/
TreeNode.prototype.rotateRight = function () {
TreeNode.prototype._rotateRight = function () {
var PP = this._parent;

@@ -289,2 +274,5 @@ var F = this._left;

}();
/**
* @internal
*/
var TreeNodeEnableIndex = /** @class */function (_super) {

@@ -294,17 +282,2 @@ __extends(TreeNodeEnableIndex, _super);

var _this = _super !== null && _super.apply(this, arguments) || this;
/**
* @internal
*/
_this._left = undefined;
/**
* @internal
*/
_this._right = undefined;
/**
* @internal
*/
_this._parent = undefined;
/**
* @internal
*/
_this._subTreeSize = 1;

@@ -315,8 +288,8 @@ return _this;

* @description Rotate left and do recount.
* @return TreeNode about moved to original position after rotation.
* @returns TreeNode about moved to original position after rotation.
*/
TreeNodeEnableIndex.prototype.rotateLeft = function () {
var parent = _super.prototype.rotateLeft.call(this);
this.recount();
parent.recount();
TreeNodeEnableIndex.prototype._rotateLeft = function () {
var parent = _super.prototype._rotateLeft.call(this);
this._recount();
parent._recount();
return parent;

@@ -326,14 +299,18 @@ };

* @description Rotate right and do recount.
* @return TreeNode about moved to original position after rotation.
* @returns TreeNode about moved to original position after rotation.
*/
TreeNodeEnableIndex.prototype.rotateRight = function () {
var parent = _super.prototype.rotateRight.call(this);
this.recount();
parent.recount();
TreeNodeEnableIndex.prototype._rotateRight = function () {
var parent = _super.prototype._rotateRight.call(this);
this._recount();
parent._recount();
return parent;
};
TreeNodeEnableIndex.prototype.recount = function () {
TreeNodeEnableIndex.prototype._recount = function () {
this._subTreeSize = 1;
if (this._left) this._subTreeSize += this._left._subTreeSize;
if (this._right) this._subTreeSize += this._right._subTreeSize;
if (this._left) {
this._subTreeSize += this._left._subTreeSize;
}
if (this._right) {
this._subTreeSize += this._right._subTreeSize;
}
};

@@ -344,2 +321,5 @@ return TreeNodeEnableIndex;

var ContainerIterator = /** @class */function () {
/**
* @internal
*/
function ContainerIterator(iteratorType) {

@@ -351,2 +331,11 @@ if (iteratorType === void 0) {

}
/**
* @param iter - The other iterator you want to compare.
* @returns Whether this equals to obj.
* @example
* container.find(1).equals(container.end());
*/
ContainerIterator.prototype.equals = function (iter) {
return this._node === iter._node;
};
return ContainerIterator;

@@ -362,4 +351,17 @@ }();

}
Object.defineProperty(Base.prototype, "length", {
/**
* @returns The size of the container.
* @example
* const container = new Vector([1, 2]);
* console.log(container.length); // 2
*/
get: function () {
return this._length;
},
enumerable: false,
configurable: true
});
/**
* @return The size of the container.
* @returns The size of the container.
* @example

@@ -373,3 +375,3 @@ * const container = new Vector([1, 2]);

/**
* @return Boolean about if the container is empty.
* @returns Whether the container is empty.
* @example

@@ -392,7 +394,14 @@ * container.clear();

/**
* @description Throw an iterator access error.
* @internal
*/
function throwIteratorAccessError() {
throw new RangeError('Iterator access denied!');
}
var TreeContainer = /** @class */function (_super) {
__extends(TreeContainer, _super);
/**
* @param cmp The compare function.
* @param enableIndex Whether to enable iterator indexing function.
* @internal
*/

@@ -432,7 +441,8 @@ function TreeContainer(cmp, enableIndex) {

curNode_1 = _a.curNode;
parentNode.recount();
grandParent.recount();
curNode_1.recount();
parentNode._recount();
grandParent._recount();
curNode_1._recount();
}
}
return this._length;
};

@@ -451,2 +461,3 @@ _this._eraseNode = function (curNode) {

if (curNode) this._insertNodeSelfBalance(curNode);
return this._length;
};

@@ -459,9 +470,6 @@ _this._eraseNode = _this._preEraseNode;

/**
* @param curNode The starting node of the search.
* @param key The key you want to search.
* @return TreeNode which key is greater than or equals to the given key.
* @internal
*/
TreeContainer.prototype._lowerBound = function (curNode, key) {
var resNode;
var resNode = this._header;
while (curNode) {

@@ -476,12 +484,9 @@ var cmpResult = this._cmp(curNode._key, key);

}
return resNode === undefined ? this._header : resNode;
return resNode;
};
/**
* @param curNode The starting node of the search.
* @param key The key you want to search.
* @return TreeNode which key is greater than the given key.
* @internal
*/
TreeContainer.prototype._upperBound = function (curNode, key) {
var resNode;
var resNode = this._header;
while (curNode) {

@@ -496,12 +501,9 @@ var cmpResult = this._cmp(curNode._key, key);

}
return resNode === undefined ? this._header : resNode;
return resNode;
};
/**
* @param curNode The starting node of the search.
* @param key The key you want to search.
* @return TreeNode which key is less than or equals to the given key.
* @internal
*/
TreeContainer.prototype._reverseLowerBound = function (curNode, key) {
var resNode;
var resNode = this._header;
while (curNode) {

@@ -516,12 +518,9 @@ var cmpResult = this._cmp(curNode._key, key);

}
return resNode === undefined ? this._header : resNode;
return resNode;
};
/**
* @param curNode The starting node of the search.
* @param key The key you want to search.
* @return TreeNode which key is less than the given key.
* @internal
*/
TreeContainer.prototype._reverseUpperBound = function (curNode, key) {
var resNode;
var resNode = this._header;
while (curNode) {

@@ -536,7 +535,5 @@ var cmpResult = this._cmp(curNode._key, key);

}
return resNode === undefined ? this._header : resNode;
return resNode;
};
/**
* @description Make self balance after erase a node.
* @param curNode The node want to remove.
* @internal

@@ -558,4 +555,4 @@ */

if (parentNode === this._root) {
this._root = parentNode.rotateLeft();
} else parentNode.rotateLeft();
this._root = parentNode._rotateLeft();
} else parentNode._rotateLeft();
} else {

@@ -567,4 +564,4 @@ if (brother._right && brother._right._color === 1 /* TreeNodeColor.RED */) {

if (parentNode === this._root) {
this._root = parentNode.rotateLeft();
} else parentNode.rotateLeft();
this._root = parentNode._rotateLeft();
} else parentNode._rotateLeft();
return;

@@ -574,3 +571,3 @@ } else if (brother._left && brother._left._color === 1 /* TreeNodeColor.RED */) {

brother._left._color = 0 /* TreeNodeColor.BLACK */;
brother.rotateRight();
brother._rotateRight();
} else {

@@ -587,4 +584,4 @@ brother._color = 1 /* TreeNodeColor.RED */;

if (parentNode === this._root) {
this._root = parentNode.rotateRight();
} else parentNode.rotateRight();
this._root = parentNode._rotateRight();
} else parentNode._rotateRight();
} else {

@@ -596,4 +593,4 @@ if (brother._left && brother._left._color === 1 /* TreeNodeColor.RED */) {

if (parentNode === this._root) {
this._root = parentNode.rotateRight();
} else parentNode.rotateRight();
this._root = parentNode._rotateRight();
} else parentNode._rotateRight();
return;

@@ -603,3 +600,3 @@ } else if (brother._right && brother._right._color === 1 /* TreeNodeColor.RED */) {

brother._right._color = 0 /* TreeNodeColor.BLACK */;
brother.rotateLeft();
brother._rotateLeft();
} else {

@@ -649,3 +646,2 @@ brother._color = 1 /* TreeNodeColor.RED */;

/**
* @description InOrder traversal the tree.
* @internal

@@ -705,4 +701,4 @@ */

if (grandParent === this._root) {
this._root = grandParent.rotateRight();
} else grandParent.rotateRight();
this._root = grandParent._rotateRight();
} else grandParent._rotateRight();
grandParent._color = 1 /* TreeNodeColor.RED */;

@@ -747,4 +743,4 @@ }

if (grandParent === this._root) {
this._root = grandParent.rotateLeft();
} else grandParent.rotateLeft();
this._root = grandParent._rotateLeft();
} else grandParent._rotateLeft();
grandParent._color = 1 /* TreeNodeColor.RED */;

@@ -802,3 +798,3 @@ }

} else /* istanbul ignore else */if (iterCmpRes > 0) {
var preNode = iterNode.pre();
var preNode = iterNode._pre();
var preCmpRes = this._cmp(preNode._key, key);

@@ -852,2 +848,16 @@ if (preCmpRes === 0) {

};
/**
* @internal
*/
TreeContainer.prototype._findElementNode = function (curNode, key) {
while (curNode) {
var cmpResult = this._cmp(curNode._key, key);
if (cmpResult < 0) {
curNode = curNode._right;
} else if (cmpResult > 0) {
curNode = curNode._left;
} else return curNode;
}
return curNode || this._header;
};
TreeContainer.prototype.clear = function () {

@@ -861,5 +871,5 @@ this._length = 0;

* @description Update node's key by iterator.
* @param iter The iterator you want to change.
* @param key The key you want to update.
* @return Boolean about if the modification is successful.
* @param iter - The iterator you want to change.
* @param key - The key you want to update.
* @returns Whether the modification is successful.
* @example

@@ -873,3 +883,3 @@ * const st = new orderedSet([1, 2, 5]);

if (node === this._header) {
throw new TypeError('Invalid iterator!');
throwIteratorAccessError();
}

@@ -881,3 +891,3 @@ if (this._length === 1) {

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

@@ -889,3 +899,3 @@ return true;

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

@@ -896,5 +906,5 @@ return true;

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

@@ -918,29 +928,15 @@ node._key = key;

});
return this._length;
};
/**
* @description Find node which key is equals to the given key.
* @param curNode The starting node of the search.
* @param key The key you want to search.
* @internal
*/
TreeContainer.prototype._findElementNode = function (curNode, key) {
while (curNode) {
var cmpResult = this._cmp(curNode._key, key);
if (cmpResult < 0) {
curNode = curNode._right;
} else if (cmpResult > 0) {
curNode = curNode._left;
} else return curNode;
}
return curNode;
};
/**
* @description Remove the element of the specified key.
* @param key The key you want to remove.
* @param key - The key you want to remove.
* @returns Whether erase successfully.
*/
TreeContainer.prototype.eraseElementByKey = function (key) {
if (!this._length) return;
if (this._length === 0) return false;
var curNode = this._findElementNode(this._root, key);
if (curNode === undefined) return;
if (curNode === this._header) return false;
this._eraseNode(curNode);
return true;
};

@@ -950,6 +946,14 @@ TreeContainer.prototype.eraseElementByIterator = function (iter) {

if (node === this._header) {
throw new RangeError('Invalid iterator');
throwIteratorAccessError();
}
if (node._right === undefined) {
iter = iter.next();
var hasNoRight = node._right === undefined;
var isNormal = iter.iteratorType === 0 /* IteratorType.NORMAL */;
// For the normal iterator, the `next` node will be swapped to `this` node when has right.
if (isNormal) {
// So we should move it to next when it's right is null.
if (hasNoRight) iter.next();
} else {
// For the reverse iterator, only when it doesn't have right and has left the `next` node will be swapped.
// So when it has right, or it is a leaf node we should move it to `next`.
if (!hasNoRight || node._left === undefined) iter.next();
}

@@ -959,8 +963,57 @@ this._eraseNode(node);

};
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;
};
/**
* @description Get the height of the tree.
* @return Number about the height of the RB-tree.
* @returns Number about the height of the RB-tree.
*/
TreeContainer.prototype.getHeight = function () {
if (!this._length) return 0;
if (this._length === 0) return 0;
var traversal = function (curNode) {

@@ -987,5 +1040,5 @@ if (!curNode) return 0;

if (this._node === this._header._left) {
throw new RangeError('Tree iterator access denied!');
throwIteratorAccessError();
}
this._node = this._node.pre();
this._node = this._node._pre();
return this;

@@ -995,5 +1048,5 @@ };

if (this._node === this._header) {
throw new RangeError('Tree iterator access denied!');
throwIteratorAccessError();
}
this._node = this._node.next();
this._node = this._node._next();
return this;

@@ -1004,5 +1057,5 @@ };

if (this._node === this._header._right) {
throw new RangeError('Tree iterator access denied!');
throwIteratorAccessError();
}
this._node = this._node.next();
this._node = this._node._next();
return this;

@@ -1012,5 +1065,5 @@ };

if (this._node === this._header) {
throw new RangeError('Tree iterator access denied!');
throwIteratorAccessError();
}
this._node = this._node.pre();
this._node = this._node._pre();
return this;

@@ -1024,6 +1077,5 @@ };

* @description Get the sequential index of the iterator in the tree container.<br/>
* <strong>
* Note:
* </strong>
* <strong>Note:</strong>
* This function only takes effect when the specified tree container `enableIndex = true`.
* @returns The index subscript of the node in the tree.
* @example

@@ -1061,5 +1113,2 @@ * const st = new OrderedSet([1, 2, 3], true);

});
TreeIterator.prototype.equals = function (obj) {
return this._node === obj._node;
};
return TreeIterator;

@@ -1076,3 +1125,3 @@ }(ContainerIterator);

if (this._node === this._header) {
throw new RangeError('OrderedMap iterator access denied');
throwIteratorAccessError();
}

@@ -1104,5 +1153,5 @@ var self = this;

/**
* @param container The initialization container.
* @param cmp The compare function.
* @param enableIndex Whether to enable iterator indexing function.
* @param container - The initialization container.
* @param cmp - The compare function.
* @param enableIndex - Whether to enable iterator indexing function.
* @example

@@ -1162,3 +1211,3 @@ * new OrderedMap();

OrderedMap.prototype.front = function () {
if (!this._length) return undefined;
if (this._length === 0) return;
var minNode = this._header._left;

@@ -1168,26 +1217,6 @@ return [minNode._key, minNode._value];

OrderedMap.prototype.back = function () {
if (!this._length) return undefined;
if (this._length === 0) return;
var maxNode = this._header._right;
return [maxNode._key, maxNode._value];
};
OrderedMap.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 pair = _c.value;
callback(pair, 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;
}
}
};
OrderedMap.prototype.lowerBound = function (key) {

@@ -1211,5 +1240,6 @@ var resNode = this._lowerBound(this._root, key);

* @description Insert a key-value pair or set value by the given key.
* @param key The key want to insert.
* @param value The value want to set.
* @param hint You can give an iterator hint to improve insertion efficiency.
* @param key - The key want to insert.
* @param value - The value want to set.
* @param hint - You can give an iterator hint to improve insertion efficiency.
* @return The size of container after setting.
* @example

@@ -1222,48 +1252,18 @@ * const mp = new OrderedMap([[2, 0], [4, 0], [5, 0]]);

OrderedMap.prototype.setElement = function (key, value, hint) {
this._set(key, value, hint);
return this._set(key, value, hint);
};
OrderedMap.prototype.find = function (key) {
var curNode = this._findElementNode(this._root, key);
if (curNode !== undefined) {
return new OrderedMapIterator(curNode, this._header);
}
return this.end();
return new OrderedMapIterator(curNode, this._header);
};
/**
* @description Get the value of the element of the specified key.
* @example const val = container.getElementByKey(1);
* @param key - The specified key you want to get.
* @example
* const val = container.getElementByKey(1);
*/
OrderedMap.prototype.getElementByKey = function (key) {
var curNode = this._findElementNode(this._root, key);
return curNode ? curNode._value : undefined;
return curNode._value;
};
OrderedMap.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 pair = _c.value;
if (index === pos) {
res = pair;
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;
};
OrderedMap.prototype.union = function (other) {

@@ -1274,2 +1274,3 @@ var self = this;

});
return this._length;
};

@@ -1276,0 +1277,0 @@ OrderedMap.prototype[Symbol.iterator] = function () {

4

dist/umd/ordered-map.min.js
/*!
* @js-sdsl/ordered-map v4.2.0-beta.1
* @js-sdsl/ordered-map v4.2.0
* https://github.com/js-sdsl/js-sdsl

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

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

2

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

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

16

README.md
<p align="center">
<a href="https://js-sdsl.org/" target="_blank" rel="noopener noreferrer">
<img src="https://js-sdsl.org/assets/logo-removebg.png" alt="js-sdsl logo" width="120" />
<img src="https://js-sdsl.org/assets/image/logo/logo-removebg.png" alt="js-sdsl logo" width="120" />
</a>

@@ -45,23 +45,23 @@ </p>

<td>
<img alt="IE / Edge" src="https://www.w3schools.com/images/compatible_edge2020.png" />
<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://www.w3schools.com/images/compatible_firefox2020.png" />
<img alt="Firefox" src="https://js-sdsl.org/assets/image/platform/firefox.png" />
<div>Firefox</div>
</td>
<td>
<img alt="Chrome" src="https://www.w3schools.com/images/compatible_chrome2020.png" />
<img alt="Chrome" src="https://js-sdsl.org/assets/image/platform/chrome.png" />
<div>Chrome</div>
</td>
<td>
<img alt="Safari" src="https://www.w3schools.com/images/compatible_safari2020.png" />
<img alt="Safari" src="https://js-sdsl.org/assets/image/platform/safari.png" />
<div>Safari</div>
</td>
<td>
<img alt="Opera" src="https://www.w3schools.com/images/compatible_opera2020.png" />
<img alt="Opera" src="https://js-sdsl.org/assets/image/platform/opera.png" />
<div>Opera</div>
</td>
<td>
<img alt="NodeJs" src="https://cdn-icons-png.flaticon.com/512/5968/5968322.png" width="20" />
<img alt="NodeJs" src="https://js-sdsl.org/assets/image/platform/nodejs.png" />
<div>NodeJs</div>

@@ -217,3 +217,3 @@ </td>

<a href="https://eslint.org/"><img src="https://js-sdsl.org/assets/sponsors/eslint-logo-color.png" alt="eslint logo" width="150"></a>
<a href="https://eslint.org/"><img src="https://js-sdsl.org/assets/image/sponsors/eslint-logo-color.png" alt="eslint logo" width="150"></a>

@@ -220,0 +220,0 @@ Thanks also give to these sponsors or backers:

16

README.zh-CN.md
<p align="center">
<a href="https://js-sdsl.org/" target="_blank" rel="noopener noreferrer">
<img src="https://js-sdsl.org/assets/logo-removebg.png" alt="js-sdsl logo" width="120" />
<img src="https://js-sdsl.org/assets/image/logo/logo-removebg.png" alt="js-sdsl logo" width="120" />
</a>

@@ -47,23 +47,23 @@ </p>

<td>
<img alt="IE / Edge" src="https://www.w3schools.com/images/compatible_edge2020.png" />
<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://www.w3schools.com/images/compatible_firefox2020.png" />
<img alt="Firefox" src="https://js-sdsl.org/assets/image/platform/firefox.png" />
<div>Firefox</div>
</td>
<td>
<img alt="Chrome" src="https://www.w3schools.com/images/compatible_chrome2020.png" />
<img alt="Chrome" src="https://js-sdsl.org/assets/image/platform/chrome.png" />
<div>Chrome</div>
</td>
<td>
<img alt="Safari" src="https://www.w3schools.com/images/compatible_safari2020.png" />
<img alt="Safari" src="https://js-sdsl.org/assets/image/platform/safari.png" />
<div>Safari</div>
</td>
<td>
<img alt="Opera" src="https://www.w3schools.com/images/compatible_opera2020.png" />
<img alt="Opera" src="https://js-sdsl.org/assets/image/platform/opera.png" />
<div>Opera</div>
</td>
<td>
<img alt="NodeJs" src="https://cdn-icons-png.flaticon.com/512/5968/5968322.png" width="20" />
<img alt="NodeJs" src="https://js-sdsl.org/assets/image/platform/nodejs.png" />
<div>NodeJs</div>

@@ -219,3 +219,3 @@ </td>

<a href="https://eslint.org/"><img src="https://js-sdsl.org/assets/sponsors/eslint-logo-color.png" alt="eslint logo" width="150"></a>
<a href="https://eslint.org/"><img src="https://js-sdsl.org/assets/image/sponsors/eslint-logo-color.png" alt="eslint logo" width="150"></a>

@@ -222,0 +222,0 @@ 同样感谢这些赞助商和支持者们：

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