1aafe1788SVolker Mische% Licensed under the Apache License, Version 2.0 (the "License"); you may not
2aafe1788SVolker Mische% use this file except in compliance with the License. You may obtain a copy of
3aafe1788SVolker Mische% the License at
4aafe1788SVolker Mische%
5aafe1788SVolker Mische%   http://www.apache.org/licenses/LICENSE-2.0
6aafe1788SVolker Mische%
7aafe1788SVolker Mische% Unless required by applicable law or agreed to in writing, software
8aafe1788SVolker Mische% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
9aafe1788SVolker Mische% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
10aafe1788SVolker Mische% License for the specific language governing permissions and limitations under
11aafe1788SVolker Mische% the License.
12aafe1788SVolker Mische
13aafe1788SVolker Mische% This module implements the querying of the vtree. It follows the rules of
14aafe1788SVolker Mische% the standard R-tree. The only difference is that you can query with multiple
15aafe1788SVolker Mische% bounding boxes at the same time. This is useful if you have queries over
16aafe1788SVolker Mische% the dateline and want to decompose it into two separate bounding boxes
17aafe1788SVolker Mische
18aafe1788SVolker Mische-module(vtree_search).
19aafe1788SVolker Mische
20aafe1788SVolker Mische-include("vtree.hrl").
21aafe1788SVolker Mische
22bb9333d5SVolker Mische-export([search/4, all/3, count_search/2, count_all/1]).
23aafe1788SVolker Mische
24aafe1788SVolker Mische-ifdef(makecheck).
25263b2ce8STimofey Barmin-compile(nowarn_export_all).
26aafe1788SVolker Mische-compile(export_all).
27aafe1788SVolker Mische-endif.
28aafe1788SVolker Mische
29bb9333d5SVolker Mische-type foldfun() :: fun((#kv_node{} | #kp_node{}, any()) -> {ok | stop, any()}).
30aafe1788SVolker Mische
31aafe1788SVolker Mische
32bb9333d5SVolker Mische-spec search(Vt :: #vtree{}, Boxes :: [mbb()], FoldFun :: foldfun(),
33bb9333d5SVolker Mische             InitAcc :: any()) -> any().
34bb9333d5SVolker Mischesearch(#vtree{root=nil}, _Boxes, _FoldFun, InitAcc) ->
35bb9333d5SVolker Mische    InitAcc;
36bb9333d5SVolker Mischesearch(Vt, Boxes, FoldFun, InitAcc) ->
37bb9333d5SVolker Mische    {_, Acc} = traverse(Vt, [Vt#vtree.root], Boxes, FoldFun, {ok, InitAcc}),
38bb9333d5SVolker Mische    Acc.
39aafe1788SVolker Mische
40bb9333d5SVolker Mische
41bb9333d5SVolker Mische% No bounding box given, return everything
42bb9333d5SVolker Mische-spec all(Vt :: #vtree{}, FoldFun :: foldfun(), InitAcc :: any()) -> any().
43bb9333d5SVolker Mischeall(#vtree{root=nil}, _FoldFun, InitAcc) ->
44bb9333d5SVolker Mische    InitAcc;
45bb9333d5SVolker Mischeall(Vt, FoldFun, InitAcc) ->
46bb9333d5SVolker Mische    {_, Acc} = traverse_all(Vt, [Vt#vtree.root], FoldFun, {ok, InitAcc}),
47bb9333d5SVolker Mische    Acc.
48bb9333d5SVolker Mische
49bb9333d5SVolker Mische
50bb9333d5SVolker Mische% Returns only the number of matching geometries (and not the geometries
51bb9333d5SVolker Mische% themselves)
52bb9333d5SVolker Mische-spec count_search(Vt :: #vtree{}, Boxes :: [mbb()]) -> non_neg_integer().
53bb9333d5SVolker Mischecount_search(Vt, Boxes) ->
54bb9333d5SVolker Mische    search(Vt, Boxes, fun(_Node, Acc) -> {ok, Acc+1} end, 0).
55bb9333d5SVolker Mische
56bb9333d5SVolker Mische
57bb9333d5SVolker Mische% Returns the number all geometries (and not the geometries themselves)
58bb9333d5SVolker Mische-spec count_all(Vt :: #vtree{}) -> non_neg_integer().
59bb9333d5SVolker Mischecount_all(Vt) ->
60bb9333d5SVolker Mische    all(Vt, fun(_Node, Acc) -> {ok, Acc+1} end, 0).
61bb9333d5SVolker Mische
62bb9333d5SVolker Mische
63bb9333d5SVolker Mische% The accumulator is always a 2-tuple with eith 'ok' or 'stop' and the actual
64bb9333d5SVolker Mische% value.
65aafe1788SVolker Mische-spec traverse(Vt :: #vtree{}, Nodes :: [#kv_node{} | #kp_node{}],
66bb9333d5SVolker Mische               Boxes :: [mbb()], FoldFun :: foldfun(),
67bb9333d5SVolker Mische               InitAcc :: {ok |stop, any()}) -> {ok | stop, any()}.
68bb9333d5SVolker Mischetraverse(_Vt, _Nodes, _Boxes, _FoldFun, {stop, Acc}) ->
69bb9333d5SVolker Mische    {stop, Acc};
70bb9333d5SVolker Mischetraverse(_Vt, [], _Boxes, _FoldFun, OkAcc) ->
71bb9333d5SVolker Mische    OkAcc;
726cdacbf8SVolker Mischetraverse(Vt, [#kv_node{}|_]=Nodes, Boxes, FoldFun, OkAcc) ->
73f6402621SVolker Mische    traverse_kv(Vt#vtree.less, Nodes, Boxes, FoldFun, OkAcc);
74bb9333d5SVolker Mischetraverse(Vt, [#kp_node{}=Node|Rest], Boxes, FoldFun, OkAcc) ->
75aafe1788SVolker Mische    #vtree{
76aafe1788SVolker Mische          less = Less,
77aafe1788SVolker Mische          fd = Fd
78aafe1788SVolker Mische         } = Vt,
79bb9333d5SVolker Mische    Result = case boxes_intersect_mbb(Boxes, Node#kp_node.key, Less) of
80bb9333d5SVolker Mische                 [] ->
81bb9333d5SVolker Mische                    % No box intersects, stop moving deeper
829505c458SVolker Mische                    OkAcc;
83bb9333d5SVolker Mische                 IntersectingBoxes ->
84bb9333d5SVolker Mische                     Children = vtree_io:read_node(
85bb9333d5SVolker Mische                                  Fd, Node#kp_node.childpointer),
86bb9333d5SVolker Mische                     % Move deeper
87bb9333d5SVolker Mische                     traverse(Vt, Children, IntersectingBoxes, FoldFun, OkAcc)
88bb9333d5SVolker Mische             end,
89bb9333d5SVolker Mische    % Move sideways
90bb9333d5SVolker Mische    traverse(Vt, Rest, Boxes, FoldFun, Result).
91bb9333d5SVolker Mische
92f6402621SVolker Mische-spec traverse_kv(Less :: lessfun(), Nodes :: [#kv_node{}], Boxes :: [mbb()],
93f6402621SVolker Mische                  FoldFun :: foldfun(), InitAcc :: {ok |stop, any()}) ->
94f6402621SVolker Mische                         {ok | stop, any()}.
95f6402621SVolker Mischetraverse_kv(_Less, _Nodes, _Boxes, _FoldFun, {stop, Acc}) ->
96f6402621SVolker Mische    {stop, Acc};
97f6402621SVolker Mischetraverse_kv(_Less, [], _Boxes, _FoldFun, OkAcc) ->
98f6402621SVolker Mische    OkAcc;
99f6402621SVolker Mischetraverse_kv(Less, [Node|Rest], Boxes, FoldFun, {ok, Acc}) ->
100f6402621SVolker Mische    Result = case any_box_intersects_mbb(
101f6402621SVolker Mische                    Boxes, Node#kv_node.key, Less) of
102f6402621SVolker Mische                 true ->
103f6402621SVolker Mische                     FoldFun(Node, Acc);
104f6402621SVolker Mische                 false ->
105f6402621SVolker Mische                     {ok, Acc}
106f6402621SVolker Mische             end,
107f6402621SVolker Mische    traverse_kv(Less, Rest, Boxes, FoldFun, Result).
108f6402621SVolker Mische
109bb9333d5SVolker Mische
110bb9333d5SVolker Mische% Traverse the full tree without any bounding box
111bb9333d5SVolker Mische-spec traverse_all(Vt :: #vtree{}, Nodes :: [#kv_node{} | #kp_node{}],
112bb9333d5SVolker Mische                   FoldFun :: foldfun(), InitAcc :: {ok |stop, any()}) ->
113bb9333d5SVolker Mische                          {ok | stop, any()}.
114bb9333d5SVolker Mischetraverse_all(_Vt, _Nodes, _FoldFun, {stop, Acc}) ->
115bb9333d5SVolker Mische    {stop, Acc};
116bb9333d5SVolker Mischetraverse_all(_Vt, [], _FoldFun, OkAcc) ->
117bb9333d5SVolker Mische    OkAcc;
1186cdacbf8SVolker Mischetraverse_all(_Vt, [#kv_node{}|_]=Nodes, FoldFun, OkAcc) ->
119f6402621SVolker Mische    traverse_all_kv(Nodes, FoldFun, OkAcc);
120bb9333d5SVolker Mischetraverse_all(Vt, [#kp_node{}=Node|Rest], FoldFun, OkAcc) ->
121bb9333d5SVolker Mische    Children = vtree_io:read_node(Vt#vtree.fd, Node#kp_node.childpointer),
122bb9333d5SVolker Mische    % Move deeper
123bb9333d5SVolker Mische    Result = traverse_all(Vt, Children, FoldFun, OkAcc),
124aafe1788SVolker Mische    % Move sideways
125bb9333d5SVolker Mische    traverse_all(Vt, Rest, FoldFun, Result).
126aafe1788SVolker Mische
127f6402621SVolker Mische-spec traverse_all_kv(Nodes :: [#kv_node{}], FoldFun :: foldfun(),
128f6402621SVolker Mische                      InitAcc :: {ok |stop, any()}) ->
129f6402621SVolker Mische                             {ok | stop, any()}.
130f6402621SVolker Mischetraverse_all_kv(_Nodes, _FoldFun, {stop, Acc}) ->
131f6402621SVolker Mische    {stop, Acc};
132f6402621SVolker Mischetraverse_all_kv([], _FoldFun, OkAcc) ->
133f6402621SVolker Mische    OkAcc;
134f6402621SVolker Mischetraverse_all_kv([#kv_node{}=Node|Rest], FoldFun, {ok, Acc}) ->
135f6402621SVolker Mische    Result = FoldFun(Node, Acc),
136f6402621SVolker Mische    traverse_all_kv(Rest, FoldFun, Result).
137f6402621SVolker Mische
138aafe1788SVolker Mische
139aafe1788SVolker Mische% Returns true if any of the boxes intersects the MBB
140aafe1788SVolker Mische-spec any_box_intersects_mbb(Boxes :: [mbb()], Mbb :: mbb(),
141aafe1788SVolker Mische                             Less :: lessfun()) -> boolean().
142aafe1788SVolker Mischeany_box_intersects_mbb([], _Mbb, _Less) ->
143aafe1788SVolker Mische    false;
144aafe1788SVolker Mischeany_box_intersects_mbb([Box|Boxes], Mbb, Less) ->
145aafe1788SVolker Mische    case vtree_util:intersect_mbb(Box, Mbb, Less) of
146aafe1788SVolker Mische        overlapfree ->
147aafe1788SVolker Mische            any_box_intersects_mbb(Boxes, Mbb, Less);
148aafe1788SVolker Mische        _ -> true
149aafe1788SVolker Mische    end.
150aafe1788SVolker Mische
151aafe1788SVolker Mische
152aafe1788SVolker Mische% Returns all boxes that intersect a given MBB
1536cdacbf8SVolker Mische-spec boxes_intersect_mbb(Boxes :: [mbb()], Mbb :: mbb() | nil,
154aafe1788SVolker Mische                          Less :: lessfun()) -> [mbb()].
1556cdacbf8SVolker Mischeboxes_intersect_mbb(Boxes, nil, _Less) ->
1566cdacbf8SVolker Mische    Boxes;
157aafe1788SVolker Mischeboxes_intersect_mbb(Boxes, Mbb, Less) ->
158aafe1788SVolker Mische    lists:filter(fun(Box) ->
159aafe1788SVolker Mische                         case vtree_util:intersect_mbb(Box, Mbb, Less) of
160aafe1788SVolker Mische                             overlapfree -> false;
161aafe1788SVolker Mische                             _ -> true
162aafe1788SVolker Mische                         end
163aafe1788SVolker Mische                 end, Boxes).