set.cs

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

//******************************
// Written by Peter Golde
// Copyright (c) 2004-2005, Wintellect
//
// Use and restribution of this code is subject to the license agreement 
// contained in the file "License.txt" accompanying this file.
//******************************

using System;
using System.Collections.Generic;
using System.Collections;
using System.Diagnostics;

namespace Wintellect.PowerCollections
{
    /// <summary>
    /// Set&lt;T&gt; is a collection that contains items of type T. 
    /// The item are maintained in a haphazard, unpredictable order, and duplicate items are not allowed.
    /// </summary>
    /// <remarks>
    /// <p>The items are compared in one of two ways. If T implements IComparable&lt;T&gt; 
    /// then the Equals method of that interface will be used to compare items, otherwise the Equals
    /// method from Object will be used. Alternatively, an instance of IComparer&lt;T&gt; can be passed
    /// to the constructor to use to compare items.</p>
    /// <p>Set is implemented as a hash table. Inserting, deleting, and looking up an
    /// an element all are done in approximately constant time, regardless of the number of items in the Set.</p>
    /// <p><see cref="OrderedSet&lt;T&gt;"/> is similar, but uses comparison instead of hashing, and does maintains
    /// the items in sorted order.</p>
    ///</remarks>
    ///<seealso cref="OrderedSet&lt;T&gt;"/>
    [Serializable]
    public class Set<T> : CollectionBase<T>, ICollection<T>, ICloneable
    {
        // The comparer used to hash/compare items. 
        private IEqualityComparer<T> equalityComparer;

        // The hash table that actually does the work of storing the items.
        private Hash<T> hash;

        #region Constructors

        /// <summary>
        /// Creates a new Set. The Equals method and GetHashCode method on T
        /// will be used to compare items for equality.
        /// </summary>
        ///<remarks>
        /// Items that are null are permitted, and will be sorted before all other items.
        ///</remarks>
        public Set(): 
            this(EqualityComparer<T>.Default)
        {
        }

        /// <summary>
        /// Creates a new Set. The Equals and GetHashCode method of the passed comparer object
        /// will be used to compare items in this set.
        /// </summary>
        /// <param name="equalityComparer">An instance of IEqualityComparer&lt;T&gt; that will be used to compare items.</param>
        public Set(IEqualityComparer<T> equalityComparer)
        {
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            this.equalityComparer = equalityComparer;
            hash = new Hash<T>(equalityComparer);
        }

        /// <summary>
        /// Creates a new Set. The Equals method and GetHashCode method on T
        /// will be used to compare items for equality.
        /// </summary>
        ///<remarks>
        /// Items that are null are permitted.
        ///</remarks>
        /// <param name="collection">A collection with items to be placed into the Set.</param>
        public Set(IEnumerable<T> collection): 
            this(collection, EqualityComparer<T>.Default)
        {
        }

        /// <summary>
        /// Creates a new Set. The Equals and GetHashCode method of the passed comparer object
        /// will be used to compare items in this set. The set is
        /// initialized with all the items in the given collection.
        /// </summary>
        /// <param name="collection">A collection with items to be placed into the Set.</param>
        /// <param name="equalityComparer">An instance of IEqualityComparer&lt;T&gt; that will be used to compare items.</param>
        public Set(IEnumerable<T> collection, IEqualityComparer<T> equalityComparer)
           : this(equalityComparer)
        {
            AddMany(collection);
        }

        /// <summary>
        /// Creates a new Set given a comparer and a tree that contains the data. Used
        /// internally for Clone.
        /// </summary>
        /// <param name="equalityComparer">EqualityComparer for the set.</param>
        /// <param name="hash">Data for the set.</param>
        private Set(IEqualityComparer<T> equalityComparer, Hash<T> hash)
        {
            this.equalityComparer = equalityComparer;
            this.hash = hash;
        }

        #endregion Constructors

        #region Cloning

        /// <summary>
        /// Makes a shallow clone of this set; i.e., if items of the
        /// set are reference types, then they are not cloned. If T is a value type,
        /// then each element is copied as if by simple assignment.
        /// </summary>
        /// <remarks>Cloning the set takes time O(N), where N is the number of items in the set.</remarks>
        /// <returns>The cloned set.</returns>
        object ICloneable.Clone()
        {
            return this.Clone();
        }

