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

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

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

  (provide/contract
   [test-table schemeunit-test-suite?]
   [test-ordered-table schemeunit-test-suite?]
   [test-hashed-table schemeunit-test-suite?]
   [test-unordered-table schemeunit-test-suite?])
  
  (define (make-table-test name table)
    (test-suite (format "Table: ~a" name)
      (test-suite "accessors"
        (test-suite "keys"
          (test-case "empty"
            (check equal?
                    (table:keys (table null))
                    (map first (table:to-sexp (table null)))))
          (test-case "1,2,3"
            (check equal?
                    (table:keys (table '([1 A] [2 B] [3 C])))
                    (map first (table:to-sexp (table '([1 A] [2 B] [3 C])))))))
        (test-suite "values"
          (test-case "empty"
            (check equal?
                    (table:values (table null))
                    (map second (table:to-sexp (table null)))))
          (test-case "1,2,3"
            (check equal?
                    (table:values (table '([1 A] [2 B] [3 C])))
                    (map second (table:to-sexp (table '([1 A] [2 B] [3 C])))))))
        (test-suite "to-sexp"
          (test-case "empty"
            (check datum-bindings=? (table:to-sexp (table null)) null))
          (test-case "1,2,3"
            (check datum-bindings=?
                    (table:to-sexp (table '([1 A] [2 B] [3 C])))
                    '([1 A] [2 B] [3 C]))))
        (test-suite "to-alist"
          (test-case "empty"
            (check equal?
                    (table:to-alist (table null))
                    (map (lambda (pair) (cons (first pair) (second pair)))
                         (table:to-sexp (table null)))))
          (test-case "1,2,3"
            (check equal?
                    (table:to-alist (table '([1 A] [2 B] [3 C])))
                    (map (lambda (pair) (cons (first pair) (second pair)))
                         (table:to-sexp (table '([1 A] [2 B] [3 C])))))))
        (test-suite "empty?"
          (test-case "true"
            (check-true (table:empty? (table null))))
          (test-case "false"
            (check-false (table:empty? (table '([1 A] [2 B] [3 C]))))))
        (test-suite "size"
          (test-case "A1-B2-C3"
            (check = (table:size (table '([A 1] [B 2] [C 3]))) 3)))
        (test-suite "contains?"
          (test-case "true"
            (check-true (table:contains? 'A (table '([A 1] [B 2] [C 3])))))
          (test-case "false"
            (check-false (table:contains? 'D (table '([A 1] [B 2] [C 3]))))))
        (test-suite "lookup"
          (test-case "a in a,b,c"
            (check = (table:lookup "a" (table '(["a" 1] ["b" 2] ["c" 3]))) 1))
          (test-case "a in b,c"
            (check-false (table:lookup "a" (table '(["b" 2] ["c" 3])))))
          (test-case "success override"
            (check eq?
                    (table:lookup 1 (table '([1 one] [2 two] [3 three]))
                                  (lambda () 'failure)
                                  (lambda (any) 'success))
                    'success))
          (test-case "failure override"
            (check eq?
                    (table:lookup 4 (table '([1 one] [2 two] [3 three]))
                                  (lambda () 'failure)
                                  (lambda (any) 'success))
                    'failure)))
        (test-suite "lookup/key"
          (test-case "present"
            (check-equal? (table:lookup/key 1 (table '([1 A] [2 B] [3 C]))) 1))
          (test-case "absent"
            (check-equal? (table:lookup/key 4 (table '([1 A] [2 B] [3 C]))) #f))
          (test-case "success override"
            (check-equal?
             (table:lookup/key 1 (table '([1 A] [2 B] [3 C]))
                               (lambda () 'failure)
                               (lambda (k v) 'success))
             'success))
          (test-case "failure override"
            (check-equal?
             (table:lookup/key 4 (table '([1 A] [2 B] [3 C]))
                               (lambda () 'failure)
                               (lambda (k v) 'success))
             'failure)))
        (test-suite "select"
          (test-case "singleton"
            (let*-values ([(key value) (table:select (table '([1 A])))])
              (check datum=? key 1)
              (check datum=? value 'A))))
        (test-suite "select/key"
          (test-case "singleton"
            (let* ([key (table:select/key (table '([1 A])))])
              (check datum=? key 1))))
        (test-suite "select/value"
          (test-case "singleton"
            (let* ([value (table:select/value (table '([1 A])))])
              (check datum=? value 'A))))
        )
      (test-suite "updaters"
        (test-suite "insert"
          (test-case "1,3 + 2"
            (check datum-bindings=?
                    (table:to-sexp (table:insert 2 'B (table '([1 A] [3 C]))))
                    '([1 A] [2 B] [3 C])))
          (test-case "1,2,3 + 2"
            (check datum-bindings=?
                    (table:to-sexp (table:insert 2 'X (table '([1 A] [2 B] [3 C]))))
                    '([1 A] [2 X] [3 C]))))
        (test-suite "remove"
          (test-case "present"
            (check datum-bindings=?
                    (table:to-sexp (table:remove 2 (table '([1 A] [2 B] [3 C]))))
                    '([1 A] [3 C])))
          (test-case "absent"
            (check datum-bindings=?
                    (table:to-sexp (table:remove 4 (table '([1 A] [2 B] [3 C]))))
                    '([1 A] [2 B] [3 C]))))
        (test-suite "update"
          (test-case "present"
            (check
             datum-bindings=?
             (table:to-sexp (table:update 1 + (table '([1 10] [2 20] [3 30]))))
             '([1 11] [2 20] [3 30])))
          (test-case "absent"
            (check
             datum-bindings=?
             (table:to-sexp (table:update 4 + (table '([1 10] [2 20] [3 30]))))
             '([1 10] [2 20] [3 30]))))
        (test-suite "update/value"
          (test-case "present"
            (check
             datum-bindings=?
             (table:to-sexp
              (table:update/value 1 symbol->string (table '([1 A] [2 B] [3 C]))))
             '([1 "A"] [2 B] [3 C])))
          (test-case "absent"
            (check
             datum-bindings=?
             (table:to-sexp
              (table:update/value 4 symbol->string (table '([1 A] [2 B] [3 C]))))
             '([1 A] [2 B] [3 C]))))
        (test-suite "update/insert"
          (test-case "present"
            (check
             datum-bindings=?
             (table:to-sexp
              (table:update/insert 1 + 10 (table '([1 10] [2 20] [3 30]))))
             '([1 11] [2 20] [3 30])))
          (test-case "absent"
            (check
             datum-bindings=?
             (table:to-sexp
              (table:update/insert 4 + 40 (table '([1 10] [2 20] [3 30]))))
             '([1 10] [2 20] [3 30] [4 40]))))
        (test-suite "update/insert/value"
          (test-case "present"
            (check
             datum-bindings=?
             (table:to-sexp
              (table:update/insert/value 1 symbol->string 'A
                                         (table '([1 A] [2 B] [3 C]))))
             '([1 "A"] [2 B] [3 C])))
          (test-case "absent"
            (check
             datum-bindings=?
             (table:to-sexp
              (table:update/insert/value 4 symbol->string 'D
                                         (table '([1 A] [2 B] [3 C]))))
             '([1 A] [2 B] [3 C] [4 D]))))
        (test-suite "clear"
          (test-case "1,2,3"
            (check-true
             (table:empty? (table:clear (table '([1 A] [2 B] [3 C])))))))
        )
      (test-suite "traversals"
        (test-suite "fold"
          (test-case "1,2,3"
            (check-equal?
             (table:fold (lambda (key value sexp)
                           (append sexp (list (list key value))))
                         null
                         (table '([1 A] [2 B] [3 C])))
             (table:to-sexp (table '([1 A] [2 B] [3 C]))))))
        (test-suite "fold/key"
          (test-case "1,2,3"
            (check-equal?
             (table:fold/key (lambda (key keys)
                               (append keys (list key)))
                             null
                             (table '([1 A] [2 B] [3 C])))
             (table:keys (table '([1 A] [2 B] [3 C]))))))
        (test-suite "fold/value"
          (test-case "1,2,3"
            (check-equal?
             (table:fold/value (lambda (value values)
                                 (append values (list value)))
                               null
                               (table '([1 A] [2 B] [3 C])))
             (table:values (table '([1 A] [2 B] [3 C]))))))
        (test-suite "for-each"
          (test-case "1,2,3"
            (let* ([vec (vector #f #f #f)])
              (table:for-each (lambda (key value)
                                (vector-set! vec (- key 1) value))
                              (table '([1 A] [2 B] [3 C])))
              (check-equal? vec (vector 'A 'B 'C))))
          (test-case "non-void"
            (table:for-each (constant #f) (table '([1 A])))))
        (test-suite "for-each/key"
          (test-case "1,2,3"
            (let* ([vec (vector #f #f #f)])
              (table:for-each/key (lambda (key)
                                    (vector-set! vec (- key 1) #t))
                                  (table '([1 A] [2 B] [3 C])))
              (check-equal? vec (vector #t #t #t))))
          (test-case "non-void"
            (table:for-each/key (constant #f) (table '([1 A])))))
        (test-suite "for-each/value"
          (test-case "1,2,3"
            (let* ([vec (vector #f #f #f)])
              (table:for-each/value (lambda (value)
                                      (vector-set! vec (- value 1) #t))
                                    (table '([A 1] [B 2] [C 3])))
              (check-equal? vec (vector #t #t #t))))
          (test-case "non-void"
            (table:for-each/value (constant #f) (table '([1 A])))))
        (test-suite "map"
          (test-case "1:10,2:20,3:30 => 1:11,2:22,3:33"
            (check datum-bindings=?
                    (table:to-sexp (table:map +
                                              (table '([1 10] [2 20] [3 30]))))
                    '([1 11] [2 22] [3 33]))))
        (test-suite "map/key"
          (test-case "1:1,2:4,3:9"
            (check datum-bindings=?
                    (table:to-sexp (table:map/key (lambda (n) (* n n))
                                                  (table '([1 #f] [2 #f] [3 #f]))))
                    '([1 1] [2 4] [3 9]))))
        (test-suite "map/value"
          (test-case "1A2B3C => 1'A'2'B'3'C'"
            (check datum-bindings=?
                    (table:to-sexp (table:map/value symbol->string
                                                    (table '([1 A] [2 B] [3 C]))))
                    '([1 "A"] [2 "B"] [3 "C"]))))
        (test-suite "filter"
          (test-case "1:4,2:3,3:2,4:1 => 1:4,2:3"
            (check datum-bindings=?
                    (table:to-sexp
                     (table:filter < (table '([1 4] [2 3] [3 2] [4 1]))))
                    '([1 4] [2 3]))))
        (test-suite "filter/key"
          (test-case "1,2,3,4 => 2,4"
            (check datum-bindings=?
                    (table:to-sexp
                     (table:filter/key even? (table '([1 A] [2 B] [3 C] [4 D]))))
                    '([2 B] [4 D]))))
        (test-suite "filter/value"
          (test-case "1,2,3,4 => 2,4"
            (check datum-bindings=?
                    (table:to-sexp
                     (table:filter/value even?
                                         (table '([A 1] [B 2] [C 3] [D 4]))))
                    '([B 2] [D 4]))))
        (test-suite "all?"
          (test-case "none"
            (check-false (table:all? < (table '([1 1] [2 2] [3 3])))))
          (test-case "some"
            (check-false (table:all? < (table '([1 0] [2 2] [3 4])))))
          (test-case "all"
            (check-true (table:all? < (table '([1 2] [2 3] [3 4]))))))
        (test-suite "all?/key"
          (test-case "none"
            (check-false (table:all?/key symbol?
                                          (table '([1 A] [2 B] [3 C])))))
          (test-case "some"
            (check-false (table:all?/key symbol?
                                          (table '([1 A] [B 2] [C C])))))
          (test-case "all"
            (check-true (table:all?/key symbol?
                                         (table '([A 1] [B 2] [C 3]))))))
        (test-suite "all?/value"
          (test-case "none"
            (check-false (table:all?/value number?
                                            (table '([1 A] [2 B] [3 C])))))
          (test-case "some"
            (check-false (table:all?/value number?
                                            (table '([1 A] [B 2] [C C])))))
          (test-case "all"
            (check-true (table:all?/value number?
                                           (table '([A 1] [B 2] [C 3]))))))
        (test-suite "any?"
          (test-case "none"
            (check-false (table:any? < (table '([1 1] [2 2] [3 3])))))
          (test-case "some"
            (check-true (table:any? < (table '([1 0] [2 2] [3 4])))))
          (test-case "all"
            (check-true (table:any? < (table '([1 2] [2 3] [3 4]))))))
        (test-suite "any?/key"
          (test-case "none"
            (check-false (table:any?/key symbol?
                                          (table '([1 A] [2 B] [3 C])))))
          (test-case "some"
            (check-true (table:any?/key symbol?
                                         (table '([1 A] [B 2] [C C])))))
          (test-case "all"
            (check-true (table:any?/key symbol?
                                         (table '([A 1] [B 2] [C 3]))))))
        (test-suite "any?/value"
          (test-case "none"
            (check-false (table:any?/value number?
                                            (table '([1 A] [2 B] [3 C])))))
          (test-case "some"
            (check-true (table:any?/value number?
                                           (table '([1 A] [B 2] [C C])))))
          (test-case "all"
            (check-true (table:any?/value number?
                                           (table '([A 1] [B 2] [C 3]))))))
        )
      (test-suite "combinations"
        (test-suite "union"
          (test-case "disjoint"
            (check datum-bindings=?
                    (table:to-sexp
                     (table:union (table '([A 1] [B 2]))
                                  (table '([C 3] [D 4]))))
                    '([A 1] [B 2] [C 3] [D 4])))
          (test-case "overlap"
            (check datum-bindings=?
                    (table:to-sexp
                     (table:union (table '([A 1] [B 2]))
                                  (table '([B 2] [C 3]))))
                    '([A 1] [B 2] [C 3])))
          (test-case "default"
            (let* ([a1 "a"]
                   [a2 (string-copy a1)])
              (check-eq? (table:lookup
                           1
                           (table:union (table `([1 ,a1]))
                                        (table `([1 ,a2]))))
                          a1)))
          (test-case "override"
            (let* ([a1 "a"]
                   [a2 (string-copy a1)])
              (check-eq? (table:lookup
                           1
                           (table:union (table `([1 ,a1]))
                                        (table `([1 ,a2]))
                                        (lambda (k a b) b)))
                          a2)))
          )
        (test-suite "union/value"
          (test-case "disjoint"
            (check datum-bindings=?
                    (table:to-sexp
                     (table:union/value (table '([A 1] [B 2]))
                                        (table '([C 3] [D 4]))))
                    '([A 1] [B 2] [C 3] [D 4])))
          (test-case "overlap"
            (check datum-bindings=?
                    (table:to-sexp
                     (table:union/value (table '([A 1] [B 2]))
                                        (table '([B 2] [C 3]))))
                    '([A 1] [B 2] [C 3])))
          (test-case "default"
            (let* ([a1 "a"]
                   [a2 (string-copy a1)])
              (check-eq? (table:lookup
                           1
                           (table:union/value (table `([1 ,a1]))
                                              (table `([1 ,a2]))))
                          a1)))
          (test-case "override"
            (let* ([a1 "a"]
                   [a2 (string-copy a1)])
              (check-eq? (table:lookup
                           1
                           (table:union/value (table `([1 ,a1]))
                                              (table `([1 ,a2]))
                                              (lambda (a b) b)))
                          a2)))
          )
        (test-suite "intersection"
          (test-case "disjoint"
            (check datum-bindings=?
                    (table:to-sexp
                     (table:intersection (table '([A 1] [B 2]))
                                         (table '([C 3] [D 4]))))
                    '()))
          (test-case "overlap"
            (check datum-bindings=?
                    (table:to-sexp
                     (table:intersection (table '([A 1] [B 2]))
                                         (table '([B 2] [C 3]))))
                    '([B 2])))
          (test-case "default"
            (let* ([a1 "a"]
                   [a2 (string-copy a1)])
              (check-eq? (table:lookup
                           1
                           (table:intersection (table `([1 ,a1]))
                                               (table `([1 ,a2]))))
                          a1)))
          (test-case "override"
            (let* ([a1 "a"]
                   [a2 (string-copy a1)])
              (check-eq? (table:lookup
                           1
                           (table:intersection (table `([1 ,a1]))
                                               (table `([1 ,a2]))
                                               (lambda (k a b) b)))
                          a2)))
          )
        (test-suite "intersection/value"
          (test-case "disjoint"
            (check datum-bindings=?
                    (table:to-sexp
                     (table:intersection/value (table '([A 1] [B 2]))
                                               (table '([C 3] [D 4]))))
                    '()))
          (test-case "overlap"
            (check datum-bindings=?
                    (table:to-sexp
                     (table:intersection/value (table '([A 1] [B 2]))
                                               (table '([B 2] [C 3]))))
                    '([B 2])))
          (test-case "default"
            (let* ([a1 "a"]
                   [a2 (string-copy a1)])
              (check-eq? (table:lookup
                           1
                           (table:intersection/value (table `([1 ,a1]))
                                                     (table `([1 ,a2]))))
                          a1)))
          (test-case "override"
            (let* ([a1 "a"]
                   [a2 (string-copy a1)])
              (check-eq? (table:lookup
                           1
                           (table:intersection/value (table `([1 ,a1]))
                                                     (table `([1 ,a2]))
                                                     (lambda (a b) b)))
                          a2)))
          )
        (test-suite "difference"
          (test-case "disjoint"
            (check datum-bindings=?
                    (table:to-sexp
                     (table:difference (table '([A 1] [B 2]))
                                       (table '([C 3] [D 4]))))
                    '([A 1] [B 2])))
          (test-case "overlap"
            (check datum-bindings=?
                    (table:to-sexp
                     (table:difference (table '([A 1] [B 2]))
                                       (table '([B 2] [C 3]))))
                    '([A 1])))
          )
        )
      (test-suite "relations"
        (test-suite "subtable?"
          (test-case "is subtable"
            (check-true (table:subtable? datum=?
                                          (table '([A 1] [B 2]))
                                          (table '([A 1] [B 2] [C 3])))))
          (test-case "missing key"
            (check-false (table:subtable? datum=?
                                           (table '([A 1] [B 2]))
                                           (table '([B 2] [C 3])))))
          (test-case "bad binding"
            (check-false (table:subtable? datum=?
                                           (table '([A 1] [B 2] [C 3]))
                                           (table '([A 1] [B 4] [C 3]))))))
        (test-suite "equal?"
          (test-case "is equal"
            (check-true (table:equal? datum=?
                                       (table '([A 1] [B 2] [C 3]))
                                       (table '([A 1] [B 2] [C 3])))))
          (test-case "missing key"
            (check-false (table:equal? datum=?
                                        (table '([A 1] [B 2] [C 3]))
                                        (table '([A 1] [B 2])))))
          (test-case "extra key"
            (check-false (table:equal? datum=?
                                        (table '([A 1] [B 2]))
                                        (table '([A 1] [B 2] [C 3])))))
          (test-case "bad binding"
            (check-false (table:equal? datum=?
                                        (table '([A 1] [B 2] [C 3]))
                                        (table '([A 1] [B 4] [C 3]))))))
        )
      ))

  (define test-ordered-table
    (make-table-test "Ordered" (curry table:sexp->ordered datum-compare)))

  (define test-hashed-table
    (make-table-test "Hashed" (curry table:sexp->hashed datum-hash datum=?)))

  (define test-unordered-table
    (make-table-test "Unordered" (curry table:sexp->unordered datum=?)))

  (define test-table
    (test-suite "Tables"
      test-ordered-table
      test-hashed-table
      test-unordered-table))

  )