orderedmultidictionary.cs

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

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