Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Auto-filter for Microsoft WPF DataGrid

, 29 Jan 2009 Eclipse
Allows auto filtering functionality for DataGrid columns.
WPFGridFilter.zip
WPFGridFilter
PowerCollections
PowerCollections.csproj.user
Properties
Stepi.Collections
bin
Filters
Properties
Stepi.UIFilters
bin
Initializers
Properties
Settings.settings
Themes
Test.GridSorting
bin
Debug
Test.GridFilter.vshost.exe
Properties
Settings.settings
//******************************
// 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;

namespace Wintellect.PowerCollections
{
    /// <summary>
    /// <para>The OrderedMultiDictionary class that associates values with a key. Unlike an OrderedDictionary,
    /// each key can have multiple values associated with it. When indexing an OrderedMultidictionary, instead
    /// of a single value associated with a key, you retrieve an enumeration of values.</para>
    /// <para>All of the key are stored in sorted order. Also, the values associated with a given key 
    /// are kept in sorted order as well.</para>
    /// <para>When constructed, you can chose to allow the same value to be associated with a key multiple
    /// times, or only one time. </para>
    /// </summary>
    /// <typeparam name="TKey">The type of the keys.</typeparam>
    /// <typeparam name="TValue">The of values associated with the keys.</typeparam>
    ///<seealso cref="MultiDictionary&lt;TKey,TValue&gt;"/>
    ///<seealso cref="OrderedDictionary&lt;TKey,TValue&gt;"/>
    [Serializable]
    public class OrderedMultiDictionary<TKey, TValue> : MultiDictionaryBase<TKey, TValue>, ICloneable
    {
        // The comparer for comparing keys
        private IComparer<TKey> keyComparer;

        // The comparer for comparing values;
        private IComparer<TValue> valueComparer;

        // The comparer for comparing key-value pairs. Ordered by keys, then by values
        private IComparer<KeyValuePair<TKey, TValue>> comparer;

        // The red-black tree that stores the keys and values. Each key-value pair is stored as a separate item,
        // sorted first by keys, then by value. Thus, all values associated with a given key are stored together.
        private RedBlackTree<KeyValuePair<TKey, TValue>> tree;

        // Whether duplicate values for the same key are allowed.
        private bool allowDuplicateValues;      

        // Total number of keys in the tree.
        private int keyCount;

        /// <summary>
        /// Helper function to create a new KeyValuePair struct.
        /// </summary>
        /// <param name="key">The key.</param>
        /// <param name="value">The value.</param>
        /// <returns>A new KeyValuePair.</returns>
        private static KeyValuePair<TKey, TValue> NewPair(TKey key, TValue value)
        {
            KeyValuePair<TKey, TValue> pair = new KeyValuePair<TKey,TValue>(key, value);
            return pair;
        }

        /// <summary>
        /// Helper function to create a new KeyValuePair struct with a default value.
        /// </summary>
        /// <param name="key">The key.</param>
        /// <returns>A new KeyValuePair.</returns>
        private static KeyValuePair<TKey, TValue> NewPair(TKey key)
        {
            KeyValuePair<TKey, TValue> pair = new KeyValuePair<TKey, TValue>(key, default(TValue));
            return pair;
        }

        /// <summary>
        /// Get a RangeTester that maps to the range of all items with the 
        /// given key.
        /// </summary>
        /// <param name="key">Key in the given range.</param>
        /// <returns>A RangeTester delegate that selects the range of items with that range.</returns>
        private RedBlackTree<KeyValuePair<TKey,TValue>>.RangeTester KeyRange(TKey key)
        {
            return delegate(KeyValuePair<TKey,TValue> pair) {
                return keyComparer.Compare(pair.Key, key);
            };
        }

        /// <summary>
        /// Gets a range tester that defines a range by first and last items.
        /// </summary>
        /// <param name="first">The lower bound.</param>
        /// <param name="firstInclusive">True if the lower bound is inclusive, false if exclusive.</param>
        /// <param name="last">The upper bound.</param>
        /// <param name="lastInclusive">True if the upper bound is inclusive, false if exclusive.</param>
        /// <returns>A RangeTester delegate that tests for a key in the given range.</returns>
        private RedBlackTree<KeyValuePair<TKey, TValue>>.RangeTester DoubleBoundedKeyRangeTester(TKey first, bool firstInclusive, TKey last, bool lastInclusive)
        {
            return delegate(KeyValuePair<TKey, TValue> pair) {
                if (firstInclusive) {
                    if (keyComparer.Compare(first, pair.Key) > 0)
                        return -1;     // item is before first.
                }
                else {
                    if (keyComparer.Compare(first, pair.Key) >= 0)
                        return -1;     // item is before or equal to first.
                }

                if (lastInclusive) {
                    if (keyComparer.Compare(last, pair.Key) < 0)
                        return 1;      // item is after last.
                }
                else {
                    if (keyComparer.Compare(last, pair.Key) <= 0)
                        return 1;      // item is after or equal to last
                }

                return 0;      // item is between first and last.
            };
        }


