Package org.magicwerk.brownies.collections.primitive

Class LongBigList.LongBlockNode

java.lang.Object

org.magicwerk.brownies.collections.primitive.LongBigList.LongBlockNode

Enclosing class:

LongBigList

static class LongBigList.LongBlockNode
extends java.lang.Object

Implements an AVLNode storing a LongBlock. 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) LongBigList.LongBlock	block	The stored block
(package private) int	height	How many levels of left/right are below this one.
(package private) LongBigList.LongBlockNode	left	The left child node or the predecessor if leftIsPrevious.
(package private) boolean	leftIsPrevious	Flag indicating that left reference is not a subtree but the predecessor.
(package private) LongBigList.LongBlockNode	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) LongBigList.LongBlockNode	right	The right child node or the successor if rightIsNext.
(package private) boolean	rightIsNext	Flag indicating that right reference is not a subtree but the successor.

Constructor Summary

Constructors

Modifier	Constructor	Description
private	LongBlockNode(LongBigList.LongBlockNode parent, int relPos, LongBigList.LongBlock block, LongBigList.LongBlockNode rightFollower, LongBigList.LongBlockNode leftFollower)	Constructs a new node.

Method Summary

Modifier and Type	Method	Description
private LongBigList.LongBlockNode	balance()	Balances according to the AVL algorithm.
private LongBigList.LongBlockNode	doRemoveSelf()
private int	getHeight(LongBigList.LongBlockNode node)	Returns the height of the node or -1 if the node is null.
private LongBigList.LongBlockNode	getLeftSubTree()	Gets the left node, returning null if its a faedelung.
private LongBigList.LongBlock	getLongBlock()	Gets the block stored by this node.
private int	getOffset(LongBigList.LongBlockNode node)	Gets the relative position.
private LongBigList.LongBlockNode	getRightSubTree()	Gets the right node, returning null if its a faedelung.
private int	heightRightMinusLeft()	Returns the height difference right - left
private LongBigList.LongBlockNode	insert(int index, LongBigList.LongBlock obj)	Inserts new node holding specified block at the position index.
private LongBigList.LongBlockNode	insertOnLeft(int relIndex, LongBigList.LongBlock obj)	Inserts new node holding specified block on the node's left side.
private LongBigList.LongBlockNode	insertOnRight(int relIndex, LongBigList.LongBlock obj)	Inserts new node holding specified block on the node's right side.
private LongBigList.LongBlockNode	max()	Gets the rightmost child of this node.
private LongBigList.LongBlockNode	min()	Gets the leftmost child of this node.
private LongBigList.LongBlockNode	next()	Gets the next node in the list after this one.
private LongBigList.LongBlockNode	previous()	Gets the node in the list before this one.
private void	recalcHeight()	Sets the height by calculation.
private LongBigList.LongBlockNode	removeMax()
private LongBigList.LongBlockNode	removeMin(int size)
private LongBigList.LongBlockNode	removeSelf()	Removes this node from the tree.
private LongBigList.LongBlockNode	rotateLeft()	Rotate tree to the left using this node as center.
private LongBigList.LongBlockNode	rotateRight()	Rotate tree to the right using this node as center.
private void	setLeft(LongBigList.LongBlockNode node, LongBigList.LongBlockNode previous)	Sets the left field to the node, or the previous node if that is null
private void	setLongBlock(LongBigList.LongBlock block)	Sets block to store by this node.
private int	setOffset(LongBigList.LongBlockNode node, int newOffest)	Sets the relative position.
private void	setRight(LongBigList.LongBlockNode node, LongBigList.LongBlockNode next)	Sets the right field to the node, or the next node if that is null
java.lang.String	toString()	Used for debugging.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

parent

LongBigList.LongBlockNode parent

Pointer to parent node (null for root)

left

LongBigList.LongBlockNode left

The left child node or the predecessor if leftIsPrevious.

leftIsPrevious

