import static org.junit.Assert.*;

    import java.util.ArrayList;
    import java.util.HashSet;

    import org.junit.Test;

    public class TestTrie {

    	Term[] terms =
    			new Term[] {new Term("ape", 6),
    			new Term("app", 4),
    			new Term("ban", 2),
    			new Term("bat", 3),
    			new Term("bee", 5),
    			new Term("car", 7),
    			new Term("cat", 1)};
    	String[] names= {"ape", "app", "ban", "bat", "bee", "car", "cat"};
    	double[] weights = {6, 4, 2, 3, 5, 7, 1};

    	public Autocompletor getInstance(){
    		return getInstance(names, weights);
    	}

    	public Autocompletor getInstance(String[] names, double[] weights){
    		return new TrieAutocomplete(names, weights);
    	}

    	public class Autoincompletor extends TrieAutocomplete{

    		public Autoincompletor(String[] terms, double[] weights) {
    			super(terms, weights);
    		}

    		@Override
    		public String[] topKMatches(String prefix, int k){
    			return new String[0];
    		}

    	}

    	public ArrayList<ArrayList<Term>> allPermutes(ArrayList<Term> arr){
    		if (arr.size() == 1){
    			ArrayList<ArrayList<Term>> output = new
    					ArrayList<ArrayList<Term>>();
    			output.add(arr);
    			return output;
    		}
    		ArrayList<ArrayList<Term>> output =
    				new ArrayList<ArrayList<Term>>();
    		for(int i = 0; i < arr.size(); i++){
    			ArrayList<Term> arrcopy = new ArrayList<Term>(arr);
    			arrcopy.remove(i);
    			ArrayList<ArrayList<Term>> subPermutes = allPermutes(arrcopy);
    			for(ArrayList<Term> permute: subPermutes)
    				permute.add(arr.get(i));
    			output.addAll(subPermutes);
    		}
    		return output;
    	}


    	/**Tests correctness of topMatch() for a few simple cases
    	 */
    	@Test(timeout = 10000)
    	public void testTopMatch() {
    		Autocompletor test = getInstance();
    		String[] queries = {"", "a", "ap", "b", "ba", "c", "ca", "cat", "d", " "};
    		String[] results = {"car", "ape", "ape", "bee", "bat", "car", "car", "cat", "", ""};
    		for(int i = 0; i < queries.length; i++){
    			String query = queries[i];
    			String reported = test.topMatch(query);
    			String actual = results[i];
    			assertEquals("wrong top match for "+query, actual, reported);
    		}
    	}


    	/**Tests correctness of topKMatches() for a few simple cases
    	 */
    	@Test(timeout = 10000)
    	public void testTopKMatches() {
    		Autocompletor test = getInstance();
    		String[] queries = {"", "", "", "", "a", "ap", "b", "ba", "d"};
    		int[] ks = {8, 1, 2, 3, 1, 1, 2, 2, 100};
    		String[][] results = {
    				{"car", "ape", "bee", "app", "bat", "ban", "cat"},
    				{"car"},
    				{"car", "ape"},
    				{"car", "ape", "bee"},
    				{"ape"},
    				{"ape"},
    				{"bee", "bat"},
    				{"bat", "ban"},
    				{}
    		};
    		for(int i = 0; i < queries.length; i++){
    			String query = queries[i];
    			String[] reported = test.topKMatches(query, ks[i]);
    			String[] actual = results[i];
    			assertArrayEquals("wrong top matches for "+query+" "+ks[i],
    					actual, reported);
    		}
    	}

    	/**
    	 * A more rigorous testing of Trie, to make sure add works.
    	 * The Trie should be constructed the same regardless of the order
    	 * words are added to the Trie, which means topMatch should return
    	 * the same output regardless of what order they are added in.
    	 * 
    	 * So, we compute all orders to add the elements, add words to the trie
    	 * in those orders, and then call topMatch on a fixed series of inputs.
    	 * We keep a set of the list of outputs - if the set size goes past 1,
    	 * then two different add orders produced two different tries
    	 * and thus two different outputs, so add is not working.
    	 */
    	@Test(timeout = 10000)
    	public void testAdd() {
    		ArrayList<Term> termList = new ArrayList<Term>();
    		Term[] terms =
    				new Term[] {new Term("ape", 6),
    				new Term("app", 4),
    				new Term("ban", 2),
    				new Term("bat", 3),
    				new Term("bee", 5),
    				new Term("car", 7),
    				new Term("cat", 1)};
    		String[] queries = {"", "a", "ap", "ape", "app", "b", "ba", "ban",
    				"bat", "be", "bee",	"c", "ca", "car", "cat", "f"};
    		for(Term t: terms)
    			termList.add(t);
    		ArrayList<ArrayList<Term>> orders = allPermutes(termList);
    		HashSet<ArrayList<String>> outputs =
    				new HashSet<ArrayList<String>>();
    		for(ArrayList<Term> order: orders){
    			String[] names = new String[order.size()];
    			double[] weights = new double[order.size()];
    			for(int i = 0; i < order.size(); i++){
    				names[i] = order.get(i).getWord();
    				weights[i] = order.get(i).getWeight();
    			}
    			TrieAutocomplete auto = new TrieAutocomplete(names, weights);
    			ArrayList<String> output = new ArrayList<String>();
    			for(String query: queries){
    				output.add(auto.topMatch(query));
    			}
    			outputs.add(output);
    			assertTrue("results depend on add order",
    					outputs.size() <= 1);
    		}
    	}
    }