TreeNode.java

package net.bmahe.genetics4j.core.chromosomes;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

import org.apache.commons.lang3.Validate;

/**
 * Represents a node in a tree structure used for genetic programming and tree-based chromosomes.
 * 
 * <p>TreeNode provides a flexible, generic tree data structure that forms the foundation for
 * tree-based genetic programming operations. Each node contains data of a specified type and
 * can have zero or more child nodes, enabling the representation of complex hierarchical
 * structures such as mathematical expressions, decision trees, or program syntax trees.
 * 
 * <p>Key features include:
 * <ul>
 * <li><strong>Generic data storage</strong>: Can hold any type of data (functions, terminals, values)</li>
 * <li><strong>Dynamic structure</strong>: Supports adding, removing, and modifying children</li>
 * <li><strong>Tree metrics</strong>: Provides size and depth calculations for analysis</li>
 * <li><strong>Hierarchical operations</strong>: Enables tree traversal and manipulation</li>
 * </ul>
 * 
 * <p>Common uses in genetic programming:
 * <ul>
 * <li><strong>Expression trees</strong>: Mathematical or logical expressions with operators and operands</li>
 * <li><strong>Program trees</strong>: Structured representation of executable code or algorithms</li>
 * <li><strong>Decision trees</strong>: Conditional logic structures for classification or control</li>
 * <li><strong>Grammar trees</strong>: Parse trees representing valid grammatical constructs</li>
 * </ul>
 * 
 * <p>Tree structure characteristics:
 * <ul>
 * <li><strong>Mutable structure</strong>: Children can be added, removed, or replaced during evolution</li>
 * <li><strong>Type safety</strong>: Generic parameterization ensures consistent data types</li>
 * <li><strong>Recursive operations</strong>: Size and depth calculations traverse the entire subtree</li>
 * <li><strong>Equality semantics</strong>: Two trees are equal if their structure and data match</li>
 * </ul>
 * 
 * <p>Example usage in genetic programming:
 * <pre>{@code
 * // Creating a simple mathematical expression: (x + 2) * 3
 * TreeNode<String> multiply = new TreeNode<>("*");
 * TreeNode<String> add = new TreeNode<>("+");
 * TreeNode<String> x = new TreeNode<>("x");
 * TreeNode<String> two = new TreeNode<>("2");
 * TreeNode<String> three = new TreeNode<>("3");
 * 
 * add.addChild(x);
 * add.addChild(two);
 * multiply.addChild(add);
 * multiply.addChild(three);
 * 
 * // Tree metrics
 * int treeSize = multiply.getSize();   // Total nodes in tree
 * int treeDepth = multiply.getDepth(); // Maximum depth from root
 * 
 * // Factory method for creating nodes with children
 * TreeNode<String> expression = TreeNode.of("*", List.of(
 *     TreeNode.of("+", List.of(
 *         new TreeNode<>("x"),
 *         new TreeNode<>("2")
 *     )),
 *     new TreeNode<>("3")
 * ));
 * }</pre>
 * 
 * <p>Integration with genetic operations:
 * <ul>
 * <li><strong>Crossover</strong>: Subtree exchange between parent trees</li>
 * <li><strong>Mutation</strong>: Replacement or modification of individual nodes or subtrees</li>
 * <li><strong>Size constraints</strong>: Enforcement of maximum tree size or depth limits</li>
 * <li><strong>Evaluation</strong>: Tree traversal for fitness computation</li>
 * </ul>
 * 
 * <p>Performance considerations:
 * <ul>
 * <li><strong>Memory usage</strong>: Each node maintains a list of children references</li>
 * <li><strong>Tree traversal</strong>: Size and depth calculations have O(n) complexity</li>
 * <li><strong>Structural sharing</strong>: Nodes can be shared between trees with care</li>
 * <li><strong>Deep trees</strong>: Very deep trees may cause stack overflow in recursive operations</li>
 * </ul>
 * 
 * @param <T> the type of data stored in each node
 * @see TreeChromosome
 * @see TreeChromosome
 */
public class TreeNode<T> {

	private final T data;

	private ArrayList<TreeNode<T>> children;

	/**
	 * Constructs a new tree node with the specified data and no children.
	 * 
	 * <p>Creates a leaf node that can later have children added to it. The data
	 * provided becomes the payload for this node and cannot be changed after construction.
	 * 
	 * @param _data the data to store in this node
	 * @throws IllegalArgumentException if data is null
	 */
	public TreeNode(final T _data) {
		Validate.notNull(_data);

		this.data = _data;
		this.children = new ArrayList<>();
	}

