DxBBTree


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: DxBBTree.java,v 1.1 2001/12/18 10:31:30 per_nyfelt Exp $
8   
9   package org.ozoneDB.DxLib;
10  
11  
12  /**
13   * Non-public class that represents a key->value map implemented
14   * using a BBTree. This is used for DxTreeMap and DxTreeSet implementations.
15   */
16  final class DxBBTree {
17      
18      final static long serialVersionUID = 1L;
19      
20      //balance faktor fuer den baum (0.25..0.32); je kleiner, desto
21      //schiefer ist evtl. der baum und umso weniger muss auch rotiert werden
22      final static int BB_ALPHA = 26;
23      final static int BB_BALANCE = 50;
24      final static int BB_MAX = 100;
25      
26      DxBBnode quietRoot;
27      int itemCount = 0;
28      DxComparator comparator = null;
29      
30      
31      /**
32       */
33      public DxBBTree() {
34          comparator = new DxStandardComparator();
35          quietRoot = new DxBBnode( null, null, comparator );
36      }
37      
38      
39      /**
40       */
41      public DxBBTree( DxComparator _comparator ) {
42          comparator = _comparator;
43          quietRoot = new DxBBnode( null, null, comparator );
44      }
45      
46      
47      /**
48       */
49      public synchronized boolean addForKey( Object   obj, Object   key ) {
50          DxBBnode node = new DxBBnode( obj, key, comparator );
51          if (itemCount == 0) {
52              node.isRight = true;
53              node.pa = quietRoot;
54              quietRoot.re = node;
55              itemCount++;
56              return true;
57          } 
58          if (root().insertNode( node )) {
59              itemCount++;
60              return true;
61          } else {
62              return false;
63          } 
64      } 
65      
66      
67      /**
68       */
69      public Object   elementForKey( Object   key ) {
70          if (root() == null) {
71              return null;
72          } 
73          
74          DxBBnode node = root().findNodeKey( key );
75          if (node != null) {
76              return node.data;
77          } 
78          
79          return null;
80      } 
81      
82      
83      /**
84       */
85      public Object   keyForElement( Object   obj ) {
86          if (root() == null) {
87              return null;
88          } 
89          
90          DxBBnode node = root().findNodeObject( obj );
91          if (node != null) {
92              return node.key;
93          } 
94          
95          return null;
96      } 
97      
98      
99      /**
100      */
101     public synchronized Object   removeForKey( Object   key ) {
102         if (root() == null) {
103             return null;
104         } 
105         
106         DxBBnode node = root().removeNodeKey( key );
107         if (node != null) {
108             itemCount--;
109             return node.data;
110         } else {
111             return null;
112         } 
113     } 
114     
115     
116     /**
117      */
118     public int count() {
119         return itemCount;
120     } 
121     
122     
123     /**
124      */
125     public boolean isEmpty() {
126         return itemCount == 0;
127     } 
128     
129     
130     /**
131      */
132     public boolean containsKey( Object   key ) {
133         return elementForKey( key ) != null;
134     } 
135     
136     
137     /**
138      */
139     DxBBnode root() {
140         return quietRoot.re;
141     } 
142 }
143
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags