    001    //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/branches/2.4_testing/src/org/deegree/io/dbaseapi/DBaseIndex.java $
    002    /*----------------------------------------------------------------------------
    003     This file is part of deegree, http://deegree.org/
    004     Copyright (C) 2001-2009 by:
    005       Department of Geography, University of Bonn
    006     and
    007       lat/lon GmbH
    008
    009     This library is free software; you can redistribute it and/or modify it under
    010     the terms of the GNU Lesser General Public License as published by the Free
    011     Software Foundation; either version 2.1 of the License, or (at your option)
    012     any later version.
    013     This library is distributed in the hope that it will be useful, but WITHOUT
    014     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
    015     FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
    016     details.
    017     You should have received a copy of the GNU Lesser General Public License
    018     along with this library; if not, write to the Free Software Foundation, Inc.,
    019     59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
    020
    021     Contact information:
    022
    023     lat/lon GmbH
    024     Aennchenstr. 19, 53177 Bonn
    025     Germany
    026     http://lat-lon.de/
    027
    028     Department of Geography, University of Bonn
    029     Prof. Dr. Klaus Greve
    030     Postfach 1147, 53001 Bonn
    031     Germany
    032     http://www.geographie.uni-bonn.de/deegree/
    033
    034     e-mail: info@deegree.org
    035    ----------------------------------------------------------------------------*/
    036
    037    package org.deegree.io.dbaseapi;
    038
    039    import java.io.File;
    040    import java.io.FileNotFoundException;
    041    import java.io.IOException;
    042    import java.io.RandomAccessFile;
    043    import java.util.ArrayList;
    044    import java.util.Hashtable;
    045    import java.util.LinkedList;
    046    import java.util.ListIterator;
    047    import java.util.Stack;
    048
    049    import org.deegree.model.spatialschema.ByteUtils;
    050
    051    /**
    052     * <p>
    053     * A class for reading from and writing to DBase index files (*.ndx), maybe not 100% xbase
    054     * compatible!
    055     * </p>
    056     *
    057     * <p>
    058     * The fileformat is described at http://www.e-bachmann.dk/computing/databases/xbase/index.html
    059     * </p>
    060     *
    061     * <p>
    062     * This index is suitable for indexing both unique and non-unique columns. Unique indexing is much
    063     * faster than non-unique because it use a faster algorithm.
    064     * </p>
    065     *
    066     * <p>
    067     * The index file is a B+tree (sometimes called a paged B-tree) that consist of pages. There are two
    068     * page types, leaves and non-leafs. The starting page (eg. the page the search algorithm starts) is
    069     * the root page.
    070     * </p>
    071     *
    072     * <p>
    073     * <b>Searching goes as follows:</b>
    074     * <ul>
    075     * <li>load the root page (eg. the starting page)</li>
    076     * <li>if the page is a leaf
    077     * <ul>
    078     * <li>search for the requested key</li>
    079     * </ul>
    080     * </li>
    081     * <li>if the page is not a leaf (eg. the page has subpages)
    082     * <ul>
    083     * <li>search for a key that is equal to or bigger than the requested key</li>
    084     * <li>load the lower page</li>
    085     * <li>continue searching inside the lower page</li>
    086     * </ul>
    087     * </li>
    088     * </ul>
    089     * </p>
    090     *
    091     * <p>
    092     * Above algorithm is implemented in two different methods, one for unique indexes and one for
    093     * non-unique indexes. Searching unique indexes is easier because the algorithm is finished as soon
    094     * as it has found a key, the non-unique version of the algorithm has to find all keys present in
    095     * the index.
    096     * <p>
    097     *
    098     * <p>
    099     * <b>Inserting goes as follows:</b>
    100     * <ul>
    101     * <li>find the leaf page the key has to insert in</li>
    102     * <li>insert the key in the leaf page</li>
    103     * <li>if the leaf page is full (eg. validEntries > noOfKeysPerPage)
    104     * <ul>
    105     * <li>split the leaf page (results in two leaf pages)</li>
    106     * <li>add the first item of the new page to the parent page</li>
    107     * </ul>
    108     * </li>
    109     * <li>if the parent page is also full
    110     * <ul>
    111     * <li>split the parent page
    112     * <li>
    113     * <li>add the first item of the new page to it's parent page</li>
    114     * <li>etc.</li>
    115     * </ul>
    116     * </li>
    117     * </ul>
    118     * </p>
    119     *
    120     * <p>
    121     * If a page that splits does not have a parent page then a new page is created. This page is the
    122     * new starting page
    123     * </p>
    124     *
    125     * <p>
    126     * Handling different data types: The index can handle strings and numbers. Numbers are always
    127     * stored als IEEE doubles. The method addKey checks the given key and throws an exception if the
    128     * datatype of the key doesn't suit the index
    129     * </p>
    130     *
    131     * @author Reijer Copier, email: reijer.copier@idgis.nl
    132     */
    133
    134    public class DBaseIndex {
    135        // The filename we use (this variable is used by toString)
    136        private String fileName;
    137
    138        // The random access file we use
    139        protected RandomAccessFile file;
    140
    141        // Attributes stored in the .ndx header
    142        protected int startingPageNo;
    143
    144        // Attributes stored in the .ndx header
    145        protected int numberOfPages;
    146
    147        // Attributes stored in the .ndx header
    148        protected int sizeOfKeyRecord;
    149
    150        // Attributes stored in the .ndx header
    151        protected int keyLength;
    152
    153        // Attributes stored in the .ndx header
    154        protected int noOfKeysPerPage;
    155
    156        // Attributes stored in the .ndx header
    157        protected int keyType;
    158
    159        private boolean uniqueFlag;
    160
    161        // Buffers
    162        protected byte[] b = new byte[4];
    163
    164        // Buffers
    165        protected byte[] page = new byte[512];
    166
    167        // Buffers
    168        protected byte[] keyBytes;
    169
    170        // Cache size
    171        protected int cacheSize = 20;
    172
    173        // Cache
    174        private Cache cache = new Cache();
    175
    176        /**
    177         * Inner class for the cache. The cache remembers recently used pages.
    178         */
    179        public class Cache {
    180
    181            /**
    182             * Inner class for the cache items
    183             */
    184
    185            class Item implements Comparable {
    186                /**
    187                 * Create a new item with the given page
    188                 */
    189                Item( Page p ) {
    190                    this.p = p;
    191                    timeStamp = System.currentTimeMillis();
    192                }
    193
    194                /**
    195                 * Mark the item as used (eg. create a new time stamp)
    196                 */
    197                void use() {
    198                    timeStamp = System.currentTimeMillis();
    199                }
    200
    201                long timeStamp;
    202
    203                Page p;
    204
    205                /**
    206                 * Compare the time stamp from this object to the time stamp of another object
    207                 */
    208                public int compareTo( Object o ) {
    209                    return new Long( timeStamp ).compareTo( new Long( ( (Item) o ).timeStamp ) );
    210                }
    211            }
    212
    213            private Hashtable<Integer, Item> pages;
    214
    215            private LinkedList<Item> cacheItems;
    216
    217            /**
    218             * Create a new cache
    219             */
    220            public Cache() {
    221                pages = new Hashtable<Integer, Item>();
    222                cacheItems = new LinkedList<Item>();
    223            }
    224
    225            /**
    226             * Remove an item from the cache (this method searches for the last used item)
    227             */
    228            void removeItem()
    229                                    throws IOException {
    230                Item i = cacheItems.removeFirst();
    231
    232                if ( i.p.onStoreList )
    233                    i.p.write();
    234
    235                pages.remove( new Integer( i.p.number ) );
    236            }
    237
    238            /**
    239             * Insert a new item into the cache
    240             */
    241            public void insert( int number, Page p )
    242                                    throws IOException {
    243                Item i = new Item( p );
    244
    245                pages.put( new Integer( number ), i );
    246                cacheItems.addLast( i );
    247
    248                if ( cacheItems.size() > cacheSize )
    249                    removeItem();
    250            }
    251
    252            /**
    253             * Get a page form the cache
    254             *
    255             * @return returns the addressed page or <code>null</code>
    256             */
    257            public Page get( int number ) {
    258                Item item = pages.get( new Integer( number ) );
    259
    260                if ( item != null ) {
    261                    cacheItems.remove( item );
    262                    item.use();
    263                    cacheItems.addLast( item );
    264
    265                    return item.p;
    266                }
    267                return null;
    268            }
    269
    270            /**
    271             * Flush the cache (eg. store modified pages)
    272             */
    273            public void flush() {
    274                ListIterator i = cacheItems.listIterator();
    275
    276                while ( i.hasNext() ) {
    277                    Item item = (Item) i.next();
    278
    279                    try {
    280                        if ( item.p.onStoreList ) {
    281                            item.p.write();
    282                        }
    283                    } catch ( IOException e ) {
    284                        e.printStackTrace();
    285                    }
    286                }
    287
    288                cacheItems.clear();
    289                pages.clear();
    290            }
    291        }
    292
    293        /**
    294         * Inner class for the key entries
    295         */
    296        private class KeyEntry {
    297            // Lower pointer and record number
    298            int lower;
    299
    300            // Lower pointer and record number
    301            int record;
    302
    303            // Data
    304            Comparable data;
    305
    306            /**
    307             * Construct a new KeyEntry
    308             */
    309            KeyEntry( int lower, int record, Comparable data ) {
    310                this.lower = lower;
    311                this.record = record;
    312                this.data = data;
    313            }
    314
    315            /**
    316             * Read an existing KeyEntry
    317             */
    318            KeyEntry( int lower, int record ) throws IOException {
    319                this.lower = lower;
    320                this.record = record;
    321                read();
    322            }
    323
    324            /**
    325             * Compare this key entry to another key
    326             */
    327            int compareTo( Comparable key ) {
    328                return this.data.compareTo( key );
    329            }
    330
    331            /**
    332             * Read data from current file position
    333             */
    334            void read()
    335                                    throws IOException {
    336                if ( keyType == 0 ) {
    337                    file.read( keyBytes );
    338                    data = new String( keyBytes ).trim();
    339                } else {
    340                    data = new Double( file.readDouble() );
    341                }
    342            }
    343
    344            /**
    345             * Write data to current file position
    346             */
    347            void write()
    348                                    throws IOException {
    349                if ( keyType == 0 ) {
    350                    byte[] currentKeyBytes = ( (String) data ).getBytes();
    351                    file.write( currentKeyBytes );
    352                    file.write( new byte[keyLength - currentKeyBytes.length] );
    353                } else {
    354                    file.writeDouble( ( (Double) data ).doubleValue() );
    355                }
    356            }
    357        }
    358
    359        /**
    360         * Inner class for the pages
    361         */
    362
    363        private class Page {
    364            /**
    365             * Page numer, number of valid entries and the last lower pointer
    366             */
    367            int number;
    368
    369            /**
    370             * Page numer, number of valid entries and the last lower pointer
    371             */
    372            int validEntries;
    373
    374            /**
    375             * Page numer, number of valid entries and the last lower pointer
    376             */
    377            int lastLower;
    378
    379            /**
    380             * An array with the key entries;
    381             */
    382            KeyEntry[] entries = new KeyEntry[noOfKeysPerPage + 1];
    383
    384            /**
    385             * Is this page on the store list?
    386             */
    387            boolean onStoreList;
    388
    389            /**
    390             * This constructor is only used by newPage(), it creates an empty page
    391             */
    392            Page() {
    393                validEntries = 0;
    394                lastLower = 0;
    395                onStoreList = true;
    396            }
    397
    398            /**
    399             * This constructor is only used by getPage(), it loads a page from the file
    400             */
    401            Page( int number ) throws IOException {
    402                this.number = number;
    403                onStoreList = false;
    404
    405                // Seek to the page
    406                file.seek( number * 512 );
    407                // Read the number of valid entries
    408                file.read( b );
    409                validEntries = ByteUtils.readLEInt( b, 0 );
    410
    411                // Read the key entries
    412                for ( int i = 0; i < validEntries; i++ ) {
    413                    int lower, record;
    414
    415                    // Read the lower pointer
    416                    file.read( b );
    417                    lower = ByteUtils.readLEInt( b, 0 );
    418
    419                    // Read the record number
    420                    file.read( b );
    421                    record = ByteUtils.readLEInt( b, 0 );
    422
    423                    // Store the key in the array
    424                    entries[i] = new KeyEntry( lower, record );
    425
    426                    // Skip some unused bytes
    427                    file.skipBytes( sizeOfKeyRecord - ( keyLength + 8 ) );
    428                }
    429                // Read the last lower pointer
    430                file.read( b );
    431                lastLower = ByteUtils.readLEInt( b, 0 );
    432            }
    433
    434            /**
    435             * Write the page to disk
    436             */
    437            void write()
    438                                    throws IOException {
    439                file.seek( number * 512 );
    440                // Write the number of valid entries
    441                ByteUtils.writeLEInt( b, 0, validEntries );
    442                file.write( b );
    443
    444                // Write all the key entries
    445                for ( int i = 0; i < validEntries; i++ ) {
    446                    // Write the lower pointer
    447                    ByteUtils.writeLEInt( b, 0, entries[i].lower );
    448                    file.write( b );
    449
    450                    // Write the the recordnumber
    451                    ByteUtils.writeLEInt( b, 0, entries[i].record );
    452                    file.write( b );
    453
    454                    // Write the key
    455                    entries[i].write();
    456
    457                    for ( int j = 0; j < keyLength - keyBytes.length; j++ )
    458                        file.write( 0x20 );
    459
    460                    file.skipBytes( sizeOfKeyRecord - ( keyLength + 8 ) );
    461                }
    462                // Write the last lower pointer
    463                ByteUtils.writeLEInt( b, 0, lastLower );
    464                file.write( b );
    465
    466                long size = ( ( number + 1 ) * 512 ) - file.getFilePointer();
    467                file.write( new byte[(int) size] );
    468            }
    469
    470            /**
    471             * This method is called if saving is needed
    472             */
    473            void store() {
    474                onStoreList = true;
    475            }
    476
    477            /**
    478             * Search in this page (and lower pages)
    479             */
    480            int search( Comparable key, Stack<Integer> searchStack )
    481                                    throws IOException {
    482                if ( validEntries == 0 ) // Page is empty
    483                {
    484                    return -number;
    485                }
    486
    487                if ( entries[0].lower == 0 ) // This page is a leaf
    488                {
    489                    for ( int i = 0; i < validEntries; i++ ) {
    490                        if ( entries[i].compareTo( key ) == 0 )
    491
    492                            return entries[i].record;
    493                    }
    494
    495                    return -number;
    496                }
    497
    498                for ( int i = 0; i < validEntries; i++ ) {
    499                    int compare = entries[i].compareTo( key );
    500
    501                    if ( compare == 0 || compare > 0 ) {
    502                        Page lowerPage = getPage( entries[i].lower );
    503                        if ( searchStack != null )
    504                            searchStack.push( new Integer( number ) );
    505                        return lowerPage.search( key, searchStack );
    506                    }
    507                }
    508
    509                Page lowerPage = getPage( lastLower );
    510                if ( searchStack != null )
    511                    searchStack.push( new Integer( number ) );
    512                return lowerPage.search( key, searchStack );
    513
    514            }
    515
    516            /**
    517             * Search in this page (and lower pages), duplicates allowed
    518             */
    519            ArrayList<Integer> searchDup( Comparable key )
    520                                    throws IOException {
    521                ArrayList<Integer> found = new ArrayList<Integer>( 100 );
    522
    523                if ( validEntries != 0 ) // Page is not emtpy
    524                {
    525                    if ( entries[0].lower == 0 ) // Page is a leaf
    526                    {
    527                        for ( int i = 0; i < validEntries; i++ ) {
    528                            if ( entries[i].compareTo( key ) == 0 ) {
    529                                found.add( new Integer( entries[i].record ) );
    530                            }
    531                        }
    532                    } else {
    533                        for ( int i = 0; i < validEntries; i++ ) {
    534                            if ( entries[i].compareTo( key ) >= 0 ) {
    535                                ArrayList<Integer> lowerFound = getPage( entries[i].lower ).searchDup( key );
    536                                if ( lowerFound.size() != 0 )
    537                                    found.addAll( lowerFound );
    538                                else
    539                                    return found;
    540                            }
    541                        }
    542
    543                        found.addAll( getPage( lastLower ).searchDup( key ) );
    544                    }
    545                }
    546
    547                return found;
    548            }
    549
    550            /**
    551             * Find the insert position for a key
    552             */
    553            int searchDupPos( Comparable key, Stack<Integer> searchStack )
    554                                    throws IOException {
    555                if ( validEntries == 0 ) // Page is empty
    556                    return number;
    557
    558                if ( entries[0].lower == 0 ) // Page is a leaf
    559                    return number;
    560
    561                for ( int i = 0; i < validEntries; i++ ) {
    562                    if ( entries[i].compareTo( key ) >= 0 ) {
    563                        Page lowerPage = getPage( entries[i].lower );
    564                        searchStack.push( new Integer( number ) );
    565                        return lowerPage.searchDupPos( key, searchStack );
    566                    }
    567                }
    568
    569                Page lowerPage = getPage( lastLower );
    570                searchStack.push( new Integer( number ) );
    571                return lowerPage.searchDupPos( key, searchStack );
    572            }
    573
    574            /**
    575             * Add a node to this page, this method is only called if page is non-leaf page
    576             */
    577            void addNode( Comparable key, int left, int right, Stack searchStack )
    578                                    throws IOException {
    579                for ( int i = 0; i < validEntries + 1; i++ ) {
    580                    if ( i == validEntries ) {
    581                        entries[i] = new KeyEntry( left, 0, key );
    582                        lastLower = right;
    583                        break;
    584                    }
    585
    586                    if ( left == entries[i].lower ) {
    587                        for ( int j = validEntries - 1; j >= i; j-- ) {
    588                            entries[j + 1] = entries[j];
    589                        }
    590                        entries[i] = new KeyEntry( left, 0, key );
    591                        entries[i + 1].lower = right;
    592                        break;
    593                    }
    594                }
    595
    596                validEntries++;
    597
    598                if ( validEntries > noOfKeysPerPage ) // Split
    599                {
    600                    Page newPage = newPage();
    601
    602                    int firstEntry = validEntries / 2;
    603
    604                    KeyEntry parentKey = entries[firstEntry];
    605                    firstEntry++;
    606
    607                    int j = 0;
    608                    for ( int i = firstEntry; i < validEntries; i++ ) {
    609                        newPage.entries[j] = entries[i];
    610                        j++;
    611                    }
    612
    613                    newPage.validEntries = j;
    614                    validEntries -= newPage.validEntries + 1;
    615
    616                    newPage.lastLower = lastLower;
    617                    lastLower = parentKey.lower;
    618
    619                    Page parent;
    620                    if ( searchStack.size() == 0 ) {
    621                        parent = newPage();
    622                        setRoot( parent );
    623                    } else
    624                        parent = getPage( ( (Integer) searchStack.pop() ).intValue() );
    625
    626                    parent.addNode( parentKey.data, number, newPage.number, searchStack );
    627                }
    628                store();
    629            }
    630
    631            /**
    632             * Add a key to this page, only for leaf nodes
    633             */
    634            void addKey( Comparable key, int record, Stack searchStack )
    635                                    throws IOException {
    636                for ( int i = 0; i < validEntries + 1; i++ ) {
    637                    if ( i == validEntries ) {
    638                        entries[validEntries] = new KeyEntry( 0, record, key );
    639                        break;
    640                    }
    641
    642                    if ( entries[i].compareTo( key ) >= 0 ) {
    643                        for ( int j = validEntries - 1; j >= i; j-- ) {
    644                            entries[j + 1] = entries[j];
    645                        }
    646                        entries[i] = new KeyEntry( 0, record, key );
    647                        break;
    648                    }
    649                }
    650
    651                validEntries++;
    652
    653                if ( validEntries == noOfKeysPerPage ) // Split
    654                {
    655                    Page newPage = newPage();
    656
    657                    int firstEntry = validEntries / 2 + 1;
    658                    if ( ( validEntries % 2 ) != 0 )
    659                        firstEntry++;
    660
    661                    int j = 0;
    662                    for ( int i = firstEntry; i < validEntries; i++ ) {
    663                        newPage.entries[j] = entries[i];
    664                        j++;
    665                    }
    666
    667                    newPage.validEntries = validEntries - firstEntry;
    668                    validEntries -= newPage.validEntries;
    669
    670                    Page parent;
    671                    if ( searchStack.size() == 0 ) {
    672                        parent = newPage();
    673                        setRoot( parent );
    674                    } else
    675                        parent = getPage( ( (Integer) searchStack.pop() ).intValue() );
    676                    parent.addNode( entries[validEntries - 1].data, number, newPage.number, searchStack );
    677                }
    678
    679                store();
    680            }
    681
    682            /**
    683             * Calculate the depth for this page
    684             */
    685            int getDepth()
    686                                    throws IOException {
    687                if ( validEntries == 0 ) {
    688                    throw new IOException( "valid entries must be > 0" );
    689                }
    690
    691                if ( entries[0].lower == 0 ) {
    692                    return 1;
    693                }
    694                Page lowerPage = getPage( entries[0].lower );
    695                return lowerPage.getDepth() + 1;
    696
    697            }
    698
    699            /**
    700             * Convert the page to a string (for debugging)
    701             */
    702            public String toString() {
    703                String s = "Number: " + number + "\nValidEntries: " + validEntries + "\n";
    704
    705                for ( int i = 0; i < validEntries; i++ ) {
    706                    s += "entry: " + i + "\n";
    707
    708                    KeyEntry key = entries[i];
    709                    s += "  lower: " + key.lower + "\n";
    710                    s += "  record: " + key.record + "\n";
    711                    s += "  data: " + key.data + "\n";
    712                }
    713                s += "lower: " + lastLower;
    714                return s;
    715            }
    716        }
    717
    718        /**
    719         * Open an existing .ndx file
    720         */
    721        public DBaseIndex( String name ) throws IOException {
    722            File f = new File( name + ".ndx" );
    723
    724            if ( !f.exists() )
    725                throw new FileNotFoundException();
    726
    727            fileName = name;
    728            file = new RandomAccessFile( f, "rw" );
    729
    730            file.read( b );
    731            startingPageNo = ByteUtils.readLEInt( b, 0 );
    732
    733            file.read( b );
    734            numberOfPages = ByteUtils.readLEInt( b, 0 );
    735
    736            file.skipBytes( 4 ); // Reserved
    737            file.read( b, 0, 2 );
    738            keyLength = ByteUtils.readLEShort( b, 0 );
    739
    740            file.read( b, 0, 2 );
    741            noOfKeysPerPage = ByteUtils.readLEShort( b, 0 );
    742
    743            file.read( b, 0, 2 );
    744            keyType = ByteUtils.readLEShort( b, 0 );
    745
    746            file.read( b );
    747            sizeOfKeyRecord = ByteUtils.readLEInt( b, 0 );
    748
    749            file.skipBytes( 1 ); // Reserved
    750            uniqueFlag = file.readBoolean();
    751
    752            keyBytes = new byte[keyLength];
    753        }
    754
    755        /**
    756         * Used by createIndex()
    757         */
    758        private DBaseIndex( String name, int startingPageNo, int numberOfPages, int sizeOfKeyRecord, int keyLength,
    759                            int noOfKeysPerPage, int keyType, boolean uniqueFlag, RandomAccessFile file ) {
    760            fileName = name;
    761            this.startingPageNo = startingPageNo;
    762            this.numberOfPages = numberOfPages;
    763            this.sizeOfKeyRecord = sizeOfKeyRecord;
    764            this.keyLength = keyLength;
    765            this.noOfKeysPerPage = noOfKeysPerPage;
    766            this.keyType = keyType;
    767            this.uniqueFlag = uniqueFlag;
    768            this.file = file;
    769
    770            keyBytes = new byte[keyLength];
    771        }
    772
    773        /**
    774         * Get a page
    775         */
    776        protected Page getPage( int number )
    777                                throws IOException {
    778            Page p;
    779
    780            synchronized ( cache ) {
    781                p = cache.get( number );
    782
    783                if ( p == null ) {
    784                    p = new Page( number );
    785                    cache.insert( number, p );
    786                }
    787            }
    788
    789            if ( p.validEntries != 0 ) {
    790                if ( p.entries[0].lower != 0 ) {
    791                    Hashtable<Integer, String> test = new Hashtable<Integer, String>();
    792                    for ( int i = 0; i < p.validEntries; i++ ) {
    793                        test.put( new Integer( p.entries[i].lower ), "" );
    794                    }
    795                    test.put( new Integer( p.lastLower ), "" );
    796                    if ( test.size() != p.validEntries + 1 ) {
    797                        throw new IOException( "Error in page " + p.number );
    798                    }
    799                }
    800            }
    801
    802            return p;
    803        }
    804
    805        /**
    806         * Create a new page
    807         */
    808        protected Page newPage()
    809                                throws IOException {
    810            Page p;
    811
    812            synchronized ( cache ) {
    813                numberOfPages++;
    814
    815                p = new Page();
    816                p.number = numberOfPages;
    817
    818                cache.insert( p.number, p );
    819                p.write();
    820            }
    821            return p;
    822        }
    823
    824        /**
    825         * Set the root page
    826         */
    827        protected synchronized void setRoot( Page page ) {
    828            startingPageNo = page.number;
    829        }
    830
    831        /**
    832         * Create a new index
    833         */
    834        public static DBaseIndex createIndex( String name, String column, int keyLength, boolean uniqueFlag, boolean numbers )
    835                                throws IOException {
    836            RandomAccessFile file = new RandomAccessFile( name + ".ndx", "rw" );
    837
    838            int startingPageNo = 1, numberOfPages = 1, sizeOfKeyRecord, noOfKeysPerPage, keyType = numbers ? 1 : 0;
    839
    840            if ( numbers )
    841                keyLength = 8;
    842
    843            sizeOfKeyRecord = 8 + keyLength;
    844
    845            while ( ( sizeOfKeyRecord % 4 ) != 0 )
    846                sizeOfKeyRecord++;
    847
    848            noOfKeysPerPage = 504 / sizeOfKeyRecord;
    849
    850            byte[] b = new byte[4];
    851
    852            ByteUtils.writeLEInt( b, 0, startingPageNo );
    853            file.write( b );
    854
    855            ByteUtils.writeLEInt( b, 0, numberOfPages );
    856            file.write( b );
    857
    858            file.writeInt( 0 ); // Reserved
    859
    860            ByteUtils.writeLEShort( b, 0, keyLength );
    861            file.write( b, 0, 2 );
    862
    863            ByteUtils.writeLEShort( b, 0, noOfKeysPerPage );
    864            file.write( b, 0, 2 );
    865
    866            ByteUtils.writeLEShort( b, 0, keyType );
    867            file.write( b, 0, 2 );
    868
    869            ByteUtils.writeLEInt( b, 0, sizeOfKeyRecord );
    870            file.write( b );
    871
    872            file.write( 0 ); // Reserved
    873
    874            file.writeBoolean( uniqueFlag );
    875
    876            file.write( column.getBytes() );
    877
    878            for ( int i = 0; i < 180 - column.length(); i++ )
    879                file.write( 0x20 );
    880
    881            for ( int i = 0; i < 820; i++ )
    882                file.write( 0 );
    883
    884            return new DBaseIndex( name, startingPageNo, numberOfPages, sizeOfKeyRecord, keyLength, noOfKeysPerPage,
    885                                   keyType, uniqueFlag, file );
    886        }
    887
    888        /**
    889         * Flush all the buffers
    890         */
    891        public void flush()
    892                                throws IOException {
    893            file.seek( 0 );
    894            ByteUtils.writeLEInt( b, 0, startingPageNo );
    895            file.write( b );
    896
    897            ByteUtils.writeLEInt( b, 0, numberOfPages );
    898            file.write( b );
    899
    900            cache.flush();
    901        }
    902
    903        /**
    904         * Close the index file
    905         */
    906        public void close()
    907                                throws IOException {
    908            flush();
    909            file.close();
    910        }
    911
    912        public int[] search( Comparable key )
    913                                throws IOException, KeyNotFoundException, InvalidKeyTypeException {
    914            if ( key == null )
    915                throw new NullPointerException();
    916
    917            if ( ( keyType == 0 && !( key instanceof String ) ) || ( keyType == 1 && !( key instanceof Number ) ) ) {
    918                throw new InvalidKeyTypeException( key, this );
    919            }
    920
    921            if ( keyType == 1 && !( key instanceof Double ) ) {
    922                key = new Double( ( (Number) key ).doubleValue() );
    923            }
    924
    925            Page root = getPage( startingPageNo );
    926
    927            if ( uniqueFlag ) {
    928                int[] retval = new int[1];
    929                retval[0] = root.search( key, null );
    930                if ( retval[0] < 0 ) {
    931                    throw new KeyNotFoundException( key, this );
    932                }
    933                return retval;
    934            }
    935            ArrayList searchResult = root.searchDup( key );
    936            if ( searchResult.size() == 0 ) {
    937                throw new KeyNotFoundException( key, this );
    938            }
    939            int[] retval = new int[searchResult.size()];
    940            for ( int i = 0; i < retval.length; i++ )
    941                retval[i] = ( (Integer) searchResult.get( i ) ).intValue();
    942            return retval;
    943
    944        }
    945
    946        /**
    947         * Add a key to the index
    948         */
    949        public void addKey( Comparable key, int record )
    950                                throws IOException, KeyAlreadyExistException, InvalidKeyTypeException, KeyTooLongException {
    951            if ( key == null )
    952                throw new NullPointerException();
    953
    954            if ( ( keyType == 0 && !( key instanceof String ) ) || ( keyType == 1 && !( key instanceof Number ) ) ) {
    955                throw new InvalidKeyTypeException( key, this );
    956            }
    957
    958            if ( keyType == 1 && !( key instanceof Double ) ) {
    959                key = new Double( ( (Number) key ).doubleValue() );
    960            }
    961
    962            if ( key instanceof String ) {
    963                if ( ( (String) key ).length() > keyLength ) {
    964                    throw new KeyTooLongException( key, this );
    965                }
    966            }
    967
    968            Page root = getPage( startingPageNo );
    969            Stack<Integer> stack = new Stack<Integer>();
    970
    971            if ( uniqueFlag ) {
    972                int searchResult = root.search( key, stack );
    973                if ( searchResult >= 0 ) {
    974                    throw new KeyAlreadyExistException( key, this );
    975                }
    976
    977                getPage( -searchResult ).addKey( key, record, stack );
    978            } else {
    979                int searchResult = root.searchDupPos( key, stack );
    980                getPage( searchResult ).addKey( key, record, stack );
    981            }
    982        }
    983
    984        /**
    985         * Calculate the depth for the index
    986         */
    987        public int getDepth()
    988                                throws IOException {
    989            Page root = getPage( startingPageNo );
    990            return root.getDepth();
    991        }
    992
    993        /**
    994         * Contains this index unique values?
    995         */
    996        public boolean isUnique() {
    997            return uniqueFlag;
    998        }
    999
    1000        public String toString() {
    1001            return fileName;
    1002        }
    1003    }