Class BigList.BlockNode<E>
java.lang.Object
org.magicwerk.brownies.collections.BigList.BlockNode<E>
Implements an AVLNode storing a Block.
The nodes don't know the index of the object they are holding. They do know however their
position relative to their parent node. This allows to calculate the index of a node while traversing the tree.
There is a faedelung flag for both the left and right child
to indicate if they are a child (false) or a link as in linked list (true).
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) BigList.Block
<E> The stored block(package private) int
How many levels of left/right are below this one.(package private) BigList.BlockNode
<E> The left child node or the predecessor ifleftIsPrevious
.(package private) boolean
Flag indicating that left reference is not a subtree but the predecessor.(package private) BigList.BlockNode
<E> Pointer to parent node (null for root)(package private) int
Relative position of node relative to its parent, root holds absolute position.(package private) BigList.BlockNode
<E> The right child node or the successor ifrightIsNext
.(package private) boolean
Flag indicating that right reference is not a subtree but the successor. -
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
BlockNode
(BigList.BlockNode<E> parent, int relPos, BigList.Block<E> block, BigList.BlockNode<E> rightFollower, BigList.BlockNode<E> leftFollower) Constructs a new node. -
Method Summary
Modifier and TypeMethodDescriptionprivate BigList.BlockNode
<E> balance()
Balances according to the AVL algorithm.private BigList.BlockNode
<E> private BigList.Block
<E> getBlock()
Gets the block stored by this node.private int
getHeight
(BigList.BlockNode<E> node) Returns the height of the node or -1 if the node is null.private BigList.BlockNode
<E> Gets the left node, returning null if its a faedelung.private int
getOffset
(BigList.BlockNode<E> node) Gets the relative position.private BigList.BlockNode
<E> Gets the right node, returning null if its a faedelung.private int
Returns the height difference right - leftprivate BigList.BlockNode
<E> insert
(int index, BigList.Block<E> obj) Inserts new node holding specified block at the position index.private BigList.BlockNode
<E> insertOnLeft
(int relIndex, BigList.Block<E> obj) Inserts new node holding specified block on the node's left side.private BigList.BlockNode
<E> insertOnRight
(int relIndex, BigList.Block<E> obj) Inserts new node holding specified block on the node's right side.private BigList.BlockNode
<E> max()
Gets the rightmost child of this node.private BigList.BlockNode
<E> min()
Gets the leftmost child of this node.private BigList.BlockNode
<E> next()
Gets the next node in the list after this one.private BigList.BlockNode
<E> previous()
Gets the node in the list before this one.private void
Sets the height by calculation.private BigList.BlockNode
<E> private BigList.BlockNode
<E> removeMin
(int size) private BigList.BlockNode
<E> Removes this node from the tree.private BigList.BlockNode
<E> Rotate tree to the left using this node as center.private BigList.BlockNode
<E> Rotate tree to the right using this node as center.private void
setBlock
(BigList.Block<E> block) Sets block to store by this node.private void
setLeft
(BigList.BlockNode<E> node, BigList.BlockNode<E> previous) Sets the left field to the node, or the previous node if that is nullprivate int
setOffset
(BigList.BlockNode<E> node, int newOffest) Sets the relative position.private void
setRight
(BigList.BlockNode<E> node, BigList.BlockNode<E> next) Sets the right field to the node, or the next node if that is nulltoString()
Used for debugging.
-
Field Details
-
parent
BigList.BlockNode<E> parentPointer to parent node (null for root) -
left
BigList.BlockNode<E> leftThe left child node or the predecessor ifleftIsPrevious
. -
leftIsPrevious
boolean leftIsPreviousFlag indicating that left reference is not a subtree but the predecessor. -
right
BigList.BlockNode<E> rightThe right child node or the successor ifrightIsNext
. -
rightIsNext
boolean rightIsNextFlag indicating that right reference is not a subtree but the successor. -
height
int heightHow many levels of left/right are below this one. -
relPos
int relPosRelative position of node relative to its parent, root holds absolute position. -
block
BigList.Block<E> blockThe stored block
-
-
Constructor Details
-
BlockNode
private BlockNode(BigList.BlockNode<E> parent, int relPos, BigList.Block<E> block, BigList.BlockNode<E> rightFollower, BigList.BlockNode<E> leftFollower) Constructs a new node.- Parameters:
parent
- parent node (null for root)block
- the block to storerightFollower
- the node following this oneleftFollower
- the node leading this onerelativePosition
- the relative position of the node (absolute position for root)
-
-
Method Details
-
getBlock
Gets the block stored by this node.- Returns:
- block stored by this node
-
setBlock
Sets block to store by this node.- Parameters:
block
- the block to store
-
next
Gets the next node in the list after this one.- Returns:
- the next node
-
previous
Gets the node in the list before this one.- Returns:
- the previous node
-
insert
Inserts new node holding specified block at the position index.- Parameters:
index
- index of the position relative to the position of the parent nodeobj
- object to store in the position- Returns:
- this node or node replacing this node in the tree (if tree must be rebalanced)
-
insertOnLeft
Inserts new node holding specified block on the node's left side.- Parameters:
obj
- object to store in the positionindex
- index of the position relative to the position of the parent node- Returns:
- this node or node replacing this node in the tree (if tree must be rebalanced)
-
insertOnRight
Inserts new node holding specified block on the node's right side.- Parameters:
obj
- object to store in the positionindex
- index of the position relative to the position of the parent node- Returns:
- this node or node replacing this node in the tree (if tree must be rebalanced)
-
getLeftSubTree
Gets the left node, returning null if its a faedelung. -
getRightSubTree
Gets the right node, returning null if its a faedelung. -
max
Gets the rightmost child of this node.- Returns:
- the rightmost child (greatest index)
-
min
Gets the leftmost child of this node.- Returns:
- the leftmost child (smallest index)
-
removeMax
-
removeMin
-
removeSelf
Removes this node from the tree.- Returns:
- the node that replaces this one in the parent (can be null)
-
doRemoveSelf
-
balance
Balances according to the AVL algorithm. -
getOffset
Gets the relative position. -
setOffset
Sets the relative position. -
recalcHeight
private void recalcHeight()Sets the height by calculation. -
getHeight
Returns the height of the node or -1 if the node is null. -
heightRightMinusLeft
private int heightRightMinusLeft()Returns the height difference right - left -
rotateLeft
Rotate tree to the left using this node as center.- Returns:
- node which will take the place of this node
-
rotateRight
Rotate tree to the right using this node as center.- Returns:
- node which will take the place of this node
-
setLeft
Sets the left field to the node, or the previous node if that is null- Parameters:
node
- the new left subtree nodeprevious
- the previous node in the linked list
-
setRight
Sets the right field to the node, or the next node if that is null- Parameters:
node
- the new right subtree nodenext
- the next node in the linked list
-
toString
Used for debugging.
-