readonlymultidictionarybase.cs

C#写的类似于STL的集合类,首先是C#编写,可以用于.net变程.

//******************************
// 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;
            }