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

public class RecursionExampleWithSubList {
    
    <T> boolean contains(List<T> a, T item) {
        if( a.size() == 0 ) return false;
        if( item.equals(a.get(a.size()-1)) ) return true;
        return contains(a.subList(0,a.size()-1),item);
    } // end contains
    
    <T extends Comparable<T>> void bubbleSort(List<T> a) {
        if( a.size() == 1 ) return;
        for(int i = 0; i < a.size()-1; 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
        bubbleSort(a.subList(0,a.size()-1));
    } // end bubbleSort
    
    <T extends Comparable<T>> boolean binarySearch(List<T> a,T item) {
        if( a.size() == 0 ) return false;
        int middle = a.size()/2;
        if( item.equals(a.get(middle)) ) return true;
        if( item.compareTo(a.get(middle)) < 0 ) return binarySearch(a.subList(0,middle),item);
        return binarySearch(a.subList(middle+1,a.size()),item);
    } // end binarySearch
    
    <T extends Comparable<T>> T maxValue(List<T> a) {
        if( a.size() == 1 ) return a.get(0);
        T max = maxValue(a.subList(0,a.size()-1));
        if( max.compareTo(a.get(a.size()-1)) < 0 ) return a.get(a.size()-1);
        return max;
    } // maxValue
    
    public RecursionExampleWithSubList() {
        ArrayList<String> words = new ArrayList<String>();
        words.add("one");
        words.add("two");
        words.add("three");
        words.add("four");
        words.add("five");
        words.add("six");
        words.add("seven");
        String output = words + "\n"  + "Max Value is " + maxValue(words) + "\n";
        output += "three found " + contains(words,"three") + "\n";
        output += "one found  " + contains(words,"one") + "\n";
        output += "eight  " + contains(words,"eight") + "\n";
        bubbleSort(words);
        output += "After sorting:  " + words + "\n";
        output += "three found " + binarySearch(words,"three") + "\n";
        JOptionPane.showMessageDialog(null,output,"Output",JOptionPane.PLAIN_MESSAGE);
        ArrayList<Integer> numbers = new ArrayList<Integer>();
        numbers.add(new Integer(4));
        numbers.add(new Integer(5));
        numbers.add(new Integer(6));
        numbers.add(new Integer(7));
        numbers.add(new Integer(1));
        numbers.add(new Integer(37));
        numbers.add(new Integer(3));
        output = numbers + "\n" + "Max Value is " + maxValue(numbers) + "\n";
        output += "3 found " + contains(numbers,new Integer(3)) + "\n";
        output += "1 found " + contains(numbers,new Integer(1)) + "\n";
        output += "8 found " + contains(numbers,new Integer(8)) + "\n";
        bubbleSort(numbers);
        output += "After sorting:  " + numbers + "\n";
        output += "37 found " + binarySearch(numbers,new Integer(37)) + "\n";
        JOptionPane.showMessageDialog(null,output,"Output",JOptionPane.PLAIN_MESSAGE);
    } // end RecursionExample
    
    public static void main(String[] args) {
        new RecursionExampleWithSubList();
        System.exit(0);
    } // end main
    
}