//--------------------------------------------------------------------
//  AvlBinTree - header
//
//  created by Louis Thomas, 1-Dec-2000
//  
//  A template for managing a AVL Binary tree.

/*
QUICK-REF:

template<
    class T, 
    FIELDOFFSET(T, T * pLeft),
    FIELDOFFSET(T, T * pRight),
    FIELDOFFSET(T, T * pParent),
    FIELDOFFSET(T, unsigned int nBalance),
    int (fnCompare)(T * pLeft, T * pRight)
> struct AvlBinTree {
    
    // public data:
    T * ptHead;

    // public methods:
    operator T * ();    // get the head
    operator size_t (); // get the head (comparing to NULL)
    T * first(void);
    T * next(T * ptTemp);
    T * prev(T * ptTemp);
    void insert(T * ptNew);
    void remove(T * ptDel);

    // This structure has no constructor or destructor!
    // It can be initialized with initializer list:
    // AvlBinTree<> tree={NULL};
    // It is designed to act like a regular pointer when possible.
}
*/

#ifndef AVLBINTREE_HPP_
#define AVLBINTREE_HPP_

#ifndef FIELDOFFSET
#define FIELDOFFSET(T, m) ((unsigned int)(&(((T *)0)->m)))
#endif
#ifndef ACCESSFIELD
#define ACCESSFIELD(Tm, p, mo) (*(Tm *)(((char *)p)+mo))
#endif

template <
    class T,
    const unsigned int ofsLeft,
    const unsigned int ofsRight,
    const unsigned int ofsParent,
    const unsigned int ofsBalance,
    int (fnCompare)(T * pLeft, T * pRight)
