KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > ozoneDB > DxLib > DxBBnode


1 // You can redistribute this software and/or modify it under the terms of
2
// the Ozone Library License version 1 published by ozone-db.org.
3
//
4
// The original code and portions created by SMB are
5
// Copyright (C) 1997-@year@ by SMB GmbH. All rights reserved.
6
//
7
// $Id: DxBBnode.java,v 1.7 2000/10/28 16:55:14 daniela Exp $
8

9 package org.ozoneDB.DxLib;
10
11 import java.io.IOException JavaDoc;
12
13
14 final class DxBBnode extends DxObject {
15     
16     final static long serialVersionUID = 1L;
17     
18     DxBBnode pa;
19     DxBBnode re;
20     DxBBnode li;
21     boolean isRight;
22     int lWeight;
23     int rWeight;
24     Object JavaDoc data;
25     Object JavaDoc key;
26     DxComparator comparator;
27     
28     
29     /** */
30     public DxBBnode() {
31         lWeight = 1;
32         rWeight = 1;
33     }
34     
35     
36     /** */
37     public DxBBnode( Object JavaDoc _data, Object JavaDoc _key, DxComparator _comparator ) {
38         lWeight = 1;
39         rWeight = 1;
40         data = _data;
41         key = _key;
42         comparator = _comparator;
43     }
44     
45     
46     /** */
47     public DxBBnode findNodeKey( Object JavaDoc _key ) {
48         if (comparator.compareEquals( key, _key )) {
49             return this;
50         }
51         if (comparator.compareIsLess( key, _key ) && re != null) {
52             return re.findNodeKey( _key );
53         } else {
54             if (li != null) {
55                 return li.findNodeKey( _key );
56             }
57         }
58         return null;
59     }
60     
61     
62     /** */
63     public DxBBnode findNodeObject( Object JavaDoc obj ) {
64         if (data.equals( obj )) {
65             return this;
66         }
67         DxBBnode node = null;
68         if (li != null) {
69             node = li.findNodeObject( obj );
70         }
71         if (re != null && node == null) {
72             node = re.findNodeObject( obj );
73         }
74         return node;
75     }
76     
77     
78     /** */
79     public boolean insertNode( DxBBnode node ) {
80         boolean ret = true;
81         if (key != null && comparator.compareEquals( node.key, key )) {
82             return false;
83         }
84         if (key != null && comparator.compareIsLess( node.key, key )) {
85             if (li == null) {
86                 li = node;
87                 node.pa = this;
88                 node.isRight = false;
89                 lWeight++;
90             } else {
91                 if (ret = li.insertNode( node )) {
92                     lWeight++;
93                 }
94             }
95         } else {
96             if (re == null) {
97                 re = node;
98                 node.pa = this;
99                 node.isRight = true;
100                 rWeight++;
101             } else {
102                 if (ret = re.insertNode( node )) {
103                     rWeight++;
104                 }
105             }
106         }
107         checkWeight();
108         return ret;
109     }
110     
111     
112     /** */
113     public DxBBnode removeNodeKey( Object JavaDoc _key ) {
114         DxBBnode P = null;
115         
116         if (comparator.compareEquals( key, _key )) {
117             
118             // ohne linken und rechten sohn
119
if (re == null && li == null) {
120                 if (isRight) {
121                     pa.re = null;
122                 } else {
123                     pa.li = null;
124                 }
125                 pa = null;
126                 return this;
127             }
128             
129             // in knoten gefunden (nur linker sohn)
130
if (re == null && li != null) {
131                 li.isRight = isRight;
132                 li.pa = pa;
133                 if (isRight) {
134                     pa.re = li;
135                 } else {
136                     pa.li = li;
137                 }
138                 return this;
139             }
140             
141             // in knoten gefunden (nur rechter sohn)
142
if (re != null && li == null) {
143                 re.isRight = isRight;
144                 re.pa = pa;
145                 if (isRight) {
146                     pa.re = re;
147                 } else {
148                     pa.li = re;
149                 }
150                 return this;
151             }
152             
153             // in knoten gefunden (mit beiden soehnen)
154
if (re != null && li != null) {
155                 DxBBnode pre = li.succNode();
156                 removeNodeKey( pre.key );
157                 DxBBnode ret = new DxBBnode( data, key, comparator );
158                 data = pre.data;
159                 key = pre.key;
160                 return ret;
161             }
162         }
163         // in diesem knoten nicht gefunden;
164
if (comparator.compareIsLess( _key, key )) {
165             if (li != null) {
166                 P = li.removeNodeKey( _key );
167                 if (P != null) {
168                     if (li != null) {
169                         lWeight--;
170                     } else {
171                         lWeight = 1;
172                     }
173                 }
174             }
175         } else {
176             if (re != null) {
177                 P = re.removeNodeKey( _key );
178                 if (P != null) {
179                     if (re != null) {
180                         rWeight--;
181                     } else {
182                         rWeight = 1;
183                     }
184                 }
185             }
186         }
187         
188         checkWeight();
189         return P;
190     }
191     
192     
193     /** */
194     public DxBBnode succNode() {
195         if (re != null) {
196             return re.succNode();
197         } else {
198             return this;
199         }
200     }
201     
202     
203     /** */
204     public int p() {
205         return lWeight * 100 / (rWeight + lWeight);
206     }
207     
208     
209     /** */
210     public void checkWeight() {
211         int _p = p();
212         if (_p <= DxBBTree.BB_ALPHA) {
213             if (re != null && re.p() > DxBBTree.BB_BALANCE) {
214                 re.rotRight();
215             }
216             rotLeft();
217             return;
218         }
219         if (_p >= (DxBBTree.BB_MAX - DxBBTree.BB_ALPHA)) {
220             if (li != null && li.p() < DxBBTree.BB_BALANCE) {
221                 li.rotLeft();
222             }
223             rotRight();
224         }
225     }
226     
227     
228     /** */
229     public void rotLeft() {
230         DxBBnode rl;
231         if (isRight) {
232             pa.re = re;
233         } else {
234             pa.li = re;
235         }
236         re.pa = pa;
237         re.isRight = isRight;
238         isRight = false;
239         
240         rl = re.li;
241         re.li = this;
242         pa = re;
243         re = rl;
244         if (re != null) {
245             re.pa = this;
246             rWeight = re.rWeight + re.lWeight;
247             re.isRight = true;
248         } else {
249             rWeight = 1;
250         }
251         pa.lWeight = lWeight + rWeight;
252     }
253     
254     
255     /** */
256     public void rotRight() {
257         DxBBnode lr;
258         if (isRight) {
259             pa.re = li;
260         } else {
261             pa.li = li;
262         }
263         li.pa = pa;
264         li.isRight = isRight;
265         isRight = true;
266         
267         lr = li.re;
268         li.re = this;
269         pa = li;
270         li = lr;
271         if (li != null) {
272             li.pa = this;
273             lWeight = li.lWeight + li.rWeight;
274             li.isRight = false;
275         } else {
276             lWeight = 1;
277         }
278         pa.rWeight = lWeight + rWeight;
279     }
280     
281     
282     /** */
283     public void print( int n ) {
284         if (re != null) {
285             re.print( n + 5 );
286         }
287         
288         for (int i = 0; i < n; i++) {
289             System.out.print( " " );
290         }
291         if (data != null) {
292             System.out.println( ":" + p() );
293         } else {
294             System.out.println( "-------------------------" );
295         }
296         
297         if (li != null) {
298             li.print( n + 5 );
299         }
300     }
301 }
302
Popular Tags