/******************************************************************
*
*	Class: DLinkList
*
*   Assignment:  Project 3
*
*   Author: Mark Fraser      Course:  COP 3530, Summer C 1999
*
*  This class encapsulates a doubly-linked list.  The list
*  contains methods for histogram sort and insertion sort.
*
*
*******************************************************************/

import java.io.*;
import DLink;                    //node object

class DLinkList
{
	
/*           DATA                  */
  private static final int NUMWIDTH = 7; //display width of each number      

  protected DLink first;            // ref to first link in list
  protected DLink last;             // ref to last link in list
  protected int size;              // size of list
	
	/*            METHODS              */
  public DLinkList()              // constructor
  {
 	size = 0;
	first = null;               // no links on list yet
	last = null;
  }

  public boolean isEmpty()       // true if list is empty
  {
    return (size==0);
  }

  public int getSize()
  {
	return size;
  }
    
  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') ) )               
      {  
        addInputElement(inputStr);
      }
      else
        inputStr.append((char)inputNum);    //add digit to buffer 
	    
      inputNum = System.in.read();          //get next number or token
    }
	addInputElement(inputStr);         //add last number
  }
	 
	  
  private void addInputElement(StringBuffer newElement) //add a new element to the array
  {
    if (newElement.length() == 0) return;
	
		//instance of Integer class -
	    //used to convert the string buffer to an integer
    Integer inputInteger = new Integer(newElement.toString()); 
    insertElementAt(inputInteger, size);
    newElement.setLength(0);             //reset StringBuffer
  }  

  public void insertElementAt(Object obj, int index)    //inserts at position index
  {                           
   	if (index < 0 || index > size)    //invalid list position
	  throw new IllegalArgumentException
      ("DLinkList.insertElementAt: " +
	    "index must be between 0 and size");
		
	if (size == 0)
	{
      DLink newLink = new DLink(obj, null, null);   //first link
      first = newLink;
      last = newLink;
	}
		
	else if (index == 0)           //insert at front
	{	
      DLink newFirst = new DLink(obj, null, first);
      first.previous = newFirst;
      first = newFirst;
	}
			
	else if (index == size)	  // insert at end
	{
      DLink newLast = new DLink(obj, last, null); 
      last.next = newLast;
      last = newLast;
	}
	else                       //insert in middle
	{
      DLink l = first;
      for (int i = 0; i < index - 1; i++)
        l = l.next;
			
	//l is now pointing to the element that will be prev to new element
			
      DLink newNext = l.next;    //new element will pt to l's old next
      DLink newLink = new DLink(obj, l, newNext);  //new element has l as prev
			                                         //and newNext as next
      l.next = newLink;                 //l's next is now the new element
      newNext.previous = newLink;     //newNext's previous is the new element
	}
      size++;
  }

  public void removeElementAt(int index)  //removes at position index
  {                           
   	if (index < 0 || index >= size)    //invalid list position
	  throw new IllegalArgumentException
      ("DLinkList.removeElementAt: " +
	    "index must be between 0 and size - 1");
		
	if (index == 0)                       //removing first
	{
      first = first.next;
	  first.previous = null;
	}
	else if (index == size - 1)           //removing last
	{
	  last = last.previous;
	  last.next = null;
	}
	else
	{
	  DLink l = first;
	  for (int i = 0; i < index - 1; i++)
	    l = l.next;
	  l.next = l.next.next;	
	  l.next.previous = l;
	}
	size--;	
  }
	
  public Object elementAt(int index)  //return element with specified index
  {
	if (index < 0 || index >= size)   //invalid list position
		throw new IllegalArgumentException("DLinkList.elementAt: " +
			"index must be between 0 and size - 1");
		
	if (index == 0)
	  return first;
		
	if (index == size - 1)
	  return last;
		  
	boolean forward;                      //search forwared if element in 1st
		                                      // half, backward otherwise
	forward = (index < (size / 2)) ?      
	  true : false;                      		  
	                                          		
	DLink current = (forward) ? first : last;  //start at front or back, based on dir
	if (forward)
	{
      for (int i = 0; i < index; i++)
			current = current.next;
	}
	else
	{
      for (int i = size - 1; i > index; i--)
			current = current.previous;
	}
    return current.lData;
  }
	
  public void displayList()
  { 	
    DLink current = first;       // start at beginning of list
  	int printed = 0;
	  
	while (printed < size)
	{
	  StringBuffer tempStr = new StringBuffer(current.lData.toString());
	  while (tempStr.length() < NUMWIDTH)   //pad on left with spaces
		tempStr.insert(0, ' ');
 	  System.out.print(tempStr);
      printed++;
	  if ((printed % 10) == 0)       // new line needed?
		System.out.print("\n");
      current = current.next;  // move to next link
    }
    System.out.print("\n");
	System.out.println("");
  }
  
  public int getMin()
  {
    if (size == 0) return 0;
	DLink current;
	int temp;
	int min = ((Integer)first.lData).intValue();
	current = first.next;
	while (current != null)
	{
	  temp = ((Integer)current.lData).intValue();
	  if (temp < min)
	    min = temp;
	  current = current.next;
	}
	return min;
  }
	
  public int getMax()
  {
    if (size == 0) return 0;
  	DLink current;
  	int temp;
  	int max = ((Integer)first.lData).intValue();
  	current = first.next;
  	while (current != null)
  	{
  	  temp = ((Integer)current.lData).intValue();
  	  if (temp > max)
  	    max = temp;
  	  current = current.next;
  	}
  	return max;
  }
	
    
  public void sortHistogram()
  {
    int min, max;
	
	if (size < 2) return;                  //already sorted
	min = getMin();                        //get min and max to find range
	max = getMax();
	int range = max - min + 1;
	DLink [] bottom = new DLink[range + 1];//create bins
	DLink [] top = new DLink[range + 1];
	int b;
	for (; first != null; first = first.next)
	{
	  b = ((Integer)first.lData).intValue();
	  if (bottom[max - b] == null)                  //bin is empty
	    bottom[max - b] = top[max - b] = first;
	  else                                    //bin is not empty
      {  
		top[max - b].next = first;
		top[max - b] = first;
      }
	}
	
	DLink y = null;
	for (b = 0; b <= range; b++)
	{
	  if (bottom[b] != null)
	  {
	  	if (y == null)
		{
		  first = bottom[b];
		  bottom[b].previous = null;
		}
		else
		{
		  y.next = bottom[b];
		  bottom[b].previous = y;
		}
		y = top[b];
	  }
	}
  }	
  
  
  //sortInsertion and insertIntoSorted are both used in insertion sort
  public void sortInsertion()
  {
    int num, currentValue;
	if (size < 2) return;                   //already sorted
	DLink current, sortedElem;
	current = first;
	
	while (current != null)              //go through the list
    {
	  //remove the element
	  if (current == first)
	  {
	    first = current.next;
		first.previous = null;
	  }
	  else if (current == last)
	  {
	    last = current.previous;
		last.next = null;
	  }
	  else
	  {
	    current.previous.next = current.next;
		current.next.previous = current.previous;
	  }
      size--;
	  DLink nextElem = current.next;
	  insertIntoSorted(current);	
	  current = nextElem;
	}  
  }
        
  public void insertIntoSorted(DLink anElem)    //inserts an element into descending sorted list
  {
    DLink current;
	int temp, elemValue;
	
	if (size == 0)
	{
	  insertElementAt(anElem, 0);
	  return;
	}
	
	elemValue = ((Integer)anElem.lData).intValue();
	current = first;
	while ((current != null) && ((Integer)current.lData).intValue() > elemValue)
	  current = current.next;
	
	if (current == null)         //reached the end
	{
	  last.next = anElem;
	  anElem.previous = last;
	  anElem.next = null;
	  last = anElem;
	}
	else
	{
	  if (current == first)         //insert at front
	  {
	    first = anElem;
		anElem.previous = null;
	  }
	  else
	  {
	    anElem.previous = current.previous;
	    current.previous.next = anElem;
	  }
	  current.previous = anElem;
	  anElem.next = current;
	}
	size++;
  }
  
  public void displayListReversed()     //display list in reverse
  {
    DLink current = last;              // start at end of list
    int printed = 0;
  
   	System.out.println("Reversed sequence:");
  	while (printed < size)
  	{
  		StringBuffer tempStr = new StringBuffer(current.lData.toString());
  		while (tempStr.length() < NUMWIDTH)   //pad on left with spaces
  		tempStr.insert(0, ' ');
     	System.out.print(tempStr);
   			printed++;
  		if ((printed % 10) == 0)         //new line needed?
  		System.out.print("\n");
   			current = current.previous;  // move to next link
    }
     		System.out.print("\n");
  		System.out.println("");
  }


}