001: /*
002: * Created on 07-Oct-2004
003: *
004: * To change the template for this generated file go to
005: * Window - Preferences - Java - Code Generation - Code and Comments
006: */
007: package com.jofti.btree;
008:
009: import com.jofti.exception.JoftiException;
010: import com.jofti.oswego.concurrent.ReadWriteLock;
011:
012: /**
013:
014: * The interface for Nodes (both internal and leaf) in the BTree.<p>
015: *
016: * @author Steve Woodcock<br>
017: * @version 1.8
018: */
019: public interface INode {
020:
021: /**
022: * Gets the rightmost value for the node. This represents the largest value that this node (or its children)
023: * know about.
024: *
025: * @return The right value.
026: */
027: public abstract Comparable getRightValue();
028:
029: /**
030: * Sets the right value for the node.
031: *
032: * @param value - the value to use.
033: */
034: public abstract void setRightValue(Comparable value);
035:
036: public abstract boolean contains(Comparable value);
037:
038: /**
039: *
040: * Inserts the entry into the correct position in the node. The position is ordered by
041: * the Comparableness of its value. If the value in the entry already exists then a
042: * new Entry is not created, it will be added to a leaf node as a member of an existing entry.
043: * <p> If the value is larger than the current right value for the node then the right value is updated.<p>
044: * @param entry - the entry to set.
045: * @return - true if the new Entry required a new entry to be added to the list.
046: * @throws JoftiException
047: */
048: public abstract Object[] insertEntry(NodeEntry entry)
049: throws JoftiException;
050:
051: /**
052: * Removes an entry from the list of entries in the Node.<p> If the deleted node is the current right value, then the right
053: * value is updated with the next lowest value in the node.<p>
054: *
055: * @param entry - the entry to remove.
056: * @return if a matching entry was found to remove.
057: */
058: public abstract boolean deleteEntry(NodeEntry entry);
059:
060: /**
061: * Splits the current node into two new nodes. The two nodes have a 50/50 split of the entries distributed among them. The higher set
062: * are contained in the new node. In addition, the right values of each node are reset and the next node links are updated. The existing node's
063: * next node link is pointing the the new node and the new node is pointing to the previous right neighbour of the existing node.
064: * <p>
065: * @return the new Node containing half of the existing node's values.
066: */
067: public abstract Node splitNode(Object[] entries)
068: throws JoftiException;
069:
070: /**
071: * Retrieves the number of entries in the node.<br>
072: * @return entry number.
073: */
074: public abstract int getEntryNumber();
075:
076: /**
077: * Used to check if the node has exceeded or equaled the maximum number of allowed entries. This is used to
078: * decide whether to spilt the node as part of the insert node functions.
079: *
080: * @return If the number of entries is >= maximum allowed entries.
081: */
082: public abstract boolean isUnderFull();
083:
084: /**
085: * Checks if the node has any entries.<p>
086: *
087: * @return true if the node has no entries.
088: */
089: public abstract boolean isEmpty();
090:
091: /**
092: * Checks whether a node has been marked as deleted as a result of a remove. A node is only marked as deleted if it become empty.
093: * At some time later it will then be removed from the tree as other threads traverse it.<p>
094: * @return true if marked as deleted.
095: */
096: public abstract boolean isDeleted();
097:
098: /**
099: * Sets a node to be deleted. The node is <b>not</b> removed from the tree instead the other threads in the tree
100: * will remove a deleted node as part of their normal traversal process.<p>
101: * @param deleted
102: */
103: public abstract void setDeleted(boolean deleted);
104:
105: /**
106: * Retrieves the entries in the node as an array.
107: * @return the object array for the entries.
108: */
109: public abstract Object[] getEntries();
110:
111: /**
112: * Replaces the current entries with a new list of entries. The list passed in is shallow copied
113: * so changes to the originla list do not affect the list in the Node.
114: * <p>
115: * @param entries
116: */
117: public abstract void setEntries(Object[] entries);
118:
119: /**
120: * Returns the sibling righthand node for this node. This is part of the linking mechanism used to provide
121: * concurrency in the tree.<p>
122: *
123: * @return A nodelink containing the sibling node.
124: */
125: public abstract NodeLink getLinkNode();
126:
127: /**
128: * Sets a new right hand link for this node.<p>
129: *
130: * @param node - the nodelink to set as the right hand sibling.
131: */
132: public abstract void setLinkNode(NodeLink node);
133:
134: /**
135: * @return Returns the nodeLock.
136: */
137: public abstract ReadWriteLock getNodeLock();
138:
139: public abstract boolean isLeaf();
140: }
|