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 0 : BiNode::BiNode()
30 : {
31 0 : pLeft = pRight = NULL;
32 0 : }
33 :
34 0 : BiNode::~BiNode()
35 : {
36 0 : }
37 :
38 0 : void BiNode::EnumNodes( Link aLink ) const
39 : {
40 0 : if( Left() )
41 0 : Left()->EnumNodes( aLink );
42 0 : aLink.Call( (BiNode *)this );
43 0 : if( Right() )
44 0 : Right()->EnumNodes( aLink );
45 0 : }
46 :
47 0 : BiNode * BiNode::ChangeDLListBTree( BiNode * pList )
48 : {
49 : BiNode * pMiddle;
50 : BiNode * pTmp;
51 : sal_uInt32 nEle, i;
52 :
53 0 : if( pList )
54 : {
55 0 : while( pList->Left() )
56 0 : pList = pList->Left();
57 0 : pTmp = pList;
58 :
59 0 : for( nEle = 0; pTmp->Right(); nEle++ )
60 0 : pTmp = pTmp->Right();
61 :
62 0 : pMiddle = pList;
63 0 : if( nEle / 2 )
64 : {
65 0 : for( i = 0; i < (nEle / 2); i++ )
66 : {
67 0 : pMiddle = pMiddle->Right();
68 : }
69 : }
70 : else
71 : {
72 0 : pList = (BiNode *)0;
73 : }
74 0 : if( NULL != (pTmp = pMiddle->Left()) ) // rechten Zeiger auf Null
75 0 : pTmp->pRight = (BiNode *)0;
76 :
77 : // linken Zeiger auf Null
78 0 : BiNode * pRightNode = pMiddle->Right();
79 0 : if (pRightNode)
80 0 : pRightNode->pLeft = (BiNode *)0;
81 :
82 0 : pMiddle->pLeft = ChangeDLListBTree( pList );
83 0 : pMiddle->pRight = ChangeDLListBTree( pRightNode );
84 :
85 0 : return pMiddle;
86 : }
87 0 : return pList;
88 : }
89 :
90 0 : BiNode * BiNode::ChangeBTreeDLList()
91 : {
92 : BiNode * pList;
93 : BiNode * pLL_RN; // linke Liste rechter Knoten
94 :
95 0 : if( Right() )
96 : {
97 0 : pList = Right()->ChangeBTreeDLList();
98 0 : pRight = pList;
99 0 : pList->pLeft = this;
100 : }
101 0 : pList = this;
102 0 : if( Left() )
103 : {
104 0 : pLL_RN = pList = Left()->ChangeBTreeDLList();
105 :
106 0 : while( pLL_RN->Right() )
107 0 : pLL_RN = pLL_RN->Right();
108 :
109 0 : pLeft = pLL_RN;
110 0 : pLL_RN->pRight = this;
111 : }
112 0 : 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 0 : NameNode* NameNode::Search( const void * pSearch ) const
231 : {
232 0 : int nCmp = Compare( pSearch );
233 :
234 0 : if( nCmp == GREATER )
235 : {
236 0 : if( Left() )
237 0 : return ((NameNode *)Left())->Search( pSearch );
238 : }
239 0 : else if( nCmp == LESS )
240 : {
241 0 : if( Right() )
242 0 : return ((NameNode *)Right())->Search( pSearch );
243 : }
244 : else
245 0 : return (NameNode *)this;
246 :
247 0 : 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 0 : bool NameNode::Insert( NameNode * pTN, sal_uInt32* pnDepth )
255 : {
256 0 : bool bRet = true;
257 0 : int nCmp = Compare( pTN );
258 :
259 0 : *pnDepth += 1;
260 0 : if( nCmp == GREATER )
261 : {
262 0 : if( Left() )
263 0 : bRet = ((NameNode *)Left())->Insert( pTN, pnDepth );
264 : else
265 0 : pLeft = pTN;
266 : }
267 : else
268 : {
269 0 : if( Right() )
270 0 : bRet = ((NameNode *)Right())->Insert( pTN, pnDepth );
271 : else
272 0 : pRight = pTN;
273 :
274 0 : if( nCmp == EQUAL )
275 0 : bRet = false;
276 : }
277 0 : 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 0 : bool NameNode::Insert( NameNode * pTN )
284 : {
285 0 : sal_uInt32 nDepth = 0;
286 : bool bRet;
287 :
288 0 : bRet = Insert( pTN, &nDepth );
289 0 : if( bRet )
290 : {
291 0 : if( nDepth > 20 )
292 : {
293 0 : if( Left() )
294 0 : pLeft = ChangeDLListBTree( Left()->ChangeBTreeDLList() );
295 0 : if( Right() )
296 0 : pRight = ChangeDLListBTree( Right()->ChangeBTreeDLList() );
297 : }
298 : }
299 :
300 0 : 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 0 : IdNode * IdNode::Search( sal_uInt32 nTypeName ) const
329 : {
330 0 : return (IdNode *)NameNode::Search( (const void *)&nTypeName );
331 : }
332 :
333 0 : COMPARE IdNode::Compare( const NameNode * pSearch ) const
334 : {
335 0 : if( GetId() < (sal_uInt32)(((const IdNode *)pSearch)->GetId()) )
336 0 : return LESS;
337 0 : else if( GetId() > (sal_uInt32)(((const IdNode *)pSearch)->GetId()) )
338 0 : return GREATER;
339 : else
340 0 : return EQUAL;
341 : }
342 :
343 : // pSearch ist ein Zeiger auf sal_uInt32
344 0 : COMPARE IdNode::Compare( const void * pSearch ) const
345 : {
346 0 : if( GetId() < *((const sal_uInt32 *)pSearch) )
347 0 : return LESS;
348 0 : else if( GetId() > *((const sal_uInt32 *)pSearch) )
349 0 : return GREATER;
350 : else
351 0 : 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: */
|
