# Neural network allowing for arbitrary topology 
# and recurrent connections

# FreeNetwork.tz (c) 2010 Jacob Schrum.
# See Simulation.tz for more copyright information

@include "Abstract.tz"
@include "Constants.tz"

@define ONE_STEP_PROPAGATION 0.
@define INITIAL_MAX_WEIGHT 10.0.
# An impossible weight value
@define NO_CONNECTION -10000.
# Node Types
@define NODE_INPUT 0.
@define NODE_HIDDEN 1.
@define NODE_OUTPUT 2.
# Activation Function
@define ACTIVATE_SIGMOID 0.
@define ACTIVATE_GAUSSIAN 1.

Abstract : FreeNode {
	+ variables:
		function-type (int).
		node-type (int).
		innovation-number (int).
		current-sum (double).
		current-activation (double).
		previous-activation (double).
		output-targets (list).
		synapse-weights (list).
		absolute-position (int).
		frozen (int).
	
		# index: position in output-target list for node	
	+ to remove-link to-target index (int):
		remove output-targets{index}.
		remove synapse-weights{index}.
		
		# Set/Get Field
		
		# absolute-position only for copying
	+ to set-absolute-position to val (int):
		absolute-position = val.
		
	+ to get-absolute-position:
		return absolute-position.
		
	+ to set-activation to type (int):
		function-type = type.
		
	+ to get-activation-type:
		return function-type.
		
	+ to set-type to type (int):
		node-type = type.
		
	+ to get-type:
		return node-type.
		
	+ to set-innovation-number to num (int):
		innovation-number = num.
		
	+ to get-innovation-number:
		return innovation-number.
		
		# Construct

	+ to init:
		# user must change this
		innovation-number = 0.
		
		self flush.
		
		function-type = ACTIVATE_SIGMOID.
		output-targets = {}.
		synapse-weights = {}.
		frozen = 0.
		
	+ to flush:
		current-sum = 0.
		current-activation = 0.
		previous-activation = 0.
	
		# theNode: an instance of FreeNode contained in the node-list for the same
		#          FreeNetwork containing the calling FreeNode.
		# weight: weight along the synapse between calling node and theNode
		# - if theNode is already in the target list (connection already exists), it is not added	
		# - returns 1 on successful add, 0 otherwise
	+ to add-output-target node theNode (object) with-synaptic-weight weight (double):
		i (int).
		present (int).		

		# Only form a connection if no other connection previously exists
		present = 0.
		for i = 0,(( i < |output-targets| ) && ( !present )), i++ :
		{
			if (output-targets{i} get-innovation-number) == (theNode get-innovation-number) :
				present = 1.
		}

		if ( !present ) :
		{
			push theNode onto output-targets.
			push weight onto synapse-weights.
			return 1.
		}		

		return 0.

		# Use
		
	+ to activate:
		i (int).
		
		previous-activation = current-activation.
		
		if (function-type == ACTIVATE_SIGMOID) : current-activation = self sigmoid of current-sum.
		else if (function-type == ACTIVATE_GAUSSIAN) : current-activation = self gaussian of current-sum.
		else 
		{
			print "Error! Invalid activation function: $function-type".
			controller end-simulation.
			return.
		}
		
		current-sum = 0.
		
		for i=0, i<|output-targets|, i++ :
		{
			output-targets{i} increment-sum by (current-activation * synapse-weights{i}).
		}
		
	+ to get-output:
		return current-activation.
		
	+ to increment-sum by amount (double):
		current-sum += amount.
		
	+ to get-number-of-output-targets:
		return |output-targets|.

	+ to get-number-of-non-frozen-output-targets:
		i (int).
		total (int).

		total = 0.
		for i = 0, i < |output-targets|, i++ : {
			if !(output-targets{i} is-frozen) : {
				total++.
			}
		}
	
		return total.
	
	+ to replace-output-target at-position pos (int) with-node node (object) and-weight weight (double):
		output-targets{pos} = node.
		synapse-weights{pos} = weight.
		
	+ to replace-output-target at-position pos (int) with-node node (object):
		output-targets{pos} = node.
		
	+ to get-target-node at-position pos (int):
		return output-targets{pos}.
		
	+ to get-output-targets:
		return output-targets.
		
	+ to get-synapse-weight at-position pos (int):
		return synapse-weights{pos}.
		
	+ to set-synapse-weight at-position pos (int) to weight (double):
		synapse-weights{pos} = weight.
	
		# pos: position in synapse-weights.
		# delta: amount by which to modify the given weight.	
	+ to perturb-synapse-weight at-position pos (int) by delta (double):
		if !frozen : synapse-weights{pos} = synapse-weights{pos} + delta.

	+ to is-frozen:
		return frozen.
	
	+ to freeze:
		if (|output-targets| > 0) || (node-type == NODE_OUTPUT) : {
			frozen = 1.
		}

	+ to set-frozen to bit (int):
		frozen = bit.

	+ to thaw:
		frozen = 0.
	
	+ to get-synapse-weights:
		return synapse-weights.
		
	+ to sigmoid of x (double):
		return (2 / (1 + (E ^ (-2 * x)))) - 1.
		
	+ to gaussian of x (double):
		return (E ^ (- (x * x)/2)).
		
	+ to copy:
		i (int).
		newNode (object).
		
		newNode = new FreeNode.
		
		newNode set-type to node-type.
		newNode set-innovation-number to innovation-number.
		newNode set-frozen to frozen.
	
		for i=0, i<|output-targets|, i++ :
		{
			newNode add-output-target node output-targets{i} with-synaptic-weight synapse-weights{i}.
		}

		return newNode.

		# Are these operations even necessary?	
	+ to destroy:		
		free synapse-weights.
		synapse-weights = {}.
		output-targets = {}.
}

