001: // You can redistribute this software and/or modify it under the terms of
002: // the Ozone Library License version 1 published by ozone-db.org.
003: //
004: // The original code and portions created by SMB are
005: // Copyright (C) 1997-@year@ by SMB GmbH. All rights reserved.
006: //
007: // $Id: DxBBnode.java,v 1.1 2001/12/18 10:31:30 per_nyfelt Exp $
008:
009: package org.ozoneDB.DxLib;
010:
011: import java.io.IOException;
012:
013: final class DxBBnode extends DxObject {
014:
015: final static long serialVersionUID = 1L;
016:
017: DxBBnode pa;
018: DxBBnode re;
019: DxBBnode li;
020: boolean isRight;
021: int lWeight;
022: int rWeight;
023: Object data;
024: Object key;
025: DxComparator comparator;
026:
027: /** */
028: public DxBBnode() {
029: lWeight = 1;
030: rWeight = 1;
031: }
032:
033: /** */
034: public DxBBnode(Object _data, Object _key, DxComparator _comparator) {
035: lWeight = 1;
036: rWeight = 1;
037: data = _data;
038: key = _key;
039: comparator = _comparator;
040: }
041:
042: /** */
043: public DxBBnode findNodeKey(Object _key) {
044: if (comparator.compareEquals(key, _key)) {
045: return this ;
046: }
047: if (comparator.compareIsLess(key, _key) && re != null) {
048: return re.findNodeKey(_key);
049: } else {
050: if (li != null) {
051: return li.findNodeKey(_key);
052: }
053: }
054: return null;
055: }
056:
057: /** */
058: public DxBBnode findNodeObject(Object obj) {
059: if (data.equals(obj)) {
060: return this ;
061: }
062: DxBBnode node = null;
063: if (li != null) {
064: node = li.findNodeObject(obj);
065: }
066: if (re != null && node == null) {
067: node = re.findNodeObject(obj);
068: }
069: return node;
070: }
071:
072: /** */
073: public boolean insertNode(DxBBnode node) {
074: boolean ret = true;
075: if (key != null && comparator.compareEquals(node.key, key)) {
076: return false;
077: }
078: if (key != null && comparator.compareIsLess(node.key, key)) {
079: if (li == null) {
080: li = node;
081: node.pa = this ;
082: node.isRight = false;
083: lWeight++;
084: } else {
085: if (ret = li.insertNode(node)) {
086: lWeight++;
087: }
088: }
089: } else {
090: if (re == null) {
091: re = node;
092: node.pa = this ;
093: node.isRight = true;
094: rWeight++;
095: } else {
096: if (ret = re.insertNode(node)) {
097: rWeight++;
098: }
099: }
100: }
101: checkWeight();
102: return ret;
103: }
104:
105: /** */
106: public DxBBnode removeNodeKey(Object _key) {
107: DxBBnode P = null;
108:
109: if (comparator.compareEquals(key, _key)) {
110:
111: // ohne linken und rechten sohn
112: if (re == null && li == null) {
113: if (isRight) {
114: pa.re = null;
115: } else {
116: pa.li = null;
117: }
118: pa = null;
119: return this ;
120: }
121:
122: // in knoten gefunden (nur linker sohn)
123: if (re == null && li != null) {
124: li.isRight = isRight;
125: li.pa = pa;
126: if (isRight) {
127: pa.re = li;
128: } else {
129: pa.li = li;
130: }
131: return this ;
132: }
133:
134: // in knoten gefunden (nur rechter sohn)
135: if (re != null && li == null) {
136: re.isRight = isRight;
137: re.pa = pa;
138: if (isRight) {
139: pa.re = re;
140: } else {
141: pa.li = re;
142: }
143: return this ;
144: }
145:
146: // in knoten gefunden (mit beiden soehnen)
147: if (re != null && li != null) {
148: DxBBnode pre = li.succNode();
149: removeNodeKey(pre.key);
150: DxBBnode ret = new DxBBnode(data, key, comparator);
151: data = pre.data;
152: key = pre.key;
153: return ret;
154: }
155: }
156: // in diesem knoten nicht gefunden;
157: if (comparator.compareIsLess(_key, key)) {
158: if (li != null) {
159: P = li.removeNodeKey(_key);
160: if (P != null) {
161: if (li != null) {
162: lWeight--;
163: } else {
164: lWeight = 1;
165: }
166: }
167: }
168: } else {
169: if (re != null) {
170: P = re.removeNodeKey(_key);
171: if (P != null) {
172: if (re != null) {
173: rWeight--;
174: } else {
175: rWeight = 1;
176: }
177: }
178: }
179: }
180:
181: checkWeight();
182: return P;
183: }
184:
185: /** */
186: public DxBBnode succNode() {
187: if (re != null) {
188: return re.succNode();
189: } else {
190: return this ;
191: }
192: }
193:
194: /** */
195: public int p() {
196: return lWeight * 100 / (rWeight + lWeight);
197: }
198:
199: /** */
200: public void checkWeight() {
201: int _p = p();
202: if (_p <= DxBBTree.BB_ALPHA) {
203: if (re != null && re.p() > DxBBTree.BB_BALANCE) {
204: re.rotRight();
205: }
206: rotLeft();
207: return;
208: }
209: if (_p >= (DxBBTree.BB_MAX - DxBBTree.BB_ALPHA)) {
210: if (li != null && li.p() < DxBBTree.BB_BALANCE) {
211: li.rotLeft();
212: }
213: rotRight();
214: }
215: }
216:
217: /** */
218: public void rotLeft() {
219: DxBBnode rl;
220: if (isRight) {
221: pa.re = re;
222: } else {
223: pa.li = re;
224: }
225: re.pa = pa;
226: re.isRight = isRight;
227: isRight = false;
228:
229: rl = re.li;
230: re.li = this ;
231: pa = re;
232: re = rl;
233: if (re != null) {
234: re.pa = this ;
235: rWeight = re.rWeight + re.lWeight;
236: re.isRight = true;
237: } else {
238: rWeight = 1;
239: }
240: pa.lWeight = lWeight + rWeight;
241: }
242:
243: /** */
244: public void rotRight() {
245: DxBBnode lr;
246: if (isRight) {
247: pa.re = li;
248: } else {
249: pa.li = li;
250: }
251: li.pa = pa;
252: li.isRight = isRight;
253: isRight = true;
254:
255: lr = li.re;
256: li.re = this ;
257: pa = li;
258: li = lr;
259: if (li != null) {
260: li.pa = this ;
261: lWeight = li.lWeight + li.rWeight;
262: li.isRight = false;
263: } else {
264: lWeight = 1;
265: }
266: pa.rWeight = lWeight + rWeight;
267: }
268:
269: /** */
270: public void print(int n) {
271: if (re != null) {
272: re.print(n + 5);
273: }
274:
275: for (int i = 0; i < n; i++) {
276: System.out.print(" ");
277: }
278: if (data != null) {
279: System.out.println(":" + p());
280: } else {
281: System.out.println("-------------------------");
282: }
283:
284: if (li != null) {
285: li.print(n + 5);
286: }
287: }
288: }
|