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 *************************************************************************/
BiNode()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 *************************************************************************/
~BiNode()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 *************************************************************************/
EnumNodes(Link aLink) const74 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 *************************************************************************/
ChangeDLListBTree(BiNode * pList)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 *************************************************************************/
ChangeBTreeDLList()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 *************************************************************************/
Remove(NameNode * pRemove)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 *************************************************************************/
Compare(const NameNode * pCompare) const207 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
Compare(const void * pCompare) const216 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 *************************************************************************/
SearchParent(const NameNode * pSearch) const234 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 *************************************************************************/
Search(const NameNode * pSearch) const266 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
Search(const void * pSearch) const286 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 *************************************************************************/
Insert(NameNode * pTN,sal_uInt32 * pnDepth)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 *************************************************************************/
Insert(NameNode * pTN)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 *************************************************************************/
OrderTree()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
SubOrderTree(NameNode * pOrderNode)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:
OrderCtrl()415 OrderCtrl() { bOrder = sal_False; pName = NULL; }
IsOrder(const NameNode * pRoot)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 };
IMPL_LINK_INLINE_START(OrderCtrl,CallBackFunc,NameNode *,pNext)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 }
IMPL_LINK_INLINE_END(OrderCtrl,CallBackFunc,NameNode *,pNext)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 *************************************************************************/
Search(sal_uInt32 nTypeName) const449 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 *************************************************************************/
Compare(const NameNode * pSearch) const462 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
Compare(const void * pSearch) const472 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 *************************************************************************/
GetId() const492 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 *************************************************************************/
Search(const char * pSearch) const506 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 *************************************************************************/
Compare(const NameNode * pSearch) const519 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
Compare(const void * pSearch) const531 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