xref: /6.6.0/geocouch/vtree/test/008-search.t (revision 92def13f)
1#!/usr/bin/env escript
2%% -*- erlang -*-
3%%! -na me insert@127.0.0.1
4
5% Licensed under the Apache License, Version 2.0 (the "License"); you may not
6% use this file except in compliance with the License. You may obtain a copy of
7% the License at
8%
9%   http://www.apache.org/licenses/LICENSE-2.0
10%
11% Unless required by applicable law or agreed to in writing, software
12% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
13% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
14% License for the specific language governing permissions and limitations under
15% the License.
16
17-include_lib("../include/vtree.hrl").
18
19-define(MOD, vtree_search).
20-define(FILENAME, "/tmp/vtree_search_vtree.bin").
21
22main(_) ->
23    % Apache CouchDB doesn't have the couch_file_write_guard module
24    try
25        couch_file_write_guard:sup_start_link()
26    catch error:undef ->
27        ok
28    end,
29
30    code:add_pathz(filename:dirname(escript:script_name())),
31    etap:plan(61),
32    case (catch test()) of
33        ok ->
34            etap:end_tests();
35        Other ->
36            % Somehow etap:diag/1 and etap:bail/1 don't work properly
37            %etap:diag(io_lib:format("Test died abnormally: ~p", [Other])),
38            %etap:bail(Other),
39            io:format(standard_error, "Test died abnormally:~n~p~n", [Other])
40     end.
41
42
43test() ->
44    test_search(),
45    test_all(),
46    test_count_search(),
47    test_count_all(),
48    test_traverse(),
49    test_traverse_kv(),
50    test_traverse_all(),
51    test_traverse_all_kv(),
52    test_any_box_intersects_mbb(),
53    test_boxes_intersect_mbb(),
54    ok.
55
56
57test_search() ->
58    rand:seed(exrop, {1, 11, 91}),
59
60    Fd = vtree_test_util:create_file(?FILENAME),
61    Less = fun(A, B) -> A < B end,
62    Vtree = #vtree{
63               fd = Fd,
64               kp_chunk_threshold = 2500,
65               kv_chunk_threshold = 2500,
66               min_fill_rate = 0.4,
67               less = Less
68              },
69    Boxes = [N#kv_node.key || N <- vtree_test_util:generate_kvnodes(4)],
70
71    FoldFun = fun(Node, Acc) -> {ok, [Node|Acc]} end,
72
73    etap:is(?MOD:search(Vtree, Boxes, FoldFun, []), [],
74            "Searching empty tree works"),
75
76    Nodes1 = vtree_test_util:generate_kvnodes(97),
77    Vtree1 = vtree_insert:insert(Vtree, Nodes1),
78    Result1 = ?MOD:search(Vtree1, Boxes, FoldFun, []),
79    etap:ok(length(Nodes1 -- Result1) > 1,
80            "Searching tree (97 items) returned a subset of the items"),
81
82    etap:is(?MOD:search(Vtree1, [], FoldFun, []), [],
83            "Searching with an empty list of boxes retrns empty result"),
84
85    couch_file:close(Fd).
86
87
88test_all() ->
89    rand:seed(exrop, {1, 11, 91}),
90
91    Fd = vtree_test_util:create_file(?FILENAME),
92    Less = fun(A, B) -> A < B end,
93    Vtree = #vtree{
94               fd = Fd,
95               kp_chunk_threshold = 2500,
96               kv_chunk_threshold = 2500,
97               min_fill_rate = 0.4,
98               less = Less
99              },
100    Boxes = [N#kv_node.key || N <- vtree_test_util:generate_kvnodes(4)],
101
102    FoldFun = fun(Node, Acc) -> {ok, [Node|Acc]} end,
103
104    etap:is(?MOD:all(Vtree, FoldFun, []), [],
105            "Return all items from empty tree works"),
106
107    Nodes1 = vtree_test_util:generate_kvnodes(5),
108    Vtree1 = vtree_insert:insert(Vtree, Nodes1),
109    Result1 = ?MOD:all(Vtree1, FoldFun, []),
110    etap:is(lists:sort(Result1), lists:sort(Nodes1),
111            "Returning all items (97) worked"),
112
113    Nodes2 = vtree_test_util:generate_kvnodes(3),
114    Vtree2 = vtree_insert:insert(Vtree, Nodes2),
115    Result2 = ?MOD:all(Vtree2, FoldFun, []),
116    etap:is(lists:sort(Result2), lists:sort(Nodes2),
117            "Returning all items (3) worked"),
118
119    couch_file:close(Fd).
120
121
122test_count_search() ->
123    rand:seed(exrop, {1, 11, 91}),
124
125    Fd = vtree_test_util:create_file(?FILENAME),
126    Less = fun(A, B) -> A < B end,
127    Vtree = #vtree{
128               fd = Fd,
129               kp_chunk_threshold = 2500,
130               kv_chunk_threshold = 2500,
131               min_fill_rate = 0.4,
132               less = Less
133              },
134
135    Boxes = [N#kv_node.key || N <- vtree_test_util:generate_kvnodes(4)],
136    ExpectedFun = fun(Nodes, Boxes) ->
137                          length(lists:filter(
138                                   fun(Node) ->
139                                           ?MOD:any_box_intersects_mbb(
140                                              Boxes, Node#kv_node.key, Less)
141                                   end, Nodes))
142                  end,
143
144    Nodes1 = vtree_test_util:generate_kvnodes(20),
145    Vtree1 = vtree_insert:insert(Vtree, Nodes1),
146    Boxes1 = [hd(Boxes)],
147    etap:is(?MOD:count_search(Vtree1, Boxes1), ExpectedFun(Nodes1, Boxes1),
148            "Count (tree with 20 items) with one box was correct"),
149    {Boxes2, _} = lists:split(2, Boxes),
150    etap:is(?MOD:count_search(Vtree1, Boxes2), ExpectedFun(Nodes1, Boxes2),
151            "Count (tree with 20 items) with two boxes was correct"),
152
153    Nodes2 = vtree_test_util:generate_kvnodes(137),
154    Vtree2 = vtree_insert:insert(Vtree, Nodes2),
155    etap:is(?MOD:count_search(Vtree2, Boxes1), ExpectedFun(Nodes2, Boxes1),
156            "Count (tree with 137 items) with one box was correct"),
157    etap:is(?MOD:count_search(Vtree2, Boxes), ExpectedFun(Nodes2, Boxes),
158            "Count (tree with 137 items) with four boxes was correct"),
159
160    Nodes3 = vtree_test_util:generate_kvnodes(4),
161    Vtree3 = vtree_insert:insert(Vtree, Nodes3),
162    etap:is(?MOD:count_search(Vtree3, Boxes1), ExpectedFun(Nodes3, Boxes1),
163            "Count (tree with 4 items) with one box was correct"),
164    etap:is(?MOD:count_search(Vtree3, Boxes), ExpectedFun(Nodes3, Boxes),
165            "Count (tree with 4 items) with four boxes was correct"),
166
167    etap:is(?MOD:count_search(Vtree, Boxes1), 0,
168            "Count (empty tree) with one box was correct"),
169    etap:is(?MOD:count_search(Vtree, Boxes), 0,
170            "Count (empty tree) with four boxes was correct"),
171
172    couch_file:close(Fd).
173
174
175test_count_all() ->
176    rand:seed(exrop, {1, 11, 91}),
177
178    Fd = vtree_test_util:create_file(?FILENAME),
179    Less = fun(A, B) -> A < B end,
180    Vtree = #vtree{
181               fd = Fd,
182               kp_chunk_threshold = 2500,
183               kv_chunk_threshold = 2500,
184               min_fill_rate = 0.4,
185               less = Less
186              },
187
188    etap:is(?MOD:count_all(Vtree), 0,
189            "Return all items from empty tree works"),
190
191    Nodes1 = vtree_test_util:generate_kvnodes(97),
192    Vtree1 = vtree_insert:insert(Vtree, Nodes1),
193    etap:is(?MOD:count_all(Vtree1), 97, "Returning all items (97) worked"),
194
195    Nodes2 = vtree_test_util:generate_kvnodes(3),
196    Vtree2 = vtree_insert:insert(Vtree, Nodes2),
197    etap:is(?MOD:count_all(Vtree2), 3, "Returning all items (3) worked"),
198
199    couch_file:close(Fd).
200
201
202test_traverse() ->
203    rand:seed(exrop, {1, 11, 91}),
204
205    Fd = vtree_test_util:create_file(?FILENAME),
206    Less = fun(A, B) -> A < B end,
207    Vtree = #vtree{
208               fd = Fd,
209               kp_chunk_threshold = 2500,
210               kv_chunk_threshold = 2500,
211               min_fill_rate = 0.4,
212               less = Less
213              },
214
215    FoldFun = fun(Node, Acc) -> {ok, [Node|Acc]} end,
216
217    Boxes = [N#kv_node.key || N <- vtree_test_util:generate_kvnodes(4)],
218    ExpectedFun = fun(Nodes, Boxes) ->
219                           lists:filter(
220                             fun(Node) ->
221                                     ?MOD:any_box_intersects_mbb(
222                                        Boxes, Node#kv_node.key, Less)
223                             end, Nodes)
224                   end,
225
226    Nodes1 = vtree_test_util:generate_kvnodes(20),
227    Vtree1 = vtree_insert:insert(Vtree, Nodes1),
228    Boxes1 = [hd(Boxes)],
229    Expected1 = ExpectedFun(Nodes1, Boxes1),
230    {ok, Result1} = ?MOD:traverse(
231                       Vtree1, [Vtree1#vtree.root], Boxes1, FoldFun, {ok, []}),
232    etap:is(lists:sort(Result1), lists:sort(Expected1),
233            "Traversing tree (20 items) with one box was correct"),
234
235    {Boxes2, _} = lists:split(2, Boxes),
236    Expected2 = ExpectedFun(Nodes1, Boxes2),
237    {ok, Result2} = ?MOD:traverse(
238                       Vtree1, [Vtree1#vtree.root], Boxes2, FoldFun, {ok, []}),
239    etap:is(lists:sort(Result2), lists:sort(Expected2),
240            "Traversing tree (20 items) with two boxes was correct"),
241
242
243    Nodes2 = vtree_test_util:generate_kvnodes(137),
244    Vtree2 = vtree_insert:insert(Vtree, Nodes2),
245    Expected3 = ExpectedFun(Nodes2, Boxes1),
246    {ok, Result3} = ?MOD:traverse(
247                       Vtree2, [Vtree2#vtree.root], Boxes1, FoldFun, {ok, []}),
248    etap:is(lists:sort(Result3), lists:sort(Expected3),
249            "Traversing tree (137 items) with one box was correct"),
250
251    Expected4 = ExpectedFun(Nodes2, Boxes),
252    {ok, Result4} = ?MOD:traverse(
253                       Vtree2, [Vtree2#vtree.root], Boxes, FoldFun, {ok, []}),
254    etap:is(lists:sort(Result4), lists:sort(Expected4),
255            "Traversing tree (137 items) with four boxes was correct"),
256
257    Nodes3 = vtree_test_util:generate_kvnodes(4),
258    Vtree3 = vtree_insert:insert(Vtree, Nodes3),
259    Expected5 = ExpectedFun(Nodes3, Boxes1),
260    {ok, Result5} = ?MOD:traverse(
261                       Vtree3, [Vtree3#vtree.root], Boxes1, FoldFun, {ok, []}),
262    etap:is(lists:sort(Result5), lists:sort(Expected5),
263            "Traversing tree (4 items) with one box was correct"),
264
265    Expected6 = ExpectedFun(Nodes3, Boxes),
266    {ok, Result6} = ?MOD:traverse(
267                       Vtree3, [Vtree3#vtree.root], Boxes, FoldFun, {ok, []}),
268    etap:is(lists:sort(Result6), lists:sort(Expected6),
269            "Traversing tree (4 items) with four boxes was correct"),
270
271    couch_file:close(Fd).
272
273
274test_traverse_kv() ->
275    rand:seed(exrop, {1, 11, 91}),
276
277    Less = fun(A, B) -> A < B end,
278    FoldFun = fun(Node, Acc) -> {ok, [Node|Acc]} end,
279
280    Boxes = [N#kv_node.key || N <- vtree_test_util:generate_kvnodes(4)],
281    ExpectedFun = fun(Nodes, Boxes) ->
282                           lists:filter(
283                             fun(Node) ->
284                                     ?MOD:any_box_intersects_mbb(
285                                        Boxes, Node#kv_node.key, Less)
286                             end, Nodes)
287                   end,
288
289    Nodes1 = vtree_test_util:generate_kvnodes(20),
290    Boxes1 = [hd(Boxes)],
291    Expected1 = ExpectedFun(Nodes1, Boxes1),
292    {ok, Result1} = ?MOD:traverse_kv(Less, Nodes1, Boxes1, FoldFun, {ok, []}),
293    etap:is(lists:sort(Result1), lists:sort(Expected1),
294            "Traversing tree (20 items) with one box was correct"),
295
296    {Boxes2, _} = lists:split(2, Boxes),
297    Expected2 = ExpectedFun(Nodes1, Boxes2),
298    {ok, Result2} = ?MOD:traverse_kv(Less, Nodes1, Boxes2, FoldFun, {ok, []}),
299    etap:is(lists:sort(Result2), lists:sort(Expected2),
300            "Traversing tree (20 items) with two boxes was correct"),
301
302
303    Nodes2 = vtree_test_util:generate_kvnodes(137),
304    Expected3 = ExpectedFun(Nodes2, Boxes1),
305    {ok, Result3} = ?MOD:traverse_kv(Less, Nodes2, Boxes1, FoldFun, {ok, []}),
306    etap:is(lists:sort(Result3), lists:sort(Expected3),
307            "Traversing tree (137 items) with one box was correct"),
308
309    Expected4 = ExpectedFun(Nodes2, Boxes),
310    {ok, Result4} = ?MOD:traverse_kv(Less, Nodes2, Boxes, FoldFun, {ok, []}),
311    etap:is(lists:sort(Result4), lists:sort(Expected4),
312            "Traversing tree (137 items) with four boxes was correct"),
313
314    Nodes3 = vtree_test_util:generate_kvnodes(4),
315    Expected5 = ExpectedFun(Nodes3, Boxes1),
316    {ok, Result5} = ?MOD:traverse_kv(Less, Nodes3, Boxes1, FoldFun, {ok, []}),
317    etap:is(lists:sort(Result5), lists:sort(Expected5),
318            "Traversing tree (4 items) with one box was correct"),
319
320    Expected6 = ExpectedFun(Nodes3, Boxes),
321    {ok, Result6} = ?MOD:traverse_kv(Less, Nodes3, Boxes, FoldFun, {ok, []}),
322    etap:is(lists:sort(Result6), lists:sort(Expected6),
323            "Traversing tree (4 items) with four boxes was correct"),
324
325    Result7 = ?MOD:traverse_kv(Less, Nodes1, Boxes1, FoldFun, {stop, []}),
326    etap:is(Result7, {stop, []},
327            "Traversing tree (20 items) with one box was correct, but "
328            "using the `stop` as initial accummulator"),
329
330    Result8 = ?MOD:traverse_kv(Less, Nodes3, Boxes, FoldFun, {stop, foo}),
331    etap:is(Result8, {stop, foo},
332            "Traversing tree (4 items) with four boxes was correct, but "
333            "using `stop` as initial accummulator").
334
335
336test_traverse_all() ->
337    rand:seed(exrop, {1, 11, 91}),
338
339    Fd = vtree_test_util:create_file(?FILENAME),
340    Less = fun(A, B) -> A < B end,
341    Vtree = #vtree{
342               fd = Fd,
343               kp_chunk_threshold = 3000,
344               kv_chunk_threshold = 3000,
345               min_fill_rate = 0.4,
346               less = Less
347              },
348
349    FoldFun = fun(Node, Acc) -> {ok, [Node|Acc]} end,
350
351    Nodes1 = vtree_test_util:generate_kvnodes(20),
352    Vtree1 = vtree_insert:insert(Vtree, Nodes1),
353    {ok, Result1} = ?MOD:traverse_all(
354                       Vtree1, [Vtree1#vtree.root], FoldFun, {ok, []}),
355    etap:is(lists:sort(Result1), lists:sort(Nodes1),
356            "Traversing tree (20 items) was correct"),
357
358    Nodes2 = vtree_test_util:generate_kvnodes(137),
359    Vtree2 = vtree_insert:insert(Vtree, Nodes2),
360    {ok, Result3} = ?MOD:traverse_all(
361                       Vtree2, [Vtree2#vtree.root], FoldFun, {ok, []}),
362    etap:is(lists:sort(Result3), lists:sort(Nodes2),
363            "Traversing tree (137 items) was correct"),
364
365    Nodes3 = vtree_test_util:generate_kvnodes(4),
366    Vtree3 = vtree_insert:insert(Vtree, Nodes3),
367    {ok, Result5} = ?MOD:traverse_all(
368                       Vtree3, [Vtree3#vtree.root], FoldFun, {ok, []}),
369    etap:is(lists:sort(Result5), lists:sort(Nodes3),
370            "Traversing tree (4 items) with one box was correct"),
371
372    couch_file:close(Fd).
373
374
375test_traverse_all_kv() ->
376    rand:seed(exrop, {1, 11, 91}),
377
378    FoldFun = fun(Node, Acc) -> {ok, [Node|Acc]} end,
379
380    Nodes1 = vtree_test_util:generate_kvnodes(20),
381    {ok, Result1} = ?MOD:traverse_all_kv(Nodes1, FoldFun, {ok, []}),
382    etap:is(lists:sort(Result1), lists:sort(Nodes1),
383            "Traversing tree (20 items) was correct"),
384
385    Nodes2 = vtree_test_util:generate_kvnodes(137),
386    {ok, Result3} = ?MOD:traverse_all_kv(Nodes2, FoldFun, {ok, []}),
387    etap:is(lists:sort(Result3), lists:sort(Nodes2),
388            "Traversing tree (137 items) was correct"),
389
390    Nodes3 = vtree_test_util:generate_kvnodes(4),
391    {ok, Result5} = ?MOD:traverse_all_kv(Nodes3, FoldFun, {ok, []}),
392    etap:is(lists:sort(Result5), lists:sort(Nodes3),
393            "Traversing tree (4 items) was correct"),
394
395    Result7 = ?MOD:traverse_all_kv(Nodes1, FoldFun, {stop, []}),
396    etap:is(Result7, {stop, []},
397            "Traversing tree (20 items) was correct, but "
398            "using the `stop` as initial accummulator"),
399
400    Result8 = ?MOD:traverse_all_kv(Nodes3, FoldFun, {stop, bar}),
401    etap:is(Result8, {stop, bar},
402            "Traversing tree (4 items) was correct, but "
403            "using the `stop` as initial accummulator").
404
405
406test_any_box_intersects_mbb() ->
407    Less = fun(A, B) -> A < B end,
408
409    Mbb1 = [{-38, 74.2}, {38, 948}],
410    Mbb2 = [{-480, 5}, {-7, 428.74}],
411    Mbb3 = [{84.3, 923.8}, {39, 938}],
412    Mbb4 = [{-937, 8424}, {-1000, -82}],
413    Mbb5 = [{-100.72, -5}, {-2, 39.3}],
414    Mbb6 = [{222, 222}, {-432.39, -294.20}],
415
416    etap:is(?MOD:any_box_intersects_mbb([Mbb1], Mbb2, Less), true,
417            "One box intersects MBB"),
418    etap:is(?MOD:any_box_intersects_mbb([Mbb3], Mbb2, Less), false,
419            "One box doesn't intersect MBB"),
420    etap:is(?MOD:any_box_intersects_mbb([Mbb1, Mbb3], Mbb2, Less), true,
421            "First of two boxes intersects MBB"),
422    etap:is(?MOD:any_box_intersects_mbb([Mbb3, Mbb1], Mbb2, Less), true,
423            "Second of two boxes intersects MBB"),
424    etap:is(?MOD:any_box_intersects_mbb([Mbb4, Mbb3], Mbb2, Less), false,
425            "None of two boxes intersects MBB"),
426    etap:is(?MOD:any_box_intersects_mbb([Mbb1, Mbb5], Mbb2, Less), true,
427            "Two of two boxes intersects MBB"),
428
429    etap:is(?MOD:any_box_intersects_mbb([Mbb2, Mbb3, Mbb4], Mbb1, Less), true,
430            "First of three boxes intersects MBB"),
431    etap:is(?MOD:any_box_intersects_mbb([Mbb3, Mbb2, Mbb4], Mbb1, Less), true,
432            "Second of three boxes intersects MBB"),
433    etap:is(?MOD:any_box_intersects_mbb([Mbb3, Mbb4, Mbb2], Mbb1, Less), true,
434            "Third of three boxes intersects MBB"),
435    etap:is(?MOD:any_box_intersects_mbb([Mbb2, Mbb4, Mbb5], Mbb1, Less), true,
436            "First and last of three boxes intersects MBB"),
437    etap:is(?MOD:any_box_intersects_mbb([Mbb3, Mbb4, Mbb6], Mbb1, Less), false,
438            "None of three boxes intersects MBB").
439
440
441test_boxes_intersect_mbb() ->
442    Less = fun(A, B) -> A < B end,
443
444    Mbb1 = [{-38, 74.2}, {38, 948}],
445    Mbb2 = [{-480, 5}, {-7, 428.74}],
446    Mbb3 = [{84.3, 923.8}, {39, 938}],
447    Mbb4 = [{-937, 8424}, {-1000, -82}],
448    Mbb5 = [{-100.72, -5}, {-2, 39.3}],
449    Mbb6 = [{222, 222}, {-432.39, -294.20}],
450
451    etap:is(?MOD:boxes_intersect_mbb([Mbb1], Mbb2, Less), [Mbb1],
452            "One box intersects MBB"),
453    etap:is(?MOD:boxes_intersect_mbb([Mbb3], Mbb2, Less), [],
454            "One box doesn't intersect MBB"),
455    etap:is(?MOD:boxes_intersect_mbb([Mbb1, Mbb3], Mbb2, Less), [Mbb1],
456            "First of two boxes intersects MBB"),
457    etap:is(?MOD:boxes_intersect_mbb([Mbb3, Mbb1], Mbb2, Less), [Mbb1],
458            "Second of two boxes intersects MBB"),
459    etap:is(?MOD:boxes_intersect_mbb([Mbb4, Mbb3], Mbb2, Less), [],
460            "None of two boxes intersects MBB"),
461    etap:is(?MOD:boxes_intersect_mbb([Mbb1, Mbb5], Mbb2, Less), [Mbb1, Mbb5],
462            "Two of two boxes intersects MBB"),
463
464    etap:is(?MOD:boxes_intersect_mbb([Mbb2, Mbb3, Mbb4], Mbb1, Less), [Mbb2],
465            "First of three boxes intersects MBB"),
466    etap:is(?MOD:boxes_intersect_mbb([Mbb3, Mbb2, Mbb4], Mbb1, Less), [Mbb2],
467            "Second of three boxes intersects MBB"),
468    etap:is(?MOD:boxes_intersect_mbb([Mbb3, Mbb4, Mbb2], Mbb1, Less), [Mbb2],
469            "Third of three boxes intersects MBB"),
470    etap:is(?MOD:boxes_intersect_mbb([Mbb2, Mbb4, Mbb5], Mbb1, Less),
471            [Mbb2, Mbb5],
472            "First and last of three boxes intersects MBB"),
473    etap:is(?MOD:boxes_intersect_mbb([Mbb3, Mbb4, Mbb6], Mbb1, Less), [],
474            "None of three boxes intersects MBB").
475