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 along 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.util.*;
034:
035: public class Leaf extends Node {
036: public Leaf(RTree pTree, int id) {
037: super (pTree, id, 0, pTree.m_leafCapacity);
038: }
039:
040: protected Node chooseSubtree(Region mbr, int level, Stack pathBuffer) {
041: return this ;
042: }
043:
044: protected Leaf findLeaf(Region mbr, int id, Stack pathBuffer) {
045: for (int cChild = 0; cChild < m_children; cChild++) {
046: if ((m_pIdentifier[cChild] == id)
047: && mbr.equals(m_pMBR[cChild])) {
048: return this ;
049: }
050: }
051:
052: return null;
053: }
054:
055: protected Node[] split(byte[] pData, Region mbr, int id) {
056: m_pTree.m_stats.m_splits++;
057:
058: ArrayList g1 = new ArrayList();
059: ArrayList g2 = new ArrayList();
060:
061: switch (m_pTree.m_treeVariant) {
062: case SpatialIndex.RtreeVariantLinear:
063: case SpatialIndex.RtreeVariantQuadratic:
064: rtreeSplit(pData, mbr, id, g1, g2);
065:
066: break;
067:
068: case SpatialIndex.RtreeVariantRstar:
069: rstarSplit(pData, mbr, id, g1, g2);
070:
071: break;
072:
073: default:
074: throw new IllegalStateException("Unknown RTree variant.");
075: }
076:
077: Node left = new Leaf(m_pTree, -1);
078: Node right = new Leaf(m_pTree, -1);
079:
080: int cIndex;
081:
082: for (cIndex = 0; cIndex < g1.size(); cIndex++) {
083: int i = ((Integer) g1.get(cIndex)).intValue();
084: left.insertEntry(m_pData[i], m_pMBR[i], m_pIdentifier[i]);
085:
086: // we don't want to delete the data array from this node's destructor!
087: m_pData[i] = null;
088: }
089:
090: for (cIndex = 0; cIndex < g2.size(); cIndex++) {
091: int i = ((Integer) g2.get(cIndex)).intValue();
092: right.insertEntry(m_pData[i], m_pMBR[i], m_pIdentifier[i]);
093:
094: // we don't want to delete the data array from this node's destructor!
095: m_pData[i] = null;
096: }
097:
098: Node[] ret = new Node[2];
099: ret[0] = left;
100: ret[1] = right;
101:
102: return ret;
103: }
104:
105: protected void deleteData(int id, Stack pathBuffer) {
106: int child;
107:
108: for (child = 0; child < m_children; child++) {
109: if (m_pIdentifier[child] == id) {
110: break;
111: }
112: }
113:
114: deleteEntry(child);
115: m_pTree.writeNode(this );
116:
117: Stack toReinsert = new Stack();
118: condenseTree(toReinsert, pathBuffer);
119:
120: // re-insert eliminated nodes.
121: while (!toReinsert.empty()) {
122: Node n = (Node) toReinsert.pop();
123: m_pTree.deleteNode(n);
124:
125: for (int cChild = 0; cChild < n.m_children; cChild++) {
126: // keep this in the for loop. The tree height might change after insertions.
127: boolean[] overflowTable = new boolean[m_pTree.m_stats.m_treeHeight];
128:
129: for (int cLevel = 0; cLevel < m_pTree.m_stats.m_treeHeight; cLevel++)
130: overflowTable[cLevel] = false;
131:
132: m_pTree.insertData_impl(n.m_pData[cChild],
133: n.m_pMBR[cChild], n.m_pIdentifier[cChild],
134: n.m_level, overflowTable);
135: n.m_pData[cChild] = null;
136: }
137: }
138: }
139: }
|