1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
3 * This file is part of the LibreOffice project.
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/.
9 * This file incorporates work covered by the following license notice:
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 .
25 #include <tools/link.hxx>
26 #include <rsctree.hxx>
30 pLeft
= pRight
= NULL
;
36 void BiNode::EnumNodes( Link aLink
) const{
38 Left()->EnumNodes( aLink
);
39 aLink
.Call( (BiNode
*)this );
41 Right()->EnumNodes( aLink
);
44 BiNode
* BiNode::ChangeDLListBTree( BiNode
* pList
){
50 while( pList
->Left() )
51 pList
= pList
->Left();
53 for( nEle
= 0; pTmp
->Right(); nEle
++ )
57 for( i
= 0; i
< (nEle
/ 2); i
++ )
58 pMiddle
= pMiddle
->Right();
62 if( NULL
!= (pTmp
= pMiddle
->Left()) ) // rechten Zeiger auf Null
63 pTmp
->pRight
= (BiNode
*)0;
65 // linken Zeiger auf Null
66 BiNode
* pRightNode
= pMiddle
->Right();
68 pRightNode
->pLeft
= (BiNode
*)0;
70 pMiddle
->pLeft
= ChangeDLListBTree( pList
);
71 pMiddle
->pRight
= ChangeDLListBTree( pRightNode
);
78 BiNode
* BiNode::ChangeBTreeDLList(){
80 BiNode
* pLL_RN
; // linke Liste rechter Knoten
83 pList
= Right()->ChangeBTreeDLList();
89 pLL_RN
= pList
= Left()->ChangeBTreeDLList();
90 while( pLL_RN
->Right() )
91 pLL_RN
= pLL_RN
->Right();
93 pLL_RN
->pRight
= this;
98 NameNode
* NameNode::Remove( NameNode
* pRemove
){
99 NameNode
* pRoot
= this;
100 NameNode
* pParent
= SearchParent( pRemove
);
104 && (EQUAL
== pRemove
->Compare( pParent
->Left() ) ) ){
105 pParent
->pLeft
= pRemove
->Left();
106 if( pRemove
->Right() )
107 pParent
->Insert( pRemove
->Right() );
109 else if( pParent
->Right()
110 && (EQUAL
== pRemove
->Compare( pParent
->Right() ) ) ){
111 pParent
->pRight
= pRemove
->Right();
112 if( pRemove
->Left() )
113 pParent
->Insert( pRemove
->Left() );
116 else if( EQUAL
== this->Compare( pRemove
) ){
120 Right()->Insert( Left() );
126 pRemove
->pLeft
= pRemove
->pRight
= NULL
;
132 COMPARE
NameNode::Compare( const NameNode
* pCompare
) const{
133 if( (long)this < (long)pCompare
)
135 else if( (long)this > (long)pCompare
)
141 COMPARE
NameNode::Compare( const void * pCompare
) const{
142 if( (long)this < (long)pCompare
)
144 else if( (long)this > (long)pCompare
)
150 NameNode
* NameNode::SearchParent( const NameNode
* pSearch
) const{
151 // search for a parent node.
152 // return a pointer to the parent node if found.
153 // otherwise return 0.
154 int nCmp
= Compare( pSearch
);
156 if( nCmp
== GREATER
){
158 if( ((NameNode
*)Left())->Compare( pSearch
) == EQUAL
)
159 return (NameNode
*)this;
160 return ((NameNode
*)Left())->SearchParent( pSearch
);
163 else if( nCmp
== LESS
){
165 if( ((NameNode
*)Right())->Compare( pSearch
) == EQUAL
)
166 return (NameNode
*)this;
167 return ((NameNode
*)Right())->SearchParent( pSearch
);
170 return( (NameNode
*)NULL
);
173 NameNode
* NameNode::Search( const NameNode
* pSearch
) const{
174 // search for a node.
175 // return a pointer to the node if found.
176 // otherwise return 0.
177 int nCmp
= Compare( pSearch
);
179 if( nCmp
== GREATER
){
181 return ((NameNode
*)Left())->Search( pSearch
);
183 else if( nCmp
== LESS
){
185 return ((NameNode
*)Right())->Search( pSearch
);
188 return( (NameNode
*)this );
193 NameNode
* NameNode::Search( const void * pSearch
) const{
194 // search for a node.
195 // return a pointer to the node if found.
196 // otherwise return 0.
197 int nCmp
= Compare( pSearch
);
199 if( nCmp
== GREATER
){
201 return ((NameNode
*)Left())->Search( pSearch
);
203 else if( nCmp
== LESS
){
205 return ((NameNode
*)Right())->Search( pSearch
);
208 return( (NameNode
*)this );
213 sal_Bool
NameNode::Insert( NameNode
* pTN
, sal_uInt32
* pnDepth
){
214 // Ein Knoten wird in den Baum eingefuegt
215 // Gibt es einen Knoten mit dem gleichen Namen, dann return sal_False
216 // sonst return sal_True. Der Knoten wird auf jeden Fall eingefuegt.
218 sal_Bool bRet
= sal_True
;
219 int nCmp
= Compare( pTN
);
222 if( nCmp
== GREATER
){
224 bRet
= ((NameNode
*)Left())->Insert( pTN
, pnDepth
);
230 bRet
= ((NameNode
*)Right())->Insert( pTN
, pnDepth
);
239 sal_Bool
NameNode::Insert( NameNode
* pTN
){
240 // insert a node in the tree.
241 // if the node with the same name is in, return sal_False and no insert.
242 // if not return true.
243 sal_uInt32 nDepth
= 0;
246 bRet
= Insert( pTN
, &nDepth
);
250 pLeft
= ChangeDLListBTree( Left()->ChangeBTreeDLList() );
252 pRight
= ChangeDLListBTree( Right()->ChangeBTreeDLList() );
259 void NameNode::OrderTree(){
260 NameNode
* pTmpLeft
= (NameNode
*)Left();
261 NameNode
* pTmpRight
= (NameNode
*)Right();
265 SubOrderTree( pTmpLeft
);
266 SubOrderTree( pTmpRight
);
269 void NameNode::SubOrderTree( NameNode
* pOrderNode
){
271 NameNode
* pTmpLeft
= (NameNode
*)pOrderNode
->Left();
272 NameNode
* pTmpRight
= (NameNode
*)pOrderNode
->Right();
273 pOrderNode
->pLeft
= NULL
;
274 pOrderNode
->pRight
= NULL
;
275 Insert( pOrderNode
);
276 SubOrderTree( pTmpLeft
);
277 SubOrderTree( pTmpRight
);
281 IdNode
* IdNode::Search( sal_uInt32 nTypeName
) const{
282 return( (IdNode
*)NameNode::Search( (const void *)&nTypeName
) );
285 COMPARE
IdNode::Compare( const NameNode
* pSearch
) const
287 if( GetId() < (sal_uInt32
)(((const IdNode
*)pSearch
)->GetId()) )
289 else if( GetId() > (sal_uInt32
)(((const IdNode
*)pSearch
)->GetId()) )
295 COMPARE
IdNode::Compare( const void * pSearch
) const{
296 // pSearch ist ein Zeiger auf sal_uInt32
298 if( GetId() < *((const sal_uInt32
*)pSearch
) )
300 else if( GetId() > *((const sal_uInt32
*)pSearch
) )
306 sal_uInt32
IdNode::GetId() const
308 return( 0xFFFFFFFF );
311 StringNode
* StringNode::Search( const char * pSearch
) const{
312 return (StringNode
*)NameNode::Search( (const void *)pSearch
);
315 COMPARE
StringNode::Compare( const NameNode
* pSearch
) const
317 int nCmp
= strcmp( m_aName
.getStr(),
318 ((const StringNode
*)pSearch
)->m_aName
.getStr() );
327 COMPARE
StringNode::Compare( const void * pSearch
) const
329 // pSearch ist ein Zeiger auf const char *
330 int nCmp
= strcmp( m_aName
.getStr(), (const char *)pSearch
);
340 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */