Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
splay_tree.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * thrill/common/splay_tree.hpp
3  *
4  * Part of Project Thrill - http://project-thrill.org
5  *
6  *
7  * All rights reserved. Published under the BSD-2 license in the LICENSE file.
8  ******************************************************************************/
9 
10 #pragma once
11 #ifndef THRILL_COMMON_SPLAY_TREE_HEADER
12 #define THRILL_COMMON_SPLAY_TREE_HEADER
13 
14 /*
15  Adapted as a Generic Data structure with Template C++ by AG
16 
17  An implementation of top-down splaying with sizes
18  D. Sleator <[email protected]>, January 1994.
19 
20  This extends top-down-splay.c to maintain a size field in each node. This is
21  the number of nodes in the subtree rooted there. This makes it possible to
22  efficiently compute the rank of a key. (The rank is the number of nodes to
23  the left of the given key.) It it also possible to quickly find the node of a
24  given rank. Both of these operations are illustrated in the code below. The
25  remainder of this introduction is taken from top-down-splay.c.
26 
27  "Splay trees", or "self-adjusting search trees" are a simple and efficient
28  data structure for storing an ordered set. The data structure consists of a
29  binary tree, with no additional fields. It allows searching, insertion,
30  deletion, deletemin, deletemax, splitting, joining, and many other operations,
31  all with amortized logarithmic performance. Since the trees adapt to the
32  sequence of requests, their performance on real access patterns is typically
33  even better. Splay trees are described in a number of texts and papers
34  [1,2,3,4].
35 
36  The code here is adapted from simple top-down splay, at the bottom of page 669
37  of [2]. It can be obtained via anonymous ftp from spade.pc.cs.cmu.edu in
38  directory /usr/sleator/public.
39 
40  The chief modification here is that the splay operation works even if the item
41  being splayed is not in the tree, and even if the tree root of the tree is
42  nullptr. So the line:
43 
44  t = splay(i, t);
45 
46  causes it to search for item with key i in the tree rooted at t. If it's
47  there, it is splayed to the root. If it isn't there, then the node put at the
48  root is the last one before nullptr that would have been reached in a normal
49  binary search for i. (It's a neighbor of i in the tree.) This allows many
50  other operations to be easily implemented, as shown below.
51 
52  [1] "Data Structures and Their Algorithms", Lewis and Denenberg,
53  Harper Collins, 1991, pp 243-251.
54  [2] "Self-adjusting Binary Search Trees" Sleator and Tarjan,
55  JACM Volume 32, No 3, July 1985, pp 652-686.
56  [3] "Data Structure and Algorithm Analysis", Mark Weiss,
57  Benjamin Cummins, 1992, pp 119-130.
58  [4] "Data Structures, Algorithms, and Performance", Derick Wood,
59  Addison-Wesley, 1993, pp 367-375
60 */
61 
62 #include <cassert>
63 #include <iostream>
64 
65 namespace thrill {
66 namespace common {
67 
68 /******************************************************************************/
69 // splay -- Free Splay Tree methods without tree sizes
70 
71 //! print the tree
72 template <typename Tree>
73 inline void splay_print(Tree* t, size_t d = 0) {
74  if (t == nullptr) return;
75  splay_print(t->right, d + 1);
76  for (size_t i = 0; i < d; i++) std::cout << " ";
77  std::cout << *t << std::endl;
78  splay_print(t->left, d + 1);
79 }
80 
81 //! check the tree order, recursively calculate min and max elements
82 template <typename Tree, typename Compare>
83 inline void splay_check(
84  const Tree* t,
85  const Tree*& out_tmin, const Tree*& out_tmax,
86  const Compare& cmp) {
87 
88  if (t == nullptr) return;
89 
90  const Tree* tmin = nullptr, * tmax = nullptr;
91  splay_check(t->left, out_tmin, tmax, cmp);
92  splay_check(t->right, tmin, out_tmax, cmp);
93 
94  if (tmax) assert(cmp(tmax, t));
95  if (tmin) assert(cmp(t, tmin));
96 }
97 
98 //! check the tree order
99 template <typename Tree, typename Compare>
100 inline void splay_check(const Tree* t, const Compare& cmp) {
101  if (t == nullptr) return;
102  const Tree* tmin = nullptr, * tmax = nullptr;
103  splay_check(t, tmin, tmax, cmp);
104 }
105 
106 //! Splay using the key i (which may or may not be in the tree.) The starting
107 //! root is t, and the tree used is defined by rat size fields are maintained.
108 template <typename Key, typename Tree, typename Compare>
109 inline Tree * splay(const Key& k, Tree* t, const Compare& cmp) {
110  Tree* N_left = nullptr, * N_right = nullptr;
111  Tree* l = nullptr, * r = nullptr;
112 
113  if (t == nullptr) return t;
114 
115  for ( ; ; ) {
116  if (cmp(k, t)) {
117  if (t->left == nullptr) break;
118 
119  if (cmp(k, t->left)) {
120  /* rotate right */
121  Tree* y = t->left;
122  t->left = y->right;
123  y->right = t;
124  t = y;
125  if (t->left == nullptr) break;
126  }
127  /* link right */
128  (r ? r->left : N_left) = t;
129  r = t;
130  t = t->left;
131  }
132  else if (cmp(t, k)) {
133  if (t->right == nullptr) break;
134 
135  if (cmp(t->right, k)) {
136  /* rotate left */
137  Tree* y = t->right;
138  t->right = y->left;
139  y->left = t;
140  t = y;
141  if (t->right == nullptr) break;
142  }
143  /* link left */
144  (l ? l->right : N_right) = t;
145  l = t;
146  t = t->right;
147  }
148  else {
149  break;
150  }
151  }
152 
153  (l ? l->right : N_right) = (r ? r->left : N_left) = nullptr;
154 
155  /* assemble */
156  (l ? l->right : N_right) = t->left;
157  (r ? r->left : N_left) = t->right;
158  t->left = N_right;
159  t->right = N_left;
160 
161  return t;
162 }
163 
164 //! Insert key i into the tree t, if it is not already there. Before calling
165 //! this method, one *MUST* call splay() to rotate the tree to the right
166 //! position. Return a pointer to the resulting tree.
167 template <typename Tree, typename Compare>
168 inline Tree * splay_insert(Tree* nn, Tree* t, const Compare& cmp) {
169  if (t == nullptr) {
170  nn->left = nn->right = nullptr;
171  }
172  else if (cmp(nn, t)) {
173  nn->left = t->left;
174  nn->right = t;
175  t->left = nullptr;
176  }
177  else {
178  nn->right = t->right;
179  nn->left = t;
180  t->right = nullptr;
181  }
182  return nn;
183 }
184 
185 //! Erases i from the tree if it's there. Return a pointer to the resulting
186 //! tree.
187 template <typename Key, typename Tree, typename Compare>
188 inline Tree * splay_erase(const Key& k, Tree*& t, const Compare& cmp) {
189  if (t == nullptr) return nullptr;
190  t = splay(k, t, cmp);
191  /* k == t->key ? */
192  if (!cmp(k, t) && !cmp(t, k)) {
193  /* found it */
194  Tree* r = t;
195  if (t->left == nullptr) {
196  t = t->right;
197  }
198  else {
199  Tree* x = splay(k, t->left, cmp);
200  x->right = t->right;
201  t = x;
202  }
203  return r;
204  }
205  else {
206  /* It wasn't there */
207  return nullptr;
208  }
209 }
210 
211 //! Erases i from the tree if it's there. Return a pointer to the resulting
212 //! tree.
213 template <typename Tree, typename Compare>
214 inline Tree * splay_erase_top(Tree*& t, const Compare& cmp) {
215  if (t == nullptr) return nullptr;
216  /* found it */
217  Tree* r = t;
218  if (t->left == nullptr) {
219  t = t->right;
220  }
221  else {
222  Tree* x = splay(r, t->left, cmp);
223  x->right = t->right;
224  t = x;
225  }
226  return r;
227 }
228 
229 //! traverse the tree in preorder
230 template <typename Tree, typename Functor>
231 inline void splay_traverse_preorder(const Functor& f, const Tree* t) {
232  if (t == nullptr) return;
233  splay_traverse_preorder(f, t->left);
234  f(*t);
235  splay_traverse_preorder(f, t->right);
236 }
237 
238 /******************************************************************************/
239 // splayz -- Free Splay Tree methods with tree sizes
240 
241 template <typename Tree>
242 inline size_t splayz_size(Tree* x) {
243  return (x == nullptr) ? 0 : x->size;
244 }
245 
246 //! print the tree
247 template <typename Tree>
248 inline void splayz_print(Tree* t, size_t d = 0) {
249  if (t == nullptr) return;
250  splayz_print(t->right, d + 1);
251  for (size_t i = 0; i < d; i++) std::cout << " ";
252  std::cout << *t << std::endl;
253  splayz_print(t->left, d + 1);
254 }
255 
256 //! check the tree order, recursively calculate min and max elements
257 template <typename Tree, typename Compare>
258 inline void splayz_check(
259  const Tree* t,
260  const Tree*& out_tmin, const Tree*& out_tmax, size_t& out_size,
261  const Compare& cmp) {
262 
263  if (t == nullptr) return;
264 
265  const Tree* tmin = nullptr, * tmax = nullptr;
266  size_t left_size = 0, right_size = 0;
267  splayz_check(t->left, out_tmin, tmax, left_size, cmp);
268  splayz_check(t->right, tmin, out_tmax, right_size, cmp);
269 
270  if (tmax) assert(cmp(tmax, t));
271  if (tmin) assert(cmp(t, tmin));
272  assert(t->size == left_size + 1 + right_size);
273  out_size = t->size;
274 }
275 
276 //! check the tree order
277 template <typename Tree, typename Compare>
278 inline void splayz_check(const Tree* t, const Compare& cmp) {
279  if (t == nullptr) return;
280  const Tree* tmin = nullptr, * tmax = nullptr;
281  size_t size = 0;
282  splayz_check(t, tmin, tmax, size, cmp);
283 }
284 
285 //! Splay using the key i (which may or may not be in the tree.) The starting
286 //! root is t, and the tree used is defined by rat size fields are maintained.
287 template <typename Key, typename Tree, typename Compare>
288 inline Tree * splayz(const Key& k, Tree* t, const Compare& cmp) {
289  Tree* N_left = nullptr, * N_right = nullptr;
290  Tree* l = nullptr, * r = nullptr;
291  size_t l_size = 0, r_size = 0;
292 
293  if (t == nullptr) return t;
294 
295  for ( ; ; ) {
296  if (cmp(k, t)) {
297  if (t->left == nullptr) break;
298 
299  if (cmp(k, t->left)) {
300  /* rotate right */
301  Tree* y = t->left;
302  t->left = y->right;
303  y->right = t;
304  t->size = splayz_size(t->left) + splayz_size(t->right) + 1;
305  t = y;
306  if (t->left == nullptr) break;
307  }
308  /* link right */
309  (r ? r->left : N_left) = t;
310  r = t;
311  t = t->left;
312  r_size += 1 + splayz_size(r->right);
313  }
314  else if (cmp(t, k)) {
315  if (t->right == nullptr) break;
316 
317  if (cmp(t->right, k)) {
318  /* rotate left */
319  Tree* y = t->right;
320  t->right = y->left;
321  y->left = t;
322  t->size = splayz_size(t->left) + splayz_size(t->right) + 1;
323  t = y;
324  if (t->right == nullptr) break;
325  }
326  /* link left */
327  (l ? l->right : N_right) = t;
328  l = t;
329  t = t->right;
330  l_size += 1 + splayz_size(l->left);
331  }
332  else {
333  break;
334  }
335  }
336 
337  // Now l_size and r_size are the sizes of the left and right trees we just
338  // built.
339  l_size += splayz_size(t->left);
340  r_size += splayz_size(t->right);
341  t->size = l_size + r_size + 1;
342 
343  (l ? l->right : N_right) = (r ? r->left : N_left) = nullptr;
344 
345  /* The following two loops correct the size fields of the right path */
346  /* from the left child of the root and the right path from the left */
347  /* child of the root. */
348  for (Tree* y = N_right; y != nullptr; y = y->right) {
349  y->size = l_size;
350  l_size -= 1 + splayz_size(y->left);
351  }
352  for (Tree* y = N_left; y != nullptr; y = y->left) {
353  y->size = r_size;
354  r_size -= 1 + splayz_size(y->right);
355  }
356 
357  /* assemble */
358  (l ? l->right : N_right) = t->left;
359  (r ? r->left : N_left) = t->right;
360  t->left = N_right;
361  t->right = N_left;
362 
363  return t;
364 }
365 
366 //! Insert key i into the tree t, if it is not already there. Before calling
367 //! this method, one *MUST* call splayz() to rotate the tree to the right
368 //! position. Return a pointer to the resulting tree.
369 template <typename Tree, typename Compare>
370 inline Tree * splayz_insert(Tree* nn, Tree* t, const Compare& cmp) {
371  if (t == nullptr) {
372  nn->left = nn->right = nullptr;
373  }
374  else if (cmp(nn, t)) {
375  nn->left = t->left;
376  nn->right = t;
377  t->left = nullptr;
378  t->size = 1 + splayz_size(t->right);
379  }
380  else {
381  nn->right = t->right;
382  nn->left = t;
383  t->right = nullptr;
384  t->size = 1 + splayz_size(t->left);
385  }
386  nn->size = 1 + splayz_size(nn->left) + splayz_size(nn->right);
387  return nn;
388 }
389 
390 //! Erases i from the tree if it's there. Return a pointer to the resulting
391 //! tree.
392 template <typename Key, typename Tree, typename Compare>
393 inline Tree * splayz_erase(const Key& k, Tree*& t, const Compare& cmp) {
394  if (t == nullptr) return nullptr;
395  size_t tsize = t->size;
396  t = splayz(k, t, cmp);
397  /* k == t->key ? */
398  if (!cmp(k, t) && !cmp(t, k)) {
399  /* found it */
400  Tree* r = t;
401  if (t->left == nullptr) {
402  t = t->right;
403  }
404  else {
405  Tree* x = splayz(k, t->left, cmp);
406  x->right = t->right;
407  t = x;
408  }
409  if (t != nullptr) {
410  t->size = tsize - 1;
411  }
412  return r;
413  }
414  else {
415  /* It wasn't there */
416  return nullptr;
417  }
418 }
419 
420 //! Erases i from the tree if it's there. Return a pointer to the resulting
421 //! tree.
422 template <typename Tree, typename Compare>
423 inline Tree * splayz_erase_top(Tree*& t, const Compare& cmp) {
424  if (t == nullptr) return nullptr;
425  size_t tsize = t->size;
426  /* found it */
427  Tree* r = t;
428  if (t->left == nullptr) {
429  t = t->right;
430  }
431  else {
432  Tree* x = splayz(r, t->left, cmp);
433  x->right = t->right;
434  t = x;
435  }
436  if (t != nullptr) {
437  t->size = tsize - 1;
438  }
439  return r;
440 }
441 
442 //! Returns a pointer to the node in the tree with the given rank. Returns
443 //! nullptr if there is no such node. Does not change the tree. To guarantee
444 //! logarithmic behavior, the node found here should be splayed to the root.
445 template <typename Tree>
446 inline Tree * splayz_rank(size_t r, Tree* t) {
447  size_t lsize;
448  if (r >= splayz_size(t)) return nullptr;
449  for ( ; ; ) {
450  lsize = splayz_size(t->left);
451  if (r < lsize) {
452  t = t->left;
453  }
454  else if (r > lsize) {
455  r = r - lsize - 1;
456  t = t->right;
457  }
458  else {
459  return t;
460  }
461  }
462 }
463 
464 //! traverse the tree in preorder
465 template <typename Tree, typename Functor>
466 inline void splayz_traverse_preorder(const Functor& f, const Tree* t) {
467  if (t == nullptr) return;
468  splayz_traverse_preorder(f, t->left);
469  f(*t);
470  splayz_traverse_preorder(f, t->right);
471 }
472 
473 /******************************************************************************/
474 // Splay Tree with tree sizes
475 
476 template <typename Key>
478 {
479 public:
480  struct Node {
481  Node * left = nullptr, * right = nullptr;
482  /* maintained to be the number of nodes rooted here */
483  size_t size;
484  Key key;
485  explicit Node(const Key& k) : key(k) { }
486  Node() = default;
487  };
488 
489  struct NodeCompare {
490  bool operator () (const Node* n, const Key& k) const {
491  return n->key < k;
492  }
493  bool operator () (const Key& k, const Node* n) const {
494  return k < n->key;
495  }
496  bool operator () (const Node* a, const Node* b) const {
497  return a->key < b->key;
498  }
499  };
500 
501  Node* root_ = nullptr;
502 
503  //! insert key into tree if it does not exist, returns true if inserted.
504  bool insert(const Key& k) {
505  NodeCompare cmp;
506  if (root_ != nullptr) {
507  root_ = splayz(k, root_, cmp);
508  /* k == t->key ? */
509  if (!cmp(k, root_) && !cmp(root_, k)) {
510  /* it's already there */
511  return false;
512  }
513  }
514  Node* nn = new Node(k);
515  root_ = splayz_insert(nn, root_, cmp);
516  return true;
517  }
518 
519  bool erase(const Key& k) {
520  Node* out = splayz_erase(k, root_, NodeCompare());
521  if (!out) return false;
522  delete out;
523  return true;
524  }
525 
526  bool exists(const Key& k) {
527  root_ = splayz(k, root_, NodeCompare());
528  return root_->key == k;
529  }
530 
531  const Node * rank(size_t i) const {
532  return splayz_rank(i, root_);
533  }
534 
535  Node * find(const Key& k) {
536  return (root_ = splayz(k, root_, NodeCompare()));
537  }
538 
539  template <typename Functor>
540  void traverse_preorder(const Functor& f) const {
541  splayz_traverse_preorder([&f](const Node& n) { f(n.key); }, root_);
542  }
543 };
544 
545 } // namespace common
546 } // namespace thrill
547 
548 #endif // !THRILL_COMMON_SPLAY_TREE_HEADER
549 
550 /******************************************************************************/
bool operator()(const Node *n, const Key &k) const
Definition: splay_tree.hpp:490
size_t splayz_size(Tree *x)
Definition: splay_tree.hpp:242
Tree * splay_insert(Tree *nn, Tree *t, const Compare &cmp)
Definition: splay_tree.hpp:168
void splay_print(Tree *t, size_t d=0)
print the tree
Definition: splay_tree.hpp:73
const Node * rank(size_t i) const
Definition: splay_tree.hpp:531
void splayz_traverse_preorder(const Functor &f, const Tree *t)
traverse the tree in preorder
Definition: splay_tree.hpp:466
size_t Node
Definition: triangles.hpp:20
Tree * splay_erase(const Key &k, Tree *&t, const Compare &cmp)
Definition: splay_tree.hpp:188
bool exists(const Key &k)
Definition: splay_tree.hpp:526
bool erase(const Key &k)
Definition: splay_tree.hpp:519
Tree * splayz_rank(size_t r, Tree *t)
Definition: splay_tree.hpp:446
Node * find(const Key &k)
Definition: splay_tree.hpp:535
list x
Definition: gen_data.py:39
void splay_traverse_preorder(const Functor &f, const Tree *t)
traverse the tree in preorder
Definition: splay_tree.hpp:231
bool insert(const Key &k)
insert key into tree if it does not exist, returns true if inserted.
Definition: splay_tree.hpp:504
void splayz_check(const Tree *t, const Tree *&out_tmin, const Tree *&out_tmax, size_t &out_size, const Compare &cmp)
check the tree order, recursively calculate min and max elements
Definition: splay_tree.hpp:258
Tree * splay(const Key &k, Tree *t, const Compare &cmp)
Definition: splay_tree.hpp:109
Tree * splayz_erase_top(Tree *&t, const Compare &cmp)
Definition: splay_tree.hpp:423
Tree * splayz_insert(Tree *nn, Tree *t, const Compare &cmp)
Definition: splay_tree.hpp:370
Tree * splay_erase_top(Tree *&t, const Compare &cmp)
Definition: splay_tree.hpp:214
void splayz_print(Tree *t, size_t d=0)
print the tree
Definition: splay_tree.hpp:248
void splay_check(const Tree *t, const Tree *&out_tmin, const Tree *&out_tmax, const Compare &cmp)
check the tree order, recursively calculate min and max elements
Definition: splay_tree.hpp:83
Tree * splayz_erase(const Key &k, Tree *&t, const Compare &cmp)
Definition: splay_tree.hpp:393
void traverse_preorder(const Functor &f) const
Definition: splay_tree.hpp:540
Tree * splayz(const Key &k, Tree *t, const Compare &cmp)
Definition: splay_tree.hpp:288