|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectcom.scottlogic.util.SortedList.Node
protected class 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 |
---|
protected final int id
Constructor Detail |
---|
protected SortedList.Node(T t)
t
- the value which this node will store.Method Detail |
---|
protected boolean hasTwoChildren()
Node
has two children.
true
if this node has two children and false
otherwise.protected SortedList.Node getGrandParent()
Node
of this Node
, which may be null
.
null
otherwise.public boolean isLeftChildOfParent()
false
is returned.
true
if this is the left child of its parent node
and false
otherwise.public boolean isRightChildOfParent()
false
is returned.
true
if this is the right child of its parent node
and false
otherwise.protected SortedList.Node getLeftChild()
Node
, which may be null
.
Node
, which may be null
.protected SortedList.Node getRightChild()
Node
, which may be be null
.
null
.protected SortedList.Node getParent()
Node
of this node, which will be null
in the case that this is the root Node
.
public int compareTo(SortedList.Node other)
compareTo
in interface java.lang.Comparable<SortedList.Node>
protected final SortedList.Node smallestNodeInSubTree()
protected final SortedList.Node largestNodeInSubTree()
protected final SortedList.Node successor()
null
if this is
the largest valued node.
null
if this
is the largest valued node.protected final SortedList.Node predecessor()
null
if this is the smallest valued node.
null
if this is the smallest valued node.public boolean isLeaf()
Node
is a leaf; this is true in the case that
both its left and right children are set to null
.
true
if this node is leaf and false
otherwise.public java.lang.String toString()
Node
.
toString
in class java.lang.Object
String
representing this Node
for debugging.public int sizeOfSubTree()
Node
plus one. This method uses
a cached variable ensuring it runs in constant time.
Node
plus one.public T getValue()
Node
.
Node
stores.protected final void updateCachedValues()
#updateAdditionalCachedValues()
, for every node on the path to
this, including this one.
protected void updateAdditionalCachedValues()
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.
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |