    001    //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/branches/2.4_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    }