/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */

/*

 * This file is part of the LibreOffice project.

 *

 * This Source Code Form is subject to the terms of the Mozilla Public

 * License, v. 2.0. If a copy of the MPL was not distributed with this

 * file, You can obtain one at http://mozilla.org/MPL/2.0/.

 *

 * This file incorporates work covered by the following license notice:

 *

 *   Licensed to the Apache Software Foundation (ASF) under one or more

 *   contributor license agreements. See the NOTICE file distributed

 *   with this work for additional information regarding copyright

 *   ownership. The ASF licenses this file to you under the Apache

 *   License, Version 2.0 (the "License"); you may not use this file

 *   except in compliance with the License. You may obtain a copy of

 *   the License at http://www.apache.org/licenses/LICENSE-2.0 .

 */

#include <osl/diagnose.h>

#include "stgavl.hxx"

#include <assert.h>

StgAvlNode::StgAvlNode()

{

    m_pLeft = m_pRight = nullptr;

    m_nBalance = m_nId = 0;

}

StgAvlNode::~StgAvlNode()

{

    delete m_pLeft;

    delete m_pRight;

}

StgAvlNode* StgAvlNode::Find( StgAvlNode const * pFind )

{

    if ( pFind )

    {

        StgAvlNode* p = this;

        while( p )

        {

            sal_Int32 nRes = p->Compare( pFind );

            if( !nRes )

                return p;

            else p = ( nRes < 0 ) ? p->m_pLeft : p->m_pRight;

        }

    }

    return nullptr;

}

// find point to add node to AVL tree and returns

// +/0/- for >/=/< previous

sal_Int32 StgAvlNode::Locate

    ( StgAvlNode const * pFind,

      StgAvlNode** pPivot, StgAvlNode **pParent, StgAvlNode** pPrev )

{

    sal_Int32 nRes = 0;

    StgAvlNode* pCur = this;

    assert(pPivot && pParent && pPrev && "The pointers may not be NULL!");

    *pParent = *pPrev = nullptr;

    *pPivot = this;

    // search tree for insertion point

    if ( pFind )

    {

        while( pCur != nullptr )

        {

            // check for pPivot

            if( pCur->m_nBalance != 0 )

            {

                *pPivot = pCur;

                *pParent = *pPrev;

            }

            // save pPrev location and see what direction to go

            *pPrev = pCur;

            nRes = pCur->Compare( pFind );

            if( nRes == 0 )

                break;

            else pCur = ( nRes < 0 ) ? pCur->m_pLeft : pCur->m_pRight;

        }

    }

    return nRes;

}

// adjust balance factors in AVL tree from pivot down.

// Returns delta balance.

short StgAvlNode::Adjust( StgAvlNode** pHeavy, StgAvlNode const * pNew )

{

    StgAvlNode* pCur = this;

    short nDelta;

    // no traversing

    if( pCur == pNew || !pNew )

        return m_nBalance;

    assert(pHeavy && pNew && "The pointers is not allowed to be NULL!");

    sal_Int32 nRes = Compare( pNew );

    if( nRes > 0 )

    {

        *pHeavy = pCur = m_pRight;

        nDelta = -1;

    }

    else

    {

        *pHeavy = pCur = m_pLeft;

        nDelta = 1;

    }

    m_nBalance = 0;

    while( pCur != pNew )

    {

        nRes = pCur->Compare( pNew );

        if( nRes > 0 )

        {

            // height of right increases by 1

            pCur->m_nBalance = -1;

            pCur = pCur->m_pRight;

        }

        else

        {

            // height of left increases by 1

            pCur->m_nBalance = 1;

            pCur = pCur->m_pLeft;

        }

    }

    m_nBalance = m_nBalance + nDelta;

    return nDelta;

}

// perform LL rotation and return new root

StgAvlNode* StgAvlNode::RotLL()

{

    assert(m_pLeft && "The pointer is not allowed to be NULL!");

    StgAvlNode *pHeavy = m_pLeft;

    m_pLeft = pHeavy->m_pRight;

    pHeavy->m_pRight = this;

    pHeavy->m_nBalance = m_nBalance = 0;

    return pHeavy;

}

