source: project/nondescript/binary-tree/tests/binary-tree-test.scm @ 8915

Last change on this file since 8915 was 8915, checked in by Kon Lovett, 13 years ago

Save.

File size: 3.6 KB
Line 
1;;;; binary-tree-test.scm
2
3(use testbase testbase-output-human)
4(use avltree)
5(use srfi-1 srfi-13)
6
7;;;
8
9(define-inline (->boolean obj)
10        (and obj #t) )
11
12(define (random-alist n #!optional (lim (* n 10)))
13        (let loop ([n n] [al '()])
14                (if (zero? n)
15        al
16        (loop (sub1 n) (alist-cons (random lim) (gensym) al)) ) ) )
17
18(define (alist-same? al1 al2)
19        (every
20                (lambda (pare)
21                        (and-let* ([v2 (alist-ref (car pare) al2 equal?)])
22                                (equal? v2 (cdr pare)) ) )
23                al1) )
24
25(define (list-same? l1 l2)
26        (every (lambda (x) (->boolean (member x l2))) l1) )
27
28(define (random-tree n)
29        (alist->avltree (random-alist n) <) )
30
31;;;
32
33(define-expect-binary alist-same? alist-same "alist same key-value pairs, w/o ordering")
34
35(define-expect-binary list-same? list-same "list same values, w/o ordering")
36
37;;;
38
39(define-test avltree-test "Avl-Tree"
40  (initial
41                (define t1 #f) )
42
43        (expect-set! t1
44                (alist->avltree
45                        '(("phone" . 3456) ("fax" . 2345) ("name" . "foo") ("address" . "23 Marylane Ave"))
46                        string<))
47
48        (test/case "Avl-Tree Basic"
49
50                (expect-true (avltree? t1))
51                (expect-false (avltree? 23))
52
53                (expect-false (avltree-empty? t1))
54                (expect-eqv 4 (avltree-size t1))
55
56                (expect-true (avltree-exists? t1 "name"))
57                (expect-false (avltree-exists? t1 "foo"))
58
59                (expect-eqv 2345 (avltree-ref t1 "fax"))
60                (expect-false (avltree-ref/default t1 "foo" #f))
61                (expect-failure (avltree-ref t1 "foo"))
62
63                (expect-alist-same
64                        '(("phone" . 3456) ("fax" . 2345) ("name" . "foo") ("address" . "23 Marylane Ave"))
65                        (avltree->alist t1))
66
67                (expect-list-same
68                        '("phone" "fax" "name" "address")
69                        (avltree-keys t1))
70                (expect-list-same
71                        '(3456 2345 "foo" "23 Marylane Ave")
72                        (avltree-values t1))
73        )
74
75        (test/case "Avl-Tree Delete" (
76                        [t2 #f] )
77
78                (expect-false (avltree-delete! t1 "foo"))
79                (expect-success (avltree-delete! t1 "name"))
80                (expect-eqv 3 (avltree-size t1))
81                (expect-failure (avltree-ref t1 "name"))
82                (expect-failure (avltree-update! t1 "name" (lambda (v) v)))
83
84                (expect-set! t2 (avltree-delete t1 "fax"))
85                (expect-eqv 2 (avltree-size t2))
86                (expect-eqv 3 (avltree-size t1))
87                (expect-failure (avltree-ref t2 "fax"))
88                (expect-failure (avltree-update t2 "fax" (lambda (v) v)))
89
90                (expect-set! t2 (avltree-set t2 "name" "bar"))
91                (expect-eqv 3 (avltree-size t2))
92                (expect-equal "bar" (avltree-ref t2 "name"))
93                (expect-set! t2 (avltree-update t2 "name" (lambda (v) "baz")))
94                (expect-equal "baz" (avltree-ref t2 "name"))
95                (expect-eqv 3 (avltree-size t2))
96
97                (expect-success (avltree-set! t1 "name" "bar"))
98                (expect-eqv 4 (avltree-size t1))
99                (expect-equal "bar" (avltree-ref t1 "name"))
100                (expect-success (avltree-update! t1 "name" (lambda (v) "baz")))
101                (expect-equal "baz" (avltree-ref t1 "name"))
102                (expect-eqv 4 (avltree-size t1))
103
104                (expect-success (avltree-delete! t1 "fax"))
105                (expect-success (avltree-vacuum! t1))
106                (expect-eqv 3 (avltree-size t1))
107                (expect-alist-same
108                        '(("phone" . 3456) ("name" . "baz") ("address" . "23 Marylane Ave"))
109                        (avltree->alist t1))
110
111                (expect-set! t2 (avltree-copy t2))
112                (expect-eqv 3 (avltree-size t2))
113                (expect-alist-same
114                        '(("phone" . 3456) ("name" . "baz") ("address" . "23 Marylane Ave"))
115                        (avltree->alist t1))
116
117                (expect-success (avltree-delete! t1 "phone"))
118                (expect-success (avltree-delete! t1 "name"))
119                (expect-success (avltree-delete! t1 "address"))
120                (expect-eqv 0 (avltree-size t1))
121                (expect-alist-same
122                        '()
123                        (avltree->alist t1))
124                (expect-success (avltree-vacuum! t1))
125                (expect-eqv 0 (avltree-size t1))
126                (expect-alist-same
127                        '()
128                        (avltree->alist t1))
129        )
130)
131
132(test::styler-set! avltree-test test::output-style-human)
133(run-test "AVL Tree Tests")
134
135(test::forget!)
Note: See TracBrowser for help on using the repository browser.