import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import javax.swing.JOptionPane;

public class RecursionExample {

    //<T> means that T is a type parameter to the method
    static <T> boolean contains(List<T> list, T item) {
        return contains(list, list.size() - 1, item);
    } // end contains
    
    // does the ArrayList<T> a contain item between 0 and rightIndex
    static <T> boolean contains(List<T> list, int rightIndex, T item) {
        // if there are no elements between o and rightIndex retuen false
        if (rightIndex < 0) {
            return false;
        }
        // if item equals a.get(rightIndex) we found itmw so return true
        if (item.equals(list.get(rightIndex))) {
            return true;
        }
        // since the recursivecall solves the smaller problem
        return contains(list, rightIndex - 1, item);
    } // end contains

    static <T> boolean listContains(List<T> list, T item) {
        if( list.size() == 0 ) return false;
        if( list.get(0).equals(item) ) return true;
        return listContains(list.subList(1,list.size()), item);
    }
    
    static <T extends Comparable<T>>   void bubbleSort(List<T> a) {
        bubbleSort(a, a.size() - 1);
    } // end bubbleSort

    // sort the Arraylist<T> for any type T that extends Comparable between 0 and rightIndex
    static <T extends Comparable<T>>   void bubbleSort(List<T> a, int rightIndex) {
        // if only one item between 0 and rightIndex do nothing
        if (rightIndex <= 0) {
            return;
        }
        // move the largest item in the ArrayList to the position rightIndex
        for (int i = 0; i < rightIndex; i++) {
            if (a.get(i).compareTo(a.get(i + 1)) > 0) {
                T save = a.get(i);
                a.set(i, a.get(i + 1));
                a.set(i + 1, save);
            }// end if
        } // end for
        // since the largest element is at rightIndex
        // and the recursive call sorts the rest we are done
        bubbleSort(a, rightIndex - 1);
    } // end bubbleSort

    static <T extends Comparable<T>>  void listBubbleSort(List<T> list) {
        if (list.size() == 1) {
            return;
        }
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i).compareTo(list.get(i + 1)) > 0) {
                T save = list.get(i);
                list.set(i, list.get(i + 1));
                list.set(i + 1, save);
            }// end if
        } // end for
        listBubbleSort(list.subList(0, list.size() - 1));
    }// end listBubbleSort

    static <T extends Comparable<T>>  void listInsertionSort(List<T> list) {
        if (list.size() == 1) {
            return;
        }
        // sort all but the last element
        listInsertionSort(list.subList(0, list.size() - 1));
        // insert the last element into it's sorted position
        T hold = list.get(list.size() - 1);
        int i = list.size() - 2;
        // move elements up 1 in the list intil sorted position is found
        while (i >= 0 && hold.compareTo(list.get(i)) < 0) {
            list.set(i + 1, list.get(i));
            i--;
        } // while
        // insert hold into sorted position
        list.set(i + 1, hold);
    }// end listInsertionSort

    static <T extends Comparable<T>>   T maxValue(List<T> a) {
        return maxValue(a, a.size() - 1);
    } // maxValue

    static <T extends Comparable<T>>   T maxValue(List<T> a, int rightIndex) {
        if (rightIndex == 0) {
            return a.get(0);
        }
        T maxValue = maxValue(a, rightIndex - 1);
        if (maxValue.compareTo(a.get(rightIndex)) < 0) {
            maxValue = a.get(rightIndex);
        }
        return maxValue;
    } // maxValue

    static <T extends Comparable<T>>  void listMergeSort(List<T> list) {
        if (list.size() == 1) {
            return;
        }
        int middle = list.size() / 2;
        // Sort the left half
        listMergeSort(list.subList(0, middle));
        // Sort the right half
        listMergeSort(list.subList(middle, list.size()));
        // Merge the two halves
        List<T> merge = new ArrayList<>();
        int i = 0;
        int j = middle;
        while (i < middle && j < list.size()) {
            if (list.get(i).compareTo(list.get(j)) <= 0) {
                merge.add(list.get(i));
                i++;
            } else {
                merge.add(list.get(j));
                j++;
            }// end if
        } // end for
        while( i < middle ) {
                merge.add(list.get(i));
                i++;
        }// end while
        while( j < list.size() ) {
                merge.add(list.get(j));
                j++;
        }// end while
        // Copy back to origional list
        for( int k = 0; k < list.size(); k++ ) list.set(k,merge.get(k));
    }// end listMergeSort

    public static void main(String[] args) {
        List<String> words = new ArrayList<>();
        words.add("one");
        words.add("two");
        words.add("three");
        words.add("four");
        words.add("five");
        words.add("six");
        words.add("seven");
        List<String> wordsList = new ArrayList<>(words);
        String output = words + "\n" + "Max Value is " + maxValue(words) + "\n";
        output += "wordsList is " + wordsList + "\n";
        output += "three found " + contains(words, "three") + "\n";
        output += "one found  " + contains(words, "one") + "\n";
        output += "eight found " + listContains(words, "eight") + "\n";
        bubbleSort(words);
        listMergeSort(wordsList);
        output += "After sorting words:  " + words + "\n";
        output += "After sorting wordsList:  " + wordsList + "\n";
        JOptionPane.showMessageDialog(null, output, "Output", JOptionPane.PLAIN_MESSAGE);
        ArrayList<Integer> numbers = new ArrayList<>();
        numbers.add(4);
        numbers.add(5);
        numbers.add(6);
        numbers.add(7);
        numbers.add(1);
        numbers.add(37);
        numbers.add(3);
        numbers.add(0);
        ArrayList<Integer> numbersList = new ArrayList<>(numbers);
        output = numbers + "\n" + "Max Value is " + maxValue(numbers) + "\n";
        output += "numbersList is " + numbers + "\n";
        output += "3 found " + contains(numbers, 3) + "\n";
        output += "1 found " + contains(numbers, 1) + "\n";
        output += "8 found " + listContains(numbers, 8) + "\n";
        listInsertionSort(numbers);
        listMergeSort(numbersList);
        output += "After sorting numbers:  " + numbers + "\n";
        output += "After sorting numbersList:  " + numbersList + "\n";
        JOptionPane.showMessageDialog(null, output, "Output", JOptionPane.PLAIN_MESSAGE);
        Random random = new Random();
        int max = 1000000;
        for( int i = 0; i < max; i++ ) numbers.add(random.nextInt(1000000));
        listMergeSort(numbers);
        boolean sorted = true;
        for( int i = 0; i < max; i++ ) if( numbers.get(i) > numbers.get(i+1) ) sorted = false;
        JOptionPane.showMessageDialog(null,"Sorted? " + sorted);
    } // end main
}