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