import java.awt.Color;

public class AL {
	private Comparable [] elements;
	private int size = 0;
	
	public AL(){
		elements = new Comparable[2];
	}
	
	public AL(int initialCapacity){
		elements = new Comparable[initialCapacity];
	}
	
	public int getSize(){
		return size;
	}
	
	public void add(Comparable element){
		if(size > elements.length * 2 / 3)
			enlarge();
		
		elements[size++] = element;
	}
	
	public void add(Comparable element, int index){
		if(index > size)
			add(element);
		
		elements[index] = element;
	}
	
	public Comparable getElement(int index){
		return elements[index];
	}
	
	public Comparable remove(int index){
		Comparable c = elements[index];
		shiftRemove(index);
		return c;
	}
	
	public void shiftRemove(int start) {
		int index;
	    for (index = start; index < size; index++) {
	      elements[index] = elements[index + 1];
	    }
	    size--;
	}
	
	public int search(Comparable element){
	
		for(int i=0; i<size; i++){
			if(getElement(i).compareTo(element) == 0)
				return i;
		}
		return -1;
	}
	
	public void enlarge(){
		Comparable [] c = new Comparable[elements.length * 2];
		for(int i=0; i< size; i++){
			c[i] = elements[i];
		}
		elements = c;
	}
	
	public void compress(){
		Comparable [] c = new Comparable[size];
		for(int i=0; i< size; i++){
			c[i] = elements[i];
		}
		elements = c;
	}
	
	
	// using methods instead of reaching the array elements directly to provide 
	// a generalized algorithm
	public void selectionSortIterative() {
	
	  for (int i = 0; i < size - 1; i++) {
	    swap(i, findMinimumIterative(i));
	  }
	}
	  
	public int findMinimumIterative(int start) {
		int i, currentMin = start;
	
	  	for (i = start + 1; i < size; i++) {
		  if (this.getElement(i).compareTo(getElement(currentMin)) < 0) {
	    	currentMin = i;
	    	}
	  	}
	  	return currentMin;
	}
	  
	public void swap(int index1, int index2) {
	  	Comparable temp = getElement(index1);
	    add(getElement(index2), index1);
	    add(temp, index2);
	  }
	
	public int binarySearch(Comparable element){
		int start = 0, end = size-1;
		int mid = (start+end) / 2;
		while(start < end){
			if(getElement(mid).compareTo(element) == 0)
				return mid;
			else if (getElement(mid).compareTo(element) < 0){
				start = mid+1;
				mid = (start+end) / 2;
			}
			else{
				end = mid - 1;
				mid = (start+end) / 2;
			}
		}
		
		return -1;
	}
	
	public String toString(){
		String s = "The size of this AL is "+size + "\nThe elements are: \n";
		for(int i = 0; i<size; i++){
			s+= getElement(i).toString();
		}
		return s;
	}
	
	public static void main(String[] args) {
		AL al = new AL();
		al.add(new Shirt(Color.RED, 12));
		al.add(new Shirt(Color.BLUE, 12));
		al.add(new Shirt(Color.WHITE, 14));
		al.add(new Shirt(Color.YELLOW, 10));
		al.add(new Shirt(Color.BLACK, 13));
		System.out.println(al.toString());
		al.selectionSortIterative();
		System.out.println(al.toString());
		System.out.println(al.binarySearch(new Shirt(Color.BLACK, 15)));
		System.out.println(al.binarySearch(new Shirt(Color.BLACK, 13)));
	}
}