orderedset.cs

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

            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 set..
        /// 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 set.RangeFrom(from, true)) {
        ///    // 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 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 OrderedSet.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 set..
        /// 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 set.RangeTo(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 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 included in the range.</param>
        /// <returns>An OrderedSet.View of items in the given range.</returns>
        public View RangeTo(T to, bool toInclusive)  // A partial view that can be enumerated
        {
            return new View(this, tree.UpperBoundedRangeTester(to, toInclusive), false, false);
        }

        #endregion
        
        #region View nested class
   
        /// <summary>
        /// The OrderedSet&lt;T&gt;.View class is used to look at a subset of the Items
        /// inside an ordered set. It is returned from the Range, RangeTo, RangeFrom, and Reversed methods. 
        /// </summary>
        ///<remarks>
        /// <p>Views are dynamic. If the underlying set changes, the view changes in sync. If a change is made
        /// to the view, the underlying set changes accordingly.</p>
        ///<p>Typically, this class is used in conjunction with a foreach statement to enumerate the items 
        /// in a subset of the OrderedSet. For example:</p>
        ///<code>
        /// foreach(T item in set.Range(from, to)) {
        ///    // process item
        /// }
        ///</code>
        ///</remarks>
        [Serializable]
        public class View : CollectionBase<T>, ICollection<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>
            /// Initialize the view.
            /// </summary>
            /// <param name="mySet">OrderedSet being viewed</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>
            internal View(OrderedSet<T> mySet, RedBlackTree<T>.RangeTester rangeTester, bool entireTree, bool reversed)
            {
                this.mySet = mySet;
                this.rangeTester = rangeTester;
                this.entireTree = entireTree;
                this.reversed = reversed;
            }

            /// <summary>
            /// Determine if the given item lies within the bounds of this view.
            /// </summary>
            /// <param name="item">Item to test.</param>
            /// <returns>True if the item is within the bounds of this view.</returns>
            private bool ItemInView(T item)
            {
                return rangeTester(item) == 0;
            }

            /// <summary>
            /// Enumerate all the items in this view.
            /// </summary>
            /// <returns>An IEnumerator&lt;T&gt; with the items in this view.</returns>
            public sealed override IEnumerator<T> GetEnumerator()
            {
                if (reversed)
                    return mySet.tree.EnumerateRangeReversed(rangeTester).GetEnumerator();
                else
                    return mySet.tree.EnumerateRange(rangeTester).GetEnumerator();
            }

            /// <summary>
            /// Number of items in this view.
            /// </summary>
            /// <value>Number of items that lie within the bounds the view.</value>
            public sealed 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);
                    }
                }
            }

            /// <summary>
            /// Removes all the items within this view from the underlying set.
            /// </summary>
            /// <example>The following removes all the items that start with "A" from an OrderedSet.
            /// <code>
            /// set.Range("A", "B").Clear();
            /// </code>
            /// </example>
            public sealed override void Clear()
            {
                if (entireTree) {
                    mySet.Clear();   // much faster than DeleteRange
                }
                else {
                    mySet.tree.DeleteRange(rangeTester);
                }
            }

            /// <summary>
            /// Adds a new item to the set underlying this View. If the set already contains an item equal to
            /// <paramref name="item"/>, that item is replaces with <paramref name="item"/>. If
            /// <paramref name="item"/> is outside the range of this view, an InvalidOperationException
            /// is thrown.
            /// </summary>
            /// <remarks>
            /// <para>Equality between items is determined by the comparison instance or delegate used
            /// to create the set.</para>
            /// <para>Adding an item takes time O(log N), where N is the number of items in the set.</para></remarks>
            /// <param name="item">The item to add.</param>
            /// <returns>True if the set already contained an item equal to <paramref name="item"/> (which was replaced), false 
            /// otherwise.</returns>
            public new bool Add(T item)
            {
                if (!ItemInView(item))
                    throw new ArgumentException(Strings.OutOfViewRange, "item");
                else
                    return mySet.Add(item);
            }

            /// <summary>
            /// Adds a new item to the set underlying this View. If the set already contains an item equal to
            /// <paramref name="item"/>, that item is replaces with <paramref name="item"/>. If
            /// <paramref name="item"/> is outside the range of this view, an InvalidOperationException
            /// is thrown.
            /// </summary>
            /// <remarks>
            /// <para>Equality between items is determined by the comparison instance or delegate used
            /// to create the set.</para>
            /// <para>Adding an item takes time O(log N), where N is the number of items in the set.</para></remarks>
            /// <param name="item">The item to add.</param>
            void ICollection<T>.Add(T item)
            {
                Add(item);
            }

            /// <summary>
            /// Searches the underlying set for an item equal to <paramref name="item"/>, and if found,
            /// removes it from the set. If not found, the set is unchanged. If the item is outside
            /// the range of this view, the set is unchanged.
            /// </summary>
            /// <remarks>
            /// <para>Equality between items is determined by the comparison instance or delegate used
            /// to create the set.</para>
            /// <para>Removing an item from the set takes time O(log N), where N is the number of items in the set.</para></remarks>
            /// <param name="item">The item to remove.</param>
            /// <returns>True if <paramref name="item"/> was found and removed. False if <paramref name="item"/> was not in the set, or
            /// was outside the range of this view.</returns>
            public sealed override bool Remove(T item)
            {
                if (!ItemInView(item))
                    return false;
                else
                    return mySet.Remove(item);
            }

            /// <summary>
            /// Determines if this view of the set contains an item equal to <paramref name="item"/>. The set
            /// is not changed. If 
            /// </summary>
            /// <remarks>Searching the set for an item takes time O(log N), where N is 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"/>, and <paramref name="item"/> is within
            /// the range of this view. False otherwise.</returns>
            public sealed override bool Contains(T item)
            {
                if (!ItemInView(item))
                    return false;
                else
                    return mySet.Contains(item);
            }

            /// <summary>
            /// Get the index of the given item in the view. The smallest item in the view has index 0,
            /// the next smallest item has index 1, and the largest item has index Count-1. 
            /// </summary>
            /// <remarks>Finding the index takes time O(log N), which N is the number of items in 
            /// the set.</remarks>
            /// <param name="item">The item to get the index of.</param>
            /// <returns>The index of the item in the view, or -1 if the item is not present
            /// in the view.</returns>
            public int IndexOf(T item)
            {
                if (entireTree) {
                    if (reversed) {
                        int indexInSet = mySet.tree.FindIndex(item, false);
                        if (indexInSet < 0)
                            return -1;

                        return mySet.Count - 1 - indexInSet;
                    }
                    else {
                        return mySet.tree.FindIndex(item, true);
                    }
                }
                else {
                    T dummy;

                    if (!ItemInView(item))
                        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);