#!/usr/bin/guile
!#

;; (TreeOptimizer->reset n_nodes) -> unspecified
;; Restart generation with n_nodes
(define TreeOptimizer->reset #f)

;; (TreeOptimizer->iterate) -> (topo_factor . specification)
;; Calculate the topological factor of the next specified iteration
(define TreeOptimizer->iterate #f)

(let ([iterator (list)] [n_nodes #f])
	(set! TreeOptimizer->reset
		(lambda (n_nodes_new)
			(set! iterator (list))
			(set! n_nodes n_nodes_new)))
	(set! TreeOptimizer->iterate
		(lambda ()
			(let vertical_rec ([last_node #t] [remaining_nodes n_nodes] [index 0] [tf 0])
				(let ([trailing (= (+ (length iterator) 1) index)])
					(let ([stage (if (<= (length iterator) index)
												 '(1 . 1)
												 (list-ref iterator index))])
						(if (and trailing (= (car stage) remaining_nodes))
							; Break recursion. Must only happen on last_node
							(list	(list) 0 remaining_nodes index)
							(let ([stage (if trailing
														 (let ([max_substream (remainder (- remaining_nodes (car stage)) 2)])
															 (if (= (cdr stage) max_substream)
																 (let ([new_nodecount (+ (car stage) 1)])
																	 (cons new_nodecount (if (and last_node (not (= new_nodecount remaining_nodes))) 1 0))
																	 (cons (car stage) (+ (cdr stage) 1))))
															 stage))])
								(let ([horizontal_result (let horizontal_rec
																					 ([substream 0]
																						[remaining_nodes remaining_nodes]
																						[subindex (+ index 1)])
																					 (if (< substream (cdr stage))
																						 (let ([vertical_result (vertical_rec
																																			(and last_node (= substream (- (cdr stage) 1)))
																																			remaining_nodes
																																			subindex
																																			(+ tf (cdr stage) (car stage)))])
																							 (let ([vertical_result (horizontal_rec (+ substream 1) (list-ref vertical_result 2) (list-ref vertical_result 3))])
																								 (list
																									 (append (list-ref vertical_result 0) (list-ref horizontal_result 0))
																									 (+ (list-ref vertical_result 1) (list-ref horizontal_result 1))
																									 (list-ref horizontal_result 2)
																									 (list-ref horizontal_result 3))))
																						 (list (list) 0 remaining_nodes subindex)))])
									(list
										(append (list stage) (list-ref horizontal_result 0))
										(* tf (car stage))
										(list-ref horizontal_result 2)
										(list-ref horizontal_result 3)))))))))))

(TreeOptimizer->reset 4)
(TreeOptimizer->iterate)

; The iterator is a list of pairs each indicating the number of nodes
; and number of substreams, respectively, for each substream in a
; depth-first order. The iteration per pair proceeds according to
; - number of nodes: 1 .. remaining_nodes
; - number of substreams: 0 (1) .. (remaining_nodes - number_of nodes)/2
; where 1 is taken if
; - number of nodes is 1 or
; - number of nodes is not remaining_nodes and there are no further.
; The last iteration has thus the number of nodes being the remaining
; nodes

; (horizontal_rec
;		<substream>
;		<nodes to distribute>
;		<index of the substream>)
; =>
;		<same as vertical_rec>

; (vertical_rec
;		<no further nodes after this>
;		<nodes to distribute>
;		<index of the substream>
;		<upstream component of topological factor>)
; =>
;	(list
;		<iterator section downstream>
;		<sum of topological factor in substream>)
;		<nodes to distribute left after>
;		<first unused index after last node downstream>