|
1
6 package com.jofti.btree;
7 import com.jofti.exception.JoftiException;
8
9
10
11
18 class LeafNode extends AbstractLeafNode implements Leaf{
19
20 protected Object  [] entries = null;
21
22
23
24
25 LeafNode()
26 {
27 }
28
29
30
31
32
33 public String toString()
34 {
35 StringBuffer buf = new StringBuffer ();
36 buf.append(" LeafNode{");
37 Object [] tempEntries =entries;
38 for (int i = 0; i < entryNumber; i++)
39 {
40 buf.append(" Entry:" + tempEntries[i]);
41 }
42
43 buf.append("} ");
44 return buf.toString();
45 }
46
47
48
49 public Object [] insertEntry(NodeEntry entry) throws JoftiException {
50 Object [] tempEntries =entries;
51 if (entry == null || entry.getValue() ==null){
52 throw new JoftiException("Null node entry cannot be inserted");
53 }
54
55 resetNextNode();
56 if (entryNumber == 0)
57 {
58 tempEntries[0]=entry;
59 entryNumber++;
60 rightValue=entry.getValue();
61 return tempEntries;
62 } else if (rightValue.compareTo(entry.getValue()) >=0)
63 {
64
65 int result = indexedBinaryLocate(tempEntries, entry);
66
67 if (result <0){
68 int index = (-result)-1;
70 if (index <= entryNumber){
71 System.arraycopy(tempEntries, index, tempEntries, index + 1,
72 entryNumber - index);
73 tempEntries[index] = entry;
74
75 }else{
76 tempEntries[entryNumber]=entry;
77 }
78 entryNumber++;
79 return tempEntries;
80 } else{
81 LeafNodeEntry listEntry =(LeafNodeEntry) tempEntries[result];
82 listEntry.addUniqueIdSet(((LeafNodeEntry)entry).getUniqueIdSet());
83 return tempEntries;
84 }
85
86 }
87 throw new JoftiException("unable to insert " + entry.getValue()+ "as is bigger than current right value");
88
89 }
90
91
92 protected int indexedBinaryLocate(Object [] list1, Object obj)
93 {
94
95 int low = 0;
96 int high = entryNumber-1;
97
98 LeafNodeEntry entry =null;
99 while (low <= high) {
100 int mid = (low + high) >> 1;
101
102 entry = (LeafNodeEntry)list1[mid];
103 int cmp = entry.compareTo(obj);
104
105 if (cmp < 0)
106 low = mid + 1;
107 else if (cmp > 0)
108 high = mid - 1;
109 else
110 return mid; }
112 return -(low + 1);
114 }
115
116
117 public boolean deleteEntry(NodeEntry entry) {
118 resetNextNode();
119 Object [] tempEntries =entries;
120
121 if (entry == null || entry.getValue() ==null){
122 return false;
123 }
124 if (entryNumber == 0)
125 {
126 return false;
127 } else
128 {
129 int result = indexedBinaryLocate(tempEntries, entry);
130 if (result >=0){
131 LeafNodeEntry listEntry = (LeafNodeEntry)tempEntries[result];
132
133 listEntry.removeAllIds(((LeafNodeEntry)entry).getUniqueIdSet());
134
135 if (listEntry.getUniqueIdSize() ==0){
136 int numMoved = entryNumber - result - 1;
137 if (numMoved > 0)
138 System.arraycopy(tempEntries, result+1, tempEntries, result,
139 numMoved);
140 tempEntries[--entryNumber] = null;
142 if (entryNumber == 0){
144 rightValue = BTree.MIN_RIGHT_VALUE;
145 }else{
146 rightValue = ((LeafNodeEntry)tempEntries[entryNumber-1]).getValue();
147 }
148 return true;
149 }
150 }
151 }
152
153 return false;
154
155 }
156
157
158
159 public void setEntries(Object [] temp) {
160 entries = temp;
161
162
163 }
164
165
166 public LeafNodeEntry getEntry(Comparable value) {
167 if (entryNumber ==0)
168 {
169 return null;
170 }
171
172
174 return indexedBinaryRetrieve(entries, value);
175
176
177
178
179
180 }
181
182 public Object [] getEntries() {
183
184 Object [] objArr = new Object [entryNumber];
185 System.arraycopy(entries,0,objArr,0,entryNumber);
186 return objArr;
187
188
189 }
190
191 public Node splitNode(Object [] tempEntries) throws JoftiException{
192
194 Object [] entriesList = split(entries,entryNumber);
195
196 Node newNode = NodeFactory.getInstance().createLeafNode();
197
198 Comparable currentRight = rightValue;
199
200
201 EntrySplitWrapper newEntries = ((EntrySplitWrapper)entriesList[1]);
203 newNode.entryNumber = newEntries.size;
204 newNode.setEntries((Object [])newEntries.entries );
205
206 newNode.setRightValue(currentRight);
207 newNode.setLinkNode(getLinkNode());
208
209 EntrySplitWrapper replacements = (EntrySplitWrapper)entriesList[0];
211
212
213 entries = (Object [])replacements.entries;
214 entryNumber = replacements.size;
215 setRightValue(((NodeEntry) entries[entryNumber - 1]).getValue());
216
217 return newNode;
218 }
219
220 protected Object [] realGetEntries() {
221
222 return entries;
223 }
224
225 public boolean contains(Comparable value) {
226 if (value != null){
227 return rightValue.compareTo(value) >=0;
228 }
229 return false;
230
231 }
232
233 public boolean isLeaf(){
234 return true;
235 }
236
237 }
238 |
Popular Tags |
Java API By Example, From Geeks To Geeks.