/******************************************************************
*
*   Class: DLLMergeSort
*
*   Assignment:  Project 3
*
*   Author: Mark Fraser  (mfraser)     
*   Course:  COP 3530, Summer C 1999
*
*  This class extends a doubly-linked list to add merge sorting.
*
*******************************************************************/

public class DLLMergeSort extends DLinkList
{
  // recursive method for sorting the list 
  private void mergeSort(DLinkList leftSide)  // left side of list
  {
    DLinkList rightSide = new DLinkList(); //right half 
    if (leftSide.getSize() > 1) //  merging needed
    {
      divideList(leftSide, rightSide); // split the list into left and right
      mergeSort(leftSide);             // sort left side
      mergeSort(rightSide);            // sort right side
      merge(leftSide, rightSide);      // merges sides
    }
  }

  // splits a list in half. 
  private void divideList(DLinkList leftSide, DLinkList rightSide)
  {
    DLink current = null;                
    DLink mid = null;                    
    mid = leftSide.first;
    if (mid == null) // if the original chain is null, then there's nothing to do
      rightSide.first = null;
    else
    {
      current = mid.next;                // move to the next node
      while (current != null)
      {
        current = current.next;          // move the current node ahead again
        if (current != null)  
        {
          mid = mid.next;                // move the midpoint ahead
          current = current.next;
        }
      }
      rightSide.first = mid.next;         
      mid.next = null;                    // terminate left
      DLink tempLink = leftSide.first;    // used for counting the nodes in the left list
      int count = 0;                      // keeps count of nodes
      while (tempLink != null)            // count the links in the left list
      {
        count++; 
        tempLink = tempLink.next;
      }
      leftSide.size = count++;            // update the size of left list
      count = 0;                          // repeat for the size of right list
      tempLink = rightSide.first;
      while (tempLink != null)
      {
        count++;
        tempLink = tempLink.next;
      }
      rightSide.size = count;              // update the size of right
    }
  }

  private void merge(DLinkList aList, DLinkList bList)
  {
    DLink firstLink = null;                // firstNode
    DLink secondLink = null;               // secondNode
    DLink lastLink = null;                 // lastNode
    if (aList.first == null)               
      aList = bList;
    else if (bList.first != null)
    {
      while (bList.getSize() != 0)         // merge until bList is empty
      {
        firstLink = bList.first;           // firstLink is a node in bList to put into aList
        bList.first = bList.first.next;    // remove node from blist
        firstLink.next = null;             // seperate firstLink
        bList.size--;                      // update the size of blist
        lastLink = aList.first;            // current position in the alist
        boolean fSet = false;              // fSet tells if firstLink has been placed yet
        if (lastLink == null)
          aList.first = firstLink;
        else if (((Integer)firstLink.lData).intValue()
		     > ((Integer)lastLink.lData).intValue() )
        {
          firstLink.next = lastLink;
          aList.first = firstLink;
        }
        else
        {
          while ((lastLink != null) && (!fSet)) // find the right spot for firstlink
          {
            secondLink = lastLink;
            lastLink = lastLink.next;
            if (lastLink == null)            // firstlink is placed at the end of the alist
            {
              secondLink.next = firstLink;
            }
            else
            {
              if (((Integer)firstLink.lData).intValue() >
			      ((Integer)lastLink.lData).intValue()) // insert firstlink between two other nodes
              {
                firstLink.next = lastLink;
                secondLink.next = firstLink;
                fSet = true;
              }
            }
          }
        }
      }
    }
    DLink tempLink = aList.first; 
    int count = 0;
    while (tempLink != null)
    {
      count++;
      tempLink = tempLink.next;
    }
    aList.size = count;          // update the size of aList
  }

  /* method for calling the merge sort */
  public void mergeSort()
  {
    DLink current = first;
	DLink nextPrev = null;
	mergeSort((DLinkList)this);
  
    // the previous pointers are not used in the merge sort process, so to keep
	// the merge code simpler one pass at the end is made to properly set the previous
	// pointers - this is O(n) so it does not greatly hurt the efficiency
	
	if (first != null)
	{
	  first.previous = null;
	  nextPrev = first;
	  current = first.next;
	}
	
	for (int i = 1; i < size; i++)
	{
	    current.previous = nextPrev;
	    nextPrev = current;
	    current = current.next;
	}
	last = nextPrev;
  }
  
  
}