Custom Implementation of ObservableDictionary

Question

I recently found myself in need of an IDictionary<TKey,TValue> implementation that was observable from a WPF UI. Since the .Net framework does not provide one, I rolled my own, but borrowed very heavily from what ObservableCollection<T> does on its own.

And since there is not generic implementation of OrderedDictionary where I can lookup by both index and key, I used 2 internal collections to provide for key lookup and indexed values.

// stores an indexed list of values in the collection
private readonly IList<TValue> values;
// stores the keys and the associated index
private readonly IDictionary<TKey, int> indexMap;

Here's the entire implementation:

public class ObservableDictionary<TKey, TValue> : IDictionary<TKey, TValue>, INotifyCollectionChanged, INotifyPropertyChanged
{
 private readonly IList<TValue> values;
 private readonly IDictionary<TKey, int> indexMap;
 private ObservableDictionary<TKey, TValue>.SimpleMonitor _monitor = new ObservableDictionary<TKey, TValue>.SimpleMonitor();
 private const string CountString = "Count";
 private const string IndexerName = "Item[]";
 private const string KeysString = "Keys";
 private const string ValuesString = "Values";
 #region Constructor
 public ObservableDictionary()
 {
 this.values = new List<TValue>();
 this.indexMap = new Dictionary<TKey, int>();
 }
 public ObservableDictionary(IDictionary<TKey, TValue> dictionary)
 {
 this.values = new List<TValue>();
 this.indexMap = new Dictionary<TKey, int>();
 int idx = 0;
 foreach (var kvp in dictionary)
 {
 this.indexMap.Add(kvp.Key, idx);
 this.values.Add(kvp.Value);
 idx++;
 }
 }
 public ObservableDictionary(int capacity)
 {
 this.values = new List<TValue>(capacity);
 this.indexMap = new Dictionary<TKey, int>(capacity);
 }
 #endregion
 #region Virtual Add/Remove/Change Control Methods
 protected virtual void AddItem(TKey key, TValue value)
 {
 this.CheckReentrancy();
 var index = this.values.Count;
 this.indexMap.Add(key, index);
 this.values.Add(value);
 this.OnPropertyChanged(CountString);
 this.OnPropertyChanged(KeysString);
 this.OnPropertyChanged(ValuesString);
 this.OnPropertyChanged(IndexerName);
 this.OnCollectionChanged(NotifyCollectionChangedAction.Add, key, value, index);
 }
 protected virtual bool RemoveItem(TKey key)
 {
 this.CheckReentrancy();
 var index = this.indexMap[key];
 var value = this.values[index];
 if (this.indexMap.Remove(key))
 {
 this.values.RemoveAt(index);
 var keys = this.indexMap.Keys.ToList();
 foreach (var existingKey in keys)
 {
 if (this.indexMap[existingKey] > index)
 this.indexMap[existingKey]--;
 }
 this.OnPropertyChanged(CountString);
 this.OnPropertyChanged(KeysString);
 this.OnPropertyChanged(ValuesString);
 this.OnPropertyChanged(IndexerName);
 this.OnCollectionChanged(NotifyCollectionChangedAction.Remove, key, value, index);
 return true;
 }
 return false;
 }
 protected virtual bool RemoveItem(KeyValuePair<TKey, TValue> item)
 {
 this.CheckReentrancy();
 if (this.indexMap.ContainsKey(item.Key) && this.values[this.indexMap[item.Key]].Equals(item.Value))
 {
 var index = this.indexMap[item.Key];
 var value = this.values[index];
 this.indexMap.Remove(item.Key);
 this.values.RemoveAt(index);
 var keys = this.indexMap.Keys.ToList();
 foreach (var existingKey in keys)
 {
 if (this.indexMap[existingKey] > index)
 this.indexMap[existingKey]--;
 }
 this.OnPropertyChanged(CountString);
 this.OnPropertyChanged(KeysString);
 this.OnPropertyChanged(ValuesString);
 this.OnPropertyChanged(IndexerName);
 this.OnCollectionChanged(NotifyCollectionChangedAction.Remove, item.Key, item.Value, index);
 return true;
 }
 return false;
 }
 protected virtual void RemoveAllItems()
 {
 this.CheckReentrancy();
 this.values.Clear();
 this.indexMap.Clear();
 this.OnPropertyChanged(CountString);
 this.OnPropertyChanged(KeysString);
 this.OnPropertyChanged(ValuesString);
 this.OnPropertyChanged(IndexerName);
 this.OnCollectionChanged(NotifyCollectionChangedAction.Reset);
 }
 protected virtual void ChangeItem(TKey key, TValue newValue)
 {
 this.CheckReentrancy();
 if (!this.indexMap.ContainsKey(key))
 this.AddItem(key, newValue);
 else
 {
 var index = this.indexMap[key];
 var oldValue = this.values[index];
 this.values[index] = newValue;
 this.OnPropertyChanged(ValuesString);
 this.OnPropertyChanged(IndexerName);
 this.OnCollectionChanged(NotifyCollectionChangedAction.Replace, key, oldValue, newValue, index);
 }
 }
 protected IDisposable BlockReentrancy()
 {
 this._monitor.Enter();
 return (IDisposable)this._monitor;
 }
 protected void CheckReentrancy()
 {
 // ISSUE: reference to a compiler-generated field
 // ISSUE: reference to a compiler-generated field
 if (this._monitor.Busy && this.CollectionChanged != null && this.CollectionChanged.GetInvocationList().Length > 1)
 throw new InvalidOperationException("ObservableCollectionReentrancyNotAllowed");
 }
 #endregion
 #region IDictionary<TKey,TValue> Members
 public void Add(TKey key, TValue value)
 {
 this.AddItem(key, value);
 }
 public bool ContainsKey(TKey key)
 {
 return this.indexMap.ContainsKey(key);
 }
 public bool Remove(TKey key)
 {
 return this.RemoveItem(key);
 }
 public bool TryGetValue(TKey key, out TValue value)
 {
 int index;
 if (this.indexMap.TryGetValue(key, out index))
 {
 value = this.values[index];
 return true;
 }
 else
 {
 value = default(TValue);
 return false;
 }
 }
 public ICollection<TKey> Keys
 {
 get { return this.indexMap.Keys; }
 }
 public ICollection<TValue> Values
 {
 get { return this.Values; }
 }
 public TValue this[TKey key]
 {
 get
 {
 var index = this.indexMap[key];
 return this.values[index];
 }
 set
 {
 this.ChangeItem(key, value);
 }
 }
 #endregion
 #region ICollection<KeyValuePair<TKey,TValue>> Members
 public void Clear()
 {
 this.RemoveAllItems();
 }
 public int Count
 {
 get { return this.indexMap.Count; }
 }
 void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> item)
 {
 this.Add(item.Key, item.Value);
 }
 bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> item)
 {
 return this.indexMap.ContainsKey(item.Key) && this.values[this.indexMap[item.Key]].Equals(item.Value);
 }
 void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
 {
 foreach (var kvp in this.indexMap)
 {
 array[arrayIndex] = new KeyValuePair<TKey, TValue>(kvp.Key, this.values[kvp.Value]);
 arrayIndex++;
 }
 }
 bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly
 {
 get { return false; }
 }
 bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> item)
 {
 return this.RemoveItem(item);
 }
 #endregion
 #region IEnumerable<KeyValuePair<TKey,TValue>> Members
 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
 {
 foreach (var kvp in this.indexMap)
 {
 var pair = new KeyValuePair<TKey, TValue>(kvp.Key, this.values[kvp.Value]);
 yield return pair;
 }
 }
 #endregion
 #region IEnumerable Members
 IEnumerator IEnumerable.GetEnumerator()
 {
 return this.GetEnumerator();
 }
 #endregion
 #region INotifyCollectionChanged Members
 public event NotifyCollectionChangedEventHandler CollectionChanged;
 protected void OnCollectionChanged(NotifyCollectionChangedEventArgs e)
 {
 var handler = CollectionChanged;
 using (this.BlockReentrancy())
 {
 handler(this, e);
 }
 }
 protected void OnCollectionChanged(NotifyCollectionChangedAction action)
 {
 this.OnCollectionChanged(new NotifyCollectionChangedEventArgs(action));
 }
 protected void OnCollectionChanged(NotifyCollectionChangedAction action, TKey key, TValue value, int index)
 {
 this.OnCollectionChanged(new NotifyCollectionChangedEventArgs(action, new KeyValuePair<TKey, TValue>(key, value), index));
 }
 protected void OnCollectionChanged(NotifyCollectionChangedAction action, TKey key, TValue oldValue, TValue newValue, int index)
 {
 var newPair = new KeyValuePair<TKey, TValue>(key, newValue);
 var oldPair = new KeyValuePair<TKey, TValue>(key, oldValue);
 this.OnCollectionChanged(new NotifyCollectionChangedEventArgs(action, newPair, oldPair, index));
 }
 #endregion
 #region INotifyPropertyChanged Members
 //Copied from Stack Overflow answer: http://stackoverflow.com/questions/1315621/implementing-inotifypropertychanged-does-a-better-way-exist/1316417#1316417
 //Author: Marc Gravell (http://stackoverflow.com/users/23354/marc-gravell)
 public event PropertyChangedEventHandler PropertyChanged;
 protected virtual void OnPropertyChanged(string propertyName)
 {
 PropertyChangedEventHandler handler = PropertyChanged;
 if (handler != null) handler(this, new PropertyChangedEventArgs(propertyName));
 }
 protected bool SetField<T>(ref T field, T value, [System.Runtime.CompilerServices.CallerMemberName] string propertyName = null)
 {
 if (EqualityComparer<T>.Default.Equals(field, value)) return false;
 field = value;
 OnPropertyChanged(propertyName);
 return true;
 }
 #endregion
 private class SimpleMonitor : IDisposable
 {
 private int _busyCount;
 public bool Busy
 {
 get
 {
 return this._busyCount > 0;
 }
 }
 public void Enter()
 {
 this._busyCount = this._busyCount + 1;
 }
 public void Dispose()
 {
 this._busyCount = this._busyCount - 1;
 }
 }
}

