xref: /aoo42x/main/rsc/source/tools/rsctree.cxx (revision cdf0e10c) 
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