Package org.magicwerk.brownies.collections.primitive

Class BooleanBigList.BooleanBlockNode

java.lang.Object

org.magicwerk.brownies.collections.primitive.BooleanBigList.BooleanBlockNode

Enclosing class:

BooleanBigList

static class BooleanBigList.BooleanBlockNode
extends java.lang.Object

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

Fields

Modifier and Type	Field	Description
(package private) BooleanBigList.BooleanBlock	block	The stored block
(package private) int	height	How many levels of left/right are below this one.
(package private) BooleanBigList.BooleanBlockNode	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) BooleanBigList.BooleanBlockNode	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) BooleanBigList.BooleanBlockNode	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	BooleanBlockNode(BooleanBigList.BooleanBlockNode parent, int relPos, BooleanBigList.BooleanBlock block, BooleanBigList.BooleanBlockNode rightFollower, BooleanBigList.BooleanBlockNode leftFollower)	Constructs a new node.

Method Summary

Modifier and Type	Method	Description
private BooleanBigList.BooleanBlockNode	balance()	Balances according to the AVL algorithm.
private BooleanBigList.BooleanBlockNode	doRemoveSelf()
private BooleanBigList.BooleanBlock	getBooleanBlock()	Gets the block stored by this node.
private int	getHeight(BooleanBigList.BooleanBlockNode node)	Returns the height of the node or -1 if the node is null.
private BooleanBigList.BooleanBlockNode	getLeftSubTree()	Gets the left node, returning null if its a faedelung.
private int	getOffset(BooleanBigList.BooleanBlockNode node)	Gets the relative position.
private BooleanBigList.BooleanBlockNode	getRightSubTree()	Gets the right node, returning null if its a faedelung.
private int	heightRightMinusLeft()	Returns the height difference right - left
private 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	recalcHeight()	Sets the height by calculation.
private BooleanBigList.BooleanBlockNode	removeMax()
private BooleanBigList.BooleanBlockNode	removeMin(int size)
private BooleanBigList.BooleanBlockNode	removeSelf()	Removes this node from the tree.
private BooleanBigList.BooleanBlockNode	rotateLeft()	Rotate tree to the left using this node as center.
private BooleanBigList.BooleanBlockNode	rotateRight()	Rotate tree to the right using this node as center.
private void	setBooleanBlock(BooleanBigList.BooleanBlock block)	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 null
private int	setOffset(BooleanBigList.BooleanBlockNode node, int newOffest)	Sets the relative position.
private void	setRight(BooleanBigList.BooleanBlockNode node, BooleanBigList.BooleanBlockNode 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

BooleanBigList.BooleanBlockNode parent

Pointer to parent node (null for root)

left

BooleanBigList.BooleanBlockNode 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

BooleanBigList.BooleanBlockNode 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

BooleanBigList.BooleanBlock block

The stored block

Constructor Detail

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)

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

getBooleanBlock

private BooleanBigList.BooleanBlock getBooleanBlock()

Gets the block stored by this node.

Returns:

block stored by this node

setBooleanBlock

private void setBooleanBlock(BooleanBigList.BooleanBlock block)

Sets block to store by this node.

Parameters:

block - the block to store

next

private BooleanBigList.BooleanBlockNode next()

Gets the next node in the list after this one.

Returns:

the next node

previous

private BooleanBigList.BooleanBlockNode previous()

Gets the node in the list before this one.

Returns:

the previous node

insert

private BooleanBigList.BooleanBlockNode insert(int index,
                                               BooleanBigList.BooleanBlock 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 BooleanBigList.BooleanBlockNode insertOnLeft(int relIndex,
                                                     BooleanBigList.BooleanBlock 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 BooleanBigList.BooleanBlockNode insertOnRight(int relIndex,
                                                      BooleanBigList.BooleanBlock 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 BooleanBigList.BooleanBlockNode getLeftSubTree()

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

getRightSubTree

private BooleanBigList.BooleanBlockNode getRightSubTree()

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

max

private BooleanBigList.BooleanBlockNode max()

Gets the rightmost child of this node.

Returns:

the rightmost child (greatest index)

min

private BooleanBigList.BooleanBlockNode min()

Gets the leftmost child of this node.

Returns:

the leftmost child (smallest index)

removeMax

private BooleanBigList.BooleanBlockNode removeMax()

removeMin

private BooleanBigList.BooleanBlockNode removeMin(int size)

removeSelf

private BooleanBigList.BooleanBlockNode removeSelf()

Removes this node from the tree.

Returns:

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

doRemoveSelf

private BooleanBigList.BooleanBlockNode doRemoveSelf()

balance

private BooleanBigList.BooleanBlockNode balance()

Balances according to the AVL algorithm.

getOffset

private int getOffset(BooleanBigList.BooleanBlockNode node)

Gets the relative position.

setOffset

private int setOffset(BooleanBigList.BooleanBlockNode node,
                      int newOffest)

Sets the relative position.

recalcHeight

private void recalcHeight()

Sets the height by calculation.

getHeight

private int getHeight(BooleanBigList.BooleanBlockNode 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 BooleanBigList.BooleanBlockNode rotateLeft()

Rotate tree to the left using this node as center.

Returns:

node which will take the place of this node

rotateRight

private BooleanBigList.BooleanBlockNode 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 node

previous - the previous node in the linked list

setRight

private void setRight(BooleanBigList.BooleanBlockNode node,
                      BooleanBigList.BooleanBlockNode 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