Package org.magicwerk.brownies.collections.primitive

Class CharBigList.CharBlockNode

java.lang.Object

org.magicwerk.brownies.collections.primitive.CharBigList.CharBlockNode

Enclosing class:

CharBigList

static class CharBigList.CharBlockNode
extends java.lang.Object

Implements an AVLNode storing a CharBlock. 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) CharBigList.CharBlock	block	The stored block
(package private) int	height	How many levels of left/right are below this one.
(package private) CharBigList.CharBlockNode	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) CharBigList.CharBlockNode	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) CharBigList.CharBlockNode	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	CharBlockNode(CharBigList.CharBlockNode parent, int relPos, CharBigList.CharBlock block, CharBigList.CharBlockNode rightFollower, CharBigList.CharBlockNode leftFollower)	Constructs a new node.

Method Summary

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

CharBigList.CharBlockNode parent

Pointer to parent node (null for root)

left

CharBigList.CharBlockNode 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

CharBigList.CharBlockNode 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

CharBigList.CharBlock block

The stored block

Constructor Detail

CharBlockNode

private CharBlockNode(CharBigList.CharBlockNode parent,
                      int relPos,
                      CharBigList.CharBlock block,
                      CharBigList.CharBlockNode rightFollower,
                      CharBigList.CharBlockNode 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

getCharBlock

private CharBigList.CharBlock getCharBlock()

Gets the block stored by this node.

Returns:

block stored by this node

setCharBlock

private void setCharBlock(CharBigList.CharBlock block)

Sets block to store by this node.

Parameters:

block - the block to store

next

private CharBigList.CharBlockNode next()

Gets the next node in the list after this one.

Returns:

the next node

previous

private CharBigList.CharBlockNode previous()

Gets the node in the list before this one.

Returns:

the previous node

insert

private CharBigList.CharBlockNode insert(int index,
                                         CharBigList.CharBlock 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 CharBigList.CharBlockNode insertOnLeft(int relIndex,
                                               CharBigList.CharBlock 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 CharBigList.CharBlockNode insertOnRight(int relIndex,
                                                CharBigList.CharBlock 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 CharBigList.CharBlockNode getLeftSubTree()

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

getRightSubTree

private CharBigList.CharBlockNode getRightSubTree()

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

max

private CharBigList.CharBlockNode max()

Gets the rightmost child of this node.

Returns:

the rightmost child (greatest index)

min

private CharBigList.CharBlockNode min()

Gets the leftmost child of this node.

Returns:

the leftmost child (smallest index)

removeMax

private CharBigList.CharBlockNode removeMax()

removeMin

private CharBigList.CharBlockNode removeMin(int size)

removeSelf

private CharBigList.CharBlockNode removeSelf()

Removes this node from the tree.

Returns:

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

doRemoveSelf

private CharBigList.CharBlockNode doRemoveSelf()

balance

private CharBigList.CharBlockNode balance()

Balances according to the AVL algorithm.

getOffset

private int getOffset(CharBigList.CharBlockNode node)

Gets the relative position.

setOffset

private int setOffset(CharBigList.CharBlockNode node,
                      int newOffest)

Sets the relative position.

recalcHeight

private void recalcHeight()

Sets the height by calculation.

getHeight

private int getHeight(CharBigList.CharBlockNode 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 CharBigList.CharBlockNode rotateLeft()

Rotate tree to the left using this node as center.

Returns:

node which will take the place of this node

rotateRight

private CharBigList.CharBlockNode 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(CharBigList.CharBlockNode node,
                     CharBigList.CharBlockNode 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(CharBigList.CharBlockNode node,
                      CharBigList.CharBlockNode 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