orderedset.cs

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

        /// </summary>
        /// <param name="otherSet">OrderedSet to compare to.</param>
        /// <returns>True if this is a superset of <paramref name="otherSet"/>.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public bool IsSupersetOf(OrderedSet<T> otherSet)
        {
            CheckConsistentComparison(otherSet);

            if (otherSet.Count > this.Count)
                return false;     // Can't be a superset of a bigger set

            // Check each item in the other set to make sure it is in this set.
            foreach (T item in otherSet) {
                if (!this.Contains(item))
                    return false;
            }

            return true;
        }

        /// <summary>
        /// Determines if this set is a proper superset of another set. Neither set is modified.
        /// This set is a proper superset of <paramref name="otherSet"/> if every element in
        /// <paramref name="otherSet"/> is also in this set.
        /// Additionally, this set must have strictly more items than <paramref name="otherSet"/>.
        /// </summary>
        /// <remarks>IsProperSupersetOf is computed in time O(M log N), where M is the number of unique items in 
        /// <paramref name="otherSet"/>.</remarks>
        /// <param name="otherSet">OrderedSet to compare to.</param>
        /// <returns>True if this is a proper superset of <paramref name="otherSet"/>.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public bool IsProperSupersetOf(OrderedSet<T> otherSet)
        {
            CheckConsistentComparison(otherSet);

            if (otherSet.Count >= this.Count)
                return false;     // Can't be a proper superset of a bigger or equal set

            return IsSupersetOf(otherSet);
        }

        /// <summary>
        /// Determines if this set is a subset of another set. Neither set is modified.
        /// This set is a subset of <paramref name="otherSet"/> if every element in this set
        /// is also in <paramref name="otherSet"/>.
        /// </summary>
        /// <remarks>IsSubsetOf is computed in time O(N log M), where M is the size of the 
        /// <paramref name="otherSet"/>, and N is the size of the this set.</remarks>
        /// <param name="otherSet">Set to compare to.</param>
        /// <returns>True if this is a subset of <paramref name="otherSet"/>.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public bool IsSubsetOf(OrderedSet<T> otherSet)
        {
            return otherSet.IsSupersetOf(this);
        }


        /// <summary>
        /// Determines if this set is a proper subset of another set. Neither set is modified.
        /// This set is a subset of <paramref name="otherSet"/> if every element in this set
        /// is also in <paramref name="otherSet"/>. Additionally, this set must have strictly 
        /// fewer items than <paramref name="otherSet"/>.
        /// </summary>
        /// <remarks>IsSubsetOf is computed in time O(N log M), where M is the size of the 
        /// <paramref name="otherSet"/>, and N is the size of the this set.</remarks>
        /// <param name="otherSet">Set to compare to.</param>
        /// <returns>True if this is a proper subset of <paramref name="otherSet"/>.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public bool IsProperSubsetOf(OrderedSet<T> otherSet)
        {
            return otherSet.IsProperSupersetOf(this);
        }

        /// <summary>
        /// Determines if this set is equal to another set. This set is equal to
        /// <paramref name="otherSet"/> if they contain the same items.
        /// </summary>
        /// <remarks>IsEqualTo is computed in time O(N), where N is the number of items in 
        /// this set.</remarks>
        /// <param name="otherSet">Set to compare to</param>
        /// <returns>True if this set is equal to <paramref name="otherSet"/>, false otherwise.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public bool IsEqualTo(OrderedSet<T> otherSet)
        {
            CheckConsistentComparison(otherSet);

            // Must be the same size.
            if (otherSet.Count != this.Count)
                return false;

            // Since both sets are ordered, we can simply compare items in order.
            using (IEnumerator<T> enum1 = this.GetEnumerator(), enum2 = otherSet.GetEnumerator()) {
                bool continue1, continue2;

                for (; ; ) {
                    continue1 = enum1.MoveNext(); continue2 = enum2.MoveNext();
                    if (!continue1 || !continue2)
                        break;

                    if (comparer.Compare(enum1.Current, enum2.Current) != 0)
                        return false;     // the two items are not equal.
                }

                // If both continue1 and continue2 are false, we reached the end of both sequences at the same
                // time and found success. If one is true and one is false, the sequences were of difference lengths -- failure.
                return (continue1 == continue2);
            }
        }

        /// <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 log M), 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(OrderedSet<T> otherSet)
        {
            CheckConsistentComparison(otherSet);

            AddMany(otherSet);

            // CONSIDER: if RedBlackTree cloning is O(N), then if otherSet is much larger, better to clone it,
            // add all of the current into it, and replace.
        }

        /// <summary>
        /// Determines if this set is disjoint from another set. Two sets are disjoint
        /// if no item from one set is equal to any item in the other set.
        /// </summary>
        /// <remarks>
        /// <para>The answer is computed in time O(N log M), 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 check disjointness with.</param>
        /// <returns>True if the two sets are disjoint, false otherwise.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public bool IsDisjointFrom(OrderedSet<T> otherSet)
        {
            CheckConsistentComparison(otherSet);
            OrderedSet<T> smaller, larger;
            if (otherSet.Count > this.Count) {
                smaller = this; larger = otherSet;
            }
            else {
                smaller = otherSet; larger = this;
            }

            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. 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 log M), 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>
        /// <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 OrderedSet<T> Union(OrderedSet<T> otherSet)
        {
            CheckConsistentComparison(otherSet);
            OrderedSet<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 log M), 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 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(OrderedSet<T> otherSet)
        {
            CheckConsistentComparison(otherSet);
            tree.StopEnumerations();

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

            T dummy;
            RedBlackTree<T> newTree = new RedBlackTree<T>(comparer);

            foreach (T item in smaller) {
                if (larger.Contains(item))
                    newTree.Insert(item, DuplicatePolicy.ReplaceFirst, out dummy);
            }

            tree = newTree;
        }

        /// <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 log M), 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 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 OrderedSet<T> Intersection(OrderedSet<T> otherSet)
        {
            CheckConsistentComparison(otherSet);
            OrderedSet<T> smaller, larger, result;
            if (otherSet.Count > this.Count) {
                smaller = this; larger = otherSet;
            }
            else {
                smaller = otherSet; larger = this;
            }

            result = new OrderedSet<T>(comparer);
            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(M + N log M), 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 difference with.</param>