001: /*
002: * LeafNode.java
003: *
004: * Created on 09 May 2003, 13:22
005: */
006: package com.jofti.btree;
007:
008: import com.jofti.exception.JoftiException;
009:
010: /**
011: * The Implementation of a LeafNode. The node stores a list of LeafNodeEntries.
012: * <p>
013: *
014: * @author Steve Woodcock
015: * @version 1.0<br>
016: */
017: class LeafNode extends AbstractLeafNode implements Leaf {
018:
019: protected Object[] entries = null;
020:
021: /** Creates a new instance of LeafNode */
022: LeafNode() {
023: }
024:
025: public String toString() {
026: StringBuffer buf = new StringBuffer();
027: buf.append(" LeafNode{");
028: Object[] tempEntries = entries;
029: for (int i = 0; i < entryNumber; i++) {
030: buf.append(" Entry:" + tempEntries[i]);
031: }
032:
033: buf.append("} ");
034: return buf.toString();
035: }
036:
037: public Object[] insertEntry(NodeEntry entry) throws JoftiException {
038: Object[] tempEntries = entries;
039: if (entry == null || entry.getValue() == null) {
040: throw new JoftiException(
041: "Null node entry cannot be inserted");
042: }
043:
044: resetNextNode();
045: if (entryNumber == 0) {
046: tempEntries[0] = entry;
047: entryNumber++;
048: rightValue = entry.getValue();
049: return tempEntries;
050: } else if (rightValue.compareTo(entry.getValue()) >= 0) {
051:
052: int result = indexedBinaryLocate(tempEntries, entry);
053:
054: if (result < 0) {
055: // we need to insert it
056: int index = (-result) - 1;
057: if (index <= entryNumber) {
058: System.arraycopy(tempEntries, index, tempEntries,
059: index + 1, entryNumber - index);
060: tempEntries[index] = entry;
061:
062: } else {
063: tempEntries[entryNumber] = entry;
064: }
065: entryNumber++;
066: return tempEntries;
067: } else {
068: LeafNodeEntry listEntry = (LeafNodeEntry) tempEntries[result];
069: listEntry.addUniqueIdSet(((LeafNodeEntry) entry)
070: .getUniqueIdSet());
071: return tempEntries;
072: }
073:
074: }
075: throw new JoftiException("unable to insert " + entry.getValue()
076: + "as is bigger than current right value");
077:
078: }
079:
080: protected int indexedBinaryLocate(Object[] list1, Object obj) {
081:
082: int low = 0;
083: int high = entryNumber - 1;
084:
085: LeafNodeEntry entry = null;
086: while (low <= high) {
087: int mid = (low + high) >> 1;
088:
089: entry = (LeafNodeEntry) list1[mid];
090: int cmp = entry.compareTo(obj);
091:
092: if (cmp < 0)
093: low = mid + 1;
094: else if (cmp > 0)
095: high = mid - 1;
096: else
097: return mid; // key found
098: }
099: return -(low + 1); // key not found
100:
101: }
102:
103: public boolean deleteEntry(NodeEntry entry) {
104: resetNextNode();
105: Object[] tempEntries = entries;
106:
107: if (entry == null || entry.getValue() == null) {
108: return false;
109: }
110: if (entryNumber == 0) {
111: return false;
112: } else {
113: int result = indexedBinaryLocate(tempEntries, entry);
114: if (result >= 0) {
115: LeafNodeEntry listEntry = (LeafNodeEntry) tempEntries[result];
116:
117: listEntry.removeAllIds(((LeafNodeEntry) entry)
118: .getUniqueIdSet());
119:
120: if (listEntry.getUniqueIdSize() == 0) {
121: int numMoved = entryNumber - result - 1;
122: if (numMoved > 0)
123: System.arraycopy(tempEntries, result + 1,
124: tempEntries, result, numMoved);
125: tempEntries[--entryNumber] = null; // Let gc do its work
126:
127: // update the right value if we need to
128: if (entryNumber == 0) {
129: rightValue = BTree.MIN_RIGHT_VALUE;
130: } else {
131: rightValue = ((LeafNodeEntry) tempEntries[entryNumber - 1])
132: .getValue();
133: }
134: return true;
135: }
136: }
137: }
138:
139: return false;
140:
141: }
142:
143: public void setEntries(Object[] temp) {
144: entries = temp;
145:
146: }
147:
148: public LeafNodeEntry getEntry(Comparable value) {
149: if (entryNumber == 0) {
150: return null;
151: }
152:
153: // look through list and see if we have a match
154:
155: return indexedBinaryRetrieve(entries, value);
156:
157: }
158:
159: public Object[] getEntries() {
160:
161: Object[] objArr = new Object[entryNumber];
162: System.arraycopy(entries, 0, objArr, 0, entryNumber);
163: return objArr;
164:
165: }
166:
167: public Node splitNode(Object[] tempEntries) throws JoftiException {
168: // first insert the entry
169:
170: Object[] entriesList = split(entries, entryNumber);
171:
172: Node newNode = NodeFactory.getInstance().createLeafNode();
173:
174: Comparable currentRight = rightValue;
175:
176: //set up new node
177: EntrySplitWrapper newEntries = ((EntrySplitWrapper) entriesList[1]);
178: newNode.entryNumber = newEntries.size;
179: newNode.setEntries((Object[]) newEntries.entries);
180:
181: newNode.setRightValue(currentRight);
182: newNode.setLinkNode(getLinkNode());
183:
184: // replace values in current node
185: EntrySplitWrapper replacements = (EntrySplitWrapper) entriesList[0];
186:
187: entries = (Object[]) replacements.entries;
188: entryNumber = replacements.size;
189: setRightValue(((NodeEntry) entries[entryNumber - 1]).getValue());
190:
191: return newNode;
192: }
193:
194: protected Object[] realGetEntries() {
195:
196: return entries;
197: }
198:
199: public boolean contains(Comparable value) {
200: if (value != null) {
201: return rightValue.compareTo(value) >= 0;
202: }
203: return false;
204:
205: }
206:
207: public boolean isLeaf() {
208: return true;
209: }
210:
211: }
|