-
-
Notifications
You must be signed in to change notification settings - Fork 61
/
OrderedSet.ts
125 lines (122 loc) · 3.68 KB
/
OrderedSet.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
import TreeContainer from './Base';
import { TreeNode } from './Base/TreeNode';
import TreeIterator from './Base/TreeIterator';
import { $checkWithinAccessParams } from '@/utils/checkParams.macro';
import { initContainer, IteratorType } from '@/container/ContainerBase';
export class OrderedSetIterator<K> extends TreeIterator<K, undefined> {
get pointer() {
if (this._node === this._header) {
throw new RangeError('OrderedSet iterator access denied!');
}
return this._node._key as K;
}
copy() {
return new OrderedSetIterator(this._node, this._header, this.iteratorType);
}
}
class OrderedSet<K> extends TreeContainer<K, undefined> {
/**
* @param container The initialization container.
* @param cmp The compare function.
* @param enableIndex Whether to enable iterator indexing function.
*/
constructor(
container: initContainer<K> = [],
cmp?: (x: K, y: K) => number,
enableIndex?: boolean
) {
super(cmp, enableIndex);
container.forEach((element) => this.insert(element));
}
/**
* @internal
*/
private readonly _iterationFunc:
(curNode: TreeNode<K, undefined> | undefined) => Generator<K, void, undefined> =
function * (this: OrderedSet<K>, curNode: TreeNode<K, undefined> | undefined) {
if (curNode === undefined) return;
yield * this._iterationFunc(curNode._left);
yield curNode._key as K;
yield * this._iterationFunc(curNode._right);
};
begin() {
return new OrderedSetIterator(
this._header._left || this._header,
this._header
);
}
end() {
return new OrderedSetIterator(this._header, this._header);
}
rBegin() {
return new OrderedSetIterator(
this._header._right || this._header,
this._header,
IteratorType.REVERSE
);
}
rEnd() {
return new OrderedSetIterator(this._header, this._header, IteratorType.REVERSE);
}
front() {
return this._header._left ? this._header._left._key : undefined;
}
back() {
return this._header._right ? this._header._right._key : undefined;
}
forEach(callback: (element: K, index: number) => void) {
let index = 0;
for (const element of this) callback(element, index++);
}
getElementByPos(pos: number) {
$checkWithinAccessParams!(pos, 0, this._length - 1);
let res;
let index = 0;
for (const element of this) {
if (index === pos) {
res = element;
break;
}
index += 1;
}
return res as K;
}
/**
* @description Insert element to set.
* @param _key The _key want to insert.
* @param hint You can give an iterator hint to improve insertion efficiency.
*/
insert(_key: K, hint?: OrderedSetIterator<K>) {
this._set(_key, undefined, hint);
}
find(element: K) {
const curNode = this._findElementNode(this._root, element);
if (curNode !== undefined) {
return new OrderedSetIterator(curNode, this._header);
}
return this.end();
}
lowerBound(_key: K) {
const resNode = this._lowerBound(this._root, _key);
return new OrderedSetIterator(resNode, this._header);
}
upperBound(_key: K) {
const resNode = this._upperBound(this._root, _key);
return new OrderedSetIterator(resNode, this._header);
}
reverseLowerBound(_key: K) {
const resNode = this._reverseLowerBound(this._root, _key);
return new OrderedSetIterator(resNode, this._header);
}
reverseUpperBound(_key: K) {
const resNode = this._reverseUpperBound(this._root, _key);
return new OrderedSetIterator(resNode, this._header);
}
union(other: OrderedSet<K>) {
other.forEach((element) => this.insert(element));
}
[Symbol.iterator]() {
return this._iterationFunc(this._root);
}
}
export default OrderedSet;