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
|
#ifndef SplayTree_h__
#define SplayTree_h__
#include "utility.h"
namespace meow{
template<class Key, class Value>
class SplayTree{
private:
struct Node{
Key _key;
Key _keyOffset;
Value _value;
size_t _size;
Node* _parent;
Node* _lChild;
Node* _rChild;
//
Node(Key const& __key, Value const& __value);
};
//
Node* _root;
//
void offsetAdd (Node* __node, Key const& __delta) const;
void offsetDown (Node* __node ) const;
void sizeUpdate (Node* __node ) const;
void connectLChild(Node* __parent, Node* __child ) const;
void connectRChild(Node* __parent, Node* __child ) const;
Node const* setRoot(Node* __node) const;
//
Node* clear (Node* __node);
Node* dup (Node* __node);
//
void rotate( Node* __parent, Node* __child) const;
void rotate(Node* __grand, Node* __parent, Node* __child) const;
Node* splay(Node* __node) const;
//
Node* findKey (Node* __node, Key const& __key) const;
Node* findMinMax(Node* __node, bool minimum ) const;
Node* findOrder (Node* __node, size_t __order ) const;
//
void split(Node* __root, Node** __left, Node** __right);
Node* merge( Node* __left, Node* __right);
//
void print(Node* __now, int __depth) const;
public:
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();
SplayTree(SplayTree const& __tree2);
~SplayTree();
//
SplayTree& operator=(SplayTree const& __tree2);
void moveTo(SplayTree* __tree2);
//
Element lowerBound(Key const& __key) const;
Element upperBound(Key const& __key) const;
Element rLowerBound(Key const& __key) const;
Element rUpperBound(Key const& __key) const;
Element find (Key const& __key) const;
Element order(size_t __order ) const;
Element first( ) const;
Element last ( ) const;
Element end( ) const;
//
size_t size() const;
bool empty() const;
//
void clear();
void keyOffset(Key const& __delta);
bool insert (Key const& __key, Value const& __value);
bool erase (Key const& __key);
Value& operator[](Key const& __key);
void splitOut(Key const& __upper_bound, SplayTree* __right);
bool mergeAfter(SplayTree* __tree2);
bool merge (SplayTree* __tree2);
//
void print() const;
};
/*********************************************************
@asciidoc
=== meow:: *SplayTree<Key, Value>* (C++ class)
.Description
Like `std::map`, `SplayTree` is an dictionary(key->value). But it has
some extra method, such as `split()`, `merge()`, `keyOffset()`.
.Data Type
* `Key` is the tyepname of the key
* `Value` is the typename of value
* `SplayTree<Key, Value>:: *Element* ` is a typename which contain
(key->value). It has some methods below:
** `->first ` a constant reference to `Key`
** `->second` a reference to `Value`
** `operator==, operator!=` compare function, check if the two `Element`
is pointer to the same (key->value)
.Template Request
* `Key` should has `operator<`, `operator+`
.Support Methods
* N <- numbers of element in the SplayTree
* M <- numbers of element in another SplayTree
[options="header",width="100%",cols="1>,1<s,5<,1<,3^,10<",grid="rows"]
|=======================================================================
|Const?|Name| Parameters| Return Type| Time Complexity| Description
||operator=|(SplayTree const&)| *this | O(N) | copy operator
||moveTo|(SplayTree* t)|void|O(M)| Transform the data in this to `t`
|const|lowerBound|(Key k)|Element|O(logN)| Find the smallest (key->value)
which `k <= key` and return
|const|upperBound|(Key k)|Element|O(logN)| Find the smallest (key->value)
which `k < key` and return
|const|rLowerBound|(Key k)|Element|O(logN)| Find the largest (key->value)
which `key <= k` and return
|const|rUpperBound|(Key k)|Element|O(logN)| Find the largest (key->value)
which `key < k` and return
|const| find|(Key k)|Element|O(logN)| Find the element (key->value) which
`key == k` and return
|const|order|(size_t k)|Element|O(logN)| Find the `k`-th small element.
note that `k` start from zero like a normal C/C++ array.
|const|first|()|Element|O(logN)| Return the smallest element
|const|last|()|Element|O(logN)| Return the largest element
|const|end|()|Element|O(1)|Return an empty element(it can be use to
check if `find()` is successful)
|const|size|()|size_t|O(1)| Return number of elements in the tree
|const|empty|()|bool|O(1)|Return whether the tree is empty
||clear|()|void|O(N)|Clear
||keyOffset|(Key offset)|void|O(1)| Let all the keys in the tree
plus offset
||insert|(Key k, Value v)|bool | O(logN)| Insert an element.
If the tree already has an element with same key, return `false`.
||erase|(Key k)|bool | O(logN)|Erase an element from the tree with
given key. Return `false` if the element not found.
||operator[]|(Key k)|Value|O(logN)|Like `find()` , but it will insert an element
automatic if the corrosponding element not found
||splitOut|(Key const& upper_bound, +
SplayTree* out)|void | O(log N) | Split out all the elements with key
larger than `upper_bound` and store then into `out`
||mergeAfter|(SplayTree* t)|bool|O(logN + logM)|If not all of the elements in this
are smaller than elements in `t`, return `false` , else merge `t` into
itself and return `true`.
||merge|(SplayTree* t)|bool|O(logN + logM)|If all of the elements in this
are smaller than elements in `t` or all of the elements in this larger than
elements in `t` , merge `t` into itself and return `true`.
Else return `false`
|=======================================================================
WARNING: Consider there are two SplayTree `A` and `B`. +
`B` will become empty after you call `A.mergeAfter(&B)`
or `A.merge(&B)` successful. +
The data in `B` will override by data in `A` and `A` will become empty after
you call `A.moveTo(&B)`
'''
@asciidoc-
*********************************************************/
}
#include "SplayTree.hpp"
#endif // SplayTree_h__
|
