Class DoubleBigList.DoubleBlockNode
- java.lang.Object
-
- org.magicwerk.brownies.collections.primitive.DoubleBigList.DoubleBlockNode
-
- Enclosing class:
- DoubleBigList
static class DoubleBigList.DoubleBlockNode extends java.lang.Object
Implements an AVLNode storing a DoubleBlock. 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) DoubleBigList.DoubleBlock
block
The stored block(package private) int
height
How many levels of left/right are below this one.(package private) DoubleBigList.DoubleBlockNode
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) DoubleBigList.DoubleBlockNode
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) DoubleBigList.DoubleBlockNode
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
DoubleBlockNode(DoubleBigList.DoubleBlockNode parent, int relPos, DoubleBigList.DoubleBlock block, DoubleBigList.DoubleBlockNode rightFollower, DoubleBigList.DoubleBlockNode leftFollower)
Constructs a new node.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private DoubleBigList.DoubleBlockNode
balance()
Balances according to the AVL algorithm.private DoubleBigList.DoubleBlockNode
doRemoveSelf()
private DoubleBigList.DoubleBlock
getDoubleBlock()
Gets the block stored by this node.private int
getHeight(DoubleBigList.DoubleBlockNode node)
Returns the height of the node or -1 if the node is null.private DoubleBigList.DoubleBlockNode
getLeftSubTree()
Gets the left node, returning null if its a faedelung.private int
getOffset(DoubleBigList.DoubleBlockNode node)
Gets the relative position.private DoubleBigList.DoubleBlockNode
getRightSubTree()
Gets the right node, returning null if its a faedelung.private int
heightRightMinusLeft()
Returns the height difference right - leftprivate DoubleBigList.DoubleBlockNode
insert(int index, DoubleBigList.DoubleBlock obj)
Inserts new node holding specified block at the position index.private DoubleBigList.DoubleBlockNode
insertOnLeft(int relIndex, DoubleBigList.DoubleBlock obj)
Inserts new node holding specified block on the node's left side.private DoubleBigList.DoubleBlockNode
insertOnRight(int relIndex, DoubleBigList.DoubleBlock obj)
Inserts new node holding specified block on the node's right side.private DoubleBigList.DoubleBlockNode
max()
Gets the rightmost child of this node.private DoubleBigList.DoubleBlockNode
min()
Gets the leftmost child of this node.private DoubleBigList.DoubleBlockNode
next()
Gets the next node in the list after this one.private DoubleBigList.DoubleBlockNode
previous()
Gets the node in the list before this one.private void
recalcHeight()
Sets the height by calculation.private DoubleBigList.DoubleBlockNode
removeMax()
private DoubleBigList.DoubleBlockNode
removeMin(int size)
private DoubleBigList.DoubleBlockNode
removeSelf()
Removes this node from the tree.private DoubleBigList.DoubleBlockNode
rotateLeft()
Rotate tree to the left using this node as center.private DoubleBigList.DoubleBlockNode
rotateRight()
Rotate tree to the right using this node as center.private void
setDoubleBlock(DoubleBigList.DoubleBlock block)
Sets block to store by this node.private void
setLeft(DoubleBigList.DoubleBlockNode node, DoubleBigList.DoubleBlockNode previous)
Sets the left field to the node, or the previous node if that is nullprivate int
setOffset(DoubleBigList.DoubleBlockNode node, int newOffest)
Sets the relative position.private void
setRight(DoubleBigList.DoubleBlockNode node, DoubleBigList.DoubleBlockNode 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
DoubleBigList.DoubleBlockNode parent
Pointer to parent node (null for root)
-
left
DoubleBigList.DoubleBlockNode 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
DoubleBigList.DoubleBlockNode 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
DoubleBigList.DoubleBlock block
The stored block
-
-
Constructor Detail
-
DoubleBlockNode
private DoubleBlockNode(DoubleBigList.DoubleBlockNode parent, int relPos, DoubleBigList.DoubleBlock block, DoubleBigList.DoubleBlockNode rightFollower, DoubleBigList.DoubleBlockNode 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
-
getDoubleBlock
private DoubleBigList.DoubleBlock getDoubleBlock()
Gets the block stored by this node.- Returns:
- block stored by this node
-
setDoubleBlock
private void setDoubleBlock(DoubleBigList.DoubleBlock block)
Sets block to store by this node.- Parameters:
block
- the block to store
-
next
private DoubleBigList.DoubleBlockNode next()
Gets the next node in the list after this one.- Returns:
- the next node
-
previous
private DoubleBigList.DoubleBlockNode previous()
Gets the node in the list before this one.- Returns:
- the previous node
-
insert
private DoubleBigList.DoubleBlockNode insert(int index, DoubleBigList.DoubleBlock 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 DoubleBigList.DoubleBlockNode insertOnLeft(int relIndex, DoubleBigList.DoubleBlock 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 DoubleBigList.DoubleBlockNode insertOnRight(int relIndex, DoubleBigList.DoubleBlock 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 DoubleBigList.DoubleBlockNode getLeftSubTree()
Gets the left node, returning null if its a faedelung.
-
getRightSubTree
private DoubleBigList.DoubleBlockNode getRightSubTree()
Gets the right node, returning null if its a faedelung.
-
max
private DoubleBigList.DoubleBlockNode max()
Gets the rightmost child of this node.- Returns:
- the rightmost child (greatest index)
-
min
private DoubleBigList.DoubleBlockNode min()
Gets the leftmost child of this node.- Returns:
- the leftmost child (smallest index)
-
removeMax
private DoubleBigList.DoubleBlockNode removeMax()
-
removeMin
private DoubleBigList.DoubleBlockNode removeMin(int size)
-
removeSelf
private DoubleBigList.DoubleBlockNode removeSelf()
Removes this node from the tree.- Returns:
- the node that replaces this one in the parent (can be null)
-
doRemoveSelf
private DoubleBigList.DoubleBlockNode doRemoveSelf()
-
balance
private DoubleBigList.DoubleBlockNode balance()
Balances according to the AVL algorithm.
-
getOffset
private int getOffset(DoubleBigList.DoubleBlockNode node)
Gets the relative position.
-
setOffset
private int setOffset(DoubleBigList.DoubleBlockNode node, int newOffest)
Sets the relative position.
-
recalcHeight
private void recalcHeight()
Sets the height by calculation.
-
getHeight
private int getHeight(DoubleBigList.DoubleBlockNode 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 DoubleBigList.DoubleBlockNode rotateLeft()
Rotate tree to the left using this node as center.- Returns:
- node which will take the place of this node
-
rotateRight
private DoubleBigList.DoubleBlockNode 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(DoubleBigList.DoubleBlockNode node, DoubleBigList.DoubleBlockNode 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(DoubleBigList.DoubleBlockNode node, DoubleBigList.DoubleBlockNode 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
-
-