boolean leftIsPrevious

Flag indicating that left reference is not a subtree but the predecessor.

right

LongBigList.LongBlockNode right

The right child node or the successor if rightIsNext.

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

LongBigList.LongBlock block

The stored block

Constructor Detail

LongBlockNode

private LongBlockNode(LongBigList.LongBlockNode parent,
                      int relPos,
                      LongBigList.LongBlock block,
                      LongBigList.LongBlockNode rightFollower,
                      LongBigList.LongBlockNode 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 store

rightFollower - the node following this one

leftFollower - the node leading this one

Method Detail

getLongBlock

private LongBigList.LongBlock getLongBlock()

Gets the block stored by this node.

Returns:

block stored by this node

setLongBlock

private void setLongBlock(LongBigList.LongBlock block)

Sets block to store by this node.

Parameters:

block - the block to store

next

private LongBigList.LongBlockNode next()

Gets the next node in the list after this one.

Returns:

the next node

previous

private LongBigList.LongBlockNode previous()

Gets the node in the list before this one.

Returns:

the previous node

insert

private LongBigList.LongBlockNode insert(int index,
                                         LongBigList.LongBlock obj)

Inserts new node holding specified block at the position index.

Parameters:

index - index of the position relative to the position of the parent node

obj - object to store in the position

Returns:

this node or node replacing this node in the tree (if tree must be rebalanced)

insertOnLeft

private LongBigList.LongBlockNode insertOnLeft(int relIndex,
                                               LongBigList.LongBlock 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 node

obj - object to store in the position

Returns:

this node or node replacing this node in the tree (if tree must be rebalanced)

insertOnRight

private LongBigList.LongBlockNode insertOnRight(int relIndex,
                                                LongBigList.LongBlock 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 node

obj - object to store in the position

Returns:

this node or node replacing this node in the tree (if tree must be rebalanced)

getLeftSubTree

private LongBigList.LongBlockNode getLeftSubTree()

Gets the left node, returning null if its a faedelung.

getRightSubTree

private LongBigList.LongBlockNode getRightSubTree()

Gets the right node, returning null if its a faedelung.

max

private LongBigList.LongBlockNode max()

Gets the rightmost child of this node.

Returns:

the rightmost child (greatest index)

min

private LongBigList.LongBlockNode min()

Gets the leftmost child of this node.

Returns:

the leftmost child (smallest index)

removeMax

private LongBigList.LongBlockNode removeMax()

removeMin

private LongBigList.LongBlockNode removeMin(int size)

removeSelf

private LongBigList.LongBlockNode removeSelf()

Removes this node from the tree.

Returns:

the node that replaces this one in the parent (can be null)

doRemoveSelf

private LongBigList.LongBlockNode doRemoveSelf()

balance

private LongBigList.LongBlockNode balance()

Balances according to the AVL algorithm.

getOffset

private int getOffset(LongBigList.LongBlockNode node)

Gets the relative position.

setOffset

private int setOffset(LongBigList.LongBlockNode node,
                      int newOffest)

Sets the relative position.

recalcHeight

private void recalcHeight()

Sets the height by calculation.

getHeight

private int getHeight(LongBigList.LongBlockNode 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 LongBigList.LongBlockNode rotateLeft()

Rotate tree to the left using this node as center.

Returns:

node which will take the place of this node

rotateRight

private LongBigList.LongBlockNode 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(LongBigList.LongBlockNode node,
                     LongBigList.LongBlockNode previous)

Sets the left field to the node, or the previous node if that is null

Parameters:

node - the new left subtree node

previous - the previous node in the linked list

setRight

private void setRight(LongBigList.LongBlockNode node,
                      LongBigList.LongBlockNode next)

Sets the right field to the node, or the next node if that is null

Parameters:

node - the new right subtree node

next - the next node in the linked list

toString

public java.lang.String toString()

Used for debugging.

Overrides:

toString in class java.lang.Object