        /// <summary>
        /// Gets a range tester that defines a range by a lower bound.
        /// </summary>
        /// <param name="first">The lower bound.</param>
        /// <param name="inclusive">True if the lower bound is inclusive, false if exclusive.</param>
        /// <returns>A RangeTester delegate that tests for a key in the given range.</returns>
        private RedBlackTree<KeyValuePair<TKey, TValue>>.RangeTester LowerBoundedKeyRangeTester(TKey first, bool inclusive)
        {
            return delegate(KeyValuePair<TKey, TValue> pair) {
                if (inclusive) {
                    if (keyComparer.Compare(first, pair.Key) > 0)
                        return -1;     // item is before first.
                    else
                        return 0;      // item is after or equal to first
                }
                else {
                    if (keyComparer.Compare(first, pair.Key) >= 0)
                        return -1;     // item is before or equal to first.
                    else
                        return 0;      // item is after first
                }
            };
        }


        /// <summary>
        /// Gets a range tester that defines a range by upper bound.
        /// </summary>
        /// <param name="last">The upper bound.</param>
        /// <param name="inclusive">True if the upper bound is inclusive, false if exclusive.</param>
        /// <returns>A RangeTester delegate that tests for a key in the given range.</returns>
        private RedBlackTree<KeyValuePair<TKey, TValue>>.RangeTester UpperBoundedKeyRangeTester(TKey last, bool inclusive)
        {
            return delegate(KeyValuePair<TKey, TValue> pair) {
                if (inclusive) {
                    if (keyComparer.Compare(last, pair.Key) < 0)
                        return 1;      // item is after last.
                    else
                        return 0;      // item is before or equal to last.
                }
                else {
                    if (keyComparer.Compare(last, pair.Key) <= 0)
                        return 1;      // item is after or equal to last
                    else
                        return 0;      // item is before last.
                }
            };
        }

       #region Constructors

        /// <summary>
        /// Create a new OrderedMultiDictionary. The default ordering of keys and values are used. If duplicate values
        /// are allowed, multiple copies of the same value can be associated with the same key. For example, the key "foo"
        /// could have "a", "a", and "b" associated with it. If duplicate values are not allowed, only one copies of a given value can
        /// be associated with the same key, although different keys can have the same value. For example, the key "foo" could
        /// have "a" and "b" associated with it, which key "bar" has values "b" and "c" associated with it.
        /// </summary>
        /// <remarks>The default ordering of keys and values will be used, as defined by TKey and TValue's implementation
        /// of IComparable&lt;T&gt; (or IComparable if IComparable&lt;T&gt; is not implemented). If a different ordering should be
        /// used, other constructors allow a custom Comparer or IComparer to be passed to changed the ordering.</remarks>
        /// <param name="allowDuplicateValues">Can the same value be associated with a key multiple times?</param>
        /// <exception cref="InvalidOperationException">TKey or TValue does not implement either IComparable&lt;T&gt; or IComparable.</exception>
        public OrderedMultiDictionary(bool allowDuplicateValues)
            : this(allowDuplicateValues, Comparers.DefaultComparer<TKey>(), Comparers.DefaultComparer<TValue>())
        {
        }

        /// <summary>
        /// Create a new OrderedMultiDictionary. If duplicate values
        /// are allowed, multiple copies of the same value can be associated with the same key. For example, the key "foo"
        /// could have "a", "a", and "b" associated with it. If duplicate values are not allowed, only one copies of a given value can
        /// be associated with the same key, although different keys can have the same value. For example, the key "foo" could
        /// have "a" and "b" associated with it, which key "bar" has values "b" and "c" associated with it.
        /// </summary>
        /// <param name="allowDuplicateValues">Can the same value be associated with a key multiple times?</param>
        /// <param name="keyComparison">A delegate to a method that will be used to compare keys.</param>
        /// <exception cref="InvalidOperationException">TValue does not implement either IComparable&lt;TValue&gt; or IComparable.</exception>
        public OrderedMultiDictionary(bool allowDuplicateValues, Comparison<TKey> keyComparison)
            : this(allowDuplicateValues, Comparers.ComparerFromComparison(keyComparison), Comparers.DefaultComparer<TValue>())
        {
        }

        /// <summary>
        /// Create a new OrderedMultiDictionary. If duplicate values
        /// are allowed, multiple copies of the same value can be associated with the same key. For example, the key "foo"
        /// could have "a", "a", and "b" associated with it. If duplicate values are not allowed, only one copies of a given value can
        /// be associated with the same key, although different keys can have the same value. For example, the key "foo" could
        /// have "a" and "b" associated with it, which key "bar" has values "b" and "c" associated with it.
        /// </summary>
        /// <param name="allowDuplicateValues">Can the same value be associated with a key multiple times?</param>
        /// <param name="keyComparison">A delegate to a method that will be used to compare keys.</param>
        /// <param name="valueComparison">A delegate to a method that will be used to compare values.</param>
        public OrderedMultiDictionary(bool allowDuplicateValues, Comparison<TKey> keyComparison, Comparison<TValue> valueComparison)
            : this(allowDuplicateValues, Comparers.ComparerFromComparison(keyComparison), Comparers.ComparerFromComparison(valueComparison))
        {
        }

