1 package com.github.davidmoten.rtree;
2
3 import static com.github.davidmoten.rtree.RTreeTest.e;
4 import static org.junit.Assert.assertEquals;
5 import static org.junit.Assert.assertTrue;
6
7 import java.util.ArrayList;
8 import java.util.Arrays;
9 import java.util.Collections;
10 import java.util.HashSet;
11 import java.util.List;
12 import java.util.Set;
13
14 import org.junit.Test;
15 import org.mockito.Mockito;
16
17 import com.github.davidmoten.junit.Asserts;
18 import com.github.davidmoten.rtree.geometry.Geometry;
19 import com.github.davidmoten.rtree.geometry.Rectangle;
20 import com.github.davidmoten.rtree.internal.util.ImmutableStack;
21
22 import rx.Subscriber;
23 import rx.Subscription;
24 import rx.functions.Func1;
25
26 public class BackpressureTest {
27
28 @Test
29 public void testConstructorIsPrivate() {
30 Asserts.assertIsUtilityClass(Backpressure.class);
31 }
32
33 @SuppressWarnings("unchecked")
34 @Test
35 public void testBackpressureSearch() {
36 Subscriber<Object> sub = Mockito.mock(Subscriber.class);
37 ImmutableStack<NodePosition<Object, Geometry>> stack = ImmutableStack.empty();
38 Func1<Geometry, Boolean> condition = Mockito.mock(Func1.class);
39 Backpressure.search(condition, sub, stack, 1);
40 Mockito.verify(sub, Mockito.never()).onNext(Mockito.any());
41 }
42
43 @Test
44 public void testBackpressureSearchNodeWithConditionThatAlwaysReturnsFalse() {
45 RTree<Object, Rectangle> tree = RTree.maxChildren(3).<Object, Rectangle> create()
46 .add(e(1)).add(e(3)).add(e(5)).add(e(7));
47
48 Set<Entry<Object, Rectangle>> found = new HashSet<Entry<Object, Rectangle>>();
49 tree.search(e(1).geometry()).subscribe(backpressureSubscriber(found));
50 assertEquals(1, found.size());
51 }
52
53 @SuppressWarnings("unchecked")
54 @Test
55 public void testRequestZero() {
56 Subscriber<Object> sub = new Subscriber<Object>() {
57
58 @Override
59 public void onCompleted() {
60 }
61
62 @Override
63 public void onError(Throwable e) {
64 }
65
66 @Override
67 public void onNext(Object t) {
68
69 }
70 };
71 sub.add(new Subscription() {
72 volatile boolean subscribed = true;
73
74 @Override
75 public void unsubscribe() {
76 subscribed = false;
77 }
78
79 @Override
80 public boolean isUnsubscribed() {
81 return !subscribed;
82 }
83 });
84 Node<Object, Geometry> node = Mockito.mock(Node.class);
85 NodePosition<Object, Geometry> np = new NodePosition<Object, Geometry>(node, 1);
86 ImmutableStack<NodePosition<Object, Geometry>> stack = ImmutableStack
87 .<NodePosition<Object, Geometry>> empty().push(np);
88 Func1<Geometry, Boolean> condition = Mockito.mock(Func1.class);
89 ImmutableStack<NodePosition<Object, Geometry>> stack2 = Backpressure.search(condition, sub,
90 stack, 0);
91 assertTrue(stack2 == stack);
92 }
93
94 @SuppressWarnings("unchecked")
95 @Test
96 public void testRequestZeroWhenUnsubscribed() {
97 Subscriber<Object> sub = new Subscriber<Object>() {
98
99 @Override
100 public void onCompleted() {
101 }
102
103 @Override
104 public void onError(Throwable e) {
105 }
106
107 @Override
108 public void onNext(Object t) {
109
110 }
111 };
112 sub.add(new Subscription() {
113
114 volatile boolean subscribed = true;
115
116 @Override
117 public void unsubscribe() {
118 subscribed = false;
119 }
120
121 @Override
122 public boolean isUnsubscribed() {
123 return !subscribed;
124 }
125 });
126 sub.unsubscribe();
127 Node<Object, Geometry> node = Mockito.mock(Node.class);
128 NodePosition<Object, Geometry> np = new NodePosition<Object, Geometry>(node, 1);
129 ImmutableStack<NodePosition<Object, Geometry>> stack = ImmutableStack
130 .<NodePosition<Object, Geometry>> empty().push(np);
131 Func1<Geometry, Boolean> condition = Mockito.mock(Func1.class);
132 ImmutableStack<NodePosition<Object, Geometry>> stack2 = Backpressure.search(condition, sub,
133 stack, 1);
134 assertTrue(stack2.isEmpty());
135 }
136
137 @Test
138 public void testBackpressureIterateWhenNodeHasMaxChildrenAndIsRoot() {
139 Entry<Object, Rectangle> e1 = RTreeTest.e(1);
140 List<Entry<Object, Rectangle>> list = Arrays.asList(e1, e1, e1, e1);
141 RTree<Object, Rectangle> tree = RTree.star().maxChildren(4).<Object, Rectangle> create()
142 .add(list);
143 HashSet<Entry<Object, Rectangle>> expected = new HashSet<Entry<Object, Rectangle>>(list);
144 final HashSet<Entry<Object, Rectangle>> found = new HashSet<Entry<Object, Rectangle>>();
145 tree.entries().subscribe(backpressureSubscriber(found));
146 assertEquals(expected, found);
147 }
148
149 @Test
150 public void testBackpressureRequestZero() {
151 Entry<Object, Rectangle> e1 = RTreeTest.e(1);
152 List<Entry<Object, Rectangle>> list = Arrays.asList(e1, e1, e1, e1);
153 RTree<Object, Rectangle> tree = RTree.star().maxChildren(4).<Object, Rectangle> create()
154 .add(list);
155 HashSet<Entry<Object, Rectangle>> expected = new HashSet<Entry<Object, Rectangle>>(list);
156 final HashSet<Entry<Object, Rectangle>> found = new HashSet<Entry<Object, Rectangle>>();
157 tree.entries().subscribe(new Subscriber<Entry<Object, Rectangle>>() {
158
159 @Override
160 public void onStart() {
161 request(1);
162 }
163
164 @Override
165 public void onCompleted() {
166
167 }
168
169 @Override
170 public void onError(Throwable e) {
171
172 }
173
174 @Override
175 public void onNext(Entry<Object, Rectangle> t) {
176 found.add(t);
177 request(0);
178 }
179 });
180 assertEquals(expected, found);
181 }
182
183 @Test
184 public void testBackpressureIterateWhenNodeHasMaxChildrenAndIsNotRoot() {
185 Entry<Object, Rectangle> e1 = RTreeTest.e(1);
186 List<Entry<Object, Rectangle>> list = new ArrayList<Entry<Object, Rectangle>>();
187 for (int i = 1; i <= 17; i++)
188 list.add(e1);
189 RTree<Object, Rectangle> tree = RTree.star().maxChildren(4).<Object, Rectangle> create()
190 .add(list);
191 HashSet<Entry<Object, Rectangle>> expected = new HashSet<Entry<Object, Rectangle>>(list);
192 final HashSet<Entry<Object, Rectangle>> found = new HashSet<Entry<Object, Rectangle>>();
193 tree.entries().subscribe(backpressureSubscriber(found));
194 assertEquals(expected, found);
195 }
196
197 @Test
198 public void testBackpressureIterateWhenConditionFailsAgainstNonLeafNode() {
199 Entry<Object, Rectangle> e1 = e(1);
200 List<Entry<Object, Rectangle>> list = new ArrayList<Entry<Object, Rectangle>>();
201 for (int i = 1; i <= 17; i++)
202 list.add(e1);
203 list.add(e(2));
204 RTree<Object, Rectangle> tree = RTree.star().maxChildren(4).<Object, Rectangle> create()
205 .add(list);
206 HashSet<Entry<Object, Rectangle>> expected = new HashSet<Entry<Object, Rectangle>>(list);
207 final HashSet<Entry<Object, Rectangle>> found = new HashSet<Entry<Object, Rectangle>>();
208 tree.entries().subscribe(backpressureSubscriber(found));
209 assertEquals(expected, found);
210 }
211
212 @Test
213 public void testBackpressureIterateWhenConditionFailsAgainstLeafNode() {
214 Entry<Object, Rectangle> e3 = e(3);
215 RTree<Object, Rectangle> tree = RTree.star().maxChildren(4).<Object, Rectangle> create()
216 .add(e(1)).add(e3);
217 Set<Entry<Object, Rectangle>> expected = Collections.singleton(e3);
218 final Set<Entry<Object, Rectangle>> found = new HashSet<Entry<Object, Rectangle>>();
219 tree.search(e3.geometry()).subscribe(backpressureSubscriber(found));
220 assertEquals(expected, found);
221 }
222
223 @Test
224 public void testBackpressureFastPathNotInitiatedTwice() {
225 Entry<Object, Rectangle> e3 = e(3);
226 RTree<Object, Rectangle> tree = RTree.star().maxChildren(4).<Object, Rectangle> create()
227 .add(e(1)).add(e3);
228 Set<Entry<Object, Rectangle>> expected = Collections.singleton(e3);
229 final Set<Entry<Object, Rectangle>> found = new HashSet<Entry<Object, Rectangle>>();
230 tree.search(e3.geometry()).subscribe(new Subscriber<Entry<Object, Rectangle>>() {
231
232 @Override
233 public void onCompleted() {
234
235 }
236
237 @Override
238 public void onError(Throwable e) {
239
240 }
241
242 @Override
243 public void onNext(Entry<Object, Rectangle> t) {
244 found.add(t);
245 request(Long.MAX_VALUE);
246 }
247 });
248 assertEquals(expected, found);
249 }
250
251 private static Subscriber<Entry<Object, Rectangle>> backpressureSubscriber(
252 final Set<Entry<Object, Rectangle>> found) {
253 return new Subscriber<Entry<Object, Rectangle>>() {
254
255 @Override
256 public void onStart() {
257 request(1);
258 }
259
260 @Override
261 public void onCompleted() {
262
263 }
264
265 @Override
266 public void onError(Throwable e) {
267
268 }
269
270 @Override
271 public void onNext(Entry<Object, Rectangle> t) {
272 found.add(t);
273 request(1);
274 }
275 };
276 }
277
278 }