> struct AvlBinTree {

    T * ptHead;

    //--------------------------------------------------------------------
    // get the head
    operator T * () { return ptHead; }
    operator size_t () { return (size_t)ptHead; }

    //--------------------------------------------------------------------
    // Find the first node
    T * first(void) {
        T * ptTemp=ptHead;
        if (NULL!=ptTemp) {
            while (NULL!=ACCESSFIELD(T *, ptTemp, ofsLeft)) {
                ptTemp=ACCESSFIELD(T *, ptTemp, ofsLeft);
            }
        }
        return ptTemp;
    }

    //--------------------------------------------------------------------
    // Find the next node
    T * next(T * ptTemp) {
        if (NULL==ptTemp) {
            return NULL;
        }
        if (NULL!=ACCESSFIELD(T *, ptTemp, ofsRight)) {
            ptTemp=ACCESSFIELD(T *, ptTemp, ofsRight);
            while (NULL!=ACCESSFIELD(T *, ptTemp, ofsLeft)) {
                ptTemp=ACCESSFIELD(T *, ptTemp, ofsLeft);
            }
            return ptTemp;
        }
        while (true) {
            T * ptParent=ACCESSFIELD(T *, ptTemp, ofsParent);
            if (NULL==ptParent || fnCompare(ptTemp, ptParent)<0) {
                return ptParent;
            } else {
                ptTemp=ptParent;
            }
        }
    }

    //--------------------------------------------------------------------
    // Find the previous node
    T * prev(T * ptTemp) {
        if (NULL==ptTemp) {
            return NULL;
        }
        if (NULL!=ACCESSFIELD(T *, ptTemp, ofsLeft)) {
            ptTemp=ACCESSFIELD(T *, ptTemp, ofsLeft);
            while (NULL!=ACCESSFIELD(T *, ptTemp, ofsRight)) {
                ptTemp=ACCESSFIELD(T *, ptTemp, ofsRight);
            }
            return ptTemp;
        }
        while (true) {
            T * ptParent=ACCESSFIELD(T *, ptTemp, ofsParent);
            if (NULL==ptParent || fnCompare(ptTemp, ptParent)>0) {
                return ptParent;
            } else {
                ptTemp=ptParent;
            }
        }
    }

    //--------------------------------------------------------------------
    // Add a node to the tree
    void insert(T * ptNew)  {

        ACCESSFIELD(T *, ptNew, ofsLeft)=NULL;
        ACCESSFIELD(T *, ptNew, ofsRight)=NULL;
        ACCESSFIELD(unsigned int, ptNew, ofsBalance)=0;

        // if it's the first node, this is easy.
        if (NULL==ptHead) {
            ptHead=ptNew;
            ACCESSFIELD(T *, ptNew, ofsParent)=NULL;
            return;
        }

        // find the insertion point
        T * ptParent=NULL;
        T * ptAncestor=ptHead;
        T ** pptChildPointer=&ptHead;
        while (NULL!=*pptChildPointer) {
            ptParent=*pptChildPointer;
            if (0!=ACCESSFIELD(unsigned int, ptParent, ofsBalance)) {
                // remember the last unbalanced ancestor
                ptAncestor=ptParent;
            }

            if (fnCompare(ptParent, ptNew)>0) {
                pptChildPointer=&(ACCESSFIELD(T *, ptParent, ofsLeft));
            } else {
                pptChildPointer=&(ACCESSFIELD(T *, ptParent, ofsRight));
            }
        }

        // add node to tree
        *pptChildPointer=ptNew;
        ACCESSFIELD(T *, ptNew, ofsParent)=ptParent;

        // All nodes between the new one and the ancestor had balance 0.
        // This is no longer true, so fix it.
        signed int nImbalance;
        T * ptChild=NULL;
        if (fnCompare(ptAncestor, ptNew)>0) {
            ptChild=ACCESSFIELD(T *, ptAncestor, ofsLeft);
            nImbalance=-1;
        } else {
            ptChild=ACCESSFIELD(T *, ptAncestor, ofsRight);
            nImbalance=1;
        }
        T * ptTravel=ptChild;
        while (ptTravel!=ptNew) {
            if (fnCompare(ptTravel, ptNew)>0) {
                ACCESSFIELD(unsigned int, ptTravel, ofsBalance)=-1;
                ptTravel=ACCESSFIELD(T *, ptTravel, ofsLeft);
            } else {
                ACCESSFIELD(unsigned int, ptTravel, ofsBalance)=1;
                ptTravel=ACCESSFIELD(T *, ptTravel, ofsRight);
            }
        }

        // Now, see if the tree needs to be rebalanced
        if (0==ACCESSFIELD(unsigned int, ptAncestor, ofsBalance)) {
            // another level was added to the tree - no problem
            ACCESSFIELD(unsigned int, ptAncestor, ofsBalance)=nImbalance;
            return;
        } else if (ACCESSFIELD(unsigned int, ptAncestor, ofsBalance)!=nImbalance) {
            // new node just balanced the tree
            ACCESSFIELD(unsigned int, ptAncestor, ofsBalance)=0;
            return;
        }

        // Need to rebalance the tree
        if (ACCESSFIELD(unsigned int, ptChild, ofsBalance)==nImbalance) {
            // Ancestor and Child have been unbalanced in the same direction
            if (-1==nImbalance) {
                rotateRight(ptAncestor);
            } else {
                rotateLeft(ptAncestor);
            }
            ACCESSFIELD(unsigned int, ptAncestor, ofsBalance)=0;
            ACCESSFIELD(unsigned int, ptChild, ofsBalance)=0;

        } else {
            // Ancestor and Child are unbalanced in oposite directions!
            if (-1==nImbalance) {
                ptTravel=ACCESSFIELD(T *, ptChild, ofsRight);
                rotateLeft(ptChild);
                rotateRight(ptAncestor);
            } else {
                ptTravel=ACCESSFIELD(T *, ptChild, ofsLeft);
                rotateRight(ptChild);
                rotateLeft(ptAncestor);
            }

            // Adjust balance for involved nodes
            if (0==ACCESSFIELD(unsigned int, ptTravel, ofsBalance)) {
                // Travel was inserted node
                ACCESSFIELD(unsigned int, ptAncestor, ofsBalance)=0;
                ACCESSFIELD(unsigned int, ptChild, ofsBalance)=0;
            } else {
                if (ACCESSFIELD(unsigned int, ptTravel, ofsBalance)==nImbalance) {
                    ACCESSFIELD(unsigned int, ptAncestor, ofsBalance)=-nImbalance;
                    ACCESSFIELD(unsigned int, ptChild, ofsBalance)=0;
                } else {
                    ACCESSFIELD(unsigned int, ptAncestor, ofsBalance)=0;
                    ACCESSFIELD(unsigned int, ptChild, ofsBalance)=nImbalance;
                }
                ACCESSFIELD(unsigned int, ptTravel, ofsBalance)=0;
            }
        }
    }


    //--------------------------------------------------------------------
    // remove a node from the tree
    void remove(T * ptDel) {

        T * ptLastUnbalanced=NULL;
        T * ptLastUnbalancedPrev=NULL;
        bool bSpecialCasePrev=false;

        // standard delete - replace node with left-most right child

        // get the parent pointer
        T ** pptParent;
        if (NULL==ACCESSFIELD(T *, ptDel, ofsParent)) {
            pptParent=&ptHead;
        } else if (fnCompare(ACCESSFIELD(T *, ptDel, ofsParent), ptDel)<0) {
            pptParent=&(ACCESSFIELD(T *, ACCESSFIELD(T *, ptDel, ofsParent), ofsRight));
        } else {
            pptParent=&(ACCESSFIELD(T *, ACCESSFIELD(T *, ptDel, ofsParent), ofsLeft));
        }

        // if there is no right child, then replace the node with its left child
        if (NULL==ACCESSFIELD(T *, ptDel, ofsRight)) {
            ptLastUnbalanced=ACCESSFIELD(T *, ptDel, ofsParent);
            ptLastUnbalancedPrev=ptDel;
            *pptParent=ACCESSFIELD(T *, ptDel, ofsLeft);
            if (NULL!=*pptParent) {
                ACCESSFIELD(T *, (*pptParent), ofsParent)=ACCESSFIELD(T *, ptDel, ofsParent);
                ACCESSFIELD(unsigned int, (*pptParent), ofsBalance)=0;
            }

        // if there is a right child but it has no left child, then replace the node with its right child
        } else if (NULL==ACCESSFIELD(T *, ACCESSFIELD(T *, ptDel, ofsRight), ofsLeft)) {
            ptLastUnbalanced=ACCESSFIELD(T *, ptDel, ofsRight);
            ptLastUnbalancedPrev=ptLastUnbalanced; 
            bSpecialCasePrev=true; // special case - ptLastUnbalancedPrev can't be used.
            // fix del's left child
            ACCESSFIELD(T *, ACCESSFIELD(T *, ptDel, ofsRight), ofsLeft)=ACCESSFIELD(T *, ptDel, ofsLeft);
            if (NULL!=ACCESSFIELD(T *, ptDel, ofsLeft)) {
                ACCESSFIELD(T *, ACCESSFIELD(T *, ptDel, ofsLeft), ofsParent)=ACCESSFIELD(T *, ptDel, ofsRight);
            }
            // fix del's parent
            *pptParent=ACCESSFIELD(T *, ptDel, ofsRight);
            ACCESSFIELD(T *, (*pptParent), ofsParent)=ACCESSFIELD(T *, ptDel, ofsParent);
            ACCESSFIELD(unsigned int, (*pptParent), ofsBalance)=ACCESSFIELD(unsigned int, ptDel, ofsBalance);

        // replace the node with the left most child of its right child
        } else {
            // find it
            T * ptReplacement=ACCESSFIELD(T *, ACCESSFIELD(T *, ptDel, ofsRight), ofsLeft);
            while (NULL!=ACCESSFIELD(T *, ptReplacement, ofsLeft)) {
                ptReplacement=ACCESSFIELD(T *, ptReplacement, ofsLeft);
            }
            ptLastUnbalanced=ACCESSFIELD(T *, ptReplacement, ofsParent);
            ptLastUnbalancedPrev=ptDel;
            // fix replacement's right child
            ACCESSFIELD(T *, ACCESSFIELD(T *, ptReplacement, ofsParent), ofsLeft)=ACCESSFIELD(T *, ptReplacement, ofsRight);
            if (NULL!=ACCESSFIELD(T *, ptReplacement, ofsRight)) {
                ACCESSFIELD(T *, ACCESSFIELD(T *, ptReplacement, ofsRight), ofsParent)=ACCESSFIELD(T *, ptReplacement, ofsParent);
            }
            // fix del's right child
            ACCESSFIELD(T *, ptReplacement, ofsRight)=ACCESSFIELD(T *, ptDel, ofsRight);
            ACCESSFIELD(T *, ACCESSFIELD(T *, ptDel, ofsRight), ofsParent)=ptReplacement;
            // fix del's left child
            ACCESSFIELD(T *, ptReplacement, ofsLeft)=ACCESSFIELD(T *, ptDel, ofsLeft);
            if (NULL!=ACCESSFIELD(T *, ptDel, ofsLeft)) {
                ACCESSFIELD(T *, ACCESSFIELD(T *, ptDel, ofsLeft), ofsParent)=ptReplacement;
            }
            // fix del's parent
            *pptParent=ptReplacement;
            ACCESSFIELD(T *, ptReplacement, ofsParent)=ACCESSFIELD(T *, ptDel, ofsParent);
            ACCESSFIELD(unsigned int, ptReplacement, ofsBalance)=ACCESSFIELD(unsigned int, ptDel, ofsBalance);

        }
        // now, balance
        while (NULL!=ptLastUnbalanced) {

            if (!bSpecialCasePrev && fnCompare(ptLastUnbalancedPrev, ptLastUnbalanced)<0) { //(-1==nTraverseDir)

                // if the node was heavy on the side we lightenend, then the node is 
                // now balanced, but we must check the parent
                if (-1==ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)) {
                    ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)=0;
                    ptLastUnbalancedPrev=ptLastUnbalanced;
                    ptLastUnbalanced=ACCESSFIELD(T *, ptLastUnbalanced, ofsParent);
                    continue;
                // if the node was balanced, now it is not, but the tree is fine
                } else if (0==ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)) {
                    ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)=1;
                    break;
                } 
                // thus (1==ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance))
                // We lightened the light side, so we must rebalance the node
                T * ptChild=ACCESSFIELD(T *, ptLastUnbalanced, ofsRight);

                // if child is balanced, a rotate left will fix it, leaving
                // both unbalanced, but the tree OK
                if (0==ACCESSFIELD(unsigned int, ptChild, ofsBalance)) {
                    rotateLeft(ptLastUnbalanced);
                    ACCESSFIELD(unsigned int, ptChild, ofsBalance)=-1;
                    break;

                // if child is also light on the same side, a rotate left 
                // will fix this level, but we must keep checking up the tree
                } else if (1==ACCESSFIELD(unsigned int, ptChild, ofsBalance)) {
                    rotateLeft(ptLastUnbalanced);
                    ACCESSFIELD(unsigned int, ptChild, ofsBalance)=0;
                    ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)=0;
                    // the child took the node's place.
                    ptLastUnbalanced=ptChild;

                // child and node unbalanced in opposite directions. Need to 
                // double rotate and keep checking tree
                } else {
                    T * ptGrandChild=ACCESSFIELD(T *, ptChild, ofsLeft);
                    rotateRight(ptChild);
                    rotateLeft(ptLastUnbalanced);
                    // node and child are now left and right children of grandchild
                    if (1==ACCESSFIELD(unsigned int, ptGrandChild, ofsBalance)) {
                        ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)=-1;
                        ACCESSFIELD(unsigned int, ptChild, ofsBalance)=0;
                    } else if (0==ACCESSFIELD(unsigned int, ptGrandChild, ofsBalance)) {
                        ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)=0;
                        ACCESSFIELD(unsigned int, ptChild, ofsBalance)=0;
                    } else { //(-1==ACCESSFIELD(unsigned int, ptGrandChild, ofsBalance))
                        ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)=0;
                        ACCESSFIELD(unsigned int, ptChild, ofsBalance)=1;
                    }
                    ACCESSFIELD(unsigned int, ptGrandChild, ofsBalance)=0;
                    // the grandchild took the node's place.
                    ptLastUnbalanced=ptGrandChild;
                }

            } else { //(1==nTraverseDir)
                bSpecialCasePrev=false;

                // if the node was heavy on the side we lightenend, then the node is 
                // now balanced, but we must check the parent
                if (1==ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)) {
                    ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)=0;
                    ptLastUnbalancedPrev=ptLastUnbalanced;
                    ptLastUnbalanced=ACCESSFIELD(T *, ptLastUnbalanced, ofsParent);
                    continue;
                // if the node was balanced, now it is not, but the tree is fine
                } else if (0==ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)) {
                    ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)=-1;
                    break;
                } 
                // thus (-1==ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance))
                // We lightened the light side, so we must rebalance the node
                T * ptChild=ACCESSFIELD(T *, ptLastUnbalanced, ofsLeft);

                // if child is balanced, a rotate right will fix it, leaving
                // both unbalanced, but the tree OK
                if (0==ACCESSFIELD(unsigned int, ptChild, ofsBalance)) {
                    rotateRight(ptLastUnbalanced);
                    ACCESSFIELD(unsigned int, ptChild, ofsBalance)=1;
                    break;

                // if child is also light on the same side, a rotate right 
                // will fix this level, but we must keep checking up the tree
                } else if (-1==ACCESSFIELD(unsigned int, ptChild, ofsBalance)) {
                    rotateRight(ptLastUnbalanced);
                    ACCESSFIELD(unsigned int, ptChild, ofsBalance)=0;
                    ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)=0;
                    // the child took the node's place.
                    ptLastUnbalanced=ptChild;

                // child and node unbalanced in opposite directions. Need to 
                // double rotate and keep checking tree
                } else {
                    T * ptGrandChild=ACCESSFIELD(T *, ptChild, ofsRight);
                    rotateLeft(ptChild);
                    rotateRight(ptLastUnbalanced);
                    // child and node are now left and right children of grandchild
                    if (-1==ACCESSFIELD(unsigned int, ptGrandChild, ofsBalance)) {
                        ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)=1;
                        ACCESSFIELD(unsigned int, ptChild, ofsBalance)=0;
                    } else if (0==ACCESSFIELD(unsigned int, ptGrandChild, ofsBalance)) {
                        ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)=0;
                        ACCESSFIELD(unsigned int, ptChild, ofsBalance)=0;
                    } else { //(1==ACCESSFIELD(unsigned int, ptGrandChild, ofsBalance))
                        ACCESSFIELD(unsigned int, ptLastUnbalanced, ofsBalance)=0;
                        ACCESSFIELD(unsigned int, ptChild, ofsBalance)=-1;
                    }
                    ACCESSFIELD(unsigned int, ptGrandChild, ofsBalance)=0;
                    // the grandchild took the node's place.
                    ptLastUnbalanced=ptGrandChild;
                }

            } // end if (1==nTraverseDir)

            // move up the tree
            ptLastUnbalancedPrev=ptLastUnbalanced;
            ptLastUnbalanced=ACCESSFIELD(T *, ptLastUnbalanced, ofsParent);

        } // <- end rebalancing loop

        // done
    }

