Exercise 2, from Chapter 15 of Modern Programming Languages A Practical Introduction.

For this exercise, rewrite all three of the classes above and add any classes or interfaces you need to achieve the following goals:

1) The three basic dictionary-of-strings methods should be part of an interfact named DictionaryofStrings, which should be implemented by all three classes. With this in place, you would be able to pass an Alist a SizedAlist or an AHash object to a method that expects a parameter of type DictionaryofStrings, and that method would be able to use find, size and associate without knowing the exact class of the object.

2) You should use inheritance where appropriate to minimize the amount of duplicated code among the three implementations. Notice, in particular that the current implementations of Alist and SizedAlist have much code in common.

3)You should comment the class appropriately; that is, comment every interface every class, every field and every method, as well as anything in the code that you think needs explanation.

Do not make any material changes to the method bodies. Check that your code compiles. Other than that, there is no need to test your code, since the method bodies given already work.

public class ANode { private String key; private String value; private ANode link; public ANode(String k, String v, ANode li) { key = k; value = v; link = li; } public String getKey() { return key; } public ANode getLink() { return link; } public String getValue() { return value; } public void setValue(String v) { value = v; } }

public class SizedAList { private ANode head = null; private int size = 0; public String associate(String key, String value) { ANode n = nodeLookup(key); String oldValue; if (n != null) { oldValue = n.getValue(); n.setValue(value); } else { n = new ANode(key, value, head); head = n; oldValue = null; size++; } return oldValue; } public String find(String key) { ANode n = nodeLookup(key); return (n == null) ? null : n.getValue(); } private ANode nodeLookup(String key) { ANode n = head; while (n!=null && !n.getKey().equals(key)) { n = n.getLink(); } return n; } public int size() { return size; } }

public class AList { private ANode head = null; public String associate(String key, String value) { ANode n = nodeLookup(key); String oldValue; if (n != null) { oldValue = n.getValue(); n.setValue(value); } else { n = new ANode(key, value, head); head = n; oldValue = null; } return oldValue; } public String find(String key) { ANode n = nodeLookup(key); return (n == null) ? null : n.getValue(); } private ANode nodeLookup(String key) { ANode n = head; while (n!=null && !n.getKey().equals(key)) { n = n.getLink(); } return n; } public int size() { ANode n = head; int length = 0; while (n!=null) { n = n.getLink(); length++; } return length; } }

public class AHash { private java.util.Hashtable table = new java.util.Hashtable(); public String associate(String key, String value) { return (String) table.put(key,value); } public String find(String key) { return (String) table.get(key); } public int size() { return table.size(); } }