NodeIdManager.java

package net.bmahe.genetics4j.neat;

import java.util.Collection;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicLong;

import org.apache.commons.lang3.Validate;

import net.bmahe.genetics4j.neat.spec.NeatNodeLayout;

/**
 * Allocates collision-safe hidden-node IDs for one semantic node layout.
 *
 * <p>A manager is intended to be shared by every chromosome in an evolving population. It tracks IDs already present
 * in chromosomes and assigns one stable hidden-node ID to each ancestral connection innovation that is split by an
 * add-node mutation. Consequently, homologous mutations receive the same node ID even when they occur in different
 * genomes.
 *
 * <p>Allocation and registration methods are synchronized so a manager can safely be used by concurrent mutation
 * workers. IDs are drawn exclusively from the layout's hidden-node range and exhaustion is reported with an
 * {@link IllegalStateException}.
 *
 * @see NodeIdManagerRegistry
 * @see InnovationManager
 */
public class NodeIdManager {

	private final NeatNodeLayout nodeLayout;
	private final AtomicLong nextNodeId;
	private final Set<Integer> allocatedNodeIds = ConcurrentHashMap.newKeySet();
	private final ConcurrentHashMap<Integer, Integer> splitNodeIds = new ConcurrentHashMap<>();
	private final ConcurrentHashMap<Integer, Integer> splitInnovationsByNodeId = new ConcurrentHashMap<>();

	/**
	 * Creates a manager for one node layout.
	 *
	 * @param _nodeLayout layout defining the external IDs and hidden-node range
	 * @throws NullPointerException if {@code _nodeLayout} is {@code null}
	 */
	public NodeIdManager(final NeatNodeLayout _nodeLayout) {
		nodeLayout = Validate.notNull(_nodeLayout);
		nextNodeId = new AtomicLong(nodeLayout.hiddenNodeIdStartInclusive());
	}

	/**
	 * Returns the hidden-node ID associated with splitting an ancestral connection.
	 *
	 * <p>The first call allocates an ID; subsequent calls with the same innovation return that ID.
	 *
	 * @param connectionInnovation non-negative connection innovation number
	 * @return the stable hidden-node ID for the split
	 * @throws IllegalArgumentException if the innovation number is negative
	 * @throws IllegalStateException    if the hidden-node range is exhausted
	 */
	public synchronized int nodeIdForSplit(final int connectionInnovation) {
		Validate.isTrue(connectionInnovation >= 0, "Connection innovation must be non-negative");
		return splitNodeIds.computeIfAbsent(connectionInnovation, ignored -> {
			final int nodeId = allocateNodeId();
			splitInnovationsByNodeId.put(nodeId, connectionInnovation);
			return nodeId;
		});
	}

	/**
	 * Registers node IDs already present in a chromosome before new IDs are allocated.
	 *
	 * <p>External IDs are accepted but do not consume hidden-node allocation slots. Every other ID must belong to the
	 * layout's hidden-node range.
	 *
	 * @param nodeIds IDs referenced by an existing chromosome
	 * @throws NullPointerException     if the collection or one of its elements is {@code null}
	 * @throws IllegalArgumentException if an ID is outside the layout namespaces
	 */
	public synchronized void registerExistingNodeIds(final Collection<Integer> nodeIds) {
		Validate.notNull(nodeIds);
		for (final Integer nodeId : nodeIds) {
			Validate.notNull(nodeId);
			if (nodeLayout.isExternal(nodeId) == false) {
				Validate.isTrue(nodeLayout.isHidden(nodeId), "Node ID %d is outside the layout namespaces", nodeId);
				allocatedNodeIds.add(nodeId);
			}
		}
	}

	/**
	 * Registers a known relationship between an ancestral connection and an existing hidden node.
	 *
	 * @param connectionInnovation non-negative connection innovation number
	 * @param nodeId               hidden-node ID assigned to the split
	 * @throws IllegalArgumentException if the ID is outside the hidden range or either value conflicts with a previous
	 *                                  registration
	 */
	public synchronized void registerSplit(final int connectionInnovation, final int nodeId) {
		Validate.isTrue(connectionInnovation >= 0, "Connection innovation must be non-negative");
		Validate.isTrue(nodeLayout.isHidden(nodeId), "Node ID %d is outside the hidden-node range", nodeId);
		final Integer existing = splitNodeIds.get(connectionInnovation);
		if (existing != null && existing != nodeId) {
			throw new IllegalArgumentException("Connection innovation %d is already mapped to hidden node %d"
					.formatted(connectionInnovation, existing));
		}
		final Integer existingInnovation = splitInnovationsByNodeId.get(nodeId);
		if (existingInnovation != null && existingInnovation != connectionInnovation) {
			throw new IllegalArgumentException(
					"Hidden node ID %d is already mapped to connection innovation %d".formatted(nodeId, existingInnovation));
		}
		splitNodeIds.put(connectionInnovation, nodeId);
		splitInnovationsByNodeId.put(nodeId, connectionInnovation);
		allocatedNodeIds.add(nodeId);
	}

	private int allocateNodeId() {
		while (true) {
			final long candidate = nextNodeId.getAndIncrement();
			if (candidate >= nodeLayout.hiddenNodeIdEndExclusive()) {
				throw new IllegalStateException("Hidden-node ID range [%d, %d) is exhausted"
						.formatted(nodeLayout.hiddenNodeIdStartInclusive(), nodeLayout.hiddenNodeIdEndExclusive()));
			}
			final int nodeId = Math.toIntExact(candidate);
			if (allocatedNodeIds.add(nodeId)) {
				return nodeId;
			}
		}
	}
}