import java.util.ArrayList;
import java.util.Scanner;
public class SalComp<C extends Comparable<C>> extends ArrayList<C> {
    
    /**
     * Required for serialization
     */
    private static final long serialVersionUID = -7039052157199984372L;


    /**
     * Add a String to the sorted array list
     * @param stringToAdd
     */
    public boolean add(C toAdd) {
        int loc = findPlace(toAdd);
        insertAtLoc(toAdd, loc);
        return true;
    }

    /**
     * Find the place in the arraylist to put the string
     * @param toAdd the string to be added
     * @return the location in which to put the stirng
     */
    private int findPlace(C toAdd) {
        int place=0;
        while (place<size()) {
            // need to cast the result of get to String to allow string comparison
            if (toAdd.compareTo(get(place))<0) {
                break;
            }
            place++;
        }
        return place;
    }

    /**
     * Make a place for the new striong and put it there
     * @param toAdd the string to be added
     * @param atLoc the place to add it
     */
    private void insertAtLoc(C toAdd, int atLoc) {
        if (size()==0) {
            // use the original add function from ArrayList
            super.add(toAdd);
            return;
        }
        // Use the original Add function from arraylist
        super.add(get(size()-1));
        for (int ll=size()-2; ll>=atLoc; ll--) {
            set(ll+1, get(ll));
        }
        set(atLoc, toAdd);
    }

    public void add(String toAdd, int atLoc) {
        System.err.println("Not Supported");
    }

    public static void main(String[] args) {
        SalComp<String> sal = new SalComp<>();
        Scanner scann = new Scanner(System.in);
        System.out.print("Give me a String: ");
        String lin = scann.nextLine();
        while (!lin.equals("0")) {
            sal.add(lin);
            System.out.print("Give me a String: ");
            lin = scann.nextLine();
        }
        System.out.println(sal);
        scann.close();
    }

}