        /// <summary>
        /// Makes a shallow clone of this set; i.e., if items of the
        /// set are reference types, then they are not cloned. If T is a value type,
        /// then each element is copied as if by simple assignment.
        /// </summary>
        /// <remarks>Cloning the set takes time O(N), where N is the number of items in the set.</remarks>
        /// <returns>The cloned set.</returns>
        public Set<T> Clone()
        {
            Set<T> newSet = new Set<T>(equalityComparer, hash.Clone(null));
            return newSet; 
        }

        /// <summary>
        /// Makes a deep clone of this set. A new set is created with a clone of
        /// each element of this set, by calling ICloneable.Clone on each element. If T is
        /// a value type, then each element is copied as if by simple assignment.
        /// </summary>
        /// <remarks><para>If T is a reference type, it must implement
        /// ICloneable. Otherwise, an InvalidOperationException is thrown.</para>
        /// <para>Cloning the set takes time O(N), where N is the number of items in the set.</para></remarks>
        /// <returns>The cloned set.</returns>
        /// <exception cref="InvalidOperationException">T is a reference type that does not implement ICloneable.</exception>
        public Set<T> CloneContents()
        {
            bool itemIsValueType;
            if (!Util.IsCloneableType(typeof(T), out itemIsValueType))
                throw new InvalidOperationException(string.Format(Strings.TypeNotCloneable, typeof(T).FullName));

            Set<T> clone = new Set<T>(equalityComparer);

            // Clone each item, and add it to the new ordered set.
            foreach (T item in this) {
                T itemClone;

                if (itemIsValueType)
                    itemClone = item;
                else {
                    if (item == null)
                        itemClone = default(T);    // Really null, because we know T is a reference type
                    else
                        itemClone = (T)(((ICloneable)item).Clone());
                }

                clone.Add(itemClone);
            }

            return clone;
        }

        #endregion Cloning

        #region Basic collection containment

        /// <summary>
        /// Returns the IEqualityComparer&lt;T&gt; used to compare items in this set. 
        /// </summary>
        /// <value>If the set was created using a comparer, that comparer is returned. Otherwise
        /// the default comparer for T (EqualityComparer&lt;T&gt;.Default) is returned.</value>
        public IEqualityComparer<T> Comparer
        {
            get
            {
                return this.equalityComparer;
            }
        }

        /// <summary>
        /// Returns the number of items in the set.
        /// </summary>
        /// <remarks>The size of the set is returned in constant time.</remarks>
        /// <value>The number of items in the set.</value>
        public sealed override int Count
        {
            get
            {
                return hash.ElementCount;
            }
        }

        /// <summary>
        /// Returns an enumerator that enumerates all the items in the set. 
        /// The items are enumerated in sorted order.
        /// </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 set while it is being enumerated, then 
        /// the enumeration will end with an InvalidOperationException.</p>
        /// <p>Enumerating all the items in the set takes time O(N), where N is the number
        /// of items in the set.</p>
        /// </remarks>
        /// <returns>An enumerator for enumerating all the items in the Set.</returns>		
        public sealed override IEnumerator<T> GetEnumerator()
        {
            return hash.GetEnumerator();
        }

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

        /// <summary>
        /// <para>Determines if this set contains an item equal to <paramref name="item"/>, according to the 
        /// comparison mechanism that was used when the set was created. The set
        /// is not changed.</para>
        /// <para>If the set does contain an item equal to <paramref name="item"/>, then the item from the set is returned.</para>
        /// </summary>
        /// <remarks>Searching the set for an item takes approximately constant time, regardless of the number of items in the set.</remarks>
        /// <example>
        /// In the following example, the set contains strings which are compared in a case-insensitive manner. 
        /// <code>
        /// Set&lt;string&gt; set = new Set&lt;string&gt;(StringComparer.CurrentCultureIgnoreCase);
        /// set.Add("HELLO");
        /// string s;
        /// bool b = set.TryGetItem("Hello", out s);   // b receives true, s receives "HELLO".
        /// </code>
        /// </example>
        /// <param name="item">The item to search for.</param>
        /// <param name="foundItem">Returns the item from the set that was equal to <paramref name="item"/>.</param>
        /// <returns>True if the set contains <paramref name="item"/>. False if the set does not contain <paramref name="item"/>.</returns>
        public bool TryGetItem(T item, out T foundItem)
        {
            return hash.Find(item, false, out foundItem);
        }

        #endregion

        #region Adding elements