Source Code Cross Referenced for Node.java in  » GIS » GeoTools-2.4.1 » org » geotools » caching » spatialindex » rtree » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » GIS » GeoTools 2.4.1 » org.geotools.caching.spatialindex.rtree 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.