import java.util.ArrayList; import java.util.Set; import java.util.TreeSet; /** * Implements the interface. * A concrete implementaion of a map with all of the * ugly search * * @author gtowell * * Created: Sep 21, 2020 * Modified: Jul 2021 */ public class Map151 implements Map151Interface { /** The underlying data structure to actually do the storage */ private ArrayList> underlying = new ArrayList<>(); /** * Holds key-value pairs together The only time it is OK (or even good) to have * public instance vars is in private classes. (Since they are not really public * anyway) */ private class Pair { // the key. Once set it canot be changed public final L key; // the value public W value; // Create a key value pair. Pair(L ky, W val) { key = ky; value = val; } } /** * Set a key value pair. Will overwrite value if key already present. * * @param key the key * @param val the new value */ public void put(K key, V val) { Pair pair = iContainsKey(key); if (pair == null) { Pair np = new Pair<>(key, val); underlying.add(np); } else { pair.value = val; } } /** * Get the value associated with a key * * @param key the key * @return the associated value */ public V get(K key) { Pair pair = iContainsKey(key); if (pair != null) return pair.value; return null; } /** * does the Map contain the key? * * @param key the key in question * @return true iff the key is in the map */ public boolean containsKey(K key) { return null != iContainsKey(key); } private Pair iContainsKey(K ky) { for (Pair pair : underlying) { if (pair.key.equals(ky)) { return pair; } } return null; } /** * The number of items in the map * * @return The number of items in the map */ public int size() { return underlying.size(); } /** * All of the keys in the map This method allows users of the map to see all of * the keys. That this returns a Set is to make this consistent with the Java * Map interface. * * @return All of the keys in the map */ public Set keySet() { TreeSet set = new TreeSet<>(); for (Pair pair : underlying) { set.add(pair.key); } return set; } @Override public String toString() { StringBuffer sb = new StringBuffer(); for (Pair pair : underlying) { sb.append("[" + pair.key + ":" + pair.value + "]\n"); } return sb.toString(); } }