import DataStructures.*;
import Supporting.*;
import Exceptions.*;

public final class Josephus
{
    /**
     * Return the winner in the Josephus problem.
     * Linked list implementation.
     */
    public static int jos1( int people, int passes )
    {
        LinkedListItr p = new LinkedListItr( new LinkedList( ) );

            // Construct the list
        try
        {
            for( int i = 1; i <= people; i++ )
                p.insert( new Integer( i ) );
        }
        catch( ItemNotFound e ) { }  // Cannot happen

            // Play the game;
            // Note: p is always one player before
        while( people-- != 1 )
        {
            for( int i = 0; i < passes; i++ )
            {
                p.advance( );        // Advance
                if( !p.isInList( ) ) // If we just went past last player
                    p.first( );      // then go back to first
            }

            if( !p.removeNext( ) )   // Remove next player
            {
                // removeNext fails if p is last item,
                p.zeroth( );         // so for last item, set p
                p.removeNext( );     // to 0th player to remove first player
            }
        }

        p.first( );                    // Get first and only player and return
        return  ( (Integer)( p.retrieve( ) ) ).intValue( ); // player's number
    }

    /**
     * Recursively construct a perfectly balanced OrderedSearchTree
     * 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 )
        {
            try
              { t.insert( new MyInteger( center ) ); }
            catch( DuplicateItem e ) { }  // Cannot happen

            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( );

        try
        {
            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 ( ( MyInteger ) ( t.findKth( 1 ) ) ).intValue( );
        }
        catch( Exception e )
          { return -1; } // Cannot happen
    }


    // Quickie main to test

    public static void main( String [ ] args )
    {
        try
        {
            if( args.length == 2 )
            {
                int arg1 = Integer.parseInt( args[ 0 ] );
                int arg2 = Integer.parseInt( args[ 1 ] );
                System.out.println( jos1( arg1, arg2 ) );
                System.out.println( jos2( arg1, arg2 ) );
            }
            else
                System.err.println( "Usage: Jos People Passes" );
        }
        catch( NumberFormatException e )
          { System.err.println( "Usage: Jos People Passes" ); }
    }
}