/**
 * Merge Sort implementation and test code for linked lists
 * This code includes two implementations of list merging, one recursive and one no-recursive.
 * The recursive implementation is limited to about 15000 items.
 * This also includes two implementations of the full sorting.  One, recursive, the other not. 
 * The non-recursive one is also known as "bottom up."  in this implementation, the non-recursive 
 * algorithm is slower than the recursive be about a factor of 4. 
 * @author gtowell
 * Created: April 20
 * Modified: May 4, 2020
 */
public class MergeSortLL extends SortBase
{
    /** The front of the liked list     */
    Node head = null; 
    /** The number of items in the COMPLETE list */
    int size = 0;

    /**
     * A simple node in a doubly linked list.  Payload is fixed as int
     */
    private class Node { 
        /** The value */
        int val; 
        /** Pointer to the next node */
        Node next; 
        /** Pointer to the previous node */
        Node prev;
        /**
         * Initialized a node
         * @param val the payload
         */
        public Node(int val) 
        { 
            this.val = val;
            next=null;
            prev=null; 
        } 
    } 
  
    /**
     * A recursive implementation of merging of two sorted lists.
     * Works great but limited to merging about 15000 items
     * @param a the head of one list
     * @param b the head of the other list
     * @return the head of the merged lists
     */
    private Node sortedMerge(Node a, Node b) 
    { 
        Node result = null; 
        /* Base cases */
        if (a == null) 
            return b; 
        if (b == null) 
            return a; 
  
        /* Pick either a or b, and recur */
        if (a.val <= b.val) { 
            result = a; 
            result.next = sortedMerge(a.next, b);
            if (result.next!=null)
                result.next.prev=result; 
        } 
        else { 
            result = b; 
            result.next = sortedMerge(a, b.next); 
            if (result.next!=null)
                result.next.prev=result;
        } 
        return result; 
    } 
  
    /**
     * A non-recursive implementation of merging two lists.
     * This can handle arbitrary length lists
     * @param a the head of one list
     * @param b the head of the other list
     * @return the head of the merged lists
     */
    private Node sortedMergeNR(Node a, Node b) 
    { 
        Node result = null;
        Node tail = null;
        /* Base cases */
        if (a == null) 
            return b; 
        if (b == null) 
            return a; 
  
        while (a!=null && b!=null)
        {
            if (a.val <= b.val) { 
        	if (result==null)
        	{
        	    result = a;
        	    tail=a;
        	}
        	else
        	{
                tail.next = a;
                a.prev=tail;
        	    tail=a;
        	}
        	a=a.next;
            } 
            else {
        	if (result==null)
        	{
                result = b;
        	    tail=b;
        	}
        	else
        	{
                tail.next=b;
                b.prev=tail;
        	    tail=b;
        	}
        	b=b.next;
            }
        }
        if (a!=null) {
            tail.next=a;
            a.prev=tail;
        }
        if (b!=null) {
            tail.next=b;
            b.prev=tail;
        }
        return result; 
    } 

    /**
     * A "bottom up" non-recursive implementation of mergesort. This implementation is
     * stunningly inefficient; it is still O(nlogn) but it is about a factor of 4 slower than the 
     * recursive implementation in this code.   With some work, it could be made far mode efficient. 
     * In particular, list splitting could be done better. The tacking merges together could also 
     * be improved.  But it works.
     * With some work could pass lengths into the merge method and thereby avoid several list traversals.
     * This is "bottom up" in the sense that it starts with lists of size 1, merges them, etc.
     * 
     * @param h the head of the list to be sorted
     * @return the head of the sorted list.
     */
    private Node mergeSortBottomUp(Node h) 
    { 
        // Base case : if head is null 
        if (h == null || h.next == null) { 
            return h; 
        }
        Node head=h;
        Node prevPart=null;
        for (int step=1; step<size; step*=2) {
            prevPart=null;
            //System.out.println("\n\nStep Size: " + step);
            h=head;            
            while (h!=null) {
                Node left=h;
                for (int j=0; h!=null && j<step; j++) {
                    h=h.next;
                }
                if (h!=null) {
                    h.prev.next=null;
                    h.prev=null;
                }
                //printList("Left", left);
                Node right=h;
                for (int j=0; h!=null && j<step; j++) {
                    h=h.next;
                }
                if (h!=null) {
                    h.prev.next=null;
                    h.prev=null;
                }
                //printList("Right", right);
                Node n = sortedMergeNR(left, right);
                //printList("Merged ", n);
                if (prevPart==null) {
                    head=n;
                    prevPart=n;
                } else {
                    while (prevPart.next!=null) { 
                        prevPart=prevPart.next;
                    }
                    prevPart.next=n;
                    n.prev=prevPart;
                }
            }
        }
        return head; 
    } 

