SE251Ex:MultiMap
Writing a MultiMap
Description
A Map is useful for storing an association from a set of unique elements (keys) each to a single value. This kind of mapping is also known as a many-to-one relationship - as a value can be associated with many keys but each key can only be associated with a single value. Thus a normal Map won't be useful if we wanted to store a many-to-many relationship, for instance students to courses (or crew roles to crew members :), as each student can take many courses while a course can also have many students.
A way to support this relationship is to create a special kind of Map that stores an association from a key to a set of values, in other words having a Map<K,Set<V>> where K and V are type variables for the keys and values respectively. Using this kind of map directly can be tricky: for instance, in order to associate a key with a value, you would first have to get the set of values already associated with the given key and then add the given value to the set - that is, if the set isn't null. If it is, then you would have to create a new set, associate it with the key, and then add the value to the set. The same kind of thing would have to be done for remove() and get() as well.
So to save the trouble of having to do the above for every kind of many-to-many relationship, you are to write a generic class MultiMap<K,V> that encapsulates the above operations into the following nicely accessible methods:
- add(K,V) - adds the given value (V) to the set associated with the given key (K). Performs the necessary dirty work as mentioned above
- remove(K,V) - removes the given value (V) from the set associated with the given key (K). Performs the necessary dirty work as mentioned above
- get(K) - returns the set of values associated with the given key (K)
- keySet() - Returns the set of all keys that have at least one associated value in this multimap
- values() - Returns the set of all values that have at least one associated key in this multimap
The following skeleton code is provided for you to get started with. It is up to you as to which implementation of Map (i.e. HashMap or TreeMap) to use as your backing map.
import java.util.Collections;
import java.util.Map;
import java.util.Set;
/**
* A multi-map stores mapping from a key (type K) to a set of elements (type V)
* */
public class MultiMap<K,V> {
private Map<K,Set<V>> backingMap;
/**
* Constructs an empty MultiMap
*/
public MultiMap() {
}
/**
* Returns the set of all keys that have at least one associated value
* in this multimap.
* @return a set containing all keys
*/
public Set<K> keySet() {
}
/**
* Returns the set of all values that have at least one associated key
* in this multimap
* @return a set containing all values
*/
public Set<V> valueSet() {
}
/**
* Adds the specified value to the set associated with the specified key.
* Note, if the key doesn't have an associated set, you would have to create
* and associate it first before adding the value to it.
* @param key
* @param value
* @return true if the set associated with the key didn't contain value previously;
* false if it did (i.e. nothing was added)
*/
public boolean add(K key, V value) {
}
/**
* Removes the specified value from the set associated with the specified key.
* If the set becomes empty as a result, then also removes its association to the key
* altogether. Thus, the set returned from subsequent calls to keySet() would not
* contain this key anymore.
* Note, if the set associated with the key doesn't contain the value, nothing
* is done.
* @param key
* @param value
* @return true if the value successfully was removed; false if the set associated
* with the key didn't contain value
*/
public boolean remove(K key, V value) {
}
/**
* Returns the set associated with the given key. Returns an empty
* set if the key has no associations.
*
* @param key
* @return the set associated with the given key
*/
public Set<V> get(K key) {
}
/**
* Returns a string representation of this multimap in the form of e.g.
* [key1=[val1, val2], key2=[val1, val3, val4], key3=[val3]].
*
* @return the string representation of this multimap
*/
public String toString() {
return map.toString();
}
}
Test Cases
- Use TestMultiMap to test your implementation of MultiMap
Optional extension
Make your multimap bidirectional. That is, not only allow efficient retrieval of the set of values associated with a key, but also allow efficient retrieval of the set of keys associated with a value. The easiest way to do this is to store another map that associates each value to a set of keys (i.e. Map<V,Set<K>>) and update it whenever add() or remove() is called.
Discussion
Here you can ask questions and discuss stuff