Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

.NET

The C5 Generic Collection Library


A Multidictionary Example

A multidictionary is a dictionary that maps a key to a set of values. Multidictionaries are found in the C++ Standard Template Library and in Peter Golde's PowerCollections for .NET. The C5 collection library does not include a multidictionary implementation, but one can easily be built from the given dictionary and set classes. Here we show how all operations can be efficient thanks to listenable update events.

A hash-based multidictionary with key type K and value type V can be declared by deriving from a hash-based dictionary whose key type is K and whose value type is a collection of V:



public class MultiHashDictionary<K,V> : 
     HashDictionary<K, ICollection<V>> {
  ...
}


The multidictionary should override the Contains(K) method, which tests whether a given key is associated with any value:


public override bool Contains(K k) {
   ICollection<V> values;
   return base.Find(k, out values) 
     && values != null && !values.IsEmpty;
}


The call base.Find(k, out values) returns True if key k is in the dictionary and if so, binds the associated value to values; otherwise, it returns False. The inherited Contains method cannot be used because it will also return True if k is associated with a null reference or with an empty collection.

Similarly, the multidictionary's indexer this[k] should be overridden to return a new empty collection when k is not associated with any collection, or is associated with a null reference. Moreover, the multidictionary should have a new method Add(K,V) to add a single (key, value) pair:


public virtual void Add(K k, V v) {
   ICollection<V> values;
   if (!base.Find(k, out values) 
         || values == null) {
      values = new HashSet<V>();
      Add(k, values);
   }
   values.Add(v);
}


The negated call !base.Find(k, out values) returns False if key k is in the dictionary; if so, it binds the associated value to values. Otherwise, it returns True. It is worthwhile to contrast the new Add method with the inherited one, which has signature Add(K, ICollection<V>) and can be used only to associate an entire collection with key k.

Note that the Add method uses new HashSet<V>() to create a new hash-based set containing the value v when inserting a key k not already in the dictionary. It might as well have created a hash-based bag, a tree-based set, a tree-based bag, or some other collection of items of type V. This is part of the reason why the C5 library does not provide a multidictionary as a predefined type: Many different kinds of multidictionaries can be constructed, and the C5 library provides the components to construct the one you want. In fact, this multidictionary class could be generalized by adding a further generic parameter W, which should stand for the desired type of value collection:


public class MultiHashDictionary<K, V, W> 
     : HashDictionary<K, W>
   where W : ICollection<V>, new()
{ ... }


In the implementation { ... } of the multidictionary, we just need to replace new HashSet<V>() with new W(), and voilà, we have a typesafe and general multidictionary implementation that works for W being tree set, tree bag, hash set, hash bag, hashed linked list, and so on. Similar to the new Add(K,V) method, there should be a new method Remove(K,V) to remove a single (key, value) pair; it uses much the same logic.

The only thing missing from our multidictionary collection is a Count property that returns the total number of (key, value) pairs in the multidictionary. The inherited Count property returns the number of (key, value set) pairs in the base dictionary, which may be both smaller and larger than the number of (key, value) pairs. The straightforward way to compute Count is to sum the counts of all value sets, as in Listing Three(a). However, this takes time linear in the number of keys in the multidictionary. If the Count property needs to be computed frequently, this may be very slow. We could address this problem by adding a private field count to the MultiDictionary<K,V> class, and then override methods in the multidictionary to try to keep the count field up to date. However, this does not work because one may add items to a value set without calling any methods on the multidictionary. Also, a value set may be associated with more than one key in the multidictionary, so that each addition or removal should be counted more than once. What can you do?

(a)
public new virtual int Count {
   get {
      int count = 0;
      foreach (KeyValuePair<K,ICollection<V>> entry in this)
        if (entry.Value != null)
          count += entry.Value.Count;
      return count;
   }
}

(b)
public class MultiHashDictionary<K,V> : HashDictionary<K, ICollection<V>> {
   private int count = 0; // Cached value count, updated by events only
   private void IncrementCount(Object sender, ItemCountEventArgs<V> args) {
      count += args.Count;
   }
   private void DecrementCount(Object sender, ItemCountEventArgs<V> args) ...
   private void ClearedCount(Object sender, ClearedEventArgs args) ...
   public MultiHashDictionary() {
      ItemsAdded +=
         delegate(Object sender,
            ItemCountEventArgs<KeyValuePair<K,ICollection<V>>> args) {
         ICollection<V> values = args.Item.Value;
         if (values != null) {
            count += values.Count;
            values.ItemsAdded += IncrementCount;
            values.ItemsRemoved += DecrementCount;
            values.CollectionCleared += ClearedCount;
            }
         };
      ItemsRemoved += ...; // Similar to ItemsAdded
   }
   ...
}
Listing Three

The solution is straightforward—use C5's collection update events. We declare event handlers for adding and removing items from a value set and for clearing a value set, and attach all three event handlers to every value set. But how do we make sure to attach these handlers to every value set, regardless of how and by whom it was created? We use collection update events once more, this time attaching event listeners not to the value sets but to the base dictionary. When a value set is added to the dictionary, the three value set event listeners get attached to the value set, and if the value set is later removed again, then the event listeners get detached. This automatically handles the case where the same value set is associated with multiple keys in the base dictionary. Listing Three(b) presents a solution. Now it is easy to define a constant-time Count property; it simply returns the count field:


public new virtual int Count {
   get { return count; }
}


Clearly, it is worthwhile to install all the event listeners and maintain the count field only if the Count property may be called often. The point of the example is that the C5 library provides a safe and transparent means for maintaining derived fields (such as count), whereas other collection libraries do not.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.