diff options
Diffstat (limited to 'test')
| -rw-r--r-- | test/union-find.lisp | 92 | ||||
| -rw-r--r-- | test/union-find/test-quick-find.lisp | 45 |
2 files changed, 40 insertions, 97 deletions
diff --git a/test/union-find.lisp b/test/union-find.lisp index 4bfa61d..36eeaee 100644 --- a/test/union-find.lisp +++ b/test/union-find.lisp @@ -12,57 +12,45 @@ ;;; Test create network -(define-test create-network-test () - ;; ----- Length tests - (dotimes (nw-size 1000) - (assert-equal nw-size (length (qf-create-network nw-size))) ; Quick-Find - (assert-equal nw-size (length (qu-create-network nw-size))) ; Quick-Union - ;; Weighted-Quick-Union - (assert-equal 10 (length (get-row (wqu-create-network 10) 0))) - (assert-equal 10 (length (get-row (wqu-create-network 10) 1))) - ;; Weighted-Quick-Union with Path Compression - (assert-equal 10 (length (get-row (wqupc-create-network 10) 0))) - (assert-equal 10 (length (get-row (wqupc-create-network 10) 1)))) - ;; ----- Value tests - (assert-equalp #(0 1 2 3 4) (qf-create-network 5)) ; Quick-Find - (assert-equalp #(0 1 2 3 4) (qu-create-network 5)) ; Quick-Union - ;; Weighted-Quick-Union - (assert-true (equalp #(0 1 2 3 4 5 6 7 8 9) (get-row (wqu-create-network 10) 0))) - (assert-true (equalp (make-array 10 :initial-element 1) (get-row (wqu-create-network 10) 1))) - ;; Weighted-Quick-Union with Path Compression - (assert-true (equalp #(0 1 2 3 4 5 6 7 8 9) (get-row (wqupc-create-network 10) 0))) - (assert-true (equalp (make-array 10 :initial-element 1) (get-row (wqupc-create-network 10) 1)))) - - -;; (define-test test-union_ -;; (let ((nw (create-network 10))) -;; (setf nw (union_ nw 1 2)) -;; (setf nw (union_ nw 0 5)) -;; (assert-equal (aref nw 1) (aref nw 2)) -;; (assert-equal (aref nw 0) (aref nw 5)) -;; (assert-false (equal (aref nw 0) (aref nw 8))) -;; (assert-false (equal (aref nw 0) (aref nw 2))))) - -;; (define-test test-connected -;; (let ((nw (create-network 10))) -;; (setf nw (union_ nw 1 2)) -;; (setf nw (union_ nw 0 5)) -;; (assert-true (connected nw 1 2)) -;; (assert-true (connected nw 0 5)) -;; (assert-false (connected nw 0 8)) -;; (assert-false (connected nw 0 2)))) - -;; (define-test test-nunion__ -;; (let ((nw (create-network 10))) -;; (nunion_ nw 1 2) -;; (nunion_ nw 0 5) -;; (assert-equal (aref nw 1) (aref nw 2)) -;; (assert-equal (aref nw 0) (aref nw 5)) -;; (assert-false (equal (aref nw 0) (aref nw 8))) -;; (assert-false (equal (aref nw 0) (aref nw 2))))) - -;; ;; Run all tests -;; (setq *print-summary* t) ; Details tests locations when running tests -;; (run-tests :all) +(define-test initialize-instance-test () + ;; ----- Network Length Tests + (dotimes (test-size 100) + (let* ((algo (make-instance 'quick-find :network-size test-size)) ; Quick Find + (nw (network algo)) + (nw-size (network-size algo))) + (assert-equal test-size nw-size) + (assert-equal test-size (length nw))) + (let* ((algo (make-instance 'quick-union :network-size test-size)) ; Quick Union + (nw (network algo)) + (nw-size (network-size algo))) + (assert-equal test-size nw-size) + (assert-equal test-size (length nw))) + (let* ((algo (make-instance 'weighted-quick-union :network-size test-size)) ; Weighted Quick Union + (nw (network algo)) + (nw-size (network-size algo))) + (assert-equal test-size nw-size) + (assert-equal test-size (length (get-row nw 0))) + (assert-equal test-size (length (get-row nw 1)))) + (let* ((algo (make-instance 'weighted-quick-union-path-compression :network-size test-size)) ; Weighted Quick Union Path Compression + (nw (network algo)) + (nw-size (network-size algo))) + (assert-equal test-size nw-size) + (assert-equal test-size (length (get-row nw 0))) + (assert-equal test-size (length (get-row nw 1))))) + ;; ----- Network Values Tests + (let* ((algo (make-instance 'quick-find :network-size 5)) ; Quick Find + (nw (network algo))) + (assert-true #(0 1 2 3 4) nw)) + (let* ((algo (make-instance 'quick-union :network-size 5)) ; Quick Union + (nw (network algo))) + (assert-true #(0 1 2 3 4) nw)) + (let* ((algo (make-instance 'weighted-quick-union :network-size 10)) ; Weighted Quick Union + (nw (network algo))) + (assert-true (equalp #(0 1 2 3 4 5 6 7 8 9) (get-row nw 0))) + (assert-true (equalp (make-array 10 :initial-element 1) (get-row nw 1)))) + (let* ((algo (make-instance 'weighted-quick-union-path-compression :network-size 10)) ; Weighted Quick Union Path Compression + (nw (network algo))) + (assert-true (equalp #(0 1 2 3 4 5 6 7 8 9) (get-row nw 0))) + (assert-true (equalp (make-array 10 :initial-element 1) (get-row nw 1))))) diff --git a/test/union-find/test-quick-find.lisp b/test/union-find/test-quick-find.lisp deleted file mode 100644 index f173ea6..0000000 --- a/test/union-find/test-quick-find.lisp +++ /dev/null @@ -1,45 +0,0 @@ -(load "../lisp-unit.lisp") -(defpackage :test-quick-find - (:use :common-lisp - :lisp-unit)) - -(in-package :test-quick-find) -(load "../../src/union-find/quick-find.lisp") - -;;; Define tests -(define-test test-create-network - (assert-equal 10 (length (create-network 10))) - (assert-equalp #(0 1 2 3 4) (create-network 5))) - -(define-test test-union_ - (let ((nw (create-network 10))) - (setf nw (union_ nw 1 2)) - (setf nw (union_ nw 0 5)) - (assert-equal (aref nw 1) (aref nw 2)) - (assert-equal (aref nw 0) (aref nw 5)) - (assert-false (equal (aref nw 0) (aref nw 8))) - (assert-false (equal (aref nw 0) (aref nw 2))))) - -(define-test test-connected - (let ((nw (create-network 10))) - (setf nw (union_ nw 1 2)) - (setf nw (union_ nw 0 5)) - (assert-true (connected nw 1 2)) - (assert-true (connected nw 0 5)) - (assert-false (connected nw 0 8)) - (assert-false (connected nw 0 2)))) - -(define-test test-nunion__ - (let ((nw (create-network 10))) - (nunion_ nw 1 2) - (nunion_ nw 0 5) - (assert-equal (aref nw 1) (aref nw 2)) - (assert-equal (aref nw 0) (aref nw 5)) - (assert-false (equal (aref nw 0) (aref nw 8))) - (assert-false (equal (aref nw 0) (aref nw 2))))) - -;; Run all tests -(setq *print-summary* t) ; Details tests locations when running tests -(run-tests :all) - - |