//File:	NumberList.java
import CSLib.*;
import java.io.*;
import java.util.StringTokenizer;
public class NumberList
{
				//INPUT FUNCTIONS
	//IN:  InputBox
	//OUT: List of ints
	public static int [] inputList (InputBox inBox)
	{
		inBox.setPrompt("How many items in your list? ");
		int n=inBox.readInt();
		
		//allocate n memory locations for array x
		int [] x = new int [n];
		
		//fill the array x with values from the user
		for (int k=0; k<n; k++)
		{
			inBox.setPrompt ("Next number please: ");
			x [k] = inBox.readInt();
		}
		
		return x;	//return the filled array x
	}
	
	//The following function inputs a list of ints from fileName
	//and returns the number of items in the list
	public static int readIntList (String fileName, int [] list)
	{
    		int k=0;
			
    		try
    		{
			//Step 2.  FileReader object (stream of chars)
			FileReader fr = new FileReader(fileName); //throws FileNotFoundException
			
			//Step 3.  BufferedReader object (buffers input allowing access from RAM instead of file)
			BufferedReader br = new BufferedReader (fr);
		
			//Step 4.  readLine() message to Buffered Reader object returns String reference to first line of input
			String line = br.readLine(); //throws IOException
     			while (line != null)
     			{
     				//Since only one token (number) per line
     				//don't need StringTokenizer
     				try
     				{
     					//parseInt() throws NumberFormatException
     					list [k] = Integer.parseInt (line); //converts String to int
     				}
     				catch (NumberFormatException e)
     				{
     					System.out.println ("Error in input. ");
     					System.out.println (line);
     				}
     				k++;
     				line = br.readLine();
     			}
     			
     			br.close(); //not invoked if throws exception
     				
    		}
    		catch (FileNotFoundException e)
    		{
    			System.out.println ("The file " + fileName + " was not found.");
    		}
    		catch (IOException e)
    		{
    		}
    		
    		return k;
  	}
  	
  	//The following function inputs a table of ints from fileName
	//and returns the number of rows and columns
  	public static int [] readTable (String fileName, int [] [] list)
	{
    		int row=0;
    		int col=0;
    		String s;
    		try
    		{
			//Step 2.  FileReader object (stream of chars)
			FileReader fr = new FileReader(fileName); //throws FileNotFoundException
			
			//Step 3.  BufferedReader object (buffers input allowing access from RAM instead of file)
			BufferedReader br = new BufferedReader (fr);
		
			//Step 4.  readLine() message to Buffered Reader object returns String reference to first line of input
			String line = br.readLine(); //throws IOException
     			
     			while (line != null)
     			{
     				StringTokenizer tokenizer = new StringTokenizer (line);
     				int ncols = tokenizer.countTokens();
     				//countTokens() is member function in StringTokenizer class
     				//It's perfect for this application.
     				
     				for (col=0; col<ncols; col++)
     				{
     					s=tokenizer.nextToken();
     					list [row] [col] = Integer.parseInt (s);
     				}
     				row++;
     				line = br.readLine();
     			}
     			
     			br.close(); //not invoked if throws exception
     				
    		}
    		catch (FileNotFoundException e)
    		{
    			System.out.println ("The file " + fileName + " was not found.");
    		}
    		catch (IOException e)
    		{
      			System.out.println (e);
    		}
    		
    		int [] temp = new int [2];
    		temp[0]=row;
    		temp[1]=col;
    		
    		return temp;
  	}
	

				//OUTPUT FUNCTIONS
	//The following method outputs to the screen an array of integers
	//IN:  OutputBox and List
	public static void display (OutputBox box, int [] list)
	{
		for (int k=0; k<list.length; k++)
		{
			box.println (list[k]);
		}
		box.println();
	}
	
	//The following method outputs to the screen a list of n integers
	//IN:  OutputBox, List, Number of items in list
	public static void display (OutputBox box, int [] list, int n)
	{
		for (int k=0; k<n; k++)
		{
			box.println (list[k]);
		}
		box.println();
	}	
	
