import java.util.ArrayList;
import java.util.Scanner;

/**
* Sorted Array List
* Now it is Generic!
* 
* @author gtowell
* Created: Oct 8, 2020
* Modified: Oct 8, 2020
* Modified: Oct 18 for Comparable
* Modified: Oct 28, 2021 -- Minor tweaks
*/
public class SAL<E extends Comparable<E>> {
    
    /**
     * The ways in which the sorted Array List might be sorted
     */
    enum Ordering { ASCENDING, DESCENDING }

    /**
     * The sorting direction
     */
    private Ordering theOrder;
    /**
    * The underlying arraylist. 
    */
    private ArrayList<E> sortedAL;
    
    /**
    * Default constructor.
    * Just initialize the array list
    */
    public SAL(Ordering order) {
        theOrder = order;
        sortedAL = new ArrayList<>();
    }

    public int size() {
        return sortedAL.size();
    }

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

    public E getAndRemove(int gett) {
        if (gett>=0 && gett<size()) {
            E tmp = sortedAL.get(gett);
            sortedAL.remove(gett);
            return tmp;
        }
        return null;
    }
    public E get(int index) {
        if (index>=0 && index<size()) {
            return sortedAL.get(index);
        }
        return null;
    }
    
    /**
    * Add a String to the sorted array list
    * @param stringToAdd
    */
    public void add(Comparable<E> stringToAdd) {
        int loc = findPlace(stringToAdd);
        insertAtLoc(stringToAdd, loc);
    }
    
    /**
    * 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(Comparable<E> toAdd) { 
        int place=0;
        while (place<sortedAL.size()) {
            if (theOrder==Ordering.ASCENDING) {
                if (toAdd.compareTo(sortedAL.get(place))<0) {
                    break;
                }
            } else {
                if (toAdd.compareTo(sortedAL.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
    */
    @SuppressWarnings("unchecked")
    private void insertAtLoc(Comparable<E> toAdd, int atLoc) {
        if (sortedAL.size()==0) {
            sortedAL.add((E)toAdd);
            return;
        }
        sortedAL.add(sortedAL.get(sortedAL.size()-1));
        for (int ll=sortedAL.size()-2; ll>=atLoc; ll--) {
            sortedAL.set(ll+1, sortedAL.get(ll));
        }
        sortedAL.set(atLoc, (E)toAdd);
    }
    
    /**
    * Override the default toString method, then use the toString of ArrayList
    */
    public String toString() {
        return sortedAL.toString();
    }
    
    public static void main(String[] args) {
        SAL<String> sal = new SAL<>( Ordering.ASCENDING);
        
        try (Scanner scann = new Scanner(System.in);) {
            System.out.print("Give me a String  -- enter 0 to stop: ");
            String lin = scann.nextLine();
            while (!lin.equals("0")) {
                sal.add(lin);
                System.out.print("Give me a String: ");
                lin = scann.nextLine();
            }
        }
        System.out.println("Q");
        System.out.println(sal);
    }
    
}