001: /*
002: * IndexNode.java
003: * Copyright (C) <2005> <Steve Woodcock>
004: *
005:
006: * Created on 09 May 2003, 15:13
007: */
008: package com.jofti.btree;
009:
010: /**
011: * <p>
012: * The internal nodes in the BTree. These nodes do not contain any data - they are simply pointers to lower level
013: * index nodes or leaf nodes.</p>
014: * <p>
015: * Each node follows the pattern of an indexnode which is an array of sorted pointers to a lower level index or leaf node. Each entry
016: * in the array contains the largest value in the subtree under the pointer. The Node itself in its right value contains the largest
017: * entry in its array.
018: * </p>
019: *
020: * @author Steve Woodcock (steve@jofti.com)<br>
021: * @version 1.12<br>
022: *
023: */
024: class IndexNode extends Node {
025:
026: private IndexNodeEntry parentKey = null;
027:
028: protected Object[] keyList = new Object[BTree.getMaxNodeSize() + 1];
029:
030: private Comparable rightValue = null;
031: // b+ linked list metaphor to traverse sequentially
032:
033: private NodeLink nextNode = null;
034:
035: private boolean deleted = false;
036:
037: /**
038: * @return if the node has been deleted.
039: */
040: public boolean isDeleted() {
041: return deleted;
042: }
043:
044: /**
045: * @param deleted Sets the node to deleted if true.
046: */
047: public void setDeleted(boolean deleted) {
048: this .deleted = deleted;
049: }
050:
051: /** Creates a new instance of IndexNode */
052: protected IndexNode() {
053: }
054:
055: /**
056: * Returns the node entry where the entry should be. This is achieved by comparing the right values
057: * of the node entries in the node.<p>
058: *
059: *
060: * @param entry the value to find.
061: * @return The node in this index node that the value should be in (or in a subtreee from that node).
062: */
063: public Node getContainingNode(Comparable entry) {
064:
065: if (entryNumber == 0) {
066: return null;
067: }
068:
069: // look through list and see if we have a match
070:
071: return indexedBinaryRetrieve(keyList, entry);
072:
073: }
074:
075: protected Node indexedBinaryRetrieve(Object[] list1, Object obj) {
076: int i = 0;
077: IndexNodeEntry entry = null;
078: int size = entryNumber;
079: for (int j = size - 1; i <= j;) {
080: int k = i + j >> 1;
081: entry = (IndexNodeEntry) list1[k];
082: int l = entry.value.compareTo(obj);
083: if (l < 0) {
084: i = k + 1;
085: } else if (l > 0) {
086: j = k - 1;
087: } else {
088: return entry.getChildNode();
089: }
090: }
091:
092: i = -(i + 1);
093:
094: if (-i == entryNumber) {
095: return entry.getChildNode();
096: } else {
097: return ((IndexNodeEntry) list1[-i - 1]).getChildNode();
098: }
099:
100: }
101:
102: protected int indexedBinaryLocate(Object[] list1, Object obj) {
103:
104: int low = 0;
105: int high = entryNumber - 1;
106:
107: IndexNodeEntry entry = null;
108: while (low <= high) {
109: int mid = (low + high) >> 1;
110:
111: entry = (IndexNodeEntry) list1[mid];
112: int cmp = entry.compareTo(obj);
113:
114: if (cmp < 0)
115: low = mid + 1;
116: else if (cmp > 0)
117: high = mid - 1;
118: else
119: return mid; // key found
120: }
121: return -(low + 1); // key not found
122:
123: }
124:
125: /* (non-Javadoc)
126: * @see com.jofti.btree.INode#insertEntry(com.jofti.btree.NodeEntry)
127: */
128: public Object[] insertEntry(NodeEntry key) {
129:
130: //lets reset the next node if it is deleted
131: resetNextNode();
132:
133: IndexNodeEntry entry = (IndexNodeEntry) key;
134:
135: // if there are no entries then set it in
136: if (entryNumber == 0) {
137: keyList[0] = entry;
138: entry.setContainingNode(this );
139: entryNumber++;
140: rightValue = entry.getValue();
141: return keyList;
142:
143: } else {
144: //loop through entries to find right place
145: // we do not use a binary search here as we want to do different things
146: for (int i = 0; i < entryNumber; i++) {
147: IndexNodeEntry listEntry = (IndexNodeEntry) keyList[i];
148: // the current node is bigger so insert here
149:
150: // is it bigger than a value in the list
151: int comparison = listEntry.getValue().compareTo(
152: entry.getValue());
153: if (comparison > 0) {
154:
155: System.arraycopy(keyList, i, keyList, i + 1,
156: entryNumber - i);
157: keyList[i] = entry;
158:
159: entry.setContainingNode(this );
160: entryNumber++;
161: return keyList;
162: // is it equal - which means we will need to rest the conflicting value to make sure
163: // there is no problem - should be as the result of a split
164: } else if (comparison == 0) {
165: // this is a split node that has a key value that is equal
166: listEntry.updateValue();
167: if (i == entryNumber - 1) {
168: keyList[entryNumber] = entry;
169: rightValue = entry.getValue();
170:
171: } else {
172: int inner = i + 1;
173: System.arraycopy(keyList, inner, keyList,
174: inner + 1, entryNumber - inner);
175: keyList[inner] = entry;
176: }
177: entry.setContainingNode(this );
178: entryNumber++;
179: return keyList;
180: }
181: }
182:
183: keyList[entryNumber] = entry;
184: rightValue = entry.getValue();
185: entry.setContainingNode(this );
186: entryNumber++;
187: return keyList;
188: }
189:
190: }
191:
192: private void resetNextNode() {
193: if (nextNode != null && nextNode.getNode() != null
194: && nextNode.getNode().isDeleted()) {
195: nextNode = nextNode.getNode().getLinkNode();
196: }
197: }
198:
199: /**
200: * updates the key right value for the node entry passed in.<p>
201: *
202: * @param key - the key for the entry to update.<br>
203: * @return - true of the right value for the entire node was updated - false if the node entry was
204: * not the right most entry.
205: */
206: public boolean updateEntry(NodeEntry key) {
207:
208: resetNextNode();
209: IndexNodeEntry entry = (IndexNodeEntry) key;
210:
211: if (entryNumber == 0) {
212:
213: return false;
214:
215: } else {
216: int length = entryNumber;
217: for (int i = 0; i < length; i++) {
218: IndexNodeEntry listEntry = (IndexNodeEntry) keyList[i];
219: if (listEntry.getValue().equals(entry.getValue())) {
220: // this is a split node that has a key value that is equal
221: listEntry.updateValue();
222: if (i == length - 1) {
223: rightValue = listEntry.getValue();
224: }
225: return true;
226: }
227: }
228: return false;
229: }
230:
231: }
232:
233: /**
234: * Sets the keylist for the node entries.<p>
235: *
236: * @param keys - the new entry list for the node.
237: */
238: public void setKeyList(Object[] temp) {
239:
240: for (int i = 0; i < entryNumber; i++) {
241: IndexNodeEntry entry = (IndexNodeEntry) temp[i];
242: entry.setContainingNode(this );
243: keyList[i] = entry;
244: }
245:
246: }
247:
248: /* (non-Javadoc)
249: * @see com.jofti.btree.INode#isEmpty()
250: */
251: public boolean isEmpty() {
252: if (entryNumber == 0) {
253: return true;
254: }
255: return false;
256: }
257:
258: /* (non-Javadoc)
259: * @see com.jofti.btree.INode#getRightValue()
260: */
261: public Comparable getRightValue() {
262: return rightValue;
263: }
264:
265: IndexNodeEntry getParentKey() {
266: return parentKey;
267: }
268:
269: public String toString() {
270: StringBuffer buf = new StringBuffer();
271: buf.append(" IndexNode{");
272:
273: buf.append(" rightValue:" + getRightValue() + "}");
274: return buf.toString();
275: }
276:
277: public boolean isUnderFull() {
278: if (entryNumber < BTree.getMaxNodeSize()) {
279: return true;
280: }
281: return false;
282: }
283:
284: /** Setter for property parentNode.
285: * @param parentNode New value of property parentNode.
286: *
287: *
288: */
289: void setParentKey(IndexNodeEntry parentKey) {
290: this .parentKey = parentKey;
291: }
292:
293: /* (non-Javadoc)
294: * @see com.jofti.btree.INode#deleteEntry(com.jofti.btree.NodeEntry)
295: */
296: public boolean deleteEntry(NodeEntry entry) {
297:
298: resetNextNode();
299:
300: int location = indexedBinaryLocate(keyList, entry);
301:
302: if (location >= 0) {
303: // we need to remove the entry
304:
305: int numMoved = entryNumber - location - 1;
306: if (numMoved > 0)
307: System.arraycopy(keyList, location + 1, keyList,
308: location, numMoved);
309: keyList[--entryNumber] = null; // Let gc do its work
310:
311: if (entryNumber == 0) {
312: rightValue = BTree.MIN_RIGHT_VALUE;
313: } else {
314: ((IndexNodeEntry) keyList[entryNumber - 1])
315: .updateValue();
316: setRightValue(((IndexNodeEntry) keyList[entryNumber - 1])
317: .getValue());
318: }
319: return true;
320: }
321: return false;
322:
323: }
324:
325: /* (non-Javadoc)
326: * @see com.jofti.btree.INode#splitNode()
327: */
328: public Node splitNode(Object[] entries) {
329: // first insert the entry
330:
331: Object[] entriesList = split(entries, entryNumber);
332:
333: Node newNode = NodeFactory.getInstance().createIndexNode();
334:
335: Comparable currentRight = rightValue;
336:
337: //set up new node
338: EntrySplitWrapper newEntries = ((EntrySplitWrapper) entriesList[1]);
339:
340: newNode.entryNumber = newEntries.size;
341: newNode.setEntries((Object[]) newEntries.entries);
342:
343: newNode.setRightValue(currentRight);
344: newNode.setLinkNode(getLinkNode());
345:
346: // replace values in current node
347:
348: EntrySplitWrapper replacements = (EntrySplitWrapper) entriesList[0];
349:
350: keyList = (Object[]) replacements.entries;
351: entryNumber = replacements.size;
352: setRightValue(((NodeEntry) keyList[entryNumber - 1]).getValue());
353:
354: return newNode;
355:
356: }
357:
358: /* (non-Javadoc)
359: * @see com.jofti.btree.INode#getEntryNumber()
360: */
361: public int getEntryNumber() {
362: return entryNumber;
363: }
364:
365: /* (non-Javadoc)
366: * @see com.jofti.btree.INode#getEntries()
367: */
368: public Object[] getEntries() {
369:
370: return keyList;
371: }
372:
373: /* (non-Javadoc)
374: * @see com.jofti.btree.Node#setRightValue(java.lang.Comparable)
375: */
376: public void setRightValue(Comparable value) {
377: this .rightValue = value;
378:
379: }
380:
381: /* (non-Javadoc)
382: * @see com.jofti.btree.Node#split()
383: */
384:
385: /* (non-Javadoc)
386: * @see com.jofti.btree.Node#setEntries(java.util.List)
387: */
388: public void setEntries(Object[] entries) {
389: setKeyList(entries);
390:
391: }
392:
393: /* (non-Javadoc)
394: * @see com.jofti.btree.Node#getLinkNode()
395: */
396: public NodeLink getLinkNode() {
397:
398: return nextNode;
399: }
400:
401: /* (non-Javadoc)
402: * @see com.jofti.btree.Node#setLinkNode(com.jofti.btree.Node)
403: */
404: public void setLinkNode(NodeLink node) {
405: this .nextNode = node;
406:
407: }
408:
409: /**
410: * This method checks to see if the value should be contained in the leaf nodes that are
411: * children of this indexNode (or children of its children). It does not check if the actual
412: * value is in the sub tree- rather it checks if its values are larger than this value.<p>
413: *
414: * @param value
415: *
416: * @return true if the node has a larger value in it - false otherwise.
417: */
418: public boolean contains(Comparable value) {
419: if (entryNumber == 0 || value == null) {
420: return false;
421: }
422:
423: if (value instanceof MinComparableValue) {
424: return true;
425: }
426: return rightValue.compareTo(value) >= 0;
427: }
428:
429: }
|