splaytree.h

Go to the documentation of this file.

#ifndef _SPLAYTREE
#define _SPLAYTREE

template <class comparable>
class splaytree_iterator;

template <class comparable>
struct node {

        node<comparable> *left;
        node<comparable> *right;
        node<comparable> *parent;
        comparable element;
};

template <class comparable>
class splaytree {
        public:

                typedef splaytree_iterator<comparable> iterator;
                typedef splaytree_iterator<comparable> const_iterator;
                typedef size_t size_type;

                explicit splaytree(const comparable &notFound);
                splaytree(const splaytree &rhs);
                virtual ~splaytree() { clear(); delete Null; }

                const comparable &findMin();
                const comparable &findMax();
                const comparable &find(const comparable &x);

                bool empty() const { return root == Null; }
                size_type size() const { return count; }

                void print() const { plog("\ndump tree %x:\n", this); print(root); }

                void clear() { clear(root); root = Null; }
                void insert(const comparable &x);
                void remove(const comparable &x);
                void erase(iterator iter) { for (;iter != enditer; iter++) { remove(*iter); } }
                void sort();

                void push_back(const comparable &x) { insert(x); }

                iterator begin() { return iterator(root, Null); }
                iterator end() { return enditer; }
                
                const_iterator begin() const { return iterator(root, Null); }
                const_iterator end() const { return enditer; }

//              const splaytree &operator=(const splaytree &rhs);

        private:

                const comparable ITEM_NOT_FOUND;
                iterator enditer;
                size_type count;

                node<comparable> *root;
                node<comparable> *Null;

                void rotateLeft(node<comparable> *&k2) const;
                void rotateRight(node<comparable> *&k1) const;
                void splay(const comparable &x, node<comparable> *&t) const;

                void clear(node<comparable> *n)
                {
                        if (n != Null) {
                                clear(n->left);
                                clear(n->right);
                                delete n;
                        }
                }

                void print(node<comparable> *n) const
                {
                        if (n == Null) return;
                        print(n->left);
                        plog("%x: {", n);
                        if (n->parent == Null) { plog("Null"); } else { plog("%x", n->parent); }
                        plog(", ");
                        if (n->left == Null) { plog("Null"); } else { plog("%x", n->left); }
                        plog(", ");
                        if (n->right == Null) { plog("Null"); } else { plog("%x", n->right); }
                        plog("}\n");
                        print(n->right);
                }
};

template <class comparable>
class splaytree_iterator {
        public:

                splaytree_iterator() {}
                splaytree_iterator(const node<comparable> *root, const node<comparable> *n)
                {
                        iterations = 0;
                        current = (node<comparable> *) root;
                        Null = (node<comparable> *) n;

                        while (current->left != Null) {
                                current = current->left;
                        }
                }

                bool operator !=(const splaytree_iterator<comparable> iter) { return current != iter.current; }
                comparable operator *() { return current->element; }
                splaytree_iterator<comparable> *operator ++(int) { return ++*this; }
                splaytree_iterator<comparable> *operator ++()
                {
                        if (current->right == Null) {
                                node<comparable> *old;
                                do {
                                        old = current;
                                        current = current->parent;
                                } while ((current != Null) && (current->right == old));
                        } else {
                                current = current->right;
                                while (current->left != Null) {
                                        current = current->left;
                                }
                        }

                        iterations++;
                        return this;
                }

//              void operator --();

        private:

                long iterations;
                node<comparable> *current;
                node<comparable> *Null;
};

template<class comparable>
splaytree<comparable>::splaytree(const comparable &notFound) : ITEM_NOT_FOUND(notFound)
{
        Null = new node<comparable>;
        Null->left = Null->right = Null->parent = Null;
        Null->element = notFound;
        root = Null;

        enditer = iterator(Null, Null);
        count = 0;
}

template<class comparable>
void splaytree<comparable>::splay(const comparable &x, node<comparable> *&t) const
{
        static node<comparable> header;
        node<comparable> *leftTreeMax, *rightTreeMin;

        header.left = header.right = header.parent = Null;
        leftTreeMax = rightTreeMin = &header;

        Null->element = x;

        while (true) {
                if (x < t->element) {
                        if (x < t->left->element) {
                                rotateLeft(t);
                        }
                        if (t->left == Null) {
                                break;
                        }

                        rightTreeMin->left = t;
                        rightTreeMin = t;
                        t = t->left;
                } else {
                        if (t->right->element < x) {
                                rotateRight(t);
                        }
                        if (t->right == Null) {
                                break;
                        }

                        leftTreeMax->right = t;
                        leftTreeMax = t;
                        t = t->right;
                }
        }

        leftTreeMax->right = t->left;
        rightTreeMin->left = t->right;

        t->parent = header.parent;

        t->left = header.right;
        t->left->parent = t;

        t->right = header.left;
        t->right->parent = t;
}

template <class comparable>
void splaytree<comparable>::insert(const comparable &x)
{
        node<comparable> *newNode = new node<comparable>;
        newNode->element = x;

        if (root == Null) {
                newNode->left = newNode->right = newNode->parent = Null;
                root = newNode;
        } else {
                splay(x, root);

                newNode->parent = root->parent;
                if (x < root->element) {
                        newNode->left = root->left;
                        root->left->parent = newNode;

                        newNode->right = root;
                        newNode->right->parent = newNode;

                        root->left = Null;
                        root = newNode;
                } else {
                        newNode->right = root->right;
                        newNode->right->parent = newNode;

                        newNode->left = root;
                        newNode->left->parent = newNode;

                        root->right = Null;
                        root = newNode;
                }
        }

        count++;
}

template <class comparable>
void splaytree<comparable>::remove(const comparable &x)
{
        node<comparable> *newTree;

        splay(x, root);
        if (root->element != x) {
                return;
        }

        if (root->left == Null) {
                newTree = root->right;
        } else {
                newTree = root->left;
                splay(x, newTree);
                newTree->right = root->right;
                newTree->right->parent = newTree;
        }

        delete root;

        root = newTree;
        root->parent = Null;

        count--;
}

template <class comparable>
void splaytree<comparable>::sort()
{
#if 0
        node<comparable> *old = root;
        iterator iter = begin();

        root = Null;
        count = 0;

        while (iter != end()) {
                insert(*iter);
                iter++;
        }

        splay(old->element, root);
        clear(old);
#endif
}

template <class comparable>
const comparable &splaytree<comparable>::find(const comparable &x)
{
        splay(x, root);
        if ((x < root->element) || (root->element < x)) {
                return ITEM_NOT_FOUND;
        } else {
                return root->element;
        }
}

template <class comparable>
const comparable &splaytree<comparable>::findMax()
{
        node<comparable> *max = root;

        while (max->right != Null) {
                max = max->right;
        }

        return find(max->element);
}

template <class comparable>
const comparable &splaytree<comparable>::findMin()
{
        node<comparable> *min = root;

        while (min->left != Null) {
                min = min->left;
        }

        return find(min->element);
}

template <class comparable>
void splaytree<comparable>::rotateLeft(node<comparable> *&k2) const
{
        node<comparable> *k1 = k2->left;
        k1->parent = k2->parent;

        k2->left = k1->right;
        k2->left->parent = k2;

        k1->right = k2;
        k1->right->parent = k1;

        k2 = k1;
}

template <class comparable>
void splaytree<comparable>::rotateRight(node<comparable> *&k1) const
{
        node<comparable> *k2 = k1->right;
        k2->parent = k1->parent;

        k1->right = k2->left;
        k1->right->parent = k1;

        k2->left = k1;
        k2->left->parent = k2;

        k1 = k2;
}

#endif

---