Class BigList.BlockNode<E>
- java.lang.Object
-
- org.magicwerk.brownies.collections.BigList.BlockNode<E>
-
static class BigList.BlockNode<E> extends java.lang.Object
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
Fields Modifier and Type Field Description (package private) BigList.Block<E>
block
The stored block(package private) int
height
How many levels of left/right are below this one.(package private) BigList.BlockNode<E>
left
The left child node or the predecessor ifleftIsPrevious
.(package private) boolean
leftIsPrevious
Flag indicating that left reference is not a subtree but the predecessor.(package private) BigList.BlockNode<E>
parent
Pointer to parent node (null for root)(package private) int
relPos
Relative position of node relative to its parent, root holds absolute position.(package private) BigList.BlockNode<E>
right
The right child node or the successor ifrightIsNext
.(package private) boolean
rightIsNext
Flag indicating that right reference is not a subtree but the successor.
-
Constructor Summary
Constructors Modifier Constructor Description private
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
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private BigList.BlockNode<E>
balance()
Balances according to the AVL algorithm.private BigList.BlockNode<E>
doRemoveSelf()
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>
getLeftSubTree()
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>
getRightSubTree()
Gets the right node, returning null if its a faedelung.private int
heightRightMinusLeft()
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
recalcHeight()
Sets the height by calculation.private BigList.BlockNode<E>
removeMax()
private BigList.BlockNode<E>
removeMin(int size)
private BigList.BlockNode<E>
removeSelf()
Removes this node from the tree.private BigList.BlockNode<E>
rotateLeft()
Rotate tree to the left using this node as center.private BigList.BlockNode<E>
rotateRight()
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 nulljava.lang.String
toString()
Used for debugging.
-
-
-
Field Detail
-
parent
BigList.BlockNode<E> parent
Pointer to parent node (null for root)
-
left
BigList.BlockNode<E> left
The left child node or the predecessor ifleftIsPrevious
.
-
leftIsPrevious
boolean leftIsPrevious
Flag indicating that left reference is not a subtree but the predecessor.
-
right
BigList.BlockNode<E> right
The right child node or the successor ifrightIsNext
.
-
rightIsNext
boolean rightIsNext
Flag indicating that right reference is not a subtree but the successor.
-
height
int height
How many levels of left/right are below this one.
-
relPos
int relPos
Relative position of node relative to its parent, root holds absolute position.
-
block
BigList.Block<E> block
The stored block
-
-
Constructor Detail
-
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)relativePosition
- the relative position of the node (absolute position for root)block
- the block to storerightFollower
- the node following this oneleftFollower
- the node leading this one
-
-
Method Detail
-
getBlock
private BigList.Block<E> getBlock()
Gets the block stored by this node.- Returns:
- block stored by this node
-
setBlock
private void setBlock(BigList.Block<E> block)
Sets block to store by this node.- Parameters:
block
- the block to store
-
next
private BigList.BlockNode<E> next()
Gets the next node in the list after this one.- Returns:
- the next node
-
previous
private BigList.BlockNode<E> previous()
Gets the node in the list before this one.- Returns:
- the previous node
-
insert
private BigList.BlockNode<E> insert(int index, BigList.Block<E> obj)
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
private BigList.BlockNode<E> insertOnLeft(int relIndex, BigList.Block<E> obj)
Inserts new node holding specified block on the node's left side.- 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)
-
insertOnRight
private BigList.BlockNode<E> insertOnRight(int relIndex, BigList.Block<E> obj)
Inserts new node holding specified block on the node's right side.- 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)
-
getLeftSubTree
private BigList.BlockNode<E> getLeftSubTree()
Gets the left node, returning null if its a faedelung.
-
getRightSubTree
private BigList.BlockNode<E> getRightSubTree()
Gets the right node, returning null if its a faedelung.
-
max
private BigList.BlockNode<E> max()
Gets the rightmost child of this node.- Returns:
- the rightmost child (greatest index)
-
min
private BigList.BlockNode<E> min()
Gets the leftmost child of this node.- Returns:
- the leftmost child (smallest index)
-
removeMax
private BigList.BlockNode<E> removeMax()
-
removeMin
private BigList.BlockNode<E> removeMin(int size)
-
removeSelf
private BigList.BlockNode<E> removeSelf()
Removes this node from the tree.- Returns:
- the node that replaces this one in the parent (can be null)
-
doRemoveSelf
private BigList.BlockNode<E> doRemoveSelf()
-
balance
private BigList.BlockNode<E> balance()
Balances according to the AVL algorithm.
-
getOffset
private int getOffset(BigList.BlockNode<E> node)
Gets the relative position.
-
setOffset
private int setOffset(BigList.BlockNode<E> node, int newOffest)
Sets the relative position.
-
recalcHeight
private void recalcHeight()
Sets the height by calculation.
-
getHeight
private int getHeight(BigList.BlockNode<E> node)
Returns the height of the node or -1 if the node is null.
-
heightRightMinusLeft
private int heightRightMinusLeft()
Returns the height difference right - left
-
rotateLeft
private BigList.BlockNode<E> rotateLeft()
Rotate tree to the left using this node as center.- Returns:
- node which will take the place of this node
-
rotateRight
private BigList.BlockNode<E> rotateRight()
Rotate tree to the right using this node as center.- Returns:
- node which will take the place of this node
-
setLeft
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 null- Parameters:
node
- the new left subtree nodeprevious
- the previous node in the linked list
-
setRight
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 null- Parameters:
node
- the new right subtree nodenext
- the next node in the linked list
-
toString
public java.lang.String toString()
Used for debugging.- Overrides:
toString
in classjava.lang.Object
-
-