spacepaste

Paste details

reply | raw

  1.  
  2. #!/usr/bin/guile
  3. !#
  5. ;; (TreeOptimizer->reset n_nodes) -> unspecified
  6. ;; Restart generation with n_nodes
  7. (define TreeOptimizer->reset #f)
  9. ;; (TreeOptimizer->iterate) -> (topo_factor . specification)
  10. ;; Calculate the topological factor of the next specified iteration
  11. (define TreeOptimizer->iterate #f)
  13. (let ([iterator (list)] [n_nodes #f])
  14. (set! TreeOptimizer->reset
  15. (lambda (n_nodes_new)
  16. (set! iterator (list))
  17. (set! n_nodes n_nodes_new)))
  18. (set! TreeOptimizer->iterate
  19. (lambda ()
  20. (let vertical_rec ([last_node #t] [remaining_nodes n_nodes] [index 0] [tf 0])
  21. (let ([trailing (= (+ (length iterator) 1) index)])
  22. (let ([stage (if (<= (length iterator) index)
  23. '(1 . 1)
  24. (list-ref iterator index))])
  25. (if (and trailing (= (car stage) remaining_nodes))
  26. ; Break recursion. Must only happen on last_node
  27. (list (list) 0 remaining_nodes index)
  28. (let ([stage (if trailing
  29. (let ([max_substream (remainder (- remaining_nodes (car stage)) 2)])
  30. (if (= (cdr stage) max_substream)
  31. (let ([new_nodecount (+ (car stage) 1)])
  32. (cons new_nodecount (if (and last_node (not (= new_nodecount remaining_nodes))) 1 0))
  33. (cons (car stage) (+ (cdr stage) 1))))
  34. stage))])
  35. (let ([horizontal_result (let horizontal_rec
  36. ([substream 0]
  37. [remaining_nodes remaining_nodes]
  38. [subindex (+ index 1)])
  39. (if (< substream (cdr stage))
  40. (let ([vertical_result (vertical_rec
  41. (and last_node (= substream (- (cdr stage) 1)))
  42. remaining_nodes
  43. subindex
  44. (+ tf (cdr stage) (car stage)))])
  45. (let ([vertical_result (horizontal_rec (+ substream 1) (list-ref vertical_result 2) (list-ref vertical_result 3))])
  46. (list
  47. (append (list-ref vertical_result 0) (list-ref horizontal_result 0))
  48. (+ (list-ref vertical_result 1) (list-ref horizontal_result 1))
  49. (list-ref horizontal_result 2)
  50. (list-ref horizontal_result 3))))
  51. (list (list) 0 remaining_nodes subindex)))])
  52. (list
  53. (append (list stage) (list-ref horizontal_result 0))
  54. (* tf (car stage))
  55. (list-ref horizontal_result 2)
  56. (list-ref horizontal_result 3)))))))))))
  58. (TreeOptimizer->reset 4)
  59. (TreeOptimizer->iterate)
  61. ; The iterator is a list of pairs each indicating the number of nodes
  62. ; and number of substreams, respectively, for each substream in a
  63. ; depth-first order. The iteration per pair proceeds according to
  64. ; - number of nodes: 1 .. remaining_nodes
  65. ; - number of substreams: 0 (1) .. (remaining_nodes - number_of nodes)/2
  66. ; where 1 is taken if
  67. ; - number of nodes is 1 or
  68. ; - number of nodes is not remaining_nodes and there are no further.
  69. ; The last iteration has thus the number of nodes being the remaining
  70. ; nodes
  72. ; (horizontal_rec
  73. ; <substream>
  74. ; <nodes to distribute>
  75. ; <index of the substream>)
  76. ; =>
  77. ; <same as vertical_rec>
  79. ; (vertical_rec
  80. ; <no further nodes after this>
  81. ; <nodes to distribute>
  82. ; <index of the substream>
  83. ; <upstream component of topological factor>)
  84. ; =>
  85. ; (list
  86. ; <iterator section downstream>
  87. ; <sum of topological factor in substream>)
  88. ; <nodes to distribute left after>
  89. ; <first unused index after last node downstream>
  90.  
Powered by spacepaste. Paste removal.