001    //$HeadURL: svn+ssh://jwilden@svn.wald.intevation.org/deegree/base/branches/2.5_testing/src/org/deegree/io/quadtree/MemPointQuadtree.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    import org.deegree.model.spatialschema.Point;
044    
045    /**
046     * <code>MemPointQuadtree</code> is a memory based quadtree implementation for points.
047     *
048     * @author <a href="mailto:schmitz@lat-lon.de">Andreas Schmitz</a>
049     * @author last edited by: $Author: mschneider $
050     *
051     * @version 2.0, $Revision: 18195 $, $Date: 2009-06-18 17:55:39 +0200 (Do, 18 Jun 2009) $
052     * @param <T>
053     *            the datatype to be used as id
054     *
055     * @since 2.0
056     */
057    
058    public class MemPointQuadtree<T> implements Quadtree<T> {
059    
060        private MemPointNode<T> root;
061    
062        private double accuracyX = 0.0001;
063    
064        private double accuracyY = 0.0001;
065    
066        int maxDepth = 8;
067    
068        /**
069         * Creates a new instance with the specified region. This envelope cannot be changed.
070         *
071         * @param region
072         */
073        public MemPointQuadtree( Envelope region ) {
074            root = new MemPointNode<T>( this, region, 0 );
075        }
076    
077        /**
078         * Creates a new instance with the specified region. This envelope cannot be changed.
079         *
080         * @param region
081         * @param accuracyX
082         * @param accuracyY
083         */
084        public MemPointQuadtree( Envelope region, double accuracyX, double accuracyY ) {
085            root = new MemPointNode<T>( this, region, 0 );
086            this.accuracyX = accuracyX;
087            this.accuracyY = accuracyY;
088        }
089    
090        /**
091         * Inserts the item with the envelope into the quadtree.
092         *
093         * @param item
094         * @param envelope
095         */
096        public void insert( T item, Envelope envelope )
097                                throws IndexException {
098            root.insert( item, envelope );
099        }
100    
101        /**
102         * Inserts the item with the given point as envelope.
103         *
104         * @param item
105         * @param point
106         */
107        public void insert( T item, Point point )
108                                throws IndexException {
109            Envelope envelope = GeometryFactory.createEnvelope( point.getX() - accuracyX, point.getY() - accuracyY,
110                                                                point.getX() + accuracyX, point.getY() + accuracyY, null );
111            root.insert( item, envelope );
112        }
113    
114        /**
115         * Searches for all items intersecting with the envelope.
116         *
117         * @param envelope
118         * @return a list with the resulting items
119         */
120        public List<T> query( Envelope envelope )
121                                throws IndexException {
122            return root.query( envelope, new ArrayList<T>( 1000 ), 0 );
123        }
124    
125        /**
126         * Deletes the item from the quadtree. Untested method!
127         *
128         * @param item
129         *            the item to be deleted
130         * @throws IndexException
131         */
132        public void deleteItem( T item )
133                                throws IndexException {
134            root.delete( item, root.getEnvelope() );
135        }
136    
137        /**
138         * Deletes all items intersecting the envelope. Untested method!
139         *
140         * @param envelope
141         */
142        public void deleteRange( Envelope envelope ) {
143            root.deleteRange( envelope );
144        }
145    
146        /**
147         * @return the deepest level of this subtree
148         */
149        public int getDepth() {
150            return root.getDepth();
151        }
152    
153        /**
154         * @return the root bounding box
155         */
156        public Envelope getRootBoundingBox()
157                                throws IndexException {
158            return root.getEnvelope();
159        }
160    
161        public void update( T item, Envelope newBBox ) {
162            throw new UnsupportedOperationException(
163                                                     "This method is not implemented for the mempoint quatree, maybe use a delete and insert combination?" );
164        }
165    
166    }