WordList

/**
 * Doubly linked list of WordsEntry objects that is kept sorted by
 * either frequency or alphabetically.
 *
 * @author ■. ■■■■■■■
 * Last Modified: 19/4/17
 */
import java.util.Iterator;
import java.util.NoSuchElementException;

public class WordList implements Iterable<WordEntry> {

    /** Size of the list */
    private int size;

    /** If it is currently sorted by frequency */
    private boolean isFrequencySorted;

    private WNode head;
    private WNode tail;

    /**
     * Construct an empty LinkedList of WordEntry objects
     * @param isFrequencySorted If the list should be kept sorted by frequency
     *        (true) or alphabetically (false).
     */
    public WordList(boolean isFrequencySorted) {
        this.isFrequencySorted = isFrequencySorted;

        head = new WNode(null, null, null);
        tail = new WNode(null, head, null);
        head.next = tail;

        size = 0;
    }

    /**
     * Returns a String representation of the list's sorting order.
     * @return "freq" if sorted by frequency, "alpha" otherwise
     */
    public String getSortType() {
        return isFrequencySorted ? "freq":"alpha";
    }

    /**
     * Returns the number of items in this collection.
     * @return the number of items in this collection.
     */
    public int size() {
        return size;
    }

    /**
     * Add the String to the list
     * Creates a new WordEntry for it if it is not already in the list,
     * otherwise it increments the counter associated with the word.
     *
     * @param str String to add to the list
     */
    public void addWord(String str) {
        WordEntry newWordEntry = new WordEntry(str);
        boolean alreadyExists = false;
        WNode curNode = head.next;
        if (!isFrequencySorted){
            while(curNode != tail && newWordEntry.compareByWord(curNode.entry) >= 0){
                /* Make sure that the curNode is not the tail
                 * This loop also only advances if the newWordEntry object belongs on
                 * the right side of the curNode.
                 */
                if (newWordEntry.compareByWord(curNode.entry) == 0){
                    /* Checks to see whether or not the newWordEntry word(str) is equal
                     * to the curNode word. If they are equal it increments the count
                     * on the already existing WordEntry.
                     */
                    curNode.entry.setCount(curNode.entry.getCount() + 1);
                    alreadyExists = true;
                }
                curNode = curNode.next;
            }
            if(!alreadyExists){
                /* If the newWordEntry hasn't updated the count on an existing word
                 * the addBefore method is used to create a WNode and link it into
                 * the WordList at the curNode position.
                 */
                addBefore(curNode, newWordEntry);
            }
        }else if (isFrequencySorted){
            WNode addOrUpdate = null;
            while(curNode != tail && newWordEntry.compareByWord(curNode.entry) != 0){
                /* Changes the position in the WordList until curNode is equal to the tail
                 * OR until the loop finds an equivalent WordEntry already existing in the list.
                 */
                curNode = curNode.next;
            }
            if (curNode != tail && newWordEntry.equals(curNode.entry)){
                /* If the curNode is not equal to the tail then it must mean newWordEntry
                 * is equal to curNode.entry (there is a safety check)
                 * This then updates the count and stores the WNode position in order
                 * to bubble the WNode up or down the list to the correct frequency position.
                 */
                curNode.entry.setCount(curNode.entry.getCount() + 1);
                alreadyExists = true;
                addOrUpdate = curNode;
            }else {
                //curNode is equal to the tail so this creates a new WNode and adds to list
                addBefore(tail, newWordEntry);
                addOrUpdate = tail.prev;
            }
            while(addOrUpdate.prev != head &&
                    addOrUpdate.entry.compareByFrequency(addOrUpdate.prev.entry) < 0){
                //Loop to bubble up or down the WNode of the addOrUpdate WNode to the correct
                //Position in the WordList
                swap(addOrUpdate.prev, addOrUpdate);
            }
        }

    }

    /**addBefore takes a WNode for position in WordList
     * creates a new WNode containing the WordEntry
     * updates the next and prev references for this new WNode
     *
     * @param pos WNode for the WordEntry to be added before
     * @param w WordEntry to convert to new WNode
     */
    private void addBefore(WNode pos, WordEntry w) {
        WNode newNode = new WNode(w, pos.prev, pos);
        newNode.prev.next = newNode;
        pos.prev = newNode;
        size++;
    }

