xref: /trunk/main/rsc/source/tools/rsctree.cxx (revision 1ecadb572e7010ff3b3382ad9bf179dbc6efadbb) ! 
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 }
547