File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\mvstore\rtree\MVRTreeMap.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 */
7 package org.h2.mvstore.rtree;
8
9 import java.util.ArrayList;
10 import java.util.Iterator;
11 import org.h2.mvstore.Cursor;
12 import org.h2.mvstore.CursorPos;
13 import org.h2.mvstore.MVMap;
14 import org.h2.mvstore.Page;
15 import org.h2.mvstore.type.DataType;
16 import org.h2.util.New;
17
18 /**
19 * An r-tree implementation. It uses the quadratic split algorithm.
20 *
21 * @param <V> the value class
22 */
23 public class MVRTreeMap<V> extends MVMap<SpatialKey, V> {
24
25 /**
26 * The spatial key type.
27 */
28 final SpatialType keyType;
29
30 private boolean quadraticSplit;
31
32 public MVRTreeMap(int dimensions, DataType valueType) {
33 super(new SpatialType(dimensions), valueType);
34 this.keyType = (SpatialType) getKeyType();
35 }
36
37 /**
38 * Create a new map with the given dimensions and value type.
39 *
40 * @param <V> the value type
41 * @param dimensions the number of dimensions
42 * @param valueType the value type
43 * @return the map
44 */
45 public static <V> MVRTreeMap<V> create(int dimensions, DataType valueType) {
46 return new MVRTreeMap<V>(dimensions, valueType);
47 }
48
49 @SuppressWarnings("unchecked")
50 public V get(Object key) {
51 checkOpen();
52 return (V) get(root, key);
53 }
54
55 /**
56 * Iterate over all keys that have an intersection with the given rectangle.
57 *
58 * @param x the rectangle
59 * @return the iterator
60 */
61 public Iterator<SpatialKey> findIntersectingKeys(SpatialKey x) {
62 checkOpen();
63 return new RTreeCursor(this, root, x) {
64 protected boolean check(boolean leaf, SpatialKey key, SpatialKey test) {
65 return keyType.isOverlap(key, test);
66 }
67 };
68 }
69
70 /**
71 * Iterate over all keys that are fully contained within the given rectangle.
72 *
73 * @param x the rectangle
74 * @return the iterator
75 */
76 public Iterator<SpatialKey> findContainedKeys(SpatialKey x) {
77 checkOpen();
78 return new RTreeCursor(this, root, x) {
79 protected boolean check(boolean leaf, SpatialKey key, SpatialKey test) {
80 if (leaf) {
81 return keyType.isInside(key, test);
82 }
83 return keyType.isOverlap(key, test);
84 }
85 };
86 }
87
88 private boolean contains(Page p, int index, Object key) {
89 return keyType.contains(p.getKey(index), key);
90 }
91
92 /**
93 * Get the object for the given key. An exact match is required.
94 *
95 * @param p the page
96 * @param key the key
97 * @return the value, or null if not found
98 */
99 protected Object get(Page p, Object key) {
100 if (!p.isLeaf()) {
101 for (int i = 0; i < p.getKeyCount(); i++) {
102 if (contains(p, i, key)) {
103 Object o = get(p.getChildPage(i), key);
104 if (o != null) {
105 return o;
106 }
107 }
108 }
109 } else {
110 for (int i = 0; i < p.getKeyCount(); i++) {
111 if (keyType.equals(p.getKey(i), key)) {
112 return p.getValue(i);
113 }
114 }
115 }
116 return null;
117 }
118
119 protected Page getPage(SpatialKey key) {
120 return getPage(root, key);
121 }
122
123 private Page getPage(Page p, Object key) {
124 if (!p.isLeaf()) {
125 for (int i = 0; i < p.getKeyCount(); i++) {
126 if (contains(p, i, key)) {
127 Page x = getPage(p.getChildPage(i), key);
128 if (x != null) {
129 return x;
130 }
131 }
132 }
133 } else {
134 for (int i = 0; i < p.getKeyCount(); i++) {
135 if (keyType.equals(p.getKey(i), key)) {
136 return p;
137 }
138 }
139 }
140 return null;
141 }
142
143 protected Object remove(Page p, long writeVersion, Object key) {
144 Object result = null;
145 if (p.isLeaf()) {
146 for (int i = 0; i < p.getKeyCount(); i++) {
147 if (keyType.equals(p.getKey(i), key)) {
148 result = p.getValue(i);
149 p.remove(i);
150 if (p.getKeyCount() == 0) {
151 removePage(p);
152 }
153 break;
154 }
155 }
156 return result;
157 }
158 for (int i = 0; i < p.getKeyCount(); i++) {
159 if (contains(p, i, key)) {
160 Page cOld = p.getChildPage(i);
161 Page c = cOld.copyOnWrite(writeVersion);
162 long oldSize = c.getTotalCount();
163 result = remove(c, writeVersion, key);
164 if (oldSize == c.getTotalCount()) {
165 continue;
166 }
167 if (c.getTotalCount() == 0) {
168 // this child was deleted
169 p.remove(i);
170 if (p.getKeyCount() == 0) {
171 removePage(p);
172 }
173 break;
174 }
175 Object oldBounds = p.getKey(i);
176 if (!keyType.isInside(key, oldBounds)) {
177 p.setKey(i, getBounds(c));
178 }
179 p.setChild(i, c);
180 break;
181 }
182 }
183 return result;
184 }
185
186 private Object getBounds(Page x) {
187 Object bounds = keyType.createBoundingBox(x.getKey(0));
188 for (int i = 1; i < x.getKeyCount(); i++) {
189 keyType.increaseBounds(bounds, x.getKey(i));
190 }
191 return bounds;
192 }
193
194 @SuppressWarnings("unchecked")
195 public V put(SpatialKey key, V value) {
196 return (V) putOrAdd(key, value, false);
197 }
198
199 /**
200 * Add a given key-value pair. The key should not exist (if it exists, the
201 * result is undefined).
202 *
203 * @param key the key
204 * @param value the value
205 */
206 public void add(SpatialKey key, V value) {
207 putOrAdd(key, value, true);
208 }
209
210 private Object putOrAdd(SpatialKey key, V value, boolean alwaysAdd) {
211 checkWrite();
212 long writeVersion = store.getCurrentVersion();
213 Page p = root.copyOnWrite(writeVersion);
214 Object result;
215 if (alwaysAdd || get(key) == null) {
216 if (p.getMemory() > store.getPageSize() && p.getKeyCount() > 1) {
217 // only possible if this is the root, else we would have split earlier
218 // (this requires maxPageSize is fixed)
219 long totalCount = p.getTotalCount();
220 Page split = split(p, writeVersion);
221 Object k1 = getBounds(p);
222 Object k2 = getBounds(split);
223 Object[] keys = { k1, k2 };
224 long[] children = { p.getPos(), split.getPos(), 0 };
225 Page[] childrenPages = { p, split, null };
226 long[] counts = { p.getTotalCount(), split.getTotalCount(), 0 };
227 p = Page.create(this, writeVersion, 2,
228 keys, null, children, childrenPages, counts,
229 totalCount, 0, 0);
230 // now p is a node; continues
231 }
232 add(p, writeVersion, key, value);
233 result = null;
234 } else {
235 result = set(p, writeVersion, key, value);
236 }
237 newRoot(p);
238 return result;
239 }
240
241 /**
242 * Update the value for the given key. The key must exist.
243 *
244 * @param p the page
245 * @param writeVersion the write version
246 * @param key the key
247 * @param value the value
248 * @return the old value
249 */
250 private Object set(Page p, long writeVersion, Object key, Object value) {
251 if (!p.isLeaf()) {
252 for (int i = 0; i < p.getKeyCount(); i++) {
253 if (contains(p, i, key)) {
254 Page c = p.getChildPage(i).copyOnWrite(writeVersion);
255 Object result = set(c, writeVersion, key, value);
256 if (result != null) {
257 p.setChild(i, c);
258 return result;
259 }
260 }
261 }
262 } else {
263 for (int i = 0; i < p.getKeyCount(); i++) {
264 if (keyType.equals(p.getKey(i), key)) {
265 return p.setValue(i, value);
266 }
267 }
268 }
269 return null;
270 }
271
272 private void add(Page p, long writeVersion, Object key, Object value) {
273 if (p.isLeaf()) {
274 p.insertLeaf(p.getKeyCount(), key, value);
275 return;
276 }
277 // p is a node
278 int index = -1;
279 for (int i = 0; i < p.getKeyCount(); i++) {
280 if (contains(p, i, key)) {
281 index = i;
282 break;
283 }
284 }
285 if (index < 0) {
286 // a new entry, we don't know where to add yet
287 float min = Float.MAX_VALUE;
288 for (int i = 0; i < p.getKeyCount(); i++) {
289 Object k = p.getKey(i);
290 float areaIncrease = keyType.getAreaIncrease(k, key);
291 if (areaIncrease < min) {
292 index = i;
293 min = areaIncrease;
294 }
295 }
296 }
297 Page c = p.getChildPage(index).copyOnWrite(writeVersion);
298 if (c.getMemory() > store.getPageSize() && c.getKeyCount() > 1) {
299 // split on the way down
300 Page split = split(c, writeVersion);
301 p = p.copyOnWrite(writeVersion);
302 p.setKey(index, getBounds(c));
303 p.setChild(index, c);
304 p.insertNode(index, getBounds(split), split);
305 // now we are not sure where to add
306 add(p, writeVersion, key, value);
307 return;
308 }
309 add(c, writeVersion, key, value);
310 Object bounds = p.getKey(index);
311 keyType.increaseBounds(bounds, key);
312 p.setKey(index, bounds);
313 p.setChild(index, c);
314 }
315
316 private Page split(Page p, long writeVersion) {
317 return quadraticSplit ?
318 splitQuadratic(p, writeVersion) :
319 splitLinear(p, writeVersion);
320 }
321
322 private Page splitLinear(Page p, long writeVersion) {
323 ArrayList<Object> keys = New.arrayList();
324 for (int i = 0; i < p.getKeyCount(); i++) {
325 keys.add(p.getKey(i));
326 }
327 int[] extremes = keyType.getExtremes(keys);
328 if (extremes == null) {
329 return splitQuadratic(p, writeVersion);
330 }
331 Page splitA = newPage(p.isLeaf(), writeVersion);
332 Page splitB = newPage(p.isLeaf(), writeVersion);
333 move(p, splitA, extremes[0]);
334 if (extremes[1] > extremes[0]) {
335 extremes[1]--;
336 }
337 move(p, splitB, extremes[1]);
338 Object boundsA = keyType.createBoundingBox(splitA.getKey(0));
339 Object boundsB = keyType.createBoundingBox(splitB.getKey(0));
340 while (p.getKeyCount() > 0) {
341 Object o = p.getKey(0);
342 float a = keyType.getAreaIncrease(boundsA, o);
343 float b = keyType.getAreaIncrease(boundsB, o);
344 if (a < b) {
345 keyType.increaseBounds(boundsA, o);
346 move(p, splitA, 0);
347 } else {
348 keyType.increaseBounds(boundsB, o);
349 move(p, splitB, 0);
350 }
351 }
352 while (splitB.getKeyCount() > 0) {
353 move(splitB, p, 0);
354 }
355 return splitA;
356 }
357
358 private Page splitQuadratic(Page p, long writeVersion) {
359 Page splitA = newPage(p.isLeaf(), writeVersion);
360 Page splitB = newPage(p.isLeaf(), writeVersion);
361 float largest = Float.MIN_VALUE;
362 int ia = 0, ib = 0;
363 for (int a = 0; a < p.getKeyCount(); a++) {
364 Object objA = p.getKey(a);
365 for (int b = 0; b < p.getKeyCount(); b++) {
366 if (a == b) {
367 continue;
368 }
369 Object objB = p.getKey(b);
370 float area = keyType.getCombinedArea(objA, objB);
371 if (area > largest) {
372 largest = area;
373 ia = a;
374 ib = b;
375 }
376 }
377 }
378 move(p, splitA, ia);
379 if (ia < ib) {
380 ib--;
381 }
382 move(p, splitB, ib);
383 Object boundsA = keyType.createBoundingBox(splitA.getKey(0));
384 Object boundsB = keyType.createBoundingBox(splitB.getKey(0));
385 while (p.getKeyCount() > 0) {
386 float diff = 0, bestA = 0, bestB = 0;
387 int best = 0;
388 for (int i = 0; i < p.getKeyCount(); i++) {
389 Object o = p.getKey(i);
390 float incA = keyType.getAreaIncrease(boundsA, o);
391 float incB = keyType.getAreaIncrease(boundsB, o);
392 float d = Math.abs(incA - incB);
393 if (d > diff) {
394 diff = d;
395 bestA = incA;
396 bestB = incB;
397 best = i;
398 }
399 }
400 if (bestA < bestB) {
401 keyType.increaseBounds(boundsA, p.getKey(best));
402 move(p, splitA, best);
403 } else {
404 keyType.increaseBounds(boundsB, p.getKey(best));
405 move(p, splitB, best);
406 }
407 }
408 while (splitB.getKeyCount() > 0) {
409 move(splitB, p, 0);
410 }
411 return splitA;
412 }
413
414 private Page newPage(boolean leaf, long writeVersion) {
415 Object[] values = leaf ? new Object[4] : null;
416 long[] c = leaf ? null : new long[1];
417 Page[] cp = leaf ? null : new Page[1];
418 return Page.create(this, writeVersion, 0,
419 new Object[4], values, c, cp, c, 0, 0, 0);
420 }
421
422 private static void move(Page source, Page target, int sourceIndex) {
423 Object k = source.getKey(sourceIndex);
424 if (source.isLeaf()) {
425 Object v = source.getValue(sourceIndex);
426 target.insertLeaf(0, k, v);
427 } else {
428 Page c = source.getChildPage(sourceIndex);
429 target.insertNode(0, k, c);
430 }
431 source.remove(sourceIndex);
432 }
433
434 /**
435 * Add all node keys (including internal bounds) to the given list.
436 * This is mainly used to visualize the internal splits.
437 *
438 * @param list the list
439 * @param p the root page
440 */
441 public void addNodeKeys(ArrayList<SpatialKey> list, Page p) {
442 if (p != null && !p.isLeaf()) {
443 for (int i = 0; i < p.getKeyCount(); i++) {
444 list.add((SpatialKey) p.getKey(i));
445 addNodeKeys(list, p.getChildPage(i));
446 }
447 }
448 }
449
450 public boolean isQuadraticSplit() {
451 return quadraticSplit;
452 }
453
454 public void setQuadraticSplit(boolean quadraticSplit) {
455 this.quadraticSplit = quadraticSplit;
456 }
457
458 protected int getChildPageCount(Page p) {
459 return p.getChildPageCount() - 1;
460 }
461
462 /**
463 * A cursor to iterate over a subset of the keys.
464 */
465 static class RTreeCursor extends Cursor<SpatialKey> {
466
467 protected RTreeCursor(MVRTreeMap<?> map, Page root, SpatialKey from) {
468 super(map, root, from);
469 }
470
471 public void skip(long n) {
472 if (!hasNext()) {
473 return;
474 }
475 while (n-- > 0) {
476 fetchNext();
477 }
478 }
479
480 /**
481 * Check a given key.
482 *
483 * @param leaf if the key is from a leaf page
484 * @param key the stored key
485 * @param test the user-supplied test key
486 * @return true if there is a match
487 */
488 protected boolean check(boolean leaf, SpatialKey key, SpatialKey test) {
489 return true;
490 }
491
492 protected void min(Page p, SpatialKey x) {
493 while (true) {
494 if (p.isLeaf()) {
495 pos = new CursorPos(p, 0, pos);
496 return;
497 }
498 boolean found = false;
499 for (int i = 0; i < p.getKeyCount(); i++) {
500 if (check(false, (SpatialKey) p.getKey(i), x)) {
501 pos = new CursorPos(p, i + 1, pos);
502 p = p.getChildPage(i);
503 found = true;
504 break;
505 }
506 }
507 if (!found) {
508 break;
509 }
510 }
511 fetchNext();
512 }
513
514 protected void fetchNext() {
515 while (pos != null) {
516 while (pos.index < pos.page.getKeyCount()) {
517 SpatialKey k = (SpatialKey) pos.page.getKey(pos.index++);
518 if (check(true, k, from)) {
519 current = k;
520 return;
521 }
522 }
523 pos = pos.parent;
524 if (pos == null) {
525 break;
526 }
527 MVRTreeMap<?> m = (MVRTreeMap<?>) map;
528 if (pos.index < m.getChildPageCount(pos.page)) {
529 min(pos.page.getChildPage(pos.index++), from);
530 }
531 }
532 current = null;
533 }
534 }
535
536 public String getType() {
537 return "rtree";
538 }
539
540 }
541