    001    //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/branches/2.4_testing/src/org/deegree/io/rtree/PersistentPageFile.java $
    002    //----------------------------------------
    003    //RTree implementation.
    004    //Copyright (C) 2002-2004 Wolfgang Baer - WBaer@gmx.de
    005    //
    006    //This library is free software; you can redistribute it and/or
    007    //modify it under the terms of the GNU Lesser General Public
    008    //License as published by the Free Software Foundation; either
    009    //version 2.1 of the License, or (at your option) any later version.
    010    //
    011    //This library is distributed in the hope that it will be useful,
    012    //but WITHOUT ANY WARRANTY; without even the implied warranty of
    013    //MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    014    //Lesser General Public License for more details.
    015    //
    016    //You should have received a copy of the GNU Lesser General Public
    017    //License along with this library; if not, write to the Free Software
    018    //Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    019    //----------------------------------------
    020
    021    package org.deegree.io.rtree;
    022
    023    import java.io.ByteArrayInputStream;
    024    import java.io.ByteArrayOutputStream;
    025    import java.io.DataInputStream;
    026    import java.io.DataOutputStream;
    027    import java.io.EOFException;
    028    import java.io.File;
    029    import java.io.IOException;
    030    import java.io.RandomAccessFile;
    031    import java.util.Stack;
    032
    033    /**
    034     * <p>
    035     * A persistent implementation of a PageFile implemented based on a RandomAccesFile.
    036     * </p>
    037     * <p>
    038     * Structure of the File<br>
    039     * <br>
    040     * <br> -- Header --<br>
    041     * int pageFileVersion<br>
    042     * int dimension<br>
    043     * int capacity = maxLoad + 1 for Overflow<br>
    044     * int minimum<br>
    045     * <br>
    046     * <br> -- Body --<br>
    047     * a sequence of page one after another with:<br>
    048     * int typ - 1 LeafNode 2 NoneLeafNode<br>
    049     * int place - index of entry of this node in father node<br>
    050     * int counter - current used space in the node<br>
    051     * int parentNode - page number of father node<br>
    052     * int pageNumber - own page number<br> - for(i = 0; i < capacity; i++)<br>
    053     * int data Entry i - page number of childnode or object ID of data entry<br> - always dependend on
    054     * dimension = x<br>
    055     * double pMin x.Dimension - pMin of the common HyperBoundingBox<br>
    056     * double pMax x.Dimension - pMax of the common HyperBoundingBox<br> - for(i = 0; i < capacity;
    057     * i++)<br>
    058     * double pMin x.Dimension - pMin HyperBoundingBox for Entry i<br>
    059     * double pMax x.Dimension - pMax HyperBoundingBox for Entry i<br>
    060     * <br>
    061     * <br>
    062     * int entspr. 4 Bytes - double entspr. 8 Bytes<br>
    063     * <br>
    064     * <br>
    065     * PageSize = (4 * (5 + capacity)) + (capacity + 1) * (dimension * 16)<br>
    066     * <br>
    067     * </p>
    068     *
    069     * @author Wolfgang Baer - WBaer@gmx.de
    070     */
    071    class PersistentPageFile extends PageFile {
    072
    073        /** magic number */
    074        private static final int PAGEFILE_VERSION = 060676002;
    075
    076        private static final int EMPTY_PAGE = -22;
    077
    078        private RandomAccessFile file;
    079
    080        private int pageSize;
    081
    082        private String fileName;
    083
    084        private byte[] buffer;
    085
    086        private Stack<Integer> emptyPages;
    087
    088        private boolean closed;
    089
    090        /**
    091         * Constructor
    092         *
    093         * @param fileName
    094         */
    095        protected PersistentPageFile( String fileName ) {
    096            super();
    097            this.fileName = fileName;
    098            this.emptyPages = new Stack<Integer>();
    099            this.closed = false;
    100        }
    101
    102        /**
    103         * Initializes the PersistentPageFile. Overrides initialize in PageFile.
    104         *
    105         * @param dimension -
    106         *            dimension of the data
    107         * @param capacity -
    108         *            capacity of a node
    109         * @throws PageFileException
    110         */
    111        protected void initialize( int dimension, int capacity )
    112                                throws PageFileException {
    113            super.initialize( dimension, capacity );
    114
    115            File fileTest = new File( fileName );
    116
    117            try {
    118                if ( dimension == -999 ) {
    119                    // Initialize from existing file
    120
    121                    if ( !fileTest.exists() )
    122                        throw new PageFileException( "File does not exist" );
    123
    124                    file = new RandomAccessFile( fileTest, "rw" );
    125                    // Test if it is a PersistentPageFile
    126                    file.seek( 0 );
    127                    if ( file.readInt() != PAGEFILE_VERSION )
    128                        throw new PageFileException( "Not a PersistentPageFile or wrong version" );
    129
    130                    // Reading header - Initializing PageFile
    131                    this.dimension = file.readInt();
    132                    this.capacity = file.readInt();
    133                    this.minimum = file.readInt();
    134                    this.pageSize = ( ( 4 * ( 5 + this.capacity ) ) + ( ( this.capacity + 1 ) * ( this.dimension * 16 ) ) );
    135                    this.buffer = new byte[pageSize];
    136
    137                    // reading empty pages in Stack
    138                    int i = 0;
    139                    try {
    140                        while ( true ) {
    141                            file.seek( 16 + ( i * pageSize ) );
    142                            if ( EMPTY_PAGE == file.readInt() )
    143                                emptyPages.push( new Integer( i ) );
    144                            i++;
    145                        }
    146                    } catch ( EOFException eof ) { // not an exception - wanted
    147                    }
    148                } else {
    149                    // new file
    150                    file = new RandomAccessFile( fileTest, "rw" );
    151                    file.setLength( 0 );
    152                    this.pageSize = ( ( 4 * ( 5 + capacity ) ) + ( ( capacity + 1 ) * ( dimension * 16 ) ) );
    153                    this.buffer = new byte[pageSize];
    154
    155                    // writing header
    156                    file.seek( 0 );
    157                    file.writeInt( PAGEFILE_VERSION );
    158                    file.writeInt( this.dimension );
    159                    file.writeInt( this.capacity );
    160                    file.writeInt( this.minimum );
    161
    162                }
    163            } catch ( IOException e ) {
    164                e.fillInStackTrace();
    165                throw new PageFileException( "IOException occured: \n " + e.getMessage() );
    166            }
    167        }
    168
    169        /**
    170         * @see PageFile#readNode(int)
    171         */
    172        protected Node readNode( int pageFileNumber )
    173                                throws PageFileException {
    174
    175            Node node = null;
    176
    177            try {
    178                file.seek( 16 + ( pageFileNumber * pageSize ) );
    179
    180                int read = file.read( buffer );
    181
    182                if ( pageSize == read ) {
    183
    184                    DataInputStream ds = new DataInputStream( new ByteArrayInputStream( buffer ) );
    185
    186                    int type = ds.readInt();
    187                    if ( type == 1 )
    188                        node = new LeafNode( -1, this );
    189                    else
    190                        node = new NoneLeafNode( -1, this );
    191
    192                    node.place = ds.readInt();
    193                    node.counter = ds.readInt();
    194                    node.parentNode = ds.readInt();
    195                    node.pageNumber = ds.readInt();
    196
    197                    if ( type == 1 ) {
    198                        for ( int i = 0; i < capacity; i++ )
    199                            ( (LeafNode) node ).data[i] = ds.readInt();
    200                    } else {
    201                        for ( int i = 0; i < capacity; i++ )
    202                            ( (NoneLeafNode) node ).childNodes[i] = ds.readInt();
    203                    }
    204
    205                    node.unionMinBB = readNextHyperBoundingBox( ds );
    206
    207                    for ( int i = 0; i < capacity; i++ )
    208                        node.hyperBBs[i] = readNextHyperBoundingBox( ds );
    209
    210                    ds.close();
    211                } else {
    212                    throw new PageFileException( "Exception during read operation" );
    213                }
    214
    215                return node;
    216
    217            } catch ( IOException e ) {
    218                e.fillInStackTrace();
    219                throw new PageFileException( "PageFileException occured ! \n " + e.getMessage() );
    220            }
    221        }
    222
    223        // reads the next HyperBoundingBox from the byte buffer
    224        private HyperBoundingBox readNextHyperBoundingBox( DataInputStream ds )
    225                                throws IOException {
    226
    227            double[] point1, point2;
    228            point1 = new double[dimension];
    229            point2 = new double[dimension];
    230
    231            for ( int i = 0; i < dimension; i++ )
    232                point1[i] = ds.readDouble();
    233
    234            for ( int i = 0; i < dimension; i++ )
    235                point2[i] = ds.readDouble();
    236
    237            return new HyperBoundingBox( new HyperPoint( point1 ), new HyperPoint( point2 ) );
    238        }
    239
    240        /**
    241         * @see PageFile#writeNode(Node)
    242         */
    243        protected int writeNode( Node node )
    244                                throws PageFileException {
    245            try {
    246
    247                if ( node.pageNumber < 0 ) {
    248                    if ( !emptyPages.empty() )
    249                        node.setPageNumber( emptyPages.pop() );
    250                    else
    251                        node.setPageNumber( (int) ( ( file.length() - 16 ) / pageSize ) );
    252                }
    253
    254                ByteArrayOutputStream bs = new ByteArrayOutputStream( pageSize );
    255                DataOutputStream ds = new DataOutputStream( bs );
    256
    257                int type;
    258                if ( node instanceof LeafNode )
    259                    type = 1;
    260                else
    261                    type = 2;
    262
    263                ds.writeInt( type );
    264
    265                ds.writeInt( node.place );
    266                ds.writeInt( node.counter );
    267                ds.writeInt( node.parentNode );
    268                ds.writeInt( node.pageNumber );
    269
    270                if ( node instanceof LeafNode ) {
    271                    for ( int i = 0; i < node.counter; i++ ) {
    272                        ds.writeInt( ( (LeafNode) node ).data[i] );
    273                    }
    274                    for ( int i = 0; i < ( capacity - node.counter ); i++ )
    275                        ds.writeInt( -1 );
    276                } else {
    277                    for ( int i = 0; i < node.counter; i++ ) {
    278                        ds.writeInt( ( (NoneLeafNode) node ).childNodes[i] );
    279                    }
    280
    281                    for ( int i = 0; i < ( capacity - node.counter ); i++ )
    282                        ds.writeInt( -1 );
    283                }
    284
    285                for ( int i = 0; i < dimension; i++ )
    286                    ds.writeDouble( node.unionMinBB.getPMin().getCoord( i ) );
    287
    288                for ( int i = 0; i < dimension; i++ )
    289                    ds.writeDouble( node.unionMinBB.getPMax().getCoord( i ) );
    290
    291                for ( int j = 0; j < node.counter; j++ ) {
    292                    for ( int i = 0; i < dimension; i++ )
    293                        ds.writeDouble( node.hyperBBs[j].getPMin().getCoord( i ) );
    294
    295                    for ( int i = 0; i < dimension; i++ )
    296                        ds.writeDouble( node.hyperBBs[j].getPMax().getCoord( i ) );
    297                }
    298
    299                for ( int j = 0; j < ( capacity - node.counter ); j++ ) {
    300                    for ( int i = 0; i < ( dimension * 2 ); i++ )
    301                        ds.writeDouble( -1 );
    302                }
    303
    304                ds.flush();
    305                bs.flush();
    306
    307                file.seek( 16 + ( pageSize * node.pageNumber ) );
    308
    309                file.write( bs.toByteArray() );
    310
    311                ds.close();
    312
    313                return node.pageNumber;
    314
    315            } catch ( IOException e ) {
    316                e.fillInStackTrace();
    317                throw new PageFileException( "PageFileException occured ! \n " + e.getMessage() );
    318            }
    319        }
    320
    321        /**
    322         * @see PageFile#deleteNode(int)
    323         */
    324        protected Node deleteNode( int pageNumber )
    325                                throws PageFileException {
    326            Node node = this.readNode( pageNumber );
    327            try {
    328                file.seek( 16 + ( pageSize * node.pageNumber ) );
    329                file.writeInt( EMPTY_PAGE );
    330            } catch ( IOException e ) {
    331                e.fillInStackTrace();
    332                throw new PageFileException( "PageFileException occured ! \n " + e.getMessage() );
    333            }
    334
    335            emptyPages.push( new Integer( pageNumber ) );
    336            return node;
    337        }
    338
    339        /**
    340         * @see PageFile#close()
    341         */
    342        protected void close()
    343                                throws PageFileException {
    344            try {
    345                file.close();
    346            } catch ( IOException e ) {
    347                e.fillInStackTrace();
    348                throw new PageFileException( "PageFileException during close()" );
    349            }
    350
    351            closed = true;
    352        }
    353
    354        protected void finalize()
    355                                throws Throwable {
    356            if ( !closed )
    357                file.close();
    358
    359            super.finalize();
    360        }
    361    }