//$Id: tree.h,v 1.7 2006-11-26 00:28:50 cactus Exp $ -*- c++ -*-

#ifndef EAF_TREE_H
#define EAF_TREE_H

#include <cassert>

template<typename T> class RefCountedPtr
{
    T *ptr;
    mutable unsigned int *refcount;

public:
    RefCountedPtr (T *ptr_ = 0) : ptr (ptr_), refcount (new unsigned int (1)) {}
    
    RefCountedPtr (const RefCountedPtr<T> &other):
        ptr (other.ptr),
        refcount (other.refcount)
        {
            ++*refcount;
        }
    
    ~RefCountedPtr () { dispose (); }
    
    T * const       operator-> ()       { return ptr; }
    const T * const operator-> () const { return ptr; }
    
    operator bool () const { return ptr; }
    bool operator== (const RefCountedPtr<T> &other) const { return other.ptr == ptr; }
    
    RefCountedPtr<T> &operator= (const RefCountedPtr<T> &other) {
        if (other.ptr == ptr)
            return *this;
        
        dispose ();
        
        ptr = other.ptr;
        refcount = other.refcount;
        *refcount += 1;
        
        return *this;
    }
    
private:
    void dispose () {
        if (!--*refcount)
        {
            delete ptr;
            delete refcount;
        }
    }    
};

template<typename T> class TernaryTree
{
    struct TreeNode
    {
    public:
        T key;
        RefCountedPtr<TreeNode> parent;
        RefCountedPtr<TreeNode> left, middle, right;

        TreeNode (RefCountedPtr<TreeNode> parent_, const T &key_):
            key (key_),
            parent (parent_)
            {}

        ~TreeNode () {}
    };
    
    RefCountedPtr<TreeNode> node;

    TernaryTree (RefCountedPtr<TreeNode> node_): node (node_) {}
    
public:
    TernaryTree () {}
    TernaryTree (const T &root_key): node (new TreeNode (0, root_key)) {}
    TernaryTree (const TernaryTree<T> &other): node (other.node) {}

    operator bool () const { return node != 0; }
        
    const T& get_key () const { return node->key; }
    T& set_key (const T &key) { assert (node); return node->key = key; }

    TernaryTree parent () const { return node->parent; }
    TernaryTree left ()   const { return node->left; }
    TernaryTree middle () const { return node->middle; }
    TernaryTree right ()  const { return node->right; }

    bool is_root () const   { return !node->parent; }
    bool is_left () const   { return node->parent && node->parent->left == node; }
    bool is_middle () const { return node->parent && node->parent->middle == node; }
    bool is_right () const  { return node->parent && node->parent->right == node; }

    void remove () {
        if (is_left ())
            node->parent->left = RefCountedPtr<TreeNode> ();
        else if (is_middle ())
            node->parent->middle = RefCountedPtr<TreeNode> ();
        else if (is_right ())
            node->parent->right = RefCountedPtr<TreeNode> ();
    }
    
    void add_root (const T &key = T())
        {
            assert (!node);
            node = new TreeNode (0, key);
        }

    TernaryTree add_left (const T &key = T ())
        {
            assert (node && !node->left);
            return node->left = new TreeNode (node, key);
        }
    
    TernaryTree add_middle (const T &key = T ())
        {
            assert (node && !node->middle);
            return node->middle = new TreeNode (node, key);
        }
    
    TernaryTree add_right (const T &key = T ())
        {
            assert (node && !node->right);
            return node->right = new TreeNode (node, key);
        }

    class visitor
    {
    public:
        virtual ~visitor() {};
        
        virtual void visit_node (TernaryTree<T> &tree) = 0;
    };

    class const_visitor
    {
    public:
        virtual ~const_visitor() {};
        
        virtual void visit_node (const TernaryTree<T> &tree) = 0;
    };
    
    void visit_inorder (visitor &visitor) {
        if (!*this) return;

        left ().visit_inorder (visitor);
        visitor.visit_node (*this);
        middle ().visit_inorder (visitor);
        right ().visit_inorder (visitor);
    }

    void visit_inorder (const_visitor &visitor) const {
        if (!*this) return;

        left ().visit_inorder (visitor);
        visitor.visit_node (*this);
        middle ().visit_inorder (visitor);
        right ().visit_inorder (visitor);
    }
    
private:
    void copy_subtree (TreeNode *dst, TreeNode *src)
        {
            if (src->left)
            {
                dst->left = new TreeNode (dst, src->left->key);
                copy_subtree (dst->left, src->left);
            }

            if (src->middle)
            {
                dst->middle = new TreeNode (dst, src->middle->key);
                copy_subtree (dst->middle, src->middle);
            }

            if (src->right)
            {
                dst->right = new TreeNode (dst, src->right->key);
                copy_subtree (dst->right, src->right);
            }
        }
};

#endif