    /**
     * Swap two nodes in the list
     *
     * @param left Left node
     * @param right Right node
     */
    private void swap(WNode left, WNode right) {
        left.prev.next = right;
        right.prev = left.prev;
        left.next = right.next;
        right.next.prev = left;
        right.next = left;
        left.prev = right;
    }

    /**
     * Search for the word specified
     *
     * @param str String to find
     * @return The word entry found, or null if nothing is found
     */
    public WordEntry find(String str) {
        WNode pos = head.next;
        while (pos != tail) {
            //if (pos.data == element) {
            if (pos.entry.getWord().toLowerCase().equals(str)) {
                return pos.entry;
            }
            pos = pos.next;
        }
        return null;
    }


    /**
     * Find all entries that start with the specified letter.
     *
     * @param c Letter to find
     * @return List of words starting with the specified letter
     */
    public WordList findWordsStartingWith(char c) {
        WNode curNode = head.next;
        WordList wordsWith = new WordList(this.isFrequencySorted);
        while (curNode != tail){
            if(curNode.entry.getWord().charAt(0) == c){
                wordsWith.addBefore(wordsWith.tail, curNode.entry);
            }
            curNode = curNode.next;
        }
        return wordsWith;
    }

    /**addFrequency adds a WordEntry object inserted into a WordList
     * in a frequency sorted insertion
     *
     * Works only with fully counted WordEntry objects
     *
     * @param w WordEntry
     */
    private void addFrequency(WordEntry w){
        WNode curNode = head.next;
        while (curNode != tail && w.compareByFrequency(curNode.entry) > 0){
            curNode = curNode.next;
        }
        addBefore(curNode, w);
    }

    /**addAlphabetical adds a WordEntry object inserted into a WordList
     * in an alphabetically sorted insertion
     *
     * Works only with fully counted WordEntry objects
     *
     * @param w WordEntry
     */
    private void addAlphabetical(WordEntry w){
        WNode curNode = head.next;
        while(curNode != tail && w.compareByWord(curNode.entry) >= 0){
            curNode = curNode.next;
        }
        addBefore(curNode, w);
    }

    /**
     * Find all entries with a given frequency
     *
     * @param freq Frequency to find
     * @return List of matching words
     */
    public WordList findWordsAtFrequency(int freq) {
        if (isFrequencySorted){
            WNode curNode = head.next;
            WordList wordsWith = new WordList(this.isFrequencySorted);
            while (curNode.entry.getCount() >= freq){
                if(curNode.entry.getCount() == freq){
                    wordsWith.addBefore(wordsWith.tail, curNode.entry);
                }
                curNode = curNode.next;
            }
            return wordsWith;
        }else {
            WNode curNode = head.next;
            WordList wordsWith = new WordList(this.isFrequencySorted);
            while (curNode != tail){
                if(curNode.entry.getCount() == freq){
                    wordsWith.addBefore(wordsWith.tail, curNode.entry);
                }
                curNode = curNode.next;
            }
            return wordsWith;
        }
    }

    /**
     * Get the first N most frequently occurring words
     *
     * @param n Number of words
     * @return List of most frequent words
     */
    public WordList getMostFrequentlyUsed(int n) {
        if (isFrequencySorted){//WordList is sorted by Frequency
            WNode curNode = head.next;
            int count = 0;
            WordList wordsWith = new WordList(this.isFrequencySorted);
            while (count < n){
                /* Find the n Most Frequent words in list since it is frequency sorted
                 * We can take the first n items from our list
                 */
                wordsWith.addBefore(wordsWith.tail, curNode.entry);

                curNode = curNode.next;
                count++;
            }
            return wordsWith;
        }else {//WordList is sorted alphabetically
            WordList toFreq = new WordList(this.isFrequencySorted);
            WNode curNode = head.next;
            while (curNode != tail){
                //Loop converts alphabetically sorted list to frequency sorted
                toFreq.addFrequency(curNode.entry);
                curNode = curNode.next;
            }
            curNode = toFreq.head.next;
            int count = 0;
            WordList nMostFreq = new WordList(this.isFrequencySorted);
            while (count < n){
                /* Find the n Most Frequent words in list since it is frequency sorted
                 * We can take the first n items from our list
                 */
                nMostFreq.addBefore(nMostFreq.tail, curNode.entry);

                curNode = curNode.next;
                count++;
            }
            WordList backToAlpha = new WordList(this.isFrequencySorted);
            curNode = nMostFreq.head.next;
            while (curNode != nMostFreq.tail){
                /* Loop converts frequency sorted list of n Most Frequent back to
                 * an Alphabetically sorted WordList
                 */
                backToAlpha.addAlphabetical(curNode.entry);
                curNode = curNode.next;
            }
            return backToAlpha;
        }
    }

