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 }