;;;; srfi-1.test --- Test suite for Guile's SRFI-1 functions. -*- scheme -*-
;;;;
;;;; Copyright 2003 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

(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))))))


;;
;; concatenate and concatenate!
;;

(let ()	
  (define (common-tests concatenate-proc unmodified?)
    (define (try lstlst want)
      (let ((lstlst-copy (copy-tree lstlst))
	    (got         (concatenate-proc lstlst)))
	(if unmodified?
	    (if (not (equal? lstlst lstlst-copy))
		(error "input lists modified")))
	(equal? got want)))
    
    (pass-if-exception "too few args" exception:wrong-num-args
      (concatenate-proc))
    
    (pass-if-exception "too many args" exception:wrong-num-args
      (concatenate-proc '() '()))
    
    (pass-if "no lists"
      (try '() '()))
    
    (pass-if (try '((1))       '(1)))
    (pass-if (try '((1 2))     '(1 2)))
    (pass-if (try '(() (1))    '(1)))
    (pass-if (try '(() () (1)) '(1)))
    
    (pass-if (try '((1) (2)) '(1 2)))
    (pass-if (try '(() (1 2)) '(1 2)))
    
    (pass-if (try '((1) 2)           '(1 . 2)))
    (pass-if (try '((1) (2) 3)       '(1 2 . 3)))
    (pass-if (try '((1) (2) (3 . 4)) '(1 2 3 . 4)))
    )
  
  (with-test-prefix "concatenate"
    (common-tests concatenate #t))
  
  (with-test-prefix "concatenate!"
    (common-tests concatenate! #f)))


;;
;; 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-exception "too many args" exception:wrong-num-args
      (delete-proc 0 '() equal? 99))
    
    (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-exception "too many args" exception:wrong-num-args
      (delete-duplicates-proc '() equal? 99))
    
    (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)))))))

;;
;; drop
;;

(with-test-prefix "drop"
  
  (pass-if "'() 0"
    (null? (drop '() 0)))
  
  (pass-if "'(a) 0"
    (let ((lst '(a)))
      (eq? lst
	   (drop lst 0))))
  
  (pass-if "'(a b) 0"
    (let ((lst '(a b)))
      (eq? lst
	   (drop lst 0))))
  
  (pass-if "'(a) 1"
    (let ((lst '(a)))
      (eq? (cdr lst)
	   (drop lst 1))))
  
  (pass-if "'(a b) 1"
    (let ((lst '(a b)))
      (eq? (cdr lst)
	   (drop lst 1))))
  
  (pass-if "'(a b) 2"
    (let ((lst '(a b)))
      (eq? (cddr lst)
	   (drop lst 2))))
  
  (pass-if "'(a b c) 1"
    (let ((lst '(a b c)))
      (eq? (cddr lst)
	   (drop lst 2))))
  
  (pass-if "circular '(a) 0"
    (let ((lst (circular-list 'a)))
      (eq? lst
	   (drop lst 0))))
  
  (pass-if "circular '(a) 1"
    (let ((lst (circular-list 'a)))
      (eq? lst
	   (drop lst 1))))
  
  (pass-if "circular '(a) 2"
    (let ((lst (circular-list 'a)))
      (eq? lst
	   (drop lst 1))))
  
  (pass-if "circular '(a b) 1"
    (let ((lst (circular-list 'a)))
      (eq? (cdr lst)
	   (drop lst 0))))
  
  (pass-if "circular '(a b) 2"
    (let ((lst (circular-list 'a)))
      (eq? lst
	   (drop lst 1))))
  
  (pass-if "circular '(a b) 5"
    (let ((lst (circular-list 'a)))
      (eq? (cdr lst)
	   (drop lst 5))))
  
  (pass-if "'(a . b) 1"
    (eq? 'b
	 (drop '(a . b) 1)))
  
  (pass-if "'(a b . c) 1"
    (equal? 'c
	    (drop '(a b . c) 2))))

;;
;; take
;;

(with-test-prefix "take"
  
  (pass-if "'() 0"
    (null? (take '() 0)))
  
  (pass-if "'(a) 0"
    (null? (take '(a) 0)))
  
  (pass-if "'(a b) 0"
    (null? (take '() 0)))
  
  (pass-if "'(a b c) 0"
    (null? (take '() 0)))
  
  (pass-if "'(a) 1"
    (let* ((lst '(a))
	   (got (take lst 1)))
      (and (equal? '(a) got)
	   (not (eq? lst got)))))
  
  (pass-if "'(a b) 1"
    (equal? '(a)
	    (take '(a b) 1)))
  
  (pass-if "'(a b c) 1"
    (equal? '(a)
	    (take '(a b c) 1)))
  
  (pass-if "'(a b) 2"
    (let* ((lst '(a b))
	   (got (take lst 2)))
      (and (equal? '(a b) got)
	   (not (eq? lst got)))))
  
  (pass-if "'(a b c) 2"
    (equal? '(a b)
	    (take '(a b c) 2)))
  
  (pass-if "circular '(a) 0"
    (equal? '()
	    (take (circular-list 'a) 0)))
  
  (pass-if "circular '(a) 1"
    (equal? '(a)
	    (take (circular-list 'a) 1)))
  
  (pass-if "circular '(a) 2"
    (equal? '(a a)
	    (take (circular-list 'a) 2)))
  
  (pass-if "circular '(a b) 5"
    (equal? '(a b a b a)
	    (take (circular-list 'a 'b) 5)))
  
  (pass-if "'(a . b) 1"
    (equal? '(a)
	    (take '(a . b) 1)))
  
  (pass-if "'(a b . c) 1"
    (equal? '(a)
	    (take '(a b . c) 1)))
  
  (pass-if "'(a b . c) 2"
    (equal? '(a b)
	    (take '(a b . c) 2))))

;;
;; 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))))))