/*************************************************************
  *  Code for a circular linked list. Each node of the linked
  *  list is a Card class defined within this class.
  *************************************************************/

public class CircularQuoteSolution {

    // the first card in the circular linked list
    private Card start;

    // helper linked-list data type
    private class Card {
        private String word;
        private Card next;

        public Card(String word) {
            this.word = word;
            this.next = null;
        }
    }

    // create an empty quote
    public CircularQuoteSolution() {
        start = null;
    }

    // add the specified word to the end of the quote
    public void addWord(String word) {
        Card newWord = new Card(word);

        // degenerate case for empty Quote
        if (start == null) {
            start = newWord;
            start.next = start;
        }

        // otherwise
        else {

            // find the current last word
            Card card = start;
            do {
                card = card.next;
            } while (card.next != start);

            // insert new word
            newWord.next = start;
            card.next = newWord;
        }
    }

    // number of words in the quote
    public int count() {

        // empty quote
        if (start == null) return 0;

        Card card = start;
        int total = 0;
        do {
            total++;
            card = card.next;
        } while (card != start);
        return total;
    }

    // the ith word in the quote (where i = 1 is the first word)
    public String getWord(int i) {
        if (i > count() || i <= 0) throw new RuntimeException("index out of bounds");

        Card card = start;
        for (int j = 1; j < i; j++) {
            card = card.next;
        }
        return card.word;
    }

    // insert the specified word after the ith word (where i = 1 is the first word)
    public void insertWord(int i, String word) {
        if (i > count() || i <= 0) throw new RuntimeException("index out of bounds");

        Card newWord = new Card(word);

        // find the ith card
        Card card = start;
        for (int j = 1; j < i; j++) {
            card = card.next;
        }

        // insert between card and card.next
        newWord.next = card.next;
        card.next = newWord;
    }

    // string representation of the entire quote
    public String toString() {
        String s = "";
        if (start == null) return s;

        Card card = start;
        do {
            s = s + card.word + " ";
            card = card.next;
        } while (card != start);
        return s;
    }

    // test client
    public static void main(String[] args) {
        CircularQuoteSolution quote = new CircularQuoteSolution();
        quote.addWord("A");
        quote.addWord("rose");
        quote.addWord("is");
        quote.addWord("a");
        quote.addWord("rose.");
        SdtOut.println(quote);
        StdOut.println(quote.count());
        StdOut.println(quote.getWord(2));
        quote.insertWord(3, "just");
        StdOut.println(quote);
        StdOut.println(quote.count());
    }
}