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