Abstract : FreeNetwork {
	+ variables:
		# Add these tracking options
		unique-id (int).
		parent-ids (list).
		output-mode-to-delete-on-copy (int).
		mode-ages (list).
		most-recent-mode-usage-percentages (list).
		generations-alive (int).
		delete-soon (int).
		node-list (list).
		number-inputs (int).
		number-outputs (int).
		# for archiving
		archive-innovation-nums (list).
		archive-types (list).
		archive-frozen (list).
		archive-targets (list).	
		archive-weights (list).
		archive-activation-functions (list).
		# ES style changing mutation rates	
		mutation-rates (hash).	
		mutation-range (double).
		# Scores
		number-evaluations (list).
		average-scores (list).
		sums-of-squares (list).

	+ to set-ids unique id (int) parents ps (list):
		#print "set id $unique-id -> $id".
		unique-id = id.
		parent-ids = ps.

	+ to get-id:
		return unique-id.

	+ to get-parent-ids:
		return parent-ids.

	+ to survive-another-generation:
		generations-alive++.
		self increment-mode-ages.

	+ to get-age:
		return generations-alive.

		# This is valid when networks are copied to make a homogeneous team
	+ to set-age to age (int):
		generations-alive = age.

	+ to set-stats scores s (list) evals e (list) ss v (list):
		#print "$unique-id:set s $s e $e v $v".

		average-scores = s.
		number-evaluations = e.
		sums-of-squares = v.

	+ to get-average-scores:
		return average-scores.

	+ to get-number-evaluations:
		return number-evaluations.

	+ to get-sums-of-squares:
		return sums-of-squares.

	+ to get-variance obj x (int): 
		n (double).
		ss (double).

		#print "$unique-id:number-evaluations $number-evaluations, sums-of-squares $sums-of-squares".

		n = number-evaluations{x}.
		ss = sums-of-squares{x}.
		# Without enough evals to determine variance, it is effectively infinity
		if (n <= 1) : return INT_INFINITY.
		else return (ss / (n - 1)).

	+ to get-variances:
		temp (list).
		i (int).

		temp = {}.
		for i = 0, i < |sums-of-squares|, i++ : {
			push (self get-variance obj i) onto temp.
		}

		return temp.

	+ to get-standard-devs:
		i (int).
		temp (list).

		temp = (self get-variances).
		for i = 0, i < |temp|, i++ : {
			temp{i} = sqrt(temp{i}).
		}

		return temp.

	+ to incorporate-new-scores fitness extra (list) inclusion keep (list):
		i (int).
		xn-1 (double).

		if (|average-scores| == 0) : {
			#print "$unique-id:incorporate-new: $number-evaluations -> $keep, $average-scores -> $extra".
			average-scores = extra.
			number-evaluations = keep.
			sums-of-squares = {}.
			for i = 0, i < |extra|, i++ : {
				push 0 onto sums-of-squares.
			}
			#print "$unique-id:Fresh scores: $extra, $keep".
		} else {
			#print "$unique-id:Update: $average-scores, $number-evaluations, $sums-of-squares using $extra, $keep".
			for i = 0, i < |extra|, i++ : {
				if (keep{i} > 0) : {
					number-evaluations{i} += keep{i}.
					xn-1 = average-scores{i}.
					average-scores{i} += ((extra{i} - average-scores{i}) / ((number-evaluations{i}) * 1.0)).
					sums-of-squares{i} = (self next-sum-of-squares old (sums-of-squares{i}) 
											point (extra{i}) 
											old-avg xn-1 
											new-avg (average-scores{i}) ).
				}
			}
			#print "$unique-id:  becomes: $average-scores, $number-evaluations, $sums-of-squares".
			#print "$unique-id:$average-scores, $number-evaluations,",(self get-variances).
		}

	+ to next-sum-of-squares old ss (double) point x (double) old-avg xn-1 (double) new-avg xn (double):
		return (ss + ((x - xn)*(x - xn-1))).

		# Species

	+ to get-node-with-innovation-number node num (int):
		i (int).
		node (object).

		node = 0.

		for i = 0, i < |node-list| && !node, i++ :
		{
			if (node-list{i} get-innovation-number) == num : node = node-list{i}.
		}

		return node.

	+ to get-sorted-innovation-nums-of-targets node-with innovation-num (int):
		node (object).

		node = (self get-node-with-innovation-number node innovation-num).
		return (self get-sorted-innovation-nums-from given (node get-output-targets)).

	+ to get-sorted-innovation-nums:
		return (self get-sorted-innovation-nums-from given node-list).

	+ to get-sorted-innovation-nums-from given nodes (list):
		nums (list).
		i (int).

		nums = {}.

		for i = 0, i < |nodes|, i++ :
		{
			push (nodes{i} get-innovation-number) onto nums.
		}

		((controller get-list-ops) ascending-sort the-list nums).

		return nums.

		# Archive

	+ to blank-archive:
		free archive-innovation-nums.
		free archive-types.
		free archive-frozen.
		free archive-targets.	
		free archive-weights.
		free archive-activation-functions.
		
	+ to get-archive-activation-functions:
		return archive-activation-functions.
		
	+ to get-archive-innovation-nums:
		return archive-innovation-nums.
		
	+ to get-archive-targets:
		return archive-targets.
		
	+ to get-archive-weights:
		return archive-weights.
		
	+ to archive:
		self fill-archive.
	
		# Report success	
		return 1.
		
	+ to fill-archive:
		i (int).
		j (int).
		connections (list).
		weights (list).
		
		archive-innovation-nums = {}.
		archive-targets = {}.	
		archive-weights = {}.
		archive-types = {}.
		archive-frozen = {}.
		archive-activation-functions = {}.
		
		for i=0, i<|node-list|, i++ :
		{
			push (node-list{i} get-innovation-number) onto archive-innovation-nums.
			push (node-list{i} get-type) onto archive-types.
			push (node-list{i} is-frozen) onto archive-frozen.
			push (node-list{i} get-activation-type) onto archive-activation-functions.
			connections = {}.
			weights = {}.
			for j=0, j < (node-list{i} get-number-of-output-targets), j++ :
			{
				push ((node-list{i} get-target-node at-position j) get-innovation-number) onto connections.
				push (node-list{i} get-synapse-weights){j} onto weights.
			}
			push connections onto archive-targets.
			push weights onto archive-weights.
		}    
		
	+ to dearchive:
		i (int).
		j (int).
		
		node-list = {}.
		
		for i = 0, i < |archive-innovation-nums|, i++ :
		{
			push (new FreeNode) onto node-list.
			node-list{i} set-innovation-number to (archive-innovation-nums{i}).
			node-list{i} set-type to (archive-types{i}).
			node-list{i} set-frozen to (archive-frozen{i}).
			# Needed for backwards compatability with networks that don't have different activation types
			if (i >= |archive-activation-functions|) : push ACTIVATE_SIGMOID onto archive-activation-functions.
			node-list{i} set-activation to (archive-activation-functions{i}).
		}
		
		for i = 0, i < |archive-targets|, i++ :
		{
			for j = 0, j < |archive-targets{i}|, j++ :
			{
				self add-connection-between-nodes-with-innovation-numbers of (archive-innovation-nums{i}) and (archive-targets{i}{j}) with-synaptic-weight (archive-weights{i}{j}).
			}
		}
		
		# Reclaim space used for the dearchive
		self blank-archive.

		# Report success
		return 1.
		
		# Create

	+ to initialize-mutation-rates:
		mutation-types (list).
		i (int).
		rate (double).

		mutation-types={"perturbation-rate",
				"new-connection-rate",
				"new-input-connection-rate",
				"splice-rate",
				"new-nn-mode-rate",
				"demote-mode-rate",
				"merge-output-modes-rate",
				"merge-nodes-rate",
				"cascade-node-rate",
				"switch-activation-rate",
				"delete-mode-rate",
				"freeze-rate"}.
		
		for i = 0, i < |mutation-types|, i++ :
		{
			rate = ((controller get-commandline) num-param named ( mutation-types{i} )).
			if (rate > 0) : mutation-rates{( mutation-types{i} )} = rate.
		}

		mutation-range = ((controller get-commandline) num-param named "modify-mutation-range").

	+ to get-mutation-rate type name (string):
		if (mutation-rates{ name }) : return (mutation-rates{ name }).
		else return 0.0.		

	+ to adjust-mutation-rates:
		key (string).

		foreach key in keys( mutation-rates ) :
		{
			mutation-rates{key} = (mutation-rates{key} + (random[ (2 * mutation-range) ] - mutation-range)).
		}

		mutation-range += (random[ (2 * mutation-range) ] - mutation-range).
		if (mutation-range < 0.0) : mutation-range *= (-1).

	+ to init:
		mode-ages = { 0 }.
		output-mode-to-delete-on-copy = -1.
		most-recent-mode-usage-percentages = {}.
		delete-soon = 0.
		self reset.

	+ to get-mode-ages:
		return mode-ages.

	+ to get-mode-age of mode (int):
		return ( mode-ages{mode} ).

	+ to get-youngest-mode-age:
		if (|mode-ages| == 0) : return 0.
		else return mode-ages{ (|mode-ages| - 1) }.

	+ to set-mode-ages to ages (list):
		mode-ages = ages.

	+ to increment-mode-ages:
		i (int).

		for i = 0, i < |mode-ages|, i++ : {
			mode-ages{i} = (mode-ages{i} + 1).
		}

		#print "$self: $mode-ages".

	+ to add-mode-to-ages:
		push 0 onto mode-ages.

	+ to remove-mode-age mode m (int):
		remove mode-ages{m}.

	+ to get-most-recent-mode-usage-percentages:
		return most-recent-mode-usage-percentages.

		# xs: counts of how many times each mode was used.
		# Used to calculate percentages.
	+ to set-most-recent-mode-usage-percentages raw xs (list):
		i (int).
		total (double).

		#print "set-most-recent-mode-usage-percentages from $xs".
		total = 0.
		most-recent-mode-usage-percentages = {}.
		for i = 0, i < |xs|, i++ : {
			total += (xs{i}).
		}

		for i = 0, i < |xs|, i++ : {
			push (xs{i} / total) onto most-recent-mode-usage-percentages.
		}

	+ to plan-to-delete-mode mode x (int):
		output-mode-to-delete-on-copy = x.

	+ to get-and-reset-pending-mode-deletion:
		temp (int).

		temp = output-mode-to-delete-on-copy.
		output-mode-to-delete-on-copy = -1.
		return temp.

	+ to reset:
		#print "$unique-id:reset".
		generations-alive = 0.	
		number-evaluations = {}.
		average-scores = {}.
		sums-of-squares = {}.
	
	+ to copy:
		i (int).
		j (int).
		tempNode (object).
		tempNodeList (list).
		newNet (object).
		absolutePosition (int).
		weight (double).
		temp (list).
	
		#print "$unique-id:copy".	
		newNet = new FreeNetwork.
		newNet set-age to (self get-age).
		newNet set-stats scores (self get-average-scores) evals (self get-number-evaluations) ss (self get-sums-of-squares).
		newNet set-number-inputs to number-inputs.
		newNet set-number-outputs to number-outputs.
		
		temp = {}.
		for i = 0, i < |(self get-mode-ages)|, i++ : {
			push ((self get-mode-ages){i}) onto temp.
		}
		newNet set-mode-ages to temp.

		self update-absolute-positions.
		
		tempNodeList = {}.
		
		for i=0, i<|node-list|, i++ :
		{
			tempNode = new FreeNode.
			tempNode set-type to (node-list{i} get-type).
			tempNode set-innovation-number to (node-list{i} get-innovation-number).
			tempNode set-frozen to (node-list{i} is-frozen).
			
			push tempNode onto tempNodeList.
		}
		
		for i=0, i<|node-list|, i++ :
		{
			for j=0, j < (node-list{i} get-number-of-output-targets), j++ :
			{
				absolutePosition = (node-list{i} get-target-node at-position j) get-absolute-position.
				weight = (node-list{i} get-synapse-weights){j}.
				tempNodeList{i} add-output-target node (tempNodeList{absolutePosition}) with-synaptic-weight weight.
			}
			newNet push-onto-node-list node tempNodeList{i}.
		}
		
		return newNet.
		
	+ to update-absolute-positions:
		i (int).
		
		for i=0, i<|node-list|, i++ :
		{
			node-list{i} set-absolute-position to i.
		}
		
		# Ask Properties
		
	+ to weight-of-connection-between-innovation-numbers of num1 (int) and num2 (int):
		i (int).
		j (int).
		
		for i=0, i<|node-list| && ((node-list{i} get-innovation-number) != num1), i++ :
		{
			# loop to find innovation number
		}
		
		if i == |node-list| :
		{
			# Special case needed by crossover
			return NO_CONNECTION.

			#print "Error! Innovation number not found in whole network".
			#print "weight-of-connection-between-innovation-numbers of $num1 and $num2".
			#controller end-simulation.
			#return.
		}
		else
		{
			for j=0, j < (node-list{i} get-number-of-output-targets) && 
			         (((node-list{i} get-target-node at-position j) get-innovation-number) != num2), j++ :
			{
				# Loop to find innovation number
			}
			
			if j == (node-list{i} get-number-of-output-targets) :
			{
				return NO_CONNECTION.
			}
		}
		
		# Found connection between innovation numbers
		return (node-list{i} get-synapse-weights){j}.
	
		# pos1: position in node-list
		# pos2: position in node-list
		# - returns NO_CONNECTION if there is no connection between the nodes	
	+ to weight-of-connection-between-positions of pos1 (int) and pos2 (int):
		j (int).
		
		self update-absolute-positions.
		
		for j=0, j < (node-list{pos1} get-number-of-output-targets) && 
		             (((node-list{pos1} get-target-node at-position j) get-absolute-position) != pos2), j++ :
		{
			# Loop to find position
		}
		
		if j == (node-list{pos1} get-number-of-output-targets) :
		{
			return NO_CONNECTION.
		}
		
		# Found connection between positions
		return (node-list{pos1} get-synapse-weights){j}.
		
		# Add Nodes
		
	+ to push-onto-node-list node theNode (object):
		push theNode onto node-list.
		
	+ to insert-into-node-list node theNode (object) after-innovation num (int):
		i (int).
		new-pos (int).
		
		for i=0, (i<|node-list|) && ((node-list{i} get-innovation-number) != num), i++ :
		{
			# Just loop until the right innovation number
		}
		
		if i == |node-list| :
		{
			print "Error! Should have found the innovation number!".
			self print-network.
			print "Put ", (theNode get-innovation-number) ,"after $num".
			controller end-simulation.
			return.
		}
		
		new-pos = max((i + 1), number-inputs).
		insert theNode at node-list{ new-pos }.
		
		
		# Set/Get

		# Return a vector of 0's and 1's indicating whether or not
		# each input is connected to the network.
	+ to get-input-connectivity:
		i (int).
		usage (list).

		usage = {}.

		for i = 0, i < number-inputs, i++ : {
			if (node-list{i} get-number-of-output-targets) > 0 : {
				push 1 onto usage.
			} else {
				push 0 onto usage.
			}
		}

		return usage.
	
	+ to get-length-longest-non-recurrent-path:
		i (int).
		max-len (int).

		max-len = 0.

		self update-absolute-positions.

		for i = 0, i < (self get-number-inputs), i++ :
		{
			max-len = max(max-len,(self get-length-longest-non-recurrent-path from i)).
		}

		return max-len.

		# node: index in node-list
		# - absolute-positions must have been updated by a call to update-absolute-positions
		# - should only be called by self and the above method
	+ to get-length-longest-non-recurrent-path from node (int):
		i (int).
		max-len (int).
		temp (int).

		if ((node-list{node} get-type) == NODE_OUTPUT) : return 0.
		max-len = 0.

		for i = 0, i < (node-list{node} get-number-of-output-targets), i++ :
		{
			if (((node-list{node} get-target-node at-position i) get-absolute-position) > node) :
			{
				temp = 1 + (self get-length-longest-non-recurrent-path from ((node-list{node} get-target-node at-position i) get-absolute-position)).
				max-len = max(temp, max-len).
			}
		}

		return max-len.
	
	+ to get-number-of-links:
		i (int).
		total (int).
		
		total = 0.
		
		for i=0, i<|node-list|, i++ :
		{
			total += (node-list{i} get-number-of-output-targets).
		}
		
	+ to set-number-inputs to num (int):
		number-inputs = num.
		
	+ to set-number-outputs to num (int):
		number-outputs = num.
		
	+ to get-number-inputs:
		return number-inputs.
		
	+ to get-number-outputs:
		return number-outputs.
		
	+ to get-node-list:
		return node-list.

		# pos1: position in node-list
		# pos2: position in target list of node at position pos1
	+ to get-target-node of-parent pos1 (int) target-num pos2 (int):
		return (node-list{pos1} get-target-node at-position pos2).
	
	+ to get-innovation-number at-position pos (int):
		return (node-list{pos} get-innovation-number).

		# returns position of innovation number if exists, -1 otherwise
	+ to get-position-of-innovation num innov (int):
		i (int).

		for i = 0, i < |node-list|, i++ :
		{
			if (((node-list{i}) get-innovation-number) == innov) : {
				return i.
			}
		}
		
		return -1.
	
	+ to get-number-of-nodes:
		return |node-list|.
		
		# pos: position in node-list
	+ to get-number-of-non-frozen-targets-of-node at-position pos (int):
		return (node-list{pos} get-number-of-non-frozen-output-targets).

	+ to get-number-of-targets-of-node at-position pos (int):
		return (node-list{pos} get-number-of-output-targets).
		
		# Modify/Mutate

	+ to remove-output-node-by-innovation with-innovation innov (int):
		self remove-output-node at-position (self get-position-of-innovation num innov).	

		# pos: position in node list that is an output node
		# - pos is an output node
	+ to remove-output-node at-position pos (int):	

		#print "Remove output: $pos".

		if (pos >= |node-list|) : {
			print "Error! Node to remove is out of bounds".
			print "Size:", |node-list|.
                        self print-network.
                        print "pos: $pos".
                        controller end-simulation.
                        return.
		} else if (((node-list{pos}) get-type) != NODE_OUTPUT ) : {
			print "Error! Can only remove output node!".
                        self print-network.
                        print "pos: $pos".
                        controller end-simulation.
                        return.
		} else {
			self remove-non-input-node with-innovation ((node-list{pos}) get-innovation-number).
			number-outputs--.	
		}

		# innov: innovation number for node that is not an input node
		# - innov is a non-input node
		# Notes: innov can initially indicate either a hidden
		#        or output node, but if recursion occurs, then
		#        innov should always be a hidden node.
	+ to remove-non-input-node with-innovation innov (int):	
		i (int).
		j (int).		
		targets (int).
		targetInnovationNum (int).
		secondInnov (int).
		hadSelfLink (int).
		recurrentLinks (int).
		removedLink (int).
		pendingRemoveIndex (int).
		pos (int).
		recursed (int).
		secondNode (object).

		self update-absolute-positions.
		pos = (self get-position-of-innovation num innov).

		if (((node-list{pos}) get-type) == NODE_INPUT ) :
		{
			# Could be treated as base case.
			# Catastrophic failure not necessary
                        return.
		}
		else
		{
			recursed = 0.
			targetInnovationNum = innov.

			for i = 0, i < |node-list|, i++ :
                        {
				targets = (node-list{i} get-number-of-output-targets). 
				hadSelfLink = 0.
				removedLink = 0.
				recurrentLinks = 0.
				pendingRemoveIndex = -1.
				for j = 0, j < targets, j++ :
				{
					secondNode = (node-list{i} get-target-node at-position j).
					secondInnov = (secondNode get-innovation-number).

					if (targetInnovationNum == secondInnov) : {
						# Remove these links
						pendingRemoveIndex = j.
						removedLink = 1.
					} else if ((node-list{i} get-innovation-number) == secondInnov) : {
						hadSelfLink = 1.
					} else if ( (secondNode get-absolute-position) < (node-list{i} get-absolute-position)) : {
						recurrentLinks++.
					}
				}
	
				if (pendingRemoveIndex > -1) : {
					node-list{i} remove-link to-target pendingRemoveIndex.
				}

				# if the removed link was the only non-recurrent output,
				# then the node is disconnected, and needs to be removed as well.
				# Exceptions are input nodes, which can be disconnected, and output
				# nodes, which are always implicitly connected
				if ( removedLink && ((node-list{i} get-type) == NODE_HIDDEN) ) : {

					# SMEG: This procedure may unnecessarily remove nodes whose
					# recurrent outputs somehow loop back into connected parts of the network.
					# However, since there is really no reason for a node's ONLY outputs to
					# be recurrent (except for output nodes), this shouldn't really happen.
					# Even if it does, choosing to delete a few extra nodes in such cases should
					# not be problematic.
					if ((((targets - removedLink) - hadSelfLink) - recurrentLinks) == 0) : {
					#if (((targets - removedLink) - hadSelfLink) == 0) : {
						# recursive call
						self remove-non-input-node with-innovation (node-list{i} get-innovation-number).
						# Need to reset and re-check because a cascade of removals could drastically affect the node-list size
						i = -1.
						recursed = 1.
					}
				}
			}

			# Make sure position hasn't shifted
			if recursed : pos = (self get-position-of-innovation num innov).
			remove node-list{pos}.
		}

		# pos1: position in node list that is an output node
		# pos2: position in node list that is an output node
		# - pos1 is an output node
		# - pos2 is an output node
		# - pos1 != pos2
	+ to output-node-merge at-position pos1 (int) with-position pos2 (int):
		i (int).
		j (int).
		node1 (object).
		node2 (object).
		targets (int).
		targetInnovationNum (int).
		tempInt (int).

		if (pos1 > pos2):
		{
			tempInt = pos1.
			pos1 = pos2.
			pos2 = tempInt.
		}

		node1 = (node-list{pos1}).
		node2 = (node-list{pos2}).

		if (pos1 == pos2) :
		{
			print "Error! Cannot merge node with itself!".
                        self print-network.
                        print "pos1: $pos1, pos2: $pos2".
                        controller end-simulation.
                        return.
		}
		else if ((node1 get-type) != NODE_OUTPUT ) :
		{
			print "Error! Pos1 must be an output node!".
                        self print-network.
                        print "pos1: $pos1, pos2: $pos2".
                        controller end-simulation.
                        return.
		}
		else if ((node2 get-type) != NODE_OUTPUT ) :
		{
			print "Error! Pos2 must be an output node!".
                        self print-network.
                        print "pos1: $pos1, pos2: $pos2".
                        controller end-simulation.
                        return.
		}
		else
		{
			# Make all connections outgoing from pos2 come from pos1
			targets = (node2 get-number-of-output-targets).
			for j = 0, j < targets, j++ :
			{
				node1 add-output-target node (node2 get-target-node at-position j) 
							with-synaptic-weight (node2 get-synapse-weight at-position j).
			}

			# Not all adds will be successful because node1 may already have connections
			# to node2's targets, but we will remove node2's connections regardless.
			for j = 0, j < targets, j++ :
                        {
				node2 remove-link to-target 0.
			}

			# Make everything going into pos2 go to pos1 instead
			targetInnovationNum = (node2 get-innovation-number).

			for i = 0, i < |node-list|, i++ :
                        {
				targets = (node-list{i} get-number-of-output-targets). 
				for j = 0, j < targets, j++ :
				{
					# This nodes output target needs to be redirected from pos2 to pos1
					if (targetInnovationNum == ((node-list{i} get-target-node at-position j) get-innovation-number)) :
					{
						node-list{i} add-output-target node node1 
									       with-synaptic-weight (node-list{i} get-synapse-weight at-position j).
						# Whether this add is successful or not, the existing link to
						# pos2 needs to be removed.
						node-list{i} remove-link to-target j.
						# Then the loop can be broken because only one link
						# between two nodes is possible.
						j = targets.
					}
				}
			}

			# Output node at pos2 should now have no outgoing or incoming links
			free node2.
			remove node-list{pos2}.
			number-outputs--.	
		}

		# In these functions, pos2 is position within the first node's target list. 
		# Has nothing to do with position in node-list

		# pos1: position in node list
		# pos2: position in target list of node at pos1	
		# - pos1 not an input node
		# - pos2 not an input node
		# - pos2 not an output node
		# - pos2 is not a self-recurrent connection back to pos1
	+ to merge-node at-position pos1 (int) with-target pos2 (int):
		i (int).
		j (int).
		tempNode (object).
		targets (int).
		targetInnovationNum (int).
		targetAbsolutePos (int).
		couldAdd (int).
	
		tempNode = ((node-list{pos1}) get-target-node at-position pos2).

		if (pos1 < number-inputs) :
		{
			print "Error! Cannot merge nodes into an input node!".
			self print-network.
			print "pos1: $pos1, pos2: $pos2".
			controller end-simulation.
			return.
		}
		else if ((tempNode get-type) == NODE_OUTPUT) :
		{
			print "Error! Cannot merge an output node into another node!".
			self print-network.
			print "pos1: $pos1, pos2: $pos2".
			controller end-simulation.
			return.
		}
		else if ((tempNode get-type) == NODE_INPUT) :
		{
			print "Error! Cannot merge an input node into another node!".
			self print-network.
			print "pos1: $pos1, pos2: $pos2".
			controller end-simulation.
			return.
		}
		else if ((tempNode get-innovation-number) == (node-list{pos1} get-innovation-number)) :
		{
			print "Error! Cannot merge node with itself through self-recurrent connection!".
			self print-network.
			print "pos1: $pos1, pos2: $pos2".
			controller end-simulation.
			return.
		}
		else
		{
			targetInnovationNum = (tempNode get-innovation-number).

			# links into the target now go into the parent
			for i = 0, i < |node-list|, i++ :
			{
				if (i != pos1):
				{
					targets = (node-list{i} get-number-of-output-targets). 
					for j = 0, j < targets, j++ :
					{
						tempNode = (node-list{i} get-target-node at-position j).
						if (targetInnovationNum == (tempNode get-innovation-number)) : 
						{
							# Replace the target at j with a link to the node at pos1
							couldAdd = (node-list{i} add-output-target node (node-list{pos1}) with-synaptic-weight (node-list{i} get-synapse-weight at-position j)).
							node-list{i} remove-link to-target j.
							# If a link already existed from i to pos1, then a new one was not made, so the total number
							# of targets out of i has decreased by 1
							if (couldAdd == 0) : targets--.
							# Only one link can exist between any two nodes.
							# Since one has already been found, the loop should be exited.
							j = targets.
						}
					}
				}

				# guaranteed to happen exactly once for valid networks
				if (targetInnovationNum == (node-list{i} get-innovation-number)) : targetAbsolutePos = i.
			}
			# Now no nodes except the one at pos1 have a link to the target
			# Also, the target can no longer have any self recurrent links

			# links out of the target node are moved up to its parent
			tempNode = ((node-list{pos1}) get-target-node at-position pos2).
			targets = tempNode get-number-of-output-targets.

			for i = 0, i < targets, i++ :
			{
				node-list{pos1} add-output-target node (tempNode get-target-node at-position i) with-synaptic-weight (tempNode get-synapse-weight at-position i).		
			}

			# delete the target
			node-list{pos1} remove-link to-target pos2.
			free tempNode.
			remove node-list{targetAbsolutePos}.
		}

		# pos1: position in node-list
		# pos2: position in synaptic weight list of node-list{pos1}
		# num: a unique innovation number for the new node
		# - pos1 not an output node
	+ to splice-node-between-nodes at-position pos1 (int) and-position pos2 (int) with-innovation-number num (int):
		newNode (object).
		endNode (object).
		endWeight (double).
		new-pos (int).
		replacementWeight (double).
		
		if pos1 >= (|node-list| - number-outputs) :
		{
			print "Error! Can't splice an output node!".
			self print-network.
			print "pos1: $pos1, pos2: $pos2, new innovation $num.".
			controller end-simulation.
			return.
		}
		else
		{
			
			endNode = node-list{pos1} get-target-node at-position pos2.
			endWeight = node-list{pos1} get-synapse-weight at-position pos2.
			
			newNode = new FreeNode.
			newNode set-type to NODE_HIDDEN.
			newNode set-innovation-number to num.
			newNode add-output-target node endNode with-synaptic-weight endWeight.
			
			replacementWeight = 1.0.
			
			node-list{pos1} replace-output-target at-position pos2 with-node newNode and-weight replacementWeight.
			new-pos = (max((pos1 + 1), number-inputs)).
			insert newNode at node-list{ new-pos }.
			
		}

		# pos: position in node-list
		# num: a unique innovation number for the new node
		# weight: weight from node at pos to new output node
		# - a connection will go from pos to the new node
	+ to add-output-node with-innovation-number num (int) from-position pos (int) with-weight weight (double):
		newNode (object).
		endpos (int).

		endpos = |node-list|.

		newNode = new FreeNode.
		newNode set-type to NODE_OUTPUT.
		newNode set-innovation-number to num.
		insert newNode at node-list{ endpos }.

		number-outputs++.	

		# Input from pos
		self add-connection-between-nodes at-position pos and endpos with-synaptic-weight weight.

		# pos1: position in node list
		# pos2: position in node list
		# - pos1 must be the position of an output node
		# - pos2 must be the position of an output node
		# - pos1 != pos2
	+ to demote-output-node at-pos pos1 (int) link-to pos2 (int) with weight (double):
		firstOutputPos (int).
		tempNode (object).

                if (((node-list{pos1}) get-type) != NODE_OUTPUT) :
		# - pos1 must be the position of an output node
                {
                        print "Error! Can only demote output nodes!".
                        self print-network.
                        print "pos1: $pos1, pos2: $pos2".
                        controller end-simulation.
                        return.
                } 
		else if (((node-list{pos2}) get-type) != NODE_OUTPUT) :
		# - pos2 must be the position of an output node
                {
                        print "Error! Can only link demoted node to output nodes!".
                        self print-network.
                        print "pos1: $pos1, pos2: $pos2".
                        controller end-simulation.
                        return.
                }
		else if (pos1 == pos2) :
		# - pos1 != pos2 
                {
                        print "Error! Cannot link to self!".
                        self print-network.
                        print "pos1: $pos1, pos2: $pos2".
                        controller end-simulation.
                        return.
                }

		node-list{pos1} set-type to NODE_HIDDEN.
		self add-connection-between-nodes at-position pos1 and pos2 with-synaptic-weight weight.
		firstOutputPos = (|node-list| - number-outputs).
		if (firstOutputPos < pos1) :
		{
			tempNode = node-list{pos1}.
			remove node-list{pos1}.
			insert tempNode at node-list{ firstOutputPos }.
		}

		number-outputs--.	

	+ to add-cascade-node with-innovation-number num (int):
		i (int).
		newNode (object).
		pos (int).

		pos = ( |node-list| - number-outputs).

		newNode = new FreeNode.
		newNode set-type to NODE_HIDDEN.
		newNode set-innovation-number to num.
		insert newNode at node-list{ pos }.

		# Inputs from all previous nodes
		for i = 0, i < pos, i++ :
		{
			self add-connection-between-nodes at-position i and pos with-synaptic-weight (self random-initial-weight).
		}	

		# Outputs to all output nodes
		for i = (pos + 1), i < |node-list|, i++ :
		{
			self add-connection-between-nodes at-position pos and i with-synaptic-weight (self random-initial-weight).
		}		

		# pos1: position in node-list
		# pos2: position in synaptic weight list of node-list{pos1}
		# delta: amount by which to modify weight	
	+ to perturb-weight-between-nodes at-position pos1 (int) and-position pos2 (int) by delta (double):
		node-list{pos1} perturb-synapse-weight at-position pos2 by delta.
		
		# pos1: position in node-list
		# pos2: position in node-list
		# weight: synaptic weight of new connection between nodes
	+ to add-connection-between-nodes at-position pos1 (int) and pos2 (int) with-synaptic-weight weight (double):
		node-list{pos1} add-output-target node node-list{pos2} with-synaptic-weight weight.
	
		# num1: innovation number possessed by a node in the network
		# num2: innovation number possessed by a node in the network
		# weight: synaptic weight of new connection between nodes
	+ to add-connection-between-nodes-with-innovation-numbers of num1 (int) and num2 (int) with-synaptic-weight weight (double):
		i (int).
		pos1 (int).
		pos2 (int).
		
		pos1 = -1.
		pos2 = -1.
		
		for i=0, i<|node-list| && ((pos1 == -1) || (pos2 == -1)), i++ :
		{
			if (node-list{i} get-innovation-number) == num1 : pos1 = i.
			if (node-list{i} get-innovation-number) == num2 : pos2 = i.
		}
		
		if (pos1 == -1) || (pos2 == -1) :
		{
			print "Error! Should have found the innovation numbers!".
			self print-network.
			print "num1: $num1, num2: $num2, pos1: $pos1, pos2: $pos2".
			controller end-simulation.
			return.
		}
		else
		{
			self add-connection-between-nodes at-position pos1 and pos2 with-synaptic-weight weight.
		}
		
	+ to freeze node pos (int):
		node-list{pos} freeze.

	+ to adjust-to-non-frozen index x (int):
		i (int).
		non-frozen (int).

		#print "adjust-to-non-frozen index x".
	
		non-frozen = 0.
		i = -1.
		while (x >= 0) : {
			#print "loop x $x i $i".
			i++.
			if (i >= |node-list|) : {
				if !non-frozen : { # All nodes are frozen so give up
					i = -1.
					x = -1.
				} else {
					i = -1.
				}
			} else {
				if !(self node-is-frozen node i) : {
					x--.
					non-frozen = 1.	# At least one non-frozen node found
				}
			}
		}

		return i.

	+ to node-is-frozen node pos (int):
		return (node-list{pos} is-frozen).
	
	+ to switch-activation-function of pos (int):
		if (node-list{pos} get-activation-type) == ACTIVATE_SIGMOID : (node-list{pos} set-activation to ACTIVATE_GAUSSIAN).
		else node-list{pos} set-activation-type to ACTIVATE_SIGMOID.
		
		# Random Initialize
		
	+ to random-initial-weight:
		return random[2 * INITIAL_MAX_WEIGHT] - INITIAL_MAX_WEIGHT.
		
	+ to random-initialize with-inputs numInputs (int) and-outputs numOutputs (int):
		i (int).
		j (int).
		tempNode (object).
		innovationNumber (int).
		
		number-inputs = numInputs.
		number-outputs = numOutputs.
		
		node-list = {}.
		
		innovationNumber = -1.
		# input nodes
		for i=0, i<number-inputs, i++ :
		{
			push (new FreeNode) onto node-list.
			node-list{i} set-type to NODE_INPUT.
			node-list{i} set-innovation-number to innovationNumber.
			innovationNumber--.
		}
		
		# output nodes
		for i=0, i<number-outputs, i++ :
		{
			tempNode = new FreeNode.
			tempNode set-type to NODE_OUTPUT.
			tempNode set-innovation-number to innovationNumber.
			innovationNumber--.
			
			push tempNode onto node-list.
			for j=0, j<number-inputs, j++ :
			{
				node-list{j} add-output-target node tempNode with-synaptic-weight (self random-initial-weight).
			}
		}
		
	+ to initialize-feature-selective-structure in numInputs (int) out numOutputs (int):
		i (int).
		j (int).
		inputSource (int).
		weights (list).

		weights = {}.
		for i=0, i<numInputs, i++ :
		{
			push {} onto weights.
			for j=0, j < numOutputs, j++ :
			{
				push 0.0 onto (weights{i}).
			}
		}

		for j=0, j < numOutputs, j++ :
		{
			inputSource = random[ (numInputs - 1) ].
			weights{inputSource}{j} = (self random-initial-weight).
		}
	
		self random-initialize with-inputs numInputs and-outputs numOutputs.
		
		for i=0, i<|node-list|, i++ :
		{
			for j=0, j < (node-list{i} get-number-of-output-targets), j++ :
			{
				node-list{i} set-synapse-weight at-position j to (weights{i}{j}).
			}
		}
		
		for i=0, i<|node-list|, i++ :
		{
			for j = ((node-list{i} get-number-of-output-targets) - 1), j >= 0 , j-- :
			{
				if (weights{i}{j} == 0) :
				{
					node-list{i} remove-link to-target j.
				}
			}
		}	
		
		# Use/Run
		
	+ to run-with inputs inputList (list):
		i (int).
		
		for i=0, i<number-inputs, i++ :
		{
			node-list{i} increment-sum by inputList{i}.
		}
		
		if ONE_STEP_PROPAGATION == 1 :
		{
			for i = (|node-list| - 1), i >= 0, i-- :
			{
				node-list{i} activate.
			}
		}
		else
		{
			for i=0, i<|node-list|, i++ :
			{
				node-list{i} activate.
			}
		}
		
	+ to flush:
		i (int).
		
		for i=0, i<|node-list|, i++ :
		{
			node-list{i} flush.
		}
		
	+ to get-output at-position position (int):
		return (node-list{ (|node-list| - number-outputs + position) } get-output).
	
	+ to get-all-outputs:
		i (int).
		out (list).

		out = {}.		
		for i = 0, i < number-outputs, i++ :
		{
			push (self get-output at-position i) onto out.
		}

		return out.
	
	+ to print-network:
		print (self network-to-string).
		
	+ to network-to-string:
		i (int).
		j (int).
		innovation (int).
		connections (list).
		weights (list).
		output (string).
		type (int).
		frozen (int).
		
		output = "$self\n".
		
		for i=0, i<|node-list|, i++ :
		{
			innovation = (node-list{i} get-innovation-number).
			type = (node-list{i} get-type).
			frozen = (node-list{i} is-frozen).
			connections = {}.
			weights = {}.
			for j=0, j < (node-list{i} get-number-of-output-targets), j++ :
			{
				push ((node-list{i} get-target-node at-position j) get-innovation-number) onto connections.
				push (node-list{i} get-synapse-weights){j} onto weights.
			}
			
			if frozen : output = "$output FROZEN:".
			output = "$output$innovation ($type) ($connections)-($weights)\n".
		}    
		
		return output.
		
	+ to destroy:
		i (int).
		new-hash (hash).

                for i = 0, i < |node-list|, i++ : {
                        free (node-list{i}).
                }
		free node-list.
		free parent-ids.
		free mode-ages.
		free most-recent-mode-usage-percentages.
		free archive-innovation-nums.
		free archive-types.
		free archive-frozen.
		free archive-targets.	
		free archive-weights.
		free archive-activation-functions.

		free mutation-rates.
		mutation-rates = new-hash.
		free mutation-rates.
		#print "$unique-id:destroy".	
		free number-evaluations.
		free average-scores.
		free sums-of-squares.

	+ to prepare-to-die:
		delete-soon = 1.
		
	+ to is-ready-to-die:
		return delete-soon.

	#diagnostics

	# There should be no links to nodes outside of the network
	+ to is-closed:
		i (int).
		j (int).
		targets (int).
		secondNode (object).
		secondPos (int).
		secondInnov (int).

		self update-absolute-positions.

		for i = 0, i < |node-list|, i++ :
		{
			targets = (node-list{i} get-number-of-output-targets). 
			for j = 0, j < targets, j++ :
			{
				secondNode = (node-list{i} get-target-node at-position j).
				secondPos = (secondNode get-absolute-position).
				secondInnov = (secondNode get-innovation-number).

				# Node is outside network
				if (secondPos >= |node-list|) || (secondInnov != (node-list{secondPos} get-innovation-number)) : {
					return 0.
				} 
			}
		}

		return 1.
}