001: /*
002: * Copyright (C) <2005> <Steve Woodcock>
003: *
004: * Created on 09 May 2003, 13:22
005: */
006: package com.jofti.btree;
007:
008: /**
009: * Abstract base class for leaf node variations<p>
010: *
011: * @author Steve Woodcock<br>
012: * @version 1.9<br>
013: */
014: abstract class AbstractLeafNode extends Node implements Leaf {
015:
016: protected NodeLink nextNode = null;
017:
018: protected IndexNodeEntry parentKey = null;
019:
020: protected boolean deleted = false;
021:
022: protected Comparable rightValue;
023:
024: /**
025: * Comment for <code>serialVersionUID</code>
026: */
027:
028: /** Creates a new instance of LeafNode */
029: AbstractLeafNode() {
030: }
031:
032: /**
033: * Resets the next node if the current next node that it points to is marked as deleted
034: * (no entries and marked as deleted). This allows the garbage to collect the node and effectively
035: * means that the node is deleted from the Tree.<p>
036: */
037: protected void resetNextNode() {
038: if (nextNode != null && nextNode.getNode() != null
039: && nextNode.getNode().isDeleted()) {
040: nextNode = nextNode.getNode().getLinkNode();
041: }
042: }
043:
044: /**
045: * A specific binary search method for the leaf node. This adapted from the standard binary
046: * search implementation in the Collections API.<p>
047: *
048: * Note need to investigate the use of the Uniform Binary Search variations in Knuth Soting and searching.
049: * <p>
050: * @param list1 - the list to search<br>
051: * @param obj - the object to find <br>
052: * @return A leafnodeEntry if one is matched - otherwise null;
053: */
054: protected LeafNodeEntry indexedBinaryRetrieve(Object[] list1,
055: Object obj) {
056: int i = 0;
057: int size = entryNumber;
058: for (int j = size - 1; i <= j;) {
059: int k = i + j >> 1;
060: LeafNodeEntry obj1 = (LeafNodeEntry) list1[k];
061: int l = obj1.getValue().compareTo(obj);
062: if (l < 0)
063: i = k + 1;
064: else if (l > 0)
065: j = k - 1;
066: else
067: return obj1;
068: }
069:
070: return null;
071: }
072:
073: /*
074: * (non-Javadoc)
075: *
076: * @see com.jofti.btree.Node#getLinkNode()
077: */
078: public NodeLink getLinkNode() {
079:
080: return nextNode;
081: }
082:
083: /*
084: * (non-Javadoc)
085: *
086: * @see com.jofti.btree.Node#setLinkNode(com.jofti.btree.Node)
087: */
088: public void setLinkNode(NodeLink node) {
089: this .nextNode = node;
090:
091: }
092:
093: /**
094: * Check whether the node has been marked as deleted.<p>
095: *
096: * @return Returns whether the node has been marked as deleted.
097: */
098: public boolean isDeleted() {
099: return deleted;
100: }
101:
102: /**
103: * Sets a node to be deleted.<p>
104: * @param deleted sets the node to be deleted.
105: */
106: public void setDeleted(boolean deleted) {
107: this .deleted = deleted;
108: }
109:
110: /* (non-Javadoc)
111: * @see com.jofti.btree.INode#getRightValue()
112: */
113: public Comparable getRightValue() {
114:
115: return rightValue;
116: }
117:
118: /* (non-Javadoc)
119: * @see com.jofti.btree.INode#setRightValue(java.lang.Comparable)
120: */
121: public void setRightValue(Comparable value) {
122: this .rightValue = value;
123:
124: }
125:
126: /* (non-Javadoc)
127: * @see com.jofti.btree.INode#getEntryNumber()
128: */
129: public int getEntryNumber() {
130: return entryNumber;
131: }
132:
133: /* (non-Javadoc)
134: * @see com.jofti.btree.Leaf#getEntry(java.lang.Comparable)
135: */
136: public LeafNodeEntry getEntry(Comparable value) {
137: if (entryNumber == 0) {
138: return null;
139: }
140:
141: // look through list and see if we have a match
142:
143: return indexedBinaryRetrieve(realGetEntries(), value);
144:
145: }
146:
147: /* (non-Javadoc)
148: * @see com.jofti.btree.INode#isUnderFull()
149: */
150: public boolean isUnderFull() {
151: if (entryNumber < BTree.getMaxNodeSize()) {
152: return true;
153: }
154: return false;
155: }
156:
157: protected abstract Object[] realGetEntries();
158:
159: /* (non-Javadoc)
160: * @see com.jofti.btree.INode#isEmpty()
161: */
162: public boolean isEmpty() {
163: return entryNumber == 0;
164: }
165: }
|