Implement these methods:

-int size()

-boolean isEmpty()

-int alphaCounter(char I)

-ArrayList getAlphaList(char I)

-T removeFirst()

-T removeFirstByLetter(char I)

-T removeLast()

-T removeLastByLetter(char I)

--------------------------------------------------------

import ADTs.*; import DataStructures.*; import Exceptions.*; import java.util.ArrayList;

/** * An alphabetic list interface, that takes generic objects which * implement the AlphaKey interface. Users of this list structure * should be able to query/manipulate the list based on objects that start with * a particular letter * @version 18/2/2018 * @author clatulip * @param */ public class AlphaList implements AlphaListADT {

private final int alpha = 26; // num letters in alphabet // helper array, keeps track of how many nodes per letter private int[] alphaCount; private LinearNode first; private LinearNode last; private int numNodes;

/** * Constructor, sets up AlphaList and helper structures */ public AlphaList() { alphaCount = new int[alpha]; first = null; last = null; numNodes = 0; } /** * Adds the specified element to the AlphaList, maintaining the sorted * order of the list. * @param element T element to be added * @throws InvalidArgumentException */ @Override public void add(T element) throws InvalidArgumentException { if (element == null) { throw new InvalidArgumentException("add - element was null"); } String key = element.getKey().toUpperCase(); Character c = key.charAt(0); if (!validChar(c)) { throw new InvalidArgumentException("add - element had invalid key"); } int ascii = getASCII(c); LinearNode temp = new LinearNode(element); //check & handle special case of empty list if (numNodes == 0) { first = temp; last = temp; alphaCount[ascii]++; numNodes++; return; } // scan the list from first to last int scan = 0; LinearNode current = first; LinearNode previous = null; T curElement = current.getElement(); String s = curElement.getKey().toUpperCase(); // iterate through the list, to see where this node goes while (scan < numNodes && s.compareTo(key.toUpperCase()) < 0 && current != null) { previous = current; current = current.getNext(); scan++; if (scan != numNodes && current != null) { curElement = current.getElement(); s = curElement.getKey().toUpperCase(); } } // set the pointers inside our new node temp.setNext(current); temp.setPrev(previous); // now set the pointers in the previous and current nodes if (scan == 0) { // adding before the first node, so update first first.setPrev(temp); first = temp; } else { //Adding to middle or the end previous.setNext(temp);

if (current != null) { // adding to the middle current.setPrev(temp); } else { // adding to the end (current == null) // update the current last node last.setNext(temp); last = temp; } }

alphaCount[ascii]++; numNodes++; } /** * Returns (without removing) an ArrayList of T elements, whose key begins * with the specified letter * @param l char letter * @return ArrayList elements whose key begins with letter * @throws EmptyCollectionException * @throws InvalidArgumentException */ @Override public ArrayList getAlphaList(char l) throws EmptyCollectionException, InvalidArgumentException { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. }

/** * Returns the number of objects in the AlphaList whose key begins with the * specified letter * @param l char letter * @return int num objects beginning with letter * @throws InvalidArgumentException */ @Override public int alphaCount(char l) throws InvalidArgumentException { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.

}

/** * Removes and returns the specified element, if found * @param element T element to look for * @return T element, if found, null otherwise * @throws EmptyCollectionException * @throws InvalidArgumentException */ @Override public T remove(T element) throws EmptyCollectionException, InvalidArgumentException { if (this.isEmpty()) { throw new EmptyCollectionException("remove"); } if (element == null) { throw new InvalidArgumentException("remove - element was null"); } char c = element.getKey().charAt(0); //check that the key is valid if (!validChar(c)) { throw new InvalidArgumentException("remove element " + "had invalid key"); } //if there are no elements that have a key that begins with this letter if (this.alphaCount(c) == 0) { return null; } //if only one element in the list, we can avoid iteration if (this.size() == 1) { //if it's not a match, return null. if (!first.getElement().getKey().equals(element.getKey())) { return null; } return removeFirst(); } //if it's the first element in the list if (first.getElement().equals(element)) { return removeFirst(); } //if it's the last element in the list if (last.getElement().equals(element)) { return removeLast(); } //if not first, last, or only element, we have to find it LinearNode curr = iterateToLetter(c); int term = alphaCount[getASCII(c)]; int count = 0; while (curr != null && count < term) { if (curr.getElement().getKey().equals(element.getKey())) { curr.getPrev().setNext(curr.getNext()); curr.getNext().setPrev(curr.getPrev()); alphaCount[getASCII(c)]--; numNodes--; return curr.getElement(); } curr = curr.getNext(); count++; } //if no matches were found, return null return null; }

/** * Removes and returns the first item in the whole list * @return T element * @throws EmptyCollectionException */ @Override public T removeFirst() throws EmptyCollectionException { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. } /** * Removes and returns the last element in the list whose key begins with * the specified letter * @param l char letter * @return T element * @throws EmptyCollectionException */ @Override public T removeFirstByLetter(char l) throws EmptyCollectionException, InvalidArgumentException { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.

}

/** * Removes and returns the last item in the whole list * @return T element * @throws EmptyCollectionException */ @Override public T removeLast() throws EmptyCollectionException { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.

}

/** * Removes and returns the last item in the list whose key begins with the * specified letter * @param l char letter * @return T element * @throws EmptyCollectionException */ @Override public T removeLastByLetter(char l) throws EmptyCollectionException, InvalidArgumentException { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.

}

/** * Checks if alphaList is empty * @return true if empty, false otherwise */ @Override public boolean isEmpty() { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. }

@Override public int size() { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. }

// NB: this method we will use for testing // do not remove or change /** * For testing, this returns the alphaCount array * @return int[] alphaCount */ public int[] getAlphaCountArray() { return alphaCount; } /** * Converts a char to an index 0 - 25 * @param l * @return */ private int getASCII(char l) { return Character.toUpperCase(l) - 65; } /** * Validation method for passed-in characters * @param c * @return true/false if char is valid */ private boolean validChar(char c) { int a = this.getASCII(c); return (-1 < a && a < 26); } /** * Iterates to a node based on the passed-in char * @param c * @return a LinearNode */ private LinearNode iterateToLetter(char c) { LinearNode current = first; String s = first.getElement().getKey().toUpperCase(); Character thisC = s.charAt(0); Character target = Character.toUpperCase(c);

while (thisC.compareTo(target) != 0 && current != null) { current = current.getNext(); thisC = current.getElement().getKey().charAt(0); } return current; } @Override public String toString() { String s = ""; LinearNode curr = first; while (curr != null) { s += curr.getElement().getKey() + " "; curr = curr.getNext(); } return s; }

}