001 //$HeadURL: svn+ssh://jwilden@svn.wald.intevation.org/deegree/base/branches/2.5_testing/src/org/deegree/io/quadtree/MemPointNode.java $
002 /*----------------------------------------------------------------------------
003 This file is part of deegree, http://deegree.org/
004 Copyright (C) 2001-2009 by:
005 Department of Geography, University of Bonn
006 and
007 lat/lon GmbH
008
009 This library is free software; you can redistribute it and/or modify it under
010 the terms of the GNU Lesser General Public License as published by the Free
011 Software Foundation; either version 2.1 of the License, or (at your option)
012 any later version.
013 This library is distributed in the hope that it will be useful, but WITHOUT
014 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
015 FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
016 details.
017 You should have received a copy of the GNU Lesser General Public License
018 along with this library; if not, write to the Free Software Foundation, Inc.,
019 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
020
021 Contact information:
022
023 lat/lon GmbH
024 Aennchenstr. 19, 53177 Bonn
025 Germany
026 http://lat-lon.de/
027
028 Department of Geography, University of Bonn
029 Prof. Dr. Klaus Greve
030 Postfach 1147, 53001 Bonn
031 Germany
032 http://www.geographie.uni-bonn.de/deegree/
033
034 e-mail: info@deegree.org
035 ----------------------------------------------------------------------------*/
036 package org.deegree.io.quadtree;
037
038 import java.util.ArrayList;
039 import java.util.List;
040
041 import org.deegree.model.spatialschema.Envelope;
042 import org.deegree.model.spatialschema.GeometryFactory;
043
044 /**
045 * <code>MemPointNode</code> is the node class of a memory based implementation of a quadtree.
046 *
047 * @author <a href="mailto:schmitz@lat-lon.de">Andreas Schmitz</a>
048 * @author last edited by: $Author: mschneider $
049 *
050 * @version 2.0, $Revision: 18195 $, $Date: 2009-06-18 17:55:39 +0200 (Do, 18 Jun 2009) $
051 * @param <T>
052 * the datatype to be used as id
053 *
054 * @since 2.0
055 */
056
057 public class MemPointNode<T> implements Node<T> {
058
059 private final Envelope envelope;
060
061 private final int level;
062
063 private MemPointNode<T>[] subnodes;
064
065 private List<T> items;
066
067 private List<Envelope> itemsEnvelope;
068
069 private Quadtree owner;
070
071 /**
072 * Constructs a new node with the given envelope, object, location and level.
073 *
074 * @param owner
075 * @param env
076 * the envelope
077 * @param lvl
078 * the level
079 */
080 public MemPointNode( Quadtree owner, Envelope env, int lvl ) {
081 envelope = env;
082 level = lvl;
083 this.owner = owner;
084 }
085
086 /**
087 * @return the deepest level of this subtree
088 */
089 public int getDepth() {
090 if ( subnodes == null ) {
091 return level;
092 }
093
094 int max = 0;
095 int d = 0;
096
097 for ( MemPointNode node : subnodes ) {
098 if ( node != null ) {
099 d = node.getDepth();
100 if ( d > max ) {
101 max = d;
102 }
103 }
104 }
105
106 return max;
107 }
108
109 /**
110 * @return the region of this node
111 */
112 public Envelope getEnvelope() {
113 return envelope;
114 }
115
116 /**
117 * This method does not make sense for the memory implementation.
118 *
119 * @return null
120 */
121 public String getId() {
122 return null;
123 }
124
125 /**
126 * Inserts the item into the quadtree.
127 *
128 * @param item
129 * the item
130 * @param itemEnv
131 * the envelope of the item
132 */
133 public boolean insert( T item, Envelope itemEnv )
134 throws IndexException {
135
136 if ( !envelope.intersects( itemEnv ) ) {
137 throw new IndexException( "Item envelope does not intersect with node envelope!" );
138 }
139
140 if ( level < ( (MemPointQuadtree) owner ).maxDepth ) {
141 Envelope[] envs = split();
142
143 if ( subnodes == null ) {
144 subnodes = (MemPointNode<T>[]) new MemPointNode[4];
145 }
146
147 for ( int i = 0; i < 4; ++i ) {
148 if ( envs[i].intersects( itemEnv ) ) {
149 if ( subnodes[i] == null ) {
150 subnodes[i] = new MemPointNode<T>( owner, envs[i], level + 1 );
151 }
152 subnodes[i].insert( item, itemEnv );
153 }
154 }
155 } else {
156 if ( items == null ) {
157 items = new ArrayList<T>( 50 );
158 itemsEnvelope = new ArrayList<Envelope>( 50 );
159 }
160 items.add( item );
161 itemsEnvelope.add( itemEnv );
162 }
163 return true;
164 }
165
166 /**
167 * Searches for all items intersecting the search envelope.
168 *
169 * @param searchEnv
170 * the search envelope
171 * @param visitor
172 * the resulting list
173 * @param level
174 * unused by this implementation
175 * @return a list with all found items
176 */
177 public List<T> query( Envelope searchEnv, List<T> visitor, int level )
178 throws IndexException {
179
180 if ( subnodes == null ) {
181 return visitor;
182 }
183
184 for ( int i = 0; i < 4; ++i ) {
185 if ( subnodes[i] != null ) {
186 MemPointNode<T> node = subnodes[i];
187 if ( node.items != null ) {
188 if ( subnodes[i].envelope.intersects( searchEnv ) ) {
189 for ( int j = 0; j < node.itemsEnvelope.size(); j++ ) {
190 Envelope env = node.itemsEnvelope.get( j );
191 if ( env.intersects( searchEnv ) ) {
192 visitor.addAll( node.items );
193 }
194 }
195 }
196 } else {
197 if ( node.envelope.intersects( searchEnv ) ) {
198 node.query( searchEnv, visitor, level );
199 }
200 }
201 }
202 }
203
204 return visitor;
205 }
206
207 /**
208 * Deletes the item from the quadtree. Untested method!
209 *
210 * @param item
211 * the item to be deleted
212 */
213 public boolean delete( T item, Envelope env )
214 throws IndexException {
215
216 if ( subnodes != null ) {
217 for ( int i = 0; i < 4; ++i ) {
218 if ( subnodes[i] != null ) {
219 MemPointNode<T> node = subnodes[i];
220 if ( node.items.contains( item ) ) {
221 node.items.remove( item );
222 } else {
223 return node.delete( item, env );
224 }
225 }
226 }
227 }
228 return true;
229
230 }
231
232 public boolean update( T item, Envelope newBBox ) {
233 throw new UnsupportedOperationException(
234 "This method is not implemented for the mempoint Node, maybe use a delete and insert combination?" );
235 }
236
237 /**
238 * Deletes all items intersecting the envelope. Untested method!
239 *
240 * @param envelope
241 */
242 public void deleteRange( Envelope envelope ) {
243
244 if ( subnodes == null ) {
245 return;
246 }
247
248 for ( int i = 0; i < 4; ++i ) {
249 if ( subnodes[i] != null ) {
250 MemPointNode node = subnodes[i];
251 if ( node.envelope.intersects( envelope ) ) {
252 subnodes[i] = null;
253 } else {
254 if ( node.envelope.intersects( envelope ) ) {
255 node.deleteRange( envelope );
256 }
257 }
258 }
259 }
260
261 }
262
263 // splits the envelope of this node in four pieces
264 private Envelope[] split() {
265 Envelope[] envs = new Envelope[4];
266 double nW = envelope.getWidth() / 2d;
267 double nH = envelope.getHeight() / 2d;
268
269 envs[0] = GeometryFactory.createEnvelope( envelope.getMin().getX(), envelope.getMin().getY(),
270 envelope.getMin().getX() + nW, envelope.getMin().getY() + nH, null );
271 envs[1] = GeometryFactory.createEnvelope( envelope.getMin().getX() + nW, envelope.getMin().getY(),
272 envelope.getMin().getX() + ( 2 * nW ), envelope.getMin().getY() + nH,
273 null );
274 envs[2] = GeometryFactory.createEnvelope( envelope.getMin().getX() + nW, envelope.getMin().getY() + nH,
275 envelope.getMin().getX() + ( 2 * nW ), envelope.getMin().getY()
276 + ( 2 * nH ), null );
277 envs[3] = GeometryFactory.createEnvelope( envelope.getMin().getX(), envelope.getMin().getY() + nH,
278 envelope.getMin().getX() + nW, envelope.getMin().getY() + ( 2 * nH ),
279 null );
280
281 return envs;
282 }
283
284 }