;;;; srfi-1.test --- Test suite for Guile's SRFI-1 functions. -*- scheme -*-
;;;;
;;;; Copyright 2003, 2004 Free Software Foundation, Inc.
;;;;
;;;; 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, 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 software; see the file COPYING.  If not, write to
;;;; the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
;;;; Boston, MA 02111-1307 USA
;;;;
;;;; As a special exception, the Free Software Foundation gives permission
;;;; for additional uses of the text contained in its release of GUILE.
;;;;
;;;; The exception is that, if you link the GUILE library with other files
;;;; to produce an executable, this does not by itself cause the
;;;; resulting executable to be covered by the GNU General Public License.
;;;; Your use of that executable is in no way restricted on account of
;;;; linking the GUILE library code into it.
;;;;
;;;; This exception does not however invalidate any other reasons why
;;;; the executable file might be covered by the GNU General Public License.
;;;;
;;;; This exception applies only to the code released by the
;;;; Free Software Foundation under the name GUILE.  If you copy
;;;; code from other Free Software Foundation releases into a copy of
;;;; GUILE, as the General Public License permits, the exception does
;;;; not apply to the code that you add in this way.  To avoid misleading
;;;; anyone as to the status of such modified files, you must delete
;;;; this exception notice from them.
;;;;
;;;; If you write modifications of your own for GUILE, it is your choice
;;;; whether to permit this exception to apply to your modifications.
;;;; If you do not wish that, delete this exception notice.  

(use-modules (srfi srfi-1)
	     (test-suite lib))

