bag.cs

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

        /// Returns the representative item stored in the bag that is equal to
        /// the provided item. Also returns the number of copies of the item in the bag.
        /// </summary>
        /// <param name="item">Item to find in the bag.</param>
        /// <param name="representative">If one or more items equal to <paramref name="item"/> are present in the
        /// bag, returns the representative item. If no items equal to <paramref name="item"/> are stored in the bag, 
        /// returns <paramref name="item"/>.</param>
        /// <returns>The number of items equal to <paramref name="item"/> stored in the bag.</returns>
        public int GetRepresentativeItem(T item, out T representative)
        {
            KeyValuePair<T, int> foundPair;
            if (hash.Find(NewPair(item), false, out foundPair)) {
                representative = foundPair.Key;
                return foundPair.Value;
            }
            else {
                representative = item;
                return 0;
            }
        }

        /// <summary>
        /// Returns an enumerator that enumerates all the items in the bag. 
        /// If an item is present multiple times in the bag, the representative item is yielded by the
        /// enumerator multiple times. The order of enumeration is haphazard and may change.
        /// </summary>
        /// <remarks>
        /// <p>Typically, this method is not called directly. Instead the "foreach" statement is used
        /// to enumerate the items, which uses this method implicitly.</p>
        /// <p>If an item is added to or deleted from the bag while it is being enumerated, then 
        /// the enumeration will end with an InvalidOperationException.</p>
        /// <p>Enumeration all the items in the bag takes time O(N), where N is the number
        /// of items in the bag.</p>
        /// </remarks>
        /// <returns>An enumerator for enumerating all the items in the Bag.</returns>		
        public sealed override IEnumerator<T> GetEnumerator()
        {
            foreach (KeyValuePair<T, int> pair in hash) {
                for (int i = 0; i < pair.Value; ++i)
                    yield return pair.Key;
            }
        }

        /// <summary>
        /// Determines if this bag contains an item equal to <paramref name="item"/>. The bag
        /// is not changed.
        /// </summary>
        /// <remarks>Searching the bag for an item takes time O(log N), where N is the number of items in the bag.</remarks>
        /// <param name="item">The item to search for.</param>
        /// <returns>True if the bag contains <paramref name="item"/>. False if the bag does not contain <paramref name="item"/>.</returns>
        public sealed override bool Contains(T item)
        {
            KeyValuePair<T, int> dummy;
            return hash.Find(NewPair(item), false, out dummy);
        }

        /// <summary>
        /// Enumerates all the items in the bag, but enumerates equal items
        /// just once, even if they occur multiple times in the bag.
        /// </summary>
        /// <remarks>If the bag is changed while items are being enumerated, the
        /// enumeration will terminate with an InvalidOperationException.</remarks>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates the unique items.</returns>
        public IEnumerable<T> DistinctItems()
        {
            foreach (KeyValuePair<T, int> pair in hash) {
                yield return pair.Key;
            }
        }

        #endregion


        #region Adding elements

        /// <summary>
        /// Adds a new item to the bag. Since bags can contain duplicate items, the item 
        /// is added even if the bag already contains an item equal to <paramref name="item"/>. In
        /// this case, the count of items for the representative item is increased by one, but the existing
        /// represetative item is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>Adding an item takes approximately constant time, regardless of the number of items in the bag.</para></remarks>
        /// <param name="item">The item to add to the bag.</param>
        public sealed override void Add(T item)
        {
            KeyValuePair<T, int> pair = NewPair(item, 1);
            KeyValuePair<T, int> existing, newPair;
            if (! hash.Insert(pair, false, out existing)) {
                // The item already existed, so update the count instead.
                newPair = NewPair(existing.Key, existing.Value + 1);
                hash.Insert(newPair, true, out pair);
            }
            ++count;
        }

        // CONSIDER: add an example to the documentation below.
        /// <summary>
        /// Adds a new item to the bag. Since bags can contain duplicate items, the item 
        /// is added even if the bag already contains an item equal to <paramref name="item"/>. In
        /// this case (unlike Add), the new item becomes the representative item.
        /// </summary>
        /// <remarks>
        /// <para>Adding an item takes approximately constant time, regardless of the number of items in the bag.</para></remarks>
        /// <param name="item">The item to add to the bag.</param>
        public void AddRepresentative(T item)
        {
            KeyValuePair<T, int> pair = NewPair(item, 1);
            KeyValuePair<T, int> existing, newPair;
            if (!hash.Insert(pair, false, out existing)) {
                // The item already existed, so update the count instead.
                newPair = NewPair(pair.Key, existing.Value + 1);
                hash.Insert(newPair, true, out pair);
            }
            ++count;
        }

        /// <summary>
        /// Changes the number of copies of an existing item in the bag, or adds the indicated number
        /// of copies of the item to the bag. 
        /// </summary>
        /// <remarks>
        /// <para>Changing the number of copies takes approximately constant time, regardless of the number of items in the bag.</para></remarks>
        /// <param name="item">The item to change the number of copies of. This may or may not already be present in the bag.</param>
        /// <param name="numCopies">The new number of copies of the item.</param>
        public void ChangeNumberOfCopies(T item, int numCopies)
        {
            if (numCopies == 0)
                RemoveAllCopies(item);
            else {
                KeyValuePair<T, int> dummy, existing, newPair;
                if (hash.Find(NewPair(item), false, out existing)) {
                    count += numCopies - existing.Value;
                    newPair = NewPair(existing.Key, numCopies);
                }
                else {
                    count += numCopies;
                    newPair = NewPair(item, numCopies);
                }
                hash.Insert(newPair, true, out dummy);
            }
        }

        /// <summary>
        /// Adds all the items in <paramref name="collection"/> to the bag. 
        /// </summary>
        /// <remarks>
        /// <para>Adding the collection takes time O(M log N), where N is the number of items in the bag, and M is the 
        /// number of items in <paramref name="collection"/>.</para></remarks>
        /// <param name="collection">A collection of items to add to the bag.</param>
        public void AddMany(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            // If we're adding ourselves, we need to copy to a separate array to avoid modification
            // during enumeration.
            if (this == collection)
                collection = this.ToArray();

            foreach (T item in collection)
                Add(item);
        }

        #endregion Adding elements

        #region Removing elements

        /// <summary>
        /// Searches the bag for one item equal to <paramref name="item"/>, and if found,
        /// removes it from the bag. If not found, the bag is unchanged. 
        /// </summary>
        /// <remarks>
        /// <para>Equality between items is determined by the comparison instance or delegate used
        /// to create the bag.</para>
        /// <para>Removing an item from the bag takes approximated constant time,
        /// regardless of the number of items in the bag.</para></remarks>
        /// <param name="item">The item to remove.</param>
        /// <returns>True if <paramref name="item"/> was found and removed. False if <paramref name="item"/> was not in the bag.</returns>
        public sealed override bool Remove(T item)
        {
            KeyValuePair<T, int> removed, newPair;
            if (hash.Delete(NewPair(item), out removed)) {
                if (removed.Value > 1) {
                    // Only want to remove one copied, so add back in with a reduced count.
                    KeyValuePair<T, int> dummy;
                    newPair = NewPair(removed.Key, removed.Value - 1);
                    hash.Insert(newPair, true, out dummy);
                }
                --count;
                return true;
            }
            else
                return false;
        }

        /// <summary>
        /// Searches the bag for all items equal to <paramref name="item"/>, and 
        /// removes all of them from the bag. If not found, the bag is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>Equality between items is determined by the comparer instance used
        /// to create the bag.</para>
        /// <para>RemoveAllCopies() takes time O(M log N), where N is the total number of items in the bag, and M is
        /// the number of items equal to <paramref name="item"/>.</para></remarks>
        /// <param name="item">The item to remove.</param>
        /// <returns>The number of copies of <paramref name="item"/> that were found and removed. </returns>
        public int RemoveAllCopies(T item)
        {
            KeyValuePair<T, int> removed;
            if (hash.Delete(NewPair(item), out removed)) {
                count -= removed.Value;
                return removed.Value;
            }
            else
                return 0;
        }

        /// <summary>
        /// Removes all the items in <paramref name="collection"/> from the bag. Items that
        /// are not present in the bag are ignored.
        /// </summary>
        /// <remarks>
        /// <para>Equality between items is determined by the comparer instance used
        /// to create the bag.</para>
        /// <para>Removing the collection takes time O(M), where M is the 
        /// number of items in <paramref name="collection"/>.</para></remarks>
        /// <param name="collection">A collection of items to remove from the bag.</param>
        /// <returns>The number of items removed from the bag.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
        public int RemoveMany(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            int count = 0;

            if (collection == this) {
                count = Count;
                Clear();            // special case, otherwise we will throw.
            }
            else {
                foreach (T item in collection) {
                    if (Remove(item))
                        ++count;
                }
            }

            return count;
        }

        /// <summary>
        /// Removes all items from the bag.
        /// </summary>
        /// <remarks>Clearing the bag takes a constant amount of time, regardless of the number of items in it.</remarks>