michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* vim: set ts=8 sts=2 et sw=2 tw=80: */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /**
michael@0:  * A sorted tree with optimal access times, where recently-accessed elements
michael@0:  * are faster to access again.
michael@0:  */
michael@0: 
michael@0: #ifndef mozilla_SplayTree_h
michael@0: #define mozilla_SplayTree_h
michael@0: 
michael@0: #include "mozilla/Assertions.h"
michael@0: #include "mozilla/NullPtr.h"
michael@0: 
michael@0: namespace mozilla {
michael@0: 
michael@0: template<class T, class C>
michael@0: class SplayTree;
michael@0: 
michael@0: template<typename T>
michael@0: class SplayTreeNode
michael@0: {
michael@0:   public:
michael@0:     template<class A, class B>
michael@0:     friend class SplayTree;
michael@0: 
michael@0:     SplayTreeNode()
michael@0:       : left(nullptr), right(nullptr), parent(nullptr)
michael@0:     {}
michael@0: 
michael@0:   private:
michael@0:     T* left;
michael@0:     T* right;
michael@0:     T* parent;
michael@0: };
michael@0: 
michael@0: 
michael@0: /**
michael@0:  * Class which represents a splay tree.
michael@0:  * Splay trees are balanced binary search trees for which search, insert and
michael@0:  * remove are all amortized O(log n), but where accessing a node makes it
michael@0:  * faster to access that node in the future.
michael@0:  *
michael@0:  * T indicates the type of tree elements, Comparator must have a static
michael@0:  * compare(const T&, const T&) method ordering the elements. The compare
michael@0:  * method must be free from side effects.
michael@0:  */
michael@0: template<typename T, class Comparator>
michael@0: class SplayTree
michael@0: {
michael@0:     T* root;
michael@0: 
michael@0:   public:
michael@0:     SplayTree()
michael@0:       : root(nullptr)
michael@0:     {}
michael@0: 
michael@0:     bool empty() const {
michael@0:       return !root;
michael@0:     }
michael@0: 
michael@0:     T* find(const T& v)
michael@0:     {
michael@0:       if (empty())
michael@0:         return nullptr;
michael@0: 
michael@0:       T* last = lookup(v);
michael@0:       splay(last);
michael@0:       checkCoherency(root, nullptr);
michael@0:       return Comparator::compare(v, *last) == 0 ? last : nullptr;
michael@0:     }
michael@0: 
michael@0:     bool insert(T* v)
michael@0:     {
michael@0:       MOZ_ASSERT(!find(*v), "Duplicate elements are not allowed.");
michael@0: 
michael@0:       if (!root) {
michael@0:         root = v;
michael@0:         return true;
michael@0:       }
michael@0:       T* last = lookup(*v);
michael@0:       int cmp = Comparator::compare(*v, *last);
michael@0: 
michael@0:       T** parentPointer = (cmp < 0) ? &last->left : &last->right;
michael@0:       MOZ_ASSERT(!*parentPointer);
michael@0:       *parentPointer = v;
michael@0:       v->parent = last;
michael@0: 
michael@0:       splay(v);
michael@0:       checkCoherency(root, nullptr);
michael@0:       return true;
michael@0:     }
michael@0: 
michael@0:     T* remove(const T& v)
michael@0:     {
michael@0:       T* last = lookup(v);
michael@0:       MOZ_ASSERT(last, "This tree must contain the element being removed.");
michael@0:       MOZ_ASSERT(Comparator::compare(v, *last) == 0);
michael@0: 
michael@0:       // Splay the tree so that the item to remove is the root.
michael@0:       splay(last);
michael@0:       MOZ_ASSERT(last == root);
michael@0: 
michael@0:       // Find another node which can be swapped in for the root: either the
michael@0:       // rightmost child of the root's left, or the leftmost child of the
michael@0:       // root's right.
michael@0:       T* swap;
michael@0:       T* swapChild;
michael@0:       if (root->left) {
michael@0:         swap = root->left;
michael@0:         while (swap->right)
michael@0:           swap = swap->right;
michael@0:         swapChild = swap->left;
michael@0:       } else if (root->right) {
michael@0:         swap = root->right;
michael@0:         while (swap->left)
michael@0:           swap = swap->left;
michael@0:         swapChild = swap->right;
michael@0:       } else {
michael@0:         T* result = root;
michael@0:         root = nullptr;
michael@0:         return result;
michael@0:       }
michael@0: 
michael@0:       // The selected node has at most one child, in swapChild. Detach it
michael@0:       // from the subtree by replacing it with that child.
michael@0:       if (swap == swap->parent->left)
michael@0:         swap->parent->left = swapChild;
michael@0:       else
michael@0:         swap->parent->right = swapChild;
michael@0:       if (swapChild)
michael@0:         swapChild->parent = swap->parent;
michael@0: 
michael@0:       // Make the selected node the new root.
michael@0:       root = swap;
michael@0:       root->parent = nullptr;
michael@0:       root->left = last->left;
michael@0:       root->right = last->right;
michael@0:       if (root->left) {
michael@0:         root->left->parent = root;
michael@0:       }
michael@0:       if (root->right) {
michael@0:         root->right->parent = root;
michael@0:       }
michael@0: 
michael@0:       checkCoherency(root, nullptr);
michael@0:       return last;
michael@0:     }
michael@0: 
michael@0:     T* removeMin()
michael@0:     {
michael@0:       MOZ_ASSERT(root, "No min to remove!");
michael@0: 
michael@0:       T* min = root;
michael@0:       while (min->left)
michael@0:         min = min->left;
michael@0:       return remove(*min);
michael@0:     }
michael@0: 
michael@0:   private:
michael@0:     /**
michael@0:      * Returns the node in this comparing equal to |v|, or a node just greater or
michael@0:      * just less than |v| if there is no such node.
michael@0:      */
michael@0:     T* lookup(const T& v)
michael@0:     {
michael@0:       MOZ_ASSERT(!empty());
michael@0: 
michael@0:       T* node = root;
michael@0:       T* parent;
michael@0:       do {
michael@0:         parent = node;
michael@0:         int c = Comparator::compare(v, *node);
michael@0:         if (c == 0)
michael@0:           return node;
michael@0:         else if (c < 0)
michael@0:           node = node->left;
michael@0:         else
michael@0:           node = node->right;
michael@0:       } while (node);
michael@0:       return parent;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Rotate the tree until |node| is at the root of the tree. Performing
michael@0:      * the rotations in this fashion preserves the amortized balancing of
michael@0:      * the tree.
michael@0:      */
michael@0:     void splay(T* node)
michael@0:     {
michael@0:       MOZ_ASSERT(node);
michael@0: 
michael@0:       while (node != root) {
michael@0:         T* parent = node->parent;
michael@0:         if (parent == root) {
michael@0:           // Zig rotation.
michael@0:           rotate(node);
michael@0:           MOZ_ASSERT(node == root);
michael@0:           return;
michael@0:         }
michael@0:         T* grandparent = parent->parent;
michael@0:         if ((parent->left == node) == (grandparent->left == parent)) {
michael@0:           // Zig-zig rotation.
michael@0:           rotate(parent);
michael@0:           rotate(node);
michael@0:         } else {
michael@0:           // Zig-zag rotation.
michael@0:           rotate(node);
michael@0:           rotate(node);
michael@0:         }
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     void rotate(T* node)
michael@0:     {
michael@0:       // Rearrange nodes so that node becomes the parent of its current
michael@0:       // parent, while preserving the sortedness of the tree.
michael@0:       T* parent = node->parent;
michael@0:       if (parent->left == node) {
michael@0:         //     x          y
michael@0:         //   y  c  ==>  a  x
michael@0:         //  a b           b c
michael@0:         parent->left = node->right;
michael@0:         if (node->right)
michael@0:           node->right->parent = parent;
michael@0:         node->right = parent;
michael@0:       } else {
michael@0:         MOZ_ASSERT(parent->right == node);
michael@0:         //   x             y
michael@0:         //  a  y   ==>   x  c
michael@0:         //    b c       a b
michael@0:         parent->right = node->left;
michael@0:         if (node->left)
michael@0:           node->left->parent = parent;
michael@0:         node->left = parent;
michael@0:       }
michael@0:       node->parent = parent->parent;
michael@0:       parent->parent = node;
michael@0:       if (T* grandparent = node->parent) {
michael@0:         if (grandparent->left == parent)
michael@0:           grandparent->left = node;
michael@0:         else
michael@0:           grandparent->right = node;
michael@0:       } else {
michael@0:         root = node;
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     T* checkCoherency(T* node, T* minimum)
michael@0:     {
michael@0: #ifdef DEBUG
michael@0:       MOZ_ASSERT_IF(root, !root->parent);
michael@0:       if (!node) {
michael@0:         MOZ_ASSERT(!root);
michael@0:         return nullptr;
michael@0:       }
michael@0:       MOZ_ASSERT_IF(!node->parent, node == root);
michael@0:       MOZ_ASSERT_IF(minimum, Comparator::compare(*minimum, *node) < 0);
michael@0:       if (node->left) {
michael@0:         MOZ_ASSERT(node->left->parent == node);
michael@0:         T* leftMaximum = checkCoherency(node->left, minimum);
michael@0:         MOZ_ASSERT(Comparator::compare(*leftMaximum, *node) < 0);
michael@0:       }
michael@0:       if (node->right) {
michael@0:         MOZ_ASSERT(node->right->parent == node);
michael@0:         return checkCoherency(node->right, node);
michael@0:       }
michael@0:       return node;
michael@0: #else
michael@0:       return nullptr;
michael@0: #endif
michael@0:     }
michael@0: 
michael@0:     SplayTree(const SplayTree&) MOZ_DELETE;
michael@0:     void operator=(const SplayTree&) MOZ_DELETE;
michael@0: };
michael@0: 
michael@0: }  /* namespace mozilla */
michael@0: 
michael@0: #endif /* mozilla_SplayTree_h */