;;; 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)
          (scheme case-lambda))
  (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
      (case-lambda
        ((n)
         (accel-asc n vector-copy))
        ((n vector->)
         (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 (vector-> a 0 (+ k 2)))
                    (set! x (+ x 1))
                    (set! y (- y 1)))
                  (vector-set! a k (+ x y))
                  (set! y (+ x y -1))
                  (yield (vector-> a 0 (+ k 1)))))))))))))