com.scottlogic.util
Class SortedList.Node

java.lang.Object
  extended by com.scottlogic.util.SortedList.Node
All Implemented Interfaces:
java.lang.Comparable<SortedList.Node>
Direct Known Subclasses:
UnsortedList.UnsortedNode
Enclosing class:
SortedList<T>

protected class SortedList.Node
extends java.lang.Object
implements java.lang.Comparable<SortedList.Node>

Inner class used to represent positions in the tree. Each node stores a list of equal values, is aware of their children and parent nodes, the height of the subtree rooted at that point and the total number of children elements they have.


Field Summary
protected  int id
          The unique id of this node: auto generated from the containing tree, the newer the node the higher this value.
 
Constructor Summary
protected SortedList.Node(T t)
          Constructs a new Node which initially just stores the given value.
 
Method Summary
 int compareTo(SortedList.Node other)
          Compares the value stored at this node with the value at the given node using the comparator, if these values are equal it compares the nodes on their IDs; older nodes considered to be smaller.
protected  SortedList.Node getGrandParent()
          Returns the grand parent Node of this Node, which may be null.
protected  SortedList.Node getLeftChild()
          Returns the left child of this Node, which may be null.
protected  SortedList.Node getParent()
          Returns the parent Node of this node, which will be null in the case that this is the root Node.
protected  SortedList.Node getRightChild()
          Returns the right child of this Node, which may be be null.
 T getValue()
          Returns the value stored at this Node.
protected  boolean hasTwoChildren()
          Returns whether or not this Node has two children.
 boolean isLeaf()
          Returns whether or not this Node is a leaf; this is true in the case that both its left and right children are set to null.
 boolean isLeftChildOfParent()
          Returns whether or not this not is the left child of its parent node; if this is the root node, then false is returned.
 boolean isRightChildOfParent()
          Returns whether or not this not is the right child of its parent node; if this is the root node, then false is returned.
protected  SortedList.Node largestNodeInSubTree()
          Finds the largest node in the tree rooted at this node.
protected  SortedList.Node predecessor()
          Gets the node that is the next smallest in the tree, which is null if this is the smallest valued node.
 int sizeOfSubTree()
          Returns, the number of children of this Node plus one.
protected  SortedList.Node smallestNodeInSubTree()
          Finds and returns the smallest node in the tree rooted at this node.
protected  SortedList.Node successor()
          Gets the next biggest node in the tree, which is null if this is the largest valued node.
 java.lang.String toString()
          A (non-recursive) String representation of this Node.
protected  void updateAdditionalCachedValues()
          Called when a node is inserted or removed from the tree and provides a hook for sub-classes to get their cached values updated.
protected  void updateCachedValues()
          Updates the height and the number of children for nodes on the path to this.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

id

protected final int id
The unique id of this node: auto generated from the containing tree, the newer the node the higher this value.

Constructor Detail

SortedList.Node

protected SortedList.Node(T t)
Constructs a new Node which initially just stores the given value.

Parameters:
t - the value which this node will store.
Method Detail

hasTwoChildren

protected boolean hasTwoChildren()
Returns whether or not this Node has two children.

Returns:
true if this node has two children and false otherwise.

getGrandParent

protected SortedList.Node getGrandParent()
Returns the grand parent Node of this Node, which may be null.

Returns:
the grand parent of this node if there is one and null otherwise.

isLeftChildOfParent

public boolean isLeftChildOfParent()
Returns whether or not this not is the left child of its parent node; if this is the root node, then false is returned.

Returns:
true if this is the left child of its parent node and false otherwise.

isRightChildOfParent

public boolean isRightChildOfParent()
Returns whether or not this not is the right child of its parent node; if this is the root node, then false is returned.

Returns:
true if this is the right child of its parent node and false otherwise.

getLeftChild

protected SortedList.Node getLeftChild()
Returns the left child of this Node, which may be null.

Returns:
the left child of this Node, which may be null.

getRightChild

protected SortedList.Node getRightChild()
Returns the right child of this Node, which may be be null.

Returns:
the right child of this node, which may be null.

getParent

protected SortedList.Node getParent()
Returns the parent Node of this node, which will be null in the case that this is the root Node.

Returns:
the parent node of this one.

compareTo

public int compareTo(SortedList.Node other)
Compares the value stored at this node with the value at the given node using the comparator, if these values are equal it compares the nodes on their IDs; older nodes considered to be smaller.

Specified by:
compareTo in interface java.lang.Comparable<SortedList.Node>
Returns:
if the comparator returns a non-zero number when comparing the values stored at this node and the given node, this number is returned, otherwise this node's id minus the given node's id is returned.

smallestNodeInSubTree

protected final SortedList.Node smallestNodeInSubTree()
Finds and returns the smallest node in the tree rooted at this node.

Returns:
the smallest valued node in the tree rooted at this node, which maybe this node.

largestNodeInSubTree

protected final SortedList.Node largestNodeInSubTree()
Finds the largest node in the tree rooted at this node.

Returns:
the largest valued node in the tree rooted at this node which may be this node.

successor

protected final SortedList.Node successor()
Gets the next biggest node in the tree, which is null if this is the largest valued node.

Returns:
the next biggest node in the tree, which is null if this is the largest valued node.

predecessor

protected final SortedList.Node predecessor()
Gets the node that is the next smallest in the tree, which is null if this is the smallest valued node.

Returns:
the node that is the next smallest in the tree, which is null if this is the smallest valued node.

isLeaf

public boolean isLeaf()
Returns whether or not this Node is a leaf; this is true in the case that both its left and right children are set to null.

Returns:
true if this node is leaf and false otherwise.

toString

public java.lang.String toString()
A (non-recursive) String representation of this Node.

Overrides:
toString in class java.lang.Object
Returns:
a String representing this Node for debugging.

sizeOfSubTree

public int sizeOfSubTree()
Returns, the number of children of this Node plus one. This method uses a cached variable ensuring it runs in constant time.

Returns:
the number of children of this Node plus one.

getValue

public T getValue()
Returns the value stored at this Node.

Returns:
the value that this Node stores.

updateCachedValues

protected final void updateCachedValues()
Updates the height and the number of children for nodes on the path to this. Also calls #updateAdditionalCachedValues(), for every node on the path to this, including this one.


updateAdditionalCachedValues

protected void updateAdditionalCachedValues()
Called when a node is inserted or removed from the tree and provides a hook for sub-classes to get their cached values updated.

This method is called every time the list is altered. It is first called on the deepest node which is affected by a given change and is then subsequently called on ancestors of this node until it is called on the root node.

It is therefore only suitable for updating cached values in the case that they are non-global and do not rely on the parent node having the correct value when being calculated.

This implementation is empty, and hence does nothing.