        /// <summary>
        /// Create a new OrderedMultiDictionary. If duplicate values
        /// are allowed, multiple copies of the same value can be associated with the same key. For example, the key "foo"
        /// could have "a", "a", and "b" associated with it. If duplicate values are not allowed, only one copies of a given value can
        /// be associated with the same key, although different keys can have the same value. For example, the key "foo" could
        /// have "a" and "b" associated with it, which key "bar" has values "b" and "c" associated with it.
        /// </summary>
        /// <param name="allowDuplicateValues">Can the same value be associated with a key multiple times?</param>
        /// <param name="keyComparer">An IComparer&lt;TKey&gt; instance that will be used to compare keys.</param>
        /// <exception cref="InvalidOperationException">TValue does not implement either IComparable&lt;TValue&gt; or IComparable.</exception>
        public OrderedMultiDictionary(bool allowDuplicateValues, IComparer<TKey> keyComparer)
            : this(allowDuplicateValues, keyComparer, Comparers.DefaultComparer<TValue>())
        {
        }

        /// <summary>
        /// Create a new OrderedMultiDictionary. If duplicate values
        /// are allowed, multiple copies of the same value can be associated with the same key. For example, the key "foo"
        /// could have "a", "a", and "b" associated with it. If duplicate values are not allowed, only one copies of a given value can
        /// be associated with the same key, although different keys can have the same value. For example, the key "foo" could
        /// have "a" and "b" associated with it, which key "bar" has values "b" and "c" associated with it.
        /// </summary>
        /// <param name="allowDuplicateValues">Can the same value be associated with a key multiple times?</param>
        /// <param name="keyComparer">An IComparer&lt;TKey&gt; instance that will be used to compare keys.</param>
        /// <param name="valueComparer">An IComparer&lt;TValue&gt; instance that will be used to compare values.</param>
        public OrderedMultiDictionary(bool allowDuplicateValues, IComparer<TKey> keyComparer, IComparer<TValue> valueComparer)
        {
            if (keyComparer == null)
                throw new ArgumentNullException("keyComparer");
            if (valueComparer == null)
                throw new ArgumentNullException("valueComparer");

            this.allowDuplicateValues = allowDuplicateValues;
            this.keyComparer = keyComparer;
            this.valueComparer = valueComparer;
            this.comparer = Comparers.ComparerPairFromKeyValueComparers(keyComparer, valueComparer);
            this.tree = new RedBlackTree<KeyValuePair<TKey, TValue>>(this.comparer);
        }

        /// <summary>
        /// Create a new OrderedMultiDictionary. Used internally for cloning.
        /// </summary>
        /// <param name="allowDuplicateValues">Can the same value be associated with a key multiple times?</param>
        /// <param name="keyCount">Number of keys.</param>
        /// <param name="keyComparer">An IComparer&lt;TKey&gt; instance that will be used to compare keys.</param>
        /// <param name="valueComparer">An IComparer&lt;TValue&gt; instance that will be used to compare values.</param>
        /// <param name="comparer">Comparer of key-value pairs.</param>
        /// <param name="tree">The red-black tree used to store the data.</param>
        private OrderedMultiDictionary(bool allowDuplicateValues, int keyCount, IComparer<TKey> keyComparer, IComparer<TValue> valueComparer, IComparer<KeyValuePair<TKey,TValue>> comparer, RedBlackTree<KeyValuePair<TKey, TValue>> tree)
        {
            this.allowDuplicateValues = allowDuplicateValues;
            this.keyCount = keyCount;
            this.keyComparer = keyComparer;
            this.valueComparer = valueComparer;
            this.comparer = comparer;
            this.tree = tree;
        }

        #endregion Constructors

        #region Add or remove items

        /// <summary>
        /// <para>Adds a new value to be associated with a key. If duplicate values are permitted, this
        /// method always adds a new key-value pair to the dictionary.</para>
        /// <para>If duplicate values are not permitted, and <paramref name="key"/> already has a value
        /// equal to <paramref name="value"/> associated with it, then that value is replaced with <paramref name="value"/>,
        /// and the number of values associate with <paramref name="key"/> is unchanged.</para>
        /// </summary>
        /// <param name="key">The key to associate with.</param>
        /// <param name="value">The value to associated with <paramref name="key"/>.</param>
        public sealed override void Add(TKey key, TValue value)
        {
            KeyValuePair<TKey, TValue> pair = NewPair(key, value);
            KeyValuePair<TKey, TValue> dummy;

            if (!ContainsKey(key))
                ++keyCount;

            tree.Insert(pair, allowDuplicateValues ? DuplicatePolicy.InsertLast : DuplicatePolicy.ReplaceLast, out dummy);
        }

