001    //$HeadURL: svn+ssh://jwilden@svn.wald.intevation.org/deegree/base/branches/2.5_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    }