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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
|
#ifndef dsa_SplayTree_Range_h__
#define dsa_SplayTree_Range_h__
#include <cstdlib>
#include <utility>
#include "../math/utility.h"
namespace meow{
//#
//#=== meow:: *SplayTree_Range<Key, Value>* (C++ class)
//#==== Description
//# `SplayTree_Range` 是一種神乎其技的資料結構, 維護一堆 Key->Value. 並且支援
//# 一些 `std::map` 難以快速實踐的操作, 如 `split` , `merge` , `keyOffset`
//#
//#==== Template Class Operators Request
//#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
//#|=====================================================================
//#|Const?|Typename| Operator| Parameters | Return_Type| Description
//#|const |Key |operator+|(Key `k`) | Key | 相加
//#|const |Key |operator<|(Key `k`) | bool | 大小比較
//#| |Key |'Key' |(int `n`) | | 建構子, `n` 永遠是0
//#| |Value | 'Value' |( ) | | 建構子
//#|=====================================================================
//#
template<class Key, class Value>
class SplayTree_Range{
private:
struct Node{
Key _key;
Key _keyOffset;
Value _value;
Value _valueOffset;
Value _range;
bool _same;
size_t _size;
Node* _parent;
Node* _child[2];
//
Node(Key const& __key, Value const& __value);
//
void keyOffset (Key const& __delta);
void valueUpdate(Value const& __delta, bool __over);
void syncDown() const;
void syncUp () const;
};
//
Node* _root;
//
void connect(Node const* __parent, size_t __left_right,
Node const* __child) const;
Node const* splay (Node const* __node) const;
//
void clear(Node* __node);
Node* dup(Node* __node);
//
Node const* findKey (Node const* __node, Key const& __key ) const;
Node const* findMinMax(Node const* __node, bool __minimum) const;
Node const* findOrder (Node const* __node, size_t __order ) const;
//
void split(Node* __root, Node** __left, Node** __right);
Node* merge( Node* __left, Node* __right);
public:
//#==== Custom Type Definitions
//#
//# * `Element` -> 用來當作回傳資料的媒介
//# ** 重定義 `operator->()` 到 `std::pair<Key const&, Value&>*`
//# ** 重定義 `operator*()` 到 `std::pair<Key const&, Value&>&`
//# ** 有 `operator==` , `operator!=`, `operator=` 可用
//# ** 可以直接用 `(*e).second = some_value` 來改變SplayTree_Range中的資料
//#
class Element{
private:
typedef std::pair<Key const&, Value&> Entry;
Entry* _entry;
Node * _node;
//
void reset(Node* __node);
public:
Element();
Element(Node* __node);
Element(Element const& __iterator2);
~Element();
//
Element& operator=(Element const& __e2);
//
Entry* operator->();
Entry& operator *();
//
bool operator==(Element const& __e2) const;
bool operator!=(Element const& __e2) const;
};
//
SplayTree_Range();
SplayTree_Range(SplayTree_Range const& __tree2);
~SplayTree_Range();
SplayTree_Range& operator=(SplayTree_Range const& __tree2);
//
//#==== Support Methods
//#
//# * N <- `this` 中擁有的資料數
//# * M <- `tree2` 中擁有的資料數
//#
//#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"]
//#|=====================================================================
//#|Const?|Name | Parameters | Return_Type| Time_Complexity| Description
//#||moveTo|(SplayTree_Range* `tree2`)|void|O(M)
//#|將 `this` 的資料複寫到 `tree2` 上面, 同時清空自己,
//# 時間複雜度中的M是 `tree2` 所擁有的資料數
void moveTo(SplayTree_Range* __tree2);
//#|const|lowerBound|(Key const& `k`)|Element|O(logN)
//#|找出第一個(最小的) Element且 `k` <= 它的 Key, 並且回傳之.
//# 找不到的話回傳 `this->end()`
Element lowerBound(Key const& __key) const;
//#|const|lowerBound|(Key const& `k`)|Element|O(logN)
//#|找出第一個(最小的) Element且 `k` < 它的 Key, 並且回傳之.
//# 找不到的話回傳 `this->end()`
Element upperBound(Key const& __key) const;
//#|const|lowerBound|(Key const& `k`)|Element|O(logN)
//#|找出第一個(最小的) Element且 `k` >= 它的 Key, 並且回傳之.
//# 找不到的話回傳 `this->end()`
Element rLowerBound(Key const& __key) const;
//#|const|lowerBound|(Key const& `k`)|Element|O(logN)
//#|找出第一個(最小的) Element且 `k` > 它的 Key, 並且回傳之.
//# 找不到的話回傳 `this->end()`
Element rUpperBound(Key const& __key) const;
//#|const|find|(Key const& `k`)|Element|O(logN)
//#|找出 Key= `k` 的Elemenet 並回傳. 找不到的話回傳 `this->end()`
Element find(Key const& __key) const;
//#|const|query|()|Value|O(1)
//#|回傳整棵樹的區間Value
Value query() const;
//#|const|query|(Key const& `first` ,\Key const& `last`)|Value|O(logN)
//#|找出key介於 `first` \~ `last` 的區間Value
Value query(Key const& __first, Key const& __last) const;
//#|const|order|(size_t `ord`)|Element|O(logN)
//#|將Elements依照Key由小到大排序, 回傳第 `ord` 個Element (由0算起).
//# 其中如果 `ord` > N - 1, 則會回傳 `this->last()`
Element order(size_t __order) const;
//#|const|first|(size_t `ord`)|Element|O(logN)
//#|回傳Key最小的Element, 如果SplayTree_Range為空, 則回傳 `this->end()`
Element first() const;
//#|const|last|(size_t `ord`)|Element|O(logN)
//#|回傳Key最大的Element, 如果SplayTree_Range為空, 則回傳 `this->end()`
Element last() const;
//#|const|end|()|Element|O(1)
//#|回傳一個指向NULL的Element, 以供 `find` , `order` , `first`
//# , `last` 等判斷是否有找到相對應的Element
Element end() const;
//#|const|size|()|size_t|O(1)| 回傳資料數
size_t size() const;
//#|const|size|()|bool|O(1)| 回傳是否為空
bool empty() const;
//#||clear|()|void|O(N)| 清空資料
void clear();
//#||insert|(Key const& `key`,\Value const& `value`)|bool|O(logN)
//#|檢查是否已有Element的Key 為 `key`, 若有則回傳 `false` , 否則將
//# 一個 (Key -> Value) = (`key` -> `value`)的Element加入, 並回傳 `true`
//# 將所有Element的Key同加上 `delta`
bool insert(Key const& __key, Value const& __value);
//#||erase|(Key const& `key`)|bool|O(logN)
//#|檢查是否已有Element的Key 為 `key`, 若有則刪除之, 並回傳 `true`,
//# 否則則回傳 `false`
bool erase(Key const& __key);
//#||keyOffset|(Key const& `delta`)|void|O(1)
//#|將所有Element的Key同加上 `delta`
void keyOffset(Key const& __delta);
//#||valueOffset|(Value const& `delta`)|void|O(1)
//#|將所有Element的value同加上 `delta`
void valueOffset(Value const& __delta);
//#||valueOverride|(Value const& `vaule`)|void|O(1)
//#|將所有Element的value同變成 `value`
void valueOverride(Value const& __value);
//#||operator[]|(Key const& `key`)|Value&|O(logN)
//#|檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference
//# 否則先執行 `insert(key, Value())` 再回傳相對應的Reference
Value& operator[](Key const& __key);
//#||splitOut|(Key const& `upper_bound`,\SplayTree_Range* `tree2`)|void
//#|O(logN) + O(M)
//#|將 `tree2` 清空, 再將所有Key > `upper_bound` 的Element都丟到 `tree2`
void splitOut(Key const& __upper_bound, SplayTree_Range* __right);
//#||mergeAfter|(SplayTree_Range* `tree2`)|void|O(logN) + O(logM)
//#|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key, 是的話把 `tree2`
//# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
//# 回傳 `false`
bool mergeAfter(SplayTree_Range* __tree2);
//#||merge|(SplayTree_Range* `tree2`)|void|O(logN) + O(logM)
//#|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key 或者
//# 是否 `this` 中的 Key 都大於 `tree2` 中的Key, 是的話把 `tree2`
//# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
//# 回傳 `false`
bool merge(SplayTree_Range* __tree2);
//#|=====================================================================
};
//#
//#[NOTE]
//#========================================
//# * 假設現在有兩個SplayTree_Range `A` 和 `B`, 則:
//# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉
//# ** 執行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後
//# 如果檢查發現確實可以merge, 則之後 `B` 會變成空的
//#========================================
//#
//# '''
//#
}
#include "SplayTree_Range.hpp"
#endif // dsa_SplayTree_Range_h__
|
