test/test-set.ss
(module test-set mzscheme

  (require "../private/require.ss")
  (require-contracts)
  (require-schemeunit)
  (require-etc)
  (require-lists)

  (require "../private/datum.ss"
           (prefix set: "../set.ss"))

  (provide/contract
   [test-set schemeunit-test-suite?]
   [test-ordered-set schemeunit-test-suite?]
   [test-hashed-set schemeunit-test-suite?]
   [test-unordered-set schemeunit-test-suite?])
  
  (define (make-set-test name set)
    (test-suite (format "Set: ~a" name)
      (test-suite "accessors"
        (test-suite "elements"
          (test-case "empty"
            (check datum-list=? (set:elements (set)) null))
          (test-case "1,2,3"
            (check datum-list=? (set:elements (set 1 2 3)) (list 1 2 3))))
        (test-suite "empty?"
          (test-case "true"
            (check-true (set:empty? (set))))
          (test-case "false"
            (check-false (set:empty? (set 1 2 3)))))
        (test-suite "size"
          (test-case "empty"
            (check = (set:size (set)) 0))
          (test-case "1,2,3"
            (check = (set:size (set 1 2 3)) 3)))
        (test-suite "member?"
          (test-case "true"
            (check-true (set:member? 2 (set 1 2 3))))
          (test-case "false"
            (check-false (set:member? 4 (set 1 2 3)))))
        (test-suite "lookup"
          (test-case "a in a,b,c"
            (let* ([a "a"]
                   [b "b"]
                   [c "c"]
                   [a* (string-copy a)])
              (check eq?
                      (set:lookup a* (set a b c))
                      a)))
          (test-case "a in b,c"
            (check-false (set:lookup "a" (set "b" "c"))))
          (test-case "success override"
            (check-equal?
             (set:lookup 1 (set 1 2 3)
                         (lambda () 'failure)
                         (lambda (elem) (cons 'success elem)))
             (cons 'success 1)))
          (test-case "failure override"
            (check-equal?
             (set:lookup 4 (set 1 2 3)
                         (lambda () 'failure)
                         (lambda (elem) (cons 'success elem)))
             'failure)))
        (test-suite "select"
          (test-case "empty set"
            (check-exn exn:fail? (lambda () (set:select (set)))))
          (test-case "singleton set"
            (check datum=?
                    (set:select (set 1))
                    1))
          (test-case "1,2,3"
            (check-true
             (let* ([elem (set:select (set 1 2 3))])
               (or (= elem 1)
                   (= elem 2)
                   (= elem 3))))))
        )
      (test-suite "updaters"
        (test-suite "insert"
          (test-case "1,3 + 2"
            (check datum-list=?
                    (set:elements (set:insert 2 (set 1 3)))
                    (list 1 2 3)))
          (test-case "1,2,3 + 2"
            (check datum-list=?
                    (set:elements (set:insert 2 (set 1 2 3)))
                    (list 1 2 3)))
          (test-case "a,b,c + a"
            (let* ([a "a"]
                   [a* (string-copy a)]
                   [elems (set:elements (set:insert a* (set a)))])
              (check = (length elems) 1
                      "Inserting a duplicate changed set size.")
              (check-false
               (eq? (first elems) a)
               "Inserted duplicate; original value remains.")
              (check-true
               (eq? (first elems) a*)
               "Inserted duplicate; new value not found."))))
        (test-suite "remove"
          (test-case "present"
            (check datum-list=?
                    (set:elements (set:remove 2 (set 1 2 3)))
                    (list 1 3)))
          (test-case "absent"
            (check datum-list=?
                    (set:elements (set:remove 4 (set 1 2 3)))
                    (list 1 2 3))))
        (test-suite "clear"
          (test-case "1,2,3"
            (check-true (set:empty? (set:clear (set 1 2 3))))))
        )
      (test-suite "traversals"
        (test-suite "fold"
          (test-case "1,2,3"
            (check datum-list=?
                    (set:fold cons null (set 1 2 3))
                    (list 1 2 3))))
        (test-suite "map"
          (test-case "A,B,C"
            (check datum-list=?
                    (set:elements (set:map symbol->string (set 'A 'B 'C)))
                    (list "A" "B" "C")))
          (test-case "overlap"
            (check datum-list=?
                    (set:elements (set:map (lambda (n) (* n n)) (set -1 0 1 2)))
                    (list 0 1 4))))
        (test-suite "for-each"
          (test-case "1,2,3"
            (let* ([elems null])
              (set:for-each (lambda (elem) (set! elems (cons elem elems)))
                            (set 1 2 3))
              (check datum-list=? elems (list 1 2 3))))
          (test-case "non-void"
            (set:for-each (constant #f) (set 1 2 3))))
        (test-suite "filter"
          (test-case "numbers"
            (check datum-list=?
                    (set:elements (set:filter number?
                                              (set 1 2 3 'a 'b 'c "A" "B" "C")))
                    (list 1 2 3))))
        (test-suite "all?"
          (test-case "all"
            (check-true (set:all? number? (set 1 2 3 4))))
          (test-case "some"
            (check-false (set:all? even? (set 1 2 3 4))))
          (test-case "none"
            (check-false (set:all? negative? (set 1 2 3 4)))))
        (test-suite "any?"
          (test-case "all"
            (check-true (set:any? number? (set 1 2 3 4))))
          (test-case "some"
            (check-true (set:any? even? (set 1 2 3 4))))
          (test-case "none"
            (check-false (set:any? negative? (set 1 2 3 4)))))
        )
      (test-suite "combinations"
        (test-suite "union"
          (test-case "1,3+2,4"
            (check datum-list=?
                    (set:elements (set:union (set 1 3) (set 2 4)))
                    (list 1 2 3 4)))
          (test-case "1,2,3+2,3,4"
            (check datum-list=?
                    (set:elements (set:union (set 1 2 3) (set 2 3 4)))
                    (list 1 2 3 4)))
          (test-case "override"
            (let* ([a1 "a"]
                   [a2 (string-copy a1)]
                   [elems
                    (set:elements
                     (set:union (set a1) (set a2)
                                (lambda (one two)
                                  (check eq? one a1)
                                  (check eq? two a2)
                                  (string-copy one))))])
              (check equal? elems (list "a"))
              (check-false (eq? (car elems) a1))
              (check-false (eq? (car elems) a2)))))
        (test-suite "intersection"
          (test-case "1,3&2,4"
            (check datum-list=?
                    (set:elements (set:intersection (set 1 3) (set 2 4)))
                    null))
          (test-case "1,2,3&2,3,4"
            (check datum-list=?
                    (set:elements (set:intersection (set 1 2 3) (set 2 3 4)))
                    (list 2 3)))
          (test-case "override"
            (let* ([b1 "b"]
                   [b2 (string-copy b1)]
                   [elems
                    (set:elements
                     (set:intersection (set "a" b1)
                                       (set b2 "c")
                                       (lambda (one two)
                                         (check eq? one b1)
                                         (check eq? two b2)
                                         (string-copy one))))])
              (check equal? elems (list "b"))
              (check-false (eq? (car elems) b1))
              (check-false (eq? (car elems) b2)))))
        (test-suite "difference"
          (test-case "1,3-2,4"
            (check datum-list=?
                    (set:elements (set:difference (set 1 3) (set 2 4)))
                    (list 1 3)))
          (test-case "1,2,3-2,3,4"
            (check datum-list=?
                    (set:elements (set:difference (set 1 2 3) (set 2 3 4)))
                    (list 1))))
        )
      (test-suite "relations"
        (test-suite "subset?"
          (test-case "A subset B"
            (check-true (set:subset? (set 1 2) (set 1 2 3))))
          (test-case "A equal B"
            (check-true (set:subset? (set 1 2 3) (set 1 2 3))))
          (test-case "A superset B"
            (check-false (set:subset? (set 1 2 3) (set 1 2))))
          (test-case "A disjoint B"
            (check-false (set:subset? (set 1 2 3) (set 4 5 6))))
          (test-case "A overlaps B"
            (check-false (set:subset? (set 1 2 3) (set 2 3 4)))))
        (test-suite "equal?"
          (test-case "A subset B"
            (check-false (set:equal? (set 1 2) (set 1 2 3))))
          (test-case "A equal B"
            (check-true (set:equal? (set 1 2 3) (set 1 2 3))))
          (test-case "A superset B"
            (check-false (set:equal? (set 1 2 3) (set 1 2))))
          (test-case "A disjoint B"
            (check-false (set:equal? (set 1 2 3) (set 4 5 6))))
          (test-case "A overlaps B"
            (check-false (set:equal? (set 1 2 3) (set 2 3 4)))))
        )
      ))

  (define test-ordered-set
    (make-set-test "Ordered" (curry set:make-ordered datum-compare)))

  (define test-hashed-set
    (make-set-test "Hashed" (curry set:make-hashed datum-hash datum=?)))

  (define test-unordered-set
    (make-set-test "Unordered" (curry set:make-unordered datum=?)))

  (define test-set
    (test-suite "Sets"
      test-ordered-set
      test-hashed-set
      test-unordered-set))

  )