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 126456 : BiNode::BiNode()
30 : {
31 126456 : pLeft = pRight = NULL;
32 126456 : }
33 :
34 126456 : BiNode::~BiNode()
35 : {
36 126456 : }
37 :
38 60273 : void BiNode::EnumNodes( Link<> aLink ) const
39 : {
40 60273 : if( Left() )
41 22200 : Left()->EnumNodes( aLink );
42 60273 : aLink.Call( const_cast<BiNode *>(this) );
43 60273 : if( Right() )
44 36006 : Right()->EnumNodes( aLink );
45 60273 : }
46 :
47 553099 : BiNode * BiNode::ChangeDLListBTree( BiNode * pList )
48 : {
49 : BiNode * pMiddle;
50 : BiNode * pTmp;
51 : sal_uInt32 nEle, i;
52 :
53 553099 : if( pList )
54 : {
55 551140 : while( pList->Left() )
56 0 : pList = pList->Left();
57 275570 : pTmp = pList;
58 :
59 2017412 : for( nEle = 0; pTmp->Right(); nEle++ )
60 1741842 : pTmp = pTmp->Right();
61 :
62 275570 : pMiddle = pList;
63 275570 : if( nEle / 2 )
64 : {
65 938979 : for( i = 0; i < (nEle / 2); i++ )
66 : {
67 824245 : pMiddle = pMiddle->Right();
68 : }
69 : }
70 : else
71 : {
72 160836 : pList = nullptr;
73 : }
74 275570 : if( NULL != (pTmp = pMiddle->Left()) ) // rechten Zeiger auf Null
75 114734 : pTmp->pRight = nullptr;
76 :
77 : // linken Zeiger auf Null
78 275570 : BiNode * pRightNode = pMiddle->Right();
79 275570 : if (pRightNode)
80 158877 : pRightNode->pLeft = nullptr;
81 :
82 275570 : pMiddle->pLeft = ChangeDLListBTree( pList );
83 275570 : pMiddle->pRight = ChangeDLListBTree( pRightNode );
84 :
85 275570 : return pMiddle;
86 : }
87 277529 : return pList;
88 : }
89 :
90 275570 : BiNode * BiNode::ChangeBTreeDLList()
91 : {
92 : BiNode * pList;
93 : BiNode * pLL_RN; // linke Liste rechter Knoten
94 :
95 275570 : if( Right() )
96 : {
97 170210 : pList = Right()->ChangeBTreeDLList();
98 170210 : pRight = pList;
99 170210 : pList->pLeft = this;
100 : }
101 275570 : pList = this;
102 275570 : if( Left() )
103 : {
104 103401 : pLL_RN = pList = Left()->ChangeBTreeDLList();
105 :
106 885216 : while( pLL_RN->Right() )
107 678414 : pLL_RN = pLL_RN->Right();
108 :
109 103401 : pLeft = pLL_RN;
110 103401 : pLL_RN->pRight = this;
111 : }
112 275570 : 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( reinterpret_cast<sal_uIntPtr>(this) < reinterpret_cast<sal_uIntPtr>(pCompare) )
159 0 : return LESS;
160 0 : else if( reinterpret_cast<sal_uIntPtr>(this) > reinterpret_cast<sal_uIntPtr>(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( reinterpret_cast<sal_uIntPtr>(this) < reinterpret_cast<sal_uIntPtr>(pCompare) )
169 0 : return LESS;
170 0 : else if( reinterpret_cast<sal_uIntPtr>(this) > reinterpret_cast<sal_uIntPtr>(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( Left()->Compare( pSearch ) == EQUAL )
188 0 : return const_cast<NameNode *>(this);
189 0 : return Left()->SearchParent( pSearch );
190 : }
191 : }
192 0 : else if( nCmp == LESS )
193 : {
194 0 : if( Right() )
195 : {
196 0 : if( Right()->Compare( pSearch ) == EQUAL )
197 0 : return const_cast<NameNode *>(this);
198 0 : return Right()->SearchParent( pSearch );
199 : }
200 : }
201 0 : return nullptr;
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 Left()->Search( pSearch );
215 : }
216 0 : else if( nCmp == LESS )
217 : {
218 0 : if( Right() )
219 0 : return Right()->Search( pSearch );
220 : }
221 : else
222 0 : return const_cast<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 15635 : NameNode* NameNode::Search( const void * pSearch ) const
231 : {
232 15635 : int nCmp = Compare( pSearch );
233 :
234 15635 : if( nCmp == GREATER )
235 : {
236 13 : if( Left() )
237 0 : return Left()->Search( pSearch );
238 : }
239 15622 : else if( nCmp == LESS )
240 : {
241 94 : if( Right() )
242 0 : return Right()->Search( pSearch );
243 : }
244 : else
245 15528 : return const_cast<NameNode *>(this);
246 :
247 107 : 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 405851 : bool NameNode::Insert( NameNode * pTN, sal_uInt32* pnDepth )
255 : {
256 405851 : bool bRet = true;
257 405851 : int nCmp = Compare( pTN );
258 :
259 405851 : *pnDepth += 1;
260 405851 : if( nCmp == GREATER )
261 : {
262 29493 : if( Left() )
263 27877 : bRet = Left()->Insert( pTN, pnDepth );
264 : else
265 1616 : pLeft = pTN;
266 : }
267 : else
268 : {
269 376358 : if( Right() )
270 344150 : bRet = Right()->Insert( pTN, pnDepth );
271 : else
272 32208 : pRight = pTN;
273 :
274 376358 : if( nCmp == EQUAL )
275 0 : bRet = false;
276 : }
277 405851 : 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 33824 : bool NameNode::Insert( NameNode * pTN )
284 : {
285 33824 : sal_uInt32 nDepth = 0;
286 : bool bRet;
287 :
288 33824 : bRet = Insert( pTN, &nDepth );
289 33824 : if( bRet )
290 : {
291 33824 : if( nDepth > 20 )
292 : {
293 1640 : if( Left() )
294 327 : pLeft = ChangeDLListBTree( Left()->ChangeBTreeDLList() );
295 1640 : if( Right() )
296 1632 : pRight = ChangeDLListBTree( Right()->ChangeBTreeDLList() );
297 : }
298 : }
299 :
300 33824 : return bRet;
301 : }
302 :
303 0 : void NameNode::OrderTree()
304 : {
305 0 : NameNode * pTmpLeft = static_cast<NameNode *>(Left());
306 0 : NameNode * pTmpRight = static_cast<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 = static_cast<NameNode *>(pOrderNode->Left());
319 0 : NameNode * pTmpRight = static_cast<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 15635 : IdNode * IdNode::Search( sal_uInt32 nTypeName ) const
329 : {
330 15635 : return static_cast<IdNode *>(NameNode::Search( static_cast<const void *>(&nTypeName) ));
331 : }
332 :
333 405851 : COMPARE IdNode::Compare( const NameNode * pSearch ) const
334 : {
335 405851 : if( GetId() < (sal_uInt32)(static_cast<const IdNode *>(pSearch)->GetId()) )
336 376358 : return LESS;
337 29493 : else if( GetId() > (sal_uInt32)(static_cast<const IdNode *>(pSearch)->GetId()) )
338 29493 : return GREATER;
339 : else
340 0 : return EQUAL;
341 : }
342 :
343 : // pSearch ist ein Zeiger auf sal_uInt32
344 15635 : COMPARE IdNode::Compare( const void * pSearch ) const
345 : {
346 15635 : if( GetId() < *static_cast<const sal_uInt32 *>(pSearch) )
347 94 : return LESS;
348 15541 : else if( GetId() > *static_cast<const sal_uInt32 *>(pSearch) )
349 13 : return GREATER;
350 : else
351 15528 : 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 static_cast<StringNode *>(NameNode::Search( static_cast<const void *>(pSearch) ));
362 : }
363 :
364 0 : COMPARE StringNode::Compare( const NameNode * pSearch ) const
365 : {
366 : int nCmp = strcmp( m_aName.getStr(),
367 0 : static_cast<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(), static_cast<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: */
|
