/*
http://www.cs.wisc.edu/~solomon/cs537/java-tutorial.html#arrays
*/
import java.util.*;

public class ListTest {
	void printList(List lis) {
		for(Iterator i = lis.iterator(); i.hasNext(); ) {
			int n = ((Integer) i.next()).intValue();
			System.out.print(n+" ");
		}
		System.out.println();
	}
	
	int count(List lis) {
		if (lis.isEmpty())  // or lis.size() == 0
			return 0;
		else return 1 + count(lis.subList(1, lis.size()));
	}
	
	List reverse(List lis) {
		if (lis.isEmpty()) return lis;
		else {
			Integer first = (Integer) lis.get(0);
			List temp = new ArrayList();
			temp.addAll(reverse(lis.subList(1,lis.size())));
			//makes a copy of reveresed list,
			//temp = reverse... affects lis
			temp.add(temp.size(), first);
			return temp;
		}
	}
	
	int smallest(List lis, int small) {
		if (lis.isEmpty()) return small;
		else if (((Integer) lis.get(0)).intValue() < small) 
			return smallest(lis.subList(1,lis.size()),
				((Integer) lis.get(0)).intValue());
		else return smallest(lis.subList(1,lis.size()), small);
	}
	
	List remove(List lis, int item) {
		if (lis.isEmpty()) return lis;
		else if (((Integer) lis.get(0)).intValue() == item)
			return lis.subList(1,lis.size());
		else {
			Integer first = (Integer) lis.get(0);
			List temp = new ArrayList();
			temp.addAll(remove(lis.subList(1,lis.size()),item));
			temp.add(0,first);
			return temp;
		}
	}
	
	List selectionsort(List lis) {
		if (lis.isEmpty()) return lis;
		else {
			Integer first = (Integer) lis.get(0);
			int s = smallest(lis.subList(1,lis.size()), first.intValue());
			List sorted = new ArrayList();
			List removeList = new ArrayList();
			removeList.addAll(remove(lis,s));
			sorted.addAll(selectionsort(removeList));
			sorted.add(0, new Integer(s));
			return sorted;
		}
	}
	
	List insert(int element, List lis) {
		if (lis.isEmpty()) {
			lis.add(0, new Integer(element));
			return lis;
		} else if (element > ((Integer) lis.get(0)).intValue()) {
			Integer first = (Integer) lis.get(0);
			List restList = new ArrayList();
			restList.addAll(insert(element, lis.subList(1,lis.size())));
			restList.add(0, first);
			return restList;
		} else {
			lis.add(0, new Integer(element));
			return  lis;
		}
	}
	
	List insertionsort(List lis) {
		if (lis.isEmpty()) return lis;
		else {
			List sorted = new ArrayList();
			sorted.addAll(insertionsort(lis.subList(1,lis.size())));
			return insert(((Integer) lis.get(0)).intValue(), sorted);
		}
	}
			
			
	
	List append(List lis, List m) {
		if (lis.isEmpty()) return m;
		else {
			Integer first = (Integer) lis.get(0);
			List temp = new ArrayList();
			temp.addAll(append(lis.subList(1,lis.size()), m));
			temp.add(0, first);
			return temp;
		}
	}
	
	boolean member(int atm, List lis) {
		if (lis.isEmpty()) return false;
		else if ( ((Integer) lis.get(0)).intValue() == atm)
			return true;
		else
			return member(atm, lis.subList(1, lis.size()));
	}
	
	int gcd(int num1, int num2) {
		if (num2 == 0) return num1;
		else 
			return gcd(num2, num1 % num2);
	}
	
	public static void main(String args[]) {
		int[] nums =new int[]{3,5,2,18,19,1,4};
		Integer nums2[] = {new Integer(3), new Integer(5), 
			new Integer(2), new Integer(18), new Integer(19),
			new Integer(1), new Integer(4)};
		Integer nums3[] = {new Integer(5), new Integer(3)};
		List list = new ArrayList();     // an empty list
		List list2 = new ArrayList(Arrays.asList(nums2));
		List list3 = new ArrayList(Arrays.asList(nums3));
		ListTest test = new ListTest();
		for (int i = 0; i < 100; i++) {
			list.add(new Integer(i));
		}
    // now it contains 100 Integer objects

    // print their squares
	        for (int i = 0; i < 100; i++) {
			Integer member = (Integer) list.get(i);
			int n = member.intValue();
			System.out.println(n*n);
		}

    // another way to do that
    for (Iterator i = list.iterator(); i.hasNext(); ) {
        int n = ((Integer) i.next()).intValue();
        System.out.println(n*n);
    }
		System.out.print("Array: ");
	        test.printList(list2);
	        System.out.println("Number of elements= " + test.count(list2) +
					    " = " + list2.size());
		System.out.print("Reversed array: ");
		test.printList(test.reverse(list2));
		System.out.print("Array: ");
		test.printList(list2);	    
		System.out.println("gcd(28,124)=" + test.gcd(28,124));
		System.out.println("5 in Array? " + test.member(5,list2));	
		System.out.println("15 in Array? " + test.member(15,list2));
		System.out.print("Array appended to itself: ");
		test.printList(test.append(list2,list2));
		System.out.print("Array: ");
		test.printList(list2);
		System.out.print("Array sorted: ");
		//System.out.println(test.remove(list2,18));
		System.out.println(test.insertionsort(list2));
		System.out.print("Array: " + list2);
    
    list.set(5, "hello");        // like list[5] = "hello"
    Object o = list.get(3);      // like o = list[3];
    list.add(6, "world");        // set list[6] = "world" after first shifting
                                 // element list[7], list[8], ... to the right
                                 // to make room
    list.remove(3);              // remove list[3] and shift list[4], ... to the
                                 // left to fill in the gap

   //Elements of a List must be objects, not values. That means you can put a String or an instance of a user-defined class into a Vector, but if you want to put an integer, floating-point number, or character into List, you have to wrap it:


    //list.add(47);                   // WRONG!
    //sum += list.get(i);             // WRONG!
    list.add(new Integer(47));      // right
    //int sum = 0;
    //sum += ((Integer) list.get(i)).intValue();
                                    // ugly, but right
    }
}