	/**
	 * Returns the data stored in this node.
	 * 
	 * @return the data payload of this node
	 */
	public T getData() {
		return data;
	}

	/**
	 * Returns the list of direct children of this node.
	 * 
	 * <p>The returned list is the actual internal list used by this node.
	 * Modifications to the returned list will affect this node's structure.
	 * 
	 * @return the mutable list of child nodes
	 */
	public List<TreeNode<T>> getChildren() {
		return children;
	}

	/**
	 * Returns the child node at the specified index.
	 * 
	 * @param childIndex the index of the child to retrieve (0-based)
	 * @return the child node at the specified index
	 * @throws IllegalArgumentException if childIndex is negative
	 * @throws IndexOutOfBoundsException if childIndex is >= number of children
	 */
	public TreeNode<T> getChild(final int childIndex) {
		Validate.isTrue(childIndex >= 0);

		return children.get(childIndex);
	}

	/**
	 * Replaces the child node at the specified index with a new node.
	 * 
	 * <p>This operation modifies the tree structure by replacing an existing
	 * child with a new subtree rooted at the provided node.
	 * 
	 * @param childIndex the index of the child to replace (0-based)
	 * @param childData the new child node to set at the specified index
	 * @throws IllegalArgumentException if childIndex is negative
	 * @throws IndexOutOfBoundsException if childIndex is >= number of children
	 */
	public void setChild(final int childIndex, final TreeNode<T> childData) {
		Validate.isTrue(childIndex >= 0);

		children.set(childIndex, childData);
	}

	/**
	 * Adds a new child node to this node.
	 * 
	 * <p>The new child is appended to the end of the children list.
	 * This operation increases the arity of this node by one.
	 * 
	 * @param childData the child node to add
	 * @throws IllegalArgumentException if childData is null
	 */
	public void addChild(final TreeNode<T> childData) {
		Validate.notNull(childData);

		children.add(childData);
	}

	/**
	 * Adds multiple child nodes to this node.
	 * 
	 * <p>All nodes in the provided collection are appended to the children list
	 * in the order they appear in the collection.
	 * 
	 * @param childrenNodes the collection of child nodes to add
	 * @throws IllegalArgumentException if childrenNodes is null or empty
	 */
	public void addChildren(final Collection<TreeNode<T>> childrenNodes) {
		Validate.notNull(childrenNodes);
		Validate.isTrue(childrenNodes.isEmpty() == false);

		children.addAll(childrenNodes);
	}

	/**
	 * Returns the total number of nodes in the subtree rooted at this node.
	 * 
	 * <p>This method recursively counts all nodes in the subtree, including
	 * this node and all its descendants. The size is useful for analyzing
	 * tree complexity and implementing size-based genetic operations.
	 * 
	 * @return the total number of nodes in this subtree (always >= 1)
	 */
	public int getSize() {
		return 1 + children.stream().map(TreeNode::getSize).collect(Collectors.summingInt(x -> x));
	}