	//The following method outputs to the screen a table of integers
	//IN:  OutputBox, Table, Number of rows and columns
	public static void display (OutputBox box, int [] [] x, int rows, int cols)
	{
		for (int row=0; row<rows; row++)
		{
			for (int col=0; col<cols; col++)
			{
				box.print ("\t" + x [row] [col]);
			}
			box.println();
		}
	}
	
	//The following method outputs to the screen a table of integers
	//IN:  OutputBox and Table
	public static void display (OutputBox box, int [] [] x)
	{
		//x.length is the number of rows in the table
		for (int row=0; row<x.length; row++)
		{
			//x[row].length it the number of columns in the table
			for (int col=0; col<x[row].length; col++)
			{
				box.print ("\t" + x [row] [col]);
			}
			box.println();
		}
	}

			//STATISTICS
	//The following two methods average an array of numbers
	
	//The following averages int's
	public static int average (int [] a)
	{
		int sum=0;
		for (int k=0; k<a.length; k++)
		{
			sum = sum + a [k];
		}
		return sum/a.length;
	}
	
	//the following averages double's
	public static double average (double [] a)
	{
		double sum=0;
		for (int k=0; k<a.length; k++)
		{
			sum = sum + a [k];
		}
		return sum/a.length;
	}
	
	
	//The following calculates the standard deviation of an array of int's
	public static int sd (int [] a, int average)
	{
		int sum=0;
		for (int k=0; k<a.length; k++)
		{
			sum = sum + (a[k]-average) * (a[k]-average);
		}
		return (int) Math.sqrt(sum/a.length);
	}	
			
			
			//SORTING ALGORITHMS

	//NOTE:	In the following, length is an instance variable
	//	associated with an array object.  It carries the
	//	the size of the array, NOT necessarily the number
	//	of items input to the array.
		
	
	//The insertion sort resembles the process of placing cards
	//into a hand one at a time in order
	static void insertionSort (int [] list)
	{
		for (int i=1; i<list.length; i++)
		{
			//list[0], list[1], ..., list[i-1] are in order
			int currentItem = list[i];
			int j = i-1;
			while (j>=0 && list[j]>currentItem)	//stops when finds a smaller item
			{
				//looking for place to put list[i]
				//so moving elements to the right
				//to make room
				list[j+1] = list[j];	//jth item --> j+1 slot
				j--;
			}
			//list[i] goes into the j+1 slot immediately to right of smaller item
			list[j+1] = currentItem;
		}
	}

	static void swap (int [] list, int i, int j)
	{
		int temp = list[i];
		list[i] = list[j];
		list[j] = temp;
	}
		
	
	
	static void selectionSort (int [] list)
	{
		for (int k=0; k<list.length-1; k++)
		{
			int min = smallestIndex (list, k);
			swap (list, k, min);	//swaps list[k] with list[min]
		}
	}
	

	//The following method finds the INDEX of the smallest item from item n to the end
	public static int smallestIndex (int [] list, int n)
	{
		int smallIndex = n;
		for (int k=n+1; k<list.length; k++)
		{
			if (list[k] < list[smallIndex])
			{
				smallIndex = k;
			}
		}
		return smallIndex;
	}

	//The following method finds the smallest item in a list of integers
	public static int smallest (int [] list)
	{
		int smallestSoFar;
		
		//The following focuses on smallestSoFar,
		//a variable that is compared with each item
		//in the list in succession.  As smaller items
		//are encountered, they are assigned to the variable
		//smallestSoFar.
		smallestSoFar = list[0];
		for (int k=1; k<list.length; k++)
		{
			if (list[k] < smallestSoFar)
			{
				smallestSoFar = list[k];
			}
		}
		return smallestSoFar;
	}
	
	
	//HW #5
	public static void insertInOrder (int [] a, int p, int n)
	{
		//loop until find place for p
		//suppose p goes in slot k
		//move n-1 to n, n-2 to n-2, ...., k to k+1 (loop)
		//a[k] = p;
	}
}