/**
 * An ADT that implements TopTen in Java
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TopTenImpl implements TopTen {

    /*
     * This ADT works by storing the frequency for each
     * sentence in a Map and by keeping track of the
     * frequency of the 10th member of the top 10.
     * Thus, the top 10 is only sorted when the frequency
     * of a sentence meets the value of minFreq.
     */

    /** the size of the top 10: should be 10, but can be changed here */
    protected static final int SIZE = 10;

    /** maps a sentence(String) to its frequency of use (Integer) */
    private Map/*<String,Integer>*/ sentMap = new HashMap();

    /** the current top 10 */
    private List/*<String>*/ topTen = new ArrayList();

    /** the frequency to meet to be in the top 10 */
    private int minFreq = 0;

    /**
     * Records that the sentence has been sent.
     * @param sentence the sentence sent, ignored if null
     */
    public void recordSentenceSent(String sentence) {
	if (sentence == null) return;
	int freq = 1;
	Object val = sentMap.get(sentence);
	if (val != null) freq = ((Integer)val).intValue() + 1;
	sentMap.put(sentence, new Integer(freq));
	// if does not exceed minFreq, then does not belong in top 10
	if (freq < minFreq) return;
	// starts searching at index for placement in top 10
	int index = topTen.indexOf(sentence);
	if (index >= 0) {
	    topTen.remove(sentence);
	} else {
	    index = topTen.size();
	}
	// traverse top 10 until higher freq is found or beginning of list reached
	while (index > 0) {
	    String phraseAhead = (String)topTen.get(index - 1);
	    int otherFreq = ((Integer)sentMap.get(phraseAhead)).intValue();
	    if (freq < otherFreq) break;
	    index--;
	}
	// add sentence at new position in top 10
	topTen.add(index, sentence);
	int ttSize = topTen.size();
	// remove 11th member, if applicable
	if (ttSize > SIZE) {
	    topTen.remove(SIZE);
	    ttSize--;
	}
	// update the minimum frequency required to be in the top 10
	if (ttSize == SIZE) {
	    minFreq = ((Integer)sentMap.get(topTen.get(ttSize - 1))).intValue();
	} else {
	    minFreq = 0;
	}
    }

    /**
     * @returns an array of length 10 with the sentences
     * ordered from most frequent to least frequent
     * If fewer than 10 phrases have been used, the empty
     * spaces in the array are null
     * If two sentences have the same frequency, then the one
     * that was used more recently is listed first.
     */
    public String[] getTopTen() {
	String[] tt = new String[SIZE];
	tt = (String[])topTen.toArray(tt);
	return tt;
    }

    /** returns the non-null members of the top 10 */
    public String toString() {
	return topTen.toString();
    }

    /** used for testing */
    public static void main(String[] argv) {

	// test to make sure frequency rules are preserved
	TopTen t1 = new TopTenImpl();
	String[] strings1 = {
	    "foo", // foo (1)
	    "foo", // foo (2)
	    "foo", // foo (3)
	    "bar", // foo (3), bar (1)
	    "bar", // foo (3), bar (2)
	    "foo", // foo (4), bar (2)
	    "bar", // foo (4), bar (3)
	    "bar", // bar (4), foo (4)
	    "bar", // bar (5), foo (4)
	    "foo"  // foo (5), bar (5)
	};
	TopTenImpl.addAndPrint(strings1, t1);
	
	// test to make sure works past 10 args
	TopTen t2 = new TopTenImpl();
	String[] strings2 = {
	    "one",    // 1
	    "two",    // 2, 1
	    "three",  // 3, 2, 1
	    "four",   // 4, 3, 2, 1
	    "five",   // 5, 4, 3, 2, 1
	    "six",    // 6, 5, 4, 3, 2, 1
	    "seven",  // 7, 6, 5, 4, 3, 2, 1
	    "eight",  // 8, 7, 6, 5, 4, 3, 2, 1
	    "nine",   // 9, 8, 7, 6, 5, 4, 3, 2, 1
	    "ten",    // 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
	    "one",    // 1, 10, 9, 8, 7, 6, 5, 4, 3, 2
	    "two",    // 2, 1, 10, 9, 8, 7, 6, 5, 4, 3
	    "two",    // 2, 1, 10, 9, 8, 7, 6, 5, 4, 3
	    "eleven", // 2, 1, 11, 10, 9, 8, 7, 6, 5, 4
	    "eleven", // 2, 11, 1, 10, 9, 8, 7, 6, 5, 4
	    "eleven"  // 11, 2, 1, 10, 9, 8, 7, 6, 5, 4
	};
	TopTenImpl.addAndPrint(strings2, t2);
    }

    /** adds strings to t and prints intermediate top 10 lists */
    private static void addAndPrint(String[] strings, TopTen t) {
	for (int i = 0; i < strings.length; i++) {
	    t.recordSentenceSent(strings[i]);
	    System.out.println(t.toString());
	}
    }

}