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