public class NAryTreeImpl extends java.lang.Object implements NAryTree
Modifier and Type | Field and Description |
---|---|
protected byte[][] |
configurations
Configurations are stored in a byte-array, using 2 bits per node (rounded
up to the nearest whole byte)
|
protected int[] |
leafs
stores the index of the next leaf
|
protected int[] |
next
stores the index of the next node in the subtree under m
|
protected int |
numConfigurations
The current number of configurations
|
protected int[] |
parent
stored the index of the parent of a node m.
|
protected short[] |
type
stores the type of a node m.
|
protected short[][] |
types
stores the type of a node m for each configuration.
|
Modifier | Constructor and Description |
---|---|
|
NAryTreeImpl(int[] next,
short[] type,
int[] parent) |
protected |
NAryTreeImpl(int size,
int numConfigurations) |
|
NAryTreeImpl(java.util.List<java.lang.Integer> next,
java.util.List<java.lang.Short> type,
java.util.List<java.lang.Integer> parent) |
|
NAryTreeImpl(NAryTree original) |
|
NAryTreeImpl(gnu.trove.list.TIntList next,
gnu.trove.list.TShortList type,
gnu.trove.list.TIntList parent) |
Modifier and Type | Method and Description |
---|---|
NAryTreeImpl |
add(NAryTree source,
int node,
int par,
int location)
Returns a new tree where the subtree below the node at index node in the
source tree is copied into this tree under node with index parent at
location index.
|
NAryTree |
addChild(int operatorNode,
int location,
short leafType,
byte configurationType)
Returns a new tree in which a child is added to the operator at the given
index
|
void |
addConfiguration(Configuration configuration)
adds the given configurations to the list of configurations.
|
NAryTree |
addParent(int node,
short newType,
byte configurationType)
Returns a new tree in which node from source is replaced by a new node of
the given type and where the existing node becomes a child of this newly
added parent.
|
NAryTree |
applyConfiguration(int configurationNumber)
Applies a configuration to the tree and returns the result.
|
NAryTree |
applyHidingAndOperatorDowngrading(int configurationNumber)
Apply all hiding and downgrading configurations of the provided
configuration number.
|
int |
compareTo(NAryTree o) |
int |
countNodes(short type)
counts the number of nodes of the given type
|
boolean |
equals(java.lang.Object o)
returns true if all four internal arrays are identical.
|
protected static double |
expectedCol(int keys,
long vals) |
int |
findBlockEffect(int blockedNode)
Finds the effect of blocking a particular node.
|
int |
getChildAtIndex(int par,
int n)
returns the id of the n-th child of par.
|
Configuration |
getConfiguration(int configurationNumber)
Returns the configuration stored at the given index.
|
protected int |
getHighestParentWithOneChild(int node)
returns the highest parent of the given node, such that this parent has
one child and all intermediate parents also have one child.
|
int |
getNext(int node)
returns the first node not in the subtree of the given node .
|
int |
getNextFast(int node)
returns the first node larger than the given node, which is not part of
the subtree of the given node.
|
int |
getNextLeaf(int node)
returns the leaf greater than the given node.
|
int |
getNextLeafFast(int node)
returns the leaf greater than the given node.
|
byte |
getNodeConfiguration(int configurationNumber,
int node)
returns the configuration of the node in the given configuration.
|
byte |
getNodeConfigurationFast(int configurationNumber,
int node) |
int |
getNumberOfConfigurations()
Returns the number of configurations.
|
int |
getParent(int node)
returns the parent of the given node.
|
int |
getParentFast(int node)
returns the parent of the given node.
|
short |
getType(int node)
returns the type of a node.
|
short |
getType(int configurationNumber,
int node)
returns the type of a node.
|
short |
getTypeFast(int node)
returns the type of a node.
|
short |
getTypeFast(int configurationNumber,
int node)
returns the type of a node.
|
int |
hashCode()
returns hashcode based on the internal arrays
|
int |
hashCode(int node) |
boolean |
isBlocked(int configurationNumber,
int node)
returns true if the given node is blocked in the given configuration
|
boolean |
isConsistent()
returns true if the tree is (internally) consistent
|
boolean |
isDowngraded(int configurationNumber,
int node) |
boolean |
isHidden(int configurationNumber,
int node)
returns true if the given node is hidden in the given configuration
|
boolean |
isInSubtree(int par,
int child)
returns if the child appears in the subtree of the parent
|
boolean |
isLeaf(int node)
returns true if a node is a leaf.
|
static void |
main(java.lang.String[] args) |
NAryTree |
move(int node,
int newParent,
int location)
moves the given node by removing it from its parent and adding is under
the new parent.
|
NAryTree |
move(int par,
int n,
int newParent,
int location)
moves the n-th child of the parent "par" by removing it from the tree and
inserting it as a new child under newParent.
|
int |
nChildren(int node)
returns the number of children of a node.
|
int |
numLeafs()
returns the number of leafs in the tree.
|
NAryTree |
remove(int node)
removes the node at index node from the tre
|
NAryTree |
remove(int par,
int index)
removes the child at index from node par.
|
void |
removeAllConfigurations() |
void |
removeConfiguration(int configurationNumber)
Removes the configuration at the given index from the list of
configurations.
|
NAryTree |
replace(int par,
int n,
NAryTree source,
int node)
replaces the n-th child of parent with the node from source.
|
NAryTreeImpl |
replace(int node,
NAryTree source,
int srcNode)
replaces node from this tree with the node from the source tree
It is assumed that this tree and the given tree have an equal number of
configurations.
|
protected void |
set(int index,
short typeVal,
int parentVal,
int nextVal)
Sets the values of the internal arrays according to the given parameters.
|
void |
setNodeConfiguration(int configurationNumber,
int node,
byte configurationOption)
Sets the configuration option for a node.
|
void |
setType(int par,
int n,
short t)
sets the type of the n-th child of parent par.
|
void |
setType(int index,
short t)
Sets the type of the node.
|
int |
size()
returns the number of nodes in the tree
|
int |
size(int node)
returns the size of the subtree under node
|
NAryTreeImpl |
swap(int node1,
int node2)
returns a new tree with the two nodes swapped.
|
java.lang.String |
toInternalString()
returns a string representation of the internal datastructures of the
tree (for debugging only)
|
java.lang.String |
toString() |
protected byte[][] configurations
protected int numConfigurations
protected final int[] next
protected final short[] type
protected short[][] types
protected final int[] parent
protected final int[] leafs
public NAryTreeImpl(NAryTree original)
public NAryTreeImpl(int[] next, short[] type, int[] parent)
protected NAryTreeImpl(int size, int numConfigurations)
public NAryTreeImpl(gnu.trove.list.TIntList next, gnu.trove.list.TShortList type, gnu.trove.list.TIntList parent)
public NAryTreeImpl(java.util.List<java.lang.Integer> next, java.util.List<java.lang.Short> type, java.util.List<java.lang.Integer> parent)
public boolean isConsistent()
NAryTree
isConsistent
in interface NAryTree
protected void set(int index, short typeVal, int parentVal, int nextVal)
index
- values
- public void setType(int index, short t)
NAryTree
public void setType(int par, int n, short t)
NAryTree
public NAryTreeImpl swap(int node1, int node2)
NAryTree
public NAryTreeImpl add(NAryTree source, int node, int par, int location)
NAryTree
public NAryTree addParent(int node, short newType, byte configurationType)
NAryTree
public NAryTree addChild(int operatorNode, int location, short leafType, byte configurationType)
NAryTree
addChild
in interface NAryTree
operatorNode
- node to which a child needs to be added (cannot be a leaf or a
LOOP)location
- the index at which the child should be added. 0 means the new
child becomes the leftmost, and any value greater than the
number of children implies the new node becomes the rightmost.leafType
- the new type of the new leaf node to be insertedpublic NAryTree replace(int par, int n, NAryTree source, int node)
NAryTree
replace
in interface NAryTree
par
- a node. If par is a leaf, then the parameter n is ignoredn
- the child to replace. if n==0, the leftmost child is replaced,
if n>= nChildren the rightmost is.source
- NAryTree to get the new node fromnode
- Node from the source tree to be the replacement in this treepublic NAryTreeImpl replace(int node, NAryTree source, int srcNode)
NAryTree
public NAryTree remove(int par, int index)
NAryTree
public NAryTree remove(int node)
NAryTree
public NAryTree move(int node, int newParent, int location)
NAryTree
public NAryTree move(int par, int n, int newParent, int location)
NAryTree
move
in interface NAryTree
par
- Index of the parent of the node to be movedn
- Child index of the node to be movednewParent
- Index of the new parent of the moved nodelocation
- Child location in the parent of the moved nodepublic short getType(int node)
NAryTree
public short getTypeFast(int node)
NAryTree
getTypeFast
in interface NAryTree
node
- Index of the node to get the type forpublic int getChildAtIndex(int par, int n)
NAryTree
getChildAtIndex
in interface NAryTree
par
- a non-leaf node from which the index of the n-th child to get
fromn
- -th child to return index forpublic int size(int node)
NAryTree
public int nChildren(int node)
NAryTree
public boolean isInSubtree(int par, int child)
NAryTree
isInSubtree
in interface NAryTree
par
- Index of the parent node (/root of subtree) to searchchild
- Index (absolute) of the child node to search forpublic boolean equals(java.lang.Object o)
equals
in class java.lang.Object
public int hashCode()
hashCode
in class java.lang.Object
protected int getHighestParentWithOneChild(int node)
node
- public boolean isLeaf(int node)
NAryTree
public int size()
NAryTree
public java.lang.String toInternalString()
NAryTree
toInternalString
in interface NAryTree
public java.lang.String toString()
toString
in class java.lang.Object
public int getParent(int node)
NAryTree
public int getParentFast(int node)
NAryTree
getParentFast
in interface NAryTree
node
- Index of the node to get the parent forpublic int getNext(int node)
public int getNextFast(int node)
NAryTree
getNextFast
in interface NAryTree
node
- Index of the node to get the next node outside this subtree
forpublic int numLeafs()
NAryTree
public int compareTo(NAryTree o)
compareTo
in interface java.lang.Comparable<NAryTree>
public int getNextLeaf(int node)
NAryTree
getNextLeaf
in interface NAryTree
node
- Index of the node to get the next leaf forpublic int getNextLeafFast(int node)
NAryTree
getNextLeafFast
in interface NAryTree
node
- Index of the node to get the next leaf forpublic void addConfiguration(Configuration configuration)
NAryTree
addConfiguration
in interface NAryTree
public void removeConfiguration(int configurationNumber)
NAryTree
removeConfiguration
in interface NAryTree
public int getNumberOfConfigurations()
NAryTree
getNumberOfConfigurations
in interface NAryTree
public Configuration getConfiguration(int configurationNumber)
NAryTree
getConfiguration
in interface NAryTree
public boolean isBlocked(int configurationNumber, int node)
NAryTree
public boolean isHidden(int configurationNumber, int node)
NAryTree
public boolean isDowngraded(int configurationNumber, int node)
public void setNodeConfiguration(int configurationNumber, int node, byte configurationOption)
NAryTree
setNodeConfiguration
in interface NAryTree
public byte getNodeConfigurationFast(int configurationNumber, int node)
public byte getNodeConfiguration(int configurationNumber, int node)
NAryTree
getNodeConfiguration
in interface NAryTree
public short getType(int configurationNumber, int node)
NAryTree
public short getTypeFast(int configurationNumber, int node)
NAryTree
getTypeFast
in interface NAryTree
node
- Index of the node to get the type forpublic NAryTree applyConfiguration(int configurationNumber)
NAryTree
applyConfiguration
in interface NAryTree
public int findBlockEffect(int blockedNode)
findBlockEffect
in interface NAryTree
blockedNode
- the node that is know to be blockedpublic NAryTree applyHidingAndOperatorDowngrading(int configurationNumber)
configurationNumber
- public int countNodes(short type)
NAryTree
countNodes
in interface NAryTree
public void removeAllConfigurations()
removeAllConfigurations
in interface NAryTree
protected static double expectedCol(int keys, long vals)
public static void main(java.lang.String[] args)
public int hashCode(int node)