        /// <summary>
        /// Removes a given value from the values associated with a key. If the
        /// last value is removed from a key, the key is removed also.
        /// </summary>
        /// <param name="key">A key to remove a value from.</param>
        /// <param name="value">The value to remove.</param>
        /// <returns>True if <paramref name="value"/> was associated with <paramref name="key"/> (and was
        /// therefore removed). False if <paramref name="value"/> was not associated with <paramref name="key"/>.</returns>
        public sealed override bool Remove(TKey key, TValue value)
        {
            KeyValuePair<TKey, TValue> dummy;
            bool found =  tree.Delete(NewPair(key, value), false, out dummy);
            if (found && !ContainsKey(key))
                --keyCount;  // Removed the last value associated with the key.
            return found;
        }

        /// <summary>
        /// Removes a key and all associated values from the dictionary. If the
        /// key is not present in the dictionary, it is unchanged and false is returned.
        /// </summary>
        /// <param name="key">The key to remove.</param>
        /// <returns>True if the key was present and was removed. Returns 
        /// false if the key was not present.</returns>
        public sealed override bool Remove(TKey key)
        {
            if (tree.DeleteRange(KeyRange(key)) > 0) {
                --keyCount;
                return true;
            }
            else {
                return false;
            }
        }

        /// <summary>
        /// Removes all keys and values from the dictionary.
        /// </summary>
        public sealed override void Clear()
        {
            tree.StopEnumerations();  // Invalidate any enumerations.

            // The simplest and fastest way is simply to throw away the old tree and create a new one.
            tree = new RedBlackTree<KeyValuePair<TKey, TValue>>(comparer);
            keyCount = 0;
        }

        #endregion Add or remove items

        #region Query items

        /// <summary>
        /// Returns the IComparer&lt;T&gt; used to compare keys in this dictionary. 
        /// </summary>
        /// <value>If the dictionary was created using a comparer, that comparer is returned. If the dictionary was
        /// created using a comparison delegate, then a comparer equivalent to that delegate
        /// is returned. Otherwise
        /// the default comparer for TKey (Comparer&lt;TKey&gt;.Default) is returned.</value>
        public IComparer<TKey> KeyComparer
        {
            get
            {
                return this.keyComparer;
            }
        }

        /// <summary>
        /// Returns the IComparer&lt;T&gt; used to compare values in this dictionary. 
        /// </summary>
        /// <value>If the dictionary was created using a comparer, that comparer is returned. If the dictionary was
        /// created using a comparison delegate, then a comparer equivalent to that delegate
        /// is returned. Otherwise
        /// the default comparer for TValue (Comparer&lt;TValue&gt;.Default) is returned.</value>
        public IComparer<TValue> ValueComparer
        {
            get
            {
                return this.valueComparer;
            }
        }

        /// <summary>
        /// Determine if two values are equal.
        /// </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 sealed override bool EqualValues(TValue value1, TValue value2)
        {
            return valueComparer.Compare(value1, value2) == 0;
        }

        /// <summary>
        /// Gets the number of key-value pairs in the dictionary. Each value associated
        /// with a given key is counted. If duplicate values are permitted, each duplicate
        /// value is included in the count.
        /// </summary>
        /// <value>The number of key-value pairs in the dictionary.</value>
        public sealed override int Count
        {
            get
            {
                return keyCount;
            }
        }

        /// <summary>
        /// Checks to see if <paramref name="value"/> is associated with <paramref name="key"/>
        /// in the dictionary.
        /// </summary>
        /// <param name="key">The key to check.</param>
        /// <param name="value">The value to check.</param>
        /// <returns>True if <paramref name="value"/> is associated with <paramref name="key"/>.</returns>
        public sealed override bool Contains(TKey key, TValue value)
        {
            KeyValuePair<TKey, TValue> dummy;
            return tree.Find(NewPair(key, value), true, false, out dummy);
        }

        /// <summary>
        /// Checks to see if the key is present in the dictionary and has
        /// at least one value associated with it.
        /// </summary>
        /// <param name="key">The key to check.</param>
        /// <returns>True if <paramref name="key"/> is present and has at least
        /// one value associated with it. Returns false otherwise.</returns>
        public sealed override bool ContainsKey(TKey key)
        {
            KeyValuePair<TKey, TValue> dummy;
            return (tree.FirstItemInRange(KeyRange(key), out dummy) >= 0);
        }

        /// <summary>
        /// A private helper method that returns an enumerable that
        /// enumerates all the keys in a range.
        /// </summary>
        /// <param name="rangeTester">Defines the range to enumerate.</param>
        /// <param name="reversed">Should the keys be enumerated in reverse order?</param>
        /// <returns>An IEnumerable&lt;TKey&gt; that enumerates the keys in the given range.
        /// in the dictionary.</returns>
        private IEnumerator<TKey> EnumerateKeys(RedBlackTree<KeyValuePair<TKey,TValue>>.RangeTester rangeTester, bool reversed)
        {
            bool isFirst = true;
            TKey lastKey = default(TKey);

            IEnumerable<KeyValuePair<TKey, TValue>> pairs;

            if (reversed)
                pairs = tree.EnumerateRangeReversed(rangeTester);
            else
                pairs = tree.EnumerateRange(rangeTester);

            // Enumerate pairs; yield a new key when the key changes.
            foreach (KeyValuePair<TKey, TValue> pair in pairs) {
                if (isFirst || keyComparer.Compare(lastKey, pair.Key) != 0) {
                    lastKey = pair.Key;
                    yield return lastKey;
                }

                isFirst = false;
            }
        }

