#lang typed/racket/base
(provide partitions reset-partitions-cache)
(require math/private/vector/vector
         math/private/number-theory/types)

;;; Partitions are computed using Euler's algorithm:

;                k            k(3k+1)              k(3k-1)
; p(n) = sum (-1)   [ p( n - --------- ) + p( n - --------- ) ]
;        k>=1                    2                    2

; http://en.wikipedia.org/wiki/Partition_(number_theory)

(define cache-size 1)
(: cache (Vectorof Integer))
(define cache (make-vector cache-size 0))
(vector-set! cache 0 1)

(: reset-partitions-cache : -> Void)
(define (reset-partitions-cache)
  (set! cache-size 1)
  (make-vector cache-size 0)
  (set! cache (make-vector cache-size 0))
  (vector-set! cache 0 1))

(: grow-cache : Natural -> Void)
(define (grow-cache n)
  (cond [(> cache-size n) (void)]
        [else (define n+1 (+ n 1))
              (define new-cache (make-vector n+1 0))
              (vector-copy! new-cache 0 cache)
              (set! cache-size n+1)
              (set! cache new-cache)]))

(: ref! (Integer (-> Integer) -> Integer))
(define (ref! n thnk)
  (vector-ref! cache n thnk exact-zero?))

(: partitions : Integer -> Integer)
(define (partitions n)
  (cond [(< n 0) 0]
        [else    
         (grow-cache n)
         (: p : Integer -> Integer)
         (define (p n)
           (ref! n (λ ()
                     (: loop1 : Integer Integer Integer -> Integer)
                     (define (loop1 k m s)
                       (cond [(< m 0) s]
                             [else (loop1 (+ k 1) (- m (+ (* 3 k) 1)) 
                                          (if (odd? k) (+ s (p m)) (- s (p m))))]))
                     (: loop2 : Integer Integer Integer -> Integer)
                     (define (loop2 k m s)
                       (cond [(< m 0) s]
                             [else   (loop2 (- k 1) 
                                            (+ m (* 3 k) -2) 
                                            (if (odd? k) (+ s (p m)) (- s (p m))))]))
                     (+ (loop1  1 (- n 1) 0)
                        (loop2 -1 (- n 2) 0)))))
         (p n)]))

/home/stchang/racket/pasterack/tmp/16085/16085code.scrbl:5:27: module: identifier already imported for label from: (all-except typed/racket #%mo...
  at: cast
  in: math/private/number-theory/types
  context...:
   standard-module-name-resolver
   /home/stchang/plt601/pkgs/scribble-pkgs/scribble-lib/scribble/run.rkt:133:24
   /home/stchang/plt601/pkgs/scribble-pkgs/scribble-lib/scribble/run.rkt: [running body]