Recipe 10.5 Creating a One-to-Many Map (MultiMap)

Problem

A Hashtable 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 Hashtable whose values are ArrayLists. This structure allows you to add multiple values (in the ArrayList) for each key of the Hashtable. The MultiMap class, which is used in practically the same manner as a Hashtable class, does this:

using System;
using System.Collections;

public class MultiMap
{
    private Hashtable map = new Hashtable( );

    public ArrayList this[object key] 
    {
        get    {return ((ArrayList)map[key]);}
        set {map[key] = value;}
    }

    public void Add(object key, object item)
    {
        AddSingleMap(key, item);
    }

    public void Clear( )
    {
        map.Clear( );
    }

    public int Count
    {
        get {return (map.Count);}
    }

    public bool ContainsKey (object key)
    {
        return (map.ContainsKey(key));
    }

    public bool ContainsValue(object item)
    {
        if (item == null)
        {
            foreach (DictionaryEntry de in map)
            {
                if (((ArrayList)de.Value).Count == 0)
                {
                    return (true);
                }
            }

            return (false);
        }
        else
        {
            foreach (DictionaryEntry de in map)
            {
                if (((ArrayList)de.Value).Contains(item))
                {
                    return (true);
                }
            }

            return (false);
        }
    }

    public IEnumerator GetEnumerator( )
    {
        return (map.GetEnumerator( ));
    }

    public void Remove(object key)
    {
        RemoveSingleMap(key);
    }

    public object Clone( )
    {
        MultiMap clone = new MultiMap( );

        foreach (DictionaryEntry de in map)
        {
            clone[de.Key] = (ArrayList)((ArrayList)de.Value).Clone( );
        }

        return (clone);
    }

    protected virtual void AddSingleMap(object key, object item)
    {
        // Search for key in map Hashtable
        if (map.ContainsKey(key))
        {
            if (item  == null)
            {
                throw (new ArgumentNullException("value", 
                       "Cannot map a null to this key"));
            }
            else
            {
                // Add value to ArrayList in map
                ArrayList values = (ArrayList)map[key];

                // Add this value to this existing key
                values.Add(item);
            }
        }
        else
        {
            if (item == null)
            {
                // Create new key and mapping to an empty ArrayList
                map.Add(key, new ArrayList( ));
            }
            else
            {
                ArrayList values = new ArrayList( );
                values.Add(item);

                // Create new key and mapping to its value
                map.Add(key, values);
            }
        }
    }

    protected virtual void RemoveSingleMap(object key)
    {
        if (this.ContainsKey(key))
        {
            // Remove the key from KeysTable
            map.Remove(key);
        }
        else
        {
            throw (new ArgumentOutOfRangeException("key", key.ToString( ), 
                   "This key does not exists in the map."));
        }
    }
}

The methods defined in Table 10-3 are of particular interest to using a MultiMap object.

Table 10-3. Members of the MultiMap class

Member	Description
Indexer	The get accessor obtains an ArrayList of all values that are associated with a key. The set accessor adds an entire ArrayList of values to a key. Its syntax is: this[object key] where key is the key to be added to the MultiMap through the set accessor, or it is the key in which to retrieve all of its associated values via the get accessor.
Add method	Adds a key to the Hashtable and its associated value. Its syntax is: Add(object key, object value) where key is the key to be added to the MultiMap, and value is the value to add to the internal ArrayList of the private map field.
Clear method	Removes all items from the MultiMap object.
Count method	Returns a count of all keys in the MultiMap object.
Clone method	Returns a deep copy of the MultiMap object.
ContainsKey method	Returns a bool indicating whether the MultiMap contains a particular value as its key. Its syntax is: ContainsValue(object value) where value is the key to be found in the MultiMap.
ContainsValue method	Returns a bool indicating whether the MultiMap contains a particular value. Its syntax is: ContainsValue(object value) where value is the object to be found in the MultiMap.
Remove method	Removes a key from the Hashtable and all its referent values in the internal valuesTable Hashtable. Its syntax is: Remove(object key) where key is the key to be removed.

Items may be added to a MultiMap object in the following manner:

public static void TestMultiMap( )
{
    string s = "foo";

    // Create and populate a MultiMap object
    MultiMap myMap = new MultiMap( );
    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 (DictionaryEntry entry in myMap)
    {
        Console.Write("Key: " + entry.Key.ToString( ) + "\tValue: ");
        foreach (object o in myMap[entry.Key])
        {
            Console.Write(o.ToString( ) + " : ");
        }
        Console.WriteLine( );
    }

    MultiMap otherMap = (MultiMap)myMap.Clone( );

    // 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 an ArrayList
    ArrayList testArray = new ArrayList( );
    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 (DictionaryEntry entry in myMap)
    {
        Console.Write("entry.Key: " + entry.Key.ToString( ) + 
                      "\tentry.Value(s): ");
        foreach (object o in myMap[entry.Key])
        {
            if (o == null)
            {
                Console.Write("null : ");
            }
            else
            {
                Console.Write(o.ToString( ) + " : ");
            }
        }
        Console.WriteLine( );
    }

    // Determine if the map contains the key("2") or the value("two")
    Console.WriteLine( );
    Console.WriteLine("myMap.ContainsKey(2): " + myMap.ContainsKey("2"));
    Console.WriteLine("myMap.ContainsValue(two): " + 
    myMap.ContainsValue("two"));

    // Clear all items from MultiMap
    myMap.Clear( );
}

This code displays the following:

Key: 2  Value: two :
Key: 3  Value: three : duplicate three : duplicate three :
Key: 0  Value: zero :
Key: 1  Value: one :
Key: 6  Value: foo :
Key: 4  Value:
Key: 5  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: 6    entry.Value(s): foo :
entry.Key: 4    entry.Value(s):
entry.Key: 5    entry.Value(s): foo :
entry.Key: 10   entry.Value(s): BAR : BAZ :

myMap.ContainsKey(2): True
myMap.ContainsValue(two): 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 class presented here operates similarly to a Hashtable. The MultiMap class contains a Hashtable field called map that contains the actual mapping of keys to values. Several of the MultiMap methods are delegated to the methods on the map Hashtable object.

A Hashtable 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 class. The private map field associates a key with a single ArrayList 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 object:

To remove a key using the Remove method, the key and ArrayList pair are removed from the map Hashtable. This allows removal of all values associated with a single key. The MultiMap.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.Clear method. This method removes all items from the map Hashtable.

The other major member of the MultiMap class to discuss is its indexer. The indexer returns the ArrayList of values for a particular key through its get accessor. The set accessor simply adds the ArrayList provided to a single key. This code creates an array of values and attempts to map them to key "5" in the myMap object:

ArrayList testArray = new ArrayList( );
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 is used to pull the ArrayList from the map Hashtable and the second indexer is used to obtain the value in the ArrayList. This code displays the following:

three
duplicate three
duplicate three

This MultiMap 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 (DictionaryEntry entry in myMap)
{
    Console.Write("Key: " + entry.Key.ToString( ) + "\tValue: ");
    foreach (object o in myMap[entry.Key])
    {
        Console.Write(o.ToString( ) + " : ");
    }
    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: 2  Value: two :
Key: 3  Value: three : duplicate three : duplicate three :
Key: 0  Value: zero :
Key: 1  Value: one :
Key: 4  Value:

There are two methods that allow searching of the MultiMap object: ContainsKey and ContainsValue. The ContainsKey method searches for the specified key in the map Hashtable. The ContainsValue method searches for the specified value in an ArrayList in the map Hashtable. 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 "ArrayList Class," "Hashtable Class," and "IEnumerator Interface" topics in the MSDN documentation.