001: // Spatial Index Library
002: //
003: // Copyright (C) 2002 Navel Ltd.
004: //
005: // This library is free software; you can redistribute it and/or
006: // modify it under the terms of the GNU Lesser General Public
007: // License as published by the Free Software Foundation; either
008: // version 2.1 of the License, or (at your option) any later version.
009: //
010: // This library is distributed in the hope that it will be useful,
011: // but WITHOUT ANY WARRANTY; without even the implied warranty of
012: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: // Lesser General Public License for more details.
014: //
015: // You should have received a copy of the GNU Lesser General Public
016: // License aint with this library; if not, write to the Free Software
017: // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: //
019: // Contact information:
020: // Mailing address:
021: // Marios Hadjieleftheriou
022: // University of California, Riverside
023: // Department of Computer Science
024: // Surge Building, Room 310
025: // Riverside, CA 92521
026: //
027: // Email:
028: // marioh@cs.ucr.edu
029: package org.geotools.caching.spatialindex.rtree;
030:
031: import org.geotools.caching.spatialindex.spatialindex.*;
032:
033: import java.io.*;
034:
035: import java.util.*;
036:
037: abstract class Node implements INode {
038: protected RTree m_pTree = null;
039:
040: // Parent of all nodes.
041: protected int m_level = -1;
042:
043: // The level of the node in the tree.
044: // Leaves are always at level 0.
045: protected int m_identifier = -1;
046:
047: // The unique ID of this node.
048: protected int m_children = 0;
049:
050: // The number of children pointed by this node.
051: protected int m_capacity = -1;
052:
053: // Specifies the node capacity.
054: protected Region m_nodeMBR = null;
055:
056: // The minimum bounding region enclosing all data contained in the node.
057: protected byte[][] m_pData = null;
058:
059: // The data stored in the node.
060: protected Region[] m_pMBR = null;
061:
062: // The corresponding data MBRs.
063: protected int[] m_pIdentifier = null;
064:
065: // The corresponding data identifiers.
066: protected int[] m_pDataLength = null;
067: int m_totalDataLength = 0;
068:
069: //
070: // Internal
071: //
072: protected Node(RTree pTree, int id, int level, int capacity) {
073: m_pTree = pTree;
074: m_level = level;
075: m_identifier = id;
076: m_capacity = capacity;
077: m_nodeMBR = (Region) pTree.m_infiniteRegion.clone();
078:
079: m_pDataLength = new int[m_capacity + 1];
080: m_pData = new byte[m_capacity + 1][];
081: m_pMBR = new Region[m_capacity + 1];
082: m_pIdentifier = new int[m_capacity + 1];
083: }
084:
085: //
086: // Abstract methods
087: //
088: protected abstract Node chooseSubtree(Region mbr, int level,
089: Stack pathBuffer);
090:
091: protected abstract Leaf findLeaf(Region mbr, int id,
092: Stack pathBuffer);
093:
094: protected abstract Node[] split(byte[] pData, Region mbr, int id);
095:
096: //
097: // IEntry interface
098: //
099: public int getIdentifier() {
100: return m_identifier;
101: }
102:
103: public IShape getShape() {
104: return (IShape) m_nodeMBR.clone();
105: }
106:
107: //
108: // INode interface
109: //
110: public int getChildrenCount() {
111: return m_children;
112: }
113:
114: public int getChildIdentifier(int index)
115: throws IndexOutOfBoundsException {
116: if ((index < 0) || (index >= m_children)) {
117: throw new IndexOutOfBoundsException("" + index);
118: }
119:
120: return m_pIdentifier[index];
121: }
122:
123: public IShape getChildShape(int index)
124: throws IndexOutOfBoundsException {
125: if ((index < 0) || (index >= m_children)) {
126: throw new IndexOutOfBoundsException("" + index);
127: }
128:
129: return new Region(m_pMBR[index]);
130: }
131:
132: public int getLevel() {
133: return m_level;
134: }
135:
136: public boolean isLeaf() {
137: return (m_level == 0);
138: }
139:
140: public boolean isIndex() {
141: return (m_level != 0);
142: }
143:
144: protected void insertEntry(byte[] pData, Region mbr, int id)
145: throws IllegalStateException {
146: if (m_children >= m_capacity) {
147: throw new IllegalStateException(
148: "m_children >= m_nodeCapacity");
149: }
150:
151: m_pDataLength[m_children] = (pData != null) ? pData.length : 0;
152: m_pData[m_children] = pData;
153: m_pMBR[m_children] = mbr;
154: m_pIdentifier[m_children] = id;
155:
156: m_totalDataLength += m_pDataLength[m_children];
157: m_children++;
158:
159: Region.combinedRegion(m_nodeMBR, mbr);
160: }
161:
162: protected void deleteEntry(int index)
163: throws IndexOutOfBoundsException {
164: if ((index < 0) || (index >= m_children)) {
165: throw new IndexOutOfBoundsException("" + index);
166: }
167:
168: boolean touches = m_nodeMBR.touches(m_pMBR[index]);
169:
170: m_totalDataLength -= m_pDataLength[index];
171: m_pData[index] = null;
172:
173: if ((m_children > 1) && (index != (m_children - 1))) {
174: m_pDataLength[index] = m_pDataLength[m_children - 1];
175: m_pData[index] = m_pData[m_children - 1];
176: m_pData[m_children - 1] = null;
177: m_pMBR[index] = m_pMBR[m_children - 1];
178: m_pMBR[m_children - 1] = null;
179: m_pIdentifier[index] = m_pIdentifier[m_children - 1];
180: }
181:
182: m_children--;
183:
184: if (m_children == 0) {
185: m_nodeMBR = (Region) m_pTree.m_infiniteRegion.clone();
186: } else if (touches) {
187: for (int cDim = 0; cDim < m_pTree.m_dimension; cDim++) {
188: m_nodeMBR.m_pLow[cDim] = Double.POSITIVE_INFINITY;
189: m_nodeMBR.m_pHigh[cDim] = Double.NEGATIVE_INFINITY;
190:
191: for (int cChild = 0; cChild < m_children; cChild++) {
192: m_nodeMBR.m_pLow[cDim] = Math.min(
193: m_nodeMBR.m_pLow[cDim],
194: m_pMBR[cChild].m_pLow[cDim]);
195: m_nodeMBR.m_pHigh[cDim] = Math.max(
196: m_nodeMBR.m_pHigh[cDim],
197: m_pMBR[cChild].m_pHigh[cDim]);
198: }
199: }
200: }
201: }
202:
203: protected boolean insertData(byte[] pData, Region mbr, int id,
204: Stack pathBuffer, boolean[] overflowTable) {
205: if (m_children < m_capacity) {
206: boolean adjusted = false;
207: boolean b = m_nodeMBR.contains(mbr);
208:
209: insertEntry(pData, mbr, id);
210: m_pTree.writeNode(this );
211:
212: if (!b && !pathBuffer.empty()) {
213: int cParent = ((Integer) pathBuffer.pop()).intValue();
214: Index p = (Index) m_pTree.readNode(cParent);
215: p.adjustTree(this , pathBuffer);
216: adjusted = true;
217: }
218:
219: return adjusted;
220: } else if ((m_pTree.m_treeVariant == SpatialIndex.RtreeVariantRstar)
221: && !pathBuffer.empty()
222: && (overflowTable[m_level] == false)) {
223: overflowTable[m_level] = true;
224:
225: ArrayList vReinsert = new ArrayList();
226: ArrayList vKeep = new ArrayList();
227: reinsertData(pData, mbr, id, vReinsert, vKeep);
228:
229: int lReinsert = vReinsert.size();
230: int lKeep = vKeep.size();
231:
232: byte[][] reinsertdata = new byte[lReinsert][];
233: Region[] reinsertmbr = new Region[lReinsert];
234: int[] reinsertid = new int[lReinsert];
235: int[] reinsertlen = new int[lReinsert];
236: byte[][] keepdata = new byte[m_capacity + 1][];
237: Region[] keepmbr = new Region[m_capacity + 1];
238: int[] keepid = new int[m_capacity + 1];
239: int[] keeplen = new int[m_capacity + 1];
240:
241: int cIndex;
242:
243: for (cIndex = 0; cIndex < lReinsert; cIndex++) {
244: int i = ((Integer) vReinsert.get(cIndex)).intValue();
245: reinsertlen[cIndex] = m_pDataLength[i];
246: reinsertdata[cIndex] = m_pData[i];
247: reinsertmbr[cIndex] = m_pMBR[i];
248: reinsertid[cIndex] = m_pIdentifier[i];
249: }
250:
251: for (cIndex = 0; cIndex < lKeep; cIndex++) {
252: int i = ((Integer) vKeep.get(cIndex)).intValue();
253: keeplen[cIndex] = m_pDataLength[i];
254: keepdata[cIndex] = m_pData[i];
255: keepmbr[cIndex] = m_pMBR[i];
256: keepid[cIndex] = m_pIdentifier[i];
257: }
258:
259: m_pDataLength = keeplen;
260: m_pData = keepdata;
261: m_pMBR = keepmbr;
262: m_pIdentifier = keepid;
263: m_children = lKeep;
264: m_totalDataLength = 0;
265:
266: for (int cChild = 0; cChild < m_children; cChild++)
267: m_totalDataLength += m_pDataLength[cChild];
268:
269: for (int cDim = 0; cDim < m_pTree.m_dimension; cDim++) {
270: m_nodeMBR.m_pLow[cDim] = Double.POSITIVE_INFINITY;
271: m_nodeMBR.m_pHigh[cDim] = Double.NEGATIVE_INFINITY;
272:
273: for (int cChild = 0; cChild < m_children; cChild++) {
274: m_nodeMBR.m_pLow[cDim] = Math.min(
275: m_nodeMBR.m_pLow[cDim],
276: m_pMBR[cChild].m_pLow[cDim]);
277: m_nodeMBR.m_pHigh[cDim] = Math.max(
278: m_nodeMBR.m_pHigh[cDim],
279: m_pMBR[cChild].m_pHigh[cDim]);
280: }
281: }
282:
283: m_pTree.writeNode(this );
284:
285: // Divertion from R*-Tree algorithm here. First adjust
286: // the path to the root, then start reinserts, to avoid complicated handling
287: // of changes to the same node from multiple insertions.
288: int cParent = ((Integer) pathBuffer.pop()).intValue();
289: Index p = (Index) m_pTree.readNode(cParent);
290: p.adjustTree(this , pathBuffer);
291:
292: for (cIndex = 0; cIndex < lReinsert; cIndex++) {
293: m_pTree.insertData_impl(reinsertdata[cIndex],
294: reinsertmbr[cIndex], reinsertid[cIndex],
295: m_level, overflowTable);
296: }
297:
298: return true;
299: } else {
300: Node[] nodes = split(pData, mbr, id);
301: Node n = nodes[0];
302: Node nn = nodes[1];
303:
304: if (pathBuffer.empty()) {
305: n.m_identifier = -1;
306: nn.m_identifier = -1;
307: m_pTree.writeNode(n);
308: m_pTree.writeNode(nn);
309:
310: Index r = new Index(m_pTree, m_pTree.m_rootID,
311: m_level + 1);
312:
313: r.insertEntry(null, (Region) n.m_nodeMBR.clone(),
314: n.m_identifier);
315: r.insertEntry(null, (Region) nn.m_nodeMBR.clone(),
316: nn.m_identifier);
317:
318: m_pTree.writeNode(r);
319:
320: m_pTree.m_stats.m_nodesInLevel.set(m_level,
321: new Integer(2));
322: m_pTree.m_stats.m_nodesInLevel.add(new Integer(1));
323: m_pTree.m_stats.m_treeHeight = m_level + 2;
324: } else {
325: n.m_identifier = m_identifier;
326: nn.m_identifier = -1;
327:
328: m_pTree.writeNode(n);
329: m_pTree.writeNode(nn);
330:
331: int cParent = ((Integer) pathBuffer.pop()).intValue();
332: Index p = (Index) m_pTree.readNode(cParent);
333: p.adjustTree(n, nn, pathBuffer, overflowTable);
334: }
335:
336: return true;
337: }
338: }
339:
340: protected void reinsertData(byte[] pData, Region mbr, int id,
341: ArrayList reinsert, ArrayList keep) {
342: ReinsertEntry[] v = new ReinsertEntry[m_capacity + 1];
343:
344: m_pDataLength[m_children] = (pData != null) ? pData.length : 0;
345: m_pData[m_children] = pData;
346: m_pMBR[m_children] = mbr;
347: m_pIdentifier[m_children] = id;
348:
349: double[] nc = m_nodeMBR.getCenter();
350:
351: for (int cChild = 0; cChild < (m_capacity + 1); cChild++) {
352: ReinsertEntry e = new ReinsertEntry(cChild, 0.0f);
353:
354: double[] c = m_pMBR[cChild].getCenter();
355:
356: // calculate relative distance of every entry from the node MBR (ignore square root.)
357: for (int cDim = 0; cDim < m_pTree.m_dimension; cDim++) {
358: double d = nc[cDim] - c[cDim];
359: e.m_dist += (d * d);
360: }
361:
362: v[cChild] = e;
363: }
364:
365: // sort by increasing order of distances.
366: Arrays.sort(v, new ReinsertEntryComparator());
367:
368: int cReinsert = (int) Math.floor((m_capacity + 1)
369: * m_pTree.m_reinsertFactor);
370: int cCount;
371:
372: for (cCount = 0; cCount < cReinsert; cCount++) {
373: reinsert.add(new Integer(v[cCount].m_id));
374: }
375:
376: for (cCount = cReinsert; cCount < (m_capacity + 1); cCount++) {
377: keep.add(new Integer(v[cCount].m_id));
378: }
379: }
380:
381: protected void rtreeSplit(byte[] pData, Region mbr, int id,
382: ArrayList group1, ArrayList group2) {
383: int cChild;
384: int minimumLoad = (int) Math.floor(m_capacity
385: * m_pTree.m_fillFactor);
386:
387: // use this mask array for marking visited entries.
388: boolean[] mask = new boolean[m_capacity + 1];
389:
390: for (cChild = 0; cChild < (m_capacity + 1); cChild++)
391: mask[cChild] = false;
392:
393: // insert new data in the node for easier manipulation. Data arrays are always
394: // by one larger than node capacity.
395: m_pDataLength[m_capacity] = (pData != null) ? pData.length : 0;
396: m_pData[m_capacity] = pData;
397: m_pMBR[m_capacity] = mbr;
398: m_pIdentifier[m_capacity] = id;
399:
400: // initialize each group with the seed entries.
401: int[] seeds = pickSeeds();
402:
403: group1.add(new Integer(seeds[0]));
404: group2.add(new Integer(seeds[1]));
405:
406: mask[seeds[0]] = true;
407: mask[seeds[1]] = true;
408:
409: // find MBR of each group.
410: Region mbr1 = (Region) m_pMBR[seeds[0]].clone();
411: Region mbr2 = (Region) m_pMBR[seeds[1]].clone();
412:
413: // count how many entries are left unchecked (exclude the seeds here.)
414: int cRemaining = (m_capacity + 1) - 2;
415:
416: while (cRemaining > 0) {
417: if ((minimumLoad - group1.size()) == cRemaining) {
418: // all remaining entries must be assigned to group1 to comply with minimun load requirement.
419: for (cChild = 0; cChild < (m_capacity + 1); cChild++) {
420: if (mask[cChild] == false) {
421: group1.add(new Integer(cChild));
422: mask[cChild] = true;
423: cRemaining--;
424: }
425: }
426: } else if ((minimumLoad - group2.size()) == cRemaining) {
427: // all remaining entries must be assigned to group2 to comply with minimun load requirement.
428: for (cChild = 0; cChild < (m_capacity + 1); cChild++) {
429: if (mask[cChild] == false) {
430: group2.add(new Integer(cChild));
431: mask[cChild] = true;
432: cRemaining--;
433: }
434: }
435: } else {
436: // For all remaining entries compute the difference of the cost of grouping an
437: // entry in either group. When done, choose the entry that yielded the maximum
438: // difference. In case of linear split, select any entry (e.g. the first one.)
439: int sel = -1;
440: double md1 = 0.0f;
441: double md2 = 0.0f;
442: double m = Double.NEGATIVE_INFINITY;
443: double d1;
444: double d2;
445: double d;
446: double a1 = mbr1.getArea();
447: double a2 = mbr2.getArea();
448:
449: for (cChild = 0; cChild < (m_capacity + 1); cChild++) {
450: if (mask[cChild] == false) {
451: Region a = mbr1.combinedRegion(m_pMBR[cChild]);
452: d1 = a.getArea() - a1;
453:
454: Region b = mbr2.combinedRegion(m_pMBR[cChild]);
455: d2 = b.getArea() - a2;
456: d = Math.abs(d1 - d2);
457:
458: if (d > m) {
459: m = d;
460: md1 = d1;
461: md2 = d2;
462: sel = cChild;
463:
464: if ((m_pTree.m_treeVariant == SpatialIndex.RtreeVariantLinear)
465: || (m_pTree.m_treeVariant == SpatialIndex.RtreeVariantRstar)) {
466: break;
467: }
468: }
469: }
470: }
471:
472: // determine the group where we should add the new entry.
473: int group = -1;
474:
475: if (md1 < md2) {
476: group1.add(new Integer(sel));
477: group = 1;
478: } else if (md2 < md1) {
479: group2.add(new Integer(sel));
480: group = 2;
481: } else if (a1 < a2) {
482: group1.add(new Integer(sel));
483: group = 1;
484: } else if (a2 < a1) {
485: group2.add(new Integer(sel));
486: group = 2;
487: } else if (group1.size() < group2.size()) {
488: group1.add(new Integer(sel));
489: group = 1;
490: } else if (group2.size() < group1.size()) {
491: group2.add(new Integer(sel));
492: group = 2;
493: } else {
494: group1.add(new Integer(sel));
495: group = 1;
496: }
497:
498: mask[sel] = true;
499: cRemaining--;
500:
501: if (group == 1) {
502: Region.combinedRegion(mbr1, m_pMBR[sel]);
503: } else {
504: Region.combinedRegion(mbr2, m_pMBR[sel]);
505: }
506: }
507: }
508: }
509:
510: protected void rstarSplit(byte[] pData, Region mbr, int id,
511: ArrayList group1, ArrayList group2) {
512: RstarSplitEntry[] dataLow = new RstarSplitEntry[m_capacity + 1];
513: ;
514:
515: RstarSplitEntry[] dataHigh = new RstarSplitEntry[m_capacity + 1];
516: ;
517:
518: m_pDataLength[m_children] = (pData != null) ? pData.length : 0;
519: m_pData[m_capacity] = pData;
520: m_pMBR[m_capacity] = mbr;
521: m_pIdentifier[m_capacity] = id;
522:
523: int nodeSPF = (int) (Math.floor((m_capacity + 1)
524: * m_pTree.m_splitDistributionFactor));
525: int splitDistribution = (m_capacity + 1) - (2 * nodeSPF) + 2;
526:
527: int cChild;
528: int cDim;
529: int cIndex;
530:
531: for (cChild = 0; cChild < (m_capacity + 1); cChild++) {
532: RstarSplitEntry e = new RstarSplitEntry(m_pMBR[cChild],
533: cChild, 0);
534:
535: dataLow[cChild] = e;
536: dataHigh[cChild] = e;
537: }
538:
539: double minimumMargin = Double.POSITIVE_INFINITY;
540: int splitAxis = -1;
541: int sortOrder = -1;
542:
543: // chooseSplitAxis.
544: for (cDim = 0; cDim < m_pTree.m_dimension; cDim++) {
545: Arrays.sort(dataLow, new RstarSplitEntryComparatorLow());
546: Arrays.sort(dataHigh, new RstarSplitEntryComparatorHigh());
547:
548: // calculate sum of margins and overlap for all distributions.
549: double marginl = 0.0;
550: double marginh = 0.0;
551:
552: for (cChild = 1; cChild <= splitDistribution; cChild++) {
553: int l = nodeSPF - 1 + cChild;
554:
555: Region[] tl1 = new Region[l];
556: Region[] th1 = new Region[l];
557:
558: for (cIndex = 0; cIndex < l; cIndex++) {
559: tl1[cIndex] = dataLow[cIndex].m_pRegion;
560: th1[cIndex] = dataHigh[cIndex].m_pRegion;
561: }
562:
563: Region bbl1 = Region.combinedRegion(tl1);
564: Region bbh1 = Region.combinedRegion(th1);
565:
566: Region[] tl2 = new Region[(m_capacity + 1) - l];
567: Region[] th2 = new Region[(m_capacity + 1) - l];
568:
569: int tmpIndex = 0;
570:
571: for (cIndex = l; cIndex < (m_capacity + 1); cIndex++) {
572: tl2[tmpIndex] = dataLow[cIndex].m_pRegion;
573: th2[tmpIndex] = dataHigh[cIndex].m_pRegion;
574: tmpIndex++;
575: }
576:
577: Region bbl2 = Region.combinedRegion(tl2);
578: Region bbh2 = Region.combinedRegion(th2);
579:
580: marginl += (bbl1.getMargin() + bbl2.getMargin());
581: marginh += (bbh1.getMargin() + bbh2.getMargin());
582: } // for (cChild)
583:
584: double margin = Math.min(marginl, marginh);
585:
586: // keep minimum margin as split axis.
587: if (margin < minimumMargin) {
588: minimumMargin = margin;
589: splitAxis = cDim;
590: sortOrder = (marginl < marginh) ? 0 : 1;
591: }
592:
593: // increase the dimension according to which the data entries should be sorted.
594: for (cChild = 0; cChild < (m_capacity + 1); cChild++) {
595: dataLow[cChild].m_sortDim = cDim + 1;
596: }
597: } // for (cDim)
598:
599: for (cChild = 0; cChild < (m_capacity + 1); cChild++) {
600: dataLow[cChild].m_sortDim = splitAxis;
601: }
602:
603: if (sortOrder == 0) {
604: Arrays.sort(dataLow, new RstarSplitEntryComparatorLow());
605: } else {
606: Arrays.sort(dataLow, new RstarSplitEntryComparatorHigh());
607: }
608:
609: double ma = Double.POSITIVE_INFINITY;
610: double mo = Double.POSITIVE_INFINITY;
611: int splitPoint = -1;
612:
613: for (cChild = 1; cChild <= splitDistribution; cChild++) {
614: int l = nodeSPF - 1 + cChild;
615:
616: Region[] t1 = new Region[l];
617:
618: for (cIndex = 0; cIndex < l; cIndex++) {
619: t1[cIndex] = dataLow[cIndex].m_pRegion;
620: }
621:
622: Region bb1 = Region.combinedRegion(t1);
623:
624: Region[] t2 = new Region[(m_capacity + 1) - l];
625:
626: int tmpIndex = 0;
627:
628: for (cIndex = l; cIndex < (m_capacity + 1); cIndex++) {
629: t2[tmpIndex] = dataLow[cIndex].m_pRegion;
630: tmpIndex++;
631: }
632:
633: Region bb2 = Region.combinedRegion(t2);
634:
635: double o = bb1.getIntersectingArea(bb2);
636:
637: if (o < mo) {
638: splitPoint = cChild;
639: mo = o;
640: ma = bb1.getArea() + bb2.getArea();
641: } else if (o == mo) {
642: double a = bb1.getArea() + bb2.getArea();
643:
644: if (a < ma) {
645: splitPoint = cChild;
646: ma = a;
647: }
648: }
649: } // for (cChild)
650:
651: int l1 = nodeSPF - 1 + splitPoint;
652:
653: for (cIndex = 0; cIndex < l1; cIndex++) {
654: group1.add(new Integer(dataLow[cIndex].m_id));
655: }
656:
657: for (cIndex = l1; cIndex <= m_capacity; cIndex++) {
658: group2.add(new Integer(dataLow[cIndex].m_id));
659: }
660: }
661:
662: protected int[] pickSeeds() {
663: double separation = Double.NEGATIVE_INFINITY;
664: double inefficiency = Double.NEGATIVE_INFINITY;
665: int cDim;
666: int cChild;
667: int cIndex;
668: int i1 = 0;
669: int i2 = 0;
670:
671: switch (m_pTree.m_treeVariant) {
672: case SpatialIndex.RtreeVariantLinear:
673: case SpatialIndex.RtreeVariantRstar:
674:
675: for (cDim = 0; cDim < m_pTree.m_dimension; cDim++) {
676: double leastLower = m_pMBR[0].m_pLow[cDim];
677: double greatestUpper = m_pMBR[0].m_pHigh[cDim];
678: int greatestLower = 0;
679: int leastUpper = 0;
680: double width;
681:
682: for (cChild = 1; cChild < (m_capacity + 1); cChild++) {
683: if (m_pMBR[cChild].m_pLow[cDim] > m_pMBR[greatestLower].m_pLow[cDim]) {
684: greatestLower = cChild;
685: }
686:
687: if (m_pMBR[cChild].m_pHigh[cDim] < m_pMBR[leastUpper].m_pHigh[cDim]) {
688: leastUpper = cChild;
689: }
690:
691: leastLower = Math.min(m_pMBR[cChild].m_pLow[cDim],
692: leastLower);
693: greatestUpper = Math
694: .max(m_pMBR[cChild].m_pHigh[cDim],
695: greatestUpper);
696: }
697:
698: width = greatestUpper - leastLower;
699:
700: if (width <= 0) {
701: width = 1;
702: }
703:
704: double f = (m_pMBR[greatestLower].m_pLow[cDim] - m_pMBR[leastUpper].m_pHigh[cDim])
705: / width;
706:
707: if (f > separation) {
708: i1 = leastUpper;
709: i2 = greatestLower;
710: separation = f;
711: }
712: } // for (cDim)
713:
714: if (i1 == i2) {
715: i2 = (i2 != m_capacity) ? (i2 + 1) : (i2 - 1);
716: }
717:
718: break;
719:
720: case SpatialIndex.RtreeVariantQuadratic:
721:
722: // for each pair of Regions (account for overflow Region too!)
723: for (cChild = 0; cChild < m_capacity; cChild++) {
724: double a = m_pMBR[cChild].getArea();
725:
726: for (cIndex = cChild + 1; cIndex < (m_capacity + 1); cIndex++) {
727: // get the combined MBR of those two entries.
728: Region r = m_pMBR[cChild]
729: .combinedRegion(m_pMBR[cIndex]);
730:
731: // find the inefficiency of grouping these entries together.
732: double d = r.getArea() - a
733: - m_pMBR[cIndex].getArea();
734:
735: if (d > inefficiency) {
736: inefficiency = d;
737: i1 = cChild;
738: i2 = cIndex;
739: }
740: } // for (cIndex)
741: } // for (cChild)
742:
743: break;
744:
745: default:
746: throw new IllegalStateException("Unknown RTree variant.");
747: }
748:
749: int[] ret = new int[2];
750: ret[0] = i1;
751: ret[1] = i2;
752:
753: return ret;
754: }
755:
756: protected void condenseTree(Stack toReinsert, Stack pathBuffer) {
757: int minimumLoad = (int) (Math.floor(m_capacity
758: * m_pTree.m_fillFactor));
759:
760: if (pathBuffer.empty()) {
761: // eliminate root if it has only one child.
762: if ((m_level != 0) && (m_children == 1)) {
763: Node n = m_pTree.readNode(m_pIdentifier[0]);
764: m_pTree.deleteNode(n);
765: n.m_identifier = m_pTree.m_rootID;
766: m_pTree.writeNode(n);
767:
768: m_pTree.m_stats.m_nodesInLevel
769: .remove(m_pTree.m_stats.m_nodesInLevel.size() - 1);
770: m_pTree.m_stats.m_treeHeight -= 1;
771: // HACK: pending deleteNode for deleted child will decrease nodesInLevel, later on.
772: m_pTree.m_stats.m_nodesInLevel.set(
773: m_pTree.m_stats.m_treeHeight - 1,
774: new Integer(2));
775: }
776: } else {
777: int cParent = ((Integer) pathBuffer.pop()).intValue();
778: Index p = (Index) m_pTree.readNode(cParent);
779:
780: // find the entry in the parent, that points to this node.
781: int child;
782:
783: for (child = 0; child != p.m_children; child++) {
784: if (p.m_pIdentifier[child] == m_identifier) {
785: break;
786: }
787: }
788:
789: if (m_children < minimumLoad) {
790: // used space less than the minimum
791: // 1. eliminate node entry from the parent. deleteEntry will fix the parent's MBR.
792: p.deleteEntry(child);
793: // 2. add this node to the stack in order to reinsert its entries.
794: toReinsert.push(this );
795: } else {
796: // adjust the entry in 'p' to contain the new bounding region of this node.
797: p.m_pMBR[child] = (Region) m_nodeMBR.clone();
798:
799: // global recalculation necessary since the MBR can only shrink in size,
800: // due to data removal.
801: for (int cDim = 0; cDim < m_pTree.m_dimension; cDim++) {
802: p.m_nodeMBR.m_pLow[cDim] = Double.POSITIVE_INFINITY;
803: p.m_nodeMBR.m_pHigh[cDim] = Double.NEGATIVE_INFINITY;
804:
805: for (int cChild = 0; cChild < p.m_children; cChild++) {
806: p.m_nodeMBR.m_pLow[cDim] = Math.min(
807: p.m_nodeMBR.m_pLow[cDim],
808: p.m_pMBR[cChild].m_pLow[cDim]);
809: p.m_nodeMBR.m_pHigh[cDim] = Math.max(
810: p.m_nodeMBR.m_pHigh[cDim],
811: p.m_pMBR[cChild].m_pHigh[cDim]);
812: }
813: }
814: }
815:
816: // write parent node back to storage.
817: m_pTree.writeNode(p);
818:
819: p.condenseTree(toReinsert, pathBuffer);
820: }
821: }
822:
823: protected void load(byte[] data) throws IOException {
824: m_nodeMBR = (Region) m_pTree.m_infiniteRegion.clone();
825:
826: DataInputStream ds = new DataInputStream(
827: new ByteArrayInputStream(data));
828:
829: // skip the node type information, it is not needed.
830: ds.readInt();
831:
832: m_level = ds.readInt();
833: m_children = ds.readInt();
834:
835: for (int cChild = 0; cChild < m_children; cChild++) {
836: m_pMBR[cChild] = new Region();
837: m_pMBR[cChild].m_pLow = new double[m_pTree.m_dimension];
838: m_pMBR[cChild].m_pHigh = new double[m_pTree.m_dimension];
839:
840: for (int cDim = 0; cDim < m_pTree.m_dimension; cDim++) {
841: m_pMBR[cChild].m_pLow[cDim] = ds.readDouble();
842: m_pMBR[cChild].m_pHigh[cDim] = ds.readDouble();
843: }
844:
845: m_pIdentifier[cChild] = ds.readInt();
846:
847: m_pDataLength[cChild] = ds.readInt();
848:
849: if (m_pDataLength[cChild] > 0) {
850: m_totalDataLength += m_pDataLength[cChild];
851: m_pData[cChild] = new byte[m_pDataLength[cChild]];
852: ds.read(m_pData[cChild]);
853: } else {
854: m_pData[cChild] = null;
855: }
856:
857: Region.combinedRegion(m_nodeMBR, m_pMBR[cChild]);
858: }
859: }
860:
861: protected byte[] store() throws IOException {
862: ByteArrayOutputStream bs = new ByteArrayOutputStream();
863: DataOutputStream ds = new DataOutputStream(bs);
864:
865: int type;
866:
867: if (m_level == 0) {
868: type = SpatialIndex.PersistentLeaf;
869: } else {
870: type = SpatialIndex.PersistentIndex;
871: }
872:
873: ds.writeInt(type);
874:
875: ds.writeInt(m_level);
876: ds.writeInt(m_children);
877:
878: for (int cChild = 0; cChild < m_children; cChild++) {
879: for (int cDim = 0; cDim < m_pTree.m_dimension; cDim++) {
880: ds.writeDouble(m_pMBR[cChild].m_pLow[cDim]);
881: ds.writeDouble(m_pMBR[cChild].m_pHigh[cDim]);
882: }
883:
884: ds.writeInt(m_pIdentifier[cChild]);
885:
886: ds.writeInt(m_pDataLength[cChild]);
887:
888: if (m_pDataLength[cChild] > 0) {
889: ds.write(m_pData[cChild]);
890: }
891: }
892:
893: ds.flush();
894:
895: return bs.toByteArray();
896: }
897:
898: class ReinsertEntry {
899: int m_id;
900: double m_dist;
901:
902: public ReinsertEntry(int id, double dist) {
903: m_id = id;
904: m_dist = dist;
905: }
906: } // ReinsertEntry
907:
908: class ReinsertEntryComparator implements Comparator {
909: public int compare(Object o1, Object o2) {
910: if (((ReinsertEntry) o1).m_dist < ((ReinsertEntry) o2).m_dist) {
911: return -1;
912: }
913:
914: if (((ReinsertEntry) o1).m_dist > ((ReinsertEntry) o2).m_dist) {
915: return 1;
916: }
917:
918: return 0;
919: }
920: } // ReinsertEntryComparator
921:
922: class RstarSplitEntry {
923: Region m_pRegion;
924: int m_id;
925: int m_sortDim;
926:
927: RstarSplitEntry(Region r, int id, int dimension) {
928: m_pRegion = r;
929: m_id = id;
930: m_sortDim = dimension;
931: }
932: }
933:
934: class RstarSplitEntryComparatorLow implements Comparator {
935: public int compare(Object o1, Object o2) {
936: RstarSplitEntry e1 = (RstarSplitEntry) o1;
937: RstarSplitEntry e2 = (RstarSplitEntry) o2;
938:
939: if (e1.m_pRegion.m_pLow[e1.m_sortDim] < e2.m_pRegion.m_pLow[e2.m_sortDim]) {
940: return -1;
941: }
942:
943: if (e1.m_pRegion.m_pLow[e1.m_sortDim] > e2.m_pRegion.m_pLow[e2.m_sortDim]) {
944: return 1;
945: }
946:
947: return 0;
948: }
949: }
950:
951: class RstarSplitEntryComparatorHigh implements Comparator {
952: public int compare(Object o1, Object o2) {
953: RstarSplitEntry e1 = (RstarSplitEntry) o1;
954: RstarSplitEntry e2 = (RstarSplitEntry) o2;
955:
956: if (e1.m_pRegion.m_pHigh[e1.m_sortDim] < e2.m_pRegion.m_pHigh[e2.m_sortDim]) {
957: return -1;
958: }
959:
960: if (e1.m_pRegion.m_pHigh[e1.m_sortDim] > e2.m_pRegion.m_pHigh[e2.m_sortDim]) {
961: return 1;
962: }
963:
964: return 0;
965: }
966: }
967: }
|