com.sun.sgs.app.util
Class ScalableList.TreeNode<E>

java.lang.Object
  com.sun.sgs.app.util.ScalableList.TreeNode<E>

Type Parameters:

E - the type of element stored in the ScalableList

All Implemented Interfaces:

ManagedObject, ScalableList.Node<E>, Serializable

Enclosing class:

ScalableList<E>

static class ScalableList.TreeNode<E>
extends Object
implements ManagedObject, Serializable, ScalableList.Node<E>

An object which forms a tree above the ListNode<E> linked list. Each TreeNode<E> has a child reference to either one TreeNode<E> or a ListNode<E>. The TreeNode<E> also has a reference to its next and previous sibling and its parent.

The TreeNode<E> is intended to only track the size of its descendant children and the number of children that it owns.

Field Summary

static byte	DECREMENT_CHILDREN_AND_SIZE
static byte	DECREMENT_SIZE
static byte	INCREMENT_CHILDREN_AND_SIZE
static byte	INCREMENT_SIZE

Constructor Summary

ScalableList.TreeNode(ScalableList<E> list, ScalableList.TreeNode<E> parent, boolean isSplit)
Constructor which creates a TreeNode while specifying parameters for the node characteristics

ScalableList.TreeNode(ScalableList<E> list, ScalableList.TreeNode<E> parent, E e)
Create a new TreeNode on account of a new leaf (ListNode) being created.

Method Summary

void	clear() Walks up the tree and removes the object and any of its parents.
(package private) void	decrement() Recursively decrements the node's size until reaching the root.
(package private) void	decrementChildrenAndSize() Decrements the number of children and size, and determines whether the parent should do both again, or just decrement the size.
(package private) ScalableList.Node<E>	getChild() Obtains the child of the current node.
(package private) int	getChildCount() Retrieves the number of immediate children beneath this node.
ScalableList.TreeNode<E>	getParent() Retrieves the node's parent.
(package private) void	increment() Recursively increments the node's size until reaching the root.
(package private) void	incrementChildrenAndSize() Increments the number of children and size, and determines whether the parent should do both, or just perform an increment of the size.
ScalableList.TreeNode<E>	next() Returns the next Node in sequence, or null if none exists.
ScalableList.TreeNode<E>	prev() Returns the previous Node in sequence, or null if none exists.
(package private) void	prune() Unlinks itself from the tree without performing a recursive deletion.
com.sun.sgs.app.util.ScalableList.SearchResult<E>	search(int currentValue, int destIndex) Traverses the tree (recursively) in search of the ListNode which contains the index provided.
(package private) void	setChild(ScalableList.Node<E> child, int size, int numberOfChildren) Sets the child to be the supplied parameter as long as it is not null.
(package private) void	setChildToNull() Sets the child to null for the relinking process.
void	setNext(ScalableList.Node<E> ref) Sets the next element to be the supplied argument.
void	setParent(ScalableList.TreeNode<E> parent) Sets the parent for the node.
void	setPrev(ScalableList.Node<E> ref) Sets the previous element to be the supplied argument.
int	size() The size of the node; that is, the sum of the sizes of its immediate children.
String	toString() Returns a String representation of this object.

Methods inherited from class java.lang.Object

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

Field Detail

DECREMENT_SIZE

public static final byte DECREMENT_SIZE

See Also:

Constant Field Values

INCREMENT_SIZE

public static final byte INCREMENT_SIZE

See Also:

Constant Field Values

INCREMENT_CHILDREN_AND_SIZE

public static final byte INCREMENT_CHILDREN_AND_SIZE

See Also:

Constant Field Values

DECREMENT_CHILDREN_AND_SIZE

public static final byte DECREMENT_CHILDREN_AND_SIZE

See Also:

Constant Field Values

Constructor Detail

ScalableList.TreeNode

ScalableList.TreeNode(ScalableList<E> list,
                      ScalableList.TreeNode<E> parent,
                      E e)

Create a new TreeNode on account of a new leaf (ListNode) being created.

Parameters:

list - the ScalableList which is the owner of this structure

parent - the intended parent

e - an element to add into the empty ListNode

ScalableList.TreeNode

ScalableList.TreeNode(ScalableList<E> list,
                      ScalableList.TreeNode<E> parent,
                      boolean isSplit)

