4
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – psubsee2003 May 7 '16 at 9:21
0
\$\begingroup\$

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);
        }
    }
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Vogel612 Aug 28 '18 at 9:27
-1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – willaien Jan 14 '16 at 16:42
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – Brad Divine Jan 14 '16 at 23:33
  • \$\begingroup\$ 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. \$\endgroup\$ – CodesInChaos Apr 13 '16 at 14:34
  • \$\begingroup\$ ...ConcurrentDictionary implements IDictionary. msdn.microsoft.com/en-us/library/dd287191%28v=vs.110%29.aspx \$\endgroup\$ – Brad Divine Apr 14 '16 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.