I have an n-ary tree structure which has a functionality such that any node in the tree can be referenced. This means the referencing node will take it's value from the referenced node.
Rule number 1: The value of a node is computed from its children
A reference node saves you from creating a structure you have already created in the tree by letting you set a reference node and just copy its value to your preferred place in the tree. Since you have just inserted a value somewhere in this tree now it should be cascaded upwards because Rule number 1 must be satisfied.
Rule number 2: Child nodes which are used to compute value of a parent node are always leaf nodes.
Rule number 3: Cyclic references are not allowed.
Rule number 4: Root node cannot be referenced.
Tree nodes have a value which are added and that is the value of their parent node. e.g. if two child nodes have a value of 10, then their parent node's value will be 20.
Since the tree is initialized without taking reference nodes into account, references nodes should be found via a new method.
The problem is after finding the reference node, its value should be cascaded up to the root of the tree.
How can I implement this behaviour? I can find a reference node in the current tree but cascading it upwards is the issue.
Visual example:
public class TreeNode {
private Long id;
private TreeNode parent;
private List<TreeNode> children = new ArrayList<TreeNode>();
private TreeNode referenceNode;
private BigDecimal value = BigDecimal.ZERO;
}
public class TreeNodeService {
public List<TreeNode> getTreeNodes() {
List<TreeNode> treeData = new ArrayList<TreeNode>(); // assume treeData is filled by database call
if (treeData.size() > 0) {
findReferenceNode(treeData, treeData);
}
return treeData;
}
private void findReferenceNode(List<TreeNode> allNodes,
List<TreeNode> currentNodeHolder) {
if (currentNodeHolder.size() > 0) {
TreeNode currentNode = currentNodeHolder.get(0);
for (TreeNode childNode : currentNode.getChildren()) {
if (childNode.getReferenceNode() != null) {
setReferenceNodeValue(childNode.getReferenceNode().getId(),
allNodes,
childNode,
currentNode);
}
findReferenceNode(allNodes,
Arrays.asList(childNode));
}
}
}
private void setReferenceNodeValue(Long referenceId,
List<TreeNode> allNodes,
TreeNode childNode,
TreeNode parentNode) {
if (allNodes.size() > 0 && referenceId != null) {
TreeNode rootNode = allNodes.get(0);
for (TreeNode innerChild : rootNode.getChildren()) {
// If there is a match, then innerChild is our original node which
// is being referenced by childNode
if (innerChild.getId().equals(referenceId)) {
// Copy original node value and set reference node value with it
childNode.setValue(innerChild.getValue());
// Parent of this reference node might have a non-zero value already set
BigDecimal startValue = parentNode.getValue();
updateParentNodeValue(parentNode,
startValue,
childNode.getValue());
} else {
setReferenceNodeValue(referenceId,
Arrays.asList(innerChild),
childNode,
parentNode);
}
}
}
}
private void updateParentNodeValue(TreeNode parentNode,
BigDecimal startValue,
BigDecimal valueToAdd) {
BigDecimal finalValue = startValue.add(valueToAdd);
parentNode.setValue(finalValue);
}
}