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