All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
splay_tree.hpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Piotr Wygocki
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
15 #ifndef PAAL_SPLAY_TREE_HPP
16 #define PAAL_SPLAY_TREE_HPP
17 
18 #include <boost/utility.hpp>
19 #include <boost/iterator.hpp>
20 #include <boost/iterator/iterator_facade.hpp>
21 
22 #include <algorithm>
23 #include <cassert>
24 #include <cstddef>
25 #include <memory>
26 #include <unordered_map>
27 
28 namespace paal {
29 namespace data_structures {
30 
31 template <typename T> class splay_tree;
32 
33 namespace detail {
38 template <typename NPtr> std::size_t node_size(const NPtr &node) {
39  return !node ? 0 : node->size();
40 }
41 
42 template <typename V> class Node;
43 
52 template <typename V>
53 std::unique_ptr<Node<V>> copy_node(std::unique_ptr<Node<V>> const &node) {
54  // TODO on c++14 change to make_unique
55  return (!node) ? nullptr : std::unique_ptr<Node<V>>(new Node<V>(*node));
56 }
57 
58 class forward_tag {};
59 class reversed_tag {};
60 
61 inline reversed_tag other(forward_tag) {
62  return reversed_tag{};
63 }
64 
65 inline forward_tag other(reversed_tag) {
66  return forward_tag{};
67 }
68 
69 
79 template <typename V> class Node {
80  public:
81  using value_type = V;
82  using node_type = Node<value_type>;
83  using node_ptr = std::unique_ptr<node_type>;
84 
86  explicit Node(const value_type &val)
87  : val_(val), parent_(nullptr), reversed_(false), size_(1) {}
88 
90  Node(const Node &n)
91  : val_(n.val_), left_(copy_node(n.left_)), right_(copy_node(n.right_)),
92  parent_(nullptr), reversed_(n.reversed_), size_(n.size_) {
93  if (right_) {
94  right_->parent_ = this;
95  }
96  if (left_) {
97  left_->parent_ = this;
98  }
99  }
100 
102  node_type *parent() { return parent_; }
103 
104  void set_parent(node_type *p) { parent_ = p; }
105 
107  void make_root() { parent_ = nullptr; }
108 
110  node_ptr &left() {
111  normalize();
112  return left_;
113  }
114 
119  void set_left(node_ptr node) {
120  set(std::move(node), reversed_tag{});
121  }
122 
124  node_ptr &right() {
125  normalize();
126  return right_;
127  }
128 
129  void set_right(node_ptr node) {
130  set(std::move(node), forward_tag{});
131  }
132 
137  template <typename Direction> void set(node_ptr node, Direction dir_tag) {
138  normalize();
139  set_internal(std::move(node), dir_tag);
140  update_size();
141  }
142 
147  template <typename Direction>
148  void set_internal(node_ptr node, Direction dir_tag) {
149  if (node != nullptr) {
150  node->parent_ = this;
151  }
152  child(dir_tag) = std::move(node);
153  }
154 
156  void update_size() { size_ = 1 + node_size(left_) + node_size(right_); }
157 
158  node_ptr &child(reversed_tag) { return left(); }
159 
160  node_ptr &child(forward_tag) { return right(); }
161 
162  template <typename Direction> node_type *extreme(Direction dir_tag) {
163  node_type *node = this;
164  normalize();
165  while (node->child(dir_tag).get() != nullptr) {
166  node = node->child(dir_tag).get();
167  node->normalize();
168  }
169  return node;
170  }
171 
172 
175  template <typename Direction> node_type *advance(Direction dir_tag) {
176  node_type *node = child(dir_tag).get();
177  if (node != nullptr) {
178  return node->extreme(other(dir_tag));
179  } else {
180  node_type *last = nullptr;
181  node = this;
182  while (true) {
183  last = node;
184  node = node->parent();
185  if (node == nullptr) {
186  return nullptr;
187  } else if (node->child(other(dir_tag)).get() == last) {
188  return node;
189  }
190  }
191  }
192  }
193 
194 
198  return advance(forward_tag{});
199  }
200 
203  return advance(reversed_tag{});
204  }
205 
207  std::size_t size() { return size_; }
208 
210  void subtree_reverse() { reversed_ ^= 1; }
211 
213  void normalize() {
214  if (reversed_) {
215  std::swap(left_, right_);
216  if (left_ != nullptr) {
217  left_->subtree_reverse();
218  }
219  if (right_ != nullptr) {
220  right_->subtree_reverse();
221  }
222  reversed_ = false;
223  }
224  }
225 
228  node_type *node = parent();
229  if (node != nullptr) {
230  node->normalize_root_path();
231  }
232  normalize();
233  }
234 
236  value_type val_;
237 
238  private:
239  static const bool k_def_left = 0;
240  node_ptr left_, right_;
241  node_type *parent_;
242  bool reversed_;
243  std::size_t size_;
244 };
245 
246 
252 template <typename V, typename direction_tag = forward_tag>
253 class Iterator
254  : public boost::iterator_facade<Iterator<V, direction_tag>, Node<V> *,
255  boost::bidirectional_traversal_tag, V &> {
256  using ST = splay_tree<V>;
257  using node_ptr = Node<V> *;
258 
259  public:
260  using value_type = V;
261  using node_type = Node<value_type>;
262 
264  Iterator() : current_(nullptr), rotation_cnt_(0), splay_(nullptr) {}
265 
271  explicit Iterator(node_ptr node, const ST *splay)
272  : current_(node), rotation_cnt_(0), splay_(splay) {}
273 
278  Iterator(const Iterator &other)
279  : current_(other.current_), rotation_cnt_(0), splay_(other.splay_) {}
280 
281  private:
282  friend class boost::iterator_core_access;
283  friend class splay_tree<V>;
284 
285  void normalize() {
286  if (rotation_cnt_ != splay_->get_rotation_cnt()) {
287  current_->normalize_root_path();
288  rotation_cnt_ = splay_->get_rotation_cnt();
289  }
290  }
291 
293  void increment() {
294  normalize();
295  current_ = current_->advance(direction_tag{});
296  }
297 
299  void decrement() {
300  normalize();
301  current_ = current_->advance(other(direction_tag{}));
302  }
303 
308  bool equal(const Iterator &other) const {
309  return this->current_ == other.current_;
310  }
311 
313  value_type &dereference() const { return current_->val_; }
314 
316  node_ptr current_;
317  std::size_t rotation_cnt_;
318  const ST *splay_;
319 };
320 
321 }
322 
331 template <typename T> class splay_tree {
332  detail::forward_tag forward_tag;
333  detail::reversed_tag reversed_tag;
334 
335  public:
336  using value_type = T;
337  using node_type = detail::Node<value_type>;
338  using node_ptr = typename node_type::node_ptr;
339  using iterator = detail::Iterator<value_type, detail::forward_tag>;
340  using const_iterator = const iterator;
341  using reverse_iterator = detail::Iterator<value_type, detail::reversed_tag>;
342  using const_reverse_iterator = const reverse_iterator;
343 
344  splay_tree() = default;
345 
351  template <typename I> splay_tree(const I b, const I e) {
352  root_ = build_tree(b, e);
353  }
354 
356  splay_tree(splay_tree &&splay) = default;
357 
359  splay_tree &operator=(splay_tree &&splay) = default;
360  // splay.rotation_cnt_ is not 0 after this move but it doesn't matter;
361 
364  if (&splay == this) return *this;
365  splay_tree sp(splay);
366  *this = std::move(sp);
367  return *this;
368  }
369 
371  splay_tree(const splay_tree &splay) : root_(copy_node(splay.root_)) {
372  auto i = begin();
373  auto e = end();
374  for (; i != e; ++i) {
375  t_to_node_.insert(std::make_pair(*i, i.current_));
376  }
377  }
378 
383  template <typename A> explicit splay_tree(const A &array) {
384  root_ = build_tree(std::begin(array), std::end(array));
385  }
386 
388  iterator begin() const {
389  return (root_ == nullptr)
390  ? end()
391  : iterator(root_->extreme(reversed_tag), this);
392  }
393 
395  iterator end() const { return iterator(); }
396 
399  return (root_ == nullptr)
400  ? rend()
401  : reverse_iterator(root_->extreme(forward_tag), this);
402  }
403 
406 
408  std::size_t size() const { return (root_ == nullptr) ? 0 : root_->size(); }
409 
411  bool empty() { return (root_ == nullptr); }
412 
414  value_type &operator[](std::size_t i) const { return find(i)->val_; }
415 
417  std::size_t get_idx(const T &t) const {
418  node_type *node = t_to_node_.at(t);
419  if (node == nullptr) {
420  return -1;
421  }
422  node->normalize_root_path();
423 
424  std::size_t i = node_size(node->left());
425  while (node != root_.get()) {
426  if (node->parent()->left().get() == node) {
427  node = node->parent();
428  } else {
429  node = node->parent();
430  i += node_size(node->left()) + 1;
431  }
432  }
433  return i;
434  }
435 
441  std::size_t get_rotation_cnt() const { return rotation_cnt_; }
442 
447  iterator splay(std::size_t i) const {
448  splay_internal(find(i));
449  return iterator(root_.get(), this);
450  }
451 
457  splay_tree split_higher(std::size_t i) { return split(i, forward_tag); }
458 
464  splay_tree split_lower(std::size_t i) { return split(i, reversed_tag); }
465 
470  void merge_right(splay_tree other) { merge(std::move(other), forward_tag); }
471 
476  void merge_left(splay_tree other) { merge(std::move(other), reversed_tag); }
477 
483  void reverse(std::size_t i, std::size_t j) {
484  assert(i <= j);
485  // split lower
487  // split higher
488  splay_tree<value_type> rtree = split_higher(j - i);
489  // reverse
490  root_->subtree_reverse();
491  // merge
492  merge_left(std::move(ltree));
493  merge_right(std::move(rtree));
494  }
495 
496  private:
498  explicit splay_tree(node_ptr root) : root_(std::move(root)) {}
499 
500  template <typename Direction>
501  splay_tree split(std::size_t i, Direction dir_tag) {
502  splay(i);
503  node_ptr new_root = std::move(root_->child(dir_tag));
504  if (new_root != nullptr) {
505  new_root->make_root();
506  }
507  if (root_ != nullptr) {
508  root_->update_size();
509  }
510 
511  return splay_tree<value_type>(std::move(new_root));
512  }
513 
514  iterator splay(detail::forward_tag) const {
515  return splay(root_->size() - 1);
516  }
517 
518  iterator splay(detail::reversed_tag) const { return splay(0); }
519 
520  template <typename Direction>
521  void merge(splay_tree other, Direction dir_tag) {
522  if (other.root_ == nullptr) {
523  return;
524  }
525  splay(dir_tag);
526  assert(root_->child(dir_tag) == nullptr);
527  root_->set(std::move(other.root_), dir_tag);
528  }
529 
530 
531  node_ptr &get_parent(node_ptr &node) const {
532  assert(node);
533  node_type *parent = node->parent();
534  assert(parent != nullptr);
535  node_type *granpa = parent->parent();
536  if (granpa == nullptr) {
537  return root_;
538  } else {
539  if (granpa->left().get() == parent) {
540  return granpa->left();
541  } else {
542  assert(granpa->right().get() == parent);
543  return granpa->right();
544  }
545  }
546  }
547 
552  void splay_internal(node_ptr &node) const {
553  assert(node);
554  if (node == root_) {
555  return;
556  }
557  node_ptr &parent = get_parent(node);
558  if (parent == root_) {
559  if (node == parent->left()) {
560  rotate(root_, forward_tag);
561  } else {
562  assert(node == parent->right());
563  rotate(root_, reversed_tag);
564  }
565  } else {
566  node_ptr &grand = get_parent(parent);
567  if (node == parent->left() && parent == grand->left()) {
568  rotate(grand, forward_tag);
569  rotate(grand, forward_tag);
570  } else if (node == parent->right() && parent == grand->right()) {
571  rotate(grand, reversed_tag);
572  rotate(grand, reversed_tag);
573  } else if (node == parent->right() && parent == grand->left()) {
574  rotate(parent, reversed_tag);
575  rotate(grand, forward_tag);
576  } else if (node == parent->left() && parent == grand->right()) {
577  rotate(parent, forward_tag);
578  rotate(grand, reversed_tag);
579  }
580  splay_internal(grand);
581  }
582  }
583 
588  template <typename Direction>
589  void rotate(node_ptr &parent, Direction dir_tag) const {
590  auto other_tag = other(dir_tag);
591  node_ptr node = std::move(parent->child(other_tag));
592  node.swap(parent);
593  parent->set_parent(node->parent());
594  node->set(std::move(parent->child(dir_tag)),
595  other_tag); // node size is updated here
596  parent->set(std::move(node), dir_tag); // node size is updated here
597  }
598 
599 
606  template <typename I> node_ptr build_tree(const I b, const I e) {
607  if (b >= e) {
608  return nullptr;
609  }
610  std::size_t m = (e - b) / 2;
611  node_ptr node{ new node_type(*(b + m)) };
612  bool ret =
613  t_to_node_.insert(std::make_pair(*(b + m), node.get())).second;
614  assert(ret);
615  node->set_left(build_tree(b, b + m));
616  node->set_right(build_tree(b + m + 1, e));
617  return node;
618  }
619 
620 
626  node_ptr &find(std::size_t i) const {
627  node_ptr *node = &root_;
628  while (true) {
629  if (!*node) {
630  return *node;
631  }
632  node_ptr *left = &((*node)->left());
633  std::size_t left_size = node_size(*left);
634  if (left_size == i) {
635  return *node;
636  } else if (left_size > i) {
637  node = left;
638  } else {
639  i -= left_size + 1;
640  node = &(*node)->right();
641  }
642  }
643  }
644 
646  std::size_t rotation_cnt_ = 0; // to keep iterators consistent with tree
647  mutable node_ptr root_;
648  std::unordered_map<T, node_type *> t_to_node_;
649 };
650 }
651 }
652 
653 #endif // PAAL_SPLAY_TREE_HPP
void update_size()
recomputes subtree size from sizes of children&#39;s subtrees
Definition: splay_tree.hpp:156
splay_tree split_higher(std::size_t i)
splits sequence, modified this contains elements {0, ..., i}
Definition: splay_tree.hpp:457
void merge_left(splay_tree other)
merges given tree to the left of the smallest element of this
Definition: splay_tree.hpp:476
std::unique_ptr< Node< V > > copy_node(std::unique_ptr< Node< V >> const &node)
copy node pointer
Definition: splay_tree.hpp:53
splay_tree(const I b, const I e)
constructs tree from elements between two iterators
Definition: splay_tree.hpp:351
void set_left(node_ptr node)
sets left child pointer
Definition: splay_tree.hpp:119
splay_tree(const splay_tree &splay)
constructor
Definition: splay_tree.hpp:371
std::size_t node_size(const NPtr &node)
Definition: splay_tree.hpp:38
void make_root()
detaches this node from parent
Definition: splay_tree.hpp:107
Iterator(const Iterator &other)
copy constructor
Definition: splay_tree.hpp:278
void merge_right(splay_tree other)
merges given tree to the right of the biggest element of this
Definition: splay_tree.hpp:470
void set(node_ptr node, Direction dir_tag)
sets child pointer
Definition: splay_tree.hpp:137
void normalize()
locally relaxes tree
Definition: splay_tree.hpp:213
void reverse(std::size_t i, std::size_t j)
reverses subsequence of elements with indices in {i, ..., j}
Definition: splay_tree.hpp:483
value_type & operator[](std::size_t i) const
Definition: splay_tree.hpp:414
void subtree_reverse()
lazily reverses order in subtree
Definition: splay_tree.hpp:210
void normalize_root_path()
relaxes all nodes on path from root to this
Definition: splay_tree.hpp:227
Iterator()
iterator after last element
Definition: splay_tree.hpp:264
splay_tree & operator=(splay_tree &splay)
operator=
Definition: splay_tree.hpp:363
splay_tree & operator=(splay_tree &&splay)=default
operator=
void set_internal(node_ptr node, Direction dir_tag)
sets child pointer (no relaxation)
Definition: splay_tree.hpp:148
Iterator(node_ptr node, const ST *splay)
iterator to element in given node
Definition: splay_tree.hpp:271
std::size_t get_rotation_cnt() const
gets rotationCnt()
Definition: splay_tree.hpp:441
Node(const value_type &val)
Definition: splay_tree.hpp:86
iterator splay(std::size_t i) const
splays tree according to splay policy
Definition: splay_tree.hpp:447
splay_tree(const A &array)
creates tree from elements in std::vector
Definition: splay_tree.hpp:383
node_type * advance(Direction dir_tag)
Definition: splay_tree.hpp:175
value_type val_
value of the node
Definition: splay_tree.hpp:236
splay_tree split_lower(std::size_t i)
splits sequence, modified this contains elements {i, ...}
Definition: splay_tree.hpp:464
Node(const Node &n)
constructor
Definition: splay_tree.hpp:90
std::size_t get_idx(const T &t) const
Definition: splay_tree.hpp:417