orderedset.cs

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

        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public void DifferenceWith(OrderedSet<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(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>
        /// <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 OrderedSet<T> Difference(OrderedSet<T> otherSet)
        {
            CheckConsistentComparison(otherSet);
            OrderedSet<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(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 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(OrderedSet<T> otherSet)
        {
            // Symmetric difference with myself is nothing. This check is needed because the
            // main algorithm doesn't work correctly otherwise.
            if (this == otherSet)
                Clear();

            CheckConsistentComparison(otherSet);

            // CONSIDER: if otherSet is larger, better to clone it and reverse the below?
            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(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 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 OrderedSet<T> SymmetricDifference(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();
            foreach (T item in smaller) {
                if (result.Contains(item))
                    result.Remove(item);
                else
                    result.Add(item);
            }

            return result;
        }

        #endregion Set operations

        #region Read-only list view

        /// <summary>
        /// Get a read-only list view of the items in this ordered set. The
        /// items in the list are in sorted order, with the smallest item
        /// at index 0. This view does not copy any data, and reflects any
        /// changes to the underlying OrderedSet.
        /// </summary>
        /// <returns>A read-only IList&lt;T&gt; view onto this OrderedSet.</returns>
        public IList<T> AsList()
        {
            return new ListView(this, tree.EntireRangeTester, true, false);
        }

        /// <summary>
        /// The nested class that provides a read-only list view
        /// of all or part of the collection.
        /// </summary>
        [Serializable]
        private class ListView : ReadOnlyListBase<T>
        {
            private OrderedSet<T> mySet;
            private RedBlackTree<T>.RangeTester rangeTester;   // range tester for the range being used.
            private bool entireTree;                   // is the view the whole tree?
            private bool reversed;                     // is the view reversed?

            /// <summary>
            /// Create a new list view wrapped the given set.
            /// </summary>
            /// <param name="mySet"></param>
            /// <param name="rangeTester">Range tester that defines the range being used.</param>
            /// <param name="entireTree">If true, then rangeTester defines the entire tree. Used to optimize some operations.</param>
            /// <param name="reversed">Is the view enuemerated in reverse order?</param>
            public ListView(OrderedSet<T> mySet, RedBlackTree<T>.RangeTester rangeTester, bool entireTree, bool reversed)
            {
                this.mySet = mySet;
                this.rangeTester = rangeTester;
                this.entireTree = entireTree;
                this.reversed = reversed;
            }

            public override int Count
            {
                get
                {
                    if (entireTree)
                        return mySet.Count;
                    else {
                        // Note: we can't cache the result of this call because the underlying
                        // set can change, which would make the cached value incorrect.
                        return mySet.tree.CountRange(rangeTester);
                    }
                }
            }

            public override T this[int index]
            {
                get
                {
                    if (entireTree) {
                        if (reversed)
                            return mySet[mySet.Count - 1 - index];
                        else
                            return mySet[index];
                    }
                    else {
                        T dummy;
                        int firstIndex = mySet.tree.FirstItemInRange(rangeTester, out dummy);
                        int lastIndex = mySet.tree.LastItemInRange(rangeTester, out dummy);
                        if (firstIndex < 0 || lastIndex < 0 || index < 0 || index >= (lastIndex - firstIndex + 1))
                            throw new ArgumentOutOfRangeException("index");

                        if (reversed) 
                            return mySet[lastIndex - index];
                        else 
                            return mySet[firstIndex + index];
                    }
                }
            }

            public override int IndexOf(T item)
            {
                if (entireTree) {
                    if (reversed)
                        return mySet.Count - 1 - mySet.IndexOf(item);
                    else
                        return mySet.IndexOf(item);
                }
                else {
                    T dummy;

                    if (rangeTester(item) != 0)
                        return -1;

                    if (reversed) {
                        int indexInSet = mySet.tree.FindIndex(item, false);
                        if (indexInSet < 0)
                            return -1;
                        int indexOfEnd = mySet.tree.LastItemInRange(rangeTester, out dummy);
                        return indexOfEnd - indexInSet;

                    }
                    else {
                        int indexInSet = mySet.tree.FindIndex(item, true);
                        if (indexInSet < 0)
                            return -1;
                        int indexOfStart = mySet.tree.FirstItemInRange(rangeTester, out dummy);
                        return indexInSet - indexOfStart;
                    }
                }
            }
        }

        #endregion Read-only list view

        #region Sub-views

        /// <summary>
        /// Returns a View collection that can be used for enumerating the items in the set in 
        /// reversed order.
        /// </summary>
        ///<remarks>
        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
        ///<code>
        /// foreach(T item in set.Reversed()) {
        ///    // process item
        /// }
        ///</code></p>
        /// <p>If an item is added to or deleted from the set 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 tree, and the operation takes constant time.</p>
        ///</remarks>
        /// <returns>An OrderedSet.View of items in reverse order.</returns>
        public View Reversed()   // A reversed view that can be enumerated
        {
            return new View(this, tree.EntireRangeTester, true, true);
        }

        /// <summary>
        /// Returns a View collection that can be used for enumerating a range of the items in the set..
        /// Only items that are greater than <paramref name="from"/> and 
        /// less than <paramref name="to"/> are included. The items are enumerated in sorted order.
        /// Items 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 <paramref name="to"/>, the returned collection is empty. </p>
        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
        ///<code>
        /// foreach(T item in set.Range(from, true, to, false)) {
        ///    // process item
        /// }
        ///</code></p>
        /// <p>If an item is added to or deleted from the set while the View is being enumerated, then 
        /// the enumeration will end with an InvalidOperationException.</p>
        ///<p>Calling Range does not copy the data in the tree, 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--items equal to the lower bound will
        /// be included in the range. If false, the lower bound is exclusive--items 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--items equal to the upper bound will
        /// be included in the range. If false, the upper bound is exclusive--items equal to the upper bound will not
        /// be included in the range.</param>
        /// <returns>An OrderedSet.View of items in the given range.</returns>
        public View Range(T from, bool fromInclusive, T to, bool toInclusive)  // A partial view that can be enumerated
        {