Branch data 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 : 510408 : BiNode::BiNode(){
40 : 510408 : pLeft = pRight = NULL;
41 : 510408 : }
42 : :
43 : : /*************************************************************************
44 : : |*
45 : : |* BiNode::~BiNode()
46 : : |*
47 : : *************************************************************************/
48 : 510408 : BiNode::~BiNode(){
49 [ - + ]: 510408 : }
50 : :
51 : : /*************************************************************************
52 : : |*
53 : : |* BiNode::EnumNodes()
54 : : |*
55 : : *************************************************************************/
56 : 283068 : void BiNode::EnumNodes( Link aLink ) const{
57 [ + + ]: 283068 : if( Left() )
58 : 106642 : Left()->EnumNodes( aLink );
59 : 283068 : aLink.Call( (BiNode *)this );
60 [ + + ]: 283068 : if( Right() )
61 : 168396 : Right()->EnumNodes( aLink );
62 : 283068 : }
63 : :
64 : : /*************************************************************************
65 : : |*
66 : : |* BiNode::ChangeDLListBTree()
67 : : |*
68 : : *************************************************************************/
69 : 1321762 : BiNode * BiNode::ChangeDLListBTree( BiNode * pList ){
70 : : BiNode * pRightNode;
71 : : BiNode * pMiddle;
72 : : BiNode * pTmp;
73 : : sal_uInt32 nEle, i;
74 : :
75 [ + + ]: 1321762 : if( pList ){
76 [ - + ]: 657016 : while( pList->Left() )
77 : 0 : pList = pList->Left();
78 : 657016 : pTmp = pList;
79 [ + + ]: 4269868 : for( nEle = 0; pTmp->Right(); nEle++ )
80 : 3612852 : pTmp = pTmp->Right();
81 : 657016 : pMiddle = pList;
82 [ + + ]: 657016 : if( nEle / 2 )
83 [ + + ]: 1958420 : for( i = 0; i < (nEle / 2); i++ )
84 : 1690296 : pMiddle = pMiddle->Right();
85 : : else
86 : 388892 : pList = (BiNode *)0;
87 : :
88 [ + + ]: 657016 : if( NULL != (pTmp = pMiddle->Left()) ) // rechten Zeiger auf Null
89 : 268124 : pTmp->pRight = (BiNode *)0;
90 : :
91 : : // linken Zeiger auf Null
92 [ + + ]: 657016 : if( NULL != (pRightNode = pMiddle->Right()) )
93 : 381162 : pRightNode->pLeft = (BiNode *)0;
94 : :
95 : 657016 : pMiddle->pLeft = ChangeDLListBTree( pList );
96 : 657016 : pMiddle->pRight = ChangeDLListBTree( pRightNode );
97 : :
98 : 657016 : return( pMiddle );
99 : : }
100 : 1321762 : return( pList );
101 : : }
102 : :
103 : : /*************************************************************************
104 : : |*
105 : : |* BiNode::ChangeBTreeDLList()
106 : : |*
107 : : *************************************************************************/
108 : 657016 : BiNode * BiNode::ChangeBTreeDLList(){
109 : : BiNode * pList;
110 : : BiNode * pLL_RN; // linke Liste rechter Knoten
111 : :
112 [ + + ]: 657016 : if( Right() ){
113 : 434574 : pList = Right()->ChangeBTreeDLList();
114 : 434574 : pRight = pList;
115 : 434574 : pList->pLeft = this;
116 : : }
117 : 657016 : pList = this;
118 [ + + ]: 657016 : if( Left() ){
119 : 214712 : pLL_RN = pList = Left()->ChangeBTreeDLList();
120 [ + + ]: 1466426 : while( pLL_RN->Right() )
121 : 1251714 : pLL_RN = pLL_RN->Right();
122 : 214712 : pLeft = pLL_RN;
123 : 214712 : pLL_RN->pRight = this;
124 : : }
125 : 657016 : 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 : 43368 : 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 : 43368 : int nCmp = Compare( pSearch );
249 : :
250 [ + + ]: 43368 : if( nCmp == GREATER ){
251 [ + + ]: 44 : if( Left() )
252 : 14 : return ((NameNode *)Left())->Search( pSearch );
253 : : }
254 [ + + ]: 43324 : else if( nCmp == LESS ){
255 [ + + ]: 226 : if( Right() )
256 : 34 : return ((NameNode *)Right())->Search( pSearch );
257 : : }
258 : : else
259 : 43098 : return( (NameNode *)this );
260 : :
261 : 43368 : return( NULL );
262 : : }
263 : :
264 : : /*************************************************************************
265 : : |*
266 : : |* NameNode::Insert()
267 : : |*
268 : : *************************************************************************/
269 : 1839096 : 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 : 1839096 : sal_Bool bRet = sal_True;
275 : 1839096 : int nCmp = Compare( pTN );
276 : :
277 : 1839096 : *pnDepth += 1;
278 [ + + ]: 1839096 : if( nCmp == GREATER ){
279 [ + + ]: 53398 : if( Left() )
280 : 50086 : bRet = ((NameNode *)Left())->Insert( pTN, pnDepth );
281 : : else
282 : 3312 : pLeft = pTN;
283 : : }
284 : : else{
285 [ + + ]: 1785698 : if( Right() )
286 : 1642618 : bRet = ((NameNode *)Right())->Insert( pTN, pnDepth );
287 : : else
288 : 143080 : pRight = pTN;
289 [ - + ]: 1785698 : if( nCmp == EQUAL )
290 : 0 : bRet = sal_False;
291 : : };
292 : 1839096 : return( bRet );
293 : : }
294 : :
295 : : /*************************************************************************
296 : : |*
297 : : |* NameNode::Insert()
298 : : |*
299 : : *************************************************************************/
300 : 146392 : 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 : 146392 : sal_uInt32 nDepth = 0;
305 : : sal_Bool bRet;
306 : :
307 [ + - ]: 146392 : bRet = Insert( pTN, &nDepth );
308 [ + - ]: 146392 : if( bRet ){
309 [ + + ]: 146392 : if( nDepth > 20 ){
310 [ + + ]: 7154 : if( Left() )
311 [ + - ][ + - ]: 598 : pLeft = ChangeDLListBTree( Left()->ChangeBTreeDLList() );
312 [ + + ]: 7154 : if( Right() )
313 [ + - ][ + - ]: 7132 : pRight = ChangeDLListBTree( Right()->ChangeBTreeDLList() );
314 : : }
315 : : }
316 : :
317 : 146392 : 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 : 43320 : IdNode * IdNode::Search( sal_uInt32 nTypeName ) const{
354 : 43320 : return( (IdNode *)NameNode::Search( (const void *)&nTypeName ) );
355 : : }
356 : :
357 : : /*************************************************************************
358 : : |*
359 : : |* IdNode::Compare()
360 : : |*
361 : : *************************************************************************/
362 : 1839096 : COMPARE IdNode::Compare( const NameNode * pSearch ) const
363 : : {
364 [ + + ]: 1839096 : if( GetId() < (sal_uInt32)(((const IdNode *)pSearch)->GetId()) )
365 : 1785698 : return LESS;
366 [ + - ]: 53398 : else if( GetId() > (sal_uInt32)(((const IdNode *)pSearch)->GetId()) )
367 : 53398 : return GREATER;
368 : : else
369 : 1839096 : return EQUAL;
370 : : }
371 : :
372 : 43368 : COMPARE IdNode::Compare( const void * pSearch ) const{
373 : : // pSearch ist ein Zeiger auf sal_uInt32
374 : :
375 [ + + ]: 43368 : if( GetId() < *((const sal_uInt32 *)pSearch) )
376 : 226 : return LESS;
377 [ + + ]: 43142 : else if( GetId() > *((const sal_uInt32 *)pSearch) )
378 : 44 : return GREATER;
379 : : else
380 : 43368 : 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: */
|
