blob: 86a2116706122bc04d4a9f639aefd1f40f0ab6a6 (
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
(load "../common")
(defvarl tr (tree))
(defvarl keys '(0 6 8 11 10 2 16 3 17 7 19 12 15 13 18 4 14 5 1 9))
(test tr #T(()))
(test (treep tr) t)
(test (treep 42) nil)
(each ((n keys))
(tree-insert tr n))
(mtest
(tree-lookup tr 0) 0
(tree-lookup tr 1) 1
(tree-lookup tr 2) 2
(tree-lookup tr 3) 3
(tree-lookup tr 4) 4
(tree-lookup tr 5) 5
(tree-lookup tr 6) 6
(tree-lookup tr 7) 7
(tree-lookup tr 8) 8
(tree-lookup tr 9) 9
(tree-lookup tr 10) 10
(tree-lookup tr 11) 11
(tree-lookup tr 12) 12
(tree-lookup tr 13) 13
(tree-lookup tr 14) 14
(tree-lookup tr 15) 15
(tree-lookup tr 16) 16
(tree-lookup tr 17) 17
(tree-lookup tr 18) 18
(tree-lookup tr 19) 19)
(vtest (build (for* ((i (tree-begin tr))
(n (tree-next i)))
(n)
((set n (tree-next i)))
(add (key n))))
(range 0 19))
(vtest (build (for* ((j (tree-begin tr))
(i (progn (tree-next j) (tree-next j) (tree-reset j tr)))
(n (tree-next i)))
(n)
((set n (tree-next i)))
(add (key n))))
(range 0 19))
(vtest (build (for* ((j (tree-begin tr))
(i (progn (tree-next j) (tree-next j) (tree-reset j tr)))
(n (tree-peek i)))
((and n (eq (tree-next i) n)))
((set n (tree-peek i)))
(add (key n))))
(range 0 19))
(defvarl trc (copy-search-tree tr))
(vtest trc tr)
(tree-clear trc)
(test trc #T(()))
(test (tree-delete tr 6) 6)
(vtest (build (for* ((i (tree-begin-at tr 6))
(n (tree-next i)))
(n)
((set n (tree-next i)))
(add (key n))))
(range 7 19))
(vtest (build (for* ((i (tree-begin-at tr 0))
(n (tree-next i)))
(n)
((set n (tree-next i)))
(add (key n))))
(rlist 0..5 7..19))
(vtest (build (for* ((i (tree-begin-at tr 8))
(n (tree-next i)))
(n)
((set n (tree-next i)))
(add (key n))))
(range 8 19))
(vtest (build (for* ((i (tree-reset-at (tree-begin #T(())) tr 8))
(n (tree-next i)))
(n)
((set n (tree-next i)))
(add (key n))))
(range 8 19))
(test (tree-next (tree-begin-at tr 20)) nil)
(test (tree-next (tree-begin-at #T(()) 0)) nil)
(test (key (tree-next (tree-begin-at #T(() 1) 1))) 1)
(mtest
(tree-delete tr 0) 0
(tree-delete tr 1) 1
(tree-delete tr 2) 2
(tree-delete tr 3) 3
(tree-delete tr 4) 4
(tree-delete tr 5) 5
(tree-delete tr 7) 7
(tree-delete tr 8) 8
(tree-delete tr 9) 9
(tree-delete tr 10) 10
(tree-delete tr 11) 11
(tree-delete tr 12) 12
(tree-delete tr 13) 13
(tree-delete tr 14) 14
(tree-delete tr 15) 15
(tree-delete tr 16) 16
(tree-delete tr 17) 17
(tree-delete tr 18) 18
(tree-delete tr 19) 19)
(set *tree-fun-whitelist* [list* '= '< *tree-fun-whitelist*])
(let ((tr [tree '(1 2 3) identity < =]))
(mtest
tr #T((identity < =) 1 2 3)
(copy-search-tree tr) #T((identity < =) 1 2 3)
(make-similar-tree tr) #T((identity < =))))
|