    /**
     * Get the N least frequently occurring words
     *
     * @param n Number of words
     * @return List of least frequent words
     */
    public WordList getLeastFrequentlyUsed(int n) {
        if (isFrequencySorted){//Word list is sorted by frequency
            WNode curNode = tail.prev;
            int count = 0;
            WordList wordsWith = new WordList(this.isFrequencySorted);
            while (count < n){
                wordsWith.addBefore(wordsWith.head.next, curNode.entry);
                curNode = curNode.prev;
                count++;
            }
            return wordsWith;
        }else {//WordList is sorted alphabetically
            WordList toFreq = new WordList(this.isFrequencySorted);
            WNode curNode = head.next;
            while (curNode != tail){
                //Loop converts alphabetically sorted list to frequency sorted
                toFreq.addFrequency(curNode.entry);
                curNode = curNode.next;
            }
            curNode = toFreq.tail.prev;
            int count = 0;
            WordList nLeastFreq = new WordList(this.isFrequencySorted);
            while (count < n){
                /* Find the n Least Frequent words in list since it is frequency sorted
                 * We can take the first n items from our list
                 */
                nLeastFreq.addBefore(nLeastFreq.tail, curNode.entry);
                curNode = curNode.prev;
                count++;
            }
            WordList backToAlpha = new WordList(this.isFrequencySorted);
            curNode = nLeastFreq.head.next;
            while (curNode != nLeastFreq.tail){
                /* Loop converts frequency sorted list of n Least Frequent back to
                 * an Alphabetically sorted WordList
                 */
                backToAlpha.addAlphabetical(curNode.entry);
                curNode = curNode.next;
            }
            return backToAlpha;
        }
    }

    /**
     * Overrides object version so that this list can be printed.
     */
    public String toString() {
        if (head.next == tail) {
            return "()";
        }

        String listContents = "(\n";
        WNode pos = head.next;
        while (pos.next != tail) {
            listContents += "    " + pos.entry.toString() + "\n";
            pos = pos.next;
        }
        // make sure that last thing in list gets added
        // without a comma after it's occurrence
        listContents += "    " + pos.entry;
        return listContents + "\n)";
    }

    /**
     * Method to allow outside classes to have access to list elements one by
     * one for things like looping, by giving them an iterator that they can
     * advance one element at a time.
     *
     * @see java.lang.Iterable#iterator()
     * @return An iterator over this list.
     */
    public Iterator<WordEntry> iterator() {
        return new WIterator();
    }

    /**
     * This is the list iterator.
     */
    private class WIterator implements Iterator<WordEntry> {

        private WNode pos;

        public WIterator(){
            pos = head;
        }

        /**
         * @return true if the iterator has more content, false otherwise
         */
        public boolean hasNext() {
            return (pos.next != tail);
        }

        /**
         * @return the next entry in the list
         * @throws NoSuchElementException if no entries remain
         */
        public WordEntry next() {
            if (!hasNext()){
                throw new NoSuchElementException("Nothing left");
            }
            pos = pos.next;
            return pos.entry;
        }
    }

    /**
     * This is the doubly-linked list node.
     */
    private class WNode {
        WordEntry entry;
        WNode prev;
        WNode next;

        public WNode(WordEntry entry, WNode prev, WNode next){
            this.entry = entry;
            this.prev = prev;
            this.next = next;
        }
    }

}