My testing shows this seems to behave exactly as I expect and the UI shows changes in the Dictionary as they occur, and my 2 internal collections remain in synch.

However, my testing experience is limited, so I am unsure if I have any hidden problems or if it can be broken by a unexpected usage. My biggest concern is my indexMap and my values collections somehow get out of synch and the index for a given key no longer points to the correct value in the values collection

Answer 1

There is a bug in the "Values" property. It should return this.values (lower case "v") not this.Values (upper case "V"). Also the collection returned may not represent the way ordered in the way indexMap would have returned. See remarks section at https://msdn.microsoft.com/en-us/library/0yxt5h4s(v=vs.110).aspx.

• psubsee2003: Looks like the Values error was just a typo in my code here. Thanks for catching it, but I'm not going to fix it in the question so I don't invalidate your answer. But the rest of the answer is good. Thanks for the heads up.

Answer 2

After my testing, I made a small change to the answer from @psubsee2003

protected void OnCollectionChanged( NotifyCollectionChangedEventArgs e )
 {
 // ISSUE: reference to a compiler-generated field
 if (this.CollectionChanged == null)
 return;
 using (this.BlockReentrancy())
 {
 // ISSUE: reference to a compiler-generated field
 this.CollectionChanged((object) this, e);
 }
 }

• Vogel612: Could you explain why your implementation changes the synchronization? The idiom used by the original code is pretty common. Note that your code is not safe from a NullReferenceException! if the Event Handler is changed after the nullcheck, but before the using-block, you still get an NRE. The original code does not have that issue, because it uses a local variable to atomically read the EventHandler and then operates on that one only.

Answer 3

I would suggest that AddItem(), RemoveItem(), RemoveAllItems() and ChangeItem() be updated to be thread-safe. Adding a lock in there should take care of that. This would have the added benefit in that your indexMap and values would remain in synch.

• willaien: Honestly, that's outside of the responsibility of a regular collection class. If you want an observable ConcurrentDictionary, that's one thing, but, not everything should be threadsafe by default.
• Brad Divine: It is the responsibility of the collection to remain internally consistent, which the lock would guarantee. I perhaps should have reversed the order of importance of the side effects (internally consistent first, threadsafe second)
• CodesInChaos: In addition to being outside the responsibility of the collection, the IDictionary interface is practically unusable in a multi-threaded scenario. There is a reason for ConcurrentDictionary having a different interface from a plain Dictionary.
• Brad Divine: ...ConcurrentDictionary implements IDictionary. msdn.microsoft.com/en-us/library/dd287191%28v=vs.110%29.aspx