package Algorithms.Sorting;

import Algorithms.Interfaces.JSorter;
import Utilities.BillBoard;

import javax.lang.model.element.Element;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Class which is the implementation of MergeSort
 * 
 * @author lilott8
 * @version 0.2
 * @since 205-02-24
 */
public class JMergeSort extends JSort implements JSorter {

    public final String TAG = getClass().getSimpleName();
    
    public JMergeSort() {
        super();
    }
    
    public JMergeSort(int x) {
        super(x);
    }
    
    public JMergeSort(List<Integer> values) {
        super(values);
    }

    /**
     * Get the size of the array 
     * @return int as size of array
     */
    public int getSize() {
        return mSize;
    }

    /**
     * Gets a value at an index of the array 
     * @param x index to be retrieved
     * @return int value at index
     */
    public int getValue(int x) {
        return mValues.get(x);
    }

    /**
     * Sort the array using selection
     */
    public void sort() {
        mValues = mergeSort(mValues);
    } // sort

    /**
     * Split the lists recursively until they contain 1 element 
     * @param list list of elements to be split
     * @return list of elements, sorted.
     */
    protected List<Integer> mergeSort(List<Integer> list) {
        // Base case, we have only 1 item in our list
        if(list.size() == 1) {
            return list;
        }
        
        // Get the middle value to split the list into 2
        int midPoint = list.size()/2;

        List<Integer> left = new ArrayList<Integer>();
        List<Integer> right = new ArrayList<Integer>();

        // get the left half of the list
        for(int x = 0; x < midPoint; x++) {
            left.add(list.get(x));
        }
        
        // get the right half of the list
        for(int x = midPoint; x < list.size(); x++) {
            right.add(list.get(x));
        }

        // merge sort again!
        left = mergeSort(left);
        right = mergeSort(right);
        
        // zipper the lists together
        return merge(left, right);
    }

    /**
     * Combine the fragmented lists into one big list 
     * @param left left half of the lists, the lower numbers
     * @param right right half of the lists, the higher numbers
     * @return merged lists
     */
    private List<Integer> merge(List<Integer> left, List<Integer> right) {
        List<Integer> result = new ArrayList<Integer>();

        // Move elements from either side to the result list
        while(!left.isEmpty() && !right.isEmpty()) {
            if(left.get(0) <= right.get(0)) {
                result.add(left.get(0));
                left.remove(0);
            } else {
                result.add(right.get(0));
                right.remove(0);
            }
        }
        
        // Finish emptying either list if there are elements.
        while(!left.isEmpty()) {
            result.add(left.get(0));
            left.remove(0);
        }
        while(!right.isEmpty()) {
            result.add(right.get(0));
            right.remove(0);
        }
        
        return result;
    }
    
    /**
     * Print the array to std out. 
     */
    public void printArray() {
        BillBoard.d(TAG, super.getArrayAsString());
    }

}
