Recipe 11.5. 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 Example 11-8, which is used in practically the same manner as a Dictionary<T,U> class, does this. Example 11-8. 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 Table 11-3 are of particular interest to using a MultiMap<T,U> object. Table 11-3. 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 Example 11-9. Example 11-9. 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. |
