001    //$HeadURL: svn+ssh://jwilden@svn.wald.intevation.org/deegree/base/branches/2.5_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    }