rsc/source/tools/rsctree.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2000, 2010 Oracle and/or its affiliates.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * This file is part of OpenOffice.org.
  10  *
  11  * OpenOffice.org is free software: you can redistribute it and/or modify
  12  * it under the terms of the GNU Lesser General Public License version 3
  13  * only, as published by the Free Software Foundation.
  14  *
  15  * OpenOffice.org is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU Lesser General Public License version 3 for more details
  19  * (a copy is included in the LICENSE file that accompanied this code).
  20  *
  21  * You should have received a copy of the GNU Lesser General Public License
  22  * version 3 along with OpenOffice.org.  If not, see
  23  * <http://www.openoffice.org/license.html>
  24  * for a copy of the LGPLv3 License.
  25  *
  26  ************************************************************************/
  27
  28 // MARKER(update_precomp.py): autogen include statement, do not remove
  29 #include "precompiled_rsc.hxx"
  30 /****************** I N C L U D E S **************************************/
  31
  32 // C and C++ Includes.
  33 #include <stdlib.h>
  34 #include <stdio.h>
  35 #include <string.h>
  36
  37 // Programmabh�ngige Includes.
  38 #include <tools/link.hxx>
  39 #include <rsctree.hxx>
  40
  41 /****************** C O D E **********************************************/
  42
  43 /****************** B i N o d e ******************************************/
  44 /*************************************************************************
  45 |*
  46 |*    BiNode::BiNode()
  47 |*
  48 |*    Beschreibung      NAME.DOC
  49 |*    Ersterstellung    MM 07.02.91
  50 |*    Letzte Aenderung  MM 07.02.91
  51 |*
  52 *************************************************************************/
  53 BiNode::BiNode(){
  54     pLeft = pRight = NULL;
  55 }
  56
  57 /*************************************************************************
  58 |*
  59 |*    BiNode::~BiNode()
  60 |*
  61 |*    Beschreibung
  62 |*    Ersterstellung    MM 07.02.91
  63 |*    Letzte Aenderung  MM 07.02.91
  64 |*
  65 *************************************************************************/
  66 BiNode::~BiNode(){
  67 }
  68
  69 /*************************************************************************
  70 |*
  71 |*    BiNode::EnumNodes()
  72 |*
  73 |*    Beschreibung
  74 |*    Ersterstellung    MM 07.02.91
  75 |*    Letzte Aenderung  MM 07.02.91
  76 |*
  77 *************************************************************************/
  78 void BiNode::EnumNodes( Link aLink ) const{
  79     if( Left() )
  80         Left()->EnumNodes( aLink );
  81     aLink.Call( (BiNode *)this );
  82     if( Right() )
  83         Right()->EnumNodes( aLink );
  84 }
  85
  86 /*************************************************************************
  87 |*
  88 |*    BiNode::ChangeDLListBTree()
  89 |*
  90 |*    Beschreibung
  91 |*    Ersterstellung    MM 11.01.91
  92 |*    Letzte Aenderung  MM 11.01.91
  93 |*
  94 *************************************************************************/
  95 BiNode * BiNode::ChangeDLListBTree( BiNode * pList ){
  96     BiNode * pRightNode;
  97     BiNode * pMiddle;
  98     BiNode * pTmp;
  99     sal_uInt32 nEle, i;
 100
 101     if( pList ){
 102         while( pList->Left() )
 103             pList = pList->Left();
 104         pTmp = pList;
 105         for( nEle = 0; pTmp->Right(); nEle++ )
 106             pTmp = pTmp->Right();
 107         pMiddle = pList;
 108         if( nEle / 2 )
 109             for( i = 0; i < (nEle / 2); i++ )
 110                 pMiddle = pMiddle->Right();
 111         else
 112             pList = (BiNode *)0;
 113
 114         if( NULL != (pTmp = pMiddle->Left()) )  // rechten Zeiger auf Null
 115             pTmp->pRight = (BiNode *)0;
 116
 117         // linken Zeiger auf Null
 118         if( NULL != (pRightNode = pMiddle->Right()) )
 119             pRightNode->pLeft = (BiNode *)0;
 120
 121         pMiddle->pLeft = ChangeDLListBTree( pList );
 122         pMiddle->pRight = ChangeDLListBTree( pRightNode );
 123
 124         return( pMiddle );
 125     }
 126     return( pList );
 127 }
 128
 129 /*************************************************************************
 130 |*
 131 |*    BiNode::ChangeBTreeDLList()
 132 |*
 133 |*    Beschreibung
 134 |*    Ersterstellung    MM 11.01.91
 135 |*    Letzte Aenderung  MM 11.01.91
 136 |*
 137 *************************************************************************/
 138 BiNode * BiNode::ChangeBTreeDLList(){
 139     BiNode * pList;
 140     BiNode * pLL_RN;    // linke Liste rechter Knoten
 141
 142     if( Right() ){
 143         pList = Right()->ChangeBTreeDLList();
 144         pRight = pList;
 145         pList->pLeft = this;
 146     }
 147     pList = this;
 148     if( Left() ){
 149         pLL_RN = pList = Left()->ChangeBTreeDLList();
 150         while( pLL_RN->Right() )
 151             pLL_RN = pLL_RN->Right();
 152         pLeft = pLL_RN;
 153         pLL_RN->pRight = this;
 154     }
 155     return( pList );
 156 }
 157
 158 /****************** N a m e N o d e **************************************/
 159 /*************************************************************************
 160 |*
 161 |*    NameNode::Remove()
 162 |*
 163 |*    Beschreibung
 164 |*    Ersterstellung    MM 10.07.91
 165 |*    Letzte Aenderung  MM 10.07.91
 166 |*
 167 *************************************************************************/
 168 NameNode * NameNode::Remove( NameNode * pRemove ){
 169     NameNode * pRoot = this;
 170     NameNode * pParent = SearchParent( pRemove );
 171
 172     if( pParent ){
 173         if( pParent->Left()
 174           && (EQUAL == pRemove->Compare( pParent->Left() ) ) ){
 175             pParent->pLeft = pRemove->Left();
 176             if( pRemove->Right() )
 177                 pParent->Insert( pRemove->Right() );
 178         }
 179         else if( pParent->Right()
 180           && (EQUAL == pRemove->Compare( pParent->Right() ) ) ){
 181             pParent->pRight = pRemove->Right();
 182             if( pRemove->Left() )
 183                 pParent->Insert( pRemove->Left() );
 184         }
 185     }
 186     else if( EQUAL == this->Compare( pRemove ) ){
 187         if( Right() ){
 188             pRoot = Right();
 189             if( Left() )
 190                 Right()->Insert( Left() );
 191         }
 192         else{
 193             pRoot = Left();
 194         }
 195     }
 196     pRemove->pLeft = pRemove->pRight = NULL;
 197
 198     return pRoot;
 199 }
 200
 201
 202 /*************************************************************************
 203 |*
 204 |*    NameNode::Compare
 205 |*
 206 |*    Beschreibung
 207 |*    Ersterstellung    MM 10.07.91
 208 |*    Letzte Aenderung  MM 13.07.91
 209 |*
 210 *************************************************************************/
 211 COMPARE NameNode::Compare( const NameNode * pCompare ) const{
 212     if( (long)this < (long)pCompare )
 213         return LESS;
 214     else if( (long)this > (long)pCompare )
 215         return GREATER;
 216     else
 217         return EQUAL;
 218 }
 219
 220 COMPARE NameNode::Compare( const void * pCompare ) const{
 221     if( (long)this < (long)pCompare )
 222         return LESS;
 223     else if( (long)this > (long)pCompare )
 224         return GREATER;
 225     else
 226         return EQUAL;
 227 }
 228
 229 /*************************************************************************
 230 |*
 231 |*    NameNode::SearchParent
 232 |*
 233 |*    Beschreibung
 234 |*    Ersterstellung    MM 10.07.91
 235 |*    Letzte Aenderung  MM 10.07.91
 236 |*
 237 *************************************************************************/
 238 NameNode* NameNode::SearchParent( const NameNode * pSearch ) const{
 239 // search for a parent node.
 240 // return a pointer to the parent node if found.
 241 // otherwise return 0.
 242     int nCmp = Compare( pSearch );
 243
 244     if( nCmp == GREATER ){
 245         if( Left() ){
 246             if( ((NameNode *)Left())->Compare( pSearch ) == EQUAL )
 247                 return (NameNode *)this;
 248             return ((NameNode *)Left())->SearchParent( pSearch );
 249         };
 250     }
 251     else if( nCmp == LESS ){
 252         if( Right() ){
 253             if( ((NameNode *)Right())->Compare( pSearch ) == EQUAL )
 254                 return (NameNode *)this;
 255             return ((NameNode *)Right())->SearchParent( pSearch );
 256         }
 257     };
 258     return( (NameNode *)NULL );
 259 }
 260
 261 /*************************************************************************
 262 |*
 263 |*    NameNode::Search
 264 |*
 265 |*    Beschreibung
 266 |*    Ersterstellung    MM 21.03.90
 267 |*    Letzte Aenderung  MM 27.06.90
 268 |*
 269 *************************************************************************/
 270 NameNode* NameNode::Search( const NameNode * pSearch ) const{
 271 // search for a node.
 272 // return a pointer to the node if found.
 273 // otherwise return 0.
 274     int nCmp = Compare( pSearch );
 275
 276     if( nCmp == GREATER ){
 277         if( Left() )
 278             return ((NameNode *)Left())->Search( pSearch );
 279     }
 280     else if( nCmp == LESS ){
 281         if( Right() )
 282             return ((NameNode *)Right())->Search( pSearch );
 283     }
 284     else
 285         return( (NameNode *)this );
 286
 287     return( NULL );
 288 }
 289
 290 NameNode* NameNode::Search( const void * pSearch ) const{
 291 // search for a node.
 292 // return a pointer to the node if found.
 293 // otherwise return 0.
 294     int nCmp = Compare( pSearch );
 295
 296     if( nCmp == GREATER ){
 297         if( Left() )
 298             return ((NameNode *)Left())->Search( pSearch );
 299     }
 300     else if( nCmp == LESS ){
 301         if( Right() )
 302             return ((NameNode *)Right())->Search( pSearch );
 303     }
 304     else
 305         return( (NameNode *)this );
 306
 307     return( NULL );
 308 }
 309
 310 /*************************************************************************
 311 |*
 312 |*    NameNode::Insert()
 313 |*
 314 |*    Beschreibung      NAME.DOC
 315 |*    Ersterstellung    MM 11.01.91
 316 |*    Letzte Aenderung  MM 11.01.91
 317 |*
 318 *************************************************************************/
 319 sal_Bool NameNode::Insert( NameNode * pTN, sal_uInt32* pnDepth ){
 320 // Ein Knoten wird in den Baum eingefuegt
 321 // Gibt es einen Knoten mit dem gleichen Namen, dann return sal_False
 322 // sonst return sal_True. Der Knoten wird auf jeden Fall eingefuegt.
 323
 324     sal_Bool bRet = sal_True;
 325     int nCmp = Compare( pTN );
 326
 327     *pnDepth += 1;
 328     if( nCmp == GREATER ){
 329         if( Left() )
 330             bRet =  ((NameNode *)Left())->Insert( pTN, pnDepth );
 331         else
 332             pLeft = pTN;
 333     }
 334     else{
 335         if( Right() )
 336             bRet = ((NameNode *)Right())->Insert( pTN, pnDepth );
 337         else
 338             pRight = pTN;
 339         if( nCmp == EQUAL )
 340             bRet = sal_False;
 341     };
 342     return( bRet );
 343 }
 344
 345 /*************************************************************************
 346 |*
 347 |*    NameNode::Insert()
 348 |*
 349 |*    Beschreibung      NAME.DOC
 350 |*    Ersterstellung    MM 21.03.90
 351 |*    Letzte Aenderung  MM 11.01.91
 352 |*
 353 *************************************************************************/
 354 sal_Bool NameNode::Insert( NameNode * pTN ){
 355 // insert a node in the tree.
 356 // if the node with the same name is in, return sal_False and no insert.
 357 // if not return true.
 358     sal_uInt32  nDepth = 0;
 359     sal_Bool        bRet;
 360
 361     bRet = Insert( pTN, &nDepth );
 362     if( bRet ){
 363         if( nDepth > 20 ){
 364             if( Left() )
 365                 pLeft =  ChangeDLListBTree(  Left()->ChangeBTreeDLList() );
 366             if( Right() )
 367                 pRight = ChangeDLListBTree( Right()->ChangeBTreeDLList() );
 368         }
 369     }
 370
 371     return( bRet );
 372 }
 373
 374 /*************************************************************************
 375 |*
 376 |*    NameNode::OrderTree()
 377 |*
 378 |*    Beschreibung
 379 |*    Ersterstellung    MM 23.09.91
 380 |*    Letzte Aenderung  MM 23.09.91
 381 |*
 382 *************************************************************************/
 383 void NameNode::OrderTree(){
 384     NameNode * pTmpLeft = (NameNode *)Left();
 385     NameNode * pTmpRight = (NameNode *)Right();
 386
 387     pLeft = NULL;
 388     pRight = NULL;
 389     SubOrderTree( pTmpLeft );
 390     SubOrderTree( pTmpRight );
 391 }
 392
 393 void NameNode::SubOrderTree( NameNode * pOrderNode ){
 394     if( pOrderNode ){
 395         NameNode * pTmpLeft = (NameNode *)pOrderNode->Left();
 396         NameNode * pTmpRight = (NameNode *)pOrderNode->Right();
 397         pOrderNode->pLeft = NULL;
 398         pOrderNode->pRight = NULL;
 399         Insert( pOrderNode );
 400         SubOrderTree( pTmpLeft );
 401         SubOrderTree( pTmpRight );
 402     }
 403 }
 404
 405 /*************************************************************************
 406 |*
 407 |*    NameNode::IdOrderTree()
 408 |*
 409 |*    Beschreibung
 410 |*    Ersterstellung    MM 15.11.91
 411 |*    Letzte Aenderung  MM 15.11.91
 412 |*
 413 *************************************************************************/
 414 class OrderCtrl {
 415     sal_Bool       bOrder;
 416     NameNode * pName;
 417     DECL_LINK( CallBackFunc, NameNode * );
 418 public:
 419             OrderCtrl() { bOrder = sal_False; pName = NULL; }
 420     sal_Bool    IsOrder( const NameNode * pRoot )
 421     {
 422             bOrder = sal_True;
 423             pName  = NULL;
 424             pRoot->EnumNodes( LINK( this, OrderCtrl, CallBackFunc ) );
 425             return bOrder;
 426     };
 427 };
 428 IMPL_LINK_INLINE_START( OrderCtrl, CallBackFunc, NameNode *, pNext )
 429 {
 430     if( pName && pName->Compare( pNext ) != LESS )
 431         bOrder = sal_False;
 432     pName = pNext;
 433     return 0;
 434 }
 435 IMPL_LINK_INLINE_END( OrderCtrl, CallBackFunc, NameNode *, pNext )
 436
 437 sal_Bool NameNode::IsOrderTree() const{
 438     OrderCtrl aOrder;
 439
 440     return aOrder.IsOrder( this );
 441 }
 442
 443 /****************** I d N o d e ******************************************/
 444 /*************************************************************************
 445 |*
 446 |*    IdNode::Search()
 447 |*
 448 |*    Beschreibung
 449 |*    Ersterstellung    MM 06.11.91
 450 |*    Letzte Aenderung  MM 06.11.91
 451 |*
 452 *************************************************************************/
 453 IdNode * IdNode::Search( sal_uInt32 nTypeName ) const{
 454     return( (IdNode *)NameNode::Search( (const void *)&nTypeName ) );
 455 }
 456
 457 /*************************************************************************
 458 |*
 459 |*    IdNode::Compare()
 460 |*
 461 |*    Beschreibung
 462 |*    Ersterstellung    MM 06.11.91
 463 |*    Letzte Aenderung  MM 06.11.91
 464 |*
 465 *************************************************************************/
 466 COMPARE IdNode::Compare( const NameNode * pSearch ) const
 467 {
 468     if( GetId() < (sal_uInt32)(((const IdNode *)pSearch)->GetId()) )
 469         return LESS;
 470     else if( GetId() > (sal_uInt32)(((const IdNode *)pSearch)->GetId()) )
 471         return GREATER;
 472     else
 473         return EQUAL;
 474 }
 475
 476 COMPARE IdNode::Compare( const void * pSearch ) const{
 477 // pSearch ist ein Zeiger auf sal_uInt32
 478
 479     if( GetId() < *((const sal_uInt32 *)pSearch) )
 480         return LESS;
 481     else if( GetId() > *((const sal_uInt32 *)pSearch) )
 482         return GREATER;
 483     else
 484         return EQUAL;
 485 }
 486
 487 /*************************************************************************
 488 |*
 489 |*    IdNode::GetId()
 490 |*
 491 |*    Beschreibung
 492 |*    Ersterstellung    MM 23.09.91
 493 |*    Letzte Aenderung  MM 23.09.91
 494 |*
 495 *************************************************************************/
 496 sal_uInt32 IdNode::GetId() const
 497 {
 498     return( 0xFFFFFFFF );
 499 }
 500
 501 /*************************************************************************
 502 |*
 503 |*    StringNode::Search()
 504 |*
 505 |*    Beschreibung
 506 |*    Ersterstellung    MM 06.11.91
 507 |*    Letzte Aenderung  MM 06.11.91
 508 |*
 509 *************************************************************************/
 510 StringNode * StringNode::Search( const char * pSearch ) const{
 511     return (StringNode *)NameNode::Search( (const void *)pSearch );
 512 }
 513
 514 /*************************************************************************
 515 |*
 516 |*    StringNode::Compare()
 517 |*
 518 |*    Beschreibung
 519 |*    Ersterstellung    MM 06.11.91
 520 |*    Letzte Aenderung  MM 06.11.91
 521 |*
 522 *************************************************************************/
 523 COMPARE StringNode::Compare( const NameNode * pSearch ) const
 524 {
 525     int nCmp = strcmp( aName.GetBuffer(),
 526                        ((const StringNode *)pSearch)->aName.GetBuffer() );
 527     if( nCmp < 0 )
 528         return LESS;
 529     else if( nCmp > 0 )
 530         return GREATER;
 531     else
 532         return EQUAL;
 533 }
 534
 535 COMPARE StringNode::Compare( const void * pSearch ) const
 536 {
 537 // pSearch ist ein Zeiger auf const char *
 538     int nCmp = strcmp( aName.GetBuffer(), (const char *)pSearch );
 539
 540     if( nCmp < 0 )
 541         return LESS;
 542     else if( nCmp > 0 )
 543         return GREATER;
 544     else
 545         return EQUAL;
 546 }