Auto-filter for Microsoft WPF DataGrid

//******************************
// Written by Peter Golde
// Copyright (c) 2004-2005, Wintellect
//
// Use and restribution of this code is subject to the license agreement 
// contained in the file "License.txt" accompanying this file.
//******************************

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

namespace Wintellect.PowerCollections
{
    /// <summary>
    /// MultiDictionaryBase is a base class that can be used to more easily implement a class
    /// that associates multiple values to a single key. The class implements the generic
    /// IDictionary&lt;TKey, ICollection&lt;TValue&gt;&gt; interface. The resulting collection
    /// is read-only -- items cannot be added or removed.
    /// </summary>
    /// <remarks>
    /// <para>To use ReadOnlyMultiDictionaryBase as a base class, the derived class must override
    /// Count, Contains(TKey,TValue), EnumerateKeys, and TryEnumerateValuesForKey . </para>
    /// </remarks>
    /// <typeparam name="TKey">The key type of the dictionary.</typeparam>
    /// <typeparam name="TValue">The value type of the dictionary.</typeparam>
    [Serializable]
    [DebuggerDisplay("{DebuggerDisplayString()}")]
    public abstract class ReadOnlyMultiDictionaryBase<TKey, TValue> : ReadOnlyCollectionBase<KeyValuePair<TKey, ICollection<TValue>>>,
                                                                                               IDictionary<TKey, ICollection<TValue>>
    {
        /// <summary>
        /// Creates a new ReadOnlyMultiDictionaryBase. 
        /// </summary>
        protected ReadOnlyMultiDictionaryBase()
        {
        }

        /// <summary>
        /// Throws an NotSupportedException stating that this collection cannot be modified.
        /// </summary>
        private void MethodModifiesCollection()
        {
            throw new NotSupportedException(string.Format(Strings.CannotModifyCollection, Util.SimpleClassName(this.GetType())));
        }

        /// <summary>
        /// Gets the number of keys in the dictionary. This property must be overridden
        /// in the derived class.
        /// </summary>
        public abstract override int Count
        {
            get;
        }

        /// <summary>
        /// Enumerate all the keys in the dictionary. This method must be overridden by a derived
        /// class.
        /// </summary>
        /// <returns>An IEnumerator&lt;TKey&gt; that enumerates all of the keys in the collection that
        /// have at least one value associated with them.</returns>
        protected abstract IEnumerator<TKey> EnumerateKeys();

        /// <summary>
        /// Enumerate all of the values associated with a given key. This method must be overridden
        /// by the derived class. If the key exists and has values associated with it, an enumerator for those
        /// values is returned throught <paramref name="values"/>. If the key does not exist, false is returned.
        /// </summary>
        /// <param name="key">The key to get values for.</param>
        /// <param name="values">If true is returned, this parameter receives an enumerators that
        /// enumerates the values associated with that key.</param>
        /// <returns>True if the key exists and has values associated with it. False otherwise.</returns>
        protected abstract bool TryEnumerateValuesForKey(TKey key, out IEnumerator<TValue> values);

        /// <summary>
        /// Implements IDictionary&lt;TKey, IEnumerable&lt;TValue&gt;&gt;.Add. If the 
        /// key is already present, and ArgumentException is thrown. Otherwise, a
        /// new key is added, and new values are associated with that key.
        /// </summary>
        /// <param name="key">Key to add.</param>
        /// <param name="values">Values to associate with that key.</param>
        /// <exception cref="ArgumentException">The key is already present in the dictionary.</exception>
        void IDictionary<TKey, ICollection<TValue>>.Add(TKey key, ICollection<TValue> values)
        {
            MethodModifiesCollection();
        }

        /// <summary>
        /// Removes a key from the dictionary. This method must be overridden in the derived class.
        /// </summary>
        /// <param name="key">Key to remove from the dictionary.</param>
        /// <returns>True if the key was found, false otherwise.</returns>
        bool IDictionary<TKey, ICollection<TValue>>.Remove(TKey key)
        {
            MethodModifiesCollection();
            return false;  // never reached.
        }

        /// <summary>
        /// Determines if this dictionary contains a key equal to <paramref name="key"/>. If so, all the values
        /// associated with that key are returned through the values parameter. This method must be
        /// overridden by the derived class.
        /// </summary>
        /// <param name="key">The key to search for.</param>
        /// <param name="values">Returns all values associated with key, if true was returned.</param>
        /// <returns>True if the dictionary contains key. False if the dictionary does not contain key.</returns>
        bool IDictionary<TKey, ICollection<TValue>>.TryGetValue(TKey key, out ICollection<TValue> values)
        {
            if (ContainsKey(key)) {
                values = this[key];
                return true;
            }
            else {
                values = null;
                return false;
            }
        }

        /// <summary>
        /// Determines whether a given key is found in the dictionary.
        /// </summary>
        /// <remarks>The default implementation simply calls TryGetValue.
        /// It may be appropriate to override this method to 
        /// provide a more efficient implementation.</remarks>
        /// <param name="key">Key to look for in the dictionary.</param>
        /// <returns>True if the key is present in the dictionary.</returns>
        public virtual bool ContainsKey(TKey key)
        {
            IEnumerator<TValue> values;
            return TryEnumerateValuesForKey(key, out values);
        }

        /// <summary>
        /// Determines if this dictionary contains a key-value pair equal to <paramref name="key"/> and 
        /// <paramref name="value"/>. The dictionary is not changed. This method must be overridden in the derived class.
        /// </summary>
        /// <param name="key">The key to search for.</param>
        /// <param name="value">The value to search for.</param>
        /// <returns>True if the dictionary has associated <paramref name="value"/> with <paramref name="key"/>.</returns>
        public abstract bool Contains(TKey key, TValue value);

        /// <summary>
        /// Determines if this dictionary contains the given key and all of the values associated with that key..
        /// </summary>
        /// <param name="pair">A key and collection of values to search for.</param>
        /// <returns>True if the dictionary has associated all of the values in <paramref name="pair"/>.Value with <paramref name="pair"/>.Key.</returns>
        public override bool Contains(KeyValuePair<TKey, ICollection<TValue>> pair)
        {
            foreach (TValue val in pair.Value) {
                if (!Contains(pair.Key, val))
                    return false;
            }

            return true;
        }

        // Cache the equality comparer after we get it the first time.
        private volatile IEqualityComparer<TValue> valueEqualityComparer;

        /// <summary>
        /// If the derived class does not use the default comparison for values, this
        /// methods should be overridden to compare two values for equality. This is
        /// used for the correct implementation of ICollection.Contains on the Values
        /// and KeyValuePairs collections.
        /// </summary>
        /// <param name="value1">First value to compare.</param>
        /// <param name="value2">Second value to compare.</param>
        /// <returns>True if the values are equal.</returns>
        protected virtual bool EqualValues(TValue value1, TValue value2)
        {
            if (valueEqualityComparer == null)
                valueEqualityComparer = EqualityComparer<TValue>.Default;
            return valueEqualityComparer.Equals(value1, value2);
        }

        /// <summary>
        /// Gets a count of the number of values associated with a key. The
        /// default implementation is slow; it enumerators all of the values
        /// (using TryEnumerateValuesForKey) to count them. A derived class
        /// may be able to supply a more efficient implementation.
        /// </summary>
        /// <param name="key">The key to count values for.</param>
        /// <returns>The number of values associated with <paramref name="key"/>.</returns>
        protected virtual int CountValues(TKey key)
        {
            int count = 0;
            IEnumerator<TValue> enumValues;

            if (TryEnumerateValuesForKey(key, out enumValues)) {
                using (enumValues) {
                    while (enumValues.MoveNext())
                        count += 1;
                }
            }

            return count;
        }

        /// <summary>
        /// Gets a total count of values in the collection. This default implementation
        /// is slow; it enumerates all of the keys in the dictionary and calls CountValues on each.
        /// A derived class may be able to supply a more efficient implementation.
        /// </summary>
        /// <returns>The total number of values associated with all keys in the dictionary.</returns>
        protected virtual int CountAllValues()
        {
            int count = 0;

            using (IEnumerator<TKey> enumKeys = EnumerateKeys()) {
                while (enumKeys.MoveNext()) {
                    TKey key = enumKeys.Current;
                    count += CountValues(key);
                }
            }

            return count;
        }

        /// <summary>
        /// Gets a read-only collection all the keys in this dictionary.
        /// </summary>
        /// <value>An readonly ICollection&lt;TKey&gt; of all the keys in this dictionary.</value>
        public virtual ICollection<TKey> Keys
        {
            get { return new KeysCollection(this); }
        }

        /// <summary>
        /// Gets a read-only collection of all the values in the dictionary. 
        /// </summary>
        /// <returns>A read-only ICollection&lt;TValue&gt; of all the values in the dictionary.</returns>
        public virtual ICollection<TValue> Values
        {
            get { return new ValuesCollection(this); }
        }

        /// <summary>
        /// Gets a read-only collection of all the value collections in the dictionary. 
        /// </summary>
        /// <returns>A read-only ICollection&lt;IEnumerable&lt;TValue&gt;&gt; of all the values in the dictionary.</returns>
        ICollection<ICollection<TValue>> IDictionary<TKey, ICollection<TValue>>.Values
        {
            get { return new EnumerableValuesCollection(this); }
        }

        /// <summary>
        /// Gets a read-only collection of all key-value pairs in the dictionary. If a key has multiple
        /// values associated with it, then a key-value pair is present for each value associated
        /// with the key.
        /// </summary>
        public virtual ICollection<KeyValuePair<TKey, TValue>> KeyValuePairs
        {
            get { return new KeyValuePairsCollection(this); }
        }

        /// <summary>
        /// Returns a collection of all of the values in the dictionary associated with <paramref name="key"/>.
        /// If the key is not present in the dictionary, an ICollection with no
        /// values is returned. The returned ICollection is read-only.
        /// </summary>
        /// <param name="key">The key to get the values associated with.</param>
        /// <value>An ICollection&lt;TValue&gt; with all the values associated with <paramref name="key"/>.</value>
        public virtual ICollection<TValue> this[TKey key]
        {
            get
            {
                return new ValuesForKeyCollection(this, key);
            }
        }

        /// <summary>
        /// Gets a collection of all the values in the dictionary associated with <paramref name="key"/>.
        /// If the key is not present in the dictionary, a KeyNotFound exception is thrown.
        /// </summary>
        /// <param name="key">The key to get the values associated with.</param>
        /// <value>An IEnumerable&lt;TValue&gt; that enumerates all the values associated with <paramref name="key"/>.</value>
        /// <exception cref="KeyNotFoundException">The given key is not present in the dictionary.</exception>
        /// <exception cref="NotSupportedException">The set accessor is called.</exception>
        ICollection<TValue> IDictionary<TKey, ICollection<TValue>>.this[TKey key]
        {
            get
            {
                if (ContainsKey(key))
                    return new ValuesForKeyCollection(this, key);
                else
                    throw new KeyNotFoundException(Strings.KeyNotFound);
            }
            set
            {
                MethodModifiesCollection();
            }
        }

        /// <summary>
        /// Shows the string representation of the dictionary. The string representation contains
        /// a list of the mappings in the dictionary.
        /// </summary>
        /// <returns>The string representation of the dictionary.</returns>
        public override string ToString()
        {
            bool firstItem = true;

            System.Text.StringBuilder builder = new System.Text.StringBuilder();

            builder.Append("{");

            // Call ToString on each item and put it in.
            foreach (KeyValuePair<TKey, ICollection<TValue>> pair in this) {
                if (!firstItem)
                    builder.Append(", ");

                if (pair.Key == null)
                    builder.Append("null");
                else
                    builder.Append(pair.Key.ToString());

                builder.Append("->");

                // Put all values in a parenthesized list.
                builder.Append('(');

                bool firstValue = true;
                foreach (TValue val in pair.Value) {
                    if (!firstValue)
                        builder.Append(",");

                    if (val == null)
                        builder.Append("null");
                    else
                        builder.Append(val.ToString());

                    firstValue = false;
                }

                builder.Append(')');

                firstItem = false;
            }

            builder.Append("}");
            return builder.ToString();
        }

        /// <summary>
        /// Display the contents of the dictionary in the debugger. This is intentionally private, it is called
        /// only from the debugger due to the presence of the DebuggerDisplay attribute. It is similar
        /// format to ToString(), but is limited to 250-300 characters or so, so as not to overload the debugger.
        /// </summary>
        /// <returns>The string representation of the items in the collection, similar in format to ToString().</returns>
        new internal string DebuggerDisplayString()
        {
            const int MAXLENGTH = 250;

            bool firstItem = true;

            System.Text.StringBuilder builder = new System.Text.StringBuilder();

            builder.Append("{");

            // Call ToString on each item and put it in.
            foreach (KeyValuePair<TKey, ICollection<TValue>> pair in this) {
                if (builder.Length >= MAXLENGTH) {
                    builder.Append(", ...");
                    break;
                }

                if (!firstItem)
                    builder.Append(", ");

                if (pair.Key == null)
                    builder.Append("null");
                else
                    builder.Append(pair.Key.ToString());

                builder.Append("->");

                // Put all values in a parenthesized list.
                builder.Append('(');

                bool firstValue = true;
                foreach (TValue val in pair.Value) {
                    if (!firstValue)
                        builder.Append(",");

                    if (val == null)
                        builder.Append("null");
                    else
                        builder.Append(val.ToString());

                    firstValue = false;
                }

                builder.Append(')');

                firstItem = false;
            }

            builder.Append("}");
            return builder.ToString();
        }


        /// <summary>
        /// Enumerate all the keys in the dictionary, and for each key, the collection of values for that key.
        /// </summary>
        /// <returns>An enumerator to enumerate all the key, ICollection&lt;value&gt; pairs in the dictionary.</returns>
        public override IEnumerator<KeyValuePair<TKey, ICollection<TValue>>> GetEnumerator()
        {
            using (IEnumerator<TKey> enumKeys = EnumerateKeys()) {
                while (enumKeys.MoveNext()) {
                    TKey key = enumKeys.Current;
                    yield return new KeyValuePair<TKey, ICollection<TValue>>(key, new ValuesForKeyCollection(this, key));
                }
            }
        }


        #region Keys and Values collections
        /// <summary>
        /// A private class that provides the ICollection&lt;TValue&gt; for a particular key. This is the collection
        /// that is returned from the indexer. The collections is read-write, live, and can be used to add, remove,
        /// etc. values from the multi-dictionary.
        /// </summary>
        [Serializable]
        private sealed class ValuesForKeyCollection : ReadOnlyCollectionBase<TValue>
        {
            private ReadOnlyMultiDictionaryBase<TKey, TValue> myDictionary;
            private TKey key;

            /// <summary>
            /// Constructor. Initializes this collection.
            /// </summary>
            /// <param name="myDictionary">Dictionary we're using.</param>
            /// <param name="key">The key we're looking at.</param>
            public ValuesForKeyCollection(ReadOnlyMultiDictionaryBase<TKey, TValue> myDictionary, TKey key)
            {
                this.myDictionary = myDictionary;
                this.key = key;
            }

            /// <summary>
            /// Get the number of values associated with the key.
            /// </summary>
            public override int Count
            {
                get
                {
                    return myDictionary.CountValues(key);
                }
            }

            /// <summary>
            /// A simple function that returns an IEnumerator&lt;TValue&gt; that
            /// doesn't yield any values. A helper.
            /// </summary>
            /// <returns>An IEnumerator&lt;TValue&gt; that yields no values.</returns>
            private IEnumerator<TValue> NoValues()
            {
                yield break;
            }

            /// <summary>
            /// Enumerate all the values associated with key.
            /// </summary>
            /// <returns>An IEnumerator&lt;TValue&gt; that enumerates all the values associated with key.</returns>
            public override IEnumerator<TValue> GetEnumerator()
            {
                IEnumerator<TValue> values;
                if (myDictionary.TryEnumerateValuesForKey(key, out values))
                    return values;
                else
                    return NoValues();
            }

            /// <summary>
            /// Determines if the given values is associated with key.
            /// </summary>
            /// <param name="item">Value to check for.</param>
            /// <returns>True if value is associated with key, false otherwise.</returns>
            public override bool Contains(TValue item)
            {
                return myDictionary.Contains(key, item);
            }
        }


        /// <summary>
        /// A private class that implements ICollection&lt;TKey&gt; and ICollection for the
        /// Keys collection. The collection is read-only.
        /// </summary>
        [Serializable]
        private sealed class KeysCollection : ReadOnlyCollectionBase<TKey>
        {
            private ReadOnlyMultiDictionaryBase<TKey, TValue> myDictionary;

            /// <summary>
            /// Constructor.
            /// </summary>
            /// <param name="myDictionary">The dictionary this is associated with.</param>
            public KeysCollection(ReadOnlyMultiDictionaryBase<TKey, TValue> myDictionary)
            {
                this.myDictionary = myDictionary;
            }

            public override int Count
            {
                get { return myDictionary.Count; }
            }

            public override IEnumerator<TKey> GetEnumerator()
            {
                return myDictionary.EnumerateKeys();
            }

            public override bool Contains(TKey key)
            {
                return myDictionary.ContainsKey(key);
            }
        }

        /// <summary>
        /// A private class that implements ICollection&lt;TValue&gt; and ICollection for the
        /// Values collection. The collection is read-only.
        /// </summary>
        [Serializable]
        private sealed class ValuesCollection : ReadOnlyCollectionBase<TValue>
        {
            private ReadOnlyMultiDictionaryBase<TKey, TValue> myDictionary;

            public ValuesCollection(ReadOnlyMultiDictionaryBase<TKey, TValue> myDictionary)
            {
                this.myDictionary = myDictionary;
            }

            public override int Count
            {
                get { return myDictionary.CountAllValues(); }
            }

            public override IEnumerator<TValue> GetEnumerator()
            {
                using (IEnumerator<TKey> enumKeys = myDictionary.EnumerateKeys()) {
                    while (enumKeys.MoveNext()) {
                        TKey key = enumKeys.Current;
                        IEnumerator<TValue> enumValues;
                        if (myDictionary.TryEnumerateValuesForKey(key, out enumValues)) {
                            using (enumValues) {
                                while (enumValues.MoveNext())
                                    yield return enumValues.Current;
                            }
                        }
                    }
                }
            }

            public override bool Contains(TValue value)
            {
                foreach (TValue v in this) {
                    if (myDictionary.EqualValues(v, value))
                        return true;
                }
                return false;
            }
        }

        /// <summary>
        /// A private class that implements ICollection&lt;IEnumerable&lt;TValue&gt;&gt; and ICollection for the
        /// Values collection on IDictionary. The collection is read-only.
        /// </summary>
        [Serializable]
        private sealed class EnumerableValuesCollection : ReadOnlyCollectionBase<ICollection<TValue>>
        {
            private ReadOnlyMultiDictionaryBase<TKey, TValue> myDictionary;

            public EnumerableValuesCollection(ReadOnlyMultiDictionaryBase<TKey, TValue> myDictionary)
            {
                this.myDictionary = myDictionary;
            }

            public override int Count
            {
                get { return myDictionary.Count; }
            }

            public override IEnumerator<ICollection<TValue>> GetEnumerator()
            {
                using (IEnumerator<TKey> enumKeys = myDictionary.EnumerateKeys()) {
                    while (enumKeys.MoveNext()) {
                        TKey key = enumKeys.Current;
                        yield return new ValuesForKeyCollection(myDictionary, key);
                    }
                }
            }

            public override bool Contains(ICollection<TValue> values)
            {
                if (values == null)
                    return false;
                TValue[] valueArray = Algorithms.ToArray(values);

                foreach (ICollection<TValue> v in this) {
                    if (v.Count != valueArray.Length)
                        continue;

                    // First check in order for efficiency.
                    if (Algorithms.EqualCollections(v, values, myDictionary.EqualValues))
                        return true;

                    // Now check not in order. We can't use Algorithms.EqualSets, because we don't 
                    // have an IEqualityComparer, just the ability to compare for equality. Unfortunately this is N squared,
                    // but there isn't a good choice here. We don't really expect this method to be used much.
                    bool[] found = new bool[valueArray.Length];
                    foreach (TValue x in v) {
                        for (int i = 0; i < valueArray.Length; ++i) {
                            if (!found[i] && myDictionary.EqualValues(x, valueArray[i])) 
                                found[i] = true;
                        }
                    }

                    if (Array.IndexOf(found, false) < 0)
                        return true;  // every item was found. The sets must be equal.
                }
                return false;
            }
        }

        /// <summary>
        /// A private class that implements ICollection&lt;KeyValuePair&lt;TKey,TValue&gt;&gt; and ICollection for the
        /// KeyValuePairs collection. The collection is read-only.
        /// </summary>
        [Serializable]
        private sealed class KeyValuePairsCollection : ReadOnlyCollectionBase<KeyValuePair<TKey, TValue>>
        {
            private ReadOnlyMultiDictionaryBase<TKey, TValue> myDictionary;

            public KeyValuePairsCollection(ReadOnlyMultiDictionaryBase<TKey, TValue> myDictionary)
            {
                this.myDictionary = myDictionary;
            }

            public override int Count
            {
                get { return myDictionary.CountAllValues(); }
            }

            public override IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
            {
                using (IEnumerator<TKey> enumKeys = myDictionary.EnumerateKeys()) {
                    while (enumKeys.MoveNext()) {
                        TKey key = enumKeys.Current;
                        IEnumerator<TValue> enumValues;
                        if (myDictionary.TryEnumerateValuesForKey(key, out enumValues)) {
                            using (enumValues) {
                                while (enumValues.MoveNext())
                                    yield return new KeyValuePair<TKey, TValue>(key, enumValues.Current);
                            }
                        }
                    }
                }
            }

            public override bool Contains(KeyValuePair<TKey, TValue> pair)
            {
                return myDictionary[pair.Key].Contains(pair.Value);
            }
        }

        #endregion



    }

}