	/**
	 * Returns the maximum depth of the subtree rooted at this node.
	 * 
	 * <p>The depth is defined as the length of the longest path from this node
	 * to any leaf node in the subtree. A leaf node has depth 1.
	 * 
	 * @return the maximum depth of this subtree (always >= 1)
	 */
	public int getDepth() {
		return 1 + children.stream().map(TreeNode::getDepth).max(Comparator.naturalOrder()).orElse(0);
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((children == null) ? 0 : children.hashCode());
		result = prime * result + ((data == null) ? 0 : data.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		TreeNode other = (TreeNode) obj;
		if (data == null) {
			if (other.data != null)
				return false;
		} else if (!data.equals(other.data))
			return false;
		if (children == null) {
			if (other.children != null)
				return false;
		} else if (!children.equals(other.children))
			return false;

		return true;
	}

	@Override
	public String toString() {
		return "TreeNode [data=" + data + ", children=" + children + "]";
	}

	/**
	 * Creates a new tree node with the specified data and children.
	 * 
	 * <p>This factory method provides a convenient way to construct trees
	 * with a specific structure in a single operation. All provided children
	 * are added to the new node.
	 * 
	 * @param <U> the type of data stored in the nodes
	 * @param data the data to store in the root node
	 * @param children the collection of child nodes to add
	 * @return a new tree node with the specified data and children
	 * @throws IllegalArgumentException if data is null, children is null, or children is empty
	 */
	public static <U> TreeNode<U> of(final U data, final Collection<TreeNode<U>> children) {
		Validate.notNull(data);
		Validate.notNull(children);
		Validate.isTrue(children.size() > 0);

		final TreeNode<U> rootNode = new TreeNode<>(data);
		for (TreeNode<U> childNode : children) {
			rootNode.addChild(childNode);
		}

		return rootNode;
	}
}






































Active mutators

CONDITIONALS_BOUNDARY
CONSTRUCTOR_CALLS
EMPTY_RETURNS
EXPERIMENTAL_ARGUMENT_PROPAGATION
EXPERIMENTAL_BIG_DECIMAL
EXPERIMENTAL_BIG_INTEGER
EXPERIMENTAL_MEMBER_VARIABLE
EXPERIMENTAL_NAKED_RECEIVER
EXPERIMENTAL_REMOVE_SWITCH_MUTATOR_[0-99]
EXPERIMENTAL_SWITCH
FALSE_RETURNS
INCREMENTS
INLINE_CONSTS
INVERT_NEGS
MATH
NEGATE_CONDITIONALS
NON_VOID_METHOD_CALLS
NULL_RETURNS
PRIMITIVE_RETURNS
REMOVE_CONDITIONALS_EQUAL_ELSE
REMOVE_CONDITIONALS_EQUAL_IF
REMOVE_CONDITIONALS_ORDER_ELSE
REMOVE_CONDITIONALS_ORDER_IF
REMOVE_INCREMENTS
TRUE_RETURNS
VOID_METHOD_CALLS

Tests examined

net.bmahe.genetics4j.core.chromosomes.TreeNodeTest.[engine:junit-jupiter]/[class:net.bmahe.genetics4j.core.chromosomes.TreeNodeTest]/[method:staticFactoryNullData()] (5 ms)
net.bmahe.genetics4j.core.chromosomes.TreeNodeTest.[engine:junit-jupiter]/[class:net.bmahe.genetics4j.core.chromosomes.TreeNodeTest]/[method:staticFactoryOneChild()] (0 ms)
net.bmahe.genetics4j.core.chromosomes.TreeNodeTest.[engine:junit-jupiter]/[class:net.bmahe.genetics4j.core.chromosomes.TreeNodeTest]/[method:staticFactoryMultipleChildren()] (0 ms)
net.bmahe.genetics4j.core.chromosomes.TreeChromosomeTest.[engine:junit-jupiter]/[class:net.bmahe.genetics4j.core.chromosomes.TreeChromosomeTest]/[method:simple()] (7 ms)

Report generated by PIT 1.19.6

1		package net.bmahe.genetics4j.core.chromosomes;
2
3		import java.util.ArrayList;
4		import java.util.Collection;
5		import java.util.Comparator;
6		import java.util.List;
7		import java.util.stream.Collectors;
8
9		import org.apache.commons.lang3.Validate;
10
11		/**
12		* Represents a node in a tree structure used for genetic programming and tree-based chromosomes.
13		*
14		* <p>TreeNode provides a flexible, generic tree data structure that forms the foundation for
15		* tree-based genetic programming operations. Each node contains data of a specified type and
16		* can have zero or more child nodes, enabling the representation of complex hierarchical
17		* structures such as mathematical expressions, decision trees, or program syntax trees.
18		*
19		* <p>Key features include:
20		* <ul>
21		* <li><strong>Generic data storage</strong>: Can hold any type of data (functions, terminals, values)</li>
22		* <li><strong>Dynamic structure</strong>: Supports adding, removing, and modifying children</li>
23		* <li><strong>Tree metrics</strong>: Provides size and depth calculations for analysis</li>
24		* <li><strong>Hierarchical operations</strong>: Enables tree traversal and manipulation</li>
25		* </ul>
26		*
27		* <p>Common uses in genetic programming:
28		* <ul>
29		* <li><strong>Expression trees</strong>: Mathematical or logical expressions with operators and operands</li>
30		* <li><strong>Program trees</strong>: Structured representation of executable code or algorithms</li>
31		* <li><strong>Decision trees</strong>: Conditional logic structures for classification or control</li>
32		* <li><strong>Grammar trees</strong>: Parse trees representing valid grammatical constructs</li>
33		* </ul>
34		*
35		* <p>Tree structure characteristics:
36		* <ul>
37		* <li><strong>Mutable structure</strong>: Children can be added, removed, or replaced during evolution</li>
38		* <li><strong>Type safety</strong>: Generic parameterization ensures consistent data types</li>
39		* <li><strong>Recursive operations</strong>: Size and depth calculations traverse the entire subtree</li>
40		* <li><strong>Equality semantics</strong>: Two trees are equal if their structure and data match</li>

TreeNode.java

Mutations

Active mutators

Tests examined