// Philip Peng
// Nov 20, 2007
// For Mr. Benum
//
// The "SortedList" class.
// Subclass of NameList except with sorted insertion.

public class SortedList extends NameList {

    // Constructor for SortedList.
    public SortedList (int maxSize)
    {
    	super (maxSize);      // Call NameList's constructor.
    } // SortedList constructor
	
    // Shift over all items left one space
    protected void shiftRight(int start) {
    	// Starting at slot after last, overwrite each slot with content of slot on left side
    	for (int i = (size-1); i >= start; i--) {
			list[i+1] = list[i];
		}
    }
    
    // Over-riding find method
    // Find occurance of name from a list via binary search
    protected int find (String name) {
    	int low, high, buffer;
    	low = 0;
    	high = size-1;
    	while (high >= low) {
    		buffer = name.compareToIgnoreCase(list[(high+low)/2]); // value of (name - list[#])
    		if (buffer == 0) {
    			//System.out.println("Position: " + (high+low)/2 ); // Debugging
    			return ((high+low)/2);
    		} else if (buffer < 0) { // List item bigger
    			high = ((high+low)/2)-1;
    		} else if (buffer > 0) { // List item smaller
    			low = ((high+low)/2)+1;
    		}
    	}
    	return -1; // If not found
    } // find binary method
    
    // Over-riding insert method
    // Add a name to the list in alphabetic order.
    public void insert (String name)
    {
    	if (name.length()==0) {
    		System.out.println("  Error: No name inputted");
    	} else {
	    	if (size == MAX) {
	    		System.out.println("  Error: NameList is full! Try deleting some names");
	    	} else {
		    	if (find(name) == -1) {
	    			for (int i = 0; i <= size; i++) {
	    				if (i == size) { // Note also works with the first item with size = 0
	    					list[i] = toProperCase(name);
	    					break;
	    				} else if (name.compareToIgnoreCase(list[i]) < 0) { // Comes before
	    					shiftRight(i);
	    					list[i] = toProperCase(name);
	    					break;
	    				}
	    			}
		    		size++;
		    		System.out.println("  Success: Name \"" + toProperCase(name) + "\" inserted");
		    	} else {
		    		System.out.println("  Error: Name \"" + toProperCase(name) + "\" is already on list");
		    	}
	    	}
    	}
    } // over-riding insert method
    
} // SortedList class
