| |
| import jdbm.RecordManager; |
| import jdbm.RecordManagerFactory; |
| import jdbm.RecordManagerOptions; |
| |
| import jdbm.btree.BTree; |
| |
| import jdbm.helper.LongComparator; |
| import jdbm.helper.Tuple; |
| import jdbm.helper.TupleBrowser; |
| |
| import java.util.Properties; |
| import java.util.Random; |
| import java.io.IOException; |
| |
| /** |
| * Example program dealing with B+Trees and Prime numbers. |
| */ |
| public class Primes |
| { |
| |
| /** |
| * Default number of prime number to populate in the database (if not specified on command-line) |
| */ |
| public static int DEFAULT_POPULATE = 100; |
| |
| |
| /** |
| * Default number of random lookups (if not specified on command-line) |
| */ |
| public static int DEFAULT_LOOKUPS = 100; |
| |
| |
| /** |
| * Record Manager used for persistence. |
| */ |
| private RecordManager _recman; |
| |
| |
| /** |
| * B+Tree holding prime numbers. |
| */ |
| private BTree _primes; |
| |
| |
| /** |
| * Random number generator. |
| */ |
| private static Random _random = new Random(); |
| |
| |
| /** |
| * Main constructor |
| */ |
| public Primes( String[] args ) |
| throws IOException |
| { |
| long recid; |
| Properties props; |
| |
| // open database and setup an object cache |
| props = new Properties(); |
| props.put( RecordManagerOptions.CACHE_SIZE, "10000" ); |
| _recman = RecordManagerFactory.createRecordManager( "primes", props ); |
| |
| recid = _recman.getNamedObject( "primes" ); |
| if ( recid == 0 ) { |
| System.out.println( "Creating a new primes B+Tree." ); |
| _primes = BTree.createInstance( _recman, new LongComparator() ); |
| _recman.setNamedObject( "primes", _primes.getRecid() ); |
| } else { |
| _primes = BTree.load( _recman, recid ); |
| System.out.println( "B+Tree already contains " + _primes.size() + " primes." ); |
| } |
| _recman.commit(); |
| } |
| |
| |
| /** |
| * Get the largest prime number in the database. |
| */ |
| public Long getLargestPrime() |
| throws IOException |
| { |
| Tuple tuple; |
| TupleBrowser browser; |
| Long largest = null; |
| |
| tuple = new Tuple(); |
| browser = _primes.browse( null ); |
| if ( browser.getPrevious( tuple ) ) { |
| largest = (Long) tuple.getValue(); |
| System.out.println( "Largest prime: " + largest ); |
| } else { |
| System.out.println( "No prime number in the database." ); |
| } |
| return largest; |
| } |
| |
| |
| /** |
| * Populate the database with more prime numbers. |
| * |
| * @param count Number of primes to add to database. |
| */ |
| void populate( int count ) |
| throws IOException |
| { |
| Long current; |
| Long largest; |
| |
| System.out.println( "Populating prime B+Tree..." ); |
| |
| // start after the largest known prime |
| largest = getLargestPrime(); |
| if ( largest == null ) { |
| largest = new Long( 0 ); |
| } |
| |
| current = new Long( largest.longValue() + 1L ); |
| while ( count > 0 ) { |
| if ( isPrime( current ) ) { |
| _primes.insert( current, current, false ); |
| System.out.println( "Found prime #" + _primes.size() + ": " + current ); |
| count--; |
| } |
| current = new Long( current.longValue() + 1 ); |
| } |
| _recman.commit(); |
| } |
| |
| |
| /** |
| * Returns true if a number is prime. |
| */ |
| boolean isPrime( Long number ) |
| throws IOException |
| { |
| Tuple tuple; |
| TupleBrowser browser; |
| Long largest; |
| Long current; |
| |
| if ( number.longValue() <= 0L ) { |
| throw new IllegalArgumentException( "Number must be greater than zero" ); |
| } |
| if ( number.longValue() == 1 ) { |
| return true; |
| } |
| tuple = new Tuple(); |
| browser = _primes.browse(); |
| while ( browser.getNext( tuple ) ) { |
| current = (Long) tuple.getValue(); |
| if ( current.longValue() != 1 && ( number.longValue() % current.longValue() ) == 0 ) { |
| // not a prime because it is divisibe by a prime |
| return false; |
| } |
| } |
| // this is a prime |
| return true; |
| } |
| |
| |
| /** |
| * Display a number of random prime numbers. |
| */ |
| void random( int count ) |
| throws IOException |
| { |
| Tuple tuple; |
| TupleBrowser browser; |
| Long largest; |
| Long number; |
| |
| tuple = new Tuple(); |
| largest = getLargestPrime(); |
| |
| System.out.println( "Looking up " + count + " random primes...." ); |
| long start = System.currentTimeMillis(); |
| for ( int i=0; i<count; i++ ) { |
| number = new Long( random( 0, largest.longValue() ) ); |
| browser = _primes.browse( number ); |
| if ( browser.getNext( tuple ) ) { |
| number = (Long) tuple.getValue(); |
| System.out.print( number ); |
| System.out.print( ", " ); |
| } |
| } |
| long stop = System.currentTimeMillis(); |
| System.out.println(); |
| System.out.println( "Time: " + (stop-start)/count + " millis/lookup " ); |
| } |
| |
| |
| /** |
| * Return true if number is a prime. |
| */ |
| public static boolean isPrimeCompute( long number ) |
| { |
| for ( int i=2; i<number/2; i++ ) { |
| if ( ( number % i ) == 0 ) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| |
| /** |
| * Get random number between "low" and "high" (inclusively) |
| */ |
| public static long random( long low, long high ) |
| { |
| return ( (long) ( _random.nextDouble() * (high-low) ) + low ); |
| } |
| |
| |
| /** |
| * Static program entrypoint. |
| */ |
| public static void main( String[] args ) |
| { |
| Primes primes; |
| int count; |
| Long number; |
| Long largest; |
| |
| try { |
| primes = new Primes( args ); |
| |
| for ( int i=0; i<args.length; i++ ) { |
| if ( args[i].equalsIgnoreCase( "-populate" ) ) { |
| if ( ++i < args.length ) { |
| count = Integer.parseInt( args[i] ); |
| } else { |
| count = DEFAULT_POPULATE; |
| } |
| primes.populate( count ); |
| } else if ( args[i].equalsIgnoreCase( "-check" ) ) { |
| if ( ++i < args.length ) { |
| number = new Long( Long.parseLong( args[i] ) ); |
| } else { |
| number = new Long( _random.nextLong() ); |
| } |
| largest = primes.getLargestPrime(); |
| if ( number.longValue() > primes.getLargestPrime().longValue() ) { |
| throw new IllegalArgumentException( "Number is larger than largest known prime in database." ); |
| } |
| if ( primes.isPrime( number ) ) { |
| System.out.println( "The number " + number + " is a prime." ); |
| } else { |
| System.out.println( "The number " + number + " is not a prime." ); |
| } |
| } else if ( args[i].equalsIgnoreCase( "-random" ) ) { |
| if ( ++i < args.length ) { |
| count = Integer.parseInt( args[i] ); |
| } else { |
| count = DEFAULT_LOOKUPS; |
| } |
| primes.random( count ); |
| } |
| } |
| if ( args.length == 0 ) { |
| System.out.println( "Usage: java Prime [action] [args]" ); |
| System.out.println( "" ); |
| System.out.println( "Actions:" ); |
| System.out.println( " -populate [number] Populate database with prime numbers" ); |
| System.out.println( " -check [number] Check if a number is a prime" ); |
| System.out.println( " -random [number] Display random prime numbers" ); |
| System.out.println( "" ); |
| } |
| } catch ( IOException except ) { |
| except.printStackTrace(); |
| } |
| } |
| } |