ordereddictionary.cs

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

        /// </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 OrderedDictionary.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, tree.DoubleBoundedRangeTester(NewPair(from), fromInclusive, NewPair(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 OrderedDictionary.View of key-value pairs in the given range.</returns>
        public View RangeFrom(TKey from, bool fromInclusive)
        {
            return new View(this, tree.LowerBoundedRangeTester(NewPair(from), fromInclusive), false, false);
        }

        /// <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 OrderedDictionary.View of key-value pairs in the given range.</returns>
        public View RangeTo(TKey to, bool toInclusive)
        {
            return new View(this, tree.UpperBoundedRangeTester(NewPair(to), toInclusive), false, false);
        }

		#region IDictionary<TKey,TValue> Members

		/// <summary>
		/// Removes the key (and associated value) from the collection that is equal to the passed in key. If
		/// no key in the dictionary is equal to the passed key, false is returned and the 
		/// dictionary is unchanged.
		/// </summary>
		/// <remarks>Equality between keys is determined by the comparison instance or delegate used
		/// to create the dictionary.</remarks>
		/// <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)
        {
            KeyValuePair<TKey, TValue> keyPair = NewPair(key);
			KeyValuePair<TKey, TValue> item;
			return tree.Delete(keyPair, true, out item);
		}

		/// <summary>
		/// Removes all keys and values from the dictionary.
		/// </summary>
        /// <remarks>Clearing the dictionary takes a constant amount of time, regardless of the number of keys in it.</remarks>
        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>>(pairComparer);
		}

        /// <summary>
        /// Finds a key in the dictionary. If the dictionary already contains
        /// a key equal to the passed key, then the existing value is returned via value. If the dictionary
        /// doesn't contain that key, then value is associated with that key.
        /// </summary>
        /// <remarks><para> between keys is determined by the comparison instance or delegate used
        /// to create the dictionary.</para>
        /// <para>This method takes time O(log N), where N is the number of keys in the dictionary. If a value is added, It is more efficient than
        /// calling TryGetValue followed by Add, because the dictionary is not searched twice.</para></remarks>
        /// <param name="key">The new key. </param>
        /// <param name="value">The new value to associated with that key, if the key isn't present. If the key was present, 
        /// returns the exist value associated with that key.</param>
        /// <returns>True if key was already present, false if key wasn't present (and a new value was added).</returns>
        public bool GetValueElseAdd(TKey key, ref TValue value)
        {
            KeyValuePair<TKey, TValue> pair = NewPair(key, value);
            KeyValuePair<TKey, TValue> old;

            bool added = tree.Insert(pair, DuplicatePolicy.DoNothing, out old);
            if (!added) 
                value = old.Value;
            return !added;
        }

        /// <summary>
        /// Adds a new key and value to the dictionary. If the dictionary already contains
        /// a key equal to the passed key, then an ArgumentException is thrown
        /// </summary>
        /// <remarks>
        /// <para>Equality between keys is determined by the comparison instance or delegate used
        /// to create the dictionary.</para>
        /// <para>Adding an key and value takes time O(log N), where N is the number of keys in the dictionary.</para></remarks>
        /// <param name="key">The new key. "null" is a valid key value.</param>
        /// <param name="value">The new value to associated with that key.</param>
        /// <exception cref="ArgumentException">key is already present in the dictionary</exception>
        public sealed override void Add(TKey key, TValue value)
        {
            KeyValuePair<TKey, TValue> pair = NewPair(key, value);
            KeyValuePair<TKey, TValue> dummy;

            bool added = tree.Insert(pair, DuplicatePolicy.DoNothing, out dummy);
            if (! added) 
                throw new ArgumentException(Strings.KeyAlreadyPresent, "key");
        }

        /// <summary>
        /// Changes the value associated with a given key. If the dictionary does not contain
        /// a key equal to the passed key, then an ArgumentException is thrown.
        /// </summary>
        /// <remarks>
        /// <p>Unlike adding or removing an element, changing the value associated with a key
        /// can be performed while an enumeration (foreach) on the the dictionary is in progress.</p>
        /// <p>Equality between keys is determined by the comparison instance or delegate used
        /// to create the dictionary.</p>
        /// <p>Replace takes time O(log N), where N is the number of entries in the dictionary.</p></remarks>
        /// <param name="key">The new key. </param>
        /// <param name="value">The new value to associated with that key.</param>
        /// <exception cref="KeyNotFoundException">key is not present in the dictionary</exception>
        public void Replace(TKey key, TValue value)
        {
            KeyValuePair<TKey, TValue> pair = NewPair(key, value);
            KeyValuePair<TKey, TValue> dummy;

            bool found = tree.Find(pair, true, true, out dummy);
            if (!found)
                throw new KeyNotFoundException(Strings.KeyNotFound);   
        }

        /// <summary>
        /// Adds multiple key-value pairs to a dictionary. If a key exists in both the current instance and dictionaryToAdd,
        /// then the value is updated with the value from <paramref name="keysAndValues>"/> (no exception is thrown).
        /// Since IDictionary&lt;TKey,TValue&gt; inherits from IEnumerable&lt;KeyValuePair&lt;TKey,TValue&gt;&gt;, this
        /// method can be used to merge one dictionary into another.
        /// </summary>
        /// <remarks>AddMany takes time O(M log (N+M)), where M is the size of <paramref name="keysAndValues>"/>, and N is the size of
        /// this dictionary.</remarks>
        /// <param name="keysAndValues">A collection of keys and values whose contents are added to the current dictionary.</param>
        public void AddMany(IEnumerable<KeyValuePair<TKey, TValue>> keysAndValues)
        {
            if (keysAndValues == null)
                throw new ArgumentNullException("keysAndValues");

            foreach (KeyValuePair<TKey, TValue> pair in keysAndValues) {
                this[pair.Key] = pair.Value;
            }
        }

        /// <summary>
        /// Removes all the keys found in another collection (such as an array or List&lt;TKey&gt;). Each key in keyCollectionToRemove
        /// is removed from the dictionary. Keys that are not present are ignored.
        /// </summary>
        /// <remarks>RemoveMany takes time O(M log N), where M is the size of keyCollectionToRemove, and N is this
        /// size of this collection.</remarks>
        /// <returns>The number of keys removed from the dictionary.</returns>
        /// <param name="keyCollectionToRemove">A collection of keys to remove from the dictionary.</param>
        public int RemoveMany(IEnumerable<TKey> keyCollectionToRemove)
        {
            if (keyCollectionToRemove == null)
                throw new ArgumentNullException("keyCollectionToRemove");

            int count = 0;

            foreach (TKey key in keyCollectionToRemove) {
                if (this.Remove(key))
                    ++count;
            }

            return count;
        }

		/// <summary>
		/// Gets or sets the value associated with a given key. When getting a value, if this
		/// key is not found in the collection, then an ArgumentException is thrown. When setting
		/// a value, the value replaces any existing value in the dictionary.
		/// </summary>
        /// <remarks>The indexer takes time O(log N), where N is the number of entries in the dictionary.</remarks>
        /// <value>The value associated with the key</value>
        /// <exception cref="ArgumentException">A value is being retrieved, and the key is not present in the dictionary.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="key"/> is null.</exception>
        public sealed override TValue this[TKey key]
        {
			get
			{
                KeyValuePair<TKey,TValue> pairFound;
				bool found;
				
				found = tree.Find(NewPair(key), false, false, out pairFound);
				if (found)
					return pairFound.Value;
				else
					throw new KeyNotFoundException(Strings.KeyNotFound);
			}
			set