/******************************************************************
*
*   Class: ArrayHandler
*
*   Assignment:  Project 3
*
*   Author: Mark Fraser(mfraser)
*   Course:  COP 3530, Summer C 1999
*
*  This class handles:
*
*  1)  getting a sequence of integers from a stdin; and
*  2)  outputting to std out the array after sorting it
*
*
*******************************************************************/

import java.io.*;

public class ArrayHandler
{
  /*****     Data Members   *******/
  
  private static final int MAXNUMBERS = 1000;   //most numbers allowed
  private static final int NUMWIDTH = 7;        //display width of each number      
  private int [] arrayOfIntegers;     // holds the numbers read in after they
                                      // are parsed
  private int count;            // keep count of number of elems. in seq.
  
    
  /*******    Methods        ********/
    
  public ArrayHandler()           // constructor
  {
    arrayOfIntegers = new int[MAXNUMBERS];  //allocate space for array
    count = 0;
  }
  
  public void getValues() throws java.io.IOException
  {
    //use a string buffer to accumulate each individual number
    StringBuffer inputStr = new StringBuffer();  
                                                   
    int inputNum = System.in.read();      //read the first character
                          
    while (inputNum != -1)                // read until end of file       
    {  
      //check for non-numerical token      
      if ( (inputNum != '-') && ( (inputNum < (int)'0') ||   
            (inputNum > (int)'9') ) )               
                           
      {  
    	  addElement(inputStr);            //add to array using class method
      }
      else
        inputStr.append((char)inputNum);    //add digit to buffer 
    
      inputNum = System.in.read();          //get next number or token
    }
	addElement(inputStr);                   //add last number
  }
 
  
  private void addElement(StringBuffer newElement) //add a new element to the array
  {
    if (newElement.length() == 0) return;    //there is no number to add
	
	//instance of Integer class -
    //used to convert the string buffer to an integer
    Integer inputInteger = new Integer(newElement.toString());   
    arrayOfIntegers[count] = inputInteger.intValue(); //convert Integer to int 
	                                                  //and put in array
    count++;
    newElement.setLength(0);             //reset StringBuffer
  }  
   
  public void writeSequence()          //writes sequence as read
  {
  	Integer tempInt;
	StringBuffer tempStr;

	for (int i = 0; i < count; i++)
	{
	  if ( (i > 0) && ((i % 10) == 0) )       //print new line after every ten
	    System.out.print("\n");
      tempInt = new Integer(arrayOfIntegers[i]); 
	  tempStr = new StringBuffer(tempInt.toString());
	  while (tempStr.length() < NUMWIDTH)     //pad on left with spaces
	    tempStr.insert(0, ' ');
	  System.out.print(tempStr);
	}
	System.out.print("\n");
	System.out.println("");
	
  }
  
  public void sortHistogram()
  {
    int histoSlots[];                     //slots on histogram to hold values
	int slotsNeeded, min, i, j, k;
	min = getMin();                       //minimim val used to determine range
	slotsNeeded = getMax() - min + 1;
	histoSlots = new int[slotsNeeded];     //create the histogram slots 
	for (i = 0; i < count; i++)
	  (histoSlots[arrayOfIntegers[i] - min])++;  //create the histogram
	
	//now refill the array, sorted
	j = 0;
	for (i = slotsNeeded - 1; i >= 0; i--)
	  for (k = 0; k < histoSlots[i]; k++) 
	    arrayOfIntegers[j++] = i + min;
  }
  
  public void sortInsertion()
  {
  	for (int i = 1; i < count; i++)    //insert each element to array in sorted place
	{
	  int t = arrayOfIntegers[i];
	  
	                                  //find place for t
	  int j;
	  for (j = i - 1; j >= 0 && t > arrayOfIntegers[j]; j--)
	    arrayOfIntegers[j + 1] = arrayOfIntegers[j];
	  
	  arrayOfIntegers[j + 1] = t;
	}
  }
  
  
  //merge sort is broken up into methods sortMerge, doMergeSort and merge
  public void sortMerge()
  {
  	int workspace[] = new int[count];      //array for workspace
	doMergeSort(workspace, 0, count - 1);  
  }
  
  private void doMergeSort(int[] workspace, int lower, int upper)
  {
    if (lower == upper)                    //nothing to sort
	  return;
	
	int middle = (lower + upper) / 2;           //cut array in half
	doMergeSort(workspace, lower, middle);      //sort the lower half
	doMergeSort(workspace, middle + 1, upper);  //sort the upper half
	merge(workspace, lower, middle + 1, upper); //merge the parts
  }
  
  private void merge(int[] workspace, int low, int high, int upperBound)
  {
    int j = 0;
	int lowerBound = low;                   
	int mid = high - 1;                    
	int n = upperBound - lowerBound + 1;
	
	
	//merge the arrays by adding the lower of the two halves
	//into the new sorted array
	while (low <= mid && high <= upperBound) 
	  if (arrayOfIntegers[low] > arrayOfIntegers[high])
	    workspace[j++] = arrayOfIntegers[low++];
	  else
	    workspace[j++] = arrayOfIntegers[high++];
	
	while(low <= mid)                         //put values from remaining array in ws
	  workspace[j++] = arrayOfIntegers[low++];
	
	while (high <= upperBound)
	  workspace[j++] = arrayOfIntegers[high++];
	  
	for (j = 0; j < n; j++)                  //put values from workspace into array
	  arrayOfIntegers[lowerBound+j] = workspace[j];
	
  }
	
  public int getMax()  //returns maximum in the array, or 0 if no elements
  {
    int max = 0;
    if (count > 0)
    {
      max = arrayOfIntegers[0];          //initialize max to 1st element
      for (int i = 1; i < count; i++)
      {
        if (arrayOfIntegers[i] > max)
          max = arrayOfIntegers[i];
      }
    }
    
    return max;
  }
   
  public int getMin()  //returns minimum in the array, or 0 if no elements
  {
    int min = 0;
    if (count > 0)
    {
      min = arrayOfIntegers[0];          //initialize min to 1st element
      for (int i = 1; i < count; i++)
      {
        if (arrayOfIntegers[i] < min)
          min = arrayOfIntegers[i];
      }
    }
    
    return min;
  }
	
  public int getSize()
  {
    return count;
  } 
}