/
TreeMultiSet.ts
171 lines (150 loc) · 5.5 KB
/
TreeMultiSet.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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
//================================================================
/**
* @packageDocumentation
* @module std
*/
//================================================================
import { MultiTreeSet } from "../internal/container/associative/MultiTreeSet";
import { ITreeContainer } from "../internal/container/associative/ITreeContainer";
import { IForwardIterator } from "../iterator/IForwardIterator";
import { SetElementList } from "../internal/container/associative/SetElementList";
import { MultiSetTree } from "../internal/tree/MultiSetTree";
import { Comparator } from "../internal/functional/Comparator";
import { Temporary } from "../internal/functional/Temporary";
/**
* Multiple-key Set based on Tree.
*
* @author Jeongho Nam - https://github.com/samchon
*/
export class TreeMultiSet<Key>
extends MultiTreeSet<Key,
TreeMultiSet<Key>,
TreeMultiSet.Iterator<Key>,
TreeMultiSet.ReverseIterator<Key>>
{
private tree_!: MultiSetTree<Key, TreeMultiSet<Key>>;
/* ---------------------------------------------------------
CONSTURCTORS
--------------------------------------------------------- */
/**
* Default Constructor.
*
* @param comp A binary function predicates *x* element would be placed before *y*. When returns `true`, then *x* precedes *y*. Note that, because *equality* is predicated by `!comp(x, y) && !comp(y, x)`, the function must not cover the *equality* like `<=` or `>=`. It must exclude the *equality* like `<` or `>`. Default is {@link less}.
*/
public constructor(comp?: Comparator<Key>);
/**
* Initializer Constructor.
*
* @param items Items to assign.
* @param comp A binary function predicates *x* element would be placed before *y*. When returns `true`, then *x* precedes *y*. Note that, because *equality* is predicated by `!comp(x, y) && !comp(y, x)`, the function must not cover the *equality* like `<=` or `>=`. It must exclude the *equality* like `<` or `>`. Default is {@link less}.
*/
public constructor(items: Key[], comp?: Comparator<Key>);
/**
* Copy Constructor.
*
* @param obj Object to copy.
*/
public constructor(obj: TreeMultiSet<Key>);
/**
* Range Constructor.
*
* @param first Input iterator of the first position.
* @param last Input iterator of the last position.
* @param comp A binary function predicates *x* element would be placed before *y*. When returns `true`, then *x* precedes *y*. Note that, because *equality* is predicated by `!comp(x, y) && !comp(y, x)`, the function must not cover the *equality* like `<=` or `>=`. It must exclude the *equality* like `<` or `>`. Default is {@link less}.
*/
public constructor
(
first: Readonly<IForwardIterator<Key>>,
last: Readonly<IForwardIterator<Key>>,
comp?: Comparator<Key>
);
public constructor(...args: any[])
{
super(thisArg => new SetElementList(<Temporary>thisArg) as Temporary);
ITreeContainer.construct<Key, Key,
TreeMultiSet<Key>,
TreeMultiSet.Iterator<Key>,
TreeMultiSet.ReverseIterator<Key>,
Key>
(
this, TreeMultiSet,
comp =>
{
this.tree_ = new MultiSetTree(this as TreeMultiSet<Key>, comp);
},
...args
);
}
/**
* @inheritDoc
*/
public clear(): void
{
super.clear();
this.tree_.clear();
}
/**
* @inheritDoc
*/
public swap(obj: TreeMultiSet<Key>): void
{
// SWAP CONTENTS
[this.data_, obj.data_] = [obj.data_, this.data_];
SetElementList._Swap_associative(this.data_ as Temporary, obj.data_ as Temporary);
// SWAP RB-TREE
MultiSetTree._Swap_source(this.tree_, obj.tree_);
[this.tree_, obj.tree_] = [obj.tree_, this.tree_];
}
/* ---------------------------------------------------------
ACCESSORS
--------------------------------------------------------- */
/**
* @inheritDoc
*/
public key_comp(): Comparator<Key>
{
return this.tree_.key_comp();
}
/**
* @inheritDoc
*/
public lower_bound(key: Key): TreeMultiSet.Iterator<Key>
{
return this.tree_.lower_bound(key);
}
/**
* @inheritDoc
*/
public upper_bound(key: Key): TreeMultiSet.Iterator<Key>
{
return this.tree_.upper_bound(key);
}
/* ---------------------------------------------------------
POST-PROCESS
--------------------------------------------------------- */
protected _Handle_insert(first: TreeMultiSet.Iterator<Key>, last: TreeMultiSet.Iterator<Key>): void
{
for (; !first.equals(last); first = first.next())
this.tree_.insert(first);
}
protected _Handle_erase(first: TreeMultiSet.Iterator<Key>, last: TreeMultiSet.Iterator<Key>): void
{
for (; !first.equals(last); first = first.next())
this.tree_.erase(first);
}
}
export namespace TreeMultiSet
{
// HEAD
/**
* Iterator of {@link TreeMultiSet}
*/
export type Iterator<Key> = SetElementList.Iterator<Key, false, TreeMultiSet<Key>>;
/**
* Reverse iterator of {@link TreeMultiSet}
*/
export type ReverseIterator<Key> = SetElementList.ReverseIterator<Key, false, TreeMultiSet<Key>>;
// BODY
export const Iterator = SetElementList.Iterator;
export const ReverseIterator = SetElementList.ReverseIterator;
}