1 9 package org.ozoneDB.DxLib; 10 11 import java.io.IOException ; 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 data; 25 Object key; 26 DxComparator comparator; 27 28 29 30 public DxBBnode() { 31 lWeight = 1; 32 rWeight = 1; 33 } 34 35 36 37 public DxBBnode( Object _data, Object _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 _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 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 _key ) { 114 DxBBnode P = null; 115 116 if (comparator.compareEquals( key, _key )) { 117 118 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 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 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 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 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 |