Package org.magicwerk.brownies.collections.primitive

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 if leftIsPrevious.
(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 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	DoubleBlockNode(DoubleBigList.DoubleBlockNode parent, int relPos, DoubleBigList.DoubleBlock block, DoubleBigList.DoubleBlockNode rightFollower, DoubleBigList.DoubleBlockNode leftFollower)	Constructs a new node.

Method Summary

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 - left
private 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 null
private 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 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

DoubleBigList.DoubleBlockNode parent

Pointer to parent node (null for root)

left

DoubleBigList.DoubleBlockNode 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

DoubleBigList.DoubleBlockNode 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

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 store

rightFollower - the node following this one

leftFollower - 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 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 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 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 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 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 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 node

previous - 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 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