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    }