001 //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/branches/2.3_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 }