orderedmultidictionary.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;

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");