0001: //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/trunk/src/org/deegree/io/dbaseapi/DBaseIndex.java $
0002: /*---------------- FILE HEADER ------------------------------------------
0003:
0004: This file is part of deegree.
0005: Copyright (C) 2001-2008 by:
0006: EXSE, Department of Geography, University of Bonn
0007: http://www.giub.uni-bonn.de/deegree/
0008: lat/lon GmbH
0009: http://www.lat-lon.de
0010:
0011: This library is free software; you can redistribute it and/or
0012: modify it under the terms of the GNU Lesser General Public
0013: License as published by the Free Software Foundation; either
0014: version 2.1 of the License, or (at your option) any later version.
0015:
0016: This library is distributed in the hope that it will be useful,
0017: but WITHOUT ANY WARRANTY; without even the implied warranty of
0018: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0019: Lesser General Public License for more details.
0020:
0021: You should have received a copy of the GNU Lesser General Public
0022: License along with this library; if not, write to the Free Software
0023: Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
0024:
0025: Contact:
0026:
0027: Andreas Poth
0028: lat/lon GmbH
0029: Aennchenstr. 19
0030: 53115 Bonn
0031: Germany
0032: E-Mail: poth@lat-lon.de
0033:
0034: Prof. Dr. Klaus Greve
0035: Department of Geography
0036: University of Bonn
0037: Meckenheimer Allee 166
0038: 53115 Bonn
0039: Germany
0040: E-Mail: greve@giub.uni-bonn.de
0041:
0042:
0043: ---------------------------------------------------------------------------*/
0044:
0045: package org.deegree.io.dbaseapi;
0046:
0047: import java.io.File;
0048: import java.io.FileNotFoundException;
0049: import java.io.IOException;
0050: import java.io.RandomAccessFile;
0051: import java.util.ArrayList;
0052: import java.util.Hashtable;
0053: import java.util.LinkedList;
0054: import java.util.ListIterator;
0055: import java.util.Stack;
0056:
0057: import org.deegree.model.spatialschema.ByteUtils;
0058:
0059: /**
0060: * <p>
0061: * A class for reading from and writing to DBase index files (*.ndx), maybe not 100% xbase
0062: * compatible!
0063: * </p>
0064: *
0065: * <p>
0066: * The fileformat is described at http://www.e-bachmann.dk/computing/databases/xbase/index.html
0067: * </p>
0068: *
0069: * <p>
0070: * This index is suitable for indexing both unique and non-unique columns. Unique indexing is much
0071: * faster than non-unique because it use a faster algorithm.
0072: * </p>
0073: *
0074: * <p>
0075: * The index file is a B+tree (sometimes called a paged B-tree) that consist of pages. There are two
0076: * page types, leaves and non-leafs. The starting page (eg. the page the search algorithm starts) is
0077: * the root page.
0078: * </p>
0079: *
0080: * <p>
0081: * <b>Searching goes as follows:</b>
0082: * <ul>
0083: * <li>load the root page (eg. the starting page)</li>
0084: * <li>if the page is a leaf
0085: * <ul>
0086: * <li>search for the requested key</li>
0087: * </ul>
0088: * </li>
0089: * <li>if the page is not a leaf (eg. the page has subpages)
0090: * <ul>
0091: * <li>search for a key that is equal to or bigger than the requested key</li>
0092: * <li>load the lower page</li>
0093: * <li>continue searching inside the lower page</li>
0094: * </ul>
0095: * </li>
0096: * </ul>
0097: * </p>
0098: *
0099: * <p>
0100: * Above algorithm is implemented in two different methods, one for unique indexes and one for
0101: * non-unique indexes. Searching unique indexes is easier because the algorithm is finished as soon
0102: * as it has found a key, the non-unique version of the algorithm has to find all keys present in
0103: * the index.
0104: * <p>
0105: *
0106: * <p>
0107: * <b>Inserting goes as follows:</b>
0108: * <ul>
0109: * <li>find the leaf page the key has to insert in</li>
0110: * <li>insert the key in the leaf page</li>
0111: * <li>if the leaf page is full (eg. validEntries > noOfKeysPerPage)
0112: * <ul>
0113: * <li>split the leaf page (results in two leaf pages)</li>
0114: * <li>add the first item of the new page to the parent page</li>
0115: * </ul>
0116: * </li>
0117: * <li>if the parent page is also full
0118: * <ul>
0119: * <li>split the parent page
0120: * <li>
0121: * <li>add the first item of the new page to it's parent page</li>
0122: * <li>etc.</li>
0123: * </ul>
0124: * </li>
0125: * </ul>
0126: * </p>
0127: *
0128: * <p>
0129: * If a page that splits does not have a parent page then a new page is created. This page is the
0130: * new starting page
0131: * </p>
0132: *
0133: * <p>
0134: * Handling different data types: The index can handle strings and numbers. Numbers are always
0135: * stored als IEEE doubles. The method addKey checks the given key and throws an exception if the
0136: * datatype of the key doesn't suit the index
0137: * </p>
0138: *
0139: * @author Reijer Copier, email: reijer.copier@idgis.nl
0140: */
0141:
0142: public class DBaseIndex {
0143: // The filename we use (this variable is used by toString)
0144: private String fileName;
0145:
0146: // The random access file we use
0147: protected RandomAccessFile file;
0148:
0149: // Attributes stored in the .ndx header
0150: protected int startingPageNo;
0151:
0152: // Attributes stored in the .ndx header
0153: protected int numberOfPages;
0154:
0155: // Attributes stored in the .ndx header
0156: protected int sizeOfKeyRecord;
0157:
0158: // Attributes stored in the .ndx header
0159: protected int keyLength;
0160:
0161: // Attributes stored in the .ndx header
0162: protected int noOfKeysPerPage;
0163:
0164: // Attributes stored in the .ndx header
0165: protected int keyType;
0166:
0167: private boolean uniqueFlag;
0168:
0169: // Buffers
0170: protected byte[] b = new byte[4];
0171:
0172: // Buffers
0173: protected byte[] page = new byte[512];
0174:
0175: // Buffers
0176: protected byte[] keyBytes;
0177:
0178: // Cache size
0179: protected int cacheSize = 20;
0180:
0181: // Cache
0182: private Cache cache = new Cache();
0183:
0184: /**
0185: * Inner class for the cache. The cache remembers recently used pages.
0186: */
0187: public class Cache {
0188:
0189: /**
0190: * Inner class for the cache items
0191: */
0192:
0193: class Item implements Comparable {
0194: /**
0195: * Create a new item with the given page
0196: */
0197: Item(Page p) {
0198: this .p = p;
0199: timeStamp = System.currentTimeMillis();
0200: }
0201:
0202: /**
0203: * Mark the item as used (eg. create a new time stamp)
0204: */
0205: void use() {
0206: timeStamp = System.currentTimeMillis();
0207: }
0208:
0209: long timeStamp;
0210:
0211: Page p;
0212:
0213: /**
0214: * Compare the time stamp from this object to the time stamp of another object
0215: */
0216: public int compareTo(Object o) {
0217: return new Long(timeStamp).compareTo(new Long(
0218: ((Item) o).timeStamp));
0219: }
0220: }
0221:
0222: private Hashtable<Integer, Item> pages;
0223:
0224: private LinkedList<Item> cacheItems;
0225:
0226: /**
0227: * Create a new cache
0228: */
0229: public Cache() {
0230: pages = new Hashtable<Integer, Item>();
0231: cacheItems = new LinkedList<Item>();
0232: }
0233:
0234: /**
0235: * Remove an item from the cache (this method searches for the last used item)
0236: */
0237: void removeItem() throws IOException {
0238: Item i = cacheItems.removeFirst();
0239:
0240: if (i.p.onStoreList)
0241: i.p.write();
0242:
0243: pages.remove(new Integer(i.p.number));
0244: }
0245:
0246: /**
0247: * Insert a new item into the cache
0248: */
0249: public void insert(int number, Page p) throws IOException {
0250: Item i = new Item(p);
0251:
0252: pages.put(new Integer(number), i);
0253: cacheItems.addLast(i);
0254:
0255: if (cacheItems.size() > cacheSize)
0256: removeItem();
0257: }
0258:
0259: /**
0260: * Get a page form the cache
0261: *
0262: * @return returns the addressed page or <code>null</code>
0263: */
0264: public Page get(int number) {
0265: Item item = pages.get(new Integer(number));
0266:
0267: if (item != null) {
0268: cacheItems.remove(item);
0269: item.use();
0270: cacheItems.addLast(item);
0271:
0272: return item.p;
0273: }
0274: return null;
0275: }
0276:
0277: /**
0278: * Flush the cache (eg. store modified pages)
0279: */
0280: public void flush() {
0281: ListIterator i = cacheItems.listIterator();
0282:
0283: while (i.hasNext()) {
0284: Item item = (Item) i.next();
0285:
0286: try {
0287: if (item.p.onStoreList) {
0288: item.p.write();
0289: }
0290: } catch (IOException e) {
0291: e.printStackTrace();
0292: }
0293: }
0294:
0295: cacheItems.clear();
0296: pages.clear();
0297: }
0298: }
0299:
0300: /**
0301: * Inner class for the key entries
0302: */
0303: private class KeyEntry {
0304: // Lower pointer and record number
0305: int lower;
0306:
0307: // Lower pointer and record number
0308: int record;
0309:
0310: // Data
0311: Comparable data;
0312:
0313: /**
0314: * Construct a new KeyEntry
0315: */
0316: KeyEntry(int lower, int record, Comparable data) {
0317: this .lower = lower;
0318: this .record = record;
0319: this .data = data;
0320: }
0321:
0322: /**
0323: * Read an existing KeyEntry
0324: */
0325: KeyEntry(int lower, int record) throws IOException {
0326: this .lower = lower;
0327: this .record = record;
0328: read();
0329: }
0330:
0331: /**
0332: * Compare this key entry to another key
0333: */
0334: int compareTo(Comparable key) {
0335: return this .data.compareTo(key);
0336: }
0337:
0338: /**
0339: * Read data from current file position
0340: */
0341: void read() throws IOException {
0342: if (keyType == 0) {
0343: file.read(keyBytes);
0344: data = new String(keyBytes).trim();
0345: } else {
0346: data = new Double(file.readDouble());
0347: }
0348: }
0349:
0350: /**
0351: * Write data to current file position
0352: */
0353: void write() throws IOException {
0354: if (keyType == 0) {
0355: byte[] currentKeyBytes = ((String) data).getBytes();
0356: file.write(currentKeyBytes);
0357: file
0358: .write(new byte[keyLength
0359: - currentKeyBytes.length]);
0360: } else {
0361: file.writeDouble(((Double) data).doubleValue());
0362: }
0363: }
0364: }
0365:
0366: /**
0367: * Inner class for the pages
0368: */
0369:
0370: private class Page {
0371: /**
0372: * Page numer, number of valid entries and the last lower pointer
0373: */
0374: int number;
0375:
0376: /**
0377: * Page numer, number of valid entries and the last lower pointer
0378: */
0379: int validEntries;
0380:
0381: /**
0382: * Page numer, number of valid entries and the last lower pointer
0383: */
0384: int lastLower;
0385:
0386: /**
0387: * An array with the key entries;
0388: */
0389: KeyEntry[] entries = new KeyEntry[noOfKeysPerPage + 1];
0390:
0391: /**
0392: * Is this page on the store list?
0393: */
0394: boolean onStoreList;
0395:
0396: /**
0397: * This constructor is only used by newPage(), it creates an empty page
0398: */
0399: Page() {
0400: validEntries = 0;
0401: lastLower = 0;
0402: onStoreList = true;
0403: }
0404:
0405: /**
0406: * This constructor is only used by getPage(), it loads a page from the file
0407: */
0408: Page(int number) throws IOException {
0409: this .number = number;
0410: onStoreList = false;
0411:
0412: // Seek to the page
0413: file.seek(number * 512);
0414: // Read the number of valid entries
0415: file.read(b);
0416: validEntries = ByteUtils.readLEInt(b, 0);
0417:
0418: // Read the key entries
0419: for (int i = 0; i < validEntries; i++) {
0420: int lower, record;
0421:
0422: // Read the lower pointer
0423: file.read(b);
0424: lower = ByteUtils.readLEInt(b, 0);
0425:
0426: // Read the record number
0427: file.read(b);
0428: record = ByteUtils.readLEInt(b, 0);
0429:
0430: // Store the key in the array
0431: entries[i] = new KeyEntry(lower, record);
0432:
0433: // Skip some unused bytes
0434: file.skipBytes(sizeOfKeyRecord - (keyLength + 8));
0435: }
0436: // Read the last lower pointer
0437: file.read(b);
0438: lastLower = ByteUtils.readLEInt(b, 0);
0439: }
0440:
0441: /**
0442: * Write the page to disk
0443: */
0444: void write() throws IOException {
0445: file.seek(number * 512);
0446: // Write the number of valid entries
0447: ByteUtils.writeLEInt(b, 0, validEntries);
0448: file.write(b);
0449:
0450: // Write all the key entries
0451: for (int i = 0; i < validEntries; i++) {
0452: // Write the lower pointer
0453: ByteUtils.writeLEInt(b, 0, entries[i].lower);
0454: file.write(b);
0455:
0456: // Write the the recordnumber
0457: ByteUtils.writeLEInt(b, 0, entries[i].record);
0458: file.write(b);
0459:
0460: // Write the key
0461: entries[i].write();
0462:
0463: for (int j = 0; j < keyLength - keyBytes.length; j++)
0464: file.write(0x20);
0465:
0466: file.skipBytes(sizeOfKeyRecord - (keyLength + 8));
0467: }
0468: // Write the last lower pointer
0469: ByteUtils.writeLEInt(b, 0, lastLower);
0470: file.write(b);
0471:
0472: long size = ((number + 1) * 512) - file.getFilePointer();
0473: file.write(new byte[(int) size]);
0474: }
0475:
0476: /**
0477: * This method is called if saving is needed
0478: */
0479: void store() {
0480: onStoreList = true;
0481: }
0482:
0483: /**
0484: * Search in this page (and lower pages)
0485: */
0486: int search(Comparable key, Stack<Integer> searchStack)
0487: throws IOException {
0488: if (validEntries == 0) // Page is empty
0489: {
0490: return -number;
0491: }
0492:
0493: if (entries[0].lower == 0) // This page is a leaf
0494: {
0495: for (int i = 0; i < validEntries; i++) {
0496: if (entries[i].compareTo(key) == 0)
0497:
0498: return entries[i].record;
0499: }
0500:
0501: return -number;
0502: }
0503:
0504: for (int i = 0; i < validEntries; i++) {
0505: int compare = entries[i].compareTo(key);
0506:
0507: if (compare == 0 || compare > 0) {
0508: Page lowerPage = getPage(entries[i].lower);
0509: if (searchStack != null)
0510: searchStack.push(new Integer(number));
0511: return lowerPage.search(key, searchStack);
0512: }
0513: }
0514:
0515: Page lowerPage = getPage(lastLower);
0516: if (searchStack != null)
0517: searchStack.push(new Integer(number));
0518: return lowerPage.search(key, searchStack);
0519:
0520: }
0521:
0522: /**
0523: * Search in this page (and lower pages), duplicates allowed
0524: */
0525: ArrayList<Integer> searchDup(Comparable key) throws IOException {
0526: ArrayList<Integer> found = new ArrayList<Integer>(100);
0527:
0528: if (validEntries != 0) // Page is not emtpy
0529: {
0530: if (entries[0].lower == 0) // Page is a leaf
0531: {
0532: for (int i = 0; i < validEntries; i++) {
0533: if (entries[i].compareTo(key) == 0) {
0534: found.add(new Integer(entries[i].record));
0535: }
0536: }
0537: } else {
0538: for (int i = 0; i < validEntries; i++) {
0539: if (entries[i].compareTo(key) >= 0) {
0540: ArrayList<Integer> lowerFound = getPage(
0541: entries[i].lower).searchDup(key);
0542: if (lowerFound.size() != 0)
0543: found.addAll(lowerFound);
0544: else
0545: return found;
0546: }
0547: }
0548:
0549: found.addAll(getPage(lastLower).searchDup(key));
0550: }
0551: }
0552:
0553: return found;
0554: }
0555:
0556: /**
0557: * Find the insert position for a key
0558: */
0559: int searchDupPos(Comparable key, Stack<Integer> searchStack)
0560: throws IOException {
0561: if (validEntries == 0) // Page is empty
0562: return number;
0563:
0564: if (entries[0].lower == 0) // Page is a leaf
0565: return number;
0566:
0567: for (int i = 0; i < validEntries; i++) {
0568: if (entries[i].compareTo(key) >= 0) {
0569: Page lowerPage = getPage(entries[i].lower);
0570: searchStack.push(new Integer(number));
0571: return lowerPage.searchDupPos(key, searchStack);
0572: }
0573: }
0574:
0575: Page lowerPage = getPage(lastLower);
0576: searchStack.push(new Integer(number));
0577: return lowerPage.searchDupPos(key, searchStack);
0578: }
0579:
0580: /**
0581: * Add a node to this page, this method is only called if page is non-leaf page
0582: */
0583: void addNode(Comparable key, int left, int right,
0584: Stack searchStack) throws IOException {
0585: for (int i = 0; i < validEntries + 1; i++) {
0586: if (i == validEntries) {
0587: entries[i] = new KeyEntry(left, 0, key);
0588: lastLower = right;
0589: break;
0590: }
0591:
0592: if (left == entries[i].lower) {
0593: for (int j = validEntries - 1; j >= i; j--) {
0594: entries[j + 1] = entries[j];
0595: }
0596: entries[i] = new KeyEntry(left, 0, key);
0597: entries[i + 1].lower = right;
0598: break;
0599: }
0600: }
0601:
0602: validEntries++;
0603:
0604: if (validEntries > noOfKeysPerPage) // Split
0605: {
0606: Page newPage = newPage();
0607:
0608: int firstEntry = validEntries / 2;
0609:
0610: KeyEntry parentKey = entries[firstEntry];
0611: firstEntry++;
0612:
0613: int j = 0;
0614: for (int i = firstEntry; i < validEntries; i++) {
0615: newPage.entries[j] = entries[i];
0616: j++;
0617: }
0618:
0619: newPage.validEntries = j;
0620: validEntries -= newPage.validEntries + 1;
0621:
0622: newPage.lastLower = lastLower;
0623: lastLower = parentKey.lower;
0624:
0625: Page parent;
0626: if (searchStack.size() == 0) {
0627: parent = newPage();
0628: setRoot(parent);
0629: } else
0630: parent = getPage(((Integer) searchStack.pop())
0631: .intValue());
0632:
0633: parent.addNode(parentKey.data, number, newPage.number,
0634: searchStack);
0635: }
0636: store();
0637: }
0638:
0639: /**
0640: * Add a key to this page, only for leaf nodes
0641: */
0642: void addKey(Comparable key, int record, Stack searchStack)
0643: throws IOException {
0644: for (int i = 0; i < validEntries + 1; i++) {
0645: if (i == validEntries) {
0646: entries[validEntries] = new KeyEntry(0, record, key);
0647: break;
0648: }
0649:
0650: if (entries[i].compareTo(key) >= 0) {
0651: for (int j = validEntries - 1; j >= i; j--) {
0652: entries[j + 1] = entries[j];
0653: }
0654: entries[i] = new KeyEntry(0, record, key);
0655: break;
0656: }
0657: }
0658:
0659: validEntries++;
0660:
0661: if (validEntries == noOfKeysPerPage) // Split
0662: {
0663: Page newPage = newPage();
0664:
0665: int firstEntry = validEntries / 2 + 1;
0666: if ((validEntries % 2) != 0)
0667: firstEntry++;
0668:
0669: int j = 0;
0670: for (int i = firstEntry; i < validEntries; i++) {
0671: newPage.entries[j] = entries[i];
0672: j++;
0673: }
0674:
0675: newPage.validEntries = validEntries - firstEntry;
0676: validEntries -= newPage.validEntries;
0677:
0678: Page parent;
0679: if (searchStack.size() == 0) {
0680: parent = newPage();
0681: setRoot(parent);
0682: } else
0683: parent = getPage(((Integer) searchStack.pop())
0684: .intValue());
0685: parent.addNode(entries[validEntries - 1].data, number,
0686: newPage.number, searchStack);
0687: }
0688:
0689: store();
0690: }
0691:
0692: /**
0693: * Calculate the depth for this page
0694: */
0695: int getDepth() throws IOException {
0696: if (validEntries == 0) {
0697: throw new IOException("valid entries must be > 0");
0698: }
0699:
0700: if (entries[0].lower == 0) {
0701: return 1;
0702: }
0703: Page lowerPage = getPage(entries[0].lower);
0704: return lowerPage.getDepth() + 1;
0705:
0706: }
0707:
0708: /**
0709: * Convert the page to a string (for debugging)
0710: */
0711: public String toString() {
0712: String s = "Number: " + number + "\nValidEntries: "
0713: + validEntries + "\n";
0714:
0715: for (int i = 0; i < validEntries; i++) {
0716: s += "entry: " + i + "\n";
0717:
0718: KeyEntry key = entries[i];
0719: s += " lower: " + key.lower + "\n";
0720: s += " record: " + key.record + "\n";
0721: s += " data: " + key.data + "\n";
0722: }
0723: s += "lower: " + lastLower;
0724: return s;
0725: }
0726: }
0727:
0728: /**
0729: * Open an existing .ndx file
0730: */
0731: public DBaseIndex(String name) throws IOException {
0732: File f = new File(name + ".ndx");
0733:
0734: if (!f.exists())
0735: throw new FileNotFoundException();
0736:
0737: fileName = name;
0738: file = new RandomAccessFile(f, "rw");
0739:
0740: file.read(b);
0741: startingPageNo = ByteUtils.readLEInt(b, 0);
0742:
0743: file.read(b);
0744: numberOfPages = ByteUtils.readLEInt(b, 0);
0745:
0746: file.skipBytes(4); // Reserved
0747: file.read(b, 0, 2);
0748: keyLength = ByteUtils.readLEShort(b, 0);
0749:
0750: file.read(b, 0, 2);
0751: noOfKeysPerPage = ByteUtils.readLEShort(b, 0);
0752:
0753: file.read(b, 0, 2);
0754: keyType = ByteUtils.readLEShort(b, 0);
0755:
0756: file.read(b);
0757: sizeOfKeyRecord = ByteUtils.readLEInt(b, 0);
0758:
0759: file.skipBytes(1); // Reserved
0760: uniqueFlag = file.readBoolean();
0761:
0762: keyBytes = new byte[keyLength];
0763: }
0764:
0765: /**
0766: * Used by createIndex()
0767: */
0768: private DBaseIndex(String name, int startingPageNo,
0769: int numberOfPages, int sizeOfKeyRecord, int keyLength,
0770: int noOfKeysPerPage, int keyType, boolean uniqueFlag,
0771: RandomAccessFile file) {
0772: fileName = name;
0773: this .startingPageNo = startingPageNo;
0774: this .numberOfPages = numberOfPages;
0775: this .sizeOfKeyRecord = sizeOfKeyRecord;
0776: this .keyLength = keyLength;
0777: this .noOfKeysPerPage = noOfKeysPerPage;
0778: this .keyType = keyType;
0779: this .uniqueFlag = uniqueFlag;
0780: this .file = file;
0781:
0782: keyBytes = new byte[keyLength];
0783: }
0784:
0785: /**
0786: * Get a page
0787: */
0788: protected Page getPage(int number) throws IOException {
0789: Page p;
0790:
0791: synchronized (cache) {
0792: p = cache.get(number);
0793:
0794: if (p == null) {
0795: p = new Page(number);
0796: cache.insert(number, p);
0797: }
0798: }
0799:
0800: if (p.validEntries != 0) {
0801: if (p.entries[0].lower != 0) {
0802: Hashtable<Integer, String> test = new Hashtable<Integer, String>();
0803: for (int i = 0; i < p.validEntries; i++) {
0804: test.put(new Integer(p.entries[i].lower), "");
0805: }
0806: test.put(new Integer(p.lastLower), "");
0807: if (test.size() != p.validEntries + 1) {
0808: throw new IOException("Error in page " + p.number);
0809: }
0810: }
0811: }
0812:
0813: return p;
0814: }
0815:
0816: /**
0817: * Create a new page
0818: */
0819: protected Page newPage() throws IOException {
0820: Page p;
0821:
0822: synchronized (cache) {
0823: numberOfPages++;
0824:
0825: p = new Page();
0826: p.number = numberOfPages;
0827:
0828: cache.insert(p.number, p);
0829: p.write();
0830: }
0831: return p;
0832: }
0833:
0834: /**
0835: * Set the root page
0836: */
0837: protected synchronized void setRoot(Page page) {
0838: startingPageNo = page.number;
0839: }
0840:
0841: /**
0842: * Create a new index
0843: */
0844: public static DBaseIndex createIndex(String name, String column,
0845: int keyLength, boolean uniqueFlag, boolean numbers)
0846: throws IOException {
0847: RandomAccessFile file = new RandomAccessFile(name + ".ndx",
0848: "rw");
0849:
0850: int startingPageNo = 1, numberOfPages = 1, sizeOfKeyRecord, noOfKeysPerPage, keyType = numbers ? 1
0851: : 0;
0852:
0853: if (numbers)
0854: keyLength = 8;
0855:
0856: sizeOfKeyRecord = 8 + keyLength;
0857:
0858: while ((sizeOfKeyRecord % 4) != 0)
0859: sizeOfKeyRecord++;
0860:
0861: noOfKeysPerPage = 504 / sizeOfKeyRecord;
0862:
0863: byte[] b = new byte[4];
0864:
0865: ByteUtils.writeLEInt(b, 0, startingPageNo);
0866: file.write(b);
0867:
0868: ByteUtils.writeLEInt(b, 0, numberOfPages);
0869: file.write(b);
0870:
0871: file.writeInt(0); // Reserved
0872:
0873: ByteUtils.writeLEShort(b, 0, keyLength);
0874: file.write(b, 0, 2);
0875:
0876: ByteUtils.writeLEShort(b, 0, noOfKeysPerPage);
0877: file.write(b, 0, 2);
0878:
0879: ByteUtils.writeLEShort(b, 0, keyType);
0880: file.write(b, 0, 2);
0881:
0882: ByteUtils.writeLEInt(b, 0, sizeOfKeyRecord);
0883: file.write(b);
0884:
0885: file.write(0); // Reserved
0886:
0887: file.writeBoolean(uniqueFlag);
0888:
0889: file.write(column.getBytes());
0890:
0891: for (int i = 0; i < 180 - column.length(); i++)
0892: file.write(0x20);
0893:
0894: for (int i = 0; i < 820; i++)
0895: file.write(0);
0896:
0897: return new DBaseIndex(name, startingPageNo, numberOfPages,
0898: sizeOfKeyRecord, keyLength, noOfKeysPerPage, keyType,
0899: uniqueFlag, file);
0900: }
0901:
0902: /**
0903: * Flush all the buffers
0904: */
0905: public void flush() throws IOException {
0906: file.seek(0);
0907: ByteUtils.writeLEInt(b, 0, startingPageNo);
0908: file.write(b);
0909:
0910: ByteUtils.writeLEInt(b, 0, numberOfPages);
0911: file.write(b);
0912:
0913: cache.flush();
0914: }
0915:
0916: /**
0917: * Close the index file
0918: */
0919: public void close() throws IOException {
0920: flush();
0921: file.close();
0922: }
0923:
0924: public int[] search(Comparable key) throws IOException,
0925: KeyNotFoundException, InvalidKeyTypeException {
0926: if (key == null)
0927: throw new NullPointerException();
0928:
0929: if ((keyType == 0 && !(key instanceof String))
0930: || (keyType == 1 && !(key instanceof Number))) {
0931: throw new InvalidKeyTypeException(key, this );
0932: }
0933:
0934: if (keyType == 1 && !(key instanceof Double)) {
0935: key = new Double(((Number) key).doubleValue());
0936: }
0937:
0938: Page root = getPage(startingPageNo);
0939:
0940: if (uniqueFlag) {
0941: int[] retval = new int[1];
0942: retval[0] = root.search(key, null);
0943: if (retval[0] < 0) {
0944: throw new KeyNotFoundException(key, this );
0945: }
0946: return retval;
0947: }
0948: ArrayList searchResult = root.searchDup(key);
0949: if (searchResult.size() == 0) {
0950: throw new KeyNotFoundException(key, this );
0951: }
0952: int[] retval = new int[searchResult.size()];
0953: for (int i = 0; i < retval.length; i++)
0954: retval[i] = ((Integer) searchResult.get(i)).intValue();
0955: return retval;
0956:
0957: }
0958:
0959: /**
0960: * Add a key to the index
0961: */
0962: public void addKey(Comparable key, int record) throws IOException,
0963: KeyAlreadyExistException, InvalidKeyTypeException,
0964: KeyTooLongException {
0965: if (key == null)
0966: throw new NullPointerException();
0967:
0968: if ((keyType == 0 && !(key instanceof String))
0969: || (keyType == 1 && !(key instanceof Number))) {
0970: throw new InvalidKeyTypeException(key, this );
0971: }
0972:
0973: if (keyType == 1 && !(key instanceof Double)) {
0974: key = new Double(((Number) key).doubleValue());
0975: }
0976:
0977: if (key instanceof String) {
0978: if (((String) key).length() > keyLength) {
0979: throw new KeyTooLongException(key, this );
0980: }
0981: }
0982:
0983: Page root = getPage(startingPageNo);
0984: Stack<Integer> stack = new Stack<Integer>();
0985:
0986: if (uniqueFlag) {
0987: int searchResult = root.search(key, stack);
0988: if (searchResult >= 0) {
0989: throw new KeyAlreadyExistException(key, this );
0990: }
0991:
0992: getPage(-searchResult).addKey(key, record, stack);
0993: } else {
0994: int searchResult = root.searchDupPos(key, stack);
0995: getPage(searchResult).addKey(key, record, stack);
0996: }
0997: }
0998:
0999: /**
1000: * Calculate the depth for the index
1001: */
1002: public int getDepth() throws IOException {
1003: Page root = getPage(startingPageNo);
1004: return root.getDepth();
1005: }
1006:
1007: /**
1008: * Contains this index unique values?
1009: */
1010: public boolean isUnique() {
1011: return uniqueFlag;
1012: }
1013:
1014: public String toString() {
1015: return fileName;
1016: }
1017: }
|