org.neodatis.btree.impl
Class AbstractBTreeNode

java.lang.Object
  extended by 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

Field Summary
protected  IBTree btree
          The BTree owner of this node
protected  int degree
           
protected  java.lang.Comparable[] keys
           
protected  int maxNbChildren
           
protected  int maxNbKeys
           
protected  int nbChildren
           
protected  int nbKeys
           
protected  java.lang.Object[] values
           
 
Constructor Summary
AbstractBTreeNode()
           
AbstractBTreeNode(IBTree btree)
           
 
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
 
Methods inherited from interface org.neodatis.btree.IBTreeNode
deleteChildAt, getChildIdAt, getId, getValueAsObjectAt, setChildAt, setChildAt, setId, setNullChildAt
 

Field Detail

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

Constructor Detail

AbstractBTreeNode

public AbstractBTreeNode()

AbstractBTreeNode

public AbstractBTreeNode(IBTree btree)
Method Detail

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