orderedmultidictionary.cs

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

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

    }
}