Constructor which creates a TreeNode while specifying parameters for the node characteristics

Parameters:

list - the ScalableList owner of this structure

parent - the intended parent ListNode

isSplit - true if the TreeNode is to be created due to a split operation, and false otherwise.

Method Detail

toString

public String toString()

Returns a String representation of this object.

Overrides:

toString in class Object

Returns:

a String representation of this object.

prev

public ScalableList.TreeNode<E> prev()

Returns the previous Node in sequence, or null if none exists.

Specified by:

prev in interface ScalableList.Node<E>

Returns:

the previous node

setPrev

public void setPrev(ScalableList.Node<E> ref)

Sets the previous element to be the supplied argument. The argument should be the same type as the variable.

Specified by:

setPrev in interface ScalableList.Node<E>

Parameters:

ref - the previous Node

next

public ScalableList.TreeNode<E> next()

Returns the next Node in sequence, or null if none exists.

Specified by:

next in interface ScalableList.Node<E>

Returns:

the next node

getChild

ScalableList.Node<E> getChild()

Obtains the child of the current node. The child represents the head of the list of children. The TreeNode does not have references to all the children, so it uses knowledge of the head to iterate through them.

Returns:

the child, which can be either a TreeNode or ListNode, depending on the position of the current node in the tree.

setChild

void setChild(ScalableList.Node<E> child,
              int size,
              int numberOfChildren)

Sets the child to be the supplied parameter as long as it is not null. This method also updates the size of the parent because changing the child suggests that a new size exists.

Parameters:

child - the new child

setChildToNull

void setChildToNull()

Sets the child to null for the relinking process.

size

public int size()

The size of the node; that is, the sum of the sizes of its immediate children.

Specified by:

size in interface ScalableList.Node<E>

Returns:

the size of this node.

increment

void increment()

Recursively increments the node's size until reaching the root. The root is not updated to enable some degree of concurrency.

decrement

void decrement()

Recursively decrements the node's size until reaching the root. The root is not updated to enable some degree of concurrency.

clear

public void clear()

Walks up the tree and removes the object and any of its parents. This method is intended to be called during the AsynchronousClearTask operation.

Specified by:

clear in interface ScalableList.Node<E>

getChildCount

int getChildCount()

Retrieves the number of immediate children beneath this node.

Returns:

the number of immediate children

getParent

public ScalableList.TreeNode<E> getParent()

Retrieves the node's parent.

Specified by:

getParent in interface ScalableList.Node<E>

Returns:

the parent, or null if none exists.

setNext

public void setNext(ScalableList.Node<E> ref)

Sets the next element to be the supplied argument. The argument should be the same type as the variable.

Specified by:

setNext in interface ScalableList.Node<E>

Parameters:

ref - the next Node

prune

void prune()

Unlinks itself from the tree without performing a recursive deletion. This method is guaranteed to delete itself. This method re-links references that are dangling as a result of this node's removal. There are four conditions:

The first condition is if the TreeNode is an intermediate node. If so, it is necessary to link the left and right siblings together before the node is pruned.

The second condition is if the TreeNode is the tail node. If so, then the previous element's next reference is set to null before the node is pruned.

The third condition is if the TreeNode is the head node. If so, then the next element's previous reference is set to null before the node is pruned.

The last condition is if the TreeNode is an only- child. If so, then the parent's child reference is set to null before the node is pruned.

setParent

public void setParent(ScalableList.TreeNode<E> parent)

Sets the parent for the node.

Specified by:

setParent in interface ScalableList.Node<E>

Parameters:

parent - the intended parent

incrementChildrenAndSize

void incrementChildrenAndSize()

Increments the number of children and size, and determines whether the parent should do both, or just perform an increment of the size.

decrementChildrenAndSize

void decrementChildrenAndSize()

Decrements the number of children and size, and determines whether the parent should do both again, or just decrement the size.

search

public com.sun.sgs.app.util.ScalableList.SearchResult<E> search(int currentValue,
                                                                int destIndex)

Traverses the tree (recursively) in search of the ListNode which contains the index provided. If no ListNode can be found, then null is returned.

Specified by:

search in interface ScalableList.Node<E>

Parameters:

currentValue - the current index value at the beginning of this current search

destIndex - the absolute index of the desired element

Returns:

the ListNode containing the absolute destIndex