Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /*
3 : * This file is part of the LibreOffice project.
4 : *
5 : * This Source Code Form is subject to the terms of the Mozilla Public
6 : * License, v. 2.0. If a copy of the MPL was not distributed with this
7 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 : *
9 : * This file incorporates work covered by the following license notice:
10 : *
11 : * Licensed to the Apache Software Foundation (ASF) under one or more
12 : * contributor license agreements. See the NOTICE file distributed
13 : * with this work for additional information regarding copyright
14 : * ownership. The ASF licenses this file to you under the Apache
15 : * License, Version 2.0 (the "License"); you may not use this file
16 : * except in compliance with the License. You may obtain a copy of
17 : * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 : */
19 :
20 : /****************** I N C L U D E S **************************************/
21 :
22 : // C and C++ Includes.
23 : #include <stdlib.h>
24 : #include <stdio.h>
25 : #include <string.h>
26 :
27 : // Programmabh�ngige Includes.
28 : #include <tools/link.hxx>
29 : #include <rsctree.hxx>
30 :
31 : /****************** C O D E **********************************************/
32 :
33 : /****************** B i N o d e ******************************************/
34 : /*************************************************************************
35 : |*
36 : |* BiNode::BiNode()
37 : |*
38 : *************************************************************************/
39 246806 : BiNode::BiNode(){
40 246806 : pLeft = pRight = NULL;
41 246806 : }
42 :
43 : /*************************************************************************
44 : |*
45 : |* BiNode::~BiNode()
46 : |*
47 : *************************************************************************/
48 246806 : BiNode::~BiNode(){
49 246806 : }
50 :
51 : /*************************************************************************
52 : |*
53 : |* BiNode::EnumNodes()
54 : |*
55 : *************************************************************************/
56 137678 : void BiNode::EnumNodes( Link aLink ) const{
57 137678 : if( Left() )
58 51780 : Left()->EnumNodes( aLink );
59 137678 : aLink.Call( (BiNode *)this );
60 137678 : if( Right() )
61 82050 : Right()->EnumNodes( aLink );
62 137678 : }
63 :
64 : /*************************************************************************
65 : |*
66 : |* BiNode::ChangeDLListBTree()
67 : |*
68 : *************************************************************************/
69 678870 : BiNode * BiNode::ChangeDLListBTree( BiNode * pList ){
70 : BiNode * pRightNode;
71 : BiNode * pMiddle;
72 : BiNode * pTmp;
73 : sal_uInt32 nEle, i;
74 :
75 678870 : if( pList ){
76 675084 : while( pList->Left() )
77 0 : pList = pList->Left();
78 337542 : pTmp = pList;
79 2226237 : for( nEle = 0; pTmp->Right(); nEle++ )
80 1888695 : pTmp = pTmp->Right();
81 337542 : pMiddle = pList;
82 337542 : if( nEle / 2 )
83 1022185 : for( i = 0; i < (nEle / 2); i++ )
84 884545 : pMiddle = pMiddle->Right();
85 : else
86 199902 : pList = (BiNode *)0;
87 :
88 337542 : if( NULL != (pTmp = pMiddle->Left()) ) // rechten Zeiger auf Null
89 137640 : pTmp->pRight = (BiNode *)0;
90 :
91 : // linken Zeiger auf Null
92 337542 : if( NULL != (pRightNode = pMiddle->Right()) )
93 196116 : pRightNode->pLeft = (BiNode *)0;
94 :
95 337542 : pMiddle->pLeft = ChangeDLListBTree( pList );
96 337542 : pMiddle->pRight = ChangeDLListBTree( pRightNode );
97 :
98 337542 : return( pMiddle );
99 : }
100 341328 : return( pList );
101 : }
102 :
103 : /*************************************************************************
104 : |*
105 : |* BiNode::ChangeBTreeDLList()
106 : |*
107 : *************************************************************************/
108 337542 : BiNode * BiNode::ChangeBTreeDLList(){
109 : BiNode * pList;
110 : BiNode * pLL_RN; // linke Liste rechter Knoten
111 :
112 337542 : if( Right() ){
113 222040 : pList = Right()->ChangeBTreeDLList();
114 222040 : pRight = pList;
115 222040 : pList->pLeft = this;
116 : }
117 337542 : pList = this;
118 337542 : if( Left() ){
119 111716 : pLL_RN = pList = Left()->ChangeBTreeDLList();
120 887368 : while( pLL_RN->Right() )
121 663936 : pLL_RN = pLL_RN->Right();
122 111716 : pLeft = pLL_RN;
123 111716 : pLL_RN->pRight = this;
124 : }
125 337542 : return( pList );
126 : }
127 :
128 : /****************** N a m e N o d e **************************************/
129 : /*************************************************************************
130 : |*
131 : |* NameNode::Remove()
132 : |*
133 : *************************************************************************/
134 0 : NameNode * NameNode::Remove( NameNode * pRemove ){
135 0 : NameNode * pRoot = this;
136 0 : NameNode * pParent = SearchParent( pRemove );
137 :
138 0 : if( pParent ){
139 0 : if( pParent->Left()
140 0 : && (EQUAL == pRemove->Compare( pParent->Left() ) ) ){
141 0 : pParent->pLeft = pRemove->Left();
142 0 : if( pRemove->Right() )
143 0 : pParent->Insert( pRemove->Right() );
144 : }
145 0 : else if( pParent->Right()
146 0 : && (EQUAL == pRemove->Compare( pParent->Right() ) ) ){
147 0 : pParent->pRight = pRemove->Right();
148 0 : if( pRemove->Left() )
149 0 : pParent->Insert( pRemove->Left() );
150 : }
151 : }
152 0 : else if( EQUAL == this->Compare( pRemove ) ){
153 0 : if( Right() ){
154 0 : pRoot = Right();
155 0 : if( Left() )
156 0 : Right()->Insert( Left() );
157 : }
158 : else{
159 0 : pRoot = Left();
160 : }
161 : }
162 0 : pRemove->pLeft = pRemove->pRight = NULL;
163 :
164 0 : return pRoot;
165 : }
166 :
167 :
168 : /*************************************************************************
169 : |*
170 : |* NameNode::Compare
171 : |*
172 : *************************************************************************/
173 0 : COMPARE NameNode::Compare( const NameNode * pCompare ) const{
174 0 : if( (long)this < (long)pCompare )
175 0 : return LESS;
176 0 : else if( (long)this > (long)pCompare )
177 0 : return GREATER;
178 : else
179 0 : return EQUAL;
180 : }
181 :
182 0 : COMPARE NameNode::Compare( const void * pCompare ) const{
183 0 : if( (long)this < (long)pCompare )
184 0 : return LESS;
185 0 : else if( (long)this > (long)pCompare )
186 0 : return GREATER;
187 : else
188 0 : return EQUAL;
189 : }
190 :
191 : /*************************************************************************
192 : |*
193 : |* NameNode::SearchParent
194 : |*
195 : *************************************************************************/
196 0 : NameNode* NameNode::SearchParent( const NameNode * pSearch ) const{
197 : // search for a parent node.
198 : // return a pointer to the parent node if found.
199 : // otherwise return 0.
200 0 : int nCmp = Compare( pSearch );
201 :
202 0 : if( nCmp == GREATER ){
203 0 : if( Left() ){
204 0 : if( ((NameNode *)Left())->Compare( pSearch ) == EQUAL )
205 0 : return (NameNode *)this;
206 0 : return ((NameNode *)Left())->SearchParent( pSearch );
207 : };
208 : }
209 0 : else if( nCmp == LESS ){
210 0 : if( Right() ){
211 0 : if( ((NameNode *)Right())->Compare( pSearch ) == EQUAL )
212 0 : return (NameNode *)this;
213 0 : return ((NameNode *)Right())->SearchParent( pSearch );
214 : }
215 : };
216 0 : return( (NameNode *)NULL );
217 : }
218 :
219 : /*************************************************************************
220 : |*
221 : |* NameNode::Search
222 : |*
223 : *************************************************************************/
224 0 : NameNode* NameNode::Search( const NameNode * pSearch ) const{
225 : // search for a node.
226 : // return a pointer to the node if found.
227 : // otherwise return 0.
228 0 : int nCmp = Compare( pSearch );
229 :
230 0 : if( nCmp == GREATER ){
231 0 : if( Left() )
232 0 : return ((NameNode *)Left())->Search( pSearch );
233 : }
234 0 : else if( nCmp == LESS ){
235 0 : if( Right() )
236 0 : return ((NameNode *)Right())->Search( pSearch );
237 : }
238 : else
239 0 : return( (NameNode *)this );
240 :
241 0 : return( NULL );
242 : }
243 :
244 21145 : NameNode* NameNode::Search( const void * pSearch ) const{
245 : // search for a node.
246 : // return a pointer to the node if found.
247 : // otherwise return 0.
248 21145 : int nCmp = Compare( pSearch );
249 :
250 21145 : if( nCmp == GREATER ){
251 23 : if( Left() )
252 7 : return ((NameNode *)Left())->Search( pSearch );
253 : }
254 21122 : else if( nCmp == LESS ){
255 113 : if( Right() )
256 18 : return ((NameNode *)Right())->Search( pSearch );
257 : }
258 : else
259 21009 : return( (NameNode *)this );
260 :
261 111 : return( NULL );
262 : }
263 :
264 : /*************************************************************************
265 : |*
266 : |* NameNode::Insert()
267 : |*
268 : *************************************************************************/
269 898616 : sal_Bool NameNode::Insert( NameNode * pTN, sal_uInt32* pnDepth ){
270 : // Ein Knoten wird in den Baum eingefuegt
271 : // Gibt es einen Knoten mit dem gleichen Namen, dann return sal_False
272 : // sonst return sal_True. Der Knoten wird auf jeden Fall eingefuegt.
273 :
274 898616 : sal_Bool bRet = sal_True;
275 898616 : int nCmp = Compare( pTN );
276 :
277 898616 : *pnDepth += 1;
278 898616 : if( nCmp == GREATER ){
279 27577 : if( Left() )
280 25871 : bRet = ((NameNode *)Left())->Insert( pTN, pnDepth );
281 : else
282 1706 : pLeft = pTN;
283 : }
284 : else{
285 871039 : if( Right() )
286 801270 : bRet = ((NameNode *)Right())->Insert( pTN, pnDepth );
287 : else
288 69769 : pRight = pTN;
289 871039 : if( nCmp == EQUAL )
290 0 : bRet = sal_False;
291 : };
292 898616 : return( bRet );
293 : }
294 :
295 : /*************************************************************************
296 : |*
297 : |* NameNode::Insert()
298 : |*
299 : *************************************************************************/
300 71475 : sal_Bool NameNode::Insert( NameNode * pTN ){
301 : // insert a node in the tree.
302 : // if the node with the same name is in, return sal_False and no insert.
303 : // if not return true.
304 71475 : sal_uInt32 nDepth = 0;
305 : sal_Bool bRet;
306 :
307 71475 : bRet = Insert( pTN, &nDepth );
308 71475 : if( bRet ){
309 71475 : if( nDepth > 20 ){
310 3498 : if( Left() )
311 301 : pLeft = ChangeDLListBTree( Left()->ChangeBTreeDLList() );
312 3498 : if( Right() )
313 3485 : pRight = ChangeDLListBTree( Right()->ChangeBTreeDLList() );
314 : }
315 : }
316 :
317 71475 : return( bRet );
318 : }
319 :
320 : /*************************************************************************
321 : |*
322 : |* NameNode::OrderTree()
323 : |*
324 : *************************************************************************/
325 0 : void NameNode::OrderTree(){
326 0 : NameNode * pTmpLeft = (NameNode *)Left();
327 0 : NameNode * pTmpRight = (NameNode *)Right();
328 :
329 0 : pLeft = NULL;
330 0 : pRight = NULL;
331 0 : SubOrderTree( pTmpLeft );
332 0 : SubOrderTree( pTmpRight );
333 0 : }
334 :
335 0 : void NameNode::SubOrderTree( NameNode * pOrderNode ){
336 0 : if( pOrderNode ){
337 0 : NameNode * pTmpLeft = (NameNode *)pOrderNode->Left();
338 0 : NameNode * pTmpRight = (NameNode *)pOrderNode->Right();
339 0 : pOrderNode->pLeft = NULL;
340 0 : pOrderNode->pRight = NULL;
341 0 : Insert( pOrderNode );
342 0 : SubOrderTree( pTmpLeft );
343 0 : SubOrderTree( pTmpRight );
344 : }
345 0 : }
346 :
347 : /****************** I d N o d e ******************************************/
348 : /*************************************************************************
349 : |*
350 : |* IdNode::Search()
351 : |*
352 : *************************************************************************/
353 21120 : IdNode * IdNode::Search( sal_uInt32 nTypeName ) const{
354 21120 : return( (IdNode *)NameNode::Search( (const void *)&nTypeName ) );
355 : }
356 :
357 : /*************************************************************************
358 : |*
359 : |* IdNode::Compare()
360 : |*
361 : *************************************************************************/
362 898616 : COMPARE IdNode::Compare( const NameNode * pSearch ) const
363 : {
364 898616 : if( GetId() < (sal_uInt32)(((const IdNode *)pSearch)->GetId()) )
365 871039 : return LESS;
366 27577 : else if( GetId() > (sal_uInt32)(((const IdNode *)pSearch)->GetId()) )
367 27577 : return GREATER;
368 : else
369 0 : return EQUAL;
370 : }
371 :
372 21145 : COMPARE IdNode::Compare( const void * pSearch ) const{
373 : // pSearch ist ein Zeiger auf sal_uInt32
374 :
375 21145 : if( GetId() < *((const sal_uInt32 *)pSearch) )
376 113 : return LESS;
377 21032 : else if( GetId() > *((const sal_uInt32 *)pSearch) )
378 23 : return GREATER;
379 : else
380 21009 : return EQUAL;
381 : }
382 :
383 : /*************************************************************************
384 : |*
385 : |* IdNode::GetId()
386 : |*
387 : *************************************************************************/
388 0 : sal_uInt32 IdNode::GetId() const
389 : {
390 0 : return( 0xFFFFFFFF );
391 : }
392 :
393 : /*************************************************************************
394 : |*
395 : |* StringNode::Search()
396 : |*
397 : *************************************************************************/
398 0 : StringNode * StringNode::Search( const char * pSearch ) const{
399 0 : return (StringNode *)NameNode::Search( (const void *)pSearch );
400 : }
401 :
402 : /*************************************************************************
403 : |*
404 : |* StringNode::Compare()
405 : |*
406 : *************************************************************************/
407 0 : COMPARE StringNode::Compare( const NameNode * pSearch ) const
408 : {
409 : int nCmp = strcmp( m_aName.getStr(),
410 0 : ((const StringNode *)pSearch)->m_aName.getStr() );
411 0 : if( nCmp < 0 )
412 0 : return LESS;
413 0 : else if( nCmp > 0 )
414 0 : return GREATER;
415 : else
416 0 : return EQUAL;
417 : }
418 :
419 0 : COMPARE StringNode::Compare( const void * pSearch ) const
420 : {
421 : // pSearch ist ein Zeiger auf const char *
422 0 : int nCmp = strcmp( m_aName.getStr(), (const char *)pSearch );
423 :
424 0 : if( nCmp < 0 )
425 0 : return LESS;
426 0 : else if( nCmp > 0 )
427 0 : return GREATER;
428 : else
429 0 : return EQUAL;
430 : }
431 :
432 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