        /// <summary>
        /// A private helper method for the indexer to return an enumerable that
        /// enumerates all the values for a key. This is separate method because indexers
        /// can't use the yield return construct.
        /// </summary>
        /// <param name="key"></param>
        /// <returns>An IEnumerable&lt;TValue&gt; that can be used to enumerate all the
        /// values associated with <paramref name="key"/>. If <paramref name="key"/> is not present,
        /// an enumerable that enumerates no items is returned.</returns>
        private IEnumerator<TValue> EnumerateValuesForKey(TKey key)
        {
            foreach (KeyValuePair<TKey,TValue> pair in tree.EnumerateRange(KeyRange(key)))
                yield return pair.Value;
        }

        /// <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. 
        /// </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>
        protected sealed override bool TryEnumerateValuesForKey(TKey key, out IEnumerator<TValue> values)
        {
            // CONSIDER: It would be nice to eliminate the double lookup here, but there doesn't seem to be an easy way.
            if (ContainsKey(key)) {
                values = EnumerateValuesForKey(key);
                return true;
            }
            else {
                values = null;
                return false;
            }
        }

        /// <summary>
        /// Enumerate all of the keys in the dictionary.
        /// </summary>
        /// <returns>An IEnumerator&lt;TKey&gt; of all of the keys in the dictionary.</returns>
        protected sealed override IEnumerator<TKey> EnumerateKeys()
        {
            return EnumerateKeys(tree.EntireRangeTester, false);
        }

        /// <summary>
        /// Gets the number of values associated with a given key.
        /// </summary>
        /// <param name="key">The key to count values of.</param>
        /// <returns>The number of values associated with <paramref name="key"/>. If <paramref name="key"/>
        /// is not present in the dictionary, zero is returned.</returns>
        protected sealed override int CountValues(TKey key)
        {
            return tree.CountRange(KeyRange(key));
        }

        /// <summary>
        /// Gets a total count of values in the collection. 
        /// </summary>
        /// <returns>The total number of values associated with all keys in the dictionary.</returns>
        protected sealed override int CountAllValues()
        {
            return tree.ElementCount;
        }

        #endregion Query items

        #region Cloning

        /// <summary>
        /// Makes a shallow clone of this dictionary; i.e., if keys or values of the
        /// dictionary are reference types, then they are not cloned. If TKey or TValue is a value type,
        /// then each element is copied as if by simple assignment.
        /// </summary>
        /// <remarks>Cloning the dictionary takes time O(N), where N is the number of key-value pairs in the dictionary.</remarks>
        /// <returns>The cloned dictionary.</returns>
        public OrderedMultiDictionary<TKey, TValue> Clone()
        {
            OrderedMultiDictionary<TKey, TValue> newDict = new OrderedMultiDictionary<TKey, TValue>(allowDuplicateValues, keyCount, keyComparer, valueComparer, comparer, tree.Clone());
            return newDict;
        }

        /// <summary>
        /// Implements ICloneable.Clone. Makes a shallow clone of this dictionary; i.e., if keys or values are reference types, then they are not cloned.
        /// </summary>
        /// <returns>The cloned dictionary.</returns>
        object ICloneable.Clone()
        {
            return Clone();
        }

        /// <summary>
        /// Throw an InvalidOperationException indicating that this type is not cloneable.
        /// </summary>
        /// <param name="t">Type to test.</param>
        private void NonCloneableType(Type t)
        {
            throw new InvalidOperationException(string.Format(Strings.TypeNotCloneable, t.FullName));
        }

        /// <summary>
        /// Makes a deep clone of this dictionary. A new dictionary is created with a clone of
        /// each entry of this dictionary, by calling ICloneable.Clone on each element. If TKey or TValue is
        /// a value type, then each element is copied as if by simple assignment.
        /// </summary>
        /// <remarks><para>If TKey or TValue is a reference type, it must implement
        /// ICloneable. Otherwise, an InvalidOperationException is thrown.</para>
        /// <para>Cloning the dictionary takes time O(N log N), where N is the number of key-value pairs in the dictionary.</para></remarks>
        /// <returns>The cloned dictionary.</returns>
        /// <exception cref="InvalidOperationException">TKey or TValue is a reference type that does not implement ICloneable.</exception>
        public OrderedMultiDictionary<TKey, TValue> CloneContents()
        {
            bool keyIsValueType, valueIsValueType;

            // Make sure that TKey and TValue can be cloned.
            if (!Util.IsCloneableType(typeof(TKey), out keyIsValueType))
                NonCloneableType(typeof(TKey));

            if (!Util.IsCloneableType(typeof(TValue), out valueIsValueType))
                NonCloneableType(typeof(TValue));

            OrderedMultiDictionary<TKey, TValue> newDict = new OrderedMultiDictionary<TKey, TValue>(allowDuplicateValues, keyComparer, valueComparer);

            foreach (KeyValuePair<TKey, TValue> pair in tree) {
                // Clone the key and value parts of the pair. Value types can be cloned
                // by just copying them, otherwise, ICloneable is used.
                TKey keyClone;
                TValue valueClone;

                if (keyIsValueType)
                    keyClone = pair.Key;
                else {
                    if (pair.Key == null)
                        keyClone = default(TKey);  // Really null, because we know TKey isn't a value type.
                    else
                        keyClone = (TKey)(((ICloneable)pair.Key).Clone());
                }

                if (valueIsValueType)
                    valueClone = pair.Value;
                else {
                    if (pair.Value == null)
                        valueClone = default(TValue);   // Really null, because we know TKey isn't a value type.
                    else
                        valueClone = (TValue)(((ICloneable)pair.Value).Clone());
                }

                newDict.Add(keyClone, valueClone);
            }

            return newDict;
        }

