SE251:jhor053sMultiMap
Jump to navigation
Jump to search
Here is my multi map as per showcased in the 251 Group Session 5
Any q's or comments let me know on my talk page or here Jhor053 22:13, 11 May 2008 (NZST)
If you use this for something Include Hong Yul Yang and I please and feel free to modify it and post it up on another wiki page and post your link also on here!
//package movies.core;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
/**
* A multi-map stores mapping from a key (type K) to a set of elements (type V)
* A many to many
*
* @origAuthor Hong Yul Yang (based of his Skeleton code from 251 wiki)
* @author jhor053
* */
public class MultiMap<K,V> {
//private Map<K,Set<V>> backingMap;
private Map<K, Set<V>> backingMap;
private Map<V, Set<K>> reverseMap;
/**
* Constructs an empty MultiMap
*/
public MultiMap() {
backingMap = new TreeMap<K, Set<V>> ();
reverseMap = new TreeMap<V, Set<K>> ();
}
/**
* 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() {
return backingMap.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() {
//Uses the reverse map to get a quick set of the values
return reverseMap.keySet();
}
/**
* 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) {
//Safety to get rid of false alignments
if(key == null || value == null)
return false;
//Checks too see if it is already assigned
if(containsValueAssignedToKey(key, value))
return false;
//Initialising variable names for the sets
Set <V> vSet;
Set <K> kSet;
//Seeing if the reference is non existant
//I.e. either the key is present
if (backingMap.get(key) != null){
vSet = backingMap.get(key);
}else{ //I.e. key has nothing assigned or non existant key
vSet = new TreeSet<V> ();
}
//Add the value to the set to be assigned
vSet.add(value);
//Seeing if the reference is non existant
//I.e. either the value is present
if(reverseMap.get(value) != null){
kSet = reverseMap.get(value);
}else{ //I.e. value has nothing assigned or non existant value
kSet = new TreeSet<K> ();
}
//Add the key to the set to be assigned
kSet.add(key);
//Saving references
backingMap.put(key, vSet);
reverseMap.put(value, kSet);
return true;
}
/**
* 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) {
if(containsValueAssignedToKey(key, value)){
//initialise Sets
Set <V> vSet = backingMap.get(key);
Set <K> kSet;
//boolean removeKey = false;
//Remove the value from the normal map
if(vSet.remove(value)){
//IE no more occurrences of the key
if(vSet.isEmpty()){
//removing key as nothing assigned to it
backingMap.remove(key);
//removeKey = true;
}else{//Still have references for the key
backingMap.put(key, vSet);
}
//Get all references
kSet = reverseMap.get(value);
//Ie occurrences of the value
if(kSet != null){
kSet.remove(key);
//update refferences on the reverse map
if(kSet.isEmpty()){
reverseMap.remove(value);
}else{
reverseMap.put(value, kSet);
}
}
return true;
}
}
return false;
}
/**
* Removes the specified key from the set associated with the specified value.
* 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 value
* @return true if the value successfully was removed; false if the set associated
* with the key didn't contain value
*/
public boolean removeKey(K key) {
if(backingMap.containsKey(key)){
Set<V> tempSet = backingMap.remove(key);
for (Iterator<V> iterator = tempSet.iterator(); iterator.hasNext();) {
V v = iterator.next();
Set<K> tempSet2 = reverseMap.get(v);
if(tempSet2 != null){
tempSet2.remove(key);
if(tempSet2.isEmpty()){
reverseMap.remove(v);
}else{
reverseMap.put(v, tempSet2);
}
}
}
return true;
}
return false;
}
/**
* 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 value
* @return true if the value successfully was removed; false if the set associated
* with the key didn't contain value
*/
public boolean removeValue(V value) {
if(reverseMap.containsKey(value)){
Set<K> tempSet = reverseMap.remove(value);
for (Iterator<K> iterator = tempSet.iterator(); iterator.hasNext();) {
K k = iterator.next();
Set<V> tempSet2 = backingMap.get(k);
if(tempSet2 != null){
tempSet2.remove(value);
if(tempSet2.isEmpty()){
backingMap.remove(k);
}else{
backingMap.put(k, tempSet2);
}
}
}
return true;
}
return false;
}
/**
* 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) {
Set <V> returnSet = new TreeSet<V>();
if(backingMap.get(key) == null)
return returnSet;
returnSet = backingMap.get(key);
return returnSet;
}
/**
* Returns the set associated with the given value. Returns an empty
* set if the value has no associations.
*
* @param key
* @return the set associated with the given key
*/
public Set<K> getKeySetFromValue(V value) {
Set <K> returnSet = new TreeSet<K>();
if(reverseMap.get(value) == null)
return returnSet;
returnSet = reverseMap.get(value);
return returnSet;
}
/**
* 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 backingMap.toString();
}
/**
* Checks to see if a specified value is assigned to a key
*
* @param key
* @param value
* @return true if the value is assigned to that key
*/
public boolean containsValueAssignedToKey (K key, V value){
if( backingMap.containsKey(key) ){
//Get the Set<V> as per specified by the key
Set<V> testSet = backingMap.get(key);
//See if testSet Contains the specified value
if(testSet.contains(value))
return true;
}
return false;
}
/**
* Checks to see if a specified key is assigned to a Value
*
* @param value
* @param key
* @return true if the key is assigned to that value
*/
public boolean containsKeyAssignedToValue (V value, K key){
if( reverseMap.containsKey(value) ){
//Get the Set<V> as per specified by the key
Set<K> testSet = reverseMap.get(value);
//See if testSet Contains the specified value
if(testSet.contains(key))
return true;
}
return false;
}
/**
* Implements containKey() from Map
*
* @param key
* @return True if it contains specified key
*/
public boolean containsKey(K key){
return backingMap.containsKey(key);
}
/**
* Implements containValue() from Map
*
* @param key
* @return True if it contains specified Value
*/
public boolean containsValue(V value){
return reverseMap.containsKey(value);
}
}