import java.util.*;

/**

• MyMap serves as a working implementation of the Map interface in Java.

• @author Asma Awad

• @version 1.0 */ public class MyMap implements Iterable { //implementing a map using a hashtable as the underlying structure, assuming Strings are mapped to Integers so far private ArrayList<LinkedList> theTable; private int numElements;

  public MyMap(int numBuckets) { theTable = new ArrayList<>();

  //adding the given number of empty LinkedLists to the ArrayList
  for (int i = 0; i < numBuckets; i++)
      theTable.add(new LinkedList<>());
  
  numElements = 0;
  

  }

  public MyMap() { this(10); }

  /**

  • put allows one to put a key value pair into the map

  • @param key the key or String to be mapped to an Integer value

  • @param value the value or Integer to be the corresponding value to the key */ public void put(String key, Integer value) { //using the key value (String)'s hashcode as the place in the ArrayList int bucket = whichBucket(key); LinkedList temp = theTable.get(bucket);

    //if the key already exists in the map, change its value to value, overwriting what was there for (Pair p : temp) { if (p.getKey().equals(key)) { p.setValue(value); return; }

    } //if the key was not already there, insert the key value pair into the map Pair p = new Pair(key, value); temp.add(p); numElements++; }

  /**

  • containsKey determines whether or not the map contains the given key as a key

  • @param key the key that is being searched for within the map

  • @return true if the key is found and false otherwise */ public boolean containsKey(String key) { int bucketNum = whichBucket(key); //check the index in the case that the key's hashcode is beyond the bounds of the ArrayList if (bucketNum >= 0 && bucketNum < theTable.size()) { LinkedList ref = theTable.get(bucketNum);

    //returns true if key already exists in the map
    for (Pair p : ref) {
        if (p.getKey().equals(key))
            return true;
    }
    

    } return false; }

  /**

  • containsValue determines whether or not the map contains the given value as a value
  • @param value the value being searched for within the map
  • @return true if the value is found and false otherwise */ public boolean containsValue(Integer value) { for (LinkedList list : theTable) { for (Pair p : list) { if (p.getValue().equals(value)) return true; } } return false; }

  /**

  • remove removes the key value pair associated with a given key in the map

  • @param key the key of the key value pair to be removed

  • @return true if the remove was successful and false otherwise */ public boolean remove(Object key) { //check and cast the parameter before removing if (!(key instanceof String)) return false; String strKey = (String) key;

    //determine which LinkedList to search by the key's hashcode int bucket = whichBucket(strKey); LinkedList temp = theTable.get(bucket);

    //if key is in the map, remove it if (this.containsKey(strKey)) { for (Pair p : temp) { if (p.getKey().equals(strKey)) { temp.remove(p); numElements--; return true; } } } return false; }

  /**

  • get provides the value in the map that is associated with a given key

  • @param key the key whose value is to be provided

  • @return the value mapped to the key if it is found and false otherwise */ public Integer get(String key) { if (this.containsKey(key)) { //first check if the key is there at all int bucket = whichBucket(key); LinkedList temp = theTable.get(bucket); //find the LinkedList to be searched by hashcode

     //search the LinkedList for the Pair with the matching key
     for (Pair p : temp) {
         if (p.getKey().equals(key))
             return p.getValue();
     }
    

    } return null; }

  /**

  • entrySet provides a set of all key value pairs within the map

  • @return a Set of all mapped pairs within the map */ public Set entrySet() { Set pairs = new HashSet<>();

    for (LinkedList list : theTable) pairs.addAll(list); //adds each of the entire LinkedLists into the Set

    return pairs; }

  /**

  • values returns all values of the key value pairs within the map

  • @return a List of all associated values within the map */ public Collection values() { Collection values = new ArrayList<>();

    for (LinkedList list : theTable) { for (Pair p : list) { values.add(p.getValue()); //adds the value of each Pair } }

    return values; }

  /**

  • keySet returns a set of all keys of the key value pairs within the map

  • @return a Set of all keys within the map */ public Set keySet() { Set keys = new HashSet<>();

    for (LinkedList list : theTable) { for (Pair p : list) { keys.add(p.getKey()); //adds the key of each Pair } } return keys; }

  /**

  • size provides the number of elements in the map
  • @return an int maintaining the number of elements in the map */ public int size() { return numElements; }

  /**

  • isEmpty determines whether or not the map is empty
  • @return true if there are no elements in the map, and false otherwise */ public boolean isEmpty() { return numElements == 0; }

  /**

  • iterator provides an iterator for the map in order to traverse its elements
  • @return a MapIterator to iterate over the map's elements */ public Iterator iterator() { return new MapIterator(); }

  /**

  • whichBucket serves as a helper method that determines where in the map an element should go
  • @param obj the Object to be put in the map
  • @return the index where the Object should be located */ private int whichBucket(Object obj) { return obj.hashCode() % theTable.size(); }

  /**

  • The Pair class maintains a key and value such that they are associated with each other.

  • @author Asma Awad

  • @version 1.0 */ private static class Pair { private String str; private Integer value;

    Pair(String str, Integer value) { this.str = str; this.value = value; }

    /**

    • getKey provides the key of a Pair
    • @return a String representing the key of a Pair */ public String getKey() { return str; }

    /**

    • getValue provides the value of a Pair
    • @return an Integer representing the value of a Pair */ public Integer getValue() { return value; }

    /**

    • setValue serves as a mutator method for the value of a Pair
    • @param value the value that the old value of the Pair is to be replaced with
    • @return the old value of the Pair */ public Integer setValue(Integer value) { Integer temp = this.value; this.value = value; return temp; }

    /**

    • toString provides a formatted representation of a Pair
    • @return a String representing a Pair */ public String toString() { return "[Key: " + str + " Value: " + value + "]"; } }

  /**

  • MapIterator provides a means of iterating over the elements of a given MyMap.

  • @author Asma Awad

  • @version 1.0 */ private class MapIterator implements Iterator { private ArrayList elems; private int index;

    public MapIterator() { elems = addToTable(); index = 0; }

    /**

    • next provides the next element to be looked at in the map
    • @return the next Pair that has yet to be looked at in the map */ public Pair next() { index++; return elems.get(index-1); }

    /**

    • hasNext determines whether or not a map has further elements to be looked at
    • @return true if there are more elements to be looked at, and false otherwise */ public boolean hasNext() { return index < elems.size(); }

    /**

    • remove is meant to remove the last element returned by this iterator from the map
    • @throws UnsupportedOperationException as it is optional by Java's standards */ public void remove() { throw new UnsupportedOperationException(); } }

  /**

  • addToTable serves as a helper method to the MapIterator that adds all Pairs in a map to one Collection

  • @return the ArrayList to which all Pairs in a map were added */ private ArrayList addToTable() { ArrayList elems = new ArrayList<>();

    for(LinkedList list : theTable) elems.addAll(list);

    return elems; } }