KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > jofti > btree > AbstractLeafNode


1 /*
2  * Copyright (C) <2005> <Steve Woodcock>
3  *
4  * Created on 09 May 2003, 13:22
5  */
6 package com.jofti.btree;
7
8
9
10
11
12 /**
13  * Abstract base class for leaf node variations<p>
14  *
15  * @author Steve Woodcock<br>
16  * @version 1.9<br>
17  */
18 abstract class AbstractLeafNode extends Node implements Leaf {
19
20
21     protected NodeLink nextNode = null;
22
23     protected IndexNodeEntry parentKey = null;
24
25     protected boolean deleted = false;
26
27     protected Comparable JavaDoc rightValue;
28
29     /**
30      * Comment for <code>serialVersionUID</code>
31      */
32     
33
34     /** Creates a new instance of LeafNode */
35     AbstractLeafNode() {
36     }
37
38     /**
39      * Resets the next node if the current next node that it points to is marked as deleted
40      * (no entries and marked as deleted). This allows the garbage to collect the node and effectively
41      * means that the node is deleted from the Tree.<p>
42      */
43     protected void resetNextNode() {
44         if (nextNode != null && nextNode.getNode() != null
45                 && nextNode.getNode().isDeleted()) {
46             nextNode = nextNode.getNode().getLinkNode();
47         }
48     }
49
50
51
52     /**
53      * A specific binary search method for the leaf node. This adapted from the standard binary
54      * search implementation in the Collections API.<p>
55      *
56      * Note need to investigate the use of the Uniform Binary Search variations in Knuth Soting and searching.
57      * <p>
58      * @param list1 - the list to search<br>
59      * @param obj - the object to find <br>
60      * @return A leafnodeEntry if one is matched - otherwise null;
61      */
62     protected LeafNodeEntry indexedBinaryRetrieve(Object JavaDoc[] list1, Object JavaDoc obj) {
63         int i = 0;
64         int size = entryNumber;
65         for (int j = size- 1; i <= j;) {
66             int k = i + j >> 1;
67             LeafNodeEntry obj1 = (LeafNodeEntry)list1[k];
68             int l = obj1.getValue().compareTo(obj);
69             if (l < 0)
70                 i = k + 1;
71             else if (l > 0)
72                 j = k - 1;
73             else
74                 return obj1;
75         }
76
77         return null;
78     }
79
80     /*
81      * (non-Javadoc)
82      *
83      * @see com.jofti.btree.Node#getLinkNode()
84      */
85     public NodeLink getLinkNode() {
86
87         return nextNode;
88     }
89
90     /*
91      * (non-Javadoc)
92      *
93      * @see com.jofti.btree.Node#setLinkNode(com.jofti.btree.Node)
94      */
95     public void setLinkNode(NodeLink node) {
96         this.nextNode = node;
97
98     }
99
100     /**
101      * Check whether the node has been marked as deleted.<p>
102      *
103      * @return Returns whether the node has been marked as deleted.
104      */
105     public boolean isDeleted() {
106         return deleted;
107     }
108
109     /**
110      * Sets a node to be deleted.<p>
111      * @param deleted sets the node to be deleted.
112      */
113     public void setDeleted(boolean deleted) {
114         this.deleted = deleted;
115     }
116
117     
118     /* (non-Javadoc)
119      * @see com.jofti.btree.INode#getRightValue()
120      */
121     public Comparable JavaDoc getRightValue() {
122         
123             return rightValue;
124     }
125
126     /* (non-Javadoc)
127      * @see com.jofti.btree.INode#setRightValue(java.lang.Comparable)
128      */
129     public void setRightValue(Comparable JavaDoc value) {
130         this.rightValue = value;
131         
132     }
133
134     
135
136     
137
138     /* (non-Javadoc)
139      * @see com.jofti.btree.INode#getEntryNumber()
140      */
141     public int getEntryNumber() {
142         return entryNumber;
143     }
144
145
146     /* (non-Javadoc)
147      * @see com.jofti.btree.Leaf#getEntry(java.lang.Comparable)
148      */
149     public LeafNodeEntry getEntry(Comparable JavaDoc value) {
150         if (entryNumber ==0)
151         {
152             return null;
153         }
154         
155         // look through list and see if we have a match
156
157         return indexedBinaryRetrieve(realGetEntries(), value);
158         
159         
160     
161             
162             
163     }
164
165     /* (non-Javadoc)
166      * @see com.jofti.btree.INode#isUnderFull()
167      */
168     public boolean isUnderFull() {
169         if (entryNumber < BTree.getMaxNodeSize())
170         {
171             return true;
172         }
173         return false;
174     }
175
176     
177     
178     
179     protected abstract Object JavaDoc[] realGetEntries();
180     
181     
182
183     /* (non-Javadoc)
184      * @see com.jofti.btree.INode#isEmpty()
185      */
186     public boolean isEmpty() {
187         return entryNumber ==0;
188     }
189 }
Popular Tags