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: DxBBTree.java,v 1.1 2001/12/18 10:31:30 per_nyfelt Exp $
008:
009: package org.ozoneDB.DxLib;
010:
011: import java.io.*;
012:
013: /**
014: * Non-public class that represents a key->value map implemented
015: * using a BBTree. This is used for DxTreeMap and DxTreeSet implementations.
016: */
017: final class DxBBTree {
018:
019: final static long serialVersionUID = 1L;
020:
021: //balance faktor fuer den baum (0.25..0.32); je kleiner, desto
022: //schiefer ist evtl. der baum und umso weniger muss auch rotiert werden
023: final static int BB_ALPHA = 26;
024: final static int BB_BALANCE = 50;
025: final static int BB_MAX = 100;
026:
027: DxBBnode quietRoot;
028: int itemCount = 0;
029: DxComparator comparator = null;
030:
031: /**
032: */
033: public DxBBTree() {
034: comparator = new DxStandardComparator();
035: quietRoot = new DxBBnode(null, null, comparator);
036: }
037:
038: /**
039: */
040: public DxBBTree(DxComparator _comparator) {
041: comparator = _comparator;
042: quietRoot = new DxBBnode(null, null, comparator);
043: }
044:
045: /**
046: */
047: public synchronized boolean addForKey(Object obj, Object key) {
048: DxBBnode node = new DxBBnode(obj, key, comparator);
049: if (itemCount == 0) {
050: node.isRight = true;
051: node.pa = quietRoot;
052: quietRoot.re = node;
053: itemCount++;
054: return true;
055: }
056: if (root().insertNode(node)) {
057: itemCount++;
058: return true;
059: } else {
060: return false;
061: }
062: }
063:
064: /**
065: */
066: public Object elementForKey(Object key) {
067: if (root() == null) {
068: return null;
069: }
070:
071: DxBBnode node = root().findNodeKey(key);
072: if (node != null) {
073: return node.data;
074: }
075:
076: return null;
077: }
078:
079: /**
080: */
081: public Object keyForElement(Object obj) {
082: if (root() == null) {
083: return null;
084: }
085:
086: DxBBnode node = root().findNodeObject(obj);
087: if (node != null) {
088: return node.key;
089: }
090:
091: return null;
092: }
093:
094: /**
095: */
096: public synchronized Object removeForKey(Object key) {
097: if (root() == null) {
098: return null;
099: }
100:
101: DxBBnode node = root().removeNodeKey(key);
102: if (node != null) {
103: itemCount--;
104: return node.data;
105: } else {
106: return null;
107: }
108: }
109:
110: /**
111: */
112: public int count() {
113: return itemCount;
114: }
115:
116: /**
117: */
118: public boolean isEmpty() {
119: return itemCount == 0;
120: }
121:
122: /**
123: */
124: public boolean containsKey(Object key) {
125: return elementForKey(key) != null;
126: }
127:
128: /**
129: */
130: DxBBnode root() {
131: return quietRoot.re;
132: }
133: }
|