//  File:  SearchAndSortTester.java

//  The SearchSortDemo class has an instance variable that is a 25-element
//  int array, and a constructor that fills it with random 2-digit ints. The
//  class has methods to print the list, sort it, and search it. 

//  Demonstrates the selection sort and linear search algorithms, and random
//  numbers.
//
//  Note: To get a positive random int between a and b, inclusive, use:
//        int number = r.nextInt(b - a + 1) + a ;
//        (where r is a Random class object)

import java.util.* ;				// for classes Arrays and Random
import javax.swing.JOptionPane ;	// for showInputDialog

/**
 * A class to demonstrate searching and sorting (and random numbers).
 */
class SearchSortDemo
{
	// instance vars
	private int [] list ;
	private static final int SIZE = 25 ;	// number of array elements						
	
	/**
	 * Creates an object with an array filled with random numbers.
	 */
	public SearchSortDemo()	
	{
		list = new int[SIZE] ;
		// call method to fill the array
		fill() ;
	}
	
	/**
	 * Fill the array with random, 2-digit ints.
	 */
	public void fill() 				
	{
		Random r = new Random() ;					// create random object
		for (int i = 0 ; i < list.length ; i++)
		   list[i] =  r.nextInt(90) + 10 ;
	}
	
	/**
	 * Sorts the array in ascending order using the selection sort algorithm. 
	 */
	public void sort()				
	{
		// for each element, i, from 0 to next-to-last...
		for (int i = 0 ; i < list.length - 1 ; i++)
		{ 
			// ...find smallest value in elements i+1 through last...
			int minPos = i ;
			for (int j = i + 1 ; j < list.length ; j++)
			{
				if (list[j] < list[minPos])
				  minPos = j ;
			}
			// ...and swap it with element i
			int temp = list[i] ;
			list[i] = list[minPos] ;
			list[minPos] = temp ;
		}
	}
	
	/**
	 * Searches the array to see if a particular value is there.
	 * @param key the value we are looking for
	 * @return the index (subscript) of the element containing key, or -1 if
	 * key is not in the array.
	 */
	public int linearSearch(int key)		
	{
		// check each element of array
		for (int i = 0 ; i < list.length ; i++)
		{ 
			if ( list[i] == key )	// if key found...
			  return i ;			// return index of element where found
		}
		return -1 ;					// return -1 if not in array
	}
	
	/**
	 * Print the array 10 elements per line
	 */
	public void print()				
	{
		for (int i = 0 ; i < list.length ; i++)
		{
		   System.out.print(list[i] + "   ") ;
		   if ( (i + 1) % 10 == 0 )
		     System.out.println() ;
		}
		System.out.println() ;
	}
}

public class SearchAndSortTester
{
	public static void main(String args[])
	{
		SearchSortDemo numbers = new SearchSortDemo() ;

		// print the list...
		System.out.println("The original list:\n") ;
		numbers.print() ;
		
		// do a couple searches
		for (int i = 1 ; i <= 2 ; i++)
		{
			String input = JOptionPane.showInputDialog("Number to search for?");
			int num = Integer.parseInt(input) ;
			
			int index = numbers.linearSearch(num) ;
			
			if ( index >= 0 )
				System.out.println("\n " + num + " found in element " + index) ;
			else
				System.out.println("\n " + num + " is not on the list" ) ;
		}
		
		// sort the list...
		numbers.sort() ;
		
		// print sorted list...
		System.out.println("\nThe sorted list:\n") ;
		numbers.print() ;
		System.out.println() ;
		System.exit(0) ;
	}
}
                 
/*  Sample output:

The original list:

75   27   38   62   41   80   89   27   77   25
56   11   66   58   44   22   40   43   38   61
39   49   93   57   13

 37 is not on the list

 58 found in element 13

The sorted list:

11   13   22   25   27   27   38   38   39   40
41   43   44   49   56   57   58   61   62   66
75   77   80   89   93

*/