rsc/source/tools/rsctree.cxx

   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 BiNode::BiNode()
  30 {
  31     pLeft = pRight = NULL;
  32 }
  33
  34 BiNode::~BiNode()
  35 {
  36 }
  37
  38 void BiNode::EnumNodes( Link<> aLink ) const
  39 {
  40     if( Left() )
  41         Left()->EnumNodes( aLink );
  42     aLink.Call( const_cast<BiNode *>(this) );
  43     if( Right() )
  44         Right()->EnumNodes( aLink );
  45 }
  46
  47 BiNode * BiNode::ChangeDLListBTree( BiNode * pList )
  48 {
  49     BiNode * pMiddle;
  50     BiNode * pTmp;
  51     sal_uInt32 nEle, i;
  52
  53     if( pList )
  54 {
  55         while( pList->Left() )
  56             pList = pList->Left();
  57         pTmp = pList;
  58
  59         for( nEle = 0; pTmp->Right(); nEle++ )
  60             pTmp = pTmp->Right();
  61
  62         pMiddle = pList;
  63         if( nEle / 2 )
  64         {
  65             for( i = 0; i < (nEle / 2); i++ )
  66             {
  67                 pMiddle = pMiddle->Right();
  68             }
  69         }
  70         else
  71         {
  72             pList = (BiNode *)0;
  73         }
  74         if( NULL != (pTmp = pMiddle->Left()) )  // rechten Zeiger auf Null
  75             pTmp->pRight = (BiNode *)0;
  76
  77         // linken Zeiger auf Null
  78         BiNode * pRightNode = pMiddle->Right();
  79         if (pRightNode)
  80             pRightNode->pLeft = (BiNode *)0;
  81
  82         pMiddle->pLeft = ChangeDLListBTree( pList );
  83         pMiddle->pRight = ChangeDLListBTree( pRightNode );
  84
  85         return pMiddle;
  86     }
  87     return pList;
  88 }
  89
  90 BiNode * BiNode::ChangeBTreeDLList()
  91 {
  92     BiNode * pList;
  93     BiNode * pLL_RN;    // linke Liste rechter Knoten
  94
  95     if( Right() )
  96     {
  97         pList = Right()->ChangeBTreeDLList();
  98         pRight = pList;
  99         pList->pLeft = this;
 100     }
 101     pList = this;
 102     if( Left() )
 103     {
 104         pLL_RN = pList = Left()->ChangeBTreeDLList();
 105
 106         while( pLL_RN->Right() )
 107             pLL_RN = pLL_RN->Right();
 108
 109         pLeft = pLL_RN;
 110         pLL_RN->pRight = this;
 111     }
 112     return pList;
 113 }
 114
 115 NameNode * NameNode::Remove( NameNode * pRemove )
 116 {
 117     NameNode * pRoot = this;
 118     NameNode * pParent = SearchParent( pRemove );
 119
 120     if( pParent )
 121     {
 122         if( pParent->Left() &&
 123             (EQUAL == pRemove->Compare( pParent->Left() ) ) )
 124         {
 125             pParent->pLeft = pRemove->Left();
 126             if( pRemove->Right() )
 127                 pParent->Insert( pRemove->Right() );
 128         }
 129         else if( pParent->Right() &&
 130                  (EQUAL == pRemove->Compare( pParent->Right() ) ) )
 131         {
 132             pParent->pRight = pRemove->Right();
 133             if( pRemove->Left() )
 134                 pParent->Insert( pRemove->Left() );
 135         }
 136     }
 137     else if( EQUAL == this->Compare( pRemove ) )
 138     {
 139         if( Right() )
 140         {
 141             pRoot = Right();
 142             if( Left() )
 143                 Right()->Insert( Left() );
 144         }
 145         else
 146         {
 147             pRoot = Left();
 148         }
 149     }
 150     pRemove->pLeft = pRemove->pRight = NULL;
 151
 152     return pRoot;
 153 }
 154
 155
 156 COMPARE NameNode::Compare( const NameNode * pCompare ) const
 157 {
 158     if( reinterpret_cast<sal_uIntPtr>(this) < reinterpret_cast<sal_uIntPtr>(pCompare) )
 159         return LESS;
 160     else if( reinterpret_cast<sal_uIntPtr>(this) > reinterpret_cast<sal_uIntPtr>(pCompare) )
 161         return GREATER;
 162     else
 163         return EQUAL;
 164 }
 165
 166 COMPARE NameNode::Compare( const void * pCompare ) const
 167 {
 168     if( reinterpret_cast<sal_uIntPtr>(this) < reinterpret_cast<sal_uIntPtr>(pCompare) )
 169         return LESS;
 170     else if( reinterpret_cast<sal_uIntPtr>(this) > reinterpret_cast<sal_uIntPtr>(pCompare) )
 171         return GREATER;
 172     else
 173         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 NameNode* NameNode::SearchParent( const NameNode * pSearch ) const
 180 {
 181     int nCmp = Compare( pSearch );
 182
 183     if( nCmp == GREATER )
 184     {
 185         if( Left() )
 186         {
 187             if( Left()->Compare( pSearch ) == EQUAL )
 188                 return const_cast<NameNode *>(this);
 189             return Left()->SearchParent( pSearch );
 190         }
 191     }
 192     else if( nCmp == LESS )
 193     {
 194         if( Right() )
 195         {
 196             if( Right()->Compare( pSearch ) == EQUAL )
 197                 return const_cast<NameNode *>(this);
 198             return Right()->SearchParent( pSearch );
 199         }
 200     }
 201     return (NameNode *)NULL;
 202 }
 203
 204 // search for a node.
 205 // return a pointer to the node if found.
 206 // otherwise return 0.
 207 NameNode* NameNode::Search( const NameNode * pSearch ) const
 208 {
 209     int nCmp = Compare( pSearch );
 210
 211     if( nCmp == GREATER )
 212     {
 213         if( Left() )
 214             return Left()->Search( pSearch );
 215     }
 216     else if( nCmp == LESS )
 217     {
 218         if( Right() )
 219             return Right()->Search( pSearch );
 220     }
 221     else
 222         return const_cast<NameNode *>(this);
 223
 224     return NULL;
 225 }
 226
 227 // search for a node.
 228 // return a pointer to the node if found.
 229 // otherwise return 0.
 230 NameNode* NameNode::Search( const void * pSearch ) const
 231 {
 232     int nCmp = Compare( pSearch );
 233
 234     if( nCmp == GREATER )
 235     {
 236         if( Left() )
 237             return Left()->Search( pSearch );
 238     }
 239     else if( nCmp == LESS )
 240     {
 241         if( Right() )
 242             return Right()->Search( pSearch );
 243     }
 244     else
 245         return const_cast<NameNode *>(this);
 246
 247     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 bool NameNode::Insert( NameNode * pTN, sal_uInt32* pnDepth )
 255 {
 256     bool bRet = true;
 257     int nCmp = Compare( pTN );
 258
 259     *pnDepth += 1;
 260     if( nCmp == GREATER )
 261     {
 262         if( Left() )
 263             bRet =  Left()->Insert( pTN, pnDepth );
 264         else
 265             pLeft = pTN;
 266     }
 267     else
 268     {
 269         if( Right() )
 270             bRet = Right()->Insert( pTN, pnDepth );
 271         else
 272             pRight = pTN;
 273
 274         if( nCmp == EQUAL )
 275             bRet = false;
 276     }
 277     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 bool NameNode::Insert( NameNode * pTN )
 284 {
 285     sal_uInt32  nDepth = 0;
 286     bool        bRet;
 287
 288     bRet = Insert( pTN, &nDepth );
 289     if( bRet )
 290     {
 291         if( nDepth > 20 )
 292         {
 293             if( Left() )
 294                 pLeft =  ChangeDLListBTree(  Left()->ChangeBTreeDLList() );
 295             if( Right() )
 296                 pRight = ChangeDLListBTree( Right()->ChangeBTreeDLList() );
 297         }
 298     }
 299
 300     return bRet;
 301 }
 302
 303 void NameNode::OrderTree()
 304 {
 305     NameNode * pTmpLeft = static_cast<NameNode *>(Left());
 306     NameNode * pTmpRight = static_cast<NameNode *>(Right());
 307
 308     pLeft = NULL;
 309     pRight = NULL;
 310     SubOrderTree( pTmpLeft );
 311     SubOrderTree( pTmpRight );
 312 }
 313
 314 void NameNode::SubOrderTree( NameNode * pOrderNode )
 315 {
 316     if( pOrderNode )
 317     {
 318         NameNode * pTmpLeft = static_cast<NameNode *>(pOrderNode->Left());
 319         NameNode * pTmpRight = static_cast<NameNode *>(pOrderNode->Right());
 320         pOrderNode->pLeft = NULL;
 321         pOrderNode->pRight = NULL;
 322         Insert( pOrderNode );
 323         SubOrderTree( pTmpLeft );
 324         SubOrderTree( pTmpRight );
 325     }
 326 }
 327
 328 IdNode * IdNode::Search( sal_uInt32 nTypeName ) const
 329 {
 330     return static_cast<IdNode *>(NameNode::Search( (const void *)&nTypeName ));
 331 }
 332
 333 COMPARE IdNode::Compare( const NameNode * pSearch ) const
 334 {
 335     if( GetId() < (sal_uInt32)(static_cast<const IdNode *>(pSearch)->GetId()) )
 336         return LESS;
 337     else if( GetId() > (sal_uInt32)(static_cast<const IdNode *>(pSearch)->GetId()) )
 338         return GREATER;
 339     else
 340         return EQUAL;
 341 }
 342
 343 // pSearch ist ein Zeiger auf sal_uInt32
 344 COMPARE IdNode::Compare( const void * pSearch ) const
 345 {
 346     if( GetId() < *static_cast<const sal_uInt32 *>(pSearch) )
 347         return LESS;
 348     else if( GetId() > *static_cast<const sal_uInt32 *>(pSearch) )
 349         return GREATER;
 350     else
 351         return EQUAL;
 352 }
 353
 354 sal_uInt32 IdNode::GetId() const
 355 {
 356     return 0xFFFFFFFF;
 357 }
 358
 359 StringNode * StringNode::Search( const char * pSearch ) const
 360 {
 361     return static_cast<StringNode *>(NameNode::Search( (const void *)pSearch ));
 362 }
 363
 364 COMPARE StringNode::Compare( const NameNode * pSearch ) const
 365 {
 366     int nCmp = strcmp( m_aName.getStr(),
 367                        static_cast<const StringNode *>(pSearch)->m_aName.getStr() );
 368     if( nCmp < 0 )
 369         return LESS;
 370     else if( nCmp > 0 )
 371         return GREATER;
 372     else
 373         return EQUAL;
 374 }
 375
 376 // pSearch ist ein Zeiger auf const char *
 377 COMPARE StringNode::Compare( const void * pSearch ) const
 378 {
 379     int nCmp = strcmp( m_aName.getStr(), static_cast<const char *>(pSearch) );
 380
 381     if( nCmp < 0 )
 382         return LESS;
 383     else if( nCmp > 0 )
 384         return GREATER;
 385     else
 386         return EQUAL;
 387 }
 388
 389 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */