Creating a One-to-Many Map (MultiMap)
Problem
A Hashtable or a Dictionary<T,U> can map only a single key to a single value, but you need to map a key to one or more values. In addition, it may also be possible to map a key to null.
Solution
Use a Dictionary<T,U> with values that are a List<U>. This structure allows you to add multiple values (in the List<U>) for each key of the Dictionary<T,U>. The MultiMap<T,U> class shown in Figure, which is used in practically the same manner as a Dictionary<T,U> class, does this.
MultiMap class
using System;
using System Collections;
using System.Collections.Generic;
public class MultiMap<TKey, UValue> : IDictionary<TKey, IList<UValue>>
{
private Dictionary<TKey, IList<UValue>> map =
new Dictionary<TKey, IList<UValue>>();
public IList<UValue> this[TKey key]
{
get {return (map[key]);}
set {map[key] = value;}
}
public void Add(TKey key, UValue item)
{
AddSingleMap(key, item);
}
public void Add(TKey key, IList<UValue> items)
{
foreach (UValue val in items)
AddSingleMap(key, val);
}
public void Add(KeyValuePair<TKey, IList<UValue>> keyValuePair)
{
foreach (UValue val in keyValuePair.Value)
AddSingleMap(keyValuePair.Key, val);
}
public void Clear()
{
map.Clear();
}
public int Count
{
get {return (map.Count);}
}
public bool IsReadOnly
{
get {throw(new NotSupportedException(
"This operation is not supported."));}
}
public bool Contains(TKey key)
{
return (map.ContainsKey(key));
}
public bool Contains(KeyValuePair<TKey, IList<UValue>> keyValuePair)
{
return (map.ContainsKey(keyValuePair.Key) &&
map.ContainsValue(keyValuePair.Value));
}
public bool ContainsKey (TKey key)
{
return (map.ContainsKey(key));
}
public bool ContainsValue(UValue item)
{
if (item == null)
{
foreach (KeyValuePair<TKey, IList<UValue>> kvp in map)
{
if (((List<UValue>)kvp.Value).Count == 0)
{
return (true);
}
}
return (false);
}
else
{
foreach (KeyValuePair<TKey, IList<UValue>> kvp in map)
{
if (((List<UValue>)kvp.Value).Contains(item))
{
return (true);
}
}
return (false);
}
}
IEnumerator<KeyValuePair<TKey, IList<UValue>>> IEnumerable<KeyValuePair<TKey,
IList<UValue>>>.GetEnumerator()
{
return (map.GetEnumerator());
}
IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return (map.GetEnumerator());
}
public bool Remove(TKey key)
{
return (RemoveSingleMap(key));
}
public bool Remove(KeyValuePair<TKey, IList<UValue>> keyValuePair)
{
return (Remove(keyValuePair.Key));
}
protected virtual void AddSingleMap(TKey key, UValue item)
{
// Search for key in map Hashtable.
if (map.ContainsKey(key))
{
// Add value to List in map.
List<UValue> values = (List<UValue>)map[key];
// Add this value to this existing key.
values.Add(item);
}
else
{
if (item == null)
{
// Create new key and mapping to an empty List.
map.Add(key, new List<UValue>());
}
else
{
List<UValue> values = new List<UValue>();
values.Add(item);
// Create new key and mapping to its value.
map.Add(key, values);
}
}
}
protected virtual bool RemoveSingleMap(TKey key)
{
if (this.ContainsKey(key))
{
// Remove the key from KeysTable.
return (map.Remove(key));
}
else
{
throw (new ArgumentOutOfRangeException("key", key,
"This key does not exists in the map."));
}
}
public bool TryGetValue(TKey key, out UValue item)
{
throw (new NotSupportedException(
"This operation is not supported, use " +
"TryGetValue(TKey, out IList<UValue>) instead."));
}
public bool TryGetValue(TKey key, out IList<UValue> items)
{
return (map.TryGetValue(key, out items));
}
public ICollection<TKey> Keys
{
get { return (map.Keys); }
}
public ICollection<IList<UValue>> Values
{
get { return (map.Values); }
}
public void CopyTo(TKey[] arr, int index)
{
int cntr = 0;
foreach (KeyValuePair<TKey, IList<UValue>> keyValuePair in map)
{
arr[cntr + index] = keyValuePair.Key;
cntr++;
}
}
public void CopyTo(KeyValuePair<TKey, IList<UValue>>[] arr, int index)
{
CopyTo(arr, index);
}
}
|
The methods defined in Figure are of particular interest to using a MultiMap<T,U> object.
Members of the MultiMap classMember | Description |
|---|
Indexer | The get accessor obtains a List<U> of all values that are associated with a key. The set accessor adds an entire List<U> of values to a key. Its syntax is:
public List<U> this[T key]
where key is the key to be added to the MultiMap<T,U> through the set accessor, or it is the key with values that you want to retrieve via the get accessor. | Add method | Adds a key to the Dictionary<T,List<U>> and its associated value. Its syntax is:
Add(T key, T value)
where key is the key to be added to the MultiMap<T,U> and value is the value to add to the internal List<U> of the private map field. | Clear method | Removes all items from the MultiMap<T,U> object. | Count method | Returns a count of all keys in the MultiMap<T,U> object. | Clone method | Returns a deep copy of the MultiMap<T,U> object. | ContainsKey method | Returns a bool indicating whether the MultiMap<T,U> contains a particular value as its key. Its syntax is:
ContainsKey(T key)
where key is the key to be found in the MultiMap<T,U>. | ContainsValue method | Returns a bool indicating whether the MultiMap<T,U> contains a particular value. Its syntax is:
ContainsValue(T value)
where value is the object to be found in the MultiMap<T,U>. | Remove method | Removes a key from the MultiMap<T,U> and all its referent values in the internal map Dictionary<T, List<U>>. Its syntax is:
Remove(T key)
where key is the key to be removed. |
Items may be added to a MultiMap<T,U> object by running the code shown in Figure.
Testing the MultiMap class
public static void TestMultiMap()
{
string s = "foo";
// Create and populate a MultiMap object.
MultiMap<int, string> myMap = new MultiMap<int, string>();
myMap.Add(0, "zero");
myMap.Add(1, "one");
myMap.Add(2, "two");
myMap.Add(3, "three");
myMap.Add(3, "duplicate three");
myMap.Add(3, "duplicate three");
myMap.Add(4, "null");
myMap.Add(5, s);
myMap.Add(6, s);
// Display contents.
foreach (KeyValuePair<int, List<string>> entry in myMap)
{
Console.Write("Key: " + entry.Key.ToString() + "\tValue: ");
foreach (string str in myMap[entry.Key])
{
Console.Write(str + " : ");
}
Console.WriteLine();
}
// Obtain values through the indexer.
Console.WriteLine();
Console.WriteLine("((ArrayList) myMap[3])[0]: " + myMap[3][0]);
Console.WriteLine("((ArrayList) myMap[3])[1]: " + myMap[3][1]);
// Add items to MultiMap using a List.
List<string> testArray = new List<string>();
testArray.Add("BAR");
testArray.Add("BAZ");
myMap[10] = testArray;
myMap[10] = testArray;
// Remove items from MultiMap.
myMap.Remove(0);
myMap.Remove(1);
// Display MultiMap.
Console.WriteLine();
Console.WriteLine("myMap.Count: " + myMap.Count);
foreach (KeyValuePair<int, List<string>> entry in myMap)
{
Console.Write("entry.Key: " + entry.Key.ToString() +
"\tentry.Value(s): ");
foreach (string str in myMap[entry.Key])
{
if (str == null)
{
Console.Write("null : ");
}
else
{
Console.Write(str + " : ");
}
}
Console.WriteLine();
}
// Determine if the map contains the key or the value.
Console.WriteLine();
Console.WriteLine("myMap.ContainsKey(2): " + myMap.ContainsKey(2));
Console.WriteLine("myMap.ContainsValue(two): " +
myMap.ContainsValue("two"));
Console.WriteLine("Contains Key 2: " + myMap.ContainsKey(2));
Console.WriteLine("Contains Key 12: " + myMap.ContainsKey(12));
Console.WriteLine("Contains Value two: " + myMap.ContainsValue("two"));
Console.WriteLine("Contains Value BAR: " + myMap.ContainsValue("BAR"));
// Clear all items from MultiMap.
myMap.Clear();
}
|
This code displays the following:
Key: 0 Value: zero :
Key: 1 Value: one :
Key: 2 Value: two :
Key: 3 Value: three : duplicate three : duplicate three :
Key: 4 Value:
Key: 5 Value: foo :
Key: 6 Value: foo :
((ArrayList) myMap[3])[0]: three
((ArrayList) myMap[3])[1]: duplicate three
myMap.Count: 6
entry.Key: 2 entry.Value(s): two :
entry.Key: 3 entry.Value(s): three : duplicate three : duplicate three :
entry.Key: 4 entry.Value(s):
entry.Key: 5 entry.Value(s): foo :
entry.Key: 6 entry.Value(s): foo :
entry.Key: 10 entry.Value(s): BAR : BAZ :
myMap.ContainsKey(2): True
myMap.ContainsValue(two): True
Contains Key 2: True
Contains Key 12: False
Contains Value two: True
Contains Value BAR: True
Discussion
A one-to-many map, or multimap, allows one object, a key, to be associated, or mapped, to zero or more objects. The MultiMap<T,U> class presented here operates similarly to a Dictionary<T,U>. The MultiMap<T,U> class contains a Dictionary<T, List<U>> field called map that contains the actual mapping of keys to values. Several of the MultiMap<T,U> methods are delegated to the methods on the map Dictionary<T, List<U>> object.
A Dictionary<T,U> operates on a one-to-one principle: only one key may be associated with one value at any time. However, if you need to associate multiple values with a single key, you must use the approach used by the MultiMap<T,U> class. The private map field associates a key with a single List<U> of values, which allows multiple mappings of values to a single key and mappings of a single value to multiple keys. As an added feature, a key can also be mapped to a null value.
Here's what happens when key-value pairs are added to a MultiMap<t,U> object:
The MultiMap<T,U>.Add method is called with a key and value provided as parameters. The Add method checks to see whether key exists in the map Dictionary<T, List<U>> object. If key does not exist, it is added as a key in the map Dictionary<T, List<U>> object. This key is associated with a new List<U> as the value associated with key in this Hashtable. If the key does exist, the key is looked up in the map Dictionary<T, List<U>> object and the value is added to the key's List<U>.
To remove a key using the Remove method, the key and List<U> pair are removed from the map Dictionary<T, List<U>>. This allows removal of all values associated with a single key. The MultiMap<T,U>.Remove method calls the RemoveSingleMap method, which encapsulates this behavior. Removal of key "0", and all values mapped to this key, is performed with the following code:
myMap.Remove(1);
To remove all keys and their associated values, use the MultiMap<T,U>.Clear method. This method removes all items from the map Dictionary<T, List<U>>.
The other major member of the MultiMap<T,U> class needing discussion is its indexer. The indexer returns the List<U> of values for a particular key through its get accessor. The set accessor simply adds the List<U> provided to a single key. This code creates an array of values and attempts to map them to key "5" in the myMap object:
List<string> testArray = new List<string>();
testArray.Add("BAR");
testArray.Add("BAZ");
myMap["5"] = testArray;
The following code makes use of the get accessor to access each value associated with key "3":
Console.WriteLine(myMap[3][0]);
Console.WriteLine(myMap[3][1]);
Console.WriteLine(myMap[3][2]);
This looks somewhat similar to using a jagged array. The first indexer ([3] in the preceding examples) is used to pull the List<U> from the map Dictionary<T, List<U>>, and the second indexer is used to obtain the value in the List<U>. This code displays the following:
three
duplicate three
duplicate three
This MultiMap<T,U> class also allows the use of the foreach loop to enumerate its key-value pairs. The following code displays each key-value pair in the MyMap object:
foreach (KeyValuePair<int, List<string>> entry in myMap)
{
Console.Write("Key: " + entry.Key.ToString() + "\tValue: ");
foreach (string str in myMap[entry.Key])
{
Console.Write(str + " : ");
}
Console.WriteLine();
}
The outer foreach loop is used to retrieve all the keys and the inner foreach loop is used to display each value mapped to a particular key. This code displays the following for the initial MyMap object:
Key: 0 Value: zero :
Key: 1 Value: one :
Key: 2 Value: two :
Key: 3 Value: three : duplicate three : duplicate three :
Key: 4 Value:
Key: 5 Value: foo :
Key: 6 Value: foo :
Two methods that allow searching of the MultiMap<T,U> object are ContainsKey and ContainsValue. The ContainsKey method searches for the specified key in the map Dictionary<T, List<U>>. The ContainsValue method searches for the specified value in a List<U> in the map Dictionary<T, List<U>>. Both methods return true if the key-value was found or false otherwise:
Console.WriteLine("Contains Key 2: " + myMap.ContainsKey(2));
Console.WriteLine("Contains Key 12: " + myMap.ContainsKey(12));
Console.WriteLine("Contains Value two: " + myMap.ContainsValue("two"));
Console.WriteLine("Contains Value BAR: " + myMap.ContainsValue("BAR"));
Note that the ContainsKey and ContainsValue methods are both case-sensitive.
See Also
See the "List<T> Class," "Dictionary<T,U> Class," and "IEnumerator Interface" topics in the MSDN documentation.
 |