// perform LR rotation and return new root

StgAvlNode* StgAvlNode::RotLR()

{

    assert(m_pLeft && m_pLeft->m_pRight && "The pointer is not allowed to be NULL!");

    StgAvlNode* pHeavy = m_pLeft;

    StgAvlNode* pNewRoot = pHeavy->m_pRight;

    pHeavy->m_pRight = pNewRoot->m_pLeft;

    m_pLeft = pNewRoot->m_pRight;

    pNewRoot->m_pLeft = pHeavy;

    pNewRoot->m_pRight = this;

    switch( pNewRoot->m_nBalance )

    {

        case 1:     // LR( b )

            m_nBalance = -1;

            pHeavy->m_nBalance = 0;

            break;

        case -1:    // LR( c )

            pHeavy->m_nBalance = 1;

            m_nBalance = 0;

            break;

        case 0:     // LR( a )

            m_nBalance = 0;

            pHeavy->m_nBalance = 0;

            break;

    }

    pNewRoot->m_nBalance = 0;

    return pNewRoot;

}

// perform RR rotation and return new root

StgAvlNode* StgAvlNode::RotRR()

{

    assert(m_pRight && "The pointer is not allowed to be NULL!" );

    StgAvlNode* pHeavy = m_pRight;

    m_pRight = pHeavy->m_pLeft;

    pHeavy->m_pLeft = this;

    m_nBalance = pHeavy->m_nBalance = 0;

    return pHeavy;

}

// perform the RL rotation and return the new root

StgAvlNode* StgAvlNode::RotRL()

{

    assert(m_pRight && m_pRight->m_pLeft && "The pointer is not allowed to be NULL!");

    StgAvlNode* pHeavy = m_pRight;

    StgAvlNode* pNewRoot = pHeavy->m_pLeft;

    pHeavy->m_pLeft = pNewRoot->m_pRight;

    m_pRight = pNewRoot->m_pLeft;

    pNewRoot->m_pRight = pHeavy;

    pNewRoot->m_pLeft = this;

    switch( pNewRoot->m_nBalance )

    {

        case -1:    // RL( b )

            m_nBalance = 1;

            pHeavy->m_nBalance = 0;

            break;

        case 1:     // RL( c )

            pHeavy->m_nBalance = -1;

            m_nBalance = 0;

            break;

        case 0:     // RL( a )

            m_nBalance = 0;

            pHeavy->m_nBalance = 0;

            break;

    }

    pNewRoot->m_nBalance = 0;

    return pNewRoot;

}

// Remove a tree element. Return the removed element or NULL.

StgAvlNode* StgAvlNode::Rem( StgAvlNode** p, StgAvlNode* pDel, bool bPtrs )

{

    if( p && *p && pDel )

    {

        StgAvlNode* pCur = *p;

        sal_Int32 nRes = bPtrs ? sal_Int32( pCur == pDel ) : pCur->Compare( pDel );

        if( !nRes )

        {

            // Element found: remove

            if( !pCur->m_pRight )

            {

                *p = pCur->m_pLeft; pCur->m_pLeft = nullptr;

            }

            else if( !pCur->m_pLeft )

            {

                *p = pCur->m_pRight; pCur->m_pRight = nullptr;

            }

            else

            {

                // The damn element has two leaves. Get the

                // rightmost element of the left subtree (which

                // is lexically before this element) and replace

                // this element with the element found.

                StgAvlNode* last = pCur;

                StgAvlNode* l;

                for( l = pCur->m_pLeft;

                     l->m_pRight; last = l, l = l->m_pRight ) {}

                // remove the element from chain

                if( l == last->m_pRight )

                    last->m_pRight = l->m_pLeft;

                else

                    last->m_pLeft = l->m_pLeft;

                // perform the replacement

                l->m_pLeft = pCur->m_pLeft;

                l->m_pRight = pCur->m_pRight;

                *p = l;

                // delete the element

                pCur->m_pLeft = pCur->m_pRight = nullptr;

            }

            return pCur;

        }

        else

        {

            if( nRes < 0 )

                return Rem( &pCur->m_pLeft, pDel, bPtrs );

            else

                return Rem( &pCur->m_pRight, pDel, bPtrs );

        }

    }

    return nullptr;

}

