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 :
21 : #include <stdlib.h>
22 : #include <stdio.h>
23 : #include <string.h>
24 :
25 : #include <tools/link.hxx>
26 : #include <rsctree.hxx>
27 :
28 :
29 165760 : BiNode::BiNode()
30 : {
31 165760 : pLeft = pRight = NULL;
32 165760 : }
33 :
34 165760 : BiNode::~BiNode()
35 : {
36 165760 : }
37 :
38 91658 : void BiNode::EnumNodes( Link aLink ) const
39 : {
40 91658 : if( Left() )
41 37318 : Left()->EnumNodes( aLink );
42 91658 : aLink.Call( (BiNode *)this );
43 91658 : if( Right() )
44 51781 : Right()->EnumNodes( aLink );
45 91658 : }
46 :
47 635800 : BiNode * BiNode::ChangeDLListBTree( BiNode * pList )
48 : {
49 : BiNode * pMiddle;
50 : BiNode * pTmp;
51 : sal_uInt32 nEle, i;
52 :
53 635800 : if( pList )
54 : {
55 632896 : while( pList->Left() )
56 0 : pList = pList->Left();
57 316448 : pTmp = pList;
58 :
59 2190419 : for( nEle = 0; pTmp->Right(); nEle++ )
60 1873971 : pTmp = pTmp->Right();
61 :
62 316448 : pMiddle = pList;
63 316448 : if( nEle / 2 )
64 : {
65 1014184 : for( i = 0; i < (nEle / 2); i++ )
66 : {
67 882696 : pMiddle = pMiddle->Right();
68 : }
69 : }
70 : else
71 : {
72 184960 : pList = (BiNode *)0;
73 : }
74 316448 : if( NULL != (pTmp = pMiddle->Left()) ) // rechten Zeiger auf Null
75 131488 : pTmp->pRight = (BiNode *)0;
76 :
77 : // linken Zeiger auf Null
78 316448 : BiNode * pRightNode = pMiddle->Right();
79 316448 : if (pRightNode)
80 182056 : pRightNode->pLeft = (BiNode *)0;
81 :
82 316448 : pMiddle->pLeft = ChangeDLListBTree( pList );
83 316448 : pMiddle->pRight = ChangeDLListBTree( pRightNode );
84 :
85 316448 : return pMiddle;
86 : }
87 319352 : return pList;
88 : }
89 :
90 316448 : BiNode * BiNode::ChangeBTreeDLList()
91 : {
92 : BiNode * pList;
93 : BiNode * pLL_RN; // linke Liste rechter Knoten
94 :
95 316448 : if( Right() )
96 : {
97 200866 : pList = Right()->ChangeBTreeDLList();
98 200866 : pRight = pList;
99 200866 : pList->pLeft = this;
100 : }
101 316448 : pList = this;
102 316448 : if( Left() )
103 : {
104 112678 : pLL_RN = pList = Left()->ChangeBTreeDLList();
105 :
106 917311 : while( pLL_RN->Right() )
107 691955 : pLL_RN = pLL_RN->Right();
108 :
109 112678 : pLeft = pLL_RN;
110 112678 : pLL_RN->pRight = this;
111 : }
112 316448 : return pList;
113 : }
114 :
115 0 : NameNode * NameNode::Remove( NameNode * pRemove )
116 : {
117 0 : NameNode * pRoot = this;
118 0 : NameNode * pParent = SearchParent( pRemove );
119 :
120 0 : if( pParent )
121 : {
122 0 : if( pParent->Left() &&
123 0 : (EQUAL == pRemove->Compare( pParent->Left() ) ) )
124 : {
125 0 : pParent->pLeft = pRemove->Left();
126 0 : if( pRemove->Right() )
127 0 : pParent->Insert( pRemove->Right() );
128 : }
129 0 : else if( pParent->Right() &&
130 0 : (EQUAL == pRemove->Compare( pParent->Right() ) ) )
131 : {
132 0 : pParent->pRight = pRemove->Right();
133 0 : if( pRemove->Left() )
134 0 : pParent->Insert( pRemove->Left() );
135 : }
136 : }
137 0 : else if( EQUAL == this->Compare( pRemove ) )
138 : {
139 0 : if( Right() )
140 : {
141 0 : pRoot = Right();
142 0 : if( Left() )
143 0 : Right()->Insert( Left() );
144 : }
145 : else
146 : {
147 0 : pRoot = Left();
148 : }
149 : }
150 0 : pRemove->pLeft = pRemove->pRight = NULL;
151 :
152 0 : return pRoot;
153 : }
154 :
155 :
156 0 : COMPARE NameNode::Compare( const NameNode * pCompare ) const
157 : {
158 0 : if( (long)this < (long)pCompare )
159 0 : return LESS;
160 0 : else if( (long)this > (long)pCompare )
161 0 : return GREATER;
162 : else
163 0 : return EQUAL;
164 : }
165 :
166 0 : COMPARE NameNode::Compare( const void * pCompare ) const
167 : {
168 0 : if( (long)this < (long)pCompare )
169 0 : return LESS;
170 0 : else if( (long)this > (long)pCompare )
171 0 : return GREATER;
172 : else
173 0 : return EQUAL;
174 : }
175 :
176 : // search for a parent node.
177 : // return a pointer to the parent node if found.
178 : // otherwise return 0.
179 0 : NameNode* NameNode::SearchParent( const NameNode * pSearch ) const
180 : {
181 0 : int nCmp = Compare( pSearch );
182 :
183 0 : if( nCmp == GREATER )
184 : {
185 0 : if( Left() )
186 : {
187 0 : if( ((NameNode *)Left())->Compare( pSearch ) == EQUAL )
188 0 : return (NameNode *)this;
189 0 : return ((NameNode *)Left())->SearchParent( pSearch );
190 : };
191 : }
192 0 : else if( nCmp == LESS )
193 : {
194 0 : if( Right() )
195 : {
196 0 : if( ((NameNode *)Right())->Compare( pSearch ) == EQUAL )
197 0 : return (NameNode *)this;
198 0 : return ((NameNode *)Right())->SearchParent( pSearch );
199 : }
200 : }
201 0 : return (NameNode *)NULL;
202 : }
203 :
204 : // search for a node.
205 : // return a pointer to the node if found.
206 : // otherwise return 0.
207 0 : NameNode* NameNode::Search( const NameNode * pSearch ) const
208 : {
209 0 : int nCmp = Compare( pSearch );
210 :
211 0 : if( nCmp == GREATER )
212 : {
213 0 : if( Left() )
214 0 : return ((NameNode *)Left())->Search( pSearch );
215 : }
216 0 : else if( nCmp == LESS )
217 : {
218 0 : if( Right() )
219 0 : return ((NameNode *)Right())->Search( pSearch );
220 : }
221 : else
222 0 : return (NameNode *)this;
223 :
224 0 : return NULL;
225 : }
226 :
227 : // search for a node.
228 : // return a pointer to the node if found.
229 : // otherwise return 0.
230 16895 : NameNode* NameNode::Search( const void * pSearch ) const
231 : {
232 16895 : int nCmp = Compare( pSearch );
233 :
234 16895 : if( nCmp == GREATER )
235 : {
236 18 : if( Left() )
237 0 : return ((NameNode *)Left())->Search( pSearch );
238 : }
239 16877 : else if( nCmp == LESS )
240 : {
241 97 : if( Right() )
242 1 : return ((NameNode *)Right())->Search( pSearch );
243 : }
244 : else
245 16780 : return (NameNode *)this;
246 :
247 114 : return NULL;
248 : }
249 :
250 : // Ein Knoten wird in den Baum eingefuegt
251 : // Gibt es einen Knoten mit dem gleichen Namen, dann return false
252 : // sonst return true. Der Knoten wird auf jeden Fall eingefuegt.
253 :
254 612077 : bool NameNode::Insert( NameNode * pTN, sal_uInt32* pnDepth )
255 : {
256 612077 : bool bRet = true;
257 612077 : int nCmp = Compare( pTN );
258 :
259 612077 : *pnDepth += 1;
260 612077 : if( nCmp == GREATER )
261 : {
262 28985 : if( Left() )
263 27377 : bRet = ((NameNode *)Left())->Insert( pTN, pnDepth );
264 : else
265 1608 : pLeft = pTN;
266 : }
267 : else
268 : {
269 583092 : if( Right() )
270 535545 : bRet = ((NameNode *)Right())->Insert( pTN, pnDepth );
271 : else
272 47547 : pRight = pTN;
273 :
274 583092 : if( nCmp == EQUAL )
275 0 : bRet = false;
276 : }
277 612077 : return bRet;
278 : }
279 :
280 : // insert a node in the tree.
281 : // if the node with the same name is in, return false and no insert.
282 : // if not return true.
283 49155 : bool NameNode::Insert( NameNode * pTN )
284 : {
285 49155 : sal_uInt32 nDepth = 0;
286 : bool bRet;
287 :
288 49155 : bRet = Insert( pTN, &nDepth );
289 49155 : if( bRet )
290 : {
291 49155 : if( nDepth > 20 )
292 : {
293 2588 : if( Left() )
294 324 : pLeft = ChangeDLListBTree( Left()->ChangeBTreeDLList() );
295 2588 : if( Right() )
296 2580 : pRight = ChangeDLListBTree( Right()->ChangeBTreeDLList() );
297 : }
298 : }
299 :
300 49155 : return bRet;
301 : }
302 :
303 0 : void NameNode::OrderTree()
304 : {
305 0 : NameNode * pTmpLeft = (NameNode *)Left();
306 0 : NameNode * pTmpRight = (NameNode *)Right();
307 :
308 0 : pLeft = NULL;
309 0 : pRight = NULL;
310 0 : SubOrderTree( pTmpLeft );
311 0 : SubOrderTree( pTmpRight );
312 0 : }
313 :
314 0 : void NameNode::SubOrderTree( NameNode * pOrderNode )
315 : {
316 0 : if( pOrderNode )
317 : {
318 0 : NameNode * pTmpLeft = (NameNode *)pOrderNode->Left();
319 0 : NameNode * pTmpRight = (NameNode *)pOrderNode->Right();
320 0 : pOrderNode->pLeft = NULL;
321 0 : pOrderNode->pRight = NULL;
322 0 : Insert( pOrderNode );
323 0 : SubOrderTree( pTmpLeft );
324 0 : SubOrderTree( pTmpRight );
325 : }
326 0 : }
327 :
328 16894 : IdNode * IdNode::Search( sal_uInt32 nTypeName ) const
329 : {
330 16894 : return (IdNode *)NameNode::Search( (const void *)&nTypeName );
331 : }
332 :
333 612077 : COMPARE IdNode::Compare( const NameNode * pSearch ) const
334 : {
335 612077 : if( GetId() < (sal_uInt32)(((const IdNode *)pSearch)->GetId()) )
336 583092 : return LESS;
337 28985 : else if( GetId() > (sal_uInt32)(((const IdNode *)pSearch)->GetId()) )
338 28985 : return GREATER;
339 : else
340 0 : return EQUAL;
341 : }
342 :
343 : // pSearch ist ein Zeiger auf sal_uInt32
344 16895 : COMPARE IdNode::Compare( const void * pSearch ) const
345 : {
346 16895 : if( GetId() < *((const sal_uInt32 *)pSearch) )
347 97 : return LESS;
348 16798 : else if( GetId() > *((const sal_uInt32 *)pSearch) )
349 18 : return GREATER;
350 : else
351 16780 : return EQUAL;
352 : }
353 :
354 0 : sal_uInt32 IdNode::GetId() const
355 : {
356 0 : return 0xFFFFFFFF;
357 : }
358 :
359 0 : StringNode * StringNode::Search( const char * pSearch ) const
360 : {
361 0 : return (StringNode *)NameNode::Search( (const void *)pSearch );
362 : }
363 :
364 0 : COMPARE StringNode::Compare( const NameNode * pSearch ) const
365 : {
366 : int nCmp = strcmp( m_aName.getStr(),
367 0 : ((const StringNode *)pSearch)->m_aName.getStr() );
368 0 : if( nCmp < 0 )
369 0 : return LESS;
370 0 : else if( nCmp > 0 )
371 0 : return GREATER;
372 : else
373 0 : return EQUAL;
374 : }
375 :
376 : // pSearch ist ein Zeiger auf const char *
377 0 : COMPARE StringNode::Compare( const void * pSearch ) const
378 : {
379 0 : int nCmp = strcmp( m_aName.getStr(), (const char *)pSearch );
380 :
381 0 : if( nCmp < 0 )
382 0 : return LESS;
383 0 : else if( nCmp > 0 )
384 0 : return GREATER;
385 : else
386 0 : return EQUAL;
387 : }
388 :
389 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