        #endregion Cloning

        #region KeyValuePairsCollection

        /// <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 sealed override ICollection<KeyValuePair<TKey, TValue>> KeyValuePairs
        {
            get { return new KeyValuePairsCollection(this); }
        }

        /// <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 OrderedMultiDictionary<TKey, TValue> myDictionary;

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

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

            public override IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
            {
                return myDictionary.tree.GetEnumerator();
            }

            public override bool Contains(KeyValuePair<TKey, TValue> pair)
            {
                KeyValuePair<TKey, TValue> dummy;
                return myDictionary.tree.Find(pair, true, false, out dummy);
            }
        }

        #endregion KeyValuePairs collection

        #region Views

        /// <summary>
        /// Returns a View collection that can be used for enumerating the keys and values in the collection in 
        /// reversed order.
        /// </summary>
        ///<remarks>
        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
        ///<code>
        /// foreach(KeyValuePair&lt;TKey, TValue&gt; pair in dictionary.Reversed()) {
        ///    // process pair
        /// }
        ///</code></p>
        /// <p>If an entry is added to or deleted from the dictionary while the View is being enumerated, then 
        /// the enumeration will end with an InvalidOperationException.</p>
        ///<p>Calling Reverse does not copy the data in the dictionary, and the operation takes constant time.</p>
        ///</remarks>
        /// <returns>An OrderedDictionary.View of key-value pairs in reverse order.</returns>
        public View Reversed()
        {
            return new View(this, tree.EntireRangeTester, true, true);
        }

        /// <summary>
        /// Returns a collection that can be used for enumerating some of the keys and values in the collection. 
        /// Only keys that are greater than <paramref name="from"/> and 
        /// less than <paramref name="to"/> are included. The keys are enumerated in sorted order.
        /// Keys equal to the end points of the range can be included or excluded depending on the
        /// <paramref name="fromInclusive"/> and <paramref name="toInclusive"/> parameters.
        /// </summary>
        ///<remarks>
        ///<p>If <paramref name="from"/> is greater than or equal to <paramref name="to"/>, the returned collection is empty. </p>
        ///<p>The sorted order of the keys is determined by the comparison instance or delegate used
        /// to create the dictionary.</p>
        ///<p>Typically, this property is used in conjunction with a foreach statement. For example:</p>
        ///<code>
        /// foreach(KeyValuePair&lt;TKey, TValue&gt; pair in dictionary.Range(from, true, to, false)) {
        ///    // process pair
        /// }
        ///</code>
        ///<p>Calling Range does not copy the data in the dictionary, and the operation takes constant time.</p></remarks>
        /// <param name="from">The lower bound of the range.</param>
        /// <param name="fromInclusive">If true, the lower bound is inclusive--keys equal to the lower bound will
        /// be included in the range. If false, the lower bound is exclusive--keys equal to the lower bound will not
        /// be included in the range.</param>
        /// <param name="to">The upper bound of the range. </param>
        /// <param name="toInclusive">If true, the upper bound is inclusive--keys equal to the upper bound will
        /// be included in the range. If false, the upper bound is exclusive--keys equal to the upper bound will not
        /// be included in the range.</param>
        /// <returns>An OrderedMultiDictionary.View of key-value pairs in the given range.</returns>
        public View Range(TKey from, bool fromInclusive, TKey to, bool toInclusive)
        {
            return new View(this, DoubleBoundedKeyRangeTester(from, fromInclusive, to, toInclusive), false, false);
        }


