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