//private: // would be private, but you can't use an initializer list if it is

    //--------------------------------------------------------------------
    // rotate a node right in the tree
    // Given node becomes right descendent of its left descendent
    void rotateRight(T * ptNode) {

        T * ptChild=ACCESSFIELD(T *, ptNode, ofsLeft);
        ACCESSFIELD(T *, ptNode, ofsLeft)=ACCESSFIELD(T *, ptChild, ofsRight);
        if (NULL!=ACCESSFIELD(T *, ptNode, ofsLeft)) {
            ACCESSFIELD(T *, ACCESSFIELD(T *, ptNode, ofsLeft), ofsParent)=ptNode;
        }
        ACCESSFIELD(T *, ptChild, ofsRight)=ptNode;
        ACCESSFIELD(T *, ptChild, ofsParent)=ACCESSFIELD(T *, ptNode, ofsParent);
        ACCESSFIELD(T *, ptNode, ofsParent)=ptChild;
        if (NULL==ACCESSFIELD(T *, ptChild, ofsParent)) {
            ptHead=ptChild;
        } else if (ACCESSFIELD(T *, ACCESSFIELD(T *, ptChild, ofsParent), ofsLeft)==ptNode) {
            ACCESSFIELD(T *, ACCESSFIELD(T *, ptChild, ofsParent), ofsLeft)=ptChild;
        } else {
            ACCESSFIELD(T *, ACCESSFIELD(T *, ptChild, ofsParent), ofsRight)=ptChild;
        }
    }

    //--------------------------------------------------------------------
    // rotate a node left in the tree
    // Given node becomes left descendent of its right descendent
    void rotateLeft(T * ptNode) {

        T * ptChild=ACCESSFIELD(T *, ptNode, ofsRight);
        ACCESSFIELD(T *, ptNode, ofsRight)=ACCESSFIELD(T *, ptChild, ofsLeft);
        if (NULL!=ACCESSFIELD(T *, ptNode, ofsRight)) {
            ACCESSFIELD(T *, ACCESSFIELD(T *, ptNode, ofsRight), ofsParent)=ptNode;
        }
        ACCESSFIELD(T *, ptChild, ofsLeft)=ptNode;
        ACCESSFIELD(T *, ptChild, ofsParent)=ACCESSFIELD(T *, ptNode, ofsParent);
        ACCESSFIELD(T *, ptNode, ofsParent)=ptChild;
        if (NULL==ACCESSFIELD(T *, ptChild, ofsParent)) {
            ptHead=ptChild;
        } else if (ACCESSFIELD(T *, ACCESSFIELD(T *, ptChild, ofsParent), ofsRight)==ptNode) {
            ACCESSFIELD(T *, ACCESSFIELD(T *, ptChild, ofsParent), ofsRight)=ptChild;
        } else {
            ACCESSFIELD(T *, ACCESSFIELD(T *, ptChild, ofsParent), ofsLeft)=ptChild;
        }
    }


};
#endif //AVLBINTREE_HPP_