com.scottlogic.util
Class SortedList.Node

java.lang.Object
  extended by com.scottlogic.util.SortedList.Node
All Implemented Interfaces:
java.lang.Comparable<SortedList.Node>
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.
 
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 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 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 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 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.