// Enumerate the tree for later iteration

void StgAvlNode::StgEnum( short& n )

{

    if( m_pLeft )

        m_pLeft->StgEnum( n );

    m_nId = n++;

    if( m_pRight )

        m_pRight->StgEnum( n );

}

// Add node to AVL tree.

// Return false if the element already exists.

bool StgAvlNode::Insert( StgAvlNode** pRoot, StgAvlNode* pIns )

{

    StgAvlNode* pPivot, *pHeavy, *pParent, *pPrev;

    if ( !pRoot )

        return false;

    // special case - empty tree

    if( *pRoot == nullptr )

    {

        *pRoot = pIns;

        return true;

    }

    // find insertion point and return if already present

    sal_Int32 nRes = (*pRoot)->Locate( pIns, &pPivot, &pParent, &pPrev );

    if( !nRes )

        return false;

    assert(pPivot && pPrev && "The pointers may not be NULL!");

    // add new node

    if( nRes < 0 )

        pPrev->m_pLeft = pIns;

    else

        pPrev->m_pRight = pIns;

    // rebalance tree

    short nDelta = pPivot->Adjust( &pHeavy, pIns );

    if( pPivot->m_nBalance >= 2 || pPivot->m_nBalance <= -2 )

    {

        StgAvlNode* pNewRoot;

        pHeavy = ( nDelta < 0 ) ? pPivot->m_pRight : pPivot->m_pLeft;

        // left imbalance

        if( nDelta > 0 )

            if( pHeavy->m_nBalance == 1 )

                pNewRoot = pPivot->RotLL();

            else

                pNewRoot = pPivot->RotLR();

        // right imbalance

        else if( pHeavy->m_nBalance == -1 )

            pNewRoot = pPivot->RotRR();

        else

            pNewRoot = pPivot->RotRL();

        // relink balanced subtree

        if( pParent == nullptr )

            *pRoot = pNewRoot;

        else if( pPivot == pParent->m_pLeft )

            pParent->m_pLeft = pNewRoot;

        else if( pPivot == pParent->m_pRight )

            pParent->m_pRight = pNewRoot;

    }

    return true;

}

// Remove node from tree. Returns true is found and removed.

// Actually delete if bDel

bool StgAvlNode::Remove( StgAvlNode** pRoot, StgAvlNode* pDel, bool bDel )

{

    if ( !pRoot )

        return false;

    // special case - empty tree

    if( *pRoot == nullptr )

        return false;

    // delete the element

    pDel = Rem( pRoot, pDel, false );

    if( pDel )

    {

        if( bDel )

            delete pDel;

        // Rebalance the tree the hard way

        // OS 22.09.95: On MD's request commented out due to crash

/*      StgAvlNode* pNew = NULL;

        while( *pRoot )

        {

            StgAvlNode* p = Rem( pRoot, *pRoot, false );

            Insert( &pNew, p );

        }

        *pRoot = pNew;*/

        return true;

    }

    else

        return false;

}

// Move node to a different tree. Returns true is found and moved. This routine

// may be called when the key has changed.

////////////////////////// class AvlIterator

// The iterator walks through a tree one entry by one.

StgAvlIterator::StgAvlIterator( StgAvlNode* p )

{

    m_pRoot = p;

    m_nCur = 0;

    if( p )

    {

        short nCount = 0; // tree size

        p->StgEnum( nCount );

    }

}

StgAvlNode* StgAvlIterator::Find( short n )

{

    StgAvlNode* p = m_pRoot;

    while( p )

    {

        if( n == p->m_nId )

            break;

        else p = ( n < p->m_nId ) ? p->m_pLeft : p->m_pRight;

    }

    return p;

}

StgAvlNode* StgAvlIterator::First()

{

    m_nCur = -1;

    return Next();

}

StgAvlNode* StgAvlIterator::Next()

{

    return Find( ++m_nCur );

}

/* vim:set shiftwidth=4 softtabstop=4 expandtab: */