Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : /**
8 : * A sorted tree with optimal access times, where recently-accessed elements
9 : * are faster to access again.
10 : */
11 :
12 : #ifndef mozilla_SplayTree_h
13 : #define mozilla_SplayTree_h
14 :
15 : #include "mozilla/Assertions.h"
16 : #include "mozilla/Attributes.h"
17 :
18 : namespace mozilla {
19 :
20 : template<class T, class C>
21 : class SplayTree;
22 :
23 : template<typename T>
24 : class SplayTreeNode
25 : {
26 : public:
27 : template<class A, class B>
28 : friend class SplayTree;
29 :
30 0 : SplayTreeNode()
31 : : mLeft(nullptr)
32 : , mRight(nullptr)
33 0 : , mParent(nullptr)
34 0 : {}
35 :
36 : private:
37 : T* mLeft;
38 : T* mRight;
39 : T* mParent;
40 : };
41 :
42 :
43 : /**
44 : * Class which represents a splay tree.
45 : * Splay trees are balanced binary search trees for which search, insert and
46 : * remove are all amortized O(log n), but where accessing a node makes it
47 : * faster to access that node in the future.
48 : *
49 : * T indicates the type of tree elements, Comparator must have a static
50 : * compare(const T&, const T&) method ordering the elements. The compare
51 : * method must be free from side effects.
52 : */
53 : template<typename T, class Comparator>
54 : class SplayTree
55 : {
56 : T* mRoot;
57 :
58 : public:
59 28 : constexpr SplayTree()
60 28 : : mRoot(nullptr)
61 28 : {}
62 :
63 155 : bool empty() const
64 : {
65 155 : return !mRoot;
66 : }
67 :
68 0 : T* find(const T& aValue)
69 : {
70 0 : if (empty()) {
71 0 : return nullptr;
72 : }
73 :
74 0 : T* last = lookup(aValue);
75 0 : splay(last);
76 0 : return Comparator::compare(aValue, *last) == 0 ? last : nullptr;
77 : }
78 :
79 0 : void insert(T* aValue)
80 : {
81 0 : MOZ_ASSERT(!find(*aValue), "Duplicate elements are not allowed.");
82 :
83 0 : if (!mRoot) {
84 0 : mRoot = aValue;
85 0 : return;
86 : }
87 0 : T* last = lookup(*aValue);
88 0 : int cmp = Comparator::compare(*aValue, *last);
89 :
90 0 : finishInsertion(last, cmp, aValue);
91 0 : return;
92 : }
93 :
94 : T* findOrInsert(const T& aValue);
95 :
96 0 : T* remove(const T& aValue)
97 : {
98 0 : T* last = lookup(aValue);
99 0 : MOZ_ASSERT(last, "This tree must contain the element being removed.");
100 0 : MOZ_ASSERT(Comparator::compare(aValue, *last) == 0);
101 :
102 : // Splay the tree so that the item to remove is the root.
103 0 : splay(last);
104 0 : MOZ_ASSERT(last == mRoot);
105 :
106 : // Find another node which can be swapped in for the root: either the
107 : // rightmost child of the root's left, or the leftmost child of the
108 : // root's right.
109 : T* swap;
110 : T* swapChild;
111 0 : if (mRoot->mLeft) {
112 0 : swap = mRoot->mLeft;
113 0 : while (swap->mRight) {
114 0 : swap = swap->mRight;
115 : }
116 0 : swapChild = swap->mLeft;
117 0 : } else if (mRoot->mRight) {
118 0 : swap = mRoot->mRight;
119 0 : while (swap->mLeft) {
120 0 : swap = swap->mLeft;
121 : }
122 0 : swapChild = swap->mRight;
123 : } else {
124 0 : T* result = mRoot;
125 0 : mRoot = nullptr;
126 0 : return result;
127 : }
128 :
129 : // The selected node has at most one child, in swapChild. Detach it
130 : // from the subtree by replacing it with that child.
131 0 : if (swap == swap->mParent->mLeft) {
132 0 : swap->mParent->mLeft = swapChild;
133 : } else {
134 0 : swap->mParent->mRight = swapChild;
135 : }
136 0 : if (swapChild) {
137 0 : swapChild->mParent = swap->mParent;
138 : }
139 :
140 : // Make the selected node the new root.
141 0 : mRoot = swap;
142 0 : mRoot->mParent = nullptr;
143 0 : mRoot->mLeft = last->mLeft;
144 0 : mRoot->mRight = last->mRight;
145 0 : if (mRoot->mLeft) {
146 0 : mRoot->mLeft->mParent = mRoot;
147 : }
148 0 : if (mRoot->mRight) {
149 0 : mRoot->mRight->mParent = mRoot;
150 : }
151 :
152 0 : return last;
153 : }
154 :
155 0 : T* removeMin()
156 : {
157 0 : MOZ_ASSERT(mRoot, "No min to remove!");
158 :
159 0 : T* min = mRoot;
160 0 : while (min->mLeft) {
161 0 : min = min->mLeft;
162 : }
163 0 : return remove(*min);
164 : }
165 :
166 : // For testing purposes only.
167 : void checkCoherency()
168 : {
169 : checkCoherency(mRoot, nullptr);
170 : }
171 :
172 : private:
173 : /**
174 : * Returns the node in this comparing equal to |aValue|, or a node just
175 : * greater or just less than |aValue| if there is no such node.
176 : */
177 0 : T* lookup(const T& aValue)
178 : {
179 0 : MOZ_ASSERT(!empty());
180 :
181 0 : T* node = mRoot;
182 : T* parent;
183 0 : do {
184 0 : parent = node;
185 0 : int c = Comparator::compare(aValue, *node);
186 0 : if (c == 0) {
187 0 : return node;
188 0 : } else if (c < 0) {
189 0 : node = node->mLeft;
190 : } else {
191 0 : node = node->mRight;
192 : }
193 : } while (node);
194 0 : return parent;
195 : }
196 :
197 0 : void finishInsertion(T* aLast, int32_t aCmp, T* aNew)
198 : {
199 0 : MOZ_ASSERT(aCmp, "Nodes shouldn't be equal!");
200 :
201 0 : T** parentPointer = (aCmp < 0) ? &aLast->mLeft : &aLast->mRight;
202 0 : MOZ_ASSERT(!*parentPointer);
203 0 : *parentPointer = aNew;
204 0 : aNew->mParent = aLast;
205 :
206 0 : splay(aNew);
207 0 : }
208 :
209 : /**
210 : * Rotate the tree until |node| is at the root of the tree. Performing
211 : * the rotations in this fashion preserves the amortized balancing of
212 : * the tree.
213 : */
214 0 : void splay(T* aNode)
215 : {
216 0 : MOZ_ASSERT(aNode);
217 :
218 0 : while (aNode != mRoot) {
219 0 : T* parent = aNode->mParent;
220 0 : if (parent == mRoot) {
221 : // Zig rotation.
222 0 : rotate(aNode);
223 0 : MOZ_ASSERT(aNode == mRoot);
224 0 : return;
225 : }
226 0 : T* grandparent = parent->mParent;
227 0 : if ((parent->mLeft == aNode) == (grandparent->mLeft == parent)) {
228 : // Zig-zig rotation.
229 0 : rotate(parent);
230 0 : rotate(aNode);
231 : } else {
232 : // Zig-zag rotation.
233 0 : rotate(aNode);
234 0 : rotate(aNode);
235 : }
236 : }
237 : }
238 :
239 0 : void rotate(T* aNode)
240 : {
241 : // Rearrange nodes so that aNode becomes the parent of its current
242 : // parent, while preserving the sortedness of the tree.
243 0 : T* parent = aNode->mParent;
244 0 : if (parent->mLeft == aNode) {
245 : // x y
246 : // y c ==> a x
247 : // a b b c
248 0 : parent->mLeft = aNode->mRight;
249 0 : if (aNode->mRight) {
250 0 : aNode->mRight->mParent = parent;
251 : }
252 0 : aNode->mRight = parent;
253 : } else {
254 0 : MOZ_ASSERT(parent->mRight == aNode);
255 : // x y
256 : // a y ==> x c
257 : // b c a b
258 0 : parent->mRight = aNode->mLeft;
259 0 : if (aNode->mLeft) {
260 0 : aNode->mLeft->mParent = parent;
261 : }
262 0 : aNode->mLeft = parent;
263 : }
264 0 : aNode->mParent = parent->mParent;
265 0 : parent->mParent = aNode;
266 0 : if (T* grandparent = aNode->mParent) {
267 0 : if (grandparent->mLeft == parent) {
268 0 : grandparent->mLeft = aNode;
269 : } else {
270 0 : grandparent->mRight = aNode;
271 : }
272 : } else {
273 0 : mRoot = aNode;
274 : }
275 0 : }
276 :
277 : T* checkCoherency(T* aNode, T* aMinimum)
278 : {
279 : if (mRoot) {
280 : MOZ_RELEASE_ASSERT(!mRoot->mParent);
281 : }
282 : if (!aNode) {
283 : MOZ_RELEASE_ASSERT(!mRoot);
284 : return nullptr;
285 : }
286 : if (!aNode->mParent) {
287 : MOZ_RELEASE_ASSERT(aNode == mRoot);
288 : }
289 : if (aMinimum) {
290 : MOZ_RELEASE_ASSERT(Comparator::compare(*aMinimum, *aNode) < 0);
291 : }
292 : if (aNode->mLeft) {
293 : MOZ_RELEASE_ASSERT(aNode->mLeft->mParent == aNode);
294 : T* leftMaximum = checkCoherency(aNode->mLeft, aMinimum);
295 : MOZ_RELEASE_ASSERT(Comparator::compare(*leftMaximum, *aNode) < 0);
296 : }
297 : if (aNode->mRight) {
298 : MOZ_RELEASE_ASSERT(aNode->mRight->mParent == aNode);
299 : return checkCoherency(aNode->mRight, aNode);
300 : }
301 : return aNode;
302 : }
303 :
304 : SplayTree(const SplayTree&) = delete;
305 : void operator=(const SplayTree&) = delete;
306 : };
307 :
308 : template<typename T, class Comparator>
309 : T*
310 : SplayTree<T, Comparator>::findOrInsert(const T& aValue)
311 : {
312 : if (!mRoot) {
313 : mRoot = new T(aValue);
314 : return mRoot;
315 : }
316 :
317 : T* last = lookup(aValue);
318 : int cmp = Comparator::compare(aValue, *last);
319 : if (!cmp) {
320 : return last;
321 : }
322 :
323 : T* t = new T(aValue);
324 : finishInsertion(last, cmp, t);
325 : return t;
326 : }
327 :
328 : } /* namespace mozilla */
329 :
330 : #endif /* mozilla_SplayTree_h */
|