    /**
     * The recursive merge sort method
     * @param h the head of the list to be sorted
     * @return the head of the sorted list
     */
    private Node mergeSort(Node h) 
    { 
        // Base case : if head is null 
        if (h == null || h.next == null) { 
            return h; 
        } 
  
        // get the middle of the list 
        Node middle = getMiddle(h); 
        Node nextofmiddle = middle.next; 
  
        // set the next of middle node to null 
        middle.next = null; 
  
        // Apply mergeSort on left list 
        Node left = mergeSort(h); 
  
        // Apply mergeSort on right list 
        Node right = mergeSort(nextofmiddle); 
  
        // Merge the left and right lists 
        Node sortedlist = sortedMergeNR(left, right); 
        return sortedlist; 
    } 
  
    /**
     * Use the slow-fast method to find the middle
     * @param head the head of the linked list to find the middle of
     * @return the node in the middle
     */ 
    private static Node getMiddle(Node headNode) 
    { 
        if (headNode == null) 
            return headNode; 
  
        Node slow = headNode;
        Node fast = headNode; 
  
        while (fast.next != null && fast.next.next != null) { 
            slow = slow.next; 
            fast = fast.next.next; 
        } 
        return slow; 
    } 
  
    /**
     * Add an item to the linked list
     * @param new_data the value to be added
     */
    public void push(int new_data) 
    { 
        size++;
        /* allocate node */
        Node new_node = new Node(new_data); 
  
        /* link the old list off the new node */
        new_node.next = head;
        // Bug in teh assignment code, this if was missing
        if (head!=null)
            head.prev = new_node; 
  
        /* move the head to point to the new node */
        head = new_node; 
    } 
  
    /**
     * Utility function to print the doubly linked list.
     * Prints twice, one head to tail, once tail to head.
     * @param pfx a prefix to print before the list
     * @param headref the head node of the linked list
     */ 
    void printList(String pfx, Node headref) 
    { 
        System.out.println(pfx);
        if (headref==null)
            return;
        while (true) { 
            System.out.print(headref.val + " "); 
            if (headref.next==null)
                break;
            headref = headref.next; 
        } 
        System.out.println();
        /**
        while (true) {
            System.out.print(headref.val + " "); 
            if (headref.prev==null)
                break;
            headref = headref.prev; 
        }
        System.out.println();
        **/
    } 
  


    public static void main(String[] args) 
    { 
	    MergeSortLL li = new MergeSortLL(); 
        li.dotest(7, 4000000, false, true);
        li.dotest(7, 4000000, false, false);
    }
    
    /**
     * Run a test
     * @param reps the number of repetitions to run
     * @param siz the number of items to be sorted
     * @param printP if true, print lists before and after sorting
     * @param bottomUpP if true, do mergesort bottom up.
     */
    public void dotest(int reps, int siz, boolean printP, boolean bottomUpP)
    {

        long totaltime = 0;
        for (int r=0; r<reps; r++) {
            head=null;
            int[] aa = fyShuffle(siz);
            for (int aaa : aa)
                push(aaa);

            if (printP)
            {
                printList("UNSorted Linked List is:", head); 
            }  
        
            // Apply merge Sort 
            long stime = System.nanoTime();
            if (bottomUpP) {
                head = mergeSortBottomUp(head);
            } else {
                head = mergeSort(head); 
            }
            long etime = System.nanoTime();
            totaltime+=(etime-stime);
    	    if (printP)
	        {
	            System.out.println("    Time " + " "  + (etime-stime)/100000);
	            printList("Sorted Linked List is:", head); 
            }
        }
        System.out.println("Average Time " + " "  + totaltime/(reps*100000));

    } 
    
    /** required to extend SortBase but not used here */
    public void sortInPlace(int[] array) {
    }
}