blob: 36eeaee4fa2b192bdd55cfe5000d9989fe6bdb8a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
(in-package :com.lisp-algo.test)
;;; Utils
(defun get-row (array &optional (row-id 0))
(let* ((row-size (array-dimension array 1)) ; Deduce row size from array
(row (make-array row-size :fill-pointer 0))) ; Initialize a new vector (which will contain the row row-id from array)
;; Fill row with the right values of array
(do ((cur-id 0 (+ cur-id 1)))
((>= cur-id row-size) row)
(vector-push (row-major-aref array (+ cur-id (* row-size row-id ))) row))))
;;; Test create network
(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)))))
|
