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/. */
8 * A sorted tree with optimal access times, where recently-accessed elements
9 * are faster to access again.
12 #ifndef mozilla_SplayTree_h
13 #define mozilla_SplayTree_h
15 #include "mozilla/Assertions.h"
19 template<class T
, class C
>
26 template<class A
, class B
>
27 friend class SplayTree
;
43 * Class which represents a splay tree.
44 * Splay trees are balanced binary search trees for which search, insert and
45 * remove are all amortized O(log n), but where accessing a node makes it
46 * faster to access that node in the future.
48 * T indicates the type of tree elements, Comparator must have a static
49 * compare(const T&, const T&) method ordering the elements. The compare
50 * method must be free from side effects.
52 template<typename T
, class Comparator
>
67 T
* find(const T
& aValue
)
73 T
* last
= lookup(aValue
);
75 return Comparator::compare(aValue
, *last
) == 0 ? last
: nullptr;
78 bool insert(T
* aValue
)
80 MOZ_ASSERT(!find(*aValue
), "Duplicate elements are not allowed.");
86 T
* last
= lookup(*aValue
);
87 int cmp
= Comparator::compare(*aValue
, *last
);
89 T
** parentPointer
= (cmp
< 0) ? &last
->mLeft
: &last
->mRight
;
90 MOZ_ASSERT(!*parentPointer
);
91 *parentPointer
= aValue
;
92 aValue
->mParent
= last
;
98 T
* remove(const T
& aValue
)
100 T
* last
= lookup(aValue
);
101 MOZ_ASSERT(last
, "This tree must contain the element being removed.");
102 MOZ_ASSERT(Comparator::compare(aValue
, *last
) == 0);
104 // Splay the tree so that the item to remove is the root.
106 MOZ_ASSERT(last
== mRoot
);
108 // Find another node which can be swapped in for the root: either the
109 // rightmost child of the root's left, or the leftmost child of the
115 while (swap
->mRight
) {
118 swapChild
= swap
->mLeft
;
119 } else if (mRoot
->mRight
) {
120 swap
= mRoot
->mRight
;
121 while (swap
->mLeft
) {
124 swapChild
= swap
->mRight
;
131 // The selected node has at most one child, in swapChild. Detach it
132 // from the subtree by replacing it with that child.
133 if (swap
== swap
->mParent
->mLeft
) {
134 swap
->mParent
->mLeft
= swapChild
;
136 swap
->mParent
->mRight
= swapChild
;
139 swapChild
->mParent
= swap
->mParent
;
142 // Make the selected node the new root.
144 mRoot
->mParent
= nullptr;
145 mRoot
->mLeft
= last
->mLeft
;
146 mRoot
->mRight
= last
->mRight
;
148 mRoot
->mLeft
->mParent
= mRoot
;
151 mRoot
->mRight
->mParent
= mRoot
;
159 MOZ_ASSERT(mRoot
, "No min to remove!");
168 // For testing purposes only.
169 void checkCoherency()
171 checkCoherency(mRoot
, nullptr);
176 * Returns the node in this comparing equal to |aValue|, or a node just
177 * greater or just less than |aValue| if there is no such node.
179 T
* lookup(const T
& aValue
)
181 MOZ_ASSERT(!empty());
187 int c
= Comparator::compare(aValue
, *node
);
200 * Rotate the tree until |node| is at the root of the tree. Performing
201 * the rotations in this fashion preserves the amortized balancing of
208 while (aNode
!= mRoot
) {
209 T
* parent
= aNode
->mParent
;
210 if (parent
== mRoot
) {
213 MOZ_ASSERT(aNode
== mRoot
);
216 T
* grandparent
= parent
->mParent
;
217 if ((parent
->mLeft
== aNode
) == (grandparent
->mLeft
== parent
)) {
229 void rotate(T
* aNode
)
231 // Rearrange nodes so that aNode becomes the parent of its current
232 // parent, while preserving the sortedness of the tree.
233 T
* parent
= aNode
->mParent
;
234 if (parent
->mLeft
== aNode
) {
238 parent
->mLeft
= aNode
->mRight
;
240 aNode
->mRight
->mParent
= parent
;
242 aNode
->mRight
= parent
;
244 MOZ_ASSERT(parent
->mRight
== aNode
);
248 parent
->mRight
= aNode
->mLeft
;
250 aNode
->mLeft
->mParent
= parent
;
252 aNode
->mLeft
= parent
;
254 aNode
->mParent
= parent
->mParent
;
255 parent
->mParent
= aNode
;
256 if (T
* grandparent
= aNode
->mParent
) {
257 if (grandparent
->mLeft
== parent
) {
258 grandparent
->mLeft
= aNode
;
260 grandparent
->mRight
= aNode
;
267 T
* checkCoherency(T
* aNode
, T
* aMinimum
)
270 MOZ_RELEASE_ASSERT(!mRoot
->mParent
);
273 MOZ_RELEASE_ASSERT(!mRoot
);
276 if (!aNode
->mParent
) {
277 MOZ_RELEASE_ASSERT(aNode
== mRoot
);
280 MOZ_RELEASE_ASSERT(Comparator::compare(*aMinimum
, *aNode
) < 0);
283 MOZ_RELEASE_ASSERT(aNode
->mLeft
->mParent
== aNode
);
284 T
* leftMaximum
= checkCoherency(aNode
->mLeft
, aMinimum
);
285 MOZ_RELEASE_ASSERT(Comparator::compare(*leftMaximum
, *aNode
) < 0);
288 MOZ_RELEASE_ASSERT(aNode
->mRight
->mParent
== aNode
);
289 return checkCoherency(aNode
->mRight
, aNode
);
294 SplayTree(const SplayTree
&) = delete;
295 void operator=(const SplayTree
&) = delete;
298 } /* namespace mozilla */
300 #endif /* mozilla_SplayTree_h */