set.cs

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

            }

            foreach (T item in smaller) {
                if (larger.Contains(item))
                    return false;
            }

            return true;
        }

        /// <summary>
        /// Computes the union of this set with another set. The union of two sets
        /// is all items that appear in either or both of the sets. This set receives
        /// the union of the two sets, the other set is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>If equal items appear in both sets, the union will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <para>The union of two sets is computed in time O(M + N), where M is the size of the 
        /// larger set, and N is the size of the smaller set.</para>
        /// </remarks>
        /// <param name="otherSet">Set to union with.</param>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public void UnionWith(Set<T> otherSet)
        {
            CheckConsistentComparison(otherSet);

            AddMany(otherSet);
        }

        /// <summary>
        /// Computes the union of this set with another set. The union of two sets
        /// is all items that appear in either or both of the sets. A new set is 
        /// created with the union of the sets and is returned. This set and the other set 
        /// are unchanged.
        /// </summary>
        /// <remarks>
        /// <para>If equal items appear in both sets, the union will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <para>The union of two sets is computed in time O(M + N), where M is the size of the 
        /// one set, and N is the size of the other set.</para>
        /// </remarks>
        /// <param name="otherSet">Set to union with.</param>
        /// <returns>The union of the two sets.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public Set<T> Union(Set<T> otherSet)
        {
            CheckConsistentComparison(otherSet);
            Set<T> smaller, larger, result;
            if (otherSet.Count > this.Count) {
                smaller = this; larger = otherSet;
            }
            else {
                smaller = otherSet; larger = this;
            }

            result = larger.Clone();
            result.AddMany(smaller);
            return result; 
        }

        /// <summary>
        /// Computes the intersection of this set with another set. The intersection of two sets
        /// is all items that appear in both of the sets. This set receives
        /// the intersection of the two sets, the other set is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>When equal items appear in both sets, the intersection will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <para>The intersection of two sets is computed in time O(N), where N is the size of the smaller set.</para>
        /// </remarks>
        /// <param name="otherSet">Set to intersection with.</param>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public void IntersectionWith(Set<T> otherSet)
        {
            CheckConsistentComparison(otherSet);
            hash.StopEnumerations();

            Set<T> smaller, larger;
            if (otherSet.Count > this.Count) {
                smaller = this; larger = otherSet;
            }
            else {
                smaller = otherSet; larger = this;
            }

            T dummy;
            Hash<T> newHash = new Hash<T>(equalityComparer);

            foreach (T item in smaller) {
                if (larger.Contains(item))
                    newHash.Insert(item, true, out dummy);
            }

            hash = newHash;
        }

        /// <summary>
        /// Computes the intersection of this set with another set. The intersection of two sets
        /// is all items that appear in both of the sets. A new set is 
        /// created with the intersection of the sets and is returned. This set and the other set 
        /// are unchanged.
        /// </summary>
        /// <remarks>
        /// <para>When equal items appear in both sets, the intersection will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <para>The intersection of two sets is computed in time O(N), where N is the size of the smaller set.</para>
        /// </remarks>
        /// <param name="otherSet">Set to intersection with.</param>
        /// <returns>The intersection of the two sets.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public Set<T> Intersection(Set<T> otherSet)
        {
            CheckConsistentComparison(otherSet);
            Set<T> smaller, larger, result;
            if (otherSet.Count > this.Count) {
                smaller = this; larger = otherSet;
            }
            else {
                smaller = otherSet; larger = this;
            }

            result = new Set<T>(equalityComparer);
            foreach (T item in smaller) {
                if (larger.Contains(item))
                    result.Add(item);
            }

            return result; 
        }

        /// <summary>
        /// Computes the difference of this set with another set. The difference of these two sets
        /// is all items that appear in this set, but not in <paramref name="otherSet"/>. This set receives
        /// the difference of the two sets; the other set is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The difference of two sets is computed in time O(N), where N is the size of the smaller set.</para>
        /// </remarks>
        /// <param name="otherSet">Set to difference with.</param>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public void DifferenceWith(Set<T> otherSet)
        {
            // Difference with myself is nothing. This check is needed because the
            // main algorithm doesn't work correctly otherwise.
            if (this == otherSet)
                Clear();

            CheckConsistentComparison(otherSet);

            if (otherSet.Count < this.Count) {
                foreach (T item in otherSet) {
                    this.Remove(item);
                }
            }
            else {
                RemoveAll(delegate(T item) { return otherSet.Contains(item); });
            }
        }

        /// <summary>
        /// Computes the difference of this set with another set. The difference of these two sets
        /// is all items that appear in this set, but not in <paramref name="otherSet"/>. A new set is 
        /// created with the difference of the sets and is returned. This set and the other set 
        /// are unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The difference of two sets is computed in time O(N), where N is the size of the smaller set.</para>
        /// </remarks>
        /// <param name="otherSet">Set to difference with.</param>
        /// <returns>The difference of the two sets.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public Set<T> Difference(Set<T> otherSet)
        {
            CheckConsistentComparison(otherSet);
            Set<T> result = this.Clone();
            result.DifferenceWith(otherSet);
            return result; 
        }

        /// <summary>
        /// Computes the symmetric difference of this set with another set. The symmetric difference of two sets
        /// is all items that appear in either of the sets, but not both. This set receives
        /// the symmetric difference of the two sets; the other set is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The symmetric difference of two sets is computed in time O(N), where N is the size of the smaller set.</para>
        /// </remarks>
        /// <param name="otherSet">Set to symmetric difference with.</param>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public void SymmetricDifferenceWith(Set<T> otherSet)
        {
            // main algorithm doesn't work correctly otherwise.
            if (this == otherSet)
                Clear();

            CheckConsistentComparison(otherSet);

            if (otherSet.Count > this.Count) {
                hash.StopEnumerations();
                Hash<T> newHash = otherSet.hash.Clone(null);
                T dummy;

                foreach (T item in this) {
                    if (newHash.Find(item, false, out dummy))
                        newHash.Delete(item, out dummy);
                    else
                        newHash.Insert(item, true, out dummy);
                }
                this.hash = newHash;
            }
            else {
                foreach (T item in otherSet) {
                    if (this.Contains(item))
                        this.Remove(item);
                    else
                        this.Add(item);
                }
            }
        }

        /// <summary>
        /// Computes the symmetric difference of this set with another set. The symmetric difference of two sets
        /// is all items that appear in either of the sets, but not both. A new set is 
        /// created with the symmetric difference of the sets and is returned. This set and the other set 
        /// are unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The symmetric difference of two sets is computed in time O(N), where N is the size of the smaller set.</para>
        /// </remarks>
        /// <param name="otherSet">Set to symmetric difference with.</param>
        /// <returns>The symmetric difference of the two sets.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public Set<T> SymmetricDifference(Set<T> otherSet)
        {
            CheckConsistentComparison(otherSet);
            Set<T> smaller, larger, result;
            if (otherSet.Count > this.Count) {
                smaller = this; larger = otherSet;
            }
            else {
                smaller = otherSet; larger = this;
            }

            result = larger.Clone();
            foreach (T item in smaller) {
                if (result.Contains(item))
                    result.Remove(item);
                else
                    result.Add(item);
            }

            return result;
        }

        #endregion Set operations

    }
}