(define (ref-delete x lst . proc)
  "Reference implemenation of srfi-1 `delete'."
  (set! proc (if (null? proc) equal? (car proc)))
  (do ((ret '())
       (lst lst (cdr lst)))
      ((null? lst)
       (reverse! ret))
    (if (not (proc x (car lst)))
	(set! ret (cons (car lst) ret)))))

(define (ref-delete-duplicates lst . proc)
  "Reference implemenation of srfi-1 `delete-duplicates'."
  (set! proc (if (null? proc) equal? (car proc)))
  (if (null? lst)
      '()
      (do ((keep '()))
	  ((null? lst)
	   (reverse! keep))
	(let ((elem (car lst)))
	  (set! keep (cons elem keep))
	  (set! lst  (ref-delete elem lst proc))))))

;;
;; alist-copy
;;

(with-test-prefix "alist-copy"

  ;; return a list which is the pairs making up alist A, the spine and cells
  (define (alist-pairs a)
    (let more ((a a)
	       (result a))
      (if (pair? a)
	  (more (cdr a) (cons a result))
	  result)))

  ;; return a list of the elements common to lists X and Y, compared with eq?
  (define (common-elements x y)
    (if (null? x)
	'()
	(if (memq (car x) y)
	    (cons (car x) (common-elements (cdr x) y))
	    (common-elements (cdr x) y))))

  ;; validate an alist-copy of OLD to NEW
  ;; lists must be equal, and must comprise new pairs
  (define (valid-alist-copy? old new)
    (and (equal? old new)
	 (null? (common-elements old new))))

  (pass-if-exception "too few args" exception:wrong-num-args
    (alist-copy))
    
  (pass-if-exception "too many args" exception:wrong-num-args
    (alist-copy '() '()))
    
  (let ((old '()))
    (pass-if old (valid-alist-copy? old (alist-copy old))))

  (let ((old '((1 . 2))))
    (pass-if old (valid-alist-copy? old (alist-copy old))))

  (let ((old '((1 . 2) (3 . 4))))
    (pass-if old (valid-alist-copy? old (alist-copy old))))

  (let ((old '((1 . 2) (3 . 4) (5 . 6))))
    (pass-if old (valid-alist-copy? old (alist-copy old)))))

;;
;; alist-delete
;;

(with-test-prefix "alist-delete"

  (pass-if "equality call arg order"
    (let ((good #f))
      (alist-delete 'k '((ak . 123))
		    (lambda (k ak)
		      (if (and (eq? k 'k) (eq? ak 'ak))
			  (set! good #t))))
      good))

  (pass-if "delete keys greater than 5"
    (equal? '((4 . x) (5 . y))
	    (alist-delete 5 '((4 . x) (5 . y) (6 . z)) <)))

  (pass-if "empty"
    (equal? '() (alist-delete 'x '())))

  (pass-if "(y)"
    (equal? '() (alist-delete 'y '((y . 1)))))

  (pass-if "(n)"
    (equal? '((n . 1)) (alist-delete 'y '((n . 1)))))

  (pass-if "(y y)"
    (equal? '() (alist-delete 'y '((y . 1) (y . 2)))))

  (pass-if "(n y)"
    (equal? '((n . 1)) (alist-delete 'y '((n . 1) (y . 2)))))

  (pass-if "(y n)"
    (equal? '((n . 2)) (alist-delete 'y '((y . 1) (n . 2)))))

  (pass-if "(n n)"
    (equal? '((n . 1) (n . 2)) (alist-delete 'y '((n . 1) (n . 2)))))

  (pass-if "(y y y)"
    (equal? '() (alist-delete 'y '((y . 1) (y . 2) (y . 3)))))

  (pass-if "(n y y)"
    (equal? '((n . 1)) (alist-delete 'y '((n . 1) (y . 2) (y . 3)))))

  (pass-if "(y n y)"
    (equal? '((n . 2)) (alist-delete 'y '((y . 1) (n . 2) (y . 3)))))

  (pass-if "(n n y)"
    (equal? '((n . 1) (n . 2)) (alist-delete 'y '((n . 1) (n . 2) (y . 3)))))

  (pass-if "(y y n)"
    (equal? '( (n . 3)) (alist-delete 'y '((y . 1) (y . 2) (n . 3)))))

  (pass-if "(n y n)"
    (equal? '((n . 1) (n . 3)) (alist-delete 'y '((n . 1) (y . 2) (n . 3)))))

  (pass-if "(y n n)"
    (equal? '((n . 2) (n . 3)) (alist-delete 'y '((y . 1) (n . 2) (n . 3)))))

  (pass-if "(n n n)"
    (equal? '((n . 1) (n . 2) (n . 3)) (alist-delete 'y '((n . 1) (n . 2) (n . 3))))))

;;
;; append-map
;;

(with-test-prefix "append-map"

  (with-test-prefix "one list"

    (pass-if "()"
      (equal? '() (append-map noop '(()))))

    (pass-if "(1)"
      (equal? '(1) (append-map noop '((1)))))

    (pass-if "(1 2)"
      (equal? '(1 2) (append-map noop '((1 2)))))

    (pass-if "() ()"
      (equal? '() (append-map noop '(() ()))))

    (pass-if "() (1)"
      (equal? '(1) (append-map noop '(() (1)))))

    (pass-if "() (1 2)"
      (equal? '(1 2) (append-map noop '(() (1 2)))))

    (pass-if "(1) (2)"
      (equal? '(1 2) (append-map noop '((1) (2)))))

    (pass-if "(1 2) ()"
      (equal? '(1 2) (append-map noop '(() (1 2))))))

  (with-test-prefix "two lists"

    (pass-if "() / 9"
      (equal? '() (append-map noop '(()) '(9))))

    (pass-if "(1) / 9"
      (equal? '(1) (append-map noop '((1)) '(9))))

    (pass-if "() () / 9 9"
      (equal? '() (append-map noop '(() ()) '(9 9))))

    (pass-if "(1) (2) / 9"
      (equal? '(1) (append-map noop '((1) (2)) '(9))))

    (pass-if "(1) (2) / 9 9"
      (equal? '(1 2) (append-map noop '((1) (2)) '(9 9))))))
  
;;
;; break
;;

(with-test-prefix "break"

  (define (test-break lst want-v1 want-v2)
    (call-with-values
	(lambda ()
	  (break negative? lst))
      (lambda (got-v1 got-v2)
	(and (equal? got-v1 want-v1)
	     (equal? got-v2 want-v2)))))

  (pass-if "empty"
    (test-break '() '() '()))

  (pass-if "y"
    (test-break '(1) '(1) '()))

  (pass-if "n"
    (test-break '(-1) '() '(-1)))

  (pass-if "yy"
    (test-break '(1 2) '(1 2) '()))

  (pass-if "ny"
    (test-break '(-1 1) '() '(-1 1)))

  (pass-if "yn"
    (test-break '(1 -1) '(1) '(-1)))

  (pass-if "nn"
    (test-break '(-1 -2) '() '(-1 -2)))

  (pass-if "yyy"
    (test-break '(1 2 3) '(1 2 3) '()))

  (pass-if "nyy"
    (test-break '(-1 1 2) '() '(-1 1 2)))

  (pass-if "yny"
    (test-break '(1 -1 2) '(1) '(-1 2)))

  (pass-if "nny"
    (test-break '(-1 -2 1) '() '(-1 -2 1)))

  (pass-if "yyn"
    (test-break '(1 2 -1) '(1 2) '(-1)))

  (pass-if "nyn"
    (test-break '(-1 1 -2) '() '(-1 1 -2)))

  (pass-if "ynn"
    (test-break '(1 -1 -2) '(1) '(-1 -2)))

  (pass-if "nnn"
    (test-break '(-1 -2 -3) '() '(-1 -2 -3))))

;;
;; count
;;

(with-test-prefix "count"
  (pass-if-exception "no args" exception:wrong-num-args
    (count))
  
  (pass-if-exception "one arg" exception:wrong-num-args
    (count noop))
  
  (with-test-prefix "one list"
    (define (or1 x)
      x)
    
    (pass-if "empty list" (= 0 (count or1 '())))
    
    (pass-if-exception "pred arg count 0" exception:wrong-num-args
      (count (lambda () x) '(1 2 3)))
    (pass-if-exception "pred arg count 2" exception:wrong-num-args
      (count (lambda (x y) x) '(1 2 3)))
    
    (pass-if-exception "improper 1" exception:wrong-type-arg
      (count or1 1))
    (pass-if-exception "improper 2" exception:wrong-type-arg
      (count or1 '(1 . 2)))
    (pass-if-exception "improper 3" exception:wrong-type-arg
      (count or1 '(1 2 . 3)))
    
    (pass-if "" (= 0 (count or1 '(#f))))
    (pass-if "" (= 1 (count or1 '(#t))))
    
    (pass-if "" (= 0 (count or1 '(#f #f))))
    (pass-if "" (= 1 (count or1 '(#f #t))))
    (pass-if "" (= 1 (count or1 '(#t #f))))
    (pass-if "" (= 2 (count or1 '(#t #t))))
    
    (pass-if "" (= 0 (count or1 '(#f #f #f))))
    (pass-if "" (= 1 (count or1 '(#f #f #t))))
    (pass-if "" (= 1 (count or1 '(#t #f #f))))
    (pass-if "" (= 2 (count or1 '(#t #f #t))))
    (pass-if "" (= 3 (count or1 '(#t #t #t)))))
  
  (with-test-prefix "two lists"
    (define (or2 x y)
      (or x y))
    
    (pass-if "arg order"
      (= 1 (count (lambda (x y)
		    (and (= 1 x)
			 (= 2 y)))
		  '(1) '(2))))
    
    (pass-if "empty lists" (= 0 (count or2 '() '())))
    
    (pass-if-exception "pred arg count 0" exception:wrong-num-args
      (count (lambda () #t) '(1 2 3) '(1 2 3)))
    (pass-if-exception "pred arg count 1" exception:wrong-num-args
      (count (lambda (x) x) '(1 2 3) '(1 2 3)))
    (pass-if-exception "pred arg count 3" exception:wrong-num-args
      (count (lambda (x y z) x) '(1 2 3) '(1 2 3)))
    
    (pass-if-exception "improper first 1" exception:wrong-type-arg
      (count or2 1 '(1 2 3)))
    (pass-if-exception "improper first 2" exception:wrong-type-arg
      (count or2 '(1 . 2) '(1 2 3)))
    (pass-if-exception "improper first 3" exception:wrong-type-arg
      (count or2 '(1 2 . 3) '(1 2 3)))
    
    (pass-if-exception "improper second 1" exception:wrong-type-arg
      (count or2 '(1 2 3) 1))
    (pass-if-exception "improper second 2" exception:wrong-type-arg
      (count or2 '(1 2 3) '(1 . 2)))
    (pass-if-exception "improper second 3" exception:wrong-type-arg
      (count or2 '(1 2 3) '(1 2 . 3)))
    
    (pass-if "" (= 0 (count or2 '(#f) '(#f))))
    (pass-if "" (= 1 (count or2 '(#t) '(#f))))
    (pass-if "" (= 1 (count or2 '(#f) '(#t))))
    
    (pass-if "" (= 0 (count or2 '(#f #f) '(#f #f))))
    (pass-if "" (= 1 (count or2 '(#t #f) '(#t #f))))
    (pass-if "" (= 2 (count or2 '(#t #t) '(#f #f))))
    (pass-if "" (= 2 (count or2 '(#t #f) '(#f #t))))
    
    (with-test-prefix "stop shortest"
      (pass-if "" (= 2 (count or2 '(#t #f #t) '(#f #t))))
      (pass-if "" (= 2 (count or2 '(#t #f #t #t) '(#f #t))))
      (pass-if "" (= 2 (count or2 '(#t #f) '(#f #t #t))))
      (pass-if "" (= 2 (count or2 '(#t #f) '(#f #t #t #t))))))
  
  (with-test-prefix "three lists"
    (define (or3 x y z)
      (or x y z))
    
    (pass-if "arg order"
      (= 1 (count (lambda (x y z)
		    (and (= 1 x)
			 (= 2 y)
			 (= 3 z)))
		  '(1) '(2) '(3))))
    
    (pass-if "empty lists" (= 0 (count or3 '() '() '())))
    
    ;; currently bad pred argument gives wrong-num-args when 3 or more
    ;; lists, as opposed to wrong-type-arg for 1 or 2 lists
    (pass-if-exception "pred arg count 0" exception:wrong-num-args
      (count (lambda () #t) '(1 2 3) '(1 2 3) '(1 2 3)))
    (pass-if-exception "pred arg count 2" exception:wrong-num-args
      (count (lambda (x y) x) '(1 2 3) '(1 2 3)'(1 2 3) ))
    (pass-if-exception "pred arg count 4" exception:wrong-num-args
      (count (lambda (w x y z) x) '(1 2 3) '(1 2 3) '(1 2 3)))
    
    (pass-if-exception "improper first 1" exception:wrong-type-arg
      (count or3 1 '(1 2 3) '(1 2 3)))
    (pass-if-exception "improper first 2" exception:wrong-type-arg
      (count or3 '(1 . 2) '(1 2 3) '(1 2 3)))
    (pass-if-exception "improper first 3" exception:wrong-type-arg
      (count or3 '(1 2 . 3) '(1 2 3) '(1 2 3)))
    
    (pass-if-exception "improper second 1" exception:wrong-type-arg
      (count or3 '(1 2 3) 1 '(1 2 3)))
    (pass-if-exception "improper second 2" exception:wrong-type-arg
      (count or3 '(1 2 3) '(1 . 2) '(1 2 3)))
    (pass-if-exception "improper second 3" exception:wrong-type-arg
      (count or3 '(1 2 3) '(1 2 . 3) '(1 2 3)))
    
    (pass-if-exception "improper third 1" exception:wrong-type-arg
      (count or3 '(1 2 3) '(1 2 3) 1))
    (pass-if-exception "improper third 2" exception:wrong-type-arg
      (count or3 '(1 2 3) '(1 2 3) '(1 . 2)))
    (pass-if-exception "improper third 3" exception:wrong-type-arg
      (count or3 '(1 2 3) '(1 2 3) '(1 2 . 3)))
    
    (pass-if "" (= 0 (count or3 '(#f) '(#f) '(#f))))
    (pass-if "" (= 1 (count or3 '(#t) '(#f) '(#f))))
    (pass-if "" (= 1 (count or3 '(#f) '(#t) '(#f))))
    (pass-if "" (= 1 (count or3 '(#f) '(#f) '(#t))))
    
    (pass-if "" (= 0 (count or3 '(#f #f) '(#f #f) '(#f #f))))
    
    (pass-if "" (= 1 (count or3 '(#t #f) '(#f #f) '(#f #f))))
    (pass-if "" (= 1 (count or3 '(#f #t) '(#f #f) '(#f #f))))
    (pass-if "" (= 1 (count or3 '(#f #f) '(#t #f) '(#f #f))))
    (pass-if "" (= 1 (count or3 '(#f #f) '(#f #t) '(#f #f))))
    (pass-if "" (= 1 (count or3 '(#f #f) '(#f #f) '(#t #f))))
    (pass-if "" (= 1 (count or3 '(#f #f) '(#f #f) '(#f #t))))
    
    (pass-if "" (= 2 (count or3 '(#t #t) '(#f #f) '(#f #f))))
    (pass-if "" (= 2 (count or3 '(#f #f) '(#t #t) '(#f #f))))
    (pass-if "" (= 2 (count or3 '(#f #f) '(#f #f) '(#t #t))))
    (pass-if "" (= 2 (count or3 '(#f #f) '(#t #f) '(#f #t))))
    
    (with-test-prefix "stop shortest"
      (pass-if "" (= 0 (count or3 '() '(#t #t #t) '(#t #t))))
      (pass-if "" (= 0 (count or3 '(#t #t #t) '() '(#t #t))))
      (pass-if "" (= 0 (count or3 '(#t #t #t) '(#t #t) '())))
      
      (pass-if "" (= 1 (count or3 '(#t) '(#t #t #t) '(#t #t))))
      (pass-if "" (= 1 (count or3 '(#t #t #t) '(#t) '(#t #t))))
      (pass-if "" (= 1 (count or3 '(#t #t #t) '(#t #t) '(#t)))))))

;;
;; delete and delete!
;;

(let ()	
  ;; Call (PROC lst) for all lists of length up to 6, with all combinations
  ;; of elements to be retained or deleted.  Elements to retain are numbers,
  ;; 0 upwards.  Elements to be deleted are #f.
  (define (test-lists proc)
    (do ((n 0 (1+ n)))
	((>= n 6))
      (do ((limit (ash 1 n))
	   (i 0 (1+ i)))
	  ((>= i limit))
	(let ((lst '()))
	  (do ((bit 0 (1+ bit)))
	      ((>= bit n))
	    (set! lst  (cons (if (logbit? bit i) bit #f) lst)))
	  (proc lst)))))
  
  (define (common-tests delete-proc)
    (pass-if-exception "too few args" exception:wrong-num-args
      (delete-proc 0))
    
    (pass-if "empty"
      (eq? '() (delete-proc 0 '())))
    
    (pass-if "equal? (the default)"
      (equal? '((1) (3))
	      (delete-proc '(2) '((1) (2) (3)))))
    
    (pass-if "eq?"
      (equal? '((1) (2) (3))
	      (delete-proc '(2) '((1) (2) (3)) eq?)))
    
    (pass-if "called arg order"
      (equal? '(1 2 3)
	      (delete-proc 3 '(1 2 3 4 5) <))))
  
  (with-test-prefix "delete"
    (common-tests delete)
    
    (test-lists
     (lambda (lst)
       (let ((lst-copy (list-copy lst)))
	 (with-test-prefix lst-copy
	   (pass-if "result"
	     (equal? (delete     #f lst)
		     (ref-delete #f lst)))
	   (pass-if "non-destructive"
	     (equal? lst-copy lst)))))))  
  
  (with-test-prefix "delete!"
    (common-tests delete!)
    
    (test-lists
     (lambda (lst)
       (pass-if lst
	 (equal? (delete!    #f lst)
		 (ref-delete #f lst)))))))

;;
;; delete-duplicates and delete-duplicates!
;;

(let ()	
  ;; Call (PROC lst) for all lists of length 1 <= n <= 4, with all
  ;; combinations of numbers 1 to n in the elements
  (define (test-lists proc)
    (do ((n 1 (1+ n)))
	((> n 4))
      (do ((limit (integer-expt n n))
	   (i 0 (1+ i)))
	  ((>= i limit))
	(let ((lst '()))
	  (do ((j 0 (1+ j))
	       (rem i (quotient rem n)))
	      ((>= j n))
	    (set! lst (cons (remainder rem n) lst)))
	  (proc lst)))))

  (define (common-tests delete-duplicates-proc)
    (pass-if-exception "too few args" exception:wrong-num-args
      (delete-duplicates-proc))
    
    (pass-if "empty"
      (eq? '() (delete-duplicates-proc '())))
    
    (pass-if "equal? (the default)"
      (equal? '((2))
	      (delete-duplicates-proc '((2) (2) (2)))))
    
    (pass-if "eq?"
      (equal? '((2) (2) (2))
	      (delete-duplicates-proc '((2) (2) (2)) eq?)))

    (pass-if "called arg order"
      (let ((ok #t))
	(delete-duplicates-proc '(1 2 3 4 5)
				(lambda (x y)
				  (if (> x y)
				      (set! ok #f))
				  #f))
	ok)))
  
  (with-test-prefix "delete-duplicates"
    (common-tests delete-duplicates)
    
    (test-lists
     (lambda (lst)
       (let ((lst-copy (list-copy lst)))
	 (with-test-prefix lst-copy
	   (pass-if "result"
	     (equal? (delete-duplicates     lst)
		     (ref-delete-duplicates lst)))
	   (pass-if "non-destructive"
	     (equal? lst-copy lst)))))))  
  
  (with-test-prefix "delete-duplicates!"
    (common-tests delete-duplicates!)
    
    (test-lists
     (lambda (lst)
       (pass-if lst
	 (equal? (delete-duplicates!    lst)
		 (ref-delete-duplicates lst)))))))

;;
;; filter-map
;;

(with-test-prefix "filter-map"

  (with-test-prefix "one list"
    (pass-if "(1)"
      (equal? '(1) (filter-map noop '(1))))

    (pass-if "(#f)"
      (equal? '() (filter-map noop '(#f))))

    (pass-if "(1 2)"
      (equal? '(1 2) (filter-map noop '(1 2))))

    (pass-if "(#f 2)"
      (equal? '(2) (filter-map noop '(#f 2))))

    (pass-if "(#f #f)"
      (equal? '() (filter-map noop '(#f #f))))

    (pass-if "(1 2 3)"
      (equal? '(1 2 3) (filter-map noop '(1 2 3))))

    (pass-if "(#f 2 3)"
      (equal? '(2 3) (filter-map noop '(#f 2 3))))

    (pass-if "(1 #f 3)"
      (equal? '(1 3) (filter-map noop '(1 #f 3))))

    (pass-if "(1 2 #f)"
      (equal? '(1 2) (filter-map noop '(1 2 #f)))))

  (with-test-prefix "two lists"
    (pass-if "(1 2 3) (4 5 6)"
      (equal? '(1 2 3) (filter-map noop '(1 2 3) '(4 5 6))))

    (pass-if "(#f 2 3) (4 5)"
      (equal? '(2) (filter-map noop '(#f 2 3) '(4 5))))

    (pass-if "(4 #f) (1 2 3)"
      (equal? '(4) (filter-map noop '(4 #f) '(1 2 3))))))
  
;;
;; list-copy
;;

(with-test-prefix "list-copy"
  
  ;; improper lists can be copied
  (pass-if "empty" (equal? '()          (list-copy '())))
  (pass-if "one"   (equal? '(1)         (list-copy '(1))))
  (pass-if "two"   (equal? '(1 2)       (list-copy '(1 2))))
  (pass-if "three" (equal? '(1 2 3)     (list-copy '(1 2 3))))
  (pass-if "four"  (equal? '(1 2 3 4)   (list-copy '(1 2 3 4))))
  (pass-if "five"  (equal? '(1 2 3 4 5) (list-copy '(1 2 3 4 5))))
  
  ;; improper lists can be copied
  (pass-if "one   improper" (equal? 1              (list-copy 1)))
  (pass-if "two   improper" (equal? '(1 . 2)       (list-copy '(1 . 2))))
  (pass-if "three improper" (equal? '(1 2 . 3)     (list-copy '(1 2 . 3))))
  (pass-if "four  improper" (equal? '(1 2 3 . 4)   (list-copy '(1 2 3 . 4))))
  (pass-if "five  improper" (equal? '(1 2 3 4 . 5) (list-copy '(1 2 3 4 . 5)))))

;;
;; map
;;

(with-test-prefix "map"

  (with-test-prefix "two lists"

    (pass-if "empty / empty"
      (equal? '() (map + '() '())))

    (pass-if "empty / (1)"
      (equal? '() (map + '() '(1))))

    (pass-if "empty / (1 2)"
      (equal? '() (map + '() '(1 2))))

    (pass-if "(1) / empty"
      (equal? '() (map + '(1) '())))

    (pass-if "(1) / (2)"
      (equal? '(3) (map + '(1) '(2))))

    (pass-if "(1) / (2 3)"
      (equal? '(3) (map + '(1) '(2 3))))

    (pass-if "(1 2) / empty"
      (equal? '() (map + '(1 2) '())))

    (pass-if "(1 2) / (3)"
      (equal? '(4) (map + '(1 2) '(3))))

    (pass-if "(1 2) / (3 4)"
      (equal? '(4 6) (map + '(1 2) '(3 4)))))

  (with-test-prefix "three lists"

    (pass-if "empty / empty / empty"
      (equal? '() (map + '() '() '())))

    (pass-if "(1) / (2) / ()"
      (equal? '() (map + '(1) '(2) '())))

    (pass-if "(1) / (2) / (3)"
      (equal? '(6) (map + '(1) '(2) '(3))))

    (pass-if "(1 2) / (3 4) / (5 6)"
      (equal? '(9 12) (map + '(1 2) '(3 4) '(5 6))))))

;;
;; map!
;;

(with-test-prefix "map!"

  (pass-if-exception "no args" exception:wrong-num-args
    (map!))
  
  (pass-if-exception "no lists" exception:wrong-num-args
    (map! 1+))

  (with-test-prefix "one list"

    (pass-if "empty"
      (equal? '() (map! 1+ (list))))

    (pass-if "(1)"
      (equal? '(2) (map! 1+ (list 1))))

    (pass-if "(1 2)"
      (equal? '(2 3) (map! 1+ (list 1 2)))))

  (with-test-prefix "two lists"

    (pass-if "empty / empty"
      (equal? '() (map! + (list) (list))))

    (pass-if "empty / (1)"
      (equal? '() (map! + (list) (list 1))))

    (pass-if "empty / (1 2)"
      (equal? '() (map! + (list) (list 1 2))))

    (pass-if "(1) / empty"
      (equal? '() (map! + (list 1) (list))))

    (pass-if "(1) / (2)"
      (equal? '(3) (map! + (list 1) (list 2))))

    (pass-if "(1) / (2 3)"
      (equal? '(3) (map! + (list 1) (list 2 3))))

    (pass-if "(1 2) / empty"
      (equal? '() (map! + (list 1 2) (list))))

    (pass-if "(1 2) / (3)"
      (equal? '(4) (map! + (list 1 2) (list 3))))

    (pass-if "(1 2) / (3 4)"
      (equal? '(4 6) (map! + (list 1 2) (list 3 4)))))

  (with-test-prefix "three lists"

    (pass-if "empty / empty / empty"
      (equal? '() (map! + (list) (list) (list))))

    (pass-if "(1) / (2) / ()"
      (equal? '() (map! + (list 1) (list 2) (list))))

    (pass-if "(1) / (2) / (3)"
      (equal? '(6) (map! + (list 1) (list 2) (list 3))))

    (pass-if "(1 2) / (3 4) / (5 6)"
      (equal? '(9 12) (map! + (list 1 2) (list 3 4) (list 5 6))))))

;;
;; partition
;;

(define (test-partition pred list kept-good dropped-good)
  (call-with-values (lambda ()
			(partition pred list))
      (lambda (kept dropped)
	(and (equal? kept kept-good)
	     (equal? dropped dropped-good)))))

(with-test-prefix "partition"
		  
  (pass-if "with dropped tail"
    (test-partition even? '(1 2 3 4 5 6 7)
		    '(2 4 6) '(1 3 5 7)))

  (pass-if "with kept tail"
    (test-partition even? '(1 2 3 4 5 6)
		    '(2 4 6) '(1 3 5)))

  (pass-if "with everything dropped"
    (test-partition even? '(1 3 5 7)
		    '() '(1 3 5 7)))

  (pass-if "with everything kept"
    (test-partition even? '(2 4 6)
		    '(2 4 6) '()))

  (pass-if "with empty list"
    (test-partition even? '()
		    '() '()))

  (pass-if "with reasonably long list"
    ;; the old implementation from SRFI-1 reference implementation
    ;; would signal a stack-overflow for a list of only 500 elements!
    (call-with-values (lambda ()
			(partition even?
				   (make-list 10000 1)))
      (lambda (even odd)
	(and (= (length odd) 10000)
	     (= (length even) 0))))))

;;
;; span
;;

(with-test-prefix "span"

  (define (test-span lst want-v1 want-v2)
    (call-with-values
	(lambda ()
	  (span positive? lst))
      (lambda (got-v1 got-v2)
	(and (equal? got-v1 want-v1)
	     (equal? got-v2 want-v2)))))

  (pass-if "empty"
    (test-span '() '() '()))

  (pass-if "y"
    (test-span '(1) '(1) '()))

  (pass-if "n"
    (test-span '(-1) '() '(-1)))

  (pass-if "yy"
    (test-span '(1 2) '(1 2) '()))

  (pass-if "ny"
    (test-span '(-1 1) '() '(-1 1)))

  (pass-if "yn"
    (test-span '(1 -1) '(1) '(-1)))

  (pass-if "nn"
    (test-span '(-1 -2) '() '(-1 -2)))

  (pass-if "yyy"
    (test-span '(1 2 3) '(1 2 3) '()))

  (pass-if "nyy"
    (test-span '(-1 1 2) '() '(-1 1 2)))

  (pass-if "yny"
    (test-span '(1 -1 2) '(1) '(-1 2)))

  (pass-if "nny"
    (test-span '(-1 -2 1) '() '(-1 -2 1)))

  (pass-if "yyn"
    (test-span '(1 2 -1) '(1 2) '(-1)))

  (pass-if "nyn"
    (test-span '(-1 1 -2) '() '(-1 1 -2)))

  (pass-if "ynn"
    (test-span '(1 -1 -2) '(1) '(-1 -2)))

  (pass-if "nnn"
    (test-span '(-1 -2 -3) '() '(-1 -2 -3))))