;;; Copyright 2024 Masaya Tojo <masaya@tojo.tokyo>
;;;
;;; Licensed under the Apache License, Version 2.0 (the "License");
;;; you may not use this file except in compliance with the License.
;;; You may obtain a copy of the License at
;;;
;;;     http://www.apache.org/licenses/LICENSE-2.0
;;;
;;; Unless required by applicable law or agreed to in writing, software
;;; distributed under the License is distributed on an "AS IS" BASIS,
;;; WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
;;; See the License for the specific language governing permissions and
;;; limitations under the License.

(define-library (integer-partition accel-asc)
  (export accel-asc)
  (import (scheme base))
  (cond-expand
    ((library (scheme generator))
     (import (only (scheme generator) make-coroutine-generator)))
    ((library (srfi 158))
     (import (only (srfi 158) make-coroutine-generator))))
  (begin
    (define-syntax while
      (syntax-rules ()
        ((_ condition body body* ...)
         (let loop ()
           (if condition
               (begin
                 body
                 body* ...
                 (loop))
               (if #f #f)))))))
  (begin
    ;; This is a Scheme implementation of Jerome Kelleher's algorithm for generating integer paritions.
    ;; See: https://jeromekelleher.net/category/combinatorics.html
    (define (accel-asc n)
      (accel-asc* n vector-copy))

    (define (accel-asc* n convert)
      (make-coroutine-generator
       (lambda (yield)
         (let ((a (make-vector (+ n 1) 0))
               (k 1)
               (x 0)
               (y (- n 1)))
           (while (not (= k 0))
             (set! x (+ (vector-ref a (- k 1)) 1))
             (set! k (- k 1))
             (while (<= (* 2 x) y)
               (vector-set! a k x)
               (set! y (- y x))
               (set! k (+ k 1)))
             (let ((l (+ k 1)))
               (while (<= x y)
                 (vector-set! a k x)
                 (vector-set! a l y)
                 (yield (convert a 0 (+ k 2)))
                 (set! x (+ x 1))
                 (set! y (- y 1)))
               (vector-set! a k (+ x y))
               (set! y (+ x y -1))
               (yield (convert a 0 (+ k 1)))))))))
    ))