;    Copyright (C) 2006  Will M. Farr <farr@mit.edu>
;
;    This program is free software; you can redistribute it and/or modify
;    it under the terms of the GNU General Public License as published by
;    the Free Software Foundation; either version 2 of the License, or
;    (at your option) any later version.
;
;    This program is distributed in the hope that it will be useful,
;    but WITHOUT ANY WARRANTY; without even the implied warranty of
;    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;    GNU General Public License for more details.
;
;    You should have received a copy of the GNU General Public License along
;    with this program; if not, write to the Free Software Foundation, Inc.,
;    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

(module memoization-test mzscheme
  (require "test.ss" "memoization.ss")
  
  (provide memoization-test-suite)
  
  (define memoization-test-suite
    (test-suite
     "memoization.ss test suite"
     (test-case
      "memoize1 works on fib"
      (letrec ((fib (memoize1
                     (lambda (n)
                       (if (<= n 2)
                           1
                           (+ (fib (- n 1))
                              (fib (- n 2))))))))
        (check= (fib 1000)
                43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875)))
     (test-case
      "memoize works on subsets"
      ;; See http://groups.google.com/group/comp.lang.scheme/browse_thread/thread/671474460d3e31d8
      ;; for discussion of the algorithm---it definitely benefits from memoization.
      (letrec ((length-at-least? (lambda (i l)
                                   (cond
                                     ((= i 0) #t)
                                     ((null? l) #f)
                                     (else (length-at-least? (- i 1) (cdr l))))))
               (subsets (memoize
                         (lambda (i s)
                           (cond
                             ((= i 0) '())
                             ((= i 1) (map list s))
                             ((not (length-at-least? i s))
                              '())
                             (else
                              (let ((a (car s))
                                    (rest (cdr s)))
                                (append
                                 (map (lambda (ss)
                                        (cons a ss))
                                      (subsets (- i 1) rest))
                                 (subsets i rest)))))))))
        (check-equal? (subsets 3 '(1 2 3 4))
                      '((1 2 3) (1 2 4) (1 3 4) (2 3 4))))))))