/**
 * $Id: avltree.h,v 1.2 2003/01/07 13:35:42 plasmahh Exp $
 * $Revision: 1.2 $
 * $Author: plasmahh $
 * $Date: 2003/01/07 13:35:42 $
 */

/*
 *
 * Below you will find an old draft of an avl tree with interface similar to
 * the standard libraries classes, that is, it copies its arguments. We will
 * rewrite this so that it has the following features:
 * - It's intrusive.
 * - You can control all memory stored pointer types
 * - You can chose the way of traversal (i.e. either dllist like or via a
 *   parent pointer)
 * - If the implementation shows that there are meaningfull operations that do
 *   not require the parent pointer at all, we can think about doing a variant
 *   without.
 * - You can chose the way the skew is encoded: in the pointers of left/right
 *   or in an additional member.
 *
 * That way you should have quite fine grained control over speed and space
 * occupied by its members.  
 *
 * PS: An additional mode could embed a type in the nodes, as the current one
 * does for very small data entities that would fit into padding that might be
 * necessary here.
 *
 * PPS: Oh and once this thing works properly, we will replace the recursive
 * calling of the various functions by a proper stack based iteration to avoid
 * function call overhead.
 */

namespace iwear
{
    namespace container
    {

enum  avl_tree_status 
{
    avl_ok, 
    avl_balanced, 
    avl_error
};

enum avl_tree_skew
{
    avl_none, avl_left, avl_right
};

/**
 * This is a base class for all treenodes. We do this, so we can have some of
 * the functionality thats needed to be non-templated, and offloaded to the
 * common library code. While this means it cannot be inlined, we should be
 * careful about what to choose for this operation.
 */
struct avl_tree_node_base
{
    typedef avl_tree_node_base* base_ptr;
    typedef const avl_tree_node_base* const_base_ptr;

    base_ptr left;
    base_ptr right;
    base_ptr parent;

    avl_tree_skew skew;
};

template<class Value>
struct avl_tree_node : public avl_tree_node_base
{
    /**
     * This is the actual data beeing stored. What it is, depends on whether
     * its a avlmap, avlset, and of course of the template arguments those are
     * implemented with.
     */
    Value value;
};

/**
 * This is the iterator for the avltree family of containers. It should be as
 * lightweight as possible.
 */
template<class Value>
struct avl_tree_iterator
{
    typedef avl_tree_node_base::base_ptr base_ptr;
    typedef avl_tree_node<Value>* link_ptr;
    typedef avl_tree_iterator<Value> self;

    base_ptr node;
};

/**
 * This is some AVLTree basic implementation that will be used in the avlmap,
 * avlset and probably even in the avlmultimap and avlmultiset classes. We will
 * do here a basic class, with one node structure, and a comparator for that.
 * This way we can put a single element into the structure, or a std::pair in
 * case of a map, and the comparator will only compare the pairs.
 */
template <class Value>
class avltree /*{{{*/
{
protected:
    typedef int size_type;
    /**
     * The parent is the real tree, the left and right are the left, resp.
     * right-most entries of the tree.
     */
    avl_tree_node_base header;

    size_type nodes;
public:

    avltree( );

    avltree<Key,Value>::avltree( )
    {
	this->header.skew = avl_none;
	this->header.parent = 0;
	this->header.left = &(this->header);
	this->header.right = &(this->header);
    }

