Algorithm And Running Time
Algorithm: return the instance variable count Run Time: O(1)
When I add or remove the key, I update the instance variable count, In function size(), I just return it. So it is O(1)
public String get(String key)
Algorithm: Start from root, go down the tree through the path determined by the key
until encounter null node or when path finish return the last node’s value. Run Time: O(m) m is the length of the key
Because we at most go down m levels of the tree.
public String put(String key, String value)
Algorithm: Similar with get, start from root, go down the tree through the path determined by the key, but when we encounter null node, we create new node instead return.
Run Time: O(m) m is the length of the key Because we go down m levels of the tree.
public String remove(String key)
Algorithm:
1. Same with “get” method, go down the tree
2. Go up the tree from the last node in 1. If a node’s value is null and its all children
are null, then it will be removed from the tree, recursively to the root.
Run Time: O(m) m is the length of the key
Because we go down m levels of the tree and go up at most m levels of the tree.
public int size()
public List
1. First go down the tree through path determined by prefix to a node
2. Use depth first search algorithm to find all the keys in the subtree root at node
reached in 1
• Run Time: O(m + k)
• Because in 1, we go down m levels of the tree, it is O(m), In 2, we add k keys to list which is O(k), so the overall time is O(m + k).
public int countKeysMatchingPrefix(String prefix) Algorithm: return the size of the list returned by getKeysMatchingPrefix Run Time: O(m + k)
It has the same run time with getKeysMatchingPrefix.
public int sumKeyLengths()
Algorithm: Use getKeysMatchingPrefix with empty prefix to get
the list of all keys, and then sum their length. Run Time: O(n)
getKeysMatchingPrefix(“”) is O(n), then sum the length is also O(n).
public int countPrefixes()
Algorithm: Start from the root, recursively count the prefixes for a node. For null node the count is 1, for non-null node, the count is the sum of the 4 children’s node plus 1.
Run Time: O(n) n is the number of key-value pairs in the collection Because we count n nodes.
Testing
I set up the trie in the setup method of junit, and then use this trie to test in various methods.
For each method, I test the cases that would throw exceptions, the empty trie, and the operation with existing or non-existing keys.
1. Test the empty Trie size is 0
3. Testafteraddorremoveexistingornon-existingkeys,the size is correct.
1. Test the empty Trie
testSize
assertEquals(0, new Assignment().size());
2. Testthenon-emptyTriewithkeys”GAT”,”GATTC”,
“GATTACA” is 3
assertEquals(prefixes.size(), prefixMap.size());
testIsEmpty
assertEquals(true, new Assignment().isEmpty());
2. Test the non-empty Trie
assertEquals(false, prefixMap.isEmpty());
3. Test after add or remove existing or non-existing keys for (String pre : prefixes) {
prefixMap.remove(pre); }
assertEquals(true, prefixMap.isEmpty());
testGet
1. Test exception cases
2. Test get non-existing key, the return value is null
assertNull(null, prefixMap.get(“AAAAA”));
3. Test get existing key, the return value is correct assertEquals(“1”, prefixMap.get(prefixes.get(1)));
testPut
assertEquals(“1”, prefixMap.put(prefixes.get(1), “added”));
assertEquals(“added”, prefixMap.get(prefixes.get(1)));
3. Test put non-existing key, the return value is null and then use get to check the added key-value.
assertNull(prefixMap.put(“GAGAGA”, “added”)); assertEquals(“added”, prefixMap.get(“GAGAGA”));
testRemove
assertNull(prefixMap.remove(“AAAAAA”));
3. Test remove existing key, the return value is old value
assertEquals(“1”, prefixMap.remove(prefixes.get(1))); assertNull(prefixMap.get(prefixes.get(1)));
4. Test the get after add or remove operations
1. Test exception cases
2. Test put existing key, the return value is old value
and then use get to check the value is updated.
1. Test exception cases
2. Test remove non-existing key, the return value is null
testCountKeysMatchingPrefix
1. Test exception cases
2. Test count with non-existing prefix, the return vaue is 0.
assertEquals(0,prefixMap.countKeysMatchingPrefix(“AG”)); 3. Test the count of prefix “G” of keys { “GAT”, “GATTC”, “GATTACA”}, the result is 3. assertEquals(3, prefixMap.countKeysMatchingPrefix(“G”));
1. Test exception cases
testGetKeysMatchingPrefix
2. Test match all.
assertEquals(Arrays.asList(new String[]{“GAT”, “GATTACA”, “GATTC”}), prefixMap.getKeysMatchingPrefix(“G”));
3. Test match some.
assertEquals(Arrays.asList(new String[]{“GATTACA”, “GATTC”}), prefixMap.getKeysMatchingPrefix(“GATT”));
testCountPrefixes
1. Test non-empty trie.
assertEquals(8, prefixMap.countPrefixes());
2. Test empty trie
assertEquals(0, new Assignment().countPrefixes());
3. Test after put.
prefixMap.put(“GATTACAATT”, “X”); assertEquals(11, prefixMap.countPrefixes());
4. Test after remove
prefixMap.put(“GATTACAATT”, “X”); prefixMap.remove(“GATTACAATT”); assertEquals(8, prefixMap.countPrefixes());
testSumKeyLengths
1. Test non-empty-trie
assertEquals(15, prefixMap.sumKeyLengths());
2. Test empty trie
assertEquals(0, new Assignment().sumKeyLengths());
3. Test after remove
prefixMap.remove(prefixes.get(2)); assertEquals(8, prefixMap.sumKeyLengths());