Class BooleanBigList.BooleanBlockNode
java.lang.Object
org.magicwerk.brownies.collections.primitive.BooleanBigList.BooleanBlockNode
- Enclosing class:
BooleanBigList
Implements an AVLNode storing a BooleanBlock.
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) BooleanBigList.BooleanBlock
The stored block(package private) int
How many levels of left/right are below this one.(package private) BooleanBigList.BooleanBlockNode
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) BooleanBigList.BooleanBlockNode
Pointer to parent node (null for root)(package private) int
Relative position of node relative to its parent, root holds absolute position.(package private) BooleanBigList.BooleanBlockNode
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
BooleanBlockNode
(BooleanBigList.BooleanBlockNode parent, int relPos, BooleanBigList.BooleanBlock block, BooleanBigList.BooleanBlockNode rightFollower, BooleanBigList.BooleanBlockNode leftFollower) Constructs a new node. -
Method Summary
Modifier and TypeMethodDescriptionprivate BooleanBigList.BooleanBlockNode
balance()
Balances according to the AVL algorithm.private BooleanBigList.BooleanBlockNode
private BooleanBigList.BooleanBlock
Gets the block stored by this node.private int
Returns the height of the node or -1 if the node is null.private BooleanBigList.BooleanBlockNode
Gets the left node, returning null if its a faedelung.private int
Gets the relative position.private BooleanBigList.BooleanBlockNode
Gets the right node, returning null if its a faedelung.private int
Returns the height difference right - leftprivate BooleanBigList.BooleanBlockNode
insert
(int index, BooleanBigList.BooleanBlock obj) Inserts new node holding specified block at the position index.private BooleanBigList.BooleanBlockNode
insertOnLeft
(int relIndex, BooleanBigList.BooleanBlock obj) Inserts new node holding specified block on the node's left side.private BooleanBigList.BooleanBlockNode
insertOnRight
(int relIndex, BooleanBigList.BooleanBlock obj) Inserts new node holding specified block on the node's right side.private BooleanBigList.BooleanBlockNode
max()
Gets the rightmost child of this node.private BooleanBigList.BooleanBlockNode
min()
Gets the leftmost child of this node.private BooleanBigList.BooleanBlockNode
next()
Gets the next node in the list after this one.private BooleanBigList.BooleanBlockNode
previous()
Gets the node in the list before this one.private void
Sets the height by calculation.private BooleanBigList.BooleanBlockNode
private BooleanBigList.BooleanBlockNode
removeMin
(int size) private BooleanBigList.BooleanBlockNode
Removes this node from the tree.private BooleanBigList.BooleanBlockNode
Rotate tree to the left using this node as center.private BooleanBigList.BooleanBlockNode
Rotate tree to the right using this node as center.private void
Sets block to store by this node.private void
setLeft
(BooleanBigList.BooleanBlockNode node, BooleanBigList.BooleanBlockNode previous) Sets the left field to the node, or the previous node if that is nullprivate int
setOffset
(BooleanBigList.BooleanBlockNode node, int newOffest) Sets the relative position.private void
Sets the right field to the node, or the next node if that is nulltoString()
Used for debugging.
-
Field Details
-
parent
Pointer to parent node (null for root) -
left
The left child node or the predecessor ifleftIsPrevious
. -
leftIsPrevious
boolean leftIsPreviousFlag indicating that left reference is not a subtree but the predecessor. -
right
The 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
The stored block
-
-
Constructor Details
-
BooleanBlockNode
private BooleanBlockNode(BooleanBigList.BooleanBlockNode parent, int relPos, BooleanBigList.BooleanBlock block, BooleanBigList.BooleanBlockNode rightFollower, BooleanBigList.BooleanBlockNode 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
-
getBooleanBlock
Gets the block stored by this node.- Returns:
- block stored by this node
-
setBooleanBlock
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
private BooleanBigList.BooleanBlockNode insertOnRight(int relIndex, BooleanBigList.BooleanBlock obj) 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
private void setLeft(BooleanBigList.BooleanBlockNode node, BooleanBigList.BooleanBlockNode 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
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.
-