algorithms.cs

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

            /// view onto a typed ICollection<T> interface.
            /// </summary>
            /// <param name="wrappedCollection">The ICollection&lt;T&gt; to wrap.</param>
            public UntypedCollection(ICollection<T> wrappedCollection)
            {
                this.wrappedCollection = wrappedCollection;
            }


            public void CopyTo(Array array, int index)
            {
                if (array == null)
                    throw new ArgumentNullException("array");

                int i = 0;
                int count = wrappedCollection.Count;

                if (index < 0)
                    throw new ArgumentOutOfRangeException("index", index, Strings.ArgMustNotBeNegative);
                if (index >= array.Length || count > array.Length - index)
                    throw new ArgumentException("index", Strings.ArrayTooSmall);

                foreach (T item in wrappedCollection) {
                    if (i >= count)
                        break;

                    array.SetValue(item, index);
                    ++index;
                    ++i;
                }
            }

            public int Count
            {
                get { return wrappedCollection.Count; }
            }

            public bool IsSynchronized
            {
                get { return false; }
            }

            public object SyncRoot
            {
                get { return this; }
            }

            public IEnumerator GetEnumerator()
            {
                return ((IEnumerable)wrappedCollection).GetEnumerator();
            }
        }

        /// <summary>
        /// Given a generic ICollection&lt;T&gt; interface, wrap a non-generic (untyped)
        /// ICollection interface around it. The non-generic interface will contain the same objects as the 
        /// underlying generic collection, but can be used in places that require a non-generic interface.
        /// This method is useful when interfacing generic interfaces with older code that uses non-generic interfaces.
        /// </summary>
        /// <remarks>Many generic collections already implement the non-generic interfaces directly. This
        /// method will first attempt to simply cast <paramref name="typedCollection"/> to ICollection. If that
        /// succeeds, it is returned; if it fails, then a wrapper object is created.</remarks>
        /// <typeparam name="T">The item type of the underlying collection.</typeparam>
        /// <param name="typedCollection">A typed collection to wrap.</param>
        /// <returns>A non-generic ICollection wrapper around <paramref name="typedCollection"/>.
        /// If <paramref name="typedCollection"/> is null, then null is returned.</returns>
        public static ICollection Untyped<T>(ICollection<T> typedCollection)
        {
            if (typedCollection == null)
                return null;
            else if (typedCollection is ICollection)
                return (ICollection)typedCollection;
            else
                return new UntypedCollection<T>(typedCollection);
        }

        /// <summary>
        /// The class that implements a non-generic IList wrapper
        /// around a generic IList&lt;T&gt; interface.
        /// </summary>
        [Serializable]
        private class UntypedList<T> : IList
        {
            private IList<T> wrappedList;

            /// <summary>
            /// Create a non-generic IList wrapper
            /// around a generic IList&lt;T&gt; interface.
            /// </summary>
            /// <param name="wrappedList">The IList&lt;T&gt; interface to wrap.</param>
            public UntypedList(IList<T> wrappedList)
            {
                this.wrappedList = wrappedList;
            }

            /// <summary>
            /// Convert the given parameter to T. Throw an ArgumentException
            /// if it isn't.
            /// </summary>
            /// <param name="name">parameter name</param>
            /// <param name="value">parameter value</param>
            private T ConvertToItemType(string name, object value)
            {
                try {
                    return (T)value;
                }
                catch (InvalidCastException) {
                    throw new ArgumentException(string.Format(Strings.WrongType, value, typeof(T)), name);
                }
            }


            public int Add(object value)
            {  
                // We assume that Add always adds to the end. Is this true?
                wrappedList.Add(ConvertToItemType("value", value));
                return wrappedList.Count - 1;
            }

            public void Clear()
            {  wrappedList.Clear(); }

            public bool Contains(object value)
            {
                if (value is T)
                    return wrappedList.Contains((T)value);
                else
                    return false;
            }

            public int IndexOf(object value)
            {
                if (value is T)
                    return wrappedList.IndexOf((T)value);
                else
                    return -1;
            }

            public void Insert(int index, object value)
            { wrappedList.Insert(index, ConvertToItemType("value", value)); }

            public bool IsFixedSize
            {
                get { return false; }
            }

            public bool IsReadOnly
            {
                get { return wrappedList.IsReadOnly; }
            }

            public void Remove(object value)
            {  
                if (value is T)
                    wrappedList.Remove((T)value); 
            }   

            public void RemoveAt(int index)
            {  wrappedList.RemoveAt(index);}

            public object this[int index]
            {
                get { return wrappedList[index]; }
                set { wrappedList[index] = ConvertToItemType("value", value); }
            }

            public void CopyTo(Array array, int index)
            {
                if (array == null)
                    throw new ArgumentNullException("array");

                int i = 0;
                int count = wrappedList.Count;

                if (index < 0)
                    throw new ArgumentOutOfRangeException("index", index, Strings.ArgMustNotBeNegative);
                if (index >= array.Length || count > array.Length - index)
                    throw new ArgumentException("index", Strings.ArrayTooSmall);

                foreach (T item in wrappedList) {
                    if (i >= count)
                        break;

                    array.SetValue(item, index);
                    ++index;
                    ++i;
                }
            }

            public int Count
            {
                get { return wrappedList.Count; }
            }

            public bool IsSynchronized
            {
                get { return false; }
            }

            public object SyncRoot
            {
                get { return this; }
            }

            public IEnumerator GetEnumerator()
            {  return ((IEnumerable)wrappedList).GetEnumerator(); }
        }

        /// <summary>
        /// Given a generic IList&lt;T&gt; interface, wrap a non-generic (untyped)
        /// IList interface around it. The non-generic interface will contain the same objects as the 
        /// underlying generic list, but can be used in places that require a non-generic interface.
        /// This method is useful when interfacing generic interfaces with older code that uses non-generic interfaces.
        /// </summary>
        /// <remarks>Many generic collections already implement the non-generic interfaces directly. This
        /// method will first attempt to simply cast <paramref name="typedList"/> to IList. If that
        /// succeeds, it is returned; if it fails, then a wrapper object is created.</remarks>
        /// <typeparam name="T">The item type of the underlying list.</typeparam>
        /// <param name="typedList">A typed list to wrap.</param>
        /// <returns>A non-generic IList wrapper around <paramref name="typedList"/>.
        /// If <paramref name="typedList"/> is null, then null is returned.</returns>
        public static IList Untyped<T>(IList<T> typedList)
        {
            if (typedList == null)
                return null;
            else if (typedList is IList)
                return (IList)typedList;
            else
                return new UntypedList<T>(typedList);
        }

        /// <summary>
        /// The class that is used to implement IList&lt;T&gt; to view an array
        /// in a read-write way. Insertions cause the last item in the array
        /// to fall off, deletions replace the last item with the default value.
        /// </summary>
        [Serializable]
        private class ArrayWrapper<T> : ListBase<T>, IList
        {
            private T[] wrappedArray;

            /// <summary>
            /// Create a list wrapper object on an array.
            /// </summary>
            /// <param name="wrappedArray">Array to wrap.</param>
            public ArrayWrapper(T[] wrappedArray)
            {
                this.wrappedArray = wrappedArray;
            }

            public override int Count
            {
                get
                {
                    return wrappedArray.Length;
                }
            }

            public override void Clear()
            {
                int count = wrappedArray.Length;
                for (int i = 0; i < count; ++i)
                    wrappedArray[i] = default(T);
            }

            public override void Insert(int index, T item)
            {
                if (index < 0 || index > wrappedArray.Length)
                    throw new ArgumentOutOfRangeException("index");

                if (index + 1 < wrappedArray.Length)
                    Array.Copy(wrappedArray, index, wrappedArray, index + 1, wrappedArray.Length - index - 1);
                if (index < wrappedArray.Length)
                    wrappedArray[index] = item;
            }

            public override void RemoveAt(int index)
            {
                if (index < 0 || index >= wrappedArray.Length)
                    throw new ArgumentOutOfRangeException("index");

                if (index < wrappedArray.Length - 1)
                    Array.Copy(wrappedArray, index + 1, wrappedArray, index, wrappedArray.Length - index - 1);
                wrappedArray[wrappedArray.Length - 1] = default(T);
            }

            public override T this[int index]
            {
                get
                {
                    if (index < 0 || index >= wrappedArray.Length)
                        throw new ArgumentOutOfRangeException("index");

                    return wrappedArray[index];
                }
                set
                {
                    if (index < 0 || index >= wrappedArray.Length)
                        throw new ArgumentOutOfRangeException("index");