Search Tree implementation

import java.util.Collection;

import java.util.LinkedList;

import java.util.ArrayList;

import java.util.Iterator;

import weiss.nonstandard.BinarySearchTreeWithRank;

public final class Josephus

{

/**

* Return the winner in the Josephus problem.

* Linked list implementation.

* (Can replace with ArrayList or TreeSet).

*/

public static int jos1( int people, int passes )

{

Collection theList = new LinkedList( );

// Construct the list

for( int i = 1; i <= people; i++ )

theList.add( new Integer( i ) );

// Play the game;

Iterator itr = theList.iterator( );

while( people-- != 1 )

{

for( int i = 0; i <= passes; i++ )

{

if( !itr.hasNext( ) )

itr = theList.iterator( );

itr.next( );

}

itr.remove( );

}

itr = theList.iterator( );

return ( (Integer) itr.next( ) ).intValue( );

}

/**

* Recursively construct a perfectly balanced BinarySearchTreeWithRank

* by repeated insertions in O( N log N ) time.

* t should be empty on the initial call.

*/

public static void buildTree( BinarySearchTreeWithRank t,

int low, int high )

{

int center = ( low + high ) / 2;

if( low <= high )

{

t.insert( new Integer( center ) );

buildTree( t, low, center - 1 );

buildTree( t, center + 1, high );

}

}

/**

* Return the winner in the Josephus problem.

* Search Tree implementation.

*/

public static int jos2( int people, int passes )

{

BinarySearchTreeWithRank t = new BinarySearchTreeWithRank( );

buildTree( t, 1, people );

int rank = 1;

while( people > 1 )

{

rank = ( rank + passes ) % people;

if( rank == 0 )

rank = people;

t.remove( t.findKth( rank ) );

people--;

}

return ( ( Integer ) ( t.findKth( 1 ) ) ).intValue( );

}

// Quickie main to test

public

...