001    //$HeadURL: svn+ssh://jwilden@svn.wald.intevation.org/deegree/base/branches/2.5_testing/src/org/deegree/io/quadtree/DBNode.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.security.InvalidParameterException;
039    import java.sql.Connection;
040    import java.sql.PreparedStatement;
041    import java.sql.ResultSet;
042    import java.sql.SQLException;
043    import java.sql.Statement;
044    import java.util.ArrayList;
045    import java.util.List;
046    
047    import org.deegree.framework.log.ILogger;
048    import org.deegree.framework.log.LoggerFactory;
049    import org.deegree.io.DBConnectionPool;
050    import org.deegree.io.DBPoolException;
051    import org.deegree.io.JDBCConnection;
052    import org.deegree.io.quadtree.DBQuadtree.SupportedVersions;
053    import org.deegree.model.spatialschema.Envelope;
054    import org.deegree.model.spatialschema.GeometryFactory;
055    import org.deegree.model.spatialschema.Position;
056    
057    /**
058     * Represents a node of a {@link DBQuadtree}. Nodes contain items which have a spatial extent
059     * corresponding to the node's position in the quadtree.
060     *
061     *
062     * @version $Revision: 21181 $
063     * @author <a href="mailto:poth@lat-lon.de">Andreas Poth</a>
064     * @author last edited by: $Author: aschmitz $
065     *
066     * @version 1.0. $Revision: 21181 $, $Date: 2009-12-02 16:47:53 +0100 (Mi, 02 Dez 2009) $
067     *
068     * @since 2.0
069     */
070    class DBNode<T> implements Node<T> {
071    
072        private static ILogger LOG = LoggerFactory.getLogger( DBNode.class );
073    
074        private String id = null;
075    
076        private int level;
077    
078        private String[] fk_subnode = new String[4];
079    
080        private Envelope envelope = null;
081    
082        private JDBCConnection jdbc = null;
083    
084        private DBQuadtree<T> qt = null;
085    
086        private String indexTable = null;
087    
088        private SupportedVersions version;
089    
090        private String indexItemTable;
091    
092        /**
093         * A constructor which reads the envelope from the database. Using an old Quadtree layout.
094         * 
095         * @param id
096         * @param qt
097         * @param indexTable
098         * @param jdbc
099         * @param level
100         * @throws IndexException
101         *             if the node with given id could not be read from the db.
102         */
103        // public DBNode( String id, DBQuadtree<T> qt, String indexTable, JDBCConnection jdbc, int level
104        // )
105        // throws IndexException {
106        // this( id, null, qt, indexTable, jdbc, level, SupportedVersions.ONE );
107        // }
108        /**
109         * 
110         * @param id
111         * @param env
112         * @param qt
113         * @param indexTable
114         * @param jdbc
115         * @param level
116         * @param version
117         *            of the quadtree layout to use
118         * @throws IndexException
119         *             if the node with given id could not be read from the db.
120         */
121        public DBNode( String id, Envelope env, DBQuadtree<T> qt, String indexTable, JDBCConnection jdbc, int level,
122                       SupportedVersions version ) throws IndexException {
123            this.id = id;
124            this.envelope = env;
125            if ( jdbc == null ) {
126                throw new InvalidParameterException( "The JDBCConnection reference parameter 'jdbc' may not be null." );
127            }
128            this.jdbc = jdbc;
129    
130            if ( qt == null ) {
131                throw new InvalidParameterException( "The quadtree reference parameter 'qt' may not be null." );
132            }
133            this.qt = qt;
134    
135            if ( level < 1 ) {
136                level = 1;
137            }
138            this.level = level;
139            if ( indexTable == null || "".equals( indexTable.trim() ) ) {
140                throw new InvalidParameterException(
141                                                     "The Table reference String 'indexTable' may neither be null nor an empty string." );
142            }
143            this.indexTable = indexTable.trim();
144            this.indexItemTable = this.indexTable + "_ITEM ";
145            this.version = version;
146            if ( !loadNodeFromDB() ) {
147                addNodeToDB();
148            }
149            for ( int i = 0; i < fk_subnode.length; ++i ) {
150                if ( fk_subnode[i] == null || "null".equalsIgnoreCase( fk_subnode[i].trim() ) ) {
151                    fk_subnode[i] = "";
152                }
153            }
154            qt.addToCache( this );
155        }
156    
157        /**
158         * A constructor which reads the envelope from the database.
159         * 
160         * @param id
161         * @param qt
162         * @param indexTable
163         * @param jdbc
164         * @param level
165         * @param version
166         *            of the quadtree layout to use.
167         * @throws IndexException
168         *             if the node with given id could not be read from the db.
169         */
170        public DBNode( String id, DBQuadtree<T> qt, String indexTable, JDBCConnection jdbc, int level,
171                       SupportedVersions version ) throws IndexException {
172            this( id, null, qt, indexTable, jdbc, level, version );
173        }
174    
175        public boolean insert( T itemKey, Envelope itemEnv )
176                                throws IndexException {
177            if ( version == SupportedVersions.ONE ) {
178                return insertWithLayoutOne( itemKey, itemEnv );
179            } else if ( version == SupportedVersions.TWO ) {
180                return insertWithLayoutTwo( itemKey, itemEnv );
181            }
182            return false;
183        }
184    
185        public void deleteRange( Envelope envelope ) {
186            if ( level == qt.getDepth() ) {
187                // TODO delete a range from the bottomlevel
188            } else {
189                // TODO delete a range smaller then the depth
190            }
191        }
192    
193        /**
194         * @throws UnsupportedOperationException
195         *             if the version of this quadtree(node) is not 2.0.0 or higher.
196         */
197        public boolean delete( T itemKey, Envelope itemEnv )
198                                throws IndexException {
199            Connection dbConnection = null;
200            DBConnectionPool pool = null;
201            try {
202                if ( version != SupportedVersions.TWO ) {
203                    String msg = "Deleting of items is only supported for the quadtree structure with version '2.0.0' or higher";
204                    LOG.logError( msg );
205                    throw new UnsupportedOperationException( msg );
206                }
207                pool = DBConnectionPool.getInstance();
208                dbConnection = pool.acquireConnection( jdbc.getDriver(), jdbc.getURL(), jdbc.getUser(), jdbc.getPassword() );
209                boolean result = deleteWithLayoutTwo( itemKey, itemEnv, null, dbConnection );
210    
211                return result;
212            } catch ( DBPoolException e ) {
213                throw new IndexException( e );
214            } finally {
215                try {
216                    if ( pool != null && dbConnection != null ) {
217                        pool.releaseConnection( dbConnection, jdbc.getDriver(), jdbc.getURL(), jdbc.getUser(),
218                                                jdbc.getPassword() );
219                    }
220                } catch ( DBPoolException e ) {
221                    LOG.logError( "Could not release the db Connection after deletion in the quadtree because: "
222                                  + e.getMessage() );
223                }
224            }
225    
226        }
227    
228        public boolean update( T itemKey, Envelope newBBox ) {
229            // nottin yet
230            return true;
231        }
232    
233        public List<T> query( Envelope searchEnv, List<T> visitor, int currentLevel )
234                                throws IndexException {
235            if ( version == SupportedVersions.ONE ) {
236                LOG.logDebug( "Performing query with layout 1" );
237                queryWithLayoutOne( searchEnv, visitor, currentLevel );
238            } else if ( version == SupportedVersions.TWO ) {
239                LOG.logDebug( "Performing query with layout 2" );
240                queryWithLayoutTwo( searchEnv, visitor );
241            }
242            return visitor;
243        }
244    
245        public String getId() {
246            return id;
247        }
248    
249        /**
250         * @return the envelope (bbox) of this dbNode.
251         */
252        public Envelope getEnvelope() {
253            return envelope;
254        }
255    
256        /**
257         * creates a new node with current ID and envelope
258         * 
259         * @throws IndexException
260         */
261        private void addNodeToDB()
262                                throws IndexException {
263            Connection con = null;
264            DBConnectionPool pool = null;
265            try {
266                pool = DBConnectionPool.getInstance();
267                con = pool.acquireConnection( jdbc.getDriver(), jdbc.getURL(), jdbc.getUser(), jdbc.getPassword() );
268    
269                StringBuilder sb = new StringBuilder( 100 );
270                sb.append( "INSERT INTO " ).append( indexTable );
271                sb.append( " ( ID, MINX, MINY, MAXX , MAXY ) " );
272                sb.append( "VALUES ( ?, ?, ?, ?, ? ) " );
273                PreparedStatement stmt = con.prepareStatement( sb.toString() );
274                stmt.setString( 1, id );
275                stmt.setFloat( 2, (float) envelope.getMin().getX() );
276                stmt.setFloat( 3, (float) envelope.getMin().getY() );
277                stmt.setFloat( 4, (float) envelope.getMax().getX() );
278                stmt.setFloat( 5, (float) envelope.getMax().getY() );
279                stmt.execute();
280                stmt.close();
281            } catch ( Exception e ) {
282                LOG.logError( e.getMessage(), e );
283                throw new IndexException( "could not create node definition at database", e );
284            } finally {
285                try {
286                    if ( pool != null && con != null ) {
287                        pool.releaseConnection( con, jdbc.getDriver(), jdbc.getURL(), jdbc.getUser(), jdbc.getPassword() );
288                    }
289                } catch ( Exception e1 ) {
290                    e1.printStackTrace();
291                }
292            }
293        }
294    
295        /**
296         * assignes an item to a node by creating a new row in the JT_QTNODE_ITEM table
297         * 
298         */
299        private void assignItem( T itemKey )
300                                throws IndexException {
301            Connection con = null;
302            DBConnectionPool pool = null;
303            try {
304                pool = DBConnectionPool.getInstance();
305                con = pool.acquireConnection( jdbc.getDriver(), jdbc.getURL(), jdbc.getUser(), jdbc.getPassword() );
306    
307                StringBuilder sb = new StringBuilder( 100 );
308                sb.append( "INSERT INTO " ).append( indexItemTable );
309                sb.append( "( FK_QTNODE, FK_ITEM ) " ).append( "VALUES ( ?, ? ) " );
310                PreparedStatement stmt = con.prepareStatement( sb.toString() );
311                stmt.setString( 1, id );
312                if ( itemKey instanceof Integer ) {
313                    stmt.setInt( 2, ( (Integer) itemKey ).intValue() );
314                } else {
315                    stmt.setString( 2, itemKey.toString() );
316                }
317                stmt.execute();
318                stmt.close();
319            } catch ( Exception e ) {
320                LOG.logError( e.getMessage(), e );
321                throw new IndexException( "could not create node definition at database", e );
322            } finally {
323                try {
324                    if ( pool != null && con != null ) {
325                        pool.releaseConnection( con, jdbc.getDriver(), jdbc.getURL(), jdbc.getUser(), jdbc.getPassword() );
326                    }
327                } catch ( Exception e1 ) {
328                    e1.printStackTrace();
329                }
330            }
331        }
332    
333        /**
334         * This method inserts the given item into the quadtree. The difference between layout ONE and TWO is, that in
335         * version TWO all nodes which lie inside the item's bbox possess a reference to the item, allthough the idx_table
336         * will be larger, the retrieval of multiple items inside a requested bbox will be a lot faster.
337         * 
338         * @param itemKey
339         *            to be inserted
340         * @param itemEnv
341         *            bbox of the item to be inserted.
342         * @return true if the item was successfully inserted into the quadtree false otherwise.
343         * @throws IndexException
344         *             if the item could not be inserted because of an <code>db</code> or <code>sql</code> error.
345         */
346        private boolean insertWithLayoutTwo( T itemKey, Envelope itemEnv )
347                                throws IndexException {
348            if ( level != qt.getDepth() ) {
349                if ( !envelope.intersects( itemEnv ) ) {
350                    String msg = "The item's envelope: " + itemEnv
351                                 + " does not intersect with the quadtrees' boundinbox envelope: " + envelope;
352                    LOG.logError( msg );
353                    throw new IndexException( msg );
354                }
355                // split the envelope of this node into four equal sized quarters
356                Envelope[] envs = split();
357                boolean needsUpdate = false;
358                boolean nodeInserted = false;
359                for ( int i = 0; i < envs.length; i++ ) {
360                    if ( envs[i].intersects( itemEnv ) ) {
361                        // check which subnodes are intersected by the
362                        // items envelope; only these nodes are considered for futher processing
363                        if ( "".equals( fk_subnode[i].trim() ) ) {
364                            needsUpdate = true;
365                            fk_subnode[i] = id + '_' + i;
366                        }
367                        DBNode<T> node = qt.getFromCache( fk_subnode[i] );
368                        if ( node == null ) {
369                            node = new DBNode<T>( fk_subnode[i], envs[i], qt, indexTable, jdbc, level + 1, version );
370                        }
371                        nodeInserted = node.insertWithLayoutTwo( itemKey, itemEnv );
372                    }
373                }
374                // if any child node inserted the item, the parent must know about it too, this enhances
375                // the speed of area
376                // querying.
377                if ( nodeInserted ) {
378                    assignItem( itemKey );
379                }
380                if ( needsUpdate ) {
381                    updateNodeInDB();
382                }
383                return nodeInserted;
384            }
385            assignItem( itemKey );
386            return true;
387        }
388    
389        /**
390         * @param itemEnv
391         *            the items envelope
392         * @return true if this nodes envelope lies completely inside the items envelope.
393         */
394        private boolean liesWithIn( Envelope itemEnv ) {
395            Position minThis = envelope.getMin();
396            Position maxThis = envelope.getMax();
397            Position minThat = itemEnv.getMin();
398            Position maxThat = itemEnv.getMax();
399            return ( minThis.getX() >= minThat.getX() && maxThis.getX() <= maxThat.getX()
400                     && minThis.getY() > minThat.getY() && maxThis.getY() < maxThat.getY() );
401    
402        }
403    
404        private boolean insertWithLayoutOne( T itemKey, Envelope itemEnv )
405                                throws IndexException {
406            if ( level != qt.getDepth() ) {
407                if ( !envelope.intersects( itemEnv ) ) {
408                    String msg = "The item's envelope: " + itemEnv
409                                 + " does not intersect with the quadtrees' boundinbox envelope: " + envelope;
410                    LOG.logError( msg );
411                    throw new IndexException( msg );
412                }
413                // split the envelope of this node into four equal sized quarters
414                Envelope[] envs = split();
415                boolean needsUpdate = false;
416                int numberOfInsertedSons = 0;
417                for ( int i = 0; i < envs.length; i++ ) {
418                    if ( envs[i].intersects( itemEnv ) ) {
419                        numberOfInsertedSons++;
420                        // check which subnodes are intersected by the
421                        // items envelope; only these nodes are considered for futher processing
422                        if ( "".equals( fk_subnode[i].trim() ) ) {
423                            needsUpdate = true;
424                            fk_subnode[i] = id + '_' + i;
425                        }
426                        DBNode<T> node = qt.getFromCache( fk_subnode[i] );
427                        if ( node == null ) {
428                            node = new DBNode<T>( fk_subnode[i], envs[i], qt, indexTable, jdbc, level + 1, version );
429                        }
430                        node.insertWithLayoutOne( itemKey, itemEnv );
431                    }
432                }
433                if ( numberOfInsertedSons == 4 ) {
434                    assignItem( itemKey );
435                }
436                if ( needsUpdate ) {
437                    updateNodeInDB();
438                }
439            } else {
440                assignItem( itemKey );
441            }
442            return true;
443        }
444    
445        /**
446         * The enhancement of the second layout is, that every node knows about the items inserted in it's sons. This
447         * information can be used if the bbox of this node lies totally within the requested area, all items of the sons of
448         * this node are added automatically.
449         * 
450         * @param searchEnv
451         *            the area to get all items for.
452         * @param visitor
453         *            the list inwhich the items keys will be added.
454         * @throws IndexException
455         *             if a connection to the db failed.
456         */
457        private void queryWithLayoutTwo( Envelope searchEnv, List<T> visitor )
458                                throws IndexException {
459            if ( liesWithIn( searchEnv ) || level == qt.getDepth() ) {
460                getAssignedItems( visitor );
461            } else {
462                Envelope[] envs = split();
463                for ( int i = 0; i < envs.length; i++ ) {
464                    if ( !"".equals( fk_subnode[i] ) && envs[i].intersects( searchEnv ) ) {
465                        // check which subnodes are intersected by the
466                        // items envelope; just this nodes
467                        // are considered for futher processing
468                        DBNode<T> node = new DBNode<T>( fk_subnode[i], envs[i], qt, indexTable, jdbc, level + 1, version );
469                        node.queryWithLayoutTwo( searchEnv, visitor );
470                    }
471                }
472            }
473    
474        }
475    
476        private void queryWithLayoutOne( Envelope searchEnv, List<T> visitor, int level )
477                                throws IndexException {
478            /*
479             * if ( level == qt.getDepth() || (searchEnv.getWidth() > envelope.getWidth() || searchEnv.getHeight() >
480             * envelope.getHeight()) ) { addAssignedItems( visitor ); } else {
481             */
482            getAssignedItems( visitor );
483            if ( level != qt.getDepth() ) {
484                Envelope[] envs = split();
485                for ( int i = 0; i < envs.length; i++ ) {
486                    if ( !"".equals( fk_subnode[i] ) && envs[i].intersects( searchEnv ) ) {
487                        // check which subnodes are intersected by the
488                        // items envelope; just this nodes
489                        // are considered for futher processing
490                        DBNode<T> node = new DBNode<T>( fk_subnode[i], envs[i], qt, indexTable, jdbc, level + 1, version );
491                        node.queryWithLayoutOne( searchEnv, visitor, level + 1 );
492                    }
493                }
494            }
495        }
496    
497        /**
498         * The delete method which can handle the layout with version two.
499         * 
500         * @param itemKey
501         *            the key to be deleted.
502         * @param itemEnv
503         *            the bbox of the item.
504         * @param parent
505         *            the parent node of this qt-node or <code>null</code> if this is the root node.
506         * @throws IndexException
507         *             if somehow the connection to the db is lost or an error occurred while executing the deletion.
508         */
509        private boolean deleteWithLayoutTwo( T itemKey, Envelope itemEnv, DBNode<T> parent, Connection dbConnection )
510                                throws IndexException {
511            List<T> items = new ArrayList<T>();
512            // first get all items assigned to this node, and remove the fitting item from the idx-item
513            // join table.
514            getAssignedItems( items );
515            if ( items.contains( itemKey ) ) {
516                if ( deleteItemFromDB( itemKey, dbConnection ) ) {
517                    items.remove( itemKey );
518                }
519            }
520            if ( level != qt.getDepth() ) {
521                Envelope[] envs = split();
522                for ( int i = 0; i < fk_subnode.length; ++i ) {
523                    if ( !"".equals( fk_subnode[i] ) && envs[i].intersects( itemEnv ) ) {
524                        DBNode<T> node = new DBNode<T>( fk_subnode[i], envs[i], qt, indexTable, jdbc, level + 1, version );
525                        node.deleteWithLayoutTwo( itemKey, itemEnv, this, dbConnection );
526                    }
527                }
528            }
529            // If this is not the root of the quadtree, delete this node from the parent if it is a leaf
530            // and has no items.
531            if ( parent != null ) {
532                if ( items.isEmpty() && !hasSons() ) {
533                    if ( deletNodeFromDB( dbConnection ) ) {
534                        if ( parent.deleteSon( id, dbConnection ) ) {
535                            qt.addToCache( parent );
536                            qt.removeFromCache( this );
537                        }
538                    }
539                }
540            }
541            return true;
542        }
543    
544        /**
545         * @param dbConnection
546         *            a live connection to the database
547         * @return true if the node has been successfully removed from the database.
548         */
549        private boolean deletNodeFromDB( Connection dbConnection ) {
550            if ( hasSons() ) {
551                LOG.logError( "Trying to delete a node (with id: '" + id + "') which still has sons, this may not happen!" );
552                return false;
553            }
554            StringBuilder deleteStatement = new StringBuilder( 400 );
555            deleteStatement.append( "DELETE FROM " ).append( indexTable );
556            deleteStatement.append( " WHERE ID = '" ).append( id ).append( "'" );
557            LOG.logDebug( "Trying to delete dbnode with id='" + id + "'. The sql statement is as follows:\n"
558                          + deleteStatement.toString() );
559            Statement stmt = null;
560            ResultSet rs = null;
561            try {
562                stmt = dbConnection.createStatement();
563                rs = stmt.executeQuery( deleteStatement.toString() );
564            } catch ( SQLException e ) {
565                LOG.logDebug( "Could not delete the dbNode with id='" + id + "' because: " + e.getMessage() );
566                return false;
567            } finally {
568                try {
569                    if ( rs != null ) {
570                        rs.close();
571                    }
572                    if ( stmt != null ) {
573                        stmt.close();
574                    }
575                } catch ( SQLException e ) {
576                    LOG.logDebug( "An error occurred while trying to close statement and/or resultset because: "
577                                  + e.getMessage() );
578                }
579    
580            }
581            return true;
582        }
583    
584        /**
585         * @return true if this node has a son (e.g. one of the fk_subnodes is not empty ).
586         */
587        private boolean hasSons() {
588            return !( "".equals( fk_subnode[0] ) && "".equals( fk_subnode[1] ) && "".equals( fk_subnode[2] ) && "".equals( fk_subnode[3] ) );
589    
590        }
591    
592        /**
593         * Deletes the specifies item from the quadtree, e.g. removing it from the idx_table_item join table, where the
594         * FK_QTNODE equals this.id and the FK_ITEM = itemKey.
595         * 
596         * @param itemKey
597         *            to be deleted
598         * @param dbConnection
599         *            used to execute the query.
600         * @return true if the item was deleted from the database, false otherwhise.
601         */
602        private boolean deleteItemFromDB( T itemKey, Connection dbConnection ) {
603            if ( itemKey == null ) {
604                LOG.logDebug( "Trying to delete an itemkey which is null, this may not be (current node id='" + id + "')" );
605                return false;
606            }
607            StringBuilder delItemStatement = new StringBuilder( 400 );
608            delItemStatement.append( "DELETE FROM " ).append( indexItemTable );
609            delItemStatement.append( " WHERE FK_QTNODE = '" ).append( id ).append( "'" );
610            delItemStatement.append( " AND FK_ITEM = " );
611            if ( itemKey instanceof String ) {
612                delItemStatement.append( "'" );
613            }
614            delItemStatement.append( itemKey );
615            if ( itemKey instanceof String ) {
616                delItemStatement.append( "'" );
617            }
618            LOG.logDebug( "Trying to delete item with key='" + itemKey + "' from node with id='" + id
619                          + "'. The sql statement is as follows:\n" + delItemStatement.toString() );
620            Statement stmt = null;
621            ResultSet rs = null;
622            try {
623                stmt = dbConnection.createStatement();
624                rs = stmt.executeQuery( delItemStatement.toString() );
625            } catch ( SQLException e ) {
626                LOG.logDebug( "Could not delete the item with key='" + itemKey + "' from node with id='" + id
627                              + "' because: " + e.getMessage() );
628                return false;
629            } finally {
630                try {
631                    if ( rs != null ) {
632                        rs.close();
633                    }
634                    if ( stmt != null ) {
635                        stmt.close();
636                    }
637                } catch ( SQLException e ) {
638                    LOG.logDebug( "An error occurred while trying to close statement and/or resultset because: "
639                                  + e.getMessage() );
640                }
641    
642            }
643    
644            return true;
645    
646        }
647    
648        /**
649         * Deletes a son from the database, e.g. perform an update to null on the idx_table. And if successfull also sets
650         * the fk_subnode to an empty string.
651         * 
652         * @param sonsID
653         *            which must be set to null.
654         * @param dbConnection
655         *            which will be used to perform the query.
656         * @return true if the son was deleted.
657         */
658        private boolean deleteSon( String sonsID, Connection dbConnection ) {
659            if ( sonsID == null || "".equals( sonsID.trim() ) ) {
660                LOG.logDebug( "Trying to delete a son with an id which is null, this may not be (parent node id='" + id
661                              + "')" );
662                return false;
663            }
664            for ( int i = 0; i < fk_subnode.length; ++i ) {
665                if ( fk_subnode[i].trim().equals( sonsID.trim() ) ) {
666                    StringBuilder delSonStatement = new StringBuilder( 400 );
667                    delSonStatement.append( "UPDATE " ).append( indexTable );
668                    delSonStatement.append( " SET FK_SUBNODE" ).append( ( i + 1 ) ).append( " = 'null'" );
669                    delSonStatement.append( " WHERE ID = '" ).append( id ).append( "'" );
670    
671                    LOG.logDebug( "Trying to delete son with id='" + sonsID + "' from (parent) node with id='" + this.id
672                                  + "'. The sql statement is as follows:\n" + delSonStatement.toString() );
673                    Statement stmt = null;
674                    ResultSet rs = null;
675                    try {
676                        stmt = dbConnection.createStatement();
677                        rs = stmt.executeQuery( delSonStatement.toString() );
678                    } catch ( SQLException e ) {
679                        LOG.logDebug( "Could not delete son with id='" + sonsID + "' from (parent) node with id='"
680                                      + this.id + "' because: " + e.getMessage() );
681                        return false;
682                    } finally {
683                        try {
684                            if ( rs != null ) {
685                                rs.close();
686                            }
687                            if ( stmt != null ) {
688                                stmt.close();
689                            }
690                        } catch ( SQLException e ) {
691                            LOG.logDebug( "An error occurred while trying to close statement and/or resultset because: "
692                                          + e.getMessage() );
693                        }
694    
695                    }
696                    fk_subnode[i] = "";
697                    return true;
698                }
699    
700            }
701    
702            LOG.logDebug( "It seems this (parent) node with id='" + id + "' has no son with id='" + sonsID
703                          + "', all sons of this node  are:\n " + "- fk_subnode[0]='" + fk_subnode[0] + "'\n "
704                          + "- fk_subnode[1]='" + fk_subnode[1] + "'\n " + "- fk_subnode[2]='" + fk_subnode[2] + "'\n "
705                          + "- fk_subnode[3]='" + fk_subnode[3] + "'" );
706            return false;
707        }
708    
709        /**
710         * load all Node parameters from the database.
711         * 
712         * @return true if a node with current ID is already available from the database and the parameters have been read
713         *         successfully.
714         * 
715         */
716        private boolean loadNodeFromDB()
717                                throws IndexException {
718            Connection con = null;
719            DBConnectionPool pool = null;
720            boolean available = true;
721            try {
722                pool = DBConnectionPool.getInstance();
723                con = pool.acquireConnection( jdbc.getDriver(), jdbc.getURL(), jdbc.getUser(), jdbc.getPassword() );
724    
725                StringBuilder sb = new StringBuilder( 100 );
726                sb.append( "Select * from " ).append( indexTable );
727                sb.append( " where ID = '" ).append( id ).append( "'" );
728    
729                Statement stmt = con.createStatement();
730                ResultSet rs = stmt.executeQuery( sb.toString() );
731                if ( rs.next() ) {
732                    double minx = rs.getFloat( "MINX" );
733                    double miny = rs.getFloat( "MINY" );
734                    double maxx = rs.getFloat( "MAXX" );
735                    double maxy = rs.getFloat( "MAXY" );
736                    envelope = GeometryFactory.createEnvelope( minx, miny, maxx, maxy, null );
737                    fk_subnode[0] = rs.getString( "FK_SUBNODE1" );
738                    fk_subnode[1] = rs.getString( "FK_SUBNODE2" );
739                    fk_subnode[2] = rs.getString( "FK_SUBNODE3" );
740                    fk_subnode[3] = rs.getString( "FK_SUBNODE4" );
741                } else {
742                    available = false;
743                }
744                rs.close();
745                stmt.close();
746            } catch ( Exception e ) {
747                LOG.logError( e.getMessage(), e );
748                throw new IndexException( "could not load node definition from database", e );
749            } finally {
750                try {
751                    if ( con != null && pool != null ) {
752                        pool.releaseConnection( con, jdbc.getDriver(), jdbc.getURL(), jdbc.getUser(), jdbc.getPassword() );
753                    }
754                } catch ( Exception e1 ) {
755                    e1.printStackTrace();
756                }
757            }
758            return available;
759        }
760    
761        /**
762         * updates the database representation of the current node
763         * 
764         * @throws IndexException
765         */
766        private void updateNodeInDB()
767                                throws IndexException {
768            Connection con = null;
769            DBConnectionPool pool = null;
770            try {
771                pool = DBConnectionPool.getInstance();
772                con = pool.acquireConnection( jdbc.getDriver(), jdbc.getURL(), jdbc.getUser(), jdbc.getPassword() );
773    
774                StringBuilder sb = new StringBuilder( 250 );
775                sb.append( "UPDATE " ).append( indexTable ).append( " set " );
776                boolean submit = false;
777                for ( int i = 0; i < fk_subnode.length; i++ ) {
778                    if ( !"".equals( fk_subnode[i] ) ) {
779                        sb.append( " FK_SUBNODE" ).append( i + 1 ).append( "='" );
780                        sb.append( fk_subnode[i] ).append( "' ," );
781                        submit = true;
782                    }
783                }
784                if ( submit ) {
785                    // just execute update if at least one sub node != null
786                    sb = new StringBuilder( sb.substring( 0, sb.length() - 1 ) );
787                    sb.append( " where ID = '" ).append( id ).append( "'" );
788                    Statement stmt = con.createStatement();
789                    stmt.execute( sb.toString() );
790                    stmt.close();
791                }
792            } catch ( Exception e ) {
793                LOG.logError( e.getMessage(), e );
794                throw new IndexException( "could not update node definition at database " + "for node: " + id, e );
795            } finally {
796                try {
797                    if ( pool != null && con != null ) {
798                        pool.releaseConnection( con, jdbc.getDriver(), jdbc.getURL(), jdbc.getUser(), jdbc.getPassword() );
799                    }
800                } catch ( Exception e1 ) {
801                    e1.printStackTrace();
802                }
803            }
804            qt.addToCache( this );
805        }
806    
807        /**
808         * Get the item (IDs) assigned to this node and stores them in the given list
809         * 
810         * @param visitor
811         * @throws IndexException
812         */
813        private void getAssignedItems( List<T> visitor )
814                                throws IndexException {
815    
816            Connection con = null;
817            DBConnectionPool pool = null;
818            try {
819                pool = DBConnectionPool.getInstance();
820                con = pool.acquireConnection( jdbc.getDriver(), jdbc.getURL(), jdbc.getUser(), jdbc.getPassword() );
821    
822                StringBuilder sb = new StringBuilder( 100 );
823                sb.append( "SELECT DISTINCT FK_ITEM from " ).append( indexTable ).append( "_ITEM" );
824                sb.append( " where " ).append( "FK_QTNODE = '" ).append( id ).append( "'" );
825                Statement stmt = con.createStatement();
826                ResultSet rs = stmt.executeQuery( sb.toString() );
827    
828                while ( rs.next() ) {
829                    Object result = rs.getObject( 1 );
830                    if ( result != null ) {
831                        T s = (T) result;
832                        if ( !visitor.contains( s ) ) {
833                            visitor.add( s );
834                        }
835                    } else {
836                        LOG.logDebug( "Found a node (id='" + id + "') with a null value." );
837                    }
838                }
839                stmt.close();
840            } catch ( DBPoolException e ) {
841                throw new IndexException( "Database QuadTree could not acquire sons of a node because: " + e.getMessage() );
842            } catch ( SQLException e ) {
843                throw new IndexException( "Database QuadTree could not acquire sons of a node because: " + e.getMessage() );
844            } finally {
845                try {
846                    if ( pool != null && con != null ) {
847                        pool.releaseConnection( con, jdbc.getDriver(), jdbc.getURL(), jdbc.getUser(), jdbc.getPassword() );
848                    }
849                } catch ( Exception e1 ) {
850                    e1.printStackTrace();
851                }
852            }
853        }
854    
855        private Envelope[] split() {
856            Envelope[] envs = new Envelope[4];
857            double nW = envelope.getWidth() / 2d;
858            double nH = envelope.getHeight() / 2d;
859    
860            envs[0] = GeometryFactory.createEnvelope( envelope.getMin().getX(), envelope.getMin().getY(),
861                                                      envelope.getMin().getX() + nW, envelope.getMin().getY() + nH, null );
862            envs[1] = GeometryFactory.createEnvelope( envelope.getMin().getX() + nW, envelope.getMin().getY(),
863                                                      envelope.getMin().getX() + ( 2 * nW ), envelope.getMin().getY() + nH,
864                                                      null );
865            envs[2] = GeometryFactory.createEnvelope( envelope.getMin().getX() + nW, envelope.getMin().getY() + nH,
866                                                      envelope.getMin().getX() + ( 2 * nW ), envelope.getMin().getY()
867                                                                                             + ( 2 * nH ), null );
868            envs[3] = GeometryFactory.createEnvelope( envelope.getMin().getX(), envelope.getMin().getY() + nH,
869                                                      envelope.getMin().getX() + nW, envelope.getMin().getY() + ( 2 * nH ),
870                                                      null );
871    
872            return envs;
873        }
874    
875        // /**
876        // * @param itemKey
877        // * the key of the item to get the bbox for.
878        // * @return the envelope of item with itemKey, currently stored in the quadtree.
879        // */
880        // public Envelope getBoundingBoxForItem( T itemKey ) {
881        // return null;
882        // }
883    
884    }