orderedbag.cs

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

        /// <para>The symmetric difference of two bags is computed in time O(M + N), where M is the size of the 
        /// larger bag, and N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to symmetric difference with.</param>
        /// <returns>The symmetric difference of the two bags.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public OrderedBag<T> SymmetricDifference(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);
            OrderedBag<T> result = new OrderedBag<T>(comparer);
            IEnumerator<T> enum1 = this.GetEnumerator(), enum2 = otherBag.GetEnumerator();

            bool valid1 = enum1.MoveNext();
            bool valid2 = enum2.MoveNext();
            int compare;
            for (;;) {
                // Which item is smaller? The end (!valid) is considered larger than any item.
                if (! valid1) {
                    if (! valid2)
                        break;
                    compare = 1;
                }
                else if (! valid2)
                    compare = -1;
                else 
                    compare = comparer.Compare(enum1.Current, enum2.Current);

                // If equal, move through both bags without adding. Otherwise, add the smaller item and advance
                // just through that bag.
                if (compare == 0) {
                    valid1 = enum1.MoveNext();
                    valid2 = enum2.MoveNext();
                }
                else if (compare < 0) {
                    result.Add(enum1.Current);
                    valid1 = enum1.MoveNext();
                }
                else { // compare > 0
                    result.Add(enum2.Current);
                    valid2 = enum2.MoveNext();
                }
            }

            return result;
        }

        #endregion Set operations

        #region Read-only list view

        /// <summary>
        /// Get a read-only list view of the items in this ordered bag. 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 OrderedBag.
        /// </summary>
        /// <returns>A read-only IList&lt;T&gt; view onto this OrderedBag.</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 OrderedBag<T> myBag;
            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="myBag">The ordered bag to wrap.</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(OrderedBag<T> myBag, RedBlackTree<T>.RangeTester rangeTester, bool entireTree, bool reversed)
            {
                this.myBag = myBag;
                this.rangeTester = rangeTester;
                this.entireTree = entireTree;
                this.reversed = reversed;
            }

            public sealed override int Count
            {
                get
                {
                    if (entireTree)
                        return myBag.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 myBag.tree.CountRange(rangeTester);
                    }
                }
            }

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

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

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

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

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

                    }
                    else {
                        int indexInSet = myBag.tree.FindIndex(item, true);
                        if (indexInSet < 0)
                            return -1;
                        int indexOfStart = myBag.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 bag in 
        /// reversed order.
        /// </summary>
        ///<remarks>
        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
        ///<code>
        /// foreach(T item in bag.Reversed()) {
        ///    // process item
        /// }
        ///</code></p>
        /// <p>If an item is added to or deleted from the bag 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 OrderedBag.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 bag.
        /// 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 or equal to <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 bag.Range(from, true, to, false)) {
        ///    // process item
        /// }
        ///</code></p>
        /// <p>If an item is added to or deleted from the bag 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 OrderedBag.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
        {
            return new View(this, tree.DoubleBoundedRangeTester(from, fromInclusive, to, toInclusive), false, false);
        }

        /// <summary>
        /// Returns a View collection that can be used for enumerating a range of the items in the bag.
        /// Only items that are greater than (and optionally, equal to) <paramref name="from"/> are included. 
        /// The items are enumerated in sorted order. Items equal to <paramref name="from"/> can be included
        /// or excluded depending on the <paramref name="fromInclusive"/> parameter.
        /// </summary>
        ///<remarks>
        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
        ///<code>
        /// foreach(T item in bag.RangeFrom(from, true)) {
        ///    // process item
        /// }
        ///</code></p>
        /// <p>If an item is added to or deleted from the bag while the View is being enumerated, then 
        /// the enumeration will end with an InvalidOperationException.</p>
        ///<p>Calling RangeFrom 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>
        /// <returns>An OrderedBag.View of items in the given range.</returns>
        public View RangeFrom(T from, bool fromInclusive)  // A partial view that can be enumerated
        {
            return new View(this, tree.LowerBoundedRangeTester(from, fromInclusive), false, false);
        }

        /// <summary>
        /// Returns a View collection that can be used for enumerating a range of the items in the bag.
        /// Only items that are less than (and optionally, equal to) <paramref name="to"/> are included. 
        /// The items are enumerated in sorted order. Items equal to <paramref name="to"/> can be included
        /// or excluded depending on the <paramref name="toInclusive"/> parameter.
        /// </summary>
        ///<remarks>
        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
        ///<code>
        /// foreach(T item in bag.RangeTo(to, false)) {
        ///    // process item
        /// }
        ///</code></p>
        /// <p>If an item is added to or deleted from the bag while the View is being enumerated, then 
        /// the enumeration will end with an InvalidOperationException.</p>
        ///<p>Calling RangeTo does not copy the data in the tree, and the operation takes constant time.</p>
        ///</remarks>
        /// <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 inc