001    //$HeadURL: svn+ssh://jwilden@svn.wald.intevation.org/deegree/base/branches/2.5_testing/src/org/deegree/io/quadtree/Quadtree.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.List;
039    
040    import org.deegree.model.spatialschema.Envelope;
041    import org.deegree.model.spatialschema.Point;
042    
043    /**
044     *
045     *
046     *
047     * @version $Revision: 18195 $
048     * @author <a href="mailto:poth@lat-lon.de">Andreas Poth</a>
049     * @author last edited by: $Author: mschneider $
050     *
051     * @version 1.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    public interface Quadtree<T> {
058    
059        /**
060         * inserts a new item into the quadtree
061         *
062         * @param itemKey
063         *            key of the Item to be inserted.
064         * @param envelope
065         *            bbox of the item.
066         * @throws IndexException
067         */
068        public abstract void insert( T itemKey, Envelope envelope )
069                                throws IndexException;
070    
071        /**
072         * inserts a new item into the quadtree
073         *
074         * @param itemKey
075         *            key of the Item to be inserted.
076         * @param point
077         *            if the item is a point.
078         * @throws IndexException
079         */
080        public abstract void insert( T itemKey, Point point )
081                                throws IndexException;
082    
083        /**
084         * returns a List containing all items whose envelope intersects with the passed one
085         *
086         * @param envelope
087         * @return a List containing all items whose envelope intersects with the passed one
088         * @throws IndexException
089         */
090        public abstract List query( Envelope envelope )
091                                throws IndexException;
092    
093        /**
094         * deletes a specific item from the tree (not the item itself will be deleted, just its
095         * reference will be)
096         *
097         * @param itemKey
098         *            key of item to be deleted.
099         * @throws IndexException
100         *             if the rootnode cannot be loaded, or the given item does not exist.
101         */
102        public abstract void deleteItem( T itemKey )
103                                throws IndexException;
104    
105        /**
106         * updates spacial index of the specified item in the quadtree.
107         *
108         * @param itemKey
109         *            the ID of the item.
110         * @param newBBox
111         *            the new BBoundingbox of the item.
112         * @throws IndexException
113         *             if the rootnode cannot be loaded, or the given item does not exist.
114         */
115        public abstract void update( T itemKey, Envelope newBBox )
116                                throws IndexException;
117    
118        /**
119         * deletes all references of items whose envelope intersects with the passed one (
120         *
121         * @see #deleteItem(Object) )
122         * @param envelope
123         */
124        public abstract void deleteRange( Envelope envelope );
125    
126        /**
127         *
128         * @return the maxium depth of the tree (which was configured at instantiation of the db ).
129         */
130        public abstract int getDepth();
131    
132        /**
133         * returns the bounding box covered by the quadtrees root node
134         *
135         * @return the bounding box covered by the quadtrees root node
136         * @throws IndexException
137         */
138        public abstract Envelope getRootBoundingBox()
139                                throws IndexException;
140    
141    }