001: //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/trunk/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(
128: "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 "
166: + e.getMessage());
167: }
168: }
169:
170: /**
171: * @see PageFile#readNode(int)
172: */
173: protected Node readNode(int pageFileNumber)
174: throws PageFileException {
175:
176: Node node = null;
177:
178: try {
179: file.seek(16 + (pageFileNumber * pageSize));
180:
181: int read = file.read(buffer);
182:
183: if (pageSize == read) {
184:
185: DataInputStream ds = new DataInputStream(
186: new ByteArrayInputStream(buffer));
187:
188: int type = ds.readInt();
189: if (type == 1)
190: node = new LeafNode(-1, this );
191: else
192: node = new NoneLeafNode(-1, this );
193:
194: node.place = ds.readInt();
195: node.counter = ds.readInt();
196: node.parentNode = ds.readInt();
197: node.pageNumber = ds.readInt();
198:
199: if (type == 1) {
200: for (int i = 0; i < capacity; i++)
201: ((LeafNode) node).data[i] = ds.readInt();
202: } else {
203: for (int i = 0; i < capacity; i++)
204: ((NoneLeafNode) node).childNodes[i] = ds
205: .readInt();
206: }
207:
208: node.unionMinBB = readNextHyperBoundingBox(ds);
209:
210: for (int i = 0; i < capacity; i++)
211: node.hyperBBs[i] = readNextHyperBoundingBox(ds);
212:
213: ds.close();
214: } else {
215: throw new PageFileException(
216: "Exception during read operation");
217: }
218:
219: return node;
220:
221: } catch (IOException e) {
222: e.fillInStackTrace();
223: throw new PageFileException(
224: "PageFileException occured ! \n " + e.getMessage());
225: }
226: }
227:
228: // reads the next HyperBoundingBox from the byte buffer
229: private HyperBoundingBox readNextHyperBoundingBox(DataInputStream ds)
230: throws IOException {
231:
232: double[] point1, point2;
233: point1 = new double[dimension];
234: point2 = new double[dimension];
235:
236: for (int i = 0; i < dimension; i++)
237: point1[i] = ds.readDouble();
238:
239: for (int i = 0; i < dimension; i++)
240: point2[i] = ds.readDouble();
241:
242: return new HyperBoundingBox(new HyperPoint(point1),
243: new HyperPoint(point2));
244: }
245:
246: /**
247: * @see PageFile#writeNode(Node)
248: */
249: protected int writeNode(Node node) throws PageFileException {
250: try {
251:
252: if (node.pageNumber < 0) {
253: if (!emptyPages.empty())
254: node.setPageNumber(emptyPages.pop());
255: else
256: node
257: .setPageNumber((int) ((file.length() - 16) / pageSize));
258: }
259:
260: ByteArrayOutputStream bs = new ByteArrayOutputStream(
261: pageSize);
262: DataOutputStream ds = new DataOutputStream(bs);
263:
264: int type;
265: if (node instanceof LeafNode)
266: type = 1;
267: else
268: type = 2;
269:
270: ds.writeInt(type);
271:
272: ds.writeInt(node.place);
273: ds.writeInt(node.counter);
274: ds.writeInt(node.parentNode);
275: ds.writeInt(node.pageNumber);
276:
277: if (node instanceof LeafNode) {
278: for (int i = 0; i < node.counter; i++) {
279: ds.writeInt(((LeafNode) node).data[i]);
280: }
281: for (int i = 0; i < (capacity - node.counter); i++)
282: ds.writeInt(-1);
283: } else {
284: for (int i = 0; i < node.counter; i++) {
285: ds.writeInt(((NoneLeafNode) node).childNodes[i]);
286: }
287:
288: for (int i = 0; i < (capacity - node.counter); i++)
289: ds.writeInt(-1);
290: }
291:
292: for (int i = 0; i < dimension; i++)
293: ds.writeDouble(node.unionMinBB.getPMin().getCoord(i));
294:
295: for (int i = 0; i < dimension; i++)
296: ds.writeDouble(node.unionMinBB.getPMax().getCoord(i));
297:
298: for (int j = 0; j < node.counter; j++) {
299: for (int i = 0; i < dimension; i++)
300: ds.writeDouble(node.hyperBBs[j].getPMin().getCoord(
301: i));
302:
303: for (int i = 0; i < dimension; i++)
304: ds.writeDouble(node.hyperBBs[j].getPMax().getCoord(
305: i));
306: }
307:
308: for (int j = 0; j < (capacity - node.counter); j++) {
309: for (int i = 0; i < (dimension * 2); i++)
310: ds.writeDouble(-1);
311: }
312:
313: ds.flush();
314: bs.flush();
315:
316: file.seek(16 + (pageSize * node.pageNumber));
317:
318: file.write(bs.toByteArray());
319:
320: ds.close();
321:
322: return node.pageNumber;
323:
324: } catch (IOException e) {
325: e.fillInStackTrace();
326: throw new PageFileException(
327: "PageFileException occured ! \n " + e.getMessage());
328: }
329: }
330:
331: /**
332: * @see PageFile#deleteNode(int)
333: */
334: protected Node deleteNode(int pageNumber) throws PageFileException {
335: Node node = this .readNode(pageNumber);
336: try {
337: file.seek(16 + (pageSize * node.pageNumber));
338: file.writeInt(EMPTY_PAGE);
339: } catch (IOException e) {
340: e.fillInStackTrace();
341: throw new PageFileException(
342: "PageFileException occured ! \n " + e.getMessage());
343: }
344:
345: emptyPages.push(new Integer(pageNumber));
346: return node;
347: }
348:
349: /**
350: * @see PageFile#close()
351: */
352: protected void close() throws PageFileException {
353: try {
354: file.close();
355: } catch (IOException e) {
356: e.fillInStackTrace();
357: throw new PageFileException(
358: "PageFileException during close()");
359: }
360:
361: closed = true;
362: }
363:
364: protected void finalize() throws Throwable {
365: if (!closed)
366: file.close();
367:
368: super.finalize();
369: }
370: }
|