    void add ( const Key& nk, const Value& nd );
    bool remove( const Key& rk);
    ~avltree( void );
    /**
 It has been proven that the worst-case root height for an AVL tree is bounded above by approximately 1.44log2(N+2).
 *
 * Ok, this means that for the lengths we have to make sure our stack size is
 * according to these values (lengths are calculated by the highest bit, then
 * we look how much that value max could have been, and then we put it in a
 * table, thus making it just lookup[highestbit(nodes)] and we have it.
 * (XXX as a security measurement, in DEBUG mode, we will add a sentinel value
 * *after* the VLA, which we check for beeing overwritten.
 *
 * The lookup table will consist of Bits * 1.5, rounded up.
 *
 * FIXME: Maybe we should right away fix it to 50. This would make about
 * 200bytes, nothing that we shouldn't have. I think printf itself needs about
 * 2k.
 *
 * We don't do more than 32. Although its bad to assume that 32Bit is the max
 * of the value, we assume that more than 8589934592 elements will not be
 * possible. Given a pointer is 4 Bytes, and the value itself too, we would
 * have like 40GB of data, nothing this tree should handle.
 */
private :
    /**
     * Height of the left subtree.
     */
    void rebal ( );
    void rotate_left( treenode<Key,Value> ** node);
    void rotate_right( treenode<Key,Value> ** node);
    avl_tree_status remove( treenode<Key,Value> ** node, Key _key);
    avl_tree_status insert( treenode<Key,Value> **node, const Key & _key , const Data & _data);

    avl_tree_status left_has_grown(treenode<Key,Value> **node);
    avl_tree_status right_has_grown(treenode<Key,Value> **node);
    avl_tree_status left_has_shrunk(treenode<Key,Value>**node);
    avl_tree_status right_has_shrunk(treenode<Key,Value>**node);

    uint32 find_highest(treenode<Key,Value> *target, treenode<Key,Data>**node, avl_tree_status *res);
    uint32 find_lowest(treenode<Key,Value> *target, treenode<Key,Data>**node, avl_tree_status *res);
    uint32 get_depth( treenode<Key,Value> * sub );
protected:
};/*}}}*/

template <class Key,class Value>
bool avltree<Key,Value>::remove( const Key& rk)
{
    return remove(&Root, rk);
}

template <class Key,class Value>
void avltree<Key,Value>::add ( const Key& nk, const Data& nd )
{
    insert( &Root,nk,nd );
}

template <class Key,class Value>
void avltree<Key,Value>::rotate_left( treenode<Key,Data> ** node )/*{{{*/
{
    rl++;
    /*
     *
     *         G     I
     *          \   / 
     *           \ /
     *      E     H      B    E G    I
     *       \   /        \   / \   /
     *        \ /          \ /   \ /
     *   B     F            D     H
     *    \   /              \   /
     *     \ /        -->     \ /
     *      D                  F
     *       \                  \ 
     *        K                  K
     *
     *
     *
     */
    // Note : node == Pointer to Ks pointer to D
    treenode<Key,Value> * tmp = *node; // => *node = tmp = Ks pointer to D
	    
    *node = (*node)->right; // replace K pointing to D with K pointing to F
//    *node->parent = *tmp->parent;
    tmp->right = (*node)->left; // Ds right pointer points now to Fs left pointer
//    tmp->right->parent = tmp;
    (*node)->left = tmp; // Fs Left points now to D
//    tmp->parent = (*node);

}/*}}}*/

template <class Key,class Value>
void avltree<Key,Value>::rotate_right( treenode<Key,Data> **node )/*{{{*/
{
    rr++;
    treenode<Key,Value> *tmp = *node;

    *node = (*node)->left;
//    (*node)->parent = (*tmp)->parent;
    tmp->left = (*node)->right;
//    tmp->left->parent = tmp;
    (*node)->right = tmp;
//    tmp->parent = (*node);
} /*}}}*/

template <class Key,class Value>
avl_tree_status avltree<Key,Value>::insert( treenode<Key,Data> **node, const Key & _key , const Data & _data)/*{{{*/
{
	//avl_tree_status tmp;

	if (!(*node)) 
	{
	    *node = new treenode<Key,Value> (_key,_data);
	    items++;
	    return avl_balanced;
	}
	else if (_key < (*node)->_key)
	{

	    if ( insert(& (*node)->left, _key, _data) == avl_balanced) 
	    {
		return left_has_grown(node);
	    }
	    else
	    {
		return avl_ok;
	    }
	}
	else if (_key > (*node)->_key)
	{

	    if ( insert(& (*node)->right, _key, _data) == avl_balanced) 
	    {
		return right_has_grown(node);
	    }
	    else
	    {
		return avl_ok;
	    }
	}
	else
	{
	    (*node)->_data = _data;
	    return avl_ok;
	}
}/*}}}*/

template <class Key,class Value>
avl_tree_status avltree<Key,Value>::left_has_shrunk(treenode<Key,Data> **node)/*{{{*/
{
    switch ((*node)->skew) 
    {
	case avl_left:
	    (*node)->skew = avl_none;
	    return avl_balanced;

	case avl_right:
	    if ((*node)->right->skew == avl_right) 
	    {
		(*node)->skew = (*node)->right->skew = avl_none;
		rotate_left(node);
		return avl_balanced;
	    }
	    else if ((*node)->right->skew == avl_none) 
	    {
		(*node)->skew = avl_right;
		(*node)->right->skew = avl_left;
		rotate_left(node);
		return avl_ok;
	    }
	    else 
	    {
		switch ((*node)->right->left->skew) 
		{
		    case avl_left:
			(*node)->skew = avl_none;
			(*node)->right->skew = avl_right;
			break;

		    case avl_right:
			(*node)->skew = avl_left;
			(*node)->right->skew = avl_none;
			break;

		    default:
			(*node)->skew = avl_none;
			(*node)->right->skew = avl_none;
		}
		(*node)->right->left->skew = avl_none;
		rotate_right(& (*node)->right);
		rotate_left(node);
		return avl_balanced;
	    }

	default:
	    (*node)->skew = avl_right;
	    return avl_ok;
    }
}/*}}}*/

template <class Key,class Value>
avl_tree_status avltree<Key,Value>::right_has_shrunk(treenode<Key,Data>**node)/*{{{*/
{
    switch ((*node)->skew) 
    {
	case avl_right:
	    (*node)->skew = avl_none;
	    return avl_balanced;

	case avl_left:
	if ((*node)->left->skew == avl_left) 
	{
	    (*node)->skew = (*node)->left->skew = avl_none;
	    rotate_right(node);
	    return avl_balanced;
	}
	else if ((*node)->left->skew == avl_none) 
	{
	    (*node)->skew = avl_left;
	    (*node)->left->skew = avl_right;
	    rotate_right(node);
	    return avl_ok;
	}
	else 
	{
	    switch ((*node)->left->right->skew) 
	    {
		case avl_left:
		    (*node)->skew = avl_right;
		    (*node)->left->skew = avl_none;
		    break;

		case avl_right:
		    (*node)->skew = avl_none;
		    (*node)->left->skew = avl_left;
		    break;

		default:
		    (*node)->skew = avl_none;
		    (*node)->left->skew = avl_none;
	    }
	    (*node)->left->right->skew = avl_none;
	    rotate_left(& (*node)->left);
	    rotate_right(node);
	    return avl_balanced;
	}

	default:
	    (*node)->skew = avl_left;
	    return avl_ok;
    }
}/*}}}*/

template <class Key,class Value>
avl_tree_status avltree<Key,Value>::right_has_grown(treenode<Key,Data> **node)/*{{{*/
{
    switch ((*node)->skew)
    {
	case avl_left:
	    (*node)->skew = avl_none;
	    return avl_ok;
	case avl_right:
	    if ((*node)->right->skew == avl_right)
	    {
		(*node)->skew = (*node)->right->skew = avl_none;
		rotate_left(node);
	    }
	    else
	    {
		switch ((*node)->right->left->skew)
		{
		    case avl_right:
			(*node)->skew = avl_left;
			(*node)->right->skew = avl_none;
			break;
		    case avl_left:
			(*node)->skew = avl_none;
			(*node)->right->skew = avl_right;
			break;
		    default:
			(*node)->skew = avl_none;
			(*node)->right->skew = avl_none;
		}
		(*node)->right->left->skew = avl_none;
		rotate_right(& (*node)->right);
		rotate_left(node);
	    }
	    return avl_ok;
	default:
	    (*node)->skew = avl_right;
	    return avl_balanced;
    }
}/*}}}*/

//enum AVLRES
template <class Key,class Value>
avl_tree_status avltree<Key,Value>::left_has_grown(treenode<Key,Data> **node)/*{{{*/
{
    switch ((*node)->skew) 
    {
        case avl_left:
            if ((*node)->left->skew == avl_left) 
	    {
                (*node)->skew = (*node)->left->skew = avl_none;
                rotate_right(node);
            }
            else 
	    {
		switch ((*node)->left->right->skew) 
		{
		    case avl_left:
			(*node)->skew = avl_right;
			(*node)->left->skew = avl_none;
			break;

		    case avl_right:
			(*node)->skew = avl_none;
			(*node)->left->skew = avl_left;
			break;

		    default:
			(*node)->skew = avl_none;
			(*node)->left->skew = avl_none;
		}
		(*node)->left->right->skew = avl_none;
		rotate_left(& (*node)->left);
		rotate_right(node);
	    }
                    return avl_ok;

	case avl_right:
	    (*node)->skew = avl_none;
	    return avl_ok;

	default:
	    (*node)->skew = avl_left;
	    return avl_balanced;
    }
}/*}}}*/

template <class Key,class Value>
uint32 avltree<Key,Value>::get_depth( void )
{
    return get_depth(Root);
}

template <class Key,class Value>
uint32 avltree<Key,Value>::get_depth( treenode<Key,Data> * sub )
{
    if ( sub )
    {
	return ( 1 + max(get_depth(sub->left),get_depth(sub->right)) );
    }
    else
    {
	return 0;
    }
}

template <class Key,class Value>
uint32 avltree<Key,Value>::find_lowest(treenode<Key,Data> *target, treenode<Key,Data>**node, avl_tree_status *res)/*{{{*/
{
    treenode<Key,Value> *tmp;

    *res = avl_balanced;
    if (!(*node))
    {
	return 0;
    }
    if ((*node)->left)
    {
	if ( !find_lowest(target,&(*node)->left, res) )
	{
	    return 0;
	}
	if ( *res == avl_balanced )
	{
	    *res = left_has_shrunk(node);
	}
	return 1;
    }
    target->_data = (*node)->_data;
    target->_key  = (*node)->_key;
    tmp = *node;
    *node = (*node)->right;
    delete tmp;
    return 1;
}/*}}}*/
template <class Key,class Value>
uint32 avltree<Key,Value>::find_highest(treenode<Key,Data> *target, treenode<Key,Data>**node, avl_tree_status *res)/*{{{*/
{
    treenode<Key,Value> *tmp;

    *res = avl_balanced;
    if (!(*node)) 
    {
	return 0;
    }
    else if ((*node)->right) 
    {
	if (!find_highest(target, &(*node)->right, res)) 
	{
	    return 0;
	}
	else if (*res == avl_balanced) 
	{
	    *res = right_has_shrunk(node);
	}
	return 1;
    }
    
    target->_data  = (*node)->_data;
    target->_key  = (*node)->_key;
    tmp = *node;
    *node = (*node)->left;
    delete tmp;
    return 1;
}/*}}}*/

template <class Key,class Value>
avl_tree_status avltree<Key,Value>::remove( treenode<Key,Data> ** node, Key _key)
{
    avl_tree_status tmp = avl_balanced;
    if ( !(*node) )
    {
	return avl_error;
    }
    if ( _key < (*node)->_key )
    {
	if ( ( tmp = remove(&(*node)->left,_key) ) == avl_balanced )
	{
	    return left_has_shrunk(node);
	}
	return tmp;
    }
    if ( (*node)->_key < _key )
    {
	if ( ( tmp = remove(&(*node)->right,_key) ) == avl_balanced )
	{
	    return right_has_shrunk(node);
	}
	return tmp;
    }
    if ((*node)->left)
    {
	if ( find_highest(*node, &((*node)->left), &tmp))
	{
	    if ( tmp == avl_balanced )
	    {
		tmp = left_has_shrunk(node);
	    }
	    return tmp;
	}
    }
    if ((*node)->right)
    {
	if ( find_lowest(*node, &((*node)->right), &tmp))
	{
	    if ( tmp == avl_balanced )
	    {
		tmp = right_has_shrunk(node);
	    }
	    return tmp;
	}
    }
    delete (*node);
    *node = NULL;
    return avl_balanced;
    
}