LCOV - code coverage report
Current view: top level - rsc/source/tools - rsctree.cxx (source / functions) Hit Total Coverage
Test: commit e02a6cb2c3e2b23b203b422e4e0680877f232636 Lines: 0 187 0.0 %
Date: 2014-04-14 Functions: 0 23 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
       2             : /*
       3             :  * This file is part of the LibreOffice project.
       4             :  *
       5             :  * This Source Code Form is subject to the terms of the Mozilla Public
       6             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       7             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       8             :  *
       9             :  * This file incorporates work covered by the following license notice:
      10             :  *
      11             :  *   Licensed to the Apache Software Foundation (ASF) under one or more
      12             :  *   contributor license agreements. See the NOTICE file distributed
      13             :  *   with this work for additional information regarding copyright
      14             :  *   ownership. The ASF licenses this file to you under the Apache
      15             :  *   License, Version 2.0 (the "License"); you may not use this file
      16             :  *   except in compliance with the License. You may obtain a copy of
      17             :  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
      18             :  */
      19             : 
      20             : 
      21             : #include <stdlib.h>
      22             : #include <stdio.h>
      23             : #include <string.h>
      24             : 
      25             : #include <tools/link.hxx>
      26             : #include <rsctree.hxx>
      27             : 
      28             : 
      29           0 : BiNode::BiNode()
      30             : {
      31           0 :     pLeft = pRight = NULL;
      32           0 : }
      33             : 
      34           0 : BiNode::~BiNode()
      35             : {
      36           0 : }
      37             : 
      38           0 : void BiNode::EnumNodes( Link aLink ) const
      39             : {
      40           0 :     if( Left() )
      41           0 :         Left()->EnumNodes( aLink );
      42           0 :     aLink.Call( (BiNode *)this );
      43           0 :     if( Right() )
      44           0 :         Right()->EnumNodes( aLink );
      45           0 : }
      46             : 
      47           0 : BiNode * BiNode::ChangeDLListBTree( BiNode * pList )
      48             : {
      49             :     BiNode * pMiddle;
      50             :     BiNode * pTmp;
      51             :     sal_uInt32 nEle, i;
      52             : 
      53           0 :     if( pList )
      54             : {
      55           0 :         while( pList->Left() )
      56           0 :             pList = pList->Left();
      57           0 :         pTmp = pList;
      58             : 
      59           0 :         for( nEle = 0; pTmp->Right(); nEle++ )
      60           0 :             pTmp = pTmp->Right();
      61             : 
      62           0 :         pMiddle = pList;
      63           0 :         if( nEle / 2 )
      64             :         {
      65           0 :             for( i = 0; i < (nEle / 2); i++ )
      66             :             {
      67           0 :                 pMiddle = pMiddle->Right();
      68             :             }
      69             :         }
      70             :         else
      71             :         {
      72           0 :             pList = (BiNode *)0;
      73             :         }
      74           0 :         if( NULL != (pTmp = pMiddle->Left()) )  // rechten Zeiger auf Null
      75           0 :             pTmp->pRight = (BiNode *)0;
      76             : 
      77             :         // linken Zeiger auf Null
      78           0 :         BiNode * pRightNode = pMiddle->Right();
      79           0 :         if (pRightNode)
      80           0 :             pRightNode->pLeft = (BiNode *)0;
      81             : 
      82           0 :         pMiddle->pLeft = ChangeDLListBTree( pList );
      83           0 :         pMiddle->pRight = ChangeDLListBTree( pRightNode );
      84             : 
      85           0 :         return pMiddle;
      86             :     }
      87           0 :     return pList;
      88             : }
      89             : 
      90           0 : BiNode * BiNode::ChangeBTreeDLList()
      91             : {
      92             :     BiNode * pList;
      93             :     BiNode * pLL_RN;    // linke Liste rechter Knoten
      94             : 
      95           0 :     if( Right() )
      96             :     {
      97           0 :         pList = Right()->ChangeBTreeDLList();
      98           0 :         pRight = pList;
      99           0 :         pList->pLeft = this;
     100             :     }
     101           0 :     pList = this;
     102           0 :     if( Left() )
     103             :     {
     104           0 :         pLL_RN = pList = Left()->ChangeBTreeDLList();
     105             : 
     106           0 :         while( pLL_RN->Right() )
     107           0 :             pLL_RN = pLL_RN->Right();
     108             : 
     109           0 :         pLeft = pLL_RN;
     110           0 :         pLL_RN->pRight = this;
     111             :     }
     112           0 :     return pList;
     113             : }
     114             : 
     115           0 : NameNode * NameNode::Remove( NameNode * pRemove )
     116             : {
     117           0 :     NameNode * pRoot = this;
     118           0 :     NameNode * pParent = SearchParent( pRemove );
     119             : 
     120           0 :     if( pParent )
     121             :     {
     122           0 :         if( pParent->Left() &&
     123           0 :             (EQUAL == pRemove->Compare( pParent->Left() ) ) )
     124             :         {
     125           0 :             pParent->pLeft = pRemove->Left();
     126           0 :             if( pRemove->Right() )
     127           0 :                 pParent->Insert( pRemove->Right() );
     128             :         }
     129           0 :         else if( pParent->Right() &&
     130           0 :                  (EQUAL == pRemove->Compare( pParent->Right() ) ) )
     131             :         {
     132           0 :             pParent->pRight = pRemove->Right();
     133           0 :             if( pRemove->Left() )
     134           0 :                 pParent->Insert( pRemove->Left() );
     135             :         }
     136             :     }
     137           0 :     else if( EQUAL == this->Compare( pRemove ) )
     138             :     {
     139           0 :         if( Right() )
     140             :         {
     141           0 :             pRoot = Right();
     142           0 :             if( Left() )
     143           0 :                 Right()->Insert( Left() );
     144             :         }
     145             :         else
     146             :         {
     147           0 :             pRoot = Left();
     148             :         }
     149             :     }
     150           0 :     pRemove->pLeft = pRemove->pRight = NULL;
     151             : 
     152           0 :     return pRoot;
     153             : }
     154             : 
     155             : 
     156           0 : COMPARE NameNode::Compare( const NameNode * pCompare ) const
     157             : {
     158           0 :     if( (long)this < (long)pCompare )
     159           0 :         return LESS;
     160           0 :     else if( (long)this > (long)pCompare )
     161           0 :         return GREATER;
     162             :     else
     163           0 :         return EQUAL;
     164             : }
     165             : 
     166           0 : COMPARE NameNode::Compare( const void * pCompare ) const
     167             : {
     168           0 :     if( (long)this < (long)pCompare )
     169           0 :         return LESS;
     170           0 :     else if( (long)this > (long)pCompare )
     171           0 :         return GREATER;
     172             :     else
     173           0 :         return EQUAL;
     174             : }
     175             : 
     176             : // search for a parent node.
     177             : // return a pointer to the parent node if found.
     178             : // otherwise return 0.
     179           0 : NameNode* NameNode::SearchParent( const NameNode * pSearch ) const
     180             : {
     181           0 :     int nCmp = Compare( pSearch );
     182             : 
     183           0 :     if( nCmp == GREATER )
     184             :     {
     185           0 :         if( Left() )
     186             :         {
     187           0 :             if( ((NameNode *)Left())->Compare( pSearch ) == EQUAL )
     188           0 :                 return (NameNode *)this;
     189           0 :             return ((NameNode *)Left())->SearchParent( pSearch );
     190             :         };
     191             :     }
     192           0 :     else if( nCmp == LESS )
     193             :     {
     194           0 :         if( Right() )
     195             :         {
     196           0 :             if( ((NameNode *)Right())->Compare( pSearch ) == EQUAL )
     197           0 :                 return (NameNode *)this;
     198           0 :             return ((NameNode *)Right())->SearchParent( pSearch );
     199             :         }
     200             :     }
     201           0 :     return (NameNode *)NULL;
     202             : }
     203             : 
     204             : // search for a node.
     205             : // return a pointer to the node if found.
     206             : // otherwise return 0.
     207           0 : NameNode* NameNode::Search( const NameNode * pSearch ) const
     208             : {
     209           0 :     int nCmp = Compare( pSearch );
     210             : 
     211           0 :     if( nCmp == GREATER )
     212             :     {
     213           0 :         if( Left() )
     214           0 :             return ((NameNode *)Left())->Search( pSearch );
     215             :     }
     216           0 :     else if( nCmp == LESS )
     217             :     {
     218           0 :         if( Right() )
     219           0 :             return ((NameNode *)Right())->Search( pSearch );
     220             :     }
     221             :     else
     222           0 :         return (NameNode *)this;
     223             : 
     224           0 :     return NULL;
     225             : }
     226             : 
     227             : // search for a node.
     228             : // return a pointer to the node if found.
     229             : // otherwise return 0.
     230           0 : NameNode* NameNode::Search( const void * pSearch ) const
     231             : {
     232           0 :     int nCmp = Compare( pSearch );
     233             : 
     234           0 :     if( nCmp == GREATER )
     235             :     {
     236           0 :         if( Left() )
     237           0 :             return ((NameNode *)Left())->Search( pSearch );
     238             :     }
     239           0 :     else if( nCmp == LESS )
     240             :     {
     241           0 :         if( Right() )
     242           0 :             return ((NameNode *)Right())->Search( pSearch );
     243             :     }
     244             :     else
     245           0 :         return (NameNode *)this;
     246             : 
     247           0 :     return NULL;
     248             : }
     249             : 
     250             : // Ein Knoten wird in den Baum eingefuegt
     251             : // Gibt es einen Knoten mit dem gleichen Namen, dann return false
     252             : // sonst return true. Der Knoten wird auf jeden Fall eingefuegt.
     253             : 
     254           0 : bool NameNode::Insert( NameNode * pTN, sal_uInt32* pnDepth )
     255             : {
     256           0 :     bool bRet = true;
     257           0 :     int nCmp = Compare( pTN );
     258             : 
     259           0 :     *pnDepth += 1;
     260           0 :     if( nCmp == GREATER )
     261             :     {
     262           0 :         if( Left() )
     263           0 :             bRet =  ((NameNode *)Left())->Insert( pTN, pnDepth );
     264             :         else
     265           0 :             pLeft = pTN;
     266             :     }
     267             :     else
     268             :     {
     269           0 :         if( Right() )
     270           0 :             bRet = ((NameNode *)Right())->Insert( pTN, pnDepth );
     271             :         else
     272           0 :             pRight = pTN;
     273             : 
     274           0 :         if( nCmp == EQUAL )
     275           0 :             bRet = false;
     276             :     }
     277           0 :     return bRet;
     278             : }
     279             : 
     280             : // insert a node in the tree.
     281             : // if the node with the same name is in, return false and no insert.
     282             : // if not return true.
     283           0 : bool NameNode::Insert( NameNode * pTN )
     284             : {
     285           0 :     sal_uInt32  nDepth = 0;
     286             :     bool        bRet;
     287             : 
     288           0 :     bRet = Insert( pTN, &nDepth );
     289           0 :     if( bRet )
     290             :     {
     291           0 :         if( nDepth > 20 )
     292             :         {
     293           0 :             if( Left() )
     294           0 :                 pLeft =  ChangeDLListBTree(  Left()->ChangeBTreeDLList() );
     295           0 :             if( Right() )
     296           0 :                 pRight = ChangeDLListBTree( Right()->ChangeBTreeDLList() );
     297             :         }
     298             :     }
     299             : 
     300           0 :     return bRet;
     301             : }
     302             : 
     303           0 : void NameNode::OrderTree()
     304             : {
     305           0 :     NameNode * pTmpLeft = (NameNode *)Left();
     306           0 :     NameNode * pTmpRight = (NameNode *)Right();
     307             : 
     308           0 :     pLeft = NULL;
     309           0 :     pRight = NULL;
     310           0 :     SubOrderTree( pTmpLeft );
     311           0 :     SubOrderTree( pTmpRight );
     312           0 : }
     313             : 
     314           0 : void NameNode::SubOrderTree( NameNode * pOrderNode )
     315             : {
     316           0 :     if( pOrderNode )
     317             :     {
     318           0 :         NameNode * pTmpLeft = (NameNode *)pOrderNode->Left();
     319           0 :         NameNode * pTmpRight = (NameNode *)pOrderNode->Right();
     320           0 :         pOrderNode->pLeft = NULL;
     321           0 :         pOrderNode->pRight = NULL;
     322           0 :         Insert( pOrderNode );
     323           0 :         SubOrderTree( pTmpLeft );
     324           0 :         SubOrderTree( pTmpRight );
     325             :     }
     326           0 : }
     327             : 
     328           0 : IdNode * IdNode::Search( sal_uInt32 nTypeName ) const
     329             : {
     330           0 :     return (IdNode *)NameNode::Search( (const void *)&nTypeName );
     331             : }
     332             : 
     333           0 : COMPARE IdNode::Compare( const NameNode * pSearch ) const
     334             : {
     335           0 :     if( GetId() < (sal_uInt32)(((const IdNode *)pSearch)->GetId()) )
     336           0 :         return LESS;
     337           0 :     else if( GetId() > (sal_uInt32)(((const IdNode *)pSearch)->GetId()) )
     338           0 :         return GREATER;
     339             :     else
     340           0 :         return EQUAL;
     341             : }
     342             : 
     343             : // pSearch ist ein Zeiger auf sal_uInt32
     344           0 : COMPARE IdNode::Compare( const void * pSearch ) const
     345             : {
     346           0 :     if( GetId() < *((const sal_uInt32 *)pSearch) )
     347           0 :         return LESS;
     348           0 :     else if( GetId() > *((const sal_uInt32 *)pSearch) )
     349           0 :         return GREATER;
     350             :     else
     351           0 :         return EQUAL;
     352             : }
     353             : 
     354           0 : sal_uInt32 IdNode::GetId() const
     355             : {
     356           0 :     return 0xFFFFFFFF;
     357             : }
     358             : 
     359           0 : StringNode * StringNode::Search( const char * pSearch ) const
     360             : {
     361           0 :     return (StringNode *)NameNode::Search( (const void *)pSearch );
     362             : }
     363             : 
     364           0 : COMPARE StringNode::Compare( const NameNode * pSearch ) const
     365             : {
     366             :     int nCmp = strcmp( m_aName.getStr(),
     367           0 :                        ((const StringNode *)pSearch)->m_aName.getStr() );
     368           0 :     if( nCmp < 0 )
     369           0 :         return LESS;
     370           0 :     else if( nCmp > 0 )
     371           0 :         return GREATER;
     372             :     else
     373           0 :         return EQUAL;
     374             : }
     375             : 
     376             : // pSearch ist ein Zeiger auf const char *
     377           0 : COMPARE StringNode::Compare( const void * pSearch ) const
     378             : {
     379           0 :     int nCmp = strcmp( m_aName.getStr(), (const char *)pSearch );
     380             : 
     381           0 :     if( nCmp < 0 )
     382           0 :         return LESS;
     383           0 :     else if( nCmp > 0 )
     384           0 :         return GREATER;
     385             :     else
     386           0 :         return EQUAL;
     387             : }
     388             : 
     389             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10