// Search Structure implemented using sorted arrays
// Only Comparable objects can be put in data structure.
// search method is binary search: O(log(n))
// insertion and deletion take O(n) time

import java.util.Arrays;

class SortedArray implements SearchStructure {

    private Comparable[] a;
    private int size;    // max size of array
    private int cursor;  // position to insert element
    private int count;   // current count of elements

    public SortedArray(int n) {
	a = new Comparable[n];
	size = a.length;
    }

    public Comparable get(int index) {
	return a[index];
    }
    
    public int size() {
	return size;
    }

    public boolean isEmpty() {
	return (size == 0);
    }

    public boolean isFull() {
	return (count>size);
    }

    public void sort() {
	Arrays.sort(a);
    }

    // Binary search on array sorted in increasing order
    // Takes O(log(n)) time for an array of size n:
    public boolean search(Object key) {
	int left = 0;
	int right = count - 1;
	int middle = 0; // initialization needed for empty array case

	while (left <= right) {
	    middle = (left + right)/2;
	    int test = a[middle].compareTo(key);
	    if (test < 0)
		left = middle+1;
	    else if (test > 0)
		right = middle-1;
	    else {
		cursor = middle;
		return true;
	    }

	}
	// If we reach here, we didn't find key:
	cursor = right + 1; // first position to enter new elem
	return false;
    }
    
    // Insert in first empty (null) position
    // Make array bigger by 1 elem if necessary
    // Takes O(n) time because of copying of array:
    public void insert(Object key) {

	// Set the cursor using search:
	search(key);

	// Increment count for additional element:
	int oldcount = count;
	count++;

	// If nec, make new array to hold added elem:
	if (this.isFull()) {
	    Comparable[] aNew = new Comparable[count];
	    System.arraycopy(a,0,aNew,0,size);
	    a = aNew;
	    size = a.length;
	}

	// Shift right all items to right of insertion index
	// Use oldcount...why? cursor is the next free location
	// which might be the end of the array or 1 elem beyond the
	// *original* end:
	for (int i = oldcount-1; i >= cursor; i--)
	    a[i+1] = a[i];

	// Insert item:
	a[cursor] = (Comparable) key;
    }


    // Find all occurrences and delete them
    // Although it's heavy on linear search, it still has O(n) time
    // The cost is non-constant space:
    public void  delete(Object key) {

	// Count how many keys to delete:
	int same=0;
	for (int i = 0; i< size; i++)
	    if (a[i].equals(key)) same++;

	// Rebuild array without keys:
	if (same > 0) {
	    int oldsize = size;
	    size = size - same;
	    Comparable[] aNew = new Comparable[size];
	    int newindex = 0;
	    for (int i = 0; i < oldsize;i++) {
		if (!a[i].equals(key))
		    aNew[newindex]=a[i];
		newindex++;
	    }
	}

    }

    // Description of sorted array
    // Use List's toString as a crutch:
    public String toString() {
	return Arrays.asList(a).toString();
    }

}


public class TestSortedArray {
    public static void main(String[] args) {
	SortedArray sa = new SortedArray(Integer.parseInt(args[0]));
	System.out.println(sa);
	sa.insert("A");
	System.out.println(sa);
	sa.insert("B");
	System.out.println(sa);
	sa.insert("B");
	System.out.println(sa);
	sa.insert("D");
	System.out.println(sa);
	sa.insert("A");
	System.out.println(sa);
	sa.insert("C");
	System.out.println(sa);
	System.out.println("SA size: " + sa.size());
    }
}