1 ! (c) 2009 Joe Groff, see BSD license
2 USING: assocs kernel tools.test quadtrees math.rectangles sorting ;
5 : unit-bounds ( -- rect ) { -1.0 -1.0 } { 2.0 2.0 } <rect> ;
7 : value>>key ( assoc value key -- assoc )
9 : delete>>key ( assoc key -- assoc )
10 over delete-at ; inline
12 [ T{ quadtree f T{ rect f { -1.0 -1.0 } { 2.0 2.0 } } { 0.0 -0.25 } "a" f f f f t } ]
14 unit-bounds <quadtree>
15 "a" { 0.0 -0.25 } value>>key
18 [ T{ quadtree f T{ rect f { -1.0 -1.0 } { 2.0 2.0 } } { 0.0 -0.25 } "b" f f f f t } ]
20 unit-bounds <quadtree>
21 "a" { 0.0 -0.25 } value>>key
22 "b" { 0.0 -0.25 } value>>key
25 [ T{ quadtree f T{ rect f { -1.0 -1.0 } { 2.0 2.0 } } f f
26 T{ quadtree f T{ rect f { -1.0 -1.0 } { 1.0 1.0 } } { -0.5 -0.75 } "c" f f f f t }
27 T{ quadtree f T{ rect f { 0.0 -1.0 } { 1.0 1.0 } } { 0.0 -0.25 } "a" f f f f t }
28 T{ quadtree f T{ rect f { -1.0 0.0 } { 1.0 1.0 } } f f f f f f t }
29 T{ quadtree f T{ rect f { 0.0 0.0 } { 1.0 1.0 } } { 0.25 0.25 } "b" f f f f t }
32 unit-bounds <quadtree>
33 "a" { 0.0 -0.25 } value>>key
34 "b" { 0.25 0.25 } value>>key
35 "c" { -0.5 -0.75 } value>>key
38 [ T{ quadtree f T{ rect f { -1.0 -1.0 } { 2.0 2.0 } } f f
39 T{ quadtree f T{ rect f { -1.0 -1.0 } { 1.0 1.0 } } { -0.5 -0.75 } "c" f f f f t }
40 T{ quadtree f T{ rect f { 0.0 -1.0 } { 1.0 1.0 } } { 0.0 -0.25 } "a" f f f f t }
41 T{ quadtree f T{ rect f { -1.0 0.0 } { 1.0 1.0 } } f f f f f f t }
42 T{ quadtree f T{ rect f { 0.0 0.0 } { 1.0 1.0 } } f f
43 T{ quadtree f T{ rect f { 0.0 0.0 } { 0.5 0.5 } } { 0.25 0.25 } "b" f f f f t }
44 T{ quadtree f T{ rect f { 0.5 0.0 } { 0.5 0.5 } } { 0.75 0.25 } "d" f f f f t }
45 T{ quadtree f T{ rect f { 0.0 0.5 } { 0.5 0.5 } } f f f f f f t }
46 T{ quadtree f T{ rect f { 0.5 0.5 } { 0.5 0.5 } } f f f f f f t }
50 unit-bounds <quadtree>
51 "a" { 0.0 -0.25 } value>>key
52 "b" { 0.25 0.25 } value>>key
53 "c" { -0.5 -0.75 } value>>key
54 "d" { 0.75 0.25 } value>>key
58 unit-bounds <quadtree>
59 "a" { 0.0 -0.25 } value>>key
60 "b" { 0.25 0.25 } value>>key
61 "c" { -0.5 -0.75 } value>>key
62 "d" { 0.75 0.25 } value>>key
64 { 0.25 0.25 } swap at*
68 unit-bounds <quadtree>
69 "a" { 0.0 -0.25 } value>>key
70 "b" { 0.25 0.25 } value>>key
71 "c" { -0.5 -0.75 } value>>key
72 "d" { 0.75 0.25 } value>>key
78 unit-bounds <quadtree>
79 "a" { 0.0 -0.25 } value>>key
80 "b" { 0.25 0.25 } value>>key
81 "c" { -0.5 -0.75 } value>>key
82 "d" { 0.75 0.25 } value>>key
84 { -0.6 -0.8 } { 0.8 1.0 } <rect> swap in-rect natural-sort
87 [ T{ quadtree f T{ rect f { -1.0 -1.0 } { 2.0 2.0 } } f f
88 T{ quadtree f T{ rect f { -1.0 -1.0 } { 1.0 1.0 } } { -0.5 -0.75 } "c" f f f f t }
89 T{ quadtree f T{ rect f { 0.0 -1.0 } { 1.0 1.0 } } { 0.0 -0.25 } "a" f f f f t }
90 T{ quadtree f T{ rect f { -1.0 0.0 } { 1.0 1.0 } } f f f f f f t }
91 T{ quadtree f T{ rect f { 0.0 0.0 } { 1.0 1.0 } } { 0.75 0.25 } "d" f f f f t }
94 unit-bounds <quadtree>
95 "a" { 0.0 -0.25 } value>>key
96 "b" { 0.25 0.25 } value>>key
97 "c" { -0.5 -0.75 } value>>key
98 "d" { 0.75 0.25 } value>>key
100 { 0.25 0.25 } delete>>key
104 [ T{ quadtree f T{ rect f { -1.0 -1.0 } { 2.0 2.0 } } f f
105 T{ quadtree f T{ rect f { -1.0 -1.0 } { 1.0 1.0 } } { -0.5 -0.75 } "c" f f f f t }
106 T{ quadtree f T{ rect f { 0.0 -1.0 } { 1.0 1.0 } } { 0.0 -0.25 } "a" f f f f t }
107 T{ quadtree f T{ rect f { -1.0 0.0 } { 1.0 1.0 } } f f f f f f t }
108 T{ quadtree f T{ rect f { 0.0 0.0 } { 1.0 1.0 } } f f f f f f t }
111 unit-bounds <quadtree>
112 "a" { 0.0 -0.25 } value>>key
113 "b" { 0.25 0.25 } value>>key
114 "c" { -0.5 -0.75 } value>>key
115 "d" { 0.75 0.25 } value>>key
117 { 0.25 0.25 } delete>>key
118 { 0.75 0.25 } delete>>key
122 [ T{ quadtree f T{ rect f { -1.0 -1.0 } { 2.0 2.0 } } f f
123 T{ quadtree f T{ rect f { -1.0 -1.0 } { 1.0 1.0 } } f f
124 T{ quadtree f T{ rect f { -1.0 -1.0 } { 0.5 0.5 } } { -0.75 -0.75 } "b" f f f f t }
125 T{ quadtree f T{ rect f { -0.5 -1.0 } { 0.5 0.5 } } f f f f f f t }
126 T{ quadtree f T{ rect f { -1.0 -0.5 } { 0.5 0.5 } } f f f f f f t }
127 T{ quadtree f T{ rect f { -0.5 -0.5 } { 0.5 0.5 } } { -0.25 -0.25 } "a" f f f f t }
130 T{ quadtree f T{ rect f { 0.0 -1.0 } { 1.0 1.0 } } f f
131 T{ quadtree f T{ rect f { 0.0 -1.0 } { 0.5 0.5 } } f f f f f f t }
132 T{ quadtree f T{ rect f { 0.5 -1.0 } { 0.5 0.5 } } { 0.75 -0.75 } "f" f f f f t }
133 T{ quadtree f T{ rect f { 0.0 -0.5 } { 0.5 0.5 } } { 0.25 -0.25 } "e" f f f f t }
134 T{ quadtree f T{ rect f { 0.5 -0.5 } { 0.5 0.5 } } f f f f f f t }
137 T{ quadtree f T{ rect f { -1.0 0.0 } { 1.0 1.0 } } f f
138 T{ quadtree f T{ rect f { -1.0 0.0 } { 0.5 0.5 } } f f f f f f t }
139 T{ quadtree f T{ rect f { -0.5 0.0 } { 0.5 0.5 } } { -0.25 0.25 } "c" f f f f t }
140 T{ quadtree f T{ rect f { -1.0 0.5 } { 0.5 0.5 } } { -0.75 0.75 } "d" f f f f t }
141 T{ quadtree f T{ rect f { -0.5 0.5 } { 0.5 0.5 } } f f f f f f t }
144 T{ quadtree f T{ rect f { 0.0 0.0 } { 1.0 1.0 } } f f
145 T{ quadtree f T{ rect f { 0.0 0.0 } { 0.5 0.5 } } { 0.25 0.25 } "g" f f f f t }
146 T{ quadtree f T{ rect f { 0.5 0.0 } { 0.5 0.5 } } f f f f f f t }
147 T{ quadtree f T{ rect f { 0.0 0.5 } { 0.5 0.5 } } f f f f f f t }
148 T{ quadtree f T{ rect f { 0.5 0.5 } { 0.5 0.5 } } { 0.75 0.75 } "h" f f f f t }
153 unit-bounds <quadtree>
154 "a" { -0.25 -0.25 } value>>key
155 "b" { -0.75 -0.75 } value>>key
156 "c" { -0.25 0.25 } value>>key
157 "d" { -0.75 0.75 } value>>key
158 "e" { 0.25 -0.25 } value>>key
159 "f" { 0.75 -0.75 } value>>key
160 "g" { 0.25 0.25 } value>>key
161 "h" { 0.75 0.75 } value>>key
167 unit-bounds <quadtree>
168 "a" { -0.25 -0.25 } value>>key
169 "b" { -0.75 -0.75 } value>>key
170 "c" { -0.25 0.25 } value>>key
171 "d" { -0.75 0.75 } value>>key
172 "e" { 0.25 -0.25 } value>>key
173 "f" { 0.75 -0.75 } value>>key
174 "g" { 0.25 0.25 } value>>key
175 "h" { 0.75 0.75 } value>>key
181 { { -0.75 -0.75 } "b" }
182 { { -0.75 0.75 } "d" }
183 { { -0.25 -0.25 } "a" }
184 { { -0.25 0.25 } "c" }
185 { { 0.25 -0.25 } "e" }
186 { { 0.25 0.25 } "g" }
187 { { 0.75 -0.75 } "f" }
188 { { 0.75 0.75 } "h" }
190 unit-bounds <quadtree>
191 "a" { -0.25 -0.25 } value>>key
192 "b" { -0.75 -0.75 } value>>key
193 "c" { -0.25 0.25 } value>>key
194 "d" { -0.75 0.75 } value>>key
195 "e" { 0.25 -0.25 } value>>key
196 "f" { 0.75 -0.75 } value>>key
197 "g" { 0.25 0.25 } value>>key
198 "h" { 0.75 0.75 } value>>key