        /// <summary>
        /// Returns a collection that can be used for enumerating some of the keys and values in the collection. 
        /// Only keys that are greater than (and optionally, equal to) <paramref name="from"/> are included. 
        /// The keys are enumerated in sorted order. Keys equal to <paramref name="from"/> can be included
        /// or excluded depending on the <paramref name="fromInclusive"/> parameter.
        /// </summary>
        ///<remarks>
        ///<p>The sorted order of the keys is determined by the comparison instance or delegate used
        /// to create the dictionary.</p>
        ///<p>Typically, this property is used in conjunction with a foreach statement. For example:</p>
        ///<code>
        /// foreach(KeyValuePair&lt;TKey, TValue&gt; pair in dictionary.RangeFrom(from, true)) {
        ///    // process pair
        /// }
        ///</code>
        ///<p>Calling RangeFrom does not copy of the data in the dictionary, and the operation takes constant time.</p>
        ///</remarks>
        /// <param name="from">The lower bound of the range.</param>
        /// <param name="fromInclusive">If true, the lower bound is inclusive--keys equal to the lower bound will
        /// be included in the range. If false, the lower bound is exclusive--keys equal to the lower bound will not
        /// be included in the range.</param>
        /// <returns>An OrderedMultiDictionary.View of key-value pairs in the given range.</returns>
        public View RangeFrom(TKey from, bool fromInclusive)
        {
            return new View(this, LowerBoundedKeyRangeTester(from, fromInclusive), false, false);
        }

        /// <summary>
        /// Returns a collection that can be used for enumerating some of the keys and values in the collection. 
        /// Only items that are less than (and optionally, equal to) <paramref name="to"/> are included. 
        /// The items are enumerated in sorted order. Items equal to <paramref name="to"/> can be included
        /// or excluded depending on the <paramref name="toInclusive"/> parameter.
        /// </summary>
        ///<remarks>
        ///<p>The sorted order of the keys is determined by the comparison instance or delegate used
        /// to create the dictionary.</p>
        ///<p>Typically, this property is used in conjunction with a foreach statement. For example:</p>
        ///<code>
        /// foreach(KeyValuePair&lt;TKey, TValue&gt; pair in dictionary.RangeFrom(from, false)) {
        ///    // process pair
        /// }
        ///</code>
        ///<p>Calling RangeTo does not copy the data in the dictionary, and the operation takes constant time.</p>
        ///</remarks>
        /// <param name="to">The upper bound of the range. </param>
        /// <param name="toInclusive">If true, the upper bound is inclusive--keys equal to the upper bound will
        /// be included in the range. If false, the upper bound is exclusive--keys equal to the upper bound will not
        /// be included in the range.</param>
        /// <returns>An OrderedMultiDictionary.View of key-value pairs in the given range.</returns>
        public View RangeTo(TKey to, bool toInclusive)
        {
            return new View(this, UpperBoundedKeyRangeTester(to, toInclusive), false, false);
        }

        #endregion Views

        /// <summary>
        /// The OrderedMultiDictionary&lt;TKey,TValue&gt;.View class is used to look at a subset of the keys and values
        /// inside an ordered multi-dictionary. It is returned from the Range, RangeTo, RangeFrom, and Reversed methods. 
        /// </summary>
        ///<remarks>
        /// <p>Views are dynamic. If the underlying dictionary changes, the view changes in sync. If a change is made
        /// to the view, the underlying dictionary changes accordingly.</p>
        ///<p>Typically, this class is used in conjunction with a foreach statement to enumerate the keys
        /// and values in a subset of the OrderedMultiDictionary. For example:</p>
        ///<code>
        /// foreach(KeyValuePair&lt;TKey, TValue&gt; pair in dictionary.Range(from, to)) {
        ///    // process pair
        /// }
        ///</code>
        ///</remarks>
        [Serializable]
        public class View : MultiDictionaryBase<TKey, TValue>
        {
            private OrderedMultiDictionary<TKey, TValue> myDictionary;
            private RedBlackTree<KeyValuePair<TKey, TValue>>.RangeTester rangeTester;   // range tester for the range being used.
            private bool entireTree;                   // is the view the whole tree?
            private bool reversed;                     // is the view reversed?

            /// <summary>
            /// Initialize the View.
            /// </summary>
            /// <param name="myDictionary">Associated OrderedMultiDictionary to be viewed.</param>
            /// <param name="rangeTester">Range tester that defines the range being used.</param>
            /// <param name="entireTree">If true, then rangeTester defines the entire tree.</param>
            /// <param name="reversed">Is the view enuemerated in reverse order?</param>
            internal View(OrderedMultiDictionary<TKey, TValue> myDictionary, RedBlackTree<KeyValuePair<TKey, TValue>>.RangeTester rangeTester, bool entireTree, bool reversed)
            {
                this.myDictionary = myDictionary;
                this.rangeTester = rangeTester;
                this.entireTree = entireTree;
                this.reversed = reversed;
            }

            /// <summary>
            /// Determine if the given key lies within the bounds of this view.
            /// </summary>
            /// <param name="key">Key to test.</param>
            /// <returns>True if the key is within the bounds of this view.</returns>
            private bool KeyInView(TKey key)
            {
                return rangeTester(NewPair(key, default(TValue))) == 0;
            }

            /// <summary>
            /// Enumerate all the keys in the dictionary. 
            /// </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 sealed override IEnumerator<TKey> EnumerateKeys()
            {
                return myDictionary.EnumerateKeys(rangeTester, reversed);
            }

            /// <summary>
            /// Enumerate all of the values associated with a given key. 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 sealed override bool TryEnumerateValuesForKey(TKey key, out IEnumerator<TValue> values)
            {
                if (!KeyInView(key)) {
                    values = null;
                    return false;
                }
                else
                    return myDictionary.TryEnumerateValuesForKey(key, out values);
            }

            /// <summary>
            /// Number of keys in this view.
            /// </summary>
            /// <value>Number of keys that lie within the bounds the view.</value>
            public sealed override int Count
            {
                get
                {
                    if (entireTree)
                        return myDictionary.Count;
                    else {
                        int count = 0;

                        using (IEnumerator<TKey> enumKeys = myDictionary.EnumerateKeys(rangeTester, reversed)) {
                            while (enumKeys.MoveNext()) {
                                ++count;
                            }
                        }

                        return count;
                    }
                }
            }

            /// <summary>
            /// Tests if the key is present in the part of the dictionary being viewed.
            /// </summary>
            /// <param name="key">Key to check</param>
            /// <returns>True if the key is within this view. </returns>
            public sealed override bool ContainsKey(TKey key)
            {
                if (!KeyInView(key))
                    return false;
                else
                    return myDictionary.ContainsKey(key);
            }

            /// <summary>
            /// Tests if the key-value pair is present in the part of the dictionary being viewed.
            /// </summary>
            /// <param name="key">Key to check for.</param>
            /// <param name="value">Value to check for.</param>
            /// <returns>True if the key-value pair is within this view. </returns>
            public sealed override bool Contains(TKey key, TValue value)
            {
                if (!KeyInView(key))
                    return false;
                else
                    return myDictionary.Contains(key, value);
            }

            /// <summary>
            /// Gets the number of values associated with a given key.
            /// </summary>
            /// <param name="key">The key to count values of.</param>
            /// <returns>The number of values associated with <paramref name="key"/>. If <paramref name="key"/>
            /// is not present in this view, zero is returned.</returns>
            protected sealed override int CountValues(TKey key)
            {
                if (!KeyInView(key))
                    return 0;
                else
                    return myDictionary.CountValues(key);
            }

            /// <summary>
            /// Adds the given key-value pair to the underlying dictionary of this view.
            /// If <paramref name="key"/> is not within the range of this view, an
            /// ArgumentException is thrown.
            /// </summary>
            /// <param name="key"></param>
            /// <param name="value"></param>
            /// <exception cref="ArgumentException"><paramref name="key"/> is not 
            /// within the range of this view.</exception>
            public sealed override void Add(TKey key, TValue value)
            {
                if (!KeyInView(key))
                    throw new ArgumentException(Strings.OutOfViewRange, "key");
                else
                    myDictionary.Add(key, value);
            }

            /// <summary>
            /// Removes the key (and associated value) from the underlying dictionary of this view. If
            /// no key in the view is equal to the passed key, the dictionary and view are unchanged.
            /// </summary>
            /// <param name="key">The key to remove.</param>
            /// <returns>True if the key was found and removed. False if the key was not found.</returns>
            public sealed override bool Remove(TKey key)
            {
                if (!KeyInView(key))
                    return false;
                else
                    return myDictionary.Remove(key);
            }

            /// <summary>
            /// Removes the key and value from the underlying dictionary of this view. that is equal to the passed in key. If
            /// no key in the view is equal to the passed key, or has the given value associated with it, the dictionary and view are unchanged.
            /// </summary>
            /// <param name="key">The key to remove.</param>
            /// <param name="value">The value to remove.</param>
            /// <returns>True if the key-value pair was found and removed. False if the key-value pair was not found.</returns>
            public sealed override bool Remove(TKey key, TValue value)
            {
                if (!KeyInView(key))
                    return false;
                else
                    return myDictionary.Remove(key, value);
            }

            /// <summary>
            /// Removes all the keys and values within this view from the underlying OrderedMultiDictionary.
            /// </summary>
            /// <example>The following removes all the keys that start with "A" from an OrderedMultiDictionary.
            /// <code>
            /// dictionary.Range("A", "B").Clear();
            /// </code>
            /// </example>
            public sealed override void Clear()
            {
                if (entireTree) {
                    myDictionary.Clear();
                }
                else {
                    myDictionary.keyCount -= this.Count;
                    myDictionary.tree.DeleteRange(rangeTester);
                }
            }

            /// <summary>
            /// Creates a new View that has the same keys and values as this, in the reversed order.
            /// </summary>
            /// <returns>A new View that has the reversed order of this view.</returns>
            public View Reversed()
            {
                return new View(myDictionary, rangeTester, entireTree, !reversed);
            }
        }

    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Eclipse Public License 1.0

Share

About the Author

Stefan Bocutiu
Software Developer (Senior) Lab49
United Kingdom United Kingdom
No Biography provided

| Advertise | Privacy | Mobile
Web03 | 2.8.141015.1 | Last Updated 29 Jan 2009
Article Copyright 2009 by Stefan Bocutiu
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid