/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java to edit this template
 */
package com.mycompany.programingexam2_calebfontenot;

import java.lang.reflect.Array;
import java.util.Comparator;

/**
 *
 * @author ar114
 */
public class GenericMergeSortExam {

    public static <E extends Comparable<E>> void mergeSort(E[] list) {
        mergeSort(list,
                new Comparator<E>() {
            @Override
            public int compare(E e1, E e2) {
                int compareResult = ((Comparable<E>) e1).compareTo(e2);
                return compareResult;
            }
        });
    }

    public static <E> void mergeSort(E[] list,
            Comparator<? super E> comparator) {
        if (list.length > 1) {
            // Merge sort the first half
            E[] firstHalf = (E[]) new Object[list.length / 2];
            //copies 1st half of list into array firstHalf
            System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
            mergeSort(firstHalf, comparator);
            // Merge sort the second half
            int secondHalfLength = list.length - list.length / 2;
            E[] secondHalf = (E[]) new Object[secondHalfLength];
            System.arraycopy(list, list.length / 2,
                    secondHalf, 0, secondHalfLength);
            mergeSort(secondHalf, comparator);
            // Merge firstHalf with secondHalf
            E[] temp = merge1(firstHalf, secondHalf, comparator);
            System.arraycopy(temp, 0, list, 0, temp.length);
        }
    }

    /**
     * Merges the two lists using a Comparator.
     *
     * @param <E> The generic type the methods accepts.
     * @param list1 a list of generic type E
     * @param list2 a list of generic type E
     * @param comparator Comparator
     * @return a sorted new list made of the merged list1 and list2.
     */
    private static <E> E[]
            merge1(E[] list1, E[] list2, Comparator<? super E> comparator) {
        int returnArraySize = list1.length + list2.length;
        E[] returnArray = (E[]) new Object[returnArraySize];
        int list1Iterator = 0, list2Iterator = 0, returnArrayIterator = 0, iterationsRemaining = 0;
        for (; returnArrayIterator < returnArraySize; ++returnArrayIterator) {
            iterationsRemaining = (returnArraySize - returnArrayIterator);
            if (comparator.compare(list1[list1Iterator], list2[list2Iterator]) <= 0) {
                returnArray[returnArrayIterator] = list1[list1Iterator];
                if (iterationsRemaining > 1)
                    returnArray[returnArrayIterator + 1] = list2[list2Iterator];
                if ((list1.length - 1) < (list1Iterator)) {
                    ++list1Iterator;
                } else {
                    ++list2Iterator;
                }
                ++returnArrayIterator;
            } else {
                returnArray[returnArrayIterator] = list2[list2Iterator];
                if (iterationsRemaining > 1)
                    returnArray[returnArrayIterator + 1] = list1[list1Iterator];
                if ((list2.length - 1) < (list2Iterator)) {
                    ++list2Iterator;
                } else {
                    ++list1Iterator;
                }
                ++returnArrayIterator;

            }
            /*
            if (comparator.compare(list1[list1Iterator], list2[list2Iterator]) == 1) {
                returnArray[returnArrayIterator] = list2[list2Iterator];
                ++list2Iterator;
                ++returnArrayIterator;
            } else {
                returnArray[returnArrayIterator] = list1[list1Iterator];
                ++list1Iterator;
                ++returnArrayIterator;

            }
            */
        }
        return returnArray;
    }

    public static void main(String[] args) {
        Integer[] list
                = {
                    2, 3, 2, 5, 6, 1, -2, 3, 14, 12
                };
        mergeSort(list);
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
        System.out.println();
        String[] list1
                = {
                    "ABC", "abc", "abm", "Anf", "Good", "Bad", "nice"
                };
        mergeSort(list1, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s1.compareToIgnoreCase(s2);
            }
        });
        for (int i = 0; i < list1.length; i++) {
            System.out.print(list1[i] + " ");
        }
        System.out.println("");
    }
}