stgavl.cxx

Go to the documentation of this file.

/* -*- 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;
 
    OSL_ENSURE( 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
    OSL_ENSURE( pHeavy && pNew, "The pointers is not allowed to be NULL!" );
    if( pCur == pNew || !pNew )
        return m_nBalance;
 
    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.
 
 
 
// 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: */