rsc/source/tools/rsctree.cxx

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