algorithms.cs

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

                    wrappedArray[index] = value;
                }
            }

            public override void CopyTo(T[] array, int arrayIndex)
            {
                if (array == null)
                    throw new ArgumentNullException("array");
                if (array.Length < wrappedArray.Length)
                    throw new ArgumentException("array is too short", "array");
                if (arrayIndex < 0 || arrayIndex >= array.Length)
                    throw new ArgumentOutOfRangeException("arrayIndex");
                if (array.Length + arrayIndex < wrappedArray.Length)
                    throw new ArgumentOutOfRangeException("arrayIndex");

                Array.Copy(wrappedArray, 0, array, arrayIndex, wrappedArray.Length);
            }

            public override IEnumerator<T> GetEnumerator()
            {
                return ((IList<T>)wrappedArray).GetEnumerator();
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return ((IList)wrappedArray).GetEnumerator();
            }

            /// <summary>
            /// Return true, to indicate that the list is fixed size.
            /// </summary>
            bool IList.IsFixedSize
            {
                get
                {
                    return true;
                }
            }
        }

        /// <summary>
        /// <para>Creates a read-write IList&lt;T&gt; wrapper around an array. When an array is
        /// implicitely converted to an IList&lt;T&gt;, changes to the items in the array cannot
        /// be made through the interface. This method creates a read-write IList&lt;T&gt; wrapper
        /// on an array that can be used to make changes to the array. </para>
        /// <para>Use this method when you need to pass an array to an algorithms that takes an 
        /// IList&lt;T&gt; and that tries to modify items in the list. Algorithms in this class generally do not
        /// need this method, since they have been design to operate on arrays even when they
        /// are passed as an IList&lt;T&gt;.</para>
        /// </summary>
        /// <remarks>Since arrays cannot be resized, inserting an item causes the last item in the array to be automatically
        /// removed. Removing an item causes the last item in the array to be replaced with a default value (0 or null). Clearing
        /// the list causes all the items to be replaced with a default value.</remarks>
        /// <param name="array">The array to wrap.</param>
        /// <returns>An IList&lt;T&gt; wrapper onto <paramref name="array"/>.</returns>
        public static IList<T> ReadWriteList<T>(T[] array)
        {
            if (array == null)
                throw new ArgumentNullException("array");

            return new ArrayWrapper<T>(array);
        }

        #endregion Collection wrappers

        #region Replacing

        /// <summary>
        /// Replace all items in a collection equal to a particular value with another values, yielding another collection.
        /// </summary>
        /// <remarks>The default sense of equality for T is used, as defined by T's
        /// implementation of IComparable&lt;T&gt;.Equals or object.Equals.</remarks>
        /// <param name="collection">The collection to process.</param>
        /// <param name="itemFind">The value to find and replace within <paramref name="collection"/>.</param>
        /// <param name="replaceWith">The new value to replace with.</param>
        /// <returns>An new collection with the items from <paramref name="collection"/>, in the same order, 
        /// with the appropriate replacements made.</returns>
        public static IEnumerable<T> Replace<T>(IEnumerable<T> collection, T itemFind, T replaceWith)
        {
            return Replace<T>(collection, itemFind, replaceWith, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Replace all items in a collection equal to a particular value with another values, yielding another collection. A passed
        /// IEqualityComparer is used to determine equality.
        /// </summary>
        /// <param name="collection">The collection to process.</param>
        /// <param name="itemFind">The value to find and replace within <paramref name="collection"/>.</param>
        /// <param name="replaceWith">The new value to replace with.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. Only the Equals method will be called.</param>
        /// <returns>An new collection with the items from <paramref name="collection"/>, in the same order, 
        /// with the appropriate replacements made.</returns>
        public static IEnumerable<T> Replace<T>(IEnumerable<T> collection, T itemFind, T replaceWith, IEqualityComparer<T> equalityComparer)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            foreach (T item in collection) {
                if (equalityComparer.Equals(item, itemFind))
                    yield return replaceWith;
                else
                    yield return item;
            }
        }

        /// <summary>
        /// Replace all items in a collection that a predicate evalues at true with a value, yielding another collection. .
        /// </summary>
        /// <param name="collection">The collection to process.</param>
        /// <param name="predicate">The predicate used to evaluate items with the collection. If the predicate returns true for a particular
        /// item, the item is replaces with <paramref name="replaceWith"/>.</param>
        /// <param name="replaceWith">The new value to replace with.</param>
        /// <returns>An new collection with the items from <paramref name="collection"/>, in the same order, 
        /// with the appropriate replacements made.</returns>
        public static IEnumerable<T> Replace<T>(IEnumerable<T> collection, Predicate<T> predicate, T replaceWith)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            foreach (T item in collection) {
                if (predicate(item))
                    yield return replaceWith;
                else
                    yield return item;
            }
        }

        /// <summary>
        /// Replace all items in a list or array equal to a particular value with another value. The replacement is done in-place, changing
        /// the list.
        /// </summary>
        /// <remarks><para>The default sense of equality for T is used, as defined by T's
        /// implementation of IComparable&lt;T&gt;.Equals or object.Equals.</para>
        /// <para>Although arrays cast to IList&lt;T&gt; are normally read-only, this method
        /// will work correctly and modify an array passed as <paramref name="list"/>.</para></remarks>
        /// <param name="list">The list or array to process.</param>
        /// <param name="itemFind">The value to find and replace within <paramref name="collection"/>.</param>
        /// <param name="replaceWith">The new value to replace with.</param>
        public static void ReplaceInPlace<T>(IList<T> list, T itemFind, T replaceWith)
        {
            ReplaceInPlace(list, itemFind, replaceWith, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Replace all items in a list or array equal to a particular value with another values.
        /// The replacement is done in-place, changing
        /// the list. A passed IEqualityComparer is used to determine equality.
        /// </summary>
        /// <remarks>Although arrays cast to IList&lt;T&gt; are normally read-only, this method
        /// will work correctly and modify an array passed as <paramref name="list"/>.</remarks>
        /// <param name="list">The list or array to process.</param>
        /// <param name="itemFind">The value to find and replace within <paramref name="collection"/>.</param>
        /// <param name="replaceWith">The new value to replace with.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. Only the Equals method will be called.</param>
        public static void ReplaceInPlace<T>(IList<T> list, T itemFind, T replaceWith, IEqualityComparer<T> equalityComparer)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");
            if (list is T[])
                list = new ArrayWrapper<T>((T[])list);
            if (list.IsReadOnly)
                throw new ArgumentException(Strings.ListIsReadOnly, "list");

            int listCount = list.Count;
            for (int index = 0; index < listCount; ++index) {
                if (equalityComparer.Equals(list[index], itemFind))
                    list[index] = replaceWith;
            }
        }

        /// <summary>
        /// Replace all items in a list or array that a predicate evaluates at true with a value. The replacement is done in-place, changing
        /// the list.
        /// </summary>
        /// <remarks>Although arrays cast to IList&lt;T&gt; are normally read-only, this method
        /// will work correctly and modify an array passed as <paramref name="list"/>.</remarks>
        /// <param name="list">The list or array to process.</param>
        /// <param name="predicate">The predicate used to evaluate items with the collection. If the predicate returns true for a particular
        /// item, the item is replaces with <paramref name="replaceWith"/>.</param>
        /// <param name="replaceWith">The new value to replace with.</param>
        public static void ReplaceInPlace<T>(IList<T> list, Predicate<T> predicate, T replaceWith)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (predicate == null)
                throw new ArgumentNullException("predicate");
            if (list is T[])
                list = new ArrayWrapper<T>((T[])list);
            if (list.IsReadOnly)
                throw new ArgumentException(Strings.ListIsReadOnly, "list");

            int listCount = list.Count;
            for (int index = 0; index < listCount; ++index) {
                if (predicate(list[index]))
                    list[index] = replaceWith;
            }
        }

        #endregion Replacing

        #region Consecutive items

        /// <summary>
        /// Remove consecutive equal items from a collection, yielding another collection. In each run of consecutive equal items
        /// in the collection, all items after the first item in the run are removed. 
        /// </summary>
        /// <remarks>The default sense of equality for T is used, as defined by T's
        /// implementation of IComparable&lt;T&gt;.Equals or object.Equals.</remarks>
        /// <param name="collection">The collection to process.</param>
        /// <returns>An new collection with the items from <paramref name="collection"/>, in the same order, 
        /// with consecutive duplicates removed.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
        public static IEnumerable<T> RemoveDuplicates<T>(IEnumerable<T> collection)
        {
            return RemoveDuplicates<T>(collection, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Remove consecutive equal items from a collection, yielding another collection. In each run of consecutive equal items
        /// in the collection, all items after the first item in the run are removed. A passed
        /// IEqualityComparer is used to determine equality.
        /// </summary>
        /// <param name="collection">The collection to process.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. Only the Equals method will be called.</param>
        /// <returns>An new collection with the items from <paramref name="collection"/>, in the same order, 
        /// with consecutive duplicates removed.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> or <paramref name="equalityComparer"/> is null.</exception>
        public static IEnumerable<T> RemoveDuplicates<T>(IEnumerable<T> collection, IEqualityComparer<T> equalityComparer)
        {
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            return RemoveDuplicates<T>(collection, equalityComparer.Equals);

        }

        /// <summary>
        /// Remove consecutive "equal" items from a collection, yielding another collection. In each run of consecutive equal items
        /// in the collection, all items after the first item in the run are removed. The passed 
        /// BinaryPredicate is used to determine if two items are "equal".
        /// </summary>
        /// <remarks>Since an arbitrary BinaryPredicate is passed to this function, what is being removed need not be true equality. </remarks>
        /// <param name="collection">The collection to process.</param>
        /// <param name="predicate">The BinaryPredicate used to compare items for "equality". An item <c>current</c> is removed if <c>predicate(first, current)==true</c>, where
        /// <c>first</c> is the first item in the group of "duplicate" items.</param>
        /// <returns>An new collection with the items from <paramref name="collection"/>, in the same order, 
        /// with consecutive "duplicates" removed.</returns>
        public static IEnumerable<T> RemoveDuplicates<T>(IEnumerable<T> collection, BinaryPredicate<T> predicate)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            T current = default(T);
            bool atBeginning = true;

            foreach (T item in collection) {
                // Is the new item different from the current item?
                if (atBeginning || !predicate(current, item)) {
                    current = item;
                    yield return item;
                }

                atBeginning = false;
            }
        }

        /// <summary>
        /// Remove consecutive equal items from a list or array. In each run of consecutive equal items
        /// in the list, all items after the first item in the run are removed. The removal is done in-place, changing
        /// the list. 
        /// </summary>
        /// <remarks><para>The default sense of equality for T is used, as defined by T's
        /// implementation of IComparable&lt;T&gt;.Equals or object.Equals.</para>
        /// <para>Although arrays cast to IList&lt;T&gt; are normally read-only, this method
        /// will work correctly and modify an array passed as <paramref name="list"/>.</para></remarks>
        /// <param name="list">The list or array to process.</param>
        public static void RemoveDuplicatesInPlace<T>(IList<T> list)
        {
            RemoveDuplicatesInPlace<T>(list, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Remove subsequent consecutive equal items from a list or array. In each run of consecutive equal items
        /// in the list, all items after the first item in the run are removed.
        /// The replacement is done in-place, changing
        /// the list. A passed IEqualityComparer is used to determine equality.
        /// </summary>
        /// <remarks>Although arrays cast to IList&lt;T&gt; are normally read-only, this method
        /// will work corre