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