org.neodatis.btree.impl
Class AbstractBTreeNode
java.lang.Object
org.neodatis.btree.impl.AbstractBTreeNode
- All Implemented Interfaces:
- java.io.Serializable, IBTreeNode
- Direct Known Subclasses:
- BTreeNodeMultipleValuesPerKey, BTreeNodeSingleValuePerKey
public abstract class AbstractBTreeNode
- extends java.lang.Object
- implements IBTreeNode
- See Also:
- Serialized Form
Method Summary |
void |
clear()
|
java.lang.Object |
deleteKeyAndValueAt(int keyIndex,
boolean shiftChildren)
|
java.lang.Object |
deleteKeyForLeafNode(IKeyAndValue keyAndValue)
|
IBTreeNode |
extractRightPart()
Creates a new node with the right part of this node. |
IBTree |
getBTree()
|
abstract IBTreeNode |
getChildAt(int index,
boolean throwExceptionIfNotExist)
|
int |
getDegree()
|
IKeyAndValue |
getKeyAndValueAt(int index)
|
java.lang.Comparable |
getKeyAt(int index)
|
IBTreeNode |
getLastChild()
|
IKeyAndValue |
getLastKeyAndValue()
|
IBTreeNode |
getLastPositionChild()
|
int |
getMaxNbChildren()
|
IKeyAndValue |
getMedian()
|
int |
getNbChildren()
|
int |
getNbKeys()
|
abstract IBTreeNode |
getParent()
|
abstract java.lang.Object |
getParentId()
|
int |
getPositionOfKey(java.lang.Comparable key)
Returns the position of the key. |
abstract boolean |
hasParent()
|
void |
incrementNbChildren()
|
void |
incrementNbKeys()
|
protected abstract void |
init()
|
abstract void |
insertKeyAndValue(java.lang.Comparable key,
java.lang.Object value)
|
boolean |
isFull()
|
boolean |
isLeaf()
|
protected void |
leftShiftFrom(int position,
boolean shiftChildren)
|
void |
mergeWith(IBTreeNode node)
Can only merge node without intersection => the greater key of this must
be smaller than the smallest key of the node |
abstract void |
moveChildFromTo(int sourceIndex,
int destinationIndex,
boolean throwExceptionIfDoesNotExist)
|
void |
removeKeyAndValueAt(int index)
|
protected void |
rightShiftFrom(int position,
boolean shiftChildren)
|
void |
setBTree(IBTree btree)
|
void |
setKeyAndValueAt(java.lang.Comparable key,
java.lang.Object value,
int index)
|
void |
setKeyAndValueAt(java.lang.Comparable key,
java.lang.Object value,
int index,
boolean shiftIfAlreadyExist,
boolean incrementNbKeys)
|
void |
setKeyAndValueAt(IKeyAndValue keyAndValue,
int index)
|
void |
setKeyAndValueAt(IKeyAndValue keyAndValue,
int index,
boolean shiftIfAlreadyExist,
boolean incrementNbKeys)
|
void |
setNbChildren(int nbChildren)
|
void |
setNbKeys(int nbKeys)
|
abstract void |
setParent(IBTreeNode node)
|
java.lang.String |
toString()
|
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
degree
protected int degree
keys
protected java.lang.Comparable[] keys
values
protected java.lang.Object[] values
nbKeys
protected int nbKeys
nbChildren
protected int nbChildren
maxNbKeys
protected int maxNbKeys
maxNbChildren
protected int maxNbChildren
btree
protected transient IBTree btree
- The BTree owner of this node
AbstractBTreeNode
public AbstractBTreeNode()
AbstractBTreeNode
public AbstractBTreeNode(IBTree btree)
insertKeyAndValue
public abstract void insertKeyAndValue(java.lang.Comparable key,
java.lang.Object value)
- Specified by:
insertKeyAndValue
in interface IBTreeNode
init
protected abstract void init()
getChildAt
public abstract IBTreeNode getChildAt(int index,
boolean throwExceptionIfNotExist)
- Specified by:
getChildAt
in interface IBTreeNode
getParent
public abstract IBTreeNode getParent()
- Specified by:
getParent
in interface IBTreeNode
getParentId
public abstract java.lang.Object getParentId()
- Specified by:
getParentId
in interface IBTreeNode
setParent
public abstract void setParent(IBTreeNode node)
- Specified by:
setParent
in interface IBTreeNode
hasParent
public abstract boolean hasParent()
- Specified by:
hasParent
in interface IBTreeNode
moveChildFromTo
public abstract void moveChildFromTo(int sourceIndex,
int destinationIndex,
boolean throwExceptionIfDoesNotExist)
- Specified by:
moveChildFromTo
in interface IBTreeNode
extractRightPart
public IBTreeNode extractRightPart()
- Creates a new node with the right part of this node. This should only be
called on a full node
- Specified by:
extractRightPart
in interface IBTreeNode
getKeyAndValueAt
public IKeyAndValue getKeyAndValueAt(int index)
- Specified by:
getKeyAndValueAt
in interface IBTreeNode
getLastKeyAndValue
public IKeyAndValue getLastKeyAndValue()
- Specified by:
getLastKeyAndValue
in interface IBTreeNode
getKeyAt
public java.lang.Comparable getKeyAt(int index)
- Specified by:
getKeyAt
in interface IBTreeNode
getMedian
public IKeyAndValue getMedian()
- Specified by:
getMedian
in interface IBTreeNode
getPositionOfKey
public int getPositionOfKey(java.lang.Comparable key)
- Returns the position of the key. If the key does not exist in node,
returns the position where this key should be,multiplied by -1
for example for node of degree 3 : [1 89 452 789 - ],
calling getPositionOfKey(89) returns 2 (starts with 1)
calling getPositionOfKey(99) returns -2 (starts with 1),because the position should be done, but it does not exist so multiply by -1
this is used to know the child we should descend to!in this case the getChild(2).
- Specified by:
getPositionOfKey
in interface IBTreeNode
- Parameters:
key
-
- Returns:
- The position of the key,as a negative number if key does not
exist, warning, the position starts with 1and not 0!
incrementNbChildren
public void incrementNbChildren()
- Specified by:
incrementNbChildren
in interface IBTreeNode
incrementNbKeys
public void incrementNbKeys()
- Specified by:
incrementNbKeys
in interface IBTreeNode
rightShiftFrom
protected void rightShiftFrom(int position,
boolean shiftChildren)
leftShiftFrom
protected void leftShiftFrom(int position,
boolean shiftChildren)
setKeyAndValueAt
public void setKeyAndValueAt(java.lang.Comparable key,
java.lang.Object value,
int index)
- Specified by:
setKeyAndValueAt
in interface IBTreeNode
setKeyAndValueAt
public void setKeyAndValueAt(IKeyAndValue keyAndValue,
int index)
- Specified by:
setKeyAndValueAt
in interface IBTreeNode
setKeyAndValueAt
public void setKeyAndValueAt(java.lang.Comparable key,
java.lang.Object value,
int index,
boolean shiftIfAlreadyExist,
boolean incrementNbKeys)
- Specified by:
setKeyAndValueAt
in interface IBTreeNode
setKeyAndValueAt
public void setKeyAndValueAt(IKeyAndValue keyAndValue,
int index,
boolean shiftIfAlreadyExist,
boolean incrementNbKeys)
- Specified by:
setKeyAndValueAt
in interface IBTreeNode
isFull
public boolean isFull()
- Specified by:
isFull
in interface IBTreeNode
isLeaf
public boolean isLeaf()
- Specified by:
isLeaf
in interface IBTreeNode
mergeWith
public void mergeWith(IBTreeNode node)
- Can only merge node without intersection => the greater key of this must
be smaller than the smallest key of the node
- Specified by:
mergeWith
in interface IBTreeNode
removeKeyAndValueAt
public void removeKeyAndValueAt(int index)
- Specified by:
removeKeyAndValueAt
in interface IBTreeNode
getLastChild
public IBTreeNode getLastChild()
- Specified by:
getLastChild
in interface IBTreeNode
getLastPositionChild
public IBTreeNode getLastPositionChild()
- Specified by:
getLastPositionChild
in interface IBTreeNode
getNbKeys
public int getNbKeys()
- Specified by:
getNbKeys
in interface IBTreeNode
setNbChildren
public void setNbChildren(int nbChildren)
- Specified by:
setNbChildren
in interface IBTreeNode
setNbKeys
public void setNbKeys(int nbKeys)
- Specified by:
setNbKeys
in interface IBTreeNode
getDegree
public int getDegree()
- Specified by:
getDegree
in interface IBTreeNode
getNbChildren
public int getNbChildren()
- Specified by:
getNbChildren
in interface IBTreeNode
deleteKeyForLeafNode
public java.lang.Object deleteKeyForLeafNode(IKeyAndValue keyAndValue)
- Specified by:
deleteKeyForLeafNode
in interface IBTreeNode
deleteKeyAndValueAt
public java.lang.Object deleteKeyAndValueAt(int keyIndex,
boolean shiftChildren)
- Specified by:
deleteKeyAndValueAt
in interface IBTreeNode
toString
public java.lang.String toString()
- Overrides:
toString
in class java.lang.Object
getMaxNbChildren
public int getMaxNbChildren()
- Specified by:
getMaxNbChildren
in interface IBTreeNode
setBTree
public void setBTree(IBTree btree)
- Specified by:
setBTree
in interface IBTreeNode
getBTree
public IBTree getBTree()
- Specified by:
getBTree
in interface IBTreeNode
clear
public void clear()
- Specified by:
clear
in interface IBTreeNode