orderedmultidictionary.cs

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

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