// $Id: Palindrome.java,v 1.1 1999/05/19 17:54:06 schmidt Exp $

// The Nth Positive Integer Palindrome Generator
// Copyright (C) 1999 Eric A. Schmidt
// 
// This applet converts between N and the Nth palindrome.
// Correctness was my main focus.  There is room for optimization.

import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.math.*;

public class Palindrome
	extends Applet
	implements ActionListener
{
	static BigInteger m_zero = new BigInteger( "0" );
	static BigInteger m_one = new BigInteger( "1" );
	static BigInteger m_two = new BigInteger( "2" );
	static BigInteger m_ten = new BigInteger( "10" );
	static BigInteger m_eleven = new BigInteger( "11" );

	String m_n;

	TextArea m_messageArea = null;
	TextField m_nTextField = null;
	TextField m_sTextField = null;

	public void init()
	{
		m_n = System.getProperty( "line.separator" );

		GridBagLayout gridBag = new GridBagLayout();
		setLayout( gridBag );

		GridBagConstraints c = new GridBagConstraints();

		c.gridwidth = GridBagConstraints.REMAINDER;
		c.fill = GridBagConstraints.BOTH;
		c.weightx = 1.0;
		c.weighty = 1.0;
		m_messageArea = new TextArea(
			"", 10, 50, TextArea.SCROLLBARS_VERTICAL_ONLY );
		m_messageArea.setEditable( false );
		gridBag.setConstraints( m_messageArea, c ); 
		add( m_messageArea );

		c.gridwidth = GridBagConstraints.REMAINDER;
		c.fill = GridBagConstraints.HORIZONTAL;
		c.weightx = 1.0;
		c.weighty = 0.0;
		m_nTextField = new TextField(
			"Enter integer N here and press ENTER.", 50 );
		m_nTextField.addActionListener( this );
		gridBag.setConstraints( m_nTextField, c ); 
		add( m_nTextField );

		c.gridwidth = GridBagConstraints.REMAINDER;
		c.fill = GridBagConstraints.HORIZONTAL;
		c.weightx = 1.0;
		c.weighty = 0.0;
		m_sTextField = new TextField(
			"Or enter palindrome P here and press ENTER.", 50 );
		m_sTextField.addActionListener( this );
		gridBag.setConstraints( m_sTextField, c ); 
		add( m_sTextField );

		displayMessage(
			"Enter any positive integer, N, in the first field below " +
			"and press ENTER to calculate the Nth palindrome." );
		displayMessage(
			"Or, enter any positive palindrome, P, in the second field below " +
			"and press ENTER to calculate the corresponding integer, N." );
		displayMessage(
			"For example, input 10 for N.  Press ENTER and you will see 11 " +
			"in the palindrome field because 11 is the 10th palindrome." );
		displayMessage(
			"Conversely, input 101 for P.  Press ENTER and you will see 19 " +
			"in the integer field because the 19th palindrome is 101." );
		displayMessage(
			"The larger the input, the longer the calculation time." );
	}

    public void actionPerformed( ActionEvent event )
	{
		TextField field = (TextField)event.getSource();
		String input = field.getText();
		BigInteger i = m_zero;

		if ( input.length() == 0 )
		{
			if ( field == m_nTextField )
				displayMessage(
					"Please enter a positive integer, N " +
					"and press ENTER." );
			else
				displayMessage(
					"Please enter a positive integer palindrome, P, " +
					"and press ENTER." );

			return;
		}

		try
		{
			i = new BigInteger( input );
		}
		catch ( NumberFormatException e )
		{
			displayMessage( "Please enter only numerical characters." );
			return;
		}

		// A way to strip off any leading zeros.
		input = i.toString();
		field.setText( input );

		if ( i.compareTo( m_zero ) <= 0 )
		{
			displayMessage( "Input must be positive." );
			return;
		}

		displayMessage( "Calculating..." );

		if ( field == m_nTextField )
		{
			BigInteger s = ntos( i );
			m_sTextField.setText( s.toString() );
		}
		else
		{
			// Make sure it's a palindrome.
			int j = input.length() / 2 - 1;
			int k = j + 1 + ( input.length() % 2 );
			for ( ; j >= 0; --j, ++k )
				if ( input.charAt( j ) != input.charAt( k ) )
				{
					displayMessage( "Please enter a palindrome." );
					return;
				}

			BigInteger n = ston( i );
			m_nTextField.setText( n.toString() );
		}

		displayMessage( "...done." );
	}

	public void displayMessage( String message )
	{
		m_messageArea.append( ":: " + message + m_n );
	}

	// num_digits( x ) == (BigInteger)floor( log10( x ) ).
	private int num_digits( BigInteger x )
	{
		int count = 0;

		// Don't modify input.
		BigInteger x_ = x;

		while ( x_.compareTo( m_ten ) >= 0 )
		{
			x_ = x_.divide( m_ten );
			++count;
		}

		return count;
	}

	// int_pow( x, y ) == (BigInteger)pow( x, y ).
	private BigInteger int_pow( BigInteger x, int y )
	{
		BigInteger result = m_one;

		// Don't modify input.
		int y_ = y;

		// FIXME - This can be optimized by breaking y down into binary.
		while ( y_ > 0 )
		{
			--y_;
			result = result.multiply( x );
		}

		return result;
	}

	// Convert integer, n, to palindrome, s.
	public BigInteger ntos( BigInteger n )
	{
		int logn = num_digits( n );

		int c =
			n.compareTo(
				m_eleven.
				multiply( int_pow( m_ten, logn - 1 ) ).
				subtract( m_one ) ) >= 0 &&
			n.compareTo(
				m_two.
				multiply( int_pow( m_ten, logn ) ).
				subtract( m_one ) ) < 0 ?
			1 : 0;

		BigInteger q = n;
		q = q.add( m_one );
		q = q.subtract( int_pow( m_ten, num_digits( n.add( m_one ).subtract(
			int_pow( m_ten, logn - 1 ) ) ) ) );

		int qdigits = num_digits( q );

		BigInteger s = q.mod( m_ten ).multiply(
			int_pow( m_eleven, c ).multiply( int_pow( m_ten, qdigits ) ) );

		for ( int k = 1; k <= qdigits; ++k )
			s = s.add( ( q.mod( int_pow( m_ten, k + 1 ) ).divide(
				int_pow( m_ten, k ) ) ).multiply(
					int_pow( m_ten, qdigits - k ) ).multiply(
						( int_pow( m_ten, 2 * k + c ).add( m_one ) ) ) );

		return s;
	}

	// Convert palindrome, s, to integer, n.
	public BigInteger ston( BigInteger s )
	{
		int temp1 = num_digits( s );

		int temp2 = 0;

		if ( ( temp1 % 2 ) == 1 )
		{
			++temp1;
			temp2 = 1;
		}

		temp1 /= 2;

		BigInteger q = s.divide( int_pow( m_ten, temp1 ) );

		BigInteger n = q;
		n = n.subtract( m_one );
		n = n.add( int_pow( m_ten, num_digits( q ) + temp2 ) );

		return n;
	}
}