Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version
Go to top

Auto-filter for Microsoft WPF DataGrid

, 29 Jan 2009
Allows auto filtering functionality for DataGrid columns.
WPFGridFilter.zip
WPFGridFilter
PowerCollections
PowerCollections.csproj.user
Properties
Stepi.Collections
bin
Filters
Properties
Stepi.UIFilters
bin
Initializers
Properties
Settings.settings
Themes
Test.GridSorting
bin
Debug
Test.GridFilter.vshost.exe
Properties
Settings.settings
//******************************
// Written by Peter Golde
// Copyright (c) 2004-2005, Wintellect
//
// Use and restribution of this code is subject to the license agreement 
// contained in the file "License.txt" accompanying this file.
//******************************

using System;
using System.Collections;
using System.Collections.Generic;

#pragma warning disable 419  // Ambigious cref in XML comment

// Make internals of this library available to the unit test framework.
[assembly: System.Runtime.CompilerServices.InternalsVisibleTo("UnitTests")]

// Everything should be CLS compliant.
[assembly: CLSCompliant(true)]


namespace Wintellect.PowerCollections
{
    /// <summary>
    /// The BinaryPredicate delegate type  encapsulates a method that takes two
    /// items of the same type, and returns a boolean value representating 
    /// some relationship between them. For example, checking whether two
    /// items are equal or equivalent is one kind of binary predicate.
    /// </summary>
    /// <param name="item1">The first item.</param>
    /// <param name="item2">The second item.</param>
    /// <returns>Whether item1 and item2 satisfy the relationship that the BinaryPredicate defines.</returns>
    public delegate bool BinaryPredicate<T>(T item1, T item2);

    /// <summary>
    /// Algorithms contains a number of static methods that implement
    /// algorithms that work on collections. Most of the methods deal with
    /// the standard generic collection interfaces such as IEnumerable&lt;T&gt;,
    /// ICollection&lt;T&gt; and IList&lt;T&gt;.
    /// </summary>
    public static class Algorithms
    {
        #region Collection wrappers

        /// <summary>
        /// The class that is used to implement IList&lt;T&gt; to view a sub-range
        /// of a list. The object stores a wrapped list, and a start/count indicating
        /// a sub-range of the list. Insertion/deletions through the sub-range view
        /// cause the count to change also; insertions and deletions directly on
        /// the wrapped list do not.
        /// </summary>
        [Serializable]
        private class ListRange<T> : ListBase<T>, ICollection<T>
        {
            private IList<T> wrappedList;
            private int start;
            private int count;

            /// <summary>
            /// Create a sub-range view object on the indicate part 
            /// of the list.
            /// </summary>
            /// <param name="wrappedList">List to wrap.</param>
            /// <param name="start">The start index of the view in the wrapped list.</param>
            /// <param name="count">The number of items in the view.</param>
            public ListRange(IList<T> wrappedList, int start, int count)
            {
                this.wrappedList = wrappedList;
                this.start = start;
                this.count = count;
            }

            public override int Count
            {
                get { 
                    return Math.Min(count, wrappedList.Count - start); 
                }
            }

            public override void Clear()
            {
                if (wrappedList.Count - start < count)
                    count = wrappedList.Count - start;

                while (count > 0) {
                    wrappedList.RemoveAt(start + count - 1);
                    --count;
                }
            }

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

                wrappedList.Insert(start + index, item);
                ++count;
            }

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

                wrappedList.RemoveAt(start + index);
                --count;
            }

            public override bool Remove(T item)
            {
                if (wrappedList.IsReadOnly)
                    throw new NotSupportedException(string.Format(Strings.CannotModifyCollection, "Range"));
                else
                    return base.Remove(item);
            }

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

                    return wrappedList[start + index];
                }
                set
                {
                    if (index < 0 || index >= count)
                        throw new ArgumentOutOfRangeException("index");

                    wrappedList[start + index] = value;
                }
            }

            bool ICollection<T>.IsReadOnly
            {
                get
                {
                    return wrappedList.IsReadOnly;
                }
            }
        }

        /// <summary>
        /// Returns a view onto a sub-range of a list. Items from <paramref name="list"/> are not copied; the
        /// returned IList&lt;T&gt; is simply a different view onto the same underlying items. Changes to <paramref name="list"/>
        /// are reflected in the view, and vice versa. Insertions and deletions in the view change the size of the 
        /// view, but insertions and deletions in the underlying list do not.
        /// </summary>
        /// <remarks>This method can be used to apply an algorithm to a portion of a list. For example:
        /// <code>Algorithms.ReverseInPlace(Algorithms.Range(list, 3, 6))</code>
        /// will reverse the 6 items beginning at index 3.</remarks>
        /// <typeparam name="T">The type of the items in the list.</typeparam>
        /// <param name="list">The list to view.</param>
        /// <param name="start">The starting index of the view.</param>
        /// <param name="count">The number of items in the view.</param>
        /// <returns>A list that is a view onto the given sub-list. </returns>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="start"/> or <paramref name="count"/> is negative.</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="start"/> + <paramref name="count"/> is greater than the
        /// size of <paramref name="list"/>.</exception>
        public static IList<T> Range<T>(IList<T> list, int start, int count)
        {
            if (list == null)
                throw new ArgumentOutOfRangeException("list");
            if (start < 0 || start > list.Count || (start == list.Count && count != 0))
                throw new ArgumentOutOfRangeException("start");
            if (count < 0 || count > list.Count || count + start > list.Count)
                throw new ArgumentOutOfRangeException("count");

            return new ListRange<T>(list, start, count);
        }

        /// <summary>
        /// The class that is used to implement IList&lt;T&gt; to view a sub-range
        /// of an array. The object stores a wrapped array, and a start/count indicating
        /// a sub-range of the array. Insertion/deletions through the sub-range view
        /// cause the count to change up to the size of the underlying array. Elements
        /// fall off the end of the underlying array.
        /// </summary>
        [Serializable]
        private class ArrayRange<T> : ListBase<T>
        {
            private T[] wrappedArray;
            private int start;
            private int count;

            /// <summary>
            /// Create a sub-range view object on the indicate part 
            /// of the array.
            /// </summary>
            /// <param name="wrappedArray">Array to wrap.</param>
            /// <param name="start">The start index of the view in the wrapped list.</param>
            /// <param name="count">The number of items in the view.</param>
            public ArrayRange(T[] wrappedArray, int start, int count)
            {
                this.wrappedArray = wrappedArray;
                this.start = start;
                this.count = count;
            }

            public override int Count
            {
                get
                {
                    return count;
                }
            }

            public override void Clear()
            {
                Array.Copy(wrappedArray, start + count, wrappedArray, start, wrappedArray.Length - (start + count));
                Algorithms.FillRange(wrappedArray, wrappedArray.Length - count, count, default(T));
                count = 0;
            }

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

                int i = start + index;

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

                if (start + count < wrappedArray.Length)
                    ++count;
            }

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

                int i = start + index;

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

                --count;
            }

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

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

                    wrappedArray[start + index] = value;
                }
            }
        }

        /// <summary>
        /// Returns a view onto a sub-range of an array. Items from <paramref name="array"/> are not copied; the
        /// returned IList&lt;T&gt; is simply a different view onto the same underlying items. Changes to <paramref name="array"/>
        /// are reflected in the view, and vice versa. Insertions and deletions in the view change the size of the 
        /// view. After an insertion, the last item in <paramref name="array"/> "falls off the end". After a deletion, the
        /// last item in array becomes the default value (0 or null).
        /// </summary>
        /// <remarks>This method can be used to apply an algorithm to a portion of a array. For example:
        /// <code>Algorithms.ReverseInPlace(Algorithms.Range(array, 3, 6))</code>
        /// will reverse the 6 items beginning at index 3.</remarks>
        /// <param name="array">The array to view.</param>
        /// <param name="start">The starting index of the view.</param>
        /// <param name="count">The number of items in the view.</param>
        /// <returns>A list that is a view onto the given sub-array. </returns>
        /// <exception cref="ArgumentNullException"><paramref name="array"/> is null.</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="start"/> or <paramref name="count"/> is negative.</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="start"/> + <paramref name="count"/> is greater than the
        /// size of <paramref name="array"/>.</exception>
        public static IList<T> Range<T>(T[] array, int start, int count)
        {
            if (array == null)
                throw new ArgumentOutOfRangeException("array");
            if (start < 0 || start > array.Length || (start == array.Length && count != 0))
                throw new ArgumentOutOfRangeException("start");
            if (count < 0 || count > array.Length || count + start > array.Length)
                throw new ArgumentOutOfRangeException("count");

            return new ArrayRange<T>(array, start, count);
        }

        /// <summary>
        /// The read-only ICollection&lt;T&gt; implementation that is used by the ReadOnly method.
        /// Methods that modify the collection throw a NotSupportedException, methods that don't
        /// modify are fowarded through to the wrapped collection.
        /// </summary>
        [Serializable]
        private class ReadOnlyCollection<T> : ICollection<T>
        {
            private ICollection<T> wrappedCollection;  // The collection we are wrapping (never null).

            /// <summary>
            /// Create a ReadOnlyCollection wrapped around the given collection.
            /// </summary>
            /// <param name="wrappedCollection">Collection to wrap.</param>
            public ReadOnlyCollection(ICollection<T> wrappedCollection)
            {
                this.wrappedCollection = wrappedCollection;
            }

            /// <summary>
            /// Throws an NotSupportedException stating that this collection cannot be modified.
            /// </summary>
            private void MethodModifiesCollection()
            {
                throw new NotSupportedException(string.Format(Strings.CannotModifyCollection, "read-only collection"));
            }


            public IEnumerator<T> GetEnumerator()
            { return wrappedCollection.GetEnumerator(); }

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

            public bool Contains(T item)
            { return wrappedCollection.Contains(item); }

            public void CopyTo(T[] array, int arrayIndex)
            { wrappedCollection.CopyTo(array, arrayIndex); }

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

            public bool IsReadOnly
            {
                get { return true; }
            }

            public void Add(T item)
            { MethodModifiesCollection(); }

            public void Clear()
            { MethodModifiesCollection(); }

            public bool Remove(T item)
            { MethodModifiesCollection(); return false; }
        }

        /// <summary>
        /// Returns a read-only view onto a collection. The returned ICollection&lt;T&gt; interface
        /// only allows operations that do not change the collection: GetEnumerator, Contains, CopyTo,
        /// Count. The ReadOnly property returns false, indicating that the collection is read-only. All other
        /// methods on the interface throw a NotSupportedException.
        /// </summary>
        /// <remarks>The data in the underlying collection is not copied. If the underlying
        /// collection is changed, then the read-only view also changes accordingly.</remarks>
        /// <typeparam name="T">The type of items in the collection.</typeparam>
        /// <param name="collection">The collection to wrap.</param>
        /// <returns>A read-only view onto <paramref name="collection"/>. If <paramref name="collection"/> is null, then null is returned.</returns>
        public static ICollection<T> ReadOnly<T>(ICollection<T> collection)
        {
            if (collection == null)
                return null;
            else
                return new ReadOnlyCollection<T>(collection);
        }

        /// <summary>
        /// The read-only IList&lt;T&gt; implementation that is used by the ReadOnly method.
        /// Methods that modify the list throw a NotSupportedException, methods that don't
        /// modify are fowarded through to the wrapped list.
        /// </summary>
        [Serializable]
        private class ReadOnlyList<T> : IList<T>
        {
            private IList<T> wrappedList;  // The list we are wrapping (never null).

            /// <summary>
            /// Create a ReadOnlyList wrapped around the given list.
            /// </summary>
            /// <param name="wrappedList">List to wrap.</param>
            public ReadOnlyList(IList<T> wrappedList)
            {
                this.wrappedList = wrappedList;
            }

            /// <summary>
            /// Throws an NotSupportedException stating that this collection cannot be modified.
            /// </summary>
            private void MethodModifiesCollection()
            {
                throw new NotSupportedException(string.Format(Strings.CannotModifyCollection, "read-only list"));
            }


            public IEnumerator<T> GetEnumerator()
            { return wrappedList.GetEnumerator(); }

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

            public int IndexOf(T item)
            { return wrappedList.IndexOf(item); }

            public bool Contains(T item)
            {  return wrappedList.Contains(item); }

            public void CopyTo(T[] array, int arrayIndex)
            {  wrappedList.CopyTo(array, arrayIndex); }

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

            public bool IsReadOnly
            {
                get { return true; }
            }

            public T this[int index]
            {
                get { return wrappedList[index]; }
                set { MethodModifiesCollection(); }
            }

            public void Add(T item)
            { MethodModifiesCollection(); }

            public void Clear()
            { MethodModifiesCollection(); }

            public void Insert(int index, T item)
            { MethodModifiesCollection(); }

            public void RemoveAt(int index)
            { MethodModifiesCollection(); }

            public bool Remove(T item)
            { MethodModifiesCollection(); return false; }
        }

        /// <summary>
        /// Returns a read-only view onto a list. The returned IList&lt;T&gt; interface
        /// only allows operations that do not change the list: GetEnumerator, Contains, CopyTo,
        /// Count, IndexOf, and the get accessor of the indexer. 
        /// The IsReadOnly property returns true, indicating that the list is read-only. All other
        /// methods on the interface throw a NotSupportedException.
        /// </summary>
        /// <remarks>The data in the underlying list is not copied. If the underlying
        /// list is changed, then the read-only view also changes accordingly.</remarks>
        /// <typeparam name="T">The type of items in the list.</typeparam>
        /// <param name="list">The list to wrap.</param>
        /// <returns>A read-only view onto <paramref name="list"/>. Returns null if <paramref name="list"/> is null. 
        /// If <paramref name="list"/> is already read-only, returns <paramref name="list"/>.</returns>
        public static IList<T> ReadOnly<T>(IList<T> list)
        {
            if (list == null)
                return null;
            else if (list.IsReadOnly)
                return list;
            else
                return new ReadOnlyList<T>(list);
        }

        /// <summary>
        /// The private class that implements a read-only wrapped for 
        /// IDictionary &lt;TKey,TValue&gt;.
        /// </summary>
        [Serializable]
        private class ReadOnlyDictionary<TKey, TValue> : IDictionary<TKey, TValue>
        {
            // The dictionary that is wrapped
            private IDictionary<TKey, TValue> wrappedDictionary;

            /// <summary>
            /// Create a read-only dictionary wrapped around the given dictionary.
            /// </summary>
            /// <param name="wrappedDictionary">The IDictionary&lt;TKey,TValue&gt; to wrap.</param>
            public ReadOnlyDictionary(IDictionary<TKey, TValue> wrappedDictionary)
            {
                this.wrappedDictionary = wrappedDictionary;
            }

            /// <summary>
            /// Throws an NotSupportedException stating that this collection cannot be modified.
            /// </summary>
            private void MethodModifiesCollection()
            {
                throw new NotSupportedException(string.Format(Strings.CannotModifyCollection, "read-only dictionary"));
            }

            public void Add(TKey key, TValue value)
            { MethodModifiesCollection(); }

            public bool ContainsKey(TKey key)
            { return wrappedDictionary.ContainsKey(key); }

            public ICollection<TKey> Keys
            { 
                get { return ReadOnly(wrappedDictionary.Keys); } 
            }

            public ICollection<TValue> Values
            { 
                get { return ReadOnly(wrappedDictionary.Values); } 
            }

            public bool Remove(TKey key)
            { 
                MethodModifiesCollection();
                return false;  // never reached
            }

            public bool TryGetValue(TKey key, out TValue value)
            { return wrappedDictionary.TryGetValue(key, out value); }

            public TValue this[TKey key]
            {
                get { return wrappedDictionary[key];}
                set { MethodModifiesCollection(); }
            }

            public void Add(KeyValuePair<TKey, TValue> item)
            { MethodModifiesCollection(); }

            public void Clear()
            { MethodModifiesCollection(); }

            public bool Contains(KeyValuePair<TKey, TValue> item)
            { return wrappedDictionary.Contains(item); }

            public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
            { wrappedDictionary.CopyTo(array, arrayIndex); }

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

            public bool IsReadOnly
            {
                get { return true; }
            }

            public bool Remove(KeyValuePair<TKey, TValue> item)
            { 
                MethodModifiesCollection();
                return false;     // never reached
            }

            public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
            { return wrappedDictionary.GetEnumerator(); }

            IEnumerator IEnumerable.GetEnumerator()
            { return ((IEnumerable)wrappedDictionary).GetEnumerator(); }
        }

        /// <summary>
        /// Returns a read-only view onto a dictionary. The returned IDictionary&lt;TKey,TValue&gt; interface
        /// only allows operations that do not change the dictionary. 
        /// The IsReadOnly property returns true, indicating that the dictionary is read-only. All other
        /// methods on the interface throw a NotSupportedException.
        /// </summary>
        /// <remarks>The data in the underlying dictionary is not copied. If the underlying
        /// dictionary is changed, then the read-only view also changes accordingly.</remarks>
        /// <param name="dictionary">The dictionary to wrap.</param>
        /// <returns>A read-only view onto <paramref name="dictionary"/>. Returns null if <paramref name="dictionary"/> is null. 
        /// If <paramref name="dictionary"/> is already read-only, returns <paramref name="dictionary"/>.</returns>
        public static IDictionary<TKey,TValue> ReadOnly<TKey,TValue>(IDictionary<TKey,TValue> dictionary)
        {
            if (dictionary == null)
                return null;
            else if (dictionary.IsReadOnly)
                return dictionary;
            else
                return new ReadOnlyDictionary<TKey,TValue>(dictionary);
        }

        /// <summary>
        ///  The class that provides a typed IEnumerator&lt;T&gt;
        /// view onto an untyped IEnumerator interface.
        /// </summary>
        [Serializable]
        private class TypedEnumerator<T> : IEnumerator<T>
        {
            private IEnumerator wrappedEnumerator;

            /// <summary>
            /// Create a typed IEnumerator&lt;T&gt;
            /// view onto an untyped IEnumerator interface 
            /// </summary>
            /// <param name="wrappedEnumerator">IEnumerator to wrap.</param>
            public TypedEnumerator(IEnumerator wrappedEnumerator)
            {
                this.wrappedEnumerator = wrappedEnumerator;
            }

            T IEnumerator<T>.Current
            {
                get { return (T) wrappedEnumerator.Current; }
            }

            void IDisposable.Dispose()
            {
                if (wrappedEnumerator is IDisposable)
                    ((IDisposable)wrappedEnumerator).Dispose();
            }

            object IEnumerator.Current
            {
                get { return wrappedEnumerator.Current; }
            }

            bool IEnumerator.MoveNext()
            {
                return wrappedEnumerator.MoveNext();
            }

            void IEnumerator.Reset()
            {
                wrappedEnumerator.Reset();
            }
        }

        /// <summary>
        /// The class that provides a typed IEnumerable&lt;T&gt; view
        /// onto an untyped IEnumerable interface.
        /// </summary>
        [Serializable]
        private class TypedEnumerable<T> : IEnumerable<T>
        {
            private IEnumerable wrappedEnumerable;

            /// <summary>
            /// Create a typed IEnumerable&lt;T&gt; view
            /// onto an untyped IEnumerable interface.
            /// </summary>
            /// <param name="wrappedEnumerable">IEnumerable interface to wrap.</param>
            public TypedEnumerable(IEnumerable wrappedEnumerable)
            {
                this.wrappedEnumerable = wrappedEnumerable;
            }

            public IEnumerator<T> GetEnumerator()
            {
                return new TypedEnumerator<T>(wrappedEnumerable.GetEnumerator());
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return wrappedEnumerable.GetEnumerator();
            }

        }

        /// <summary>
        /// Given a non-generic IEnumerable interface, wrap a generic IEnumerable&lt;T&gt;
        /// interface around it. The generic interface will enumerate the same objects as the 
        /// underlying non-generic collection, but can be used in places that require a generic interface.
        /// The underlying non-generic collection must contain only items that
        /// are of type <paramref name="T"/> or a type derived from it. This method is useful
        /// when interfacing older, non-generic collections to newer code that uses generic interfaces.
        /// </summary>
        /// <remarks>Some collections implement both generic and non-generic interfaces. For efficiency,
        /// this method will first attempt to cast <paramref name="untypedCollection"/> to IEnumerable&lt;T&gt;. 
        /// If that succeeds, it is returned; otherwise, a wrapper object is created.</remarks>
        /// <typeparam name="T">The item type of the wrapper collection.</typeparam>
        /// <param name="untypedCollection">An untyped collection. This collection should only contain
        /// items of type <paramref name="T"/> or a type derived from it. </param>
        /// <returns>A generic IEnumerable&lt;T&gt; wrapper around <paramref name="untypedCollection"/>. 
        /// If <paramref name="untypedCollection"/> is null, then null is returned.</returns>
        public static IEnumerable<T> TypedAs<T>(IEnumerable untypedCollection)
        {
            if (untypedCollection == null)
                return null;
            else if (untypedCollection is IEnumerable<T>)
                return (IEnumerable<T>)untypedCollection;
            else
                return new TypedEnumerable<T>(untypedCollection);
        }

        /// <summary>
        /// The class that provides a typed ICollection&lt;T&gt; view
        /// onto an untyped ICollection interface. The ICollection&lt;T&gt;
        /// is read-only.
        /// </summary>
        [Serializable]
        private class TypedCollection<T> : ICollection<T>
        {
            private ICollection wrappedCollection;

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

            /// <summary>
            /// Throws an NotSupportedException stating that this collection cannot be modified.
            /// </summary>
            private void MethodModifiesCollection()
            {
                throw new NotSupportedException(string.Format(Strings.CannotModifyCollection, "strongly-typed Collection"));
            }

            public void Add(T item)
            {  MethodModifiesCollection(); }

            public void Clear()
            {  MethodModifiesCollection(); }

            public bool Remove(T item)
            { MethodModifiesCollection(); return false; }

            public bool Contains(T item)
            {
                IEqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
                foreach (object obj in wrappedCollection) {
                    if (obj is T && equalityComparer.Equals(item, (T)obj))
                        return true;
                }
                return false;
            }

            public void CopyTo(T[] array, int arrayIndex)
            {  wrappedCollection.CopyTo(array, arrayIndex); }

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

            public bool IsReadOnly
            {
                get { return true; }
            }

            public IEnumerator<T> GetEnumerator()
            {  return new TypedEnumerator<T>(wrappedCollection.GetEnumerator()); }

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

        /// <summary>
        /// Given a non-generic ICollection interface, wrap a generic ICollection&lt;T&gt;
        /// interface around it. The generic interface will enumerate the same objects as the 
        /// underlying non-generic collection, but can be used in places that require a generic interface.
        /// The underlying non-generic collection must contain only items that
        /// are of type <paramref name="T"/> or a type derived from it. This method is useful
        /// when interfacing older, non-generic collections to newer code that uses generic interfaces.
        /// </summary>
        /// <remarks><para>Some collections implement both generic and non-generic interfaces. For efficiency,
        /// this method will first attempt to cast <paramref name="untypedCollection"/> to ICollection&lt;T&gt;. 
        /// If that succeeds, it is returned; otherwise, a wrapper object is created.</para>
        /// <para>Unlike the generic interface, the non-generic ICollection interfaces does
        /// not contain methods for adding or removing items from the collection. For this reason,
        /// the returned ICollection&lt;T&gt; will be read-only.</para></remarks>
        /// <typeparam name="T">The item type of the wrapper collection.</typeparam>
        /// <param name="untypedCollection">An untyped collection. This collection should only contain
        /// items of type <paramref name="T"/> or a type derived from it. </param>
        /// <returns>A generic ICollection&lt;T&gt; wrapper around <paramref name="untypedCollection"/>.
        /// If <paramref name="untypedCollection"/> is null, then null is returned.</returns>
        public static ICollection<T> TypedAs<T>(ICollection untypedCollection)
        {
            if (untypedCollection == null)
                return null;
            else if (untypedCollection is ICollection<T>)
                return (ICollection<T>) untypedCollection;
            else
                return new TypedCollection<T>(untypedCollection);
        }

        /// <summary>
        /// The class used to create a typed IList&lt;T&gt; view onto
        /// an untype IList interface.
        /// </summary>
        [Serializable]
        private class TypedList<T> : IList<T>
        {
            private IList wrappedList;

            /// <summary>
            /// Create a typed IList&lt;T&gt; view onto
            /// an untype IList interface.
            /// </summary>
            /// <param name="wrappedList">The IList to wrap.</param>
            public TypedList(IList wrappedList)
            {
                this.wrappedList = wrappedList;
            }


            public IEnumerator<T> GetEnumerator()
            { return new TypedEnumerator<T>(wrappedList.GetEnumerator()); }

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

            public int IndexOf(T item)
            {  return wrappedList.IndexOf(item); }

            public void Insert(int index, T item)
            {  wrappedList.Insert(index, item); }

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

            public void Add(T item)
            {  wrappedList.Add(item); }

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

            public bool Contains(T item)
            {  return wrappedList.Contains(item); }

            public void CopyTo(T[] array, int arrayIndex)
            {  wrappedList.CopyTo(array, arrayIndex); }

            public T this[int index]
            {
                get { return (T)wrappedList[index]; }
                set { wrappedList[index] = value; }
            }

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

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

            public bool Remove(T item)
            {
                if (wrappedList.Contains(item)) {
                    wrappedList.Remove(item);
                    return true;
                }
                else {
                    return false;
                }
            }
        }

        /// <summary>
        /// Given a non-generic IList interface, wrap a generic IList&lt;T&gt;
        /// interface around it. The generic interface will enumerate the same objects as the 
        /// underlying non-generic list, but can be used in places that require a generic interface.
        /// The underlying non-generic list must contain only items that
        /// are of type <paramref name="T"/> or a type derived from it. This method is useful
        /// when interfacing older, non-generic lists to newer code that uses generic interfaces.
        /// </summary>
        /// <remarks>Some collections implement both generic and non-generic interfaces. For efficiency,
        /// this method will first attempt to cast <paramref name="untypedList"/> to IList&lt;T&gt;. 
        /// If that succeeds, it is returned; otherwise, a wrapper object is created.</remarks>
        /// <typeparam name="T">The item type of the wrapper list.</typeparam>
        /// <param name="untypedList">An untyped list. This list should only contain
        /// items of type <paramref name="T"/> or a type derived from it. </param>
        /// <returns>A generic IList&lt;T&gt; wrapper around <paramref name="untypedlist"/>.
        /// If <paramref name="untypedlist"/> is null, then null is returned.</returns>
        public static IList<T> TypedAs<T>(IList untypedList)
        {
            if (untypedList == null)
                return null;
            else if (untypedList is IList<T>)
                return (IList<T>)untypedList;
            else
                return new TypedList<T>(untypedList);
        }

        /// <summary>
        /// The class that is used to provide an untyped ICollection
        /// view onto a typed ICollection&lt;T&gt; interface.
        /// </summary>
        [Serializable]
        private class UntypedCollection<T> : ICollection
        {
            private ICollection<T> wrappedCollection;

            /// <summary>
            /// Create an untyped ICollection
            /// view onto a typed ICollection&lt;T&gt; 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");

                    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 correctly and modify an array passed as <paramref name="list"/>.</remarks>
        /// <param name="list">The list or array 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>
        public static void RemoveDuplicatesInPlace<T>(IList<T> list, IEqualityComparer<T> equalityComparer)
        {
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            RemoveDuplicatesInPlace<T>(list, equalityComparer.Equals);

        }

        /// <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 replacement is done in-place, changing
        /// the list. The passed BinaryPredicate is used to determine if two items are "equal".
        /// </summary>
        /// <remarks><para>Since an arbitrary BinaryPredicate is passed to this function, what is being tested for need not be true equality. </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="predicate">The BinaryPredicate used to compare items for "equality". </param>
        public static void RemoveDuplicatesInPlace<T>(IList<T> list, BinaryPredicate<T> predicate)
        {
            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");

            T current = default(T);
            T item;
            int i = -1, j = 0;
            int listCount = list.Count;

            // Remove duplicates, compressing items to lower in the list.
            while (j < listCount) {
                item = list[j];
                if (i < 0 || !predicate(current, item)) {
                    current = item;
                    ++i;
                    if (i != j)
                        list[i] = current;
                }
                ++j;
            }

            ++i;
            if (i < listCount) {
                // remove items from the end.
                if (list is ArrayWrapper<T> || (list is IList && ((IList)list).IsFixedSize)) {
                    // An array or similar. Null out the last elements.
                    while (i < listCount)
                        list[i++] = default(T);
                }
                else {
                    // Normal list.
                    while (i < listCount) {
                        list.RemoveAt(listCount - 1);
                        --listCount;
                    }
                }
            }
        }

        /// <summary>
        /// Finds the first occurence of <paramref name="count"/> consecutive equal items in the
        /// list.
        /// </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="list">The list to examine.</param>
        /// <param name="count">The number of consecutive equal items to look for. The count must be at least 1.</param>
        /// <returns>The index of the first item in the first run of <paramref name="count"/> consecutive equal items, or -1 if no such run exists..</returns>
        public static int FirstConsecutiveEqual<T>(IList<T> list, int count)
        {
            return FirstConsecutiveEqual<T>(list, count, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Finds the first occurence of <paramref name="count"/> consecutive equal items in the
        /// list. A passed IEqualityComparer is used to determine equality.
        /// </summary>
        /// <param name="list">The list to examine.</param>
        /// <param name="count">The number of consecutive equal items to look for. The count must be at least 1.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. Only the Equals method will be called.</param>
        /// <returns>The index of the first item in the first run of <paramref name="count"/> consecutive equal items, or -1 if no such run exists.</returns>
        public static int FirstConsecutiveEqual<T>(IList<T> list, int count, IEqualityComparer<T> equalityComparer)
        {
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            return FirstConsecutiveEqual<T>(list, count, equalityComparer.Equals);
        }

        /// <summary>
        /// Finds the first occurence of <paramref name="count"/> consecutive "equal" items in the
        /// list. 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 tested for need not be true equality. </remarks>
        /// <param name="list">The list to examine.</param>
        /// <param name="count">The number of consecutive equal items to look for. The count must be at least 1.</param>
        /// <param name="predicate">The BinaryPredicate used to compare items for "equality". </param>
        /// <returns>The index of the first item in the first run of <paramref name="count"/> consecutive equal items, or -1 if no such run exists.</returns>
        public static int FirstConsecutiveEqual<T>(IList<T> list, int count, BinaryPredicate<T> predicate)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (predicate == null)
                throw new ArgumentNullException("predicate");
            if (count < 1)
                throw new ArgumentOutOfRangeException("count");

            int listCount = list.Count;
            if (listCount < count)
                return -1;         // Can't find run longer than the list itself.
            if (count == 1)
                return 0;          // Run of 1 must be the first item in the list.

            int start = 0, index = 0;
            T current = default(T);
            int runLength = 0;

            // Go through the list, looking for a run of the given length.
            foreach (T item in list) {
                if (index > 0 && predicate(current, item)) {
                    ++runLength;
                    if (runLength >= count)
                        return start;
                }
                else {
                    current = item;
                    start = index;
                    runLength = 1;
                }

                ++index;
            }

            return -1;
        }

        /// <summary>
        /// Finds the first occurence of <paramref name="count"/> consecutive items in the
        /// list for which a given predicate returns true.
        /// </summary>
        /// <param name="list">The list to examine.</param>
        /// <param name="count">The number of consecutive items to look for. The count must be at least 1.</param>
        /// <param name="predicate">The predicate used to test each item.</param>
        /// <returns>The index of the first item in the first run of <paramref name="count"/> items where <paramref name="predicate"/>
        /// returns true for all items in the run, or -1 if no such run exists.</returns>
        public static int FirstConsecutiveWhere<T>(IList<T> list, int count, Predicate<T> predicate)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (predicate == null)
                throw new ArgumentNullException("predicate");
            if (count < 1)
                throw new ArgumentOutOfRangeException("count");

            int listCount = list.Count;
            if (count > listCount)
                return -1;     // Can't find run longer than the list itself.

            int index = 0, start = -1;
            int runLength = 0;

            // Scan the list in order, looking for the number of consecutive true items.
            foreach (T item in list) {
                if (predicate(item)) {
                    if (start < 0)
                        start = index;
                    ++runLength;
                    if (runLength >= count)
                        return start;
                }
                else {
                    runLength = 0;
                    start = -1;
                }

                ++index;
            }

            return -1;
        }

        #endregion Consecutive items

        #region Find and SearchForSubsequence


        /// <summary>
        /// Finds the first item in a collection that satisfies the condition
        /// defined by <paramref name="predicate"/>.
        /// </summary>
        /// <remarks>If the default value for T could be present in the collection, and 
        /// would be matched by the predicate, then this method is inappropriate, because
        /// you cannot disguish whether the default value for T was actually present in the collection,
        /// or no items matched the predicate. In this case, use TryFindFirstWhere.</remarks>
        /// <param name="collection">The collection to search.</param>
        /// <param name="predicate">A delegate that defined the condition to check for.</param>
        /// <returns>The first item in the collection that matches the condition, or the default value for T (0 or null) if no
        /// item that matches the condition is found.</returns>
        /// <seealso cref="TryFindFirstWhere"/>
        public static T FindFirstWhere<T>(IEnumerable<T> collection, Predicate<T> predicate)
        {
            T retval;
            if (Algorithms.TryFindFirstWhere<T>(collection, predicate, out retval))
                return retval;
            else
                return default(T);
        }

        /// <summary>
        /// Finds the first item in a collection that satisfies the condition
        /// defined by <paramref name="predicate"/>.
        /// </summary>
        /// <param name="collection">The collection to search.</param>
        /// <param name="predicate">A delegate that defined the condition to check for.</param>
        /// <param name="foundItem">Outputs the first item in the collection that matches the condition, if the method returns true.</param>
        /// <returns>True if an item satisfying the condition was found. False if no such item exists in the collection.</returns>
        /// <seealso cref="FindFirstWhere"/>
        public static bool TryFindFirstWhere<T>(IEnumerable<T> collection, Predicate<T> predicate, out T foundItem)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            foreach (T item in collection) {
                if (predicate(item)) {
                    foundItem = item;
                    return true;
                }
            }

            // didn't find any item that matches.
            foundItem = default(T);
            return false;
        }

        /// <summary>
        /// Finds the last item in a collection that satisfies the condition
        /// defined by <paramref name="predicate"/>.
        /// </summary>
        /// <remarks><para>If the collection implements IList&lt;T&gt;, then the list is scanned in reverse until a 
        /// matching item is found. Otherwise, the entire collection is iterated in the forward direction.</para>
        /// <para>If the default value for T could be present in the collection, and 
        /// would be matched by the predicate, then this method is inappropriate, because
        /// you cannot disguish whether the default value for T was actually present in the collection,
        /// or no items matched the predicate. In this case, use TryFindFirstWhere.</para></remarks>
        /// <param name="collection">The collection to search.</param>
        /// <param name="predicate">A delegate that defined the condition to check for.</param>
        /// <returns>The last item in the collection that matches the condition, or the default value for T (0 or null) if no
        /// item that matches the condition is found.</returns>
        /// <seealso cref="TryFindLastWhere"/>
        public static T FindLastWhere<T>(IEnumerable<T> collection, Predicate<T> predicate)
        {
            T retval;
            if (Algorithms.TryFindLastWhere<T>(collection, predicate, out retval))
                return retval;
            else
                return default(T);
        }

        /// <summary>
        /// Finds the last item in a collection that satisfies the condition
        /// defined by <paramref name="predicate"/>.
        /// </summary>
        /// <remarks>If the collection implements IList&lt;T&gt;, then the list is scanned in reverse until a 
        /// matching item is found. Otherwise, the entire collection is iterated in the forward direction.</remarks>
        /// <param name="collection">The collection to search.</param>
        /// <param name="predicate">A delegate that defined the condition to check for.</param>
        /// <param name="foundItem">Outputs the last item in the collection that matches the condition, if the method returns true.</param>
        /// <returns>True if an item satisfying the condition was found. False if no such item exists in the collection.</returns>
        /// <seealso cref="FindLastWhere"/>
        public static bool TryFindLastWhere<T>(IEnumerable<T> collection, Predicate<T> predicate, out T foundItem)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            IList<T> list = collection as IList<T>;
            if (list != null) {
                // If it's a list, we can iterate in reverse.
                for (int index = list.Count - 1; index >= 0; --index) {
                    T item = list[index];
                    if (predicate(item)) {
                        foundItem = item;
                        return true;
                    }
                }

                // didn't find any item that matches.
                foundItem = default(T);
                return false;
            }
            else {
                // Otherwise, iterate the whole thing and remember the last matching one.
                bool found = false;
                foundItem = default(T);

                foreach (T item in collection) {
                    if (predicate(item)) {
                        foundItem = item;
                        found = true;
                    }
                }

                return found;
            }
        }

        /// <summary>
        /// Enumerates all the items in <paramref name="collection"/> that satisfy the condition defined
        /// by <paramref name="predicate"/>.
        /// </summary>
        /// <param name="collection">The collection to check all the items in.</param>
        /// <param name="predicate">A delegate that defines the condition to check for.</param>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates the items that satisfy the condition.</returns>
        public static IEnumerable<T> FindWhere<T>(IEnumerable<T> collection, Predicate<T> predicate)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

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

        /// <summary>
        /// Finds the index of the first item in a list that satisfies the condition
        /// defined by <paramref name="predicate"/>.
        /// </summary>
        /// <param name="list">The list to search.</param>
        /// <param name="predicate">A delegate that defined the condition to check for.</param>
        /// <returns>The index of the first item satisfying the condition. -1 if no such item exists in the list.</returns>
        public static int FindFirstIndexWhere<T>(IList<T> list, Predicate<T> predicate)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            int index = 0;
            foreach (T item in list) {
                if (predicate(item)) {
                    return index;
                }
                ++index;
            }

            // didn't find any item that matches.
            return -1;
        }

        /// <summary>
        /// Finds the index of the last item in a list that satisfies the condition
        /// defined by <paramref name="predicate"/>.
        /// </summary>
        /// <param name="list">The list to search.</param>
        /// <param name="predicate">A delegate that defined the condition to check for.</param>
        /// <returns>The index of the last item satisfying the condition. -1 if no such item exists in the list.</returns>
        public static int FindLastIndexWhere<T>(IList<T> list, Predicate<T> predicate)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            for (int index = list.Count - 1; index >= 0; --index) {
                if (predicate(list[index])) {
                    return index;
                }
            }

            // didn't find any item that matches.
            return -1;
        }

        /// <summary>
        /// Enumerates the indices of all the items in <paramref name="list"/> that satisfy the condition defined
        /// by <paramref name="predicate"/>.
        /// </summary>
        /// <param name="list">The list to check all the items in.</param>
        /// <param name="predicate">A delegate that defines the condition to check for.</param>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates the indices of items that satisfy the condition.</returns>
        public static IEnumerable<int> FindIndicesWhere<T>(IList<T> list, Predicate<T> predicate)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            int index = 0;
            foreach (T item in list) {
                if (predicate(item)) {
                    yield return index;
                }
                ++index;
            }
        }

        /// <summary>
        /// Finds the index of the first item in a list equal to a given item.
        /// </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="list">The list to search.</param>
        /// <param name="item">The item to search for.</param>
        /// <returns>The index of the first item equal to <paramref name="item"/>. -1 if no such item exists in the list.</returns>
        public static int FirstIndexOf<T>(IList<T> list, T item)
        {
            return FirstIndexOf<T>(list, item, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Finds the index of the first item in a list equal to a given item. A passed
        /// IEqualityComparer is used to determine equality.
        /// </summary>
        /// <param name="list">The list to search.</param>
        /// <param name="item">The item to search for.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. Only the Equals method will be called.</param>
        /// <returns>The index of the first item equal to <paramref name="item"/>. -1 if no such item exists in the list.</returns>
        public static int FirstIndexOf<T>(IList<T> list, T item, IEqualityComparer<T> equalityComparer)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            int index = 0;
            foreach (T x in list) {
                if (equalityComparer.Equals(x, item)) {
                    return index;
                }
                ++index;
            }

            // didn't find any item that matches.
            return -1;
        }

        /// <summary>
        /// Finds the index of the last item in a list equal to a given item.
        /// </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="list">The list to search.</param>
        /// <param name="item">The item to search for.</param>
        /// <returns>The index of the last item equal to <paramref name="item"/>. -1 if no such item exists in the list.</returns>
        public static int LastIndexOf<T>(IList<T> list, T item)
        {
            return LastIndexOf<T>(list, item, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Finds the index of the last item in a list equal to a given item. A passed
        /// IEqualityComparer is used to determine equality.
        /// </summary>
        /// <param name="list">The list to search.</param>
        /// <param name="item">The item to search for.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. Only the Equals method will be called.</param>
        /// <returns>The index of the last item equal to <paramref name="item"/>. -1 if no such item exists in the list.</returns>
        public static int LastIndexOf<T>(IList<T> list, T item, IEqualityComparer<T> equalityComparer)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            for (int index = list.Count - 1; index >= 0; --index) {
                if (equalityComparer.Equals(list[index], item)) {
                    return index;
                }
            }

            // didn't find any item that matches.
            return -1;
        }

        /// <summary>
        /// Enumerates the indices of all the items in a list equal to a given item.
        /// </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="list">The list to search.</param>
        /// <param name="item">The item to search for.</param>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates the indices of items equal to <paramref name="item"/>. </returns>
        public static IEnumerable<int> IndicesOf<T>(IList<T> list, T item)
        {
            return IndicesOf<T>(list, item, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Enumerates the indices of all the items in a list equal to a given item. A passed
        /// IEqualityComparer is used to determine equality.
        /// </summary>
        /// <param name="list">The list to search.</param>
        /// <param name="item">The item to search for.</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 IEnumerable&lt;T&gt; that enumerates the indices of items equal to <paramref name="item"/>. </returns>
        public static IEnumerable<int> IndicesOf<T>(IList<T> list, T item, IEqualityComparer<T> equalityComparer)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            int index = 0;
            foreach (T x in list) {
                if (equalityComparer.Equals(x, item)) {
                    yield return index;
                }
                ++index;
            }
        }

        /// <summary>
        /// Finds the index of the first item in a list equal to one of several given items.
        /// </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="list">The list to search.</param>
        /// <param name="itemsToLookFor">The items to search for.</param>
        /// <returns>The index of the first item equal to any of the items in the collection <paramref name="itemsToLookFor"/>. 
        /// -1 if no such item exists in the list.</returns>
        public static int FirstIndexOfMany<T>(IList<T> list, IEnumerable<T> itemsToLookFor)
        {
            return FirstIndexOfMany<T>(list, itemsToLookFor, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Finds the index of the first item in a list equal to one of several given items. A passed
        /// IEqualityComparer is used to determine equality.
        /// </summary>
        /// <param name="list">The list to search.</param>
        /// <param name="itemsToLookFor">The items to search for.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. 
        /// Only the Equals and GetHashCode methods will be called.</param>
        /// <returns>The index of the first item equal to any of the items in the collection <paramref name="itemsToLookFor"/>. 
        /// -1 if no such item exists in the list.</returns>
        public static int FirstIndexOfMany<T>(IList<T> list, IEnumerable<T> itemsToLookFor, IEqualityComparer<T> equalityComparer)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (itemsToLookFor == null)
                throw new ArgumentNullException("itemsToLookFor");
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            // Create a set of the items we are looking for, for efficient lookup.
            Set<T> setToLookFor = new Set<T>(itemsToLookFor, equalityComparer);

            // Scan the list for the items.
            int index = 0;
            foreach (T x in list) {
                if (setToLookFor.Contains(x)) {
                    return index;
                }
                ++index;
            }

            // didn't find any item that matches.
            return -1;
        }

        /// <summary>
        /// Finds the index of the first item in a list "equal" to one of several given items. 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. This methods finds 
        /// first item X which satisfies BinaryPredicate(X,Y), where Y is one of the items in <paramref name="itemsToLookFor"/></remarks>
        /// <param name="list">The list to search.</param>
        /// <param name="itemsToLookFor">The items to search for.</param>
        /// <param name="predicate">The BinaryPredicate used to compare items for "equality". </param>
        /// <returns>The index of the first item "equal" to any of the items in the collection <paramref name="itemsToLookFor"/>, using 
        /// <paramref name="BinaryPredicate"/> as the test for equality. 
        /// -1 if no such item exists in the list.</returns>
        public static int FirstIndexOfMany<T>(IList<T> list, IEnumerable<T> itemsToLookFor, BinaryPredicate<T> predicate)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (itemsToLookFor == null)
                throw new ArgumentNullException("itemsToLookFor");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            // Scan the list for the items.
            int index = 0;
            foreach (T x in list) {
                foreach (T y in itemsToLookFor) {
                    if (predicate(x, y)) {
                        return index;
                    }
                }

                ++index;
            }

            // didn't find any item that matches.
            return -1;
        }

        /// <summary>
        /// Finds the index of the last item in a list equal to one of several given items.
        /// </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="list">The list to search.</param>
        /// <param name="itemsToLookFor">The items to search for.</param>
        /// <returns>The index of the last item equal to any of the items in the collection <paramref name="itemsToLookFor"/>. 
        /// -1 if no such item exists in the list.</returns>
        public static int LastIndexOfMany<T>(IList<T> list, IEnumerable<T> itemsToLookFor)
        {
            return LastIndexOfMany(list, itemsToLookFor, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Finds the index of the last item in a list equal to one of several given items. A passed
        /// IEqualityComparer is used to determine equality.
        /// </summary>
        /// <param name="list">The list to search.</param>
        /// <param name="itemsToLookFor">The items to search for.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality.</param>
        /// <returns>The index of the last item equal to any of the items in the collection <paramref name="itemsToLookFor"/>. 
        /// -1 if no such item exists in the list.</returns>
        public static int LastIndexOfMany<T>(IList<T> list, IEnumerable<T> itemsToLookFor, IEqualityComparer<T> equalityComparer)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (itemsToLookFor == null)
                throw new ArgumentNullException("itemsToLookFor");
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            // Create a set of the items we are looking for, for efficient lookup.
            Set<T> setToLookFor = new Set<T>(itemsToLookFor, equalityComparer);

            // Scan the list
            for (int index = list.Count - 1; index >= 0; --index) {
                if (setToLookFor.Contains(list[index])) {
                    return index;
                }
            }

            // didn't find any item that matches.
            return -1;
        }

        /// <summary>
        /// Finds the index of the last item in a list "equal" to one of several given items. 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. This methods finds 
        /// last item X which satisfies BinaryPredicate(X,Y), where Y is one of the items in <paramref name="itemsToLookFor"/></remarks>
        /// <param name="list">The list to search.</param>
        /// <param name="itemsToLookFor">The items to search for.</param>
        /// <param name="predicate">The BinaryPredicate used to compare items for "equality". </param>
        /// <returns>The index of the last item "equal" to any of the items in the collection <paramref name="itemsToLookFor"/>, using 
        /// <paramref name="BinaryPredicate"/> as the test for equality. 
        /// -1 if no such item exists in the list.</returns>
        public static int LastIndexOfMany<T>(IList<T> list, IEnumerable<T> itemsToLookFor, BinaryPredicate<T> predicate)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (itemsToLookFor == null)
                throw new ArgumentNullException("itemsToLookFor");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            // Scan the list
            for (int index = list.Count - 1; index >= 0; --index) {
                foreach (T y in itemsToLookFor) {
                    if (predicate(list[index], y)) {
                        return index;
                    }
                }
            }

            // didn't find any item that matches.
            return -1;
        }

        /// <summary>
        /// Enumerates the indices of all the items in a list equal to one of several given items. 
        /// </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="list">The list to search.</param>
        /// <param name="itemsToLookFor">A collection of items to search for.</param>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates the indices of items equal to
        /// any of the items in the collection <paramref name="itemsToLookFor"/>. </returns>
        public static IEnumerable<int> IndicesOfMany<T>(IList<T> list, IEnumerable<T> itemsToLookFor)
        {
            return IndicesOfMany<T>(list, itemsToLookFor, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Enumerates the indices of all the items in a list equal to one of several given items. A passed
        /// IEqualityComparer is used to determine equality.
        /// </summary>
        /// <param name="list">The list to search.</param>
        /// <param name="itemsToLookFor">A collection of items to search for.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. </param>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates the indices of items equal to
        /// any of the items in the collection <paramref name="itemsToLookFor"/>. </returns>
        public static IEnumerable<int> IndicesOfMany<T>(IList<T> list, IEnumerable<T> itemsToLookFor, IEqualityComparer<T> equalityComparer)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (itemsToLookFor == null)
                throw new ArgumentNullException("itemsToLookFor");
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            // Create a set of the items we are looking for, for efficient lookup.
            Set<T> setToLookFor = new Set<T>(itemsToLookFor, equalityComparer);

            // Scan the list
            int index = 0;
            foreach (T x in list) {
                if (setToLookFor.Contains(x)) {
                    yield return index;
                }
                ++index;
            }
        }

        /// <summary>
        /// Enumerates the indices of all the items in a list equal to one of several given items. 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. This methods finds 
        /// last item X which satisfies BinaryPredicate(X,Y), where Y is one of the items in <paramref name="itemsToLookFor"/></remarks>
        /// <param name="list">The list to search.</param>
        /// <param name="itemsToLookFor">A collection of items to search for.</param>
        /// <param name="predicate">The BinaryPredicate used to compare items for "equality". </param>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates the indices of items "equal" to any of the items 
        /// in the collection <paramref name="itemsToLookFor"/>, using 
        /// <paramref name="BinaryPredicate"/> as the test for equality. </returns>
        public static IEnumerable<int> IndicesOfMany<T>(IList<T> list, IEnumerable<T> itemsToLookFor, BinaryPredicate<T> predicate)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (itemsToLookFor == null)
                throw new ArgumentNullException("itemsToLookFor");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            // Scan the list for the items.
            int index = 0;
            foreach (T x in list) {
                foreach (T y in itemsToLookFor) {
                    if (predicate(x, y)) {
                        yield return index;
                    }
                }

                ++index;
            }
        }

        /// <summary>
        /// Searchs a list for a sub-sequence of items that match a particular pattern. A subsequence 
        /// of <paramref name="list"/> matches pattern at index i if list[i] is equal to the first item
        /// in <paramref name="pattern"/>, list[i+1] is equal to the second item in <paramref name="pattern"/>,
        /// and so forth for all the items in <paramref name="pattern"/>.
        /// </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>
        /// <typeparam name="T">The type of items in the list.</typeparam>
        /// <param name="list">The list to search.</param>
        /// <param name="pattern">The sequence of items to search for.</param>
        /// <returns>The first index with <paramref name="list"/> that matches the items in <paramref name="pattern"/>.</returns>
        public static int SearchForSubsequence<T>(IList<T> list, IEnumerable<T> pattern)
        {
            return SearchForSubsequence<T>(list, pattern, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Searchs a list for a sub-sequence of items that match a particular pattern. A subsequence 
        /// of <paramref name="list"/> matches pattern at index i if list[i] is "equal" to the first item
        /// in <paramref name="pattern"/>, list[i+1] is "equal" to the second item in <paramref name="pattern"/>,
        /// and so forth for all the items in <paramref name="pattern"/>. 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 tested
        /// for in the pattern need not be equality. </remarks>
        /// <typeparam name="T">The type of items in the list.</typeparam>
        /// <param name="list">The list to search.</param>
        /// <param name="pattern">The sequence of items to search for.</param>
        /// <param name="predicate">The BinaryPredicate used to compare items for "equality". </param>
        /// <returns>The first index with <paramref name="list"/> that matches the items in <paramref name="pattern"/>.</returns>
        public static int SearchForSubsequence<T>(IList<T> list, IEnumerable<T> pattern, BinaryPredicate<T> predicate)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (pattern == null)
                throw new ArgumentNullException("pattern");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            // Put the pattern into an array for performance (don't keep allocating enumerators).
            T[] patternArray = Algorithms.ToArray<T>(pattern);

            int listCount = list.Count, patternCount = patternArray.Length;
            if (patternCount == 0)
                return 0;              // A zero-length pattern occurs anywhere.
            if (listCount == 0)
                return -1;             // no room for a pattern;

            for (int start = 0; start <= listCount - patternCount; ++start) {
                for (int count = 0; count < patternCount; ++count) {
                    if (!predicate(list[start + count], patternArray[count]))
                        goto NOMATCH;
                }
                // Got through the whole pattern. We have a match.
                return start;

            NOMATCH:
                /* no match found at start. */
                ;
            }

            // no match found anywhere.
            return -1;
        }
        
        /// <summary>
        /// Searchs a list for a sub-sequence of items that match a particular pattern. A subsequence 
        /// of <paramref name="list"/> matches pattern at index i if list[i] is equal to the first item
        /// in <paramref name="pattern"/>, list[i+1] is equal to the second item in <paramref name="pattern"/>,
        /// and so forth for all the items in <paramref name="pattern"/>. The passed 
        /// instance of IEqualityComparer&lt;T&gt; is used for determining if two items are equal.
        /// </summary>
        /// <typeparam name="T">The type of items in the list.</typeparam>
        /// <param name="list">The list to search.</param>
        /// <param name="pattern">The sequence of items to search for.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. Only the Equals method will be called.</param>
        /// <returns>The first index with <paramref name="list"/> that matches the items in <paramref name="pattern"/>.</returns>
        public static int SearchForSubsequence<T>(IList<T> list, IEnumerable<T> pattern, IEqualityComparer<T> equalityComparer)
        {
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            return SearchForSubsequence<T>(list, pattern, equalityComparer.Equals);
        }

        #endregion Find and SearchForSubsequence

        #region Set operations (coded except EqualSets)

        /// <summary>
        /// Determines if one collection is a subset of another, considered as sets. The first set is a subset
        /// of the second set if every item in the first set also occurs in the second set. If an item appears X times in the first set,
        /// it must appear at least X times in the second set.
        /// </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>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the IsSubsetOf method on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection.</param>
        /// <param name="collection2">The second collection.</param>
        /// <returns>True if <paramref name="collection1"/> is a subset of <paramref name="collection2"/>, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static bool IsSubsetOf<T>(IEnumerable<T> collection1, IEnumerable<T> collection2)
        {
            return IsSubsetOf(collection1, collection2, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Determines if one collection is a subset of another, considered as sets. The first set is a subset
        /// of the second set if every item in the first set also occurs in the second set. If an item appears X times in the first set,
        /// it must appear at least X times in the second set.
        /// </summary>
        /// <remarks>
        /// <para>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the IsSubsetOf method on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection.</param>
        /// <param name="collection2">The second collection.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality.</param>
        /// <returns>True if <paramref name="collection1"/> is a subset of <paramref name="collection2"/>, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static bool IsSubsetOf<T>(IEnumerable<T> collection1, IEnumerable<T> collection2, IEqualityComparer<T> equalityComparer)
        {
            if (collection1 == null)
                throw new ArgumentNullException("collection1");
            if (collection2 == null)
                throw new ArgumentNullException("collection2");
            if (equalityComparer == null)
                throw new ArgumentException("equalityComparer");

            Bag<T> bag1 = new Bag<T>(collection1, equalityComparer);
            Bag<T> bag2 = new Bag<T>(collection2, equalityComparer);
            return bag2.IsSupersetOf(bag1);
        }

        /// <summary>
        /// Determines if one collection is a proper subset of another, considered as sets. The first set is a proper subset
        /// of the second set if every item in the first set also occurs in the second set, and the first set is strictly smaller than
        /// the second set. If an item appears X times in the first set,
        /// it must appear at least X times in the second set.
        /// </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>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the IsSubsetOf method on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection.</param>
        /// <param name="collection2">The second collection.</param>
        /// <returns>True if <paramref name="collection1"/> is a subset of <paramref name="collection2"/>, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static bool IsProperSubsetOf<T>(IEnumerable<T> collection1, IEnumerable<T> collection2)
        {
            return IsProperSubsetOf(collection1, collection2, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Determines if one collection is a proper subset of another, considered as sets. The first set is a proper subset
        /// of the second set if every item in the first set also occurs in the second set, and the first set is strictly smaller than
        /// the second set. If an item appears X times in the first set,
        /// it must appear at least X times in the second set.
        /// </summary>
        /// <remarks>
        /// <para>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the IsSubsetOf method on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection.</param>
        /// <param name="collection2">The second collection.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. 
        /// Only the Equals and GetHashCode member functions of this interface are called.</param>
        /// <returns>True if <paramref name="collection1"/> is a proper subset of <paramref name="collection2"/>, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static bool IsProperSubsetOf<T>(IEnumerable<T> collection1, IEnumerable<T> collection2, IEqualityComparer<T> equalityComparer)
        {
            if (collection1 == null)
                throw new ArgumentNullException("collection1");
            if (collection2 == null)
                throw new ArgumentNullException("collection2");
            if (equalityComparer == null)
                throw new ArgumentException("equalityComparer");

            Bag<T> bag1 = new Bag<T>(collection1, equalityComparer);
            Bag<T> bag2 = new Bag<T>(collection2, equalityComparer);
            return bag2.IsProperSupersetOf(bag1);
        }

        
        
        /// <summary>
        /// Determines if two collections are disjoint, considered as sets. Two sets are disjoint if they
        /// have no common items.
        /// </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>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the IsDisjoint method on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection.</param>
        /// <param name="collection2">The second collection.</param>
        /// <returns>True if <paramref name="collection1"/> are <paramref name="collection2"/> are disjoint, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static bool DisjointSets<T>(IEnumerable<T> collection1, IEnumerable<T> collection2)
        {
            return DisjointSets(collection1, collection2, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Determines if two collections are disjoint, considered as sets. Two sets are disjoint if they
        /// have no common items.
        /// </summary>
        /// <remarks>
        /// <para>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the IsDisjoint method on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection.</param>
        /// <param name="collection2">The second collection.</param>
        /// <param name="equalityComparer">The IEqualityComparerComparer&lt;T&gt; used to compare items for equality. 
        /// Only the Equals and GetHashCode member functions of this interface are called.</param>
        /// <returns>True if <paramref name="collection1"/> are <paramref name="collection2"/> are disjoint, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static bool DisjointSets<T>(IEnumerable<T> collection1, IEnumerable<T> collection2, IEqualityComparer<T> equalityComparer)
        {
            if (collection1 == null)
                throw new ArgumentNullException("collection1");
            if (collection2 == null)
                throw new ArgumentNullException("collection2");
            if (equalityComparer == null)
                throw new ArgumentException("equalityComparer");

            Set<T> set1 = new Set<T>(collection1, equalityComparer);

            foreach (T item2 in collection2) {
                if (set1.Contains(item2))
                    return false;
            }

            return true;
        }

        /// <summary>
        /// Determines if two collections are equal, considered as sets. Two sets are equal if they
        /// have have the same items, with order not being significant.
        /// </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>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the EqualTo method on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection.</param>
        /// <param name="collection2">The second collection.</param>
        /// <returns>True if <paramref name="collection1"/> are <paramref name="collection2"/> are equal, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static bool EqualSets<T>(IEnumerable<T> collection1, IEnumerable<T> collection2)
        {
            return EqualSets(collection1, collection2, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Determines if two collections are equal, considered as sets. Two sets are equal if they
        /// have have the same items, with order not being significant.
        /// </summary>
        /// <remarks>
        /// <para>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the EqualTo method on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection.</param>
        /// <param name="collection2">The second collection.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. 
        /// Only the Equals and GetHashCode member functions of this interface are called.</param>
        /// <returns>True if <paramref name="collection1"/> are <paramref name="collection2"/> are equal, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static bool EqualSets<T>(IEnumerable<T> collection1, IEnumerable<T> collection2, IEqualityComparer<T> equalityComparer)
        {
            if (collection1 == null)
                throw new ArgumentNullException("collection1");
            if (collection2 == null)
                throw new ArgumentNullException("collection2");
            if (equalityComparer == null)
                throw new ArgumentException("equalityComparer");

            Bag<T> bag1 = new Bag<T>(collection1, equalityComparer);
            Bag<T> bag2 = new Bag<T>(collection2, equalityComparer);
            return bag2.IsEqualTo(bag1);
        }

        /// <summary>
        /// Computes the set-theoretic intersection of two collections. The intersection of two sets
        /// is all items that appear in both of the sets. If an item appears X times in one set,
        /// and Y times in the other set, the intersection contains the item Minimum(X,Y) times. 
        /// The source collections are not changed.
        /// A new collection is created with the intersection of the collections; the order of the
        /// items in this collection is undefined.
        /// </summary>
        /// <remarks>
        /// <para>When equal items appear in both collections, the returned collection will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <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>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the Intersection or IntersectionWith methods on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection to intersect.</param>
        /// <param name="collection2">The second collection to intersect.</param>
        /// <returns>The intersection of the two collections, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static IEnumerable<T> SetIntersection<T>(IEnumerable<T> collection1, IEnumerable<T> collection2)
        {
            return SetIntersection(collection1, collection2, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Computes the set-theoretic intersection of two collections. The intersection of two sets
        /// is all items that appear in both of the sets. If an item appears X times in one set,
        /// and Y times in the other set, the intersection contains the item Minimum(X,Y) times. 
        /// The source collections are not changed.
        /// A new collection is created with the intersection of the collections; the order of the
        /// items in this collection is undefined.
        /// </summary>
        /// <remarks>
        /// <para>When equal items appear in both collections, the returned collection will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <para>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the Intersection or IntersectionWith methods on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection to intersect.</param>
        /// <param name="collection2">The second collection to intersect.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. 
        /// Only the Equals and GetHashCode member functions of this interface are called.</param>
        /// <returns>The intersection of the two collections, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static IEnumerable<T> SetIntersection<T>(IEnumerable<T> collection1, IEnumerable<T> collection2, IEqualityComparer<T> equalityComparer)
        {
            if (collection1 == null)
                throw new ArgumentNullException("collection1");
            if (collection2 == null)
                throw new ArgumentNullException("collection2");
            if (equalityComparer == null)
                throw new ArgumentException("equalityComparer");

            Bag<T> bag1 = new Bag<T>(collection1, equalityComparer);
            Bag<T> bag2 = new Bag<T>(collection2, equalityComparer);
            return Util.CreateEnumerableWrapper(bag1.Intersection(bag2));
        }

        /// <summary>
        /// Computes the set-theoretic union of two collections. The union of two sets
        /// is all items that appear in either of the sets. If an item appears X times in one set,
        /// and Y times in the other set, the union contains the item Maximum(X,Y) times. 
        /// The source collections are not changed.
        /// A new collection is created with the union of the collections; the order of the
        /// items in this collection is undefined.
        /// </summary>
        /// <remarks>
        /// <para>When equal items appear in both collections, the returned collection will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <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>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the Union or UnionWith methods on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection to union.</param>
        /// <param name="collection2">The second collection to union.</param>
        /// <returns>The union of the two collections, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static IEnumerable<T> SetUnion<T>(IEnumerable<T> collection1, IEnumerable<T> collection2)
        {
            return SetUnion(collection1, collection2, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Computes the set-theoretic union of two collections. The union of two sets
        /// is all items that appear in either of the sets. If an item appears X times in one set,
        /// and Y times in the other set, the union contains the item Maximum(X,Y) times. 
        /// The source collections are not changed.
        /// A new collection is created with the union of the collections; the order of the
        /// items in this collection is undefined.
        /// </summary>
        /// <remarks>
        /// <para>When equal items appear in both collections, the returned collection will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <para>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the union or unionWith methods on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection to union.</param>
        /// <param name="collection2">The second collection to union.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. 
        /// Only the Equals and GetHashCode member functions of this interface are called.</param>
        /// <returns>The union of the two collections, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static IEnumerable<T> SetUnion<T>(IEnumerable<T> collection1, IEnumerable<T> collection2, IEqualityComparer<T> equalityComparer)
        {
            if (collection1 == null)
                throw new ArgumentNullException("collection1");
            if (collection2 == null)
                throw new ArgumentNullException("collection2");
            if (equalityComparer == null)
                throw new ArgumentException("equalityComparer");

            Bag<T> bag1 = new Bag<T>(collection1, equalityComparer);
            Bag<T> bag2 = new Bag<T>(collection2, equalityComparer);
            if (bag1.Count > bag2.Count) {
                bag1.UnionWith(bag2);
                return Util.CreateEnumerableWrapper(bag1);
            }
            else {
                bag2.UnionWith(bag1);
                return Util.CreateEnumerableWrapper(bag2);
            }
        }

        /// <summary>
        /// Computes the set-theoretic difference of two collections. The difference of two sets
        /// is all items that appear in the first set, but not in the second. If an item appears X times in the first set,
        /// and Y times in the second set, the difference contains the item X - Y times (0 times if X &lt; Y). 
        /// The source collections are not changed.
        /// A new collection is created with the difference of the collections; the order of the
        /// items in this collection is undefined.
        /// </summary>
        /// <remarks>
        /// <para>When equal items appear in both collections, the returned collection will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <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>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the Difference or DifferenceWith methods on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection to difference.</param>
        /// <param name="collection2">The second collection to difference.</param>
        /// <returns>The difference of <paramref name="collection1"/> and <paramref name="collection2"/>, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static IEnumerable<T> SetDifference<T>(IEnumerable<T> collection1, IEnumerable<T> collection2)
        {
            return SetDifference(collection1, collection2, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Computes the set-theoretic difference of two collections. The difference of two sets
        /// is all items that appear in the first set, but not in the second. If an item appears X times in the first set,
        /// and Y times in the second set, the difference contains the item X - Y times (0 times if X &lt; Y). 
        /// The source collections are not changed.
        /// A new collection is created with the difference of the collections; the order of the
        /// items in this collection is undefined.
        /// </summary>
        /// <remarks>
        /// <para>When equal items appear in both collections, the returned collection will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <para>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the difference or differenceWith methods on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection to difference.</param>
        /// <param name="collection2">The second collection to difference.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. 
        /// Only the Equals and GetHashCode member functions of this interface are called.</param>
        /// <returns>The difference of <paramref name="collection1"/> and <paramref name="collection2"/>, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static IEnumerable<T> SetDifference<T>(IEnumerable<T> collection1, IEnumerable<T> collection2, IEqualityComparer<T> equalityComparer)
        {
            if (collection1 == null)
                throw new ArgumentNullException("collection1");
            if (collection2 == null)
                throw new ArgumentNullException("collection2");
            if (equalityComparer == null)
                throw new ArgumentException("equalityComparer");

            Bag<T> bag1 = new Bag<T>(collection1, equalityComparer);
            Bag<T> bag2 = new Bag<T>(collection2, equalityComparer);
            bag1.DifferenceWith(bag2);
            return Util.CreateEnumerableWrapper(bag1);
        }

        /// <summary>
        /// Computes the set-theoretic symmetric difference of two collections. The symmetric difference of two sets
        /// is all items that appear in the one of the sets, but not in the other. If an item appears X times in the one set,
        /// and Y times in the other set, the symmetric difference contains the item AbsoluteValue(X - Y) times. 
        /// The source collections are not changed.
        /// A new collection is created with the symmetric difference of the collections; the order of the
        /// items in this collection is undefined.
        /// </summary>
        /// <remarks>
        /// <para>When equal items appear in both collections, the returned collection will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <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>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the SymmetricDifference or SymmetricDifferenceWith methods on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection to symmetric difference.</param>
        /// <param name="collection2">The second collection to symmetric difference.</param>
        /// <returns>The symmetric difference of <paramref name="collection1"/> and <paramref name="collection2"/>, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static IEnumerable<T> SetSymmetricDifference<T>(IEnumerable<T> collection1, IEnumerable<T> collection2)
        {
            return SetSymmetricDifference(collection1, collection2, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Computes the set-theoretic symmetric difference of two collections. The symmetric difference of two sets
        /// is all items that appear in the one of the sets, but not in the other. If an item appears X times in the one set,
        /// and Y times in the other set, the symmetric difference contains the item AbsoluteValue(X - Y) times. 
        /// The source collections are not changed.
        /// A new collection is created with the symmetric difference of the collections; the order of the
        /// items in this collection is undefined.
        /// </summary>
        /// <remarks>
        /// <para>When equal items appear in both collections, the returned collection will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <para>If both collections are Set, Bag, OrderedSet, or OrderedBag
        /// collections, it is more efficient to use the symmetric difference or symmetric differenceWith methods on that class.</para>
        /// </remarks>
        /// <param name="collection1">The first collection to symmetric difference.</param>
        /// <param name="collection2">The second collection to symmetric difference.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. 
        /// Only the Equals and GetHashCode member functions of this interface are called.</param>
        /// <returns>The symmetric difference of <paramref name="collection1"/> and <paramref name="collection2"/>, considered as sets.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/> or <paramref name="collection2"/> is null.</exception>
        public static IEnumerable<T> SetSymmetricDifference<T>(IEnumerable<T> collection1, IEnumerable<T> collection2, IEqualityComparer<T> equalityComparer)
        {
            if (collection1 == null)
                throw new ArgumentNullException("collection1");
            if (collection2 == null)
                throw new ArgumentNullException("collection2");
            if (equalityComparer == null)
                throw new ArgumentException("equalityComparer");

            Bag<T> bag1 = new Bag<T>(collection1, equalityComparer);
            Bag<T> bag2 = new Bag<T>(collection2, equalityComparer);
            if (bag1.Count > bag2.Count) {
                bag1.SymmetricDifferenceWith(bag2);
                return Util.CreateEnumerableWrapper(bag1);
            }
            else {
                bag2.SymmetricDifferenceWith(bag1);
                return Util.CreateEnumerableWrapper(bag2);
            }
        }

        /// <summary>
        /// Computes the cartestian product of two collections: all possible pairs of items, with the first item taken from the first collection and 
        /// the second item taken from the second collection. If the first collection has N items, and the second collection has M items, the cartesian
        /// product will have N * M pairs.
        /// </summary>
        /// <typeparam name="TFirst">The type of items in the first collection.</typeparam>
        /// <typeparam name="TSecond">The type of items in the second collection.</typeparam>
        /// <param name="first">The first collection.</param>
        /// <param name="second">The second collection.</param>
        /// <returns>An IEnumerable&lt;Pair&lt;TFirst, TSecond&gt;&gt; that enumerates the cartesian product of the two collections.</returns>
        public static IEnumerable<Pair<TFirst, TSecond>> CartesianProduct<TFirst, TSecond>(IEnumerable<TFirst> first, IEnumerable<TSecond> second)
        {
            if (first == null)
                throw new ArgumentNullException("first");
            if (second == null)
                throw new ArgumentNullException("second");

            foreach (TFirst itemFirst in first)
                foreach (TSecond itemSecond in second)
                    yield return new Pair<TFirst, TSecond>(itemFirst, itemSecond);
        }

        #endregion Set operations 

        #region String representations (not yet coded)

        /// <summary>
        /// Gets a string representation of the elements in the collection.
        /// The string representation starts with "{", has a list of items separated
        /// by commas (","), and ends with "}". Each item in the collection is 
        /// converted to a string by calling its ToString method (null is represented by "null").
        /// Contained collections (except strings) are recursively converted to strings by this method.
        /// </summary>
        /// <param name="collection">A collection to get the string representation of.</param>
        /// <returns>The string representation of the collection. If <paramref name="collection"/> is null, then the string "null" is returned.</returns>
        public static string ToString<T>(IEnumerable<T> collection)
        {
            return ToString(collection, true, "{", ",", "}");
        }

        /// <summary>
        /// Gets a string representation of the elements in the collection.
        /// The string to used at the beginning and end, and to separate items,
        /// and supplied by parameters. Each item in the collection is 
        /// converted to a string by calling its ToString method (null is represented by "null").
        /// </summary>
        /// <param name="collection">A collection to get the string representation of.</param>
        /// <param name="recursive">If true, contained collections (except strings) are converted to strings by a recursive call to this method, instead
        /// of by calling ToString.</param>
        /// <param name="start">The string to appear at the beginning of the output string.</param>
        /// <param name="separator">The string to appear between each item in the string.</param>
        /// <param name="end">The string to appear at the end of the output string.</param>
        /// <returns>The string representation of the collection. If <paramref name="collection"/> is null, then the string "null" is returned.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="start"/>, <paramref name="separator"/>, or <paramref name="end"/>
        ///  is null.</exception>
        public static string ToString<T>(IEnumerable<T> collection, bool recursive, string start, string separator, string end)
        {
            if (start == null)
                throw new ArgumentNullException("start");
            if (separator == null)
                throw new ArgumentNullException("separator");
            if (end == null)
                throw new ArgumentNullException("end");

            if (collection == null)
                return "null";

            bool firstItem = true;

            System.Text.StringBuilder builder = new System.Text.StringBuilder();

            builder.Append(start);

            // Call ToString on each item and put it in.
            foreach (T item in collection) {
                if (!firstItem)
                    builder.Append(separator);

                if (item == null)
                    builder.Append("null");
                else if (recursive && item is IEnumerable && !(item is string))
                    builder.Append(Algorithms.ToString(Algorithms.TypedAs<object>((IEnumerable)item), recursive, start, separator, end));
                else
                    builder.Append(item.ToString());

                firstItem = false;
            }

            builder.Append(end);
            return builder.ToString();
        }

        /// <summary>
        /// Gets a string representation of the mappings in a dictionary.
        /// The string representation starts with "{", has a list of mappings separated
        /// by commas (", "), and ends with "}". Each mapping is represented
        /// by "key->value". Each key and value in the dictionary is 
        /// converted to a string by calling its ToString method (null is represented by "null").
        /// Contained collections (except strings) are recursively converted to strings by this method.
        /// </summary>
        /// <param name="dictionary">A dictionary to get the string representation of.</param>
        /// <returns>The string representation of the collection, or "null" 
        /// if <paramref name="dictionary"/> is null.</returns>
        public static string ToString<TKey, TValue>(IDictionary<TKey, TValue> dictionary)
        {
            bool firstItem = true;

            if (dictionary == null)
                return "null";

            System.Text.StringBuilder builder = new System.Text.StringBuilder();

            builder.Append("{");

            // Call ToString on each item and put it in.
            foreach (KeyValuePair<TKey, TValue> pair in dictionary) {
                if (!firstItem)
                    builder.Append(", ");

                if (pair.Key == null)
                    builder.Append("null");
                else if (pair.Key is IEnumerable && !(pair.Key is string))
                    builder.Append(Algorithms.ToString(Algorithms.TypedAs<object>((IEnumerable)pair.Key), true, "{", ",", "}"));
                else
                    builder.Append(pair.Key.ToString());

                builder.Append("->");

                if (pair.Value == null)
                    builder.Append("null");
                else if (pair.Value is IEnumerable && !(pair.Value is string))
                    builder.Append(Algorithms.ToString(Algorithms.TypedAs<object>((IEnumerable)pair.Value), true, "{", ",", "}"));
                else
                    builder.Append(pair.Value.ToString());


                firstItem = false;
            }

            builder.Append("}");
            return builder.ToString();
        }

        #endregion String representations

        #region Shuffles and Permutations

        private static volatile Random myRandomGenerator;

        /// <summary>
        /// Return a private random number generator to use if the user
        /// doesn't supply one.
        /// </summary>
        /// <returns>The private random number generator. Only one is ever created
        /// and is always returned.</returns>
        private static Random GetRandomGenerator()
        {
            if (myRandomGenerator == null) {
                lock (typeof(Algorithms)) {
                    if (myRandomGenerator == null)
                        myRandomGenerator = new Random();
                }
            }

            return myRandomGenerator;
        }

        /// <summary>
        /// Randomly shuffles the items in a collection, yielding a new collection.
        /// </summary>
        /// <typeparam name="T">The type of the items in the collection.</typeparam>
        /// <param name="collection">The collection to shuffle.</param>
        /// <returns>An array with the same size and items as <paramref name="collection"/>, but the items in a randomly chosen order.</returns>
        public static T[] RandomShuffle<T>(IEnumerable<T> collection)
        {
            return RandomShuffle<T>(collection, GetRandomGenerator());
        }

        /// <summary>
        /// Randomly shuffles the items in a collection, yielding a new collection.
        /// </summary>
        /// <typeparam name="T">The type of the items in the collection.</typeparam>
        /// <param name="collection">The collection to shuffle.</param>
        /// <param name="randomGenerator">The random number generator to use to select the random order.</param>
        /// <returns>An array with the same size and items as <paramref name="collection"/>, but the items in a randomly chosen order.</returns>
        public static T[] RandomShuffle<T>(IEnumerable<T> collection, Random randomGenerator)
        {
            // We have to copy all items anyway, and there isn't a way to produce the items
            // on the fly that is linear. So copying to an array and shuffling it is an efficient as we can get.
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (randomGenerator == null)
                throw new ArgumentNullException("randomGenerator");

            T[] array = Algorithms.ToArray(collection);

            int count = array.Length;
            for (int i = count - 1; i >= 1; --i) {
                // Pick an random number 0 through i inclusive.
                int j = randomGenerator.Next(i + 1);

                // Swap array[i] and array[j]
                T temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }

            return array;
        }

        /// <summary>
        /// Randomly shuffles the items in a list or array, in place.
        /// </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 shuffle.</param>
        public static void RandomShuffleInPlace<T>(IList<T> list)
        {
            RandomShuffleInPlace<T>(list, GetRandomGenerator());
        }

        /// <summary>
        /// Randomly shuffles the items in a list or array, in place.
        /// </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 shuffle.</param>
        /// <param name="randomGenerator">The random number generator to use to select the random order.</param>
        public static void RandomShuffleInPlace<T>(IList<T> list, Random randomGenerator)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (randomGenerator == null)
                throw new ArgumentNullException("randomGenerator");
            if (list is T[])
                list = new ArrayWrapper<T>((T[])list);
            if (list.IsReadOnly)
                throw new ArgumentException(Strings.ListIsReadOnly, "list");

            int count = list.Count;
            for (int i = count - 1; i >= 1; --i) {
                // Pick an random number 0 through i inclusive.
                int j = randomGenerator.Next(i + 1);

                // Swap list[i] and list[j]
                T temp = list[i];
                list[i] = list[j];
                list[j] = temp;
            }
        }

        /// <summary>
        /// Picks a random subset of <paramref name="count"/> items from <paramref name="collection"/>, and places
        /// those items into a random order. No item is selected more than once.
        /// </summary>
        /// <remarks>If the collection implements IList&lt;T&gt;, then this method takes time O(<paramref name="count"/>).
        /// Otherwise, this method takes time O(N), where N is the number of items in the collection.</remarks>
        /// <typeparam name="T">The type of items in the collection.</typeparam>
        /// <param name="collection">The collection of items to select from. This collection is not changed.</param>
        /// <param name="count">The number of items in the subset to choose.</param>
        /// <returns>An array of <paramref name="count"/> items, selected at random from <paramref name="collection"/>.</returns>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="count"/> is negative or greater than <paramref name="collection"/>.Count.</exception>
        public static T[] RandomSubset<T>(IEnumerable<T> collection, int count)
        {
            return RandomSubset<T>(collection, count, GetRandomGenerator());
        }

        /// <summary>
        /// Picks a random subset of <paramref name="count"/> items from <paramref name="collection"/>, and places
        /// those items into a random order. No item is selected more than once.
        /// </summary>
        /// <remarks>If the collection implements IList&lt;T&gt;, then this method takes time O(<paramref name="count"/>).
        /// Otherwise, this method takes time O(N), where N is the number of items in the collection.</remarks>
        /// <typeparam name="T">The type of items in the collection.</typeparam>
        /// <param name="collection">The collection of items to select from. This collection is not changed.</param>
        /// <param name="count">The number of items in the subset to choose.</param>
        /// <param name="randomGenerator">The random number generates used to make the selection.</param>
        /// <returns>An array of <paramref name="count"/> items, selected at random from <paramref name="collection"/>.</returns>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="count"/> is negative or greater than <paramref name="list"/>.Count.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="randomGenerator"/> is null.</exception>
        public static T[] RandomSubset<T>(IEnumerable<T> collection, int count, Random randomGenerator)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (randomGenerator == null)
                throw new ArgumentNullException("randomGenerator");

            // We need random access to the items in the collection. If it's not already an 
            // IList<T>, copy to a temporary list.
            IList<T> list = collection as IList<T>;
            if (list == null) {
                list = new List<T>(collection);
            }

            int listCount = list.Count;
            if (count < 0 || count > listCount)
                throw new ArgumentOutOfRangeException("count");

            T[] result = new T[count];  // the result array.
            Dictionary<int, T> swappedValues = new Dictionary<int, T>(count);   // holds swapped values from the list.

            for (int i = 0; i < count; ++i) {
                // Set j to the index of the item to swap with, and value to the value to swap with.
                T value;
                int j = randomGenerator.Next(listCount - i) + i;

                // Swap values of i and j in the list. The list isn't actually changed; instead,
                // swapped values are stored in the dictionary swappedValues.
                if (!swappedValues.TryGetValue(j, out value))
                    value = list[j];

                result[i] = value;
                if (i != j) {
                    if (swappedValues.TryGetValue(i, out value))
                        swappedValues[j] = value;
                    else
                        swappedValues[j] = list[i];
                }
            }

            return result;
        }

        /// <summary>
        /// Generates all the possible permutations of the items in <paramref name="collection"/>. If <paramref name="collection"/>
        /// has N items, then N factorial permutations will be generated. This method does not compare the items to determine if
        /// any of them are equal. If some items are equal, the same permutation may be generated more than once. For example,
        /// if the collections contains the three items A, A, and B, then this method will generate the six permutations, AAB, AAB,
        /// ABA, ABA, BAA, BAA (not necessarily in that order). To take equal items into account, use the GenerateSortedPermutations
        /// method.
        /// </summary>
        /// <typeparam name="T">The type of items to permute.</typeparam>
        /// <param name="collection">The collection of items to permute.</param>
        /// <returns>An IEnumerable&lt;T[]&gt; that enumerations all the possible permutations of the 
        /// items in <paramref name="collection"/>. Each permutations is returned as an array. The items in the array
        /// should be copied if they need to be used after the next permutation is generated; each permutation may
        /// reuse the same array instance.</returns>
        public static IEnumerable<T[]> GeneratePermutations<T>(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            T[] array = Algorithms.ToArray(collection);

            if (array.Length == 0)
                yield break;

            int[] state = new int[array.Length - 1];
            int maxLength = state.Length;

            yield return array;

            if (array.Length == 1)
                yield break;

            // The following algorithm makes two swaps for each
            // permutation generated.
            // This is not optimal in terms of number of swaps, but
            // is still O(1), and shorter and clearer to understand.
            int i = 0;
            T temp;
            for (; ; ) {
                if (state[i] < i + 1) {
                    if (state[i] > 0) {
                        temp = array[i + 1];
                        array[i + 1] = array[state[i] - 1];
                        array[state[i] - 1] = temp;
                    }

                    temp = array[i + 1];
                    array[i + 1] = array[state[i]];
                    array[state[i]] = temp;

                    yield return array;

                    ++state[i];
                    i = 0;
                }
                else {
                    temp = array[i + 1];
                    array[i + 1] = array[i];
                    array[i] = temp;

                    state[i] = 0;
                    ++i;
                    if (i >= maxLength)
                        yield break;
                }
            } 
        }

        /// <summary>
        /// Generates all the possible permutations of the items in <paramref name="collection"/>, in lexicographical order. 
        /// Even if some items are equal, the same permutation will not be generated more than once. For example,
        /// if the collections contains the three items A, A, and B, then this method will generate only the three permutations, AAB, ABA,
        /// BAA. 
        /// </summary>
        /// <typeparam name="T">The type of items to permute.</typeparam>
        /// <param name="collection">The collection of items to permute.</param>
        /// <returns>An IEnumerable&lt;T[]&gt; that enumerations all the possible permutations of the 
        /// items in <paramref name="collection"/>. Each permutations is returned as an array. The items in the array
        /// should be copied if they need to be used after the next permutation is generated; each permutation may
        /// reuse the same array instance.</returns>
        public static IEnumerable<T[]> GenerateSortedPermutations<T>(IEnumerable<T> collection)
            where T: IComparable<T>
        {
            return GenerateSortedPermutations<T>(collection, Comparer<T>.Default);
        }

        /// <summary>
        /// Generates all the possible permutations of the items in <paramref name="collection"/>, in lexicographical order. A
        /// supplied IComparer&lt;T&gt; instance is used to compare the items.
        /// Even if some items are equal, the same permutation will not be generated more than once. For example,
        /// if the collections contains the three items A, A, and B, then this method will generate only the three permutations, AAB, ABA,
        /// BAA. 
        /// </summary>
        /// <typeparam name="T">The type of items to permute.</typeparam>
        /// <param name="collection">The collection of items to permute.</param>
        /// <param name="comparer">The IComparer&lt;T&gt; used to compare the items.</param>
        /// <returns>An IEnumerable&lt;T[]&gt; that enumerations all the possible permutations of the 
        /// items in <paramref name="collection"/>. Each permutations is returned as an array. The items in the array
        /// should be copied if they need to be used after the next permutation is generated; each permutation may
        /// reuse the same array instance.</returns>
        public static IEnumerable<T[]> GenerateSortedPermutations<T>(IEnumerable<T> collection, IComparer<T> comparer)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            T[] array = Algorithms.ToArray(collection);
            int length = array.Length;
            if (length == 0)
                yield break;

            Array.Sort(array, comparer);

            yield return array;
            if (length == 1)
                yield break;

            // Keep generating the next permutation until we're done. Algorithm is
            // due to Jeffrey A. Johnson ("SEPA - a Simple Efficient Permutation Algorithm")
            int key, swap, i, j;
            T temp;
            for (; ; ) {
                // Find the key point -- where array[key]<array[key+1]. Everything after the
                // key is the tail.
                key = length - 2;
                while (comparer.Compare(array[key], array[key+1]) >= 0) {
                    --key;
                    if (key < 0)
                        yield break;
                }

                // Find the last item in the tail less than key.
                swap = length - 1;
                while (comparer.Compare(array[swap], array[key]) <= 0)
                    --swap;

                // Swap it with the key.
                temp = array[key];
                array[key] = array[swap];
                array[swap] = temp;

                // Reverse the tail.
                i = key + 1;
                j = length - 1;
                while (i < j) {
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    ++i; --j;
                }

                yield return array;
            }
        }

        /// <summary>
        /// Generates all the possible permutations of the items in <paramref name="collection"/>, in lexicographical order. A
        /// supplied Comparison&lt;T&gt; delegate is used to compare the items.
        /// Even if some items are equal, the same permutation will not be generated more than once. For example,
        /// if the collections contains the three items A, A, and B, then this method will generate only the three permutations, AAB, ABA,
        /// BAA. 
        /// </summary>
        /// <typeparam name="T">The type of items to permute.</typeparam>
        /// <param name="collection">The collection of items to permute.</param>
        /// <param name="comparison">The Comparison&lt;T&gt; delegate used to compare the items.</param>
        /// <returns>An IEnumerable&lt;T[]&gt; that enumerations all the possible permutations of the 
        /// items in <paramref name="collection"/>. Each permutations is returned as an array. The items in the array
        /// should be copied if they need to be used after the next permutation is generated; each permutation may
        /// reuse the same array instance.</returns>
        public static IEnumerable<T[]> GenerateSortedPermutations<T>(IEnumerable<T> collection, Comparison<T> comparison)
        {
            return GenerateSortedPermutations(collection, Comparers.ComparerFromComparison<T>(comparison));
        }

        #endregion Shuffles and Permutations

        #region Minimum and Maximum

        /// <summary>
        /// Finds the maximum value in a collection.
        /// </summary>
        /// <remarks>Values in the collection are compared by using the IComparable&lt;T&gt;
        /// interfaces implementation on the type T.</remarks>
        /// <typeparam name="T">The type of items in the collection.</typeparam>
        /// <param name="collection">The collection to search.</param>
        /// <returns>The largest item in the collection. </returns>
        /// <exception cref="InvalidOperationException">The collection is empty.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
        public static T Maximum<T>(IEnumerable<T> collection)
            where T : IComparable<T>
        {
            return Maximum<T>(collection, Comparer<T>.Default);
        }

        /// <summary>
        /// Finds the maximum value in a collection. A supplied IComparer&lt;T&gt; is used
        /// to compare the items in the collection.
        /// </summary>
        /// <typeparam name="T">The type of items in the collection.</typeparam>
        /// <param name="collection">The collection to search.</param>
        /// <param name="comparer">The comparer instance used to compare items in the collection.</param>
        /// <returns>The largest item in the collection.</returns>
        /// <exception cref="InvalidOperationException">The collection is empty.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> or <paramref name="comparer"/> is null.</exception>
        public static T Maximum<T>(IEnumerable<T> collection, IComparer<T> comparer)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            T maxSoFar = default(T);
            bool foundOne = false;

            // Go through the collection, keeping the maximum found so far.
            foreach (T item in collection) {
                if (!foundOne || comparer.Compare(maxSoFar, item) < 0) {
                    maxSoFar = item;
                }

                foundOne = true;
            }

            // If the collection was empty, throw an exception.
            if (!foundOne)
                throw new InvalidOperationException(Strings.CollectionIsEmpty);
            else
                return maxSoFar;
        }

        /// <summary>
        /// Finds the maximum value in a collection. A supplied Comparison&lt;T&gt; delegate is used
        /// to compare the items in the collection.
        /// </summary>
        /// <typeparam name="T">The type of items in the collection.</typeparam>
        /// <param name="collection">The collection to search.</param>
        /// <param name="comparison">The comparison used to compare items in the collection.</param>
        /// <returns>The largest item in the collection.</returns>
        /// <exception cref="InvalidOperationException">The collection is empty.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> or <paramref name="comparison"/> is null.</exception>
        public static T Maximum<T>(IEnumerable<T> collection, Comparison<T> comparison)
        {
            return Maximum<T>(collection, Comparers.ComparerFromComparison<T>(comparison));
        }

        /// <summary>
        /// Finds the minimum value in a collection.
        /// </summary>
        /// <remarks>Values in the collection are compared by using the IComparable&lt;T&gt;
        /// interfaces implementation on the type T.</remarks>
        /// <typeparam name="T">The type of items in the collection.</typeparam>
        /// <param name="collection">The collection to search.</param>
        /// <returns>The smallest item in the collection.</returns>
        /// <exception cref="InvalidOperationException">The collection is empty.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
        public static T Minimum<T>(IEnumerable<T> collection)
            where T : IComparable<T>
        {
            return Minimum<T>(collection, Comparer<T>.Default);
        }

        /// <summary>
        /// Finds the minimum value in a collection. A supplied IComparer&lt;T&gt; is used
        /// to compare the items in the collection.
        /// </summary>
        /// <typeparam name="T">The type of items in the collection.</typeparam>
        /// <param name="collection">The collection to search.</param>
        /// <param name="comparer">The comparer instance used to compare items in the collection.</param>
        /// <returns>The smallest item in the collection.</returns>
        /// <exception cref="InvalidOperationException">The collection is empty.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> or <paramref name="comparer"/> is null.</exception>
        public static T Minimum<T>(IEnumerable<T> collection, IComparer<T> comparer)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            T minSoFar = default(T);
            bool foundOne = false;

            // Go through the collection, keeping the minimum found so far.
            foreach (T item in collection) {
                if (!foundOne || comparer.Compare(minSoFar, item) > 0) {
                    minSoFar = item;
                }

                foundOne = true;
            }

            // If the collection was empty, throw an exception.
            if (!foundOne)
                throw new InvalidOperationException(Strings.CollectionIsEmpty);
            else
                return minSoFar;
        }

        /// <summary>
        /// Finds the minimum value in a collection. A supplied Comparison&lt;T&gt; delegate is used
        /// to compare the items in the collection.
        /// </summary>
        /// <typeparam name="T">The type of items in the collection.</typeparam>
        /// <param name="collection">The collection to search.</param>
        /// <param name="comparison">The comparison used to compare items in the collection.</param>
        /// <returns>The smallest item in the collection.</returns>
        /// <exception cref="InvalidOperationException">The collection is empty.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> or <paramref name="comparison"/> is null.</exception>
        public static T Minimum<T>(IEnumerable<T> collection, Comparison<T> comparison)
        {
            return Minimum<T>(collection, Comparers.ComparerFromComparison<T>(comparison));
        }

        /// <summary>
        /// Finds the index of the maximum value in a list.
        /// </summary>
        /// <remarks>Values in the list are compared by using the IComparable&lt;T&gt;
        /// interfaces implementation on the type T.</remarks>
        /// <typeparam name="T">The type of items in the list.</typeparam>
        /// <param name="list">The list to search.</param>
        /// <returns>The index of the largest item in the list. If the maximum value appears
        /// multiple times, the index of the first appearance is used. If the list is empty, -1 is returned.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
        public static int IndexOfMaximum<T>(IList<T> list)
           where T : IComparable<T>
        {
            return IndexOfMaximum<T>(list, Comparer<T>.Default);
        }

        /// <summary>
        /// Finds the index of the maximum value in a list. A supplied IComparer&lt;T&gt; is used
        /// to compare the items in the collection. 
        /// </summary>
        /// <typeparam name="T">The type of items in the list.</typeparam>
        /// <param name="list">The list to search.</param>
        /// <param name="comparer">The comparer instance used to compare items in the collection.</param>
        /// <returns>The index of the largest item in the list. If the maximum value appears
        /// multiple times, the index of the first appearance is used. If the list is empty, -1 is returned.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> or <paramref name="comparer"/> is null.</exception>
        public static int IndexOfMaximum<T>(IList<T> list, IComparer<T> comparer)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            T maxSoFar = default(T);
            int indexSoFar = -1;

            // Go through the collection, keeping the maximum found so far.
            int i = 0;
            foreach (T item in list) {
                if (indexSoFar < 0 || comparer.Compare(maxSoFar, item) < 0) {
                    maxSoFar = item;
                    indexSoFar = i;
                }

                ++i;
            }

            return indexSoFar;
        }

        /// <summary>
        /// Finds the index of the maximum value in a list. A supplied Comparison&lt;T&gt; delegate is used
        /// to compare the items in the collection.
        /// </summary>
        /// <typeparam name="T">The type of items in the list.</typeparam>
        /// <param name="list">The list to search.</param>
        /// <param name="comparison">The comparison used to compare items in the collection.</param>
        /// <returns>The index of the largest item in the list. If the maximum value appears
        /// multiple times, the index of the first appearance is used. If the list is empty, -1 is returned.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> or <paramref name="comparison"/> is null.</exception>
        public static int IndexOfMaximum<T>(IList<T> list, Comparison<T> comparison)
        {
            return IndexOfMaximum<T>(list, Comparers.ComparerFromComparison<T>(comparison));
        }

        /// <summary>
        /// Finds the index of the minimum value in a list.
        /// </summary>
        /// <remarks>Values in the list are compared by using the IComparable&lt;T&gt;
        /// interfaces implementation on the type T.</remarks>
        /// <typeparam name="T">The type of items in the list.</typeparam>
        /// <param name="list">The list to search.</param>
        /// <returns>The index of the smallest item in the list. If the minimum value appears
        /// multiple times, the index of the first appearance is used.</returns>
        /// <exception cref="InvalidOperationException">The collection is empty.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
        public static int IndexOfMinimum<T>(IList<T> list)
            where T : IComparable<T>
        {
            return IndexOfMinimum<T>(list, Comparer<T>.Default);
        }

        /// <summary>
        /// Finds the index of the minimum value in a list. A supplied IComparer&lt;T&gt; is used
        /// to compare the items in the collection. 
        /// </summary>
        /// <typeparam name="T">The type of items in the list.</typeparam>
        /// <param name="list">The list to search.</param>
        /// <param name="comparer">The comparer instance used to compare items in the collection.</param>
        /// <returns>The index of the smallest item in the list. If the minimum value appears
        /// multiple times, the index of the first appearance is used.</returns>
        /// <exception cref="InvalidOperationException">The collection is empty.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> or <paramref name="comparer"/> is null.</exception>
        public static int IndexOfMinimum<T>(IList<T> list, IComparer<T> comparer)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            T minSoFar = default(T);
            int indexSoFar = -1;

            // Go through the collection, keeping the minimum found so far.
            int i = 0;
            foreach (T item in list) {
                if (indexSoFar < 0 || comparer.Compare(minSoFar, item) > 0) {
                    minSoFar = item;
                    indexSoFar = i;
                }

                ++i;
            }

            return indexSoFar;
        }

        /// <summary>
        /// Finds the index of the minimum value in a list. A supplied Comparison&lt;T&gt; delegate is used
        /// to compare the items in the collection.
        /// </summary>
        /// <typeparam name="T">The type of items in the list.</typeparam>
        /// <param name="list">The list to search.</param>
        /// <param name="comparison">The comparison delegate used to compare items in the collection.</param>
        /// <returns>The index of the smallest item in the list. If the minimum value appears
        /// multiple times, the index of the first appearance is used.</returns>
        /// <exception cref="InvalidOperationException">The collection is empty.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> or <paramref name="comparison"/> is null.</exception>
        public static int IndexOfMinimum<T>(IList<T> list, Comparison<T> comparison)
        {
            return IndexOfMinimum<T>(list, Comparers.ComparerFromComparison<T>(comparison));
        }

        #endregion Minimum and Maximum

        #region Sorting and operations on sorted collections

        /// <summary>
        /// Creates a sorted version of a collection.
        /// </summary>
        /// <remarks>Values are compared by using the IComparable&lt;T&gt;
        /// interfaces implementation on the type T.</remarks>
        /// <param name="collection">The collection to sort.</param>
        /// <returns>An array containing the sorted version of the collection.</returns>
        public static T[] Sort<T>(IEnumerable<T> collection)
            where T : IComparable<T>
        {
            return Sort<T>(collection, Comparer<T>.Default);
        }

        /// <summary>
        /// Creates a sorted version of a collection. A supplied IComparer&lt;T&gt; is used
        /// to compare the items in the collection. 
        /// </summary>
        /// <param name="collection">The collection to sort.</param>
        /// <param name="comparer">The comparer instance used to compare items in the collection. Only
        /// the Compare method is used.</param>
        /// <returns>An array containing the sorted version of the collection.</returns>
        public static T[] Sort<T>(IEnumerable<T> collection, IComparer<T> comparer)
        {
            T[] array;

            if (collection == null)
                throw new ArgumentNullException("collection");
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            array = Algorithms.ToArray(collection);

            Array.Sort(array, comparer);
            return array;
        }

        /// <summary>
        /// Creates a sorted version of a collection. A supplied Comparison&lt;T&gt; delegate is used
        /// to compare the items in the collection.
        /// </summary>
        /// <param name="collection">The collection to sort.</param>
        /// <param name="comparison">The comparison delegate used to compare items in the collection.</param>
        /// <returns>An array containing the sorted version of the collection.</returns>
        public static T[] Sort<T>(IEnumerable<T> collection, Comparison<T> comparison)
        {
            return Sort<T>(collection, Comparers.ComparerFromComparison<T>(comparison));
        }

        /// <summary>
        /// Sorts a list or array in place.
        /// </summary>
        /// <remarks><para>The Quicksort algorithms is used to sort the items. In virtually all cases,
        /// this takes time O(N log N), where N is the number of items in the list.</para>
        /// <para>Values are compared by using the IComparable&lt;T&gt;
        /// interfaces implementation on the type T.</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 sort.</param>
        public static void SortInPlace<T>(IList<T> list)
            where T : IComparable<T>
        {
            SortInPlace<T>(list, Comparer<T>.Default);
        }

        /// <summary>
        /// Sorts a list or array in place. A supplied IComparer&lt;T&gt; is used
        /// to compare the items in the list. 
        /// </summary>
        /// <remarks><para>The Quicksort algorithms is used to sort the items. In virtually all cases,
        /// this takes time O(N log N), where N is the number of items in the list.</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 sort.</param>
        /// <param name="comparer">The comparer instance used to compare items in the collection. Only
        /// the Compare method is used.</param>
        public static void SortInPlace<T>(IList<T> list, IComparer<T> comparer)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            // If we have an array, use the built-in array sort (faster than going through IList accessors
            // with virtual calls).
            if (list is T[]) {
                Array.Sort((T[])list, comparer);
                return;
            }

            if (list.IsReadOnly)
                throw new ArgumentException(Strings.ListIsReadOnly, "list");

            // Instead of a recursive procedure, we use an explicit stack to hold
            // ranges that we still need to sort.
            int[] leftStack = new int[32], rightStack = new int[32];
            int stackPtr = 0;

            int l = 0;                       // the inclusive left edge of the current range we are sorting.
            int r = list.Count - 1;    // the inclusive right edge of the current range we are sorting.
            T partition;                   // The partition value.

            // Loop until we have nothing left to sort. On each iteration, l and r contains the bounds
            // of something to sort (unless r <= l), and leftStack/rightStack have a stack of unsorted
            // pieces (unles stackPtr == 0).
            for (; ; ) {
                if (l == r - 1) {
                    // We have exactly 2 elements to sort. Compare them and swap if needed.
                    T e1, e2;
                    e1 = list[l];
                    e2 = list[r];
                    if (comparer.Compare(e1, e2) > 0) {
                        list[r] = e1;
                        list[l] = e2;
                    }
                    l = r;     // sort complete, find other work from the stack.
                }
                else if (l < r) {
                    // Sort the items in the inclusive range l .. r

                    // Get the left, middle, and right-most elements and sort them, yielding e1=smallest, e2=median, e3=largest
                    int m = l + (r - l) / 2;
                    T e1 = list[l], e2 = list[m], e3 = list[r], temp;
                    if (comparer.Compare(e1, e2) > 0) { 
                        temp = e1; e1 = e2; e2 = temp; 
                    }
                    if (comparer.Compare(e1, e3) > 0) {
                        temp = e3; e3 = e2; e2 = e1; e1 = temp;
                    }
                    else if (comparer.Compare(e2, e3) > 0) {
                        temp = e2; e2 = e3; e3 = temp; 
                    }

                    if (l == r - 2) {
                        // We have exactly 3 elements to sort, and we've done that. Store back and we're done.
                        list[l] = e1; list[m] = e2; list[r] = e3;
                        l = r;  // sort complete, find other work from the stack.
                    }
                    else {
                        // Put the smallest at the left, largest in the middle, and the median at the right (which is the partitioning value)
                        list[l] = e1;
                        list[m] = e3;
                        list[r] = partition = e2;

                        // Partition into three parts, items <= partition, items == partition, and items >= partition
                        int i = l, j = r;
                        T item_i, item_j;
                        for (; ; ) {
                            do {
                                ++i;
                                item_i = list[i];
                            } while (comparer.Compare(item_i, partition) < 0);

                            do {
                                --j;
                                item_j = list[j];
                            } while (comparer.Compare(item_j, partition) > 0);

                            if (j < i)
                                break;

                            list[i] = item_j; list[j] = item_i; // swap items to continue the partition.
                        }

                        // Move the partition value into place.
                        list[r] = item_i;
                        list[i] = partition;
                        ++i;

                        // We have partitioned the list. 
                        //    Items in the inclusive range l .. j are <= partition.
                        //    Items in the inclusive range i .. r are >= partition.
                        //    Items in the inclusive range j+1 .. i - 1 are == partition (and in the correct final position).
                        // We now need to sort l .. j and i .. r.
                        // To do this, we stack one of the lists for later processing, and change l and r to the other list.
                        // If we always stack the larger of the two sub-parts, the stack cannot get greater
                        // than log2(Count) in size; i.e., a 32-element stack is enough for the maximum list size.
                        if ((j - l) > (r - i)) {
                            // The right partition is smaller. Stack the left, and get ready to sort the right.
                            leftStack[stackPtr] = l;
                            rightStack[stackPtr] = j;
                            l = i;
                        }
                        else {
                            // The left partition is smaller. Stack the right, and get ready to sort the left.
                            leftStack[stackPtr] = i;
                            rightStack[stackPtr] = r;
                            r = j;
                        }
                        ++stackPtr;
                    }
                }
               else if (stackPtr > 0) {
                    // We have a stacked sub-list to sort. Pop it off and sort it.
                    --stackPtr;
                    l = leftStack[stackPtr];
                    r = rightStack[stackPtr];
                }
                else {
                    // We have nothing left to sort.
                    break;
                }
            }
        }

        /// <summary>
        /// Sorts a list or array in place. A supplied Comparison&lt;T&gt; delegate is used
        /// to compare the items in the list.
        /// </summary>
        /// <remarks><para>The Quicksort algorithms is used to sort the items. In virtually all cases,
        /// this takes time O(N log N), where N is the number of items in the list.</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 sort.</param>
        /// <param name="comparison">The comparison delegate used to compare items in the collection.</param>
        public static void SortInPlace<T>(IList<T> list, Comparison<T> comparison)
        {
            SortInPlace<T>(list, Comparers.ComparerFromComparison<T>(comparison));
        }

        /// <summary>
        /// Creates a sorted version of a collection. The sort is stable, which means that if items X and Y are equal,
        /// and X precedes Y in the unsorted collection, X will precede Y is the sorted collection.
        /// </summary>
        /// <remarks>Values are compared by using the IComparable&lt;T&gt;
        /// interfaces implementation on the type T.</remarks>
        /// <param name="collection">The collection to sort.</param>
        /// <returns>An array containing the sorted version of the collection.</returns>
        public static T[] StableSort<T>(IEnumerable<T> collection)
            where T : IComparable<T>
        {
            return StableSort(collection, Comparer<T>.Default);
        }

        /// <summary>
        /// Creates a sorted version of a collection. The sort is stable, which means that if items X and Y are equal,
        /// and X precedes Y in the unsorted collection, X will precede Y is the sorted collection. A supplied IComparer&lt;T&gt; is used
        /// to compare the items in the collection. 
        /// </summary>
        /// <param name="collection">The collection to sort.</param>
        /// <param name="comparer">The comparer instance used to compare items in the collection. Only
        /// the Compare method is used.</param>
        /// <returns>An array containing the sorted version of the collection.</returns>
        public static T[] StableSort<T>(IEnumerable<T> collection, IComparer<T> comparer)
        {
            T[] array;

            if (collection == null)
                throw new ArgumentNullException("collection");
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            array = Algorithms.ToArray(collection);

            StableSortInPlace<T>(Algorithms.ReadWriteList<T>(array), comparer);
            return array;
        }

        /// <summary>
        /// Creates a sorted version of a collection. The sort is stable, which means that if items X and Y are equal,
        /// and X precedes Y in the unsorted collection, X will precede Y is the sorted collection. 
        /// A supplied Comparison&lt;T&gt; delegate is used
        /// to compare the items in the collection.
        /// </summary>
        /// <remarks>Values are compared by using the IComparable&lt;T&gt;
        /// interfaces implementation on the type T.</remarks>
        /// <param name="collection">The collection to sort.</param>
        /// <param name="comparison">The comparison delegate used to compare items in the collection.</param>
        /// <returns>An array containing the sorted version of the collection.</returns>
        public static T[] StableSort<T>(IEnumerable<T> collection, Comparison<T> comparison)
        {
            return StableSort<T>(collection, Comparers.ComparerFromComparison<T>(comparison));
        }

        /// <summary>
        /// Sorts a list or array in place. The sort is stable, which means that if items X and Y are equal,
        /// and X precedes Y in the unsorted collection, X will precede Y is the sorted collection. 
        /// </summary>
        /// <remarks><para>Values are compared by using the IComparable&lt;T&gt;
        /// interfaces implementation on the type T.</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 sort.</param>
        public static void StableSortInPlace<T>(IList<T> list)
            where T : IComparable<T>
        {
            StableSortInPlace<T>(list, Comparer<T>.Default);
        }

        /// <summary>
        /// Sorts a list or array in place. The sort is stable, which means that if items X and Y are equal,
        /// and X precedes Y in the unsorted collection, X will precede Y is the sorted collection. 
        /// A supplied IComparer&lt;T&gt; is used
        /// to compare the items in 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 sort.</param>
        /// <param name="comparer">The comparer instance used to compare items in the collection. Only
        /// the Compare method is used.</param>
        public static void StableSortInPlace<T>(IList<T> list, IComparer<T> comparer)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (comparer == null)
                throw new ArgumentNullException("comparer");
            if (list is T[])
                list = new ArrayWrapper<T>((T[])list);
            if (list.IsReadOnly)
                throw new ArgumentException(Strings.ListIsReadOnly, "list");

            // The stable sort algorithms also uses QuickSort. An additional array of indices (order) is
            // used to maintain the original order of items in the array, and that array is used
            // as a secondary compare when the primary compare returns equal.
            int[] order = new int[list.Count];
            for (int x = 0; x < order.Length; ++x)
                order[x] = x;

            // Instead of a recursive procedure, we use an explicit stack to hold
            // ranges that we still need to sort.
            int[] leftStack = new int[32], rightStack = new int[32];
            int stackPtr = 0;

            int l = 0;                       // the inclusive left edge of the current range we are sorting.
            int r = list.Count - 1;    // the inclusive right edge of the current range we are sorting.
            T partition;                   // The partition value.
            int order_partition;      // The order of the partition value;
            int c;                            // holds the result of a comparison temporarily.

            // Loop until we have nothing left to sort. On each iteration, l and r contains the bounds
            // of something to sort (unless r <= l), and leftStack/rightStack have a stack of unsorted
            // pieces (unles stackPtr == 0).
            for (; ; ) {
                if (l == r - 1) {
                    // We have exactly 2 elements to sort. Compare them and swap if needed.
                    T e1, e2;
                    int o1, o2;
                    e1 = list[l]; o1 = order[l];
                    e2 = list[r]; o2 = order[r];
                    if ((c = comparer.Compare(e1, e2)) > 0 || (c == 0 && o1 > o2)) {
                        list[r] = e1; order[r] = o1;
                        list[l] = e2; order[l] = o2;
                    }
                    l = r;     // sort complete, find other work from the stack.
                }
                else if (l < r) {
                    // Sort the items in the inclusive range l .. r

                    // Get the left, middle, and right-most elements and sort them, yielding e1=smallest, e2=median, e3=largest
                    int m = l + (r - l) / 2;
                    T e1 = list[l], e2 = list[m], e3 = list[r], temp;
                    int o1 = order[l], o2 = order[m], o3 = order[r], otemp;
                    if ((c = comparer.Compare(e1, e2)) > 0 || (c == 0 && o1 > o2)) {
                        temp = e1; e1 = e2; e2 = temp;
                        otemp = o1; o1 = o2; o2 = otemp;
                    }
                    if ((c = comparer.Compare(e1, e3)) > 0 || (c == 0 && o1 > o3)) {
                        temp = e3; e3 = e2; e2 = e1; e1 = temp;
                        otemp = o3; o3 = o2; o2 = o1; o1 = otemp;
                    }
                    else if ((c = comparer.Compare(e2, e3)) > 0 || (c == 0 && o2 > o3)) {
                        temp = e2; e2 = e3; e3 = temp;
                        otemp = o2; o2 = o3; o3 = otemp;
                    }

                    if (l == r - 2) {
                        // We have exactly 3 elements to sort, and we've done that. Store back and we're done.
                        list[l] = e1; list[m] = e2; list[r] = e3;
                        order[l] = o1; order[m] = o2; order[r] = o3;
                        l = r;  // sort complete, find other work from the stack.
                    }
                    else {
                        // Put the smallest at the left, largest in the middle, and the median at the right (which is the partitioning value)
                        list[l] = e1; order[l] = o1;
                        list[m] = e3; order[m] = o3;
                        list[r] = partition = e2; order[r] = order_partition = o2;

                        // Partition into three parts, items <= partition, items == partition, and items >= partition
                        int i = l, j = r;
                        T item_i, item_j;
                        int order_i, order_j;
                        for (; ; ) {
                            do {
                                ++i;
                                item_i = list[i]; order_i = order[i];
                            } while ((c = comparer.Compare(item_i, partition)) < 0 || (c == 0 && order_i < order_partition));

                            do {
                                --j;
                                item_j = list[j]; order_j = order[j];
                            } while ((c = comparer.Compare(item_j, partition)) > 0 || (c == 0 && order_j > order_partition));

                            if (j < i)
                                break;

                            list[i] = item_j; list[j] = item_i; // swap items to continue the partition.
                            order[i] = order_j; order[j] = order_i;
                        }

                        // Move the partition value into place.
                        list[r] = item_i; order[r] = order_i;
                        list[i] = partition; order[i] = order_partition;
                        ++i;

                        // We have partitioned the list. 
                        //    Items in the inclusive range l .. j are <= partition.
                        //    Items in the inclusive range i .. r are >= partition.
                        //    Items in the inclusive range j+1 .. i - 1 are == partition (and in the correct final position).
                        // We now need to sort l .. j and i .. r.
                        // To do this, we stack one of the lists for later processing, and change l and r to the other list.
                        // If we always stack the larger of the two sub-parts, the stack cannot get greater
                        // than log2(Count) in size; i.e., a 32-element stack is enough for the maximum list size.
                        if ((j - l) > (r - i)) {
                            // The right partition is smaller. Stack the left, and get ready to sort the right.
                            leftStack[stackPtr] = l;
                            rightStack[stackPtr] = j;
                            l = i;
                        }
                        else {
                            // The left partition is smaller. Stack the right, and get ready to sort the left.
                            leftStack[stackPtr] = i;
                            rightStack[stackPtr] = r;
                            r = j;
                        }
                        ++stackPtr;
                    }
                }
                else if (stackPtr > 0) {
                    // We have a stacked sub-list to sort. Pop it off and sort it.
                    --stackPtr;
                    l = leftStack[stackPtr];
                    r = rightStack[stackPtr];
                }
                else {
                    // We have nothing left to sort.
                    break;
                }
            }
        }

        /// <summary>
        /// Sorts a list or array in place. The sort is stable, which means that if items X and Y are equal,
        /// and X precedes Y in the unsorted collection, X will precede Y is the sorted collection. 
        /// A supplied Comparison&lt;T&gt; delegate is used
        /// to compare the items in 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 sort.</param>
        /// <param name="comparison">The comparison delegate used to compare items in the collection.</param>
        public static void StableSortInPlace<T>(IList<T> list, Comparison<T> comparison)
        {
            StableSortInPlace<T>(list, Comparers.ComparerFromComparison<T>(comparison));
        }

        /// <summary>
        /// Searches a sorted list for an item via binary search. The list must be sorted
        /// by the natural ordering of the type (it's implementation of IComparable&lt;T&gt;).
        /// </summary>
        /// <param name="list">The sorted list to search.</param>
        /// <param name="item">The item to search for.</param>
        /// <param name="index">Returns the first index at which the item can be found. If the return
        /// value is zero, indicating that <paramref name="item"/> was not present in the list, then this
        /// returns the index at which <paramref name="item"/> could be inserted to maintain the sorted
        /// order of the list.</param>
        /// <returns>The number of items equal to <paramref name="item"/> that appear in the list.</returns>
        public static int BinarySearch<T>(IList<T> list, T item, out int index)
            where T: IComparable<T>
        {
            return BinarySearch<T>(list, item, Comparer<T>.Default, out index);
        }

        /// <summary>
        /// Searches a sorted list for an item via binary search. The list must be sorted
        /// by the ordering in the passed instance of IComparer&lt;T&gt;.
        /// </summary>
        /// <param name="list">The sorted list to search.</param>
        /// <param name="item">The item to search for.</param>
        /// <param name="comparer">The comparer instance used to sort the list. Only
        /// the Compare method is used.</param>
        /// <param name="index">Returns the first index at which the item can be found. If the return
        /// value is zero, indicating that <paramref name="item"/> was not present in the list, then this
        /// returns the index at which <paramref name="item"/> could be inserted to maintain the sorted
        /// order of the list.</param>
        /// <returns>The number of items equal to <paramref name="item"/> that appear in the list.</returns>
        public static int BinarySearch<T>(IList<T> list, T item, IComparer<T> comparer, out int index)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            int l = 0;
            int r = list.Count;

            while (r > l) {
                int m = l + (r - l) / 2;
                T middleItem = list[m];
                int comp = comparer.Compare(middleItem, item);
                if (comp < 0) {
                    // middleItem < item
                    l = m + 1;
                }
                else if (comp > 0) {
                    r = m;
                }
                else {
                    // Found something equal to item at m. Now we need to find the start and end of this run of equal items.
                    int lFound = l, rFound = r, found = m;

                    // Find the start of the run.
                    l = lFound;
                    r = found;
                    while (r > l) {
                        m = l + (r - l) / 2;
                        middleItem = list[m];
                        comp = comparer.Compare(middleItem, item);
                        if (comp < 0) {
                            // middleItem < item
                            l = m + 1;
                        }
                        else {
                            r = m;
                        }
                    }
                    System.Diagnostics.Debug.Assert(l == r);
                    index = l;

                    // Find the end of the run.
                    l = found;
                    r = rFound;
                    while (r > l) {
                        m = l + (r - l) / 2;
                        middleItem = list[m];
                        comp = comparer.Compare(middleItem, item);
                        if (comp <= 0) {
                            // middleItem <= item
                            l = m + 1;
                        }
                        else {
                            r = m;
                        }
                    }
                    System.Diagnostics.Debug.Assert(l == r);
                    return l - index;
                }
            }

            // We did not find the item. l and r must be equal. 
            System.Diagnostics.Debug.Assert(l == r);
            index = l;
            return 0;
        }

        /// <summary>
        /// Searches a sorted list for an item via binary search. The list must be sorted
        /// by the ordering in the passed Comparison&lt;T&gt; delegate.
        /// </summary>
        /// <param name="list">The sorted list to search.</param>
        /// <param name="item">The item to search for.</param>
        /// <param name="comparison">The comparison delegate used to sort the list.</param>
        /// <param name="index">Returns the first index at which the item can be found. If the return
        /// value is zero, indicating that <paramref name="item"/> was not present in the list, then this
        /// returns the index at which <paramref name="item"/> could be inserted to maintain the sorted
        /// order of the list.</param>
        /// <returns>The number of items equal to <paramref name="item"/> that appear in the list.</returns>
        public static int BinarySearch<T>(IList<T> list, T item, Comparison<T> comparison, out int index)
        {
            return BinarySearch<T>(list, item, Comparers.ComparerFromComparison<T>(comparison), out index);
        }

        /// <summary>
        /// Merge several sorted collections into a single sorted collection. Each input collection must be sorted
        /// by the natural ordering of the type (it's implementation of IComparable&lt;T&gt;). The merging
        /// is stable; equal items maintain their ordering, and equal items in different collections are placed
        /// in the order of the collections.
        /// </summary>
        /// <param name="collections">The set of collections to merge. In many languages, this parameter
        /// can be specified as several individual parameters.</param>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates all the items in all the collections
        /// in sorted order. </returns>
        public static IEnumerable<T> MergeSorted<T>(params IEnumerable<T>[] collections)
            where T : IComparable<T>
        {
            return MergeSorted<T>(Comparer<T>.Default, collections);
        }

        /// <summary>
        /// Merge several sorted collections into a single sorted collection. Each input collection must be sorted
        /// by the ordering in the passed instance of IComparer&lt;T&gt;. The merging
        /// is stable; equal items maintain their ordering, and equal items in different collections are placed
        /// in the order of the collections.
        /// </summary>
        /// <param name="collections">The set of collections to merge. In many languages, this parameter
        /// can be specified as several individual parameters.</param>
        /// <param name="comparer">The comparer instance used to sort the list. Only
        /// the Compare method is used.</param>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates all the items in all the collections
        /// in sorted order. </returns>
        public static IEnumerable<T> MergeSorted<T>(IComparer<T> comparer, params IEnumerable<T>[] collections)
        {
            if (collections == null)
                throw new ArgumentNullException("collections");
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            IEnumerator<T>[] enumerators = new IEnumerator<T>[collections.Length];
            bool[] more = new bool[collections.Length];
            T smallestItem = default(T);
            int smallestItemIndex;

            try {
                // Get enumerators from each collection, and advance to the first element.
                for (int i = 0; i < collections.Length; ++i) {
                    if (collections[i] != null) {
                        enumerators[i] = collections[i].GetEnumerator();
                        more[i] = enumerators[i].MoveNext();
                    }
                }

                for (; ; ) {
                    // Find the smallest item, and which collection it is in.
                    smallestItemIndex = -1;      // -1 indicates no smallest yet.
                    for (int i = 0; i < enumerators.Length; ++i) {
                        if (more[i]) {
                            T item = enumerators[i].Current;
                            if (smallestItemIndex < 0 || comparer.Compare(smallestItem, item) > 0) {
                                smallestItemIndex = i;
                                smallestItem = item;
                            }
                        }
                    }

                    // If no smallest item found, we're done.
                    if (smallestItemIndex == -1)
                        yield break;

                    // Yield the smallest item.
                    yield return smallestItem;

                    // Advance the enumerator it came from.
                    more[smallestItemIndex] = enumerators[smallestItemIndex].MoveNext();
                }
            }
            finally {
                // Dispose all enumerators.
                foreach (IEnumerator<T> e in enumerators) {
                    if (e != null)
                        e.Dispose();
                }
            }
        }

        /// <summary>
        /// Merge several sorted collections into a single sorted collection. Each input collection must be sorted
        /// by the ordering in the passed Comparison&lt;T&gt; delegate. The merging
        /// is stable; equal items maintain their ordering, and equal items in different collections are placed
        /// in the order of the collections.
        /// </summary>
        /// <param name="collections">The set of collections to merge. In many languages, this parameter
        /// can be specified as several individual parameters.</param>
        /// <param name="comparison">The comparison delegate used to sort the collections.</param>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates all the items in all the collections
        /// in sorted order. </returns>
        public static IEnumerable<T> MergeSorted<T>(Comparison<T> comparison, params IEnumerable<T>[] collections)
        {
            return MergeSorted<T>(Comparers.ComparerFromComparison<T>(comparison), collections);
        }


        /// <summary>
        /// Performs a lexicographical comparison of two sequences of values. A lexicographical comparison compares corresponding
        /// pairs of elements from two sequences in order. If the first element of sequence1 is less than the first element of sequence2, 
        /// then the comparison ends and the first sequence is lexicographically less than the second. If the first elements of each sequence
        /// are equal, then the comparison proceeds to the second element of each sequence. If one sequence is shorter than the other,
        /// but corresponding elements are all equal, then the shorter sequence is considered less than the longer one.
        /// </summary>
        /// <remarks>T must implement either IComparable&lt;T&gt; and this implementation is used
        /// to compare the items. </remarks>
        /// <typeparam name="T">Types of items to compare. This type must implement IComparable&lt;T&gt; to allow 
        /// items to be compared.</typeparam>
        /// <param name="sequence1">The first sequence to compare.</param>
        /// <param name="sequence2">The second sequence to compare.</param>
        /// <returns>Less than zero if <paramref name="sequence1"/> is lexicographically less than <paramref name="sequence2"/>.
        /// Greater than zero if <paramref name="sequence1"/> is lexicographically greater than <paramref name="sequence2"/>.
        /// Zero if <paramref name="sequence1"/> is equal to <paramref name="sequence2"/>.</returns>
        /// <exception cref="NotSupportedException">T does not implement IComparable&lt;T&gt; or IComparable.</exception>
        public static int LexicographicalCompare<T>(IEnumerable<T> sequence1, IEnumerable<T> sequence2)
            where T : IComparable<T>
        {
            return LexicographicalCompare<T>(sequence1, sequence2, Comparer<T>.Default);
        }

        /// <summary>
        /// Performs a lexicographical comparison of two sequences of values, using a supplied comparison delegate. A lexicographical comparison compares corresponding
        /// pairs of elements from two sequences in order. If the first element of sequence1 is less than the first element of sequence2, 
        /// then the comparison ends and the first sequence is lexicographically less than the second. If the first elements of each sequence
        /// are equal, then the comparison proceeds to the second element of each sequence. If one sequence is shorter than the other,
        /// but corresponding elements are all equal, then the shorter sequence is considered less than the longer one.
        /// </summary>
        /// <typeparam name="T">Types of items to compare.</typeparam>
        /// <param name="sequence1">The first sequence to compare.</param>
        /// <param name="sequence2">The second sequence to compare.</param>
        /// <param name="comparison">The IComparison&lt;T&gt; delegate to compare items. 
        /// Only the Compare member function of this interface is called.</param>
        /// <returns>Less than zero if <paramref name="sequence1"/> is lexicographically less than <paramref name="sequence2"/>.
        /// Greater than zero if <paramref name="sequence1"/> is lexicographically greater than <paramref name="sequence2"/>.
        /// Zero if <paramref name="sequence1"/> is equal to <paramref name="sequence2"/>.</returns>
        public static int LexicographicalCompare<T>(IEnumerable<T> sequence1, IEnumerable<T> sequence2, Comparison<T> comparison)
        {
            return LexicographicalCompare<T>(sequence1, sequence2, Comparers.ComparerFromComparison(comparison));
        }

        /// <summary>
        /// Performs a lexicographical comparison of two sequences of values, using a supplied comparer interface. A lexicographical comparison compares corresponding
        /// pairs of elements from two sequences in order. If the first element of sequence1 is less than the first element of sequence2, 
        /// then the comparison ends and the first sequence is lexicographically less than the second. If the first elements of each sequence
        /// are equal, then the comparison proceeds to the second element of each sequence. If one sequence is shorter than the other,
        /// but corresponding elements are all equal, then the shorter sequence is considered less than the longer one.
        /// </summary>
        /// <typeparam name="T">Types of items to compare.</typeparam>
        /// <param name="sequence1">The first sequence to compare.</param>
        /// <param name="sequence2">The second sequence to compare.</param>
        /// <param name="comparer">The IComparer&lt;T&gt; used to compare items. 
        /// Only the Compare member function of this interface is called.</param>
        /// <returns>Less than zero if <paramref name="sequence1"/> is lexicographically less than <paramref name="sequence2"/>.
        /// Greater than zero if <paramref name="sequence1"/> is lexicographically greater than <paramref name="sequence2"/>.
        /// Zero if <paramref name="sequence1"/> is equal to <paramref name="sequence2"/>.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="sequence1"/>, <paramref name="sequence2"/>, or 
        /// <paramref name="comparer"/> is null.</exception>
        public static int LexicographicalCompare<T>(IEnumerable<T> sequence1, IEnumerable<T> sequence2, IComparer<T> comparer)
        {
            if (sequence1 == null)
                throw new ArgumentNullException("sequence1");
            if (sequence2 == null)
                throw new ArgumentNullException("sequence2");
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            using (IEnumerator<T> enum1 = sequence1.GetEnumerator(), enum2 = sequence2.GetEnumerator()) {
                bool continue1, continue2;

                for (; ; ) {
                    continue1 = enum1.MoveNext(); continue2 = enum2.MoveNext();
                    if (!continue1 || !continue2)
                        break;

                    int compare = comparer.Compare(enum1.Current, enum2.Current);
                    if (compare != 0)
                        return compare;
                }

                // If both continue1 and continue2 are false, we reached the end of both sequences at the same
                // time and the sequences are equal. Otherwise, the shorter sequence is considered first.
                if (continue1 == continue2)
                    return 0;
                else if (continue1)
                    return 1;
                else
                    return -1;
            }
        }

        #endregion Sorting

        #region Comparers/Comparison utilities 

        /// <summary>
        /// A private class used by the LexicographicalComparer method to compare sequences
        /// (IEnumerable) of T by there Lexicographical ordering.
        /// </summary>
        [Serializable]
        private class LexicographicalComparerClass<T> : IComparer<IEnumerable<T>>
        {
            IComparer<T> itemComparer;

            /// <summary>
            /// Creates a new instance that comparer sequences of T by their lexicographical
            /// ordered.
            /// </summary>
            /// <param name="itemComparer">The IComparer used to compare individual items of type T.</param>
            public LexicographicalComparerClass(IComparer<T> itemComparer)
            {
                this.itemComparer = itemComparer;
            }

            public int Compare(IEnumerable<T> x, IEnumerable<T> y)
            {
                return LexicographicalCompare<T>(x, y, itemComparer);
            }


            // For comparing this comparer to others.

            public override bool Equals(object obj)
            {
                if (obj is LexicographicalComparerClass<T>)
                    return this.itemComparer.Equals(((LexicographicalComparerClass<T>)obj).itemComparer);
                else
                    return false;
            }

            public override int GetHashCode()
            {
                return itemComparer.GetHashCode();
            }
        }

        /// <summary>
        /// Creates an IComparer instance that can be used for comparing ordered
        /// sequences of type T; that is IEnumerable&lt;Tgt;. This comparer can be used
        /// for collections or algorithms that use sequences of T as an item type. The Lexicographical
        /// ordered of sequences is for comparison.
        /// </summary>
        /// <remarks>T must implement either IComparable&lt;T&gt; and this implementation is used
        /// to compare the items. </remarks>
        /// <returns>At IComparer&lt;IEnumerable&lt;T&gt;&gt; that compares sequences of T.</returns>
        public static IComparer<IEnumerable<T>> GetLexicographicalComparer<T>()
            where T: IComparable<T>
        {
            return GetLexicographicalComparer<T>(Comparer<T>.Default);
        }

        /// <summary>
        /// Creates an IComparer instance that can be used for comparing ordered
        /// sequences of type T; that is IEnumerable&lt;Tgt;. This comparer can be uses
        /// for collections or algorithms that use sequences of T as an item type. The Lexicographics
        /// ordered of sequences is for comparison.
        /// </summary>
        /// <param name="comparer">A comparer instance used to compare individual items of type T.</param>
        /// <returns>At IComparer&lt;IEnumerable&lt;T&gt;&gt; that compares sequences of T.</returns>
        public static IComparer<IEnumerable<T>> GetLexicographicalComparer<T>(IComparer<T> comparer)
        {
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            return new LexicographicalComparerClass<T>(comparer);
        }

        /// <summary>
        /// Creates an IComparer instance that can be used for comparing ordered
        /// sequences of type T; that is IEnumerable&lt;Tgt;. This comparer can be uses
        /// for collections or algorithms that use sequences of T as an item type. The Lexicographics
        /// ordered of sequences is for comparison.
        /// </summary>
        /// <param name="comparison">A comparison delegate used to compare individual items of type T.</param>
        /// <returns>At IComparer&lt;IEnumerable&lt;T&gt;&gt; that compares sequences of T.</returns>
        public static IComparer<IEnumerable<T>> GetLexicographicalComparer<T>(Comparison<T> comparison)
        {
            if (comparison == null)
                throw new ArgumentNullException("comparison");

            return new LexicographicalComparerClass<T>(Comparers.ComparerFromComparison(comparison));
        }

        /// <summary>
        /// An IComparer instance that can be used to reverse the sense of 
        /// a wrapped IComparer instance.
        /// </summary>
        [Serializable]
        private class ReverseComparerClass<T> : IComparer<T>
        {
            IComparer<T> comparer;

            /// <summary>
            /// </summary>
            /// <param name="comparer">The comparer to reverse.</param>
            public ReverseComparerClass(IComparer<T> comparer)
            {
                this.comparer = comparer;
            }

            public int Compare(T x, T y)
            {
                return - comparer.Compare(x, y);
            }

            // For comparing this comparer to others.

            public override bool Equals(object obj)
            {
                if (obj is ReverseComparerClass<T>)
                    return this.comparer.Equals(((ReverseComparerClass<T>)obj).comparer);
                else
                    return false;
            }

            public override int GetHashCode()
            {
                return comparer.GetHashCode();
            }
        }

        /// <summary>
        /// Reverses the order of comparison of an IComparer&lt;T&gt;. The resulting comparer can be used,
        /// for example, to sort a collection in descending order. Equality and hash codes are unchanged.
        /// </summary>
        /// <typeparam name="T">The type of items thta are being compared.</typeparam>
        /// <param name="comparer">The comparer to reverse.</param>
        /// <returns>An IComparer&lt;T&gt; that compares items in the reverse order of <paramref name="comparer"/>.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="comparer"/> is null.</exception>
        public static IComparer<T> GetReverseComparer<T>(IComparer<T> comparer)
        {
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            return new ReverseComparerClass<T>(comparer);
        }

        /// <summary>
        /// A class, implementing IEqualityComparer&lt;T&gt;, that compares objects
        /// for object identity only. Only Equals and GetHashCode can be used;
        /// this implementation is not appropriate for ordering.
        /// </summary>
        [Serializable]
        private class IdentityComparer<T> : IEqualityComparer<T>
            where T:class
        {
            public bool Equals(T x, T y)
            {
                return ((object)x == (object)y);
            }

            public int GetHashCode(T obj)
            {
                return System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(obj);
            }

            // For comparing two IComparers to see if they compare the same thing.
            public override bool Equals(object obj)
            {
                return (obj != null && obj is IdentityComparer<T>);
            }

            // For comparing two IComparers to see if they compare the same thing.
            public override int GetHashCode()
            {
                return 0x7143DDEF;
            }
        }

        /// <summary>
        /// Gets an IEqualityComparer&lt;T&gt; instance that can be used to compare objects
        /// of type T for object identity only. Two objects compare equal only if they
        /// are references to the same object. 
        /// </summary>
        /// <returns>An IEqualityComparer&lt;T&gt; instance for identity comparison.</returns>
        public static IEqualityComparer<T> GetIdentityComparer<T>()
            where T : class
        {
            return new IdentityComparer<T>();
        }

        /// <summary>
        /// Reverses the order of comparison of an Comparison&lt;T&gt;. The resulting comparison can be used,
        /// for example, to sort a collection in descending order. 
        /// </summary>
        /// <typeparam name="T">The type of items that are being compared.</typeparam>
        /// <param name="comparison">The comparison to reverse.</param>
        /// <returns>A Comparison&lt;T&gt; that compares items in the reverse order of <paramref name="comparison"/>.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="comparison"/> is null.</exception>
        public static Comparison<T> GetReverseComparison<T>(Comparison<T> comparison)
        {
            if (comparison == null)
                throw new ArgumentNullException("comparison");

            return delegate(T x, T y) { return -comparison(x, y); };
        }

        /// <summary>
        /// Given a comparison delegate that compares two items of type T, gets an
        /// IComparer&lt;T&gt; instance that performs the same comparison.
        /// </summary>
        /// <param name="comparison">The comparison delegate to use.</param>
        /// <returns>An IComparer&lt;T&gt; that performs the same comparing operation
        /// as <paramref name="comparison"/>.</returns>
        public static IComparer<T> GetComparerFromComparison<T>(Comparison<T> comparison)
        {
            if (comparison == null)
                throw new ArgumentNullException("comparison");

            return Comparers.ComparerFromComparison<T>(comparison);
        }

        /// <summary>
        /// Given in IComparer&lt;T&gt; instenace that comparers two items from type T, 
        /// gets a Comparison delegate that performs the same comparison.
        /// </summary>
        /// <param name="comparer">The IComparer&lt;T&gt; instance to use.</param>
        /// <returns>A Comparison&lt;T&gt; delegate that performans the same comparing
        /// operation as <paramref name="comparer"/>.</returns>
        public static Comparison<T> GetComparisonFromComparer<T>(IComparer<T> comparer)
        {
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            return comparer.Compare;
        }

        /// <summary>
        /// A private class used to implement GetCollectionEqualityComparer(). This
        /// class implements IEqualityComparer&lt;IEnumerable&lt;T&gt;gt; to compare
        /// two enumerables for equality, where order is significant.
        /// </summary>
        [Serializable]
        private class CollectionEqualityComparer<T> : IEqualityComparer<IEnumerable<T>>
        {
            private IEqualityComparer<T> equalityComparer;

            public CollectionEqualityComparer(IEqualityComparer<T> equalityComparer)
            {
                this.equalityComparer = equalityComparer;
            }

            public bool Equals(IEnumerable<T> x, IEnumerable<T> y)
            {
                return Algorithms.EqualCollections<T>(x, y, equalityComparer);
            }

            public int GetHashCode(IEnumerable<T> obj)
            {
                int hash = 0x374F293E;
                foreach (T t in obj) {
                    int itemHash = Util.GetHashCode(t, equalityComparer);
                    hash += itemHash;
                    hash = (hash << 9) | (hash >> 23);
                }

                return hash & 0x7FFFFFFF;
            }
        }

        /// <summary>
        /// Gets an IEqualityComparer&lt;IEnumerable&lt;T&gt;&gt; implementation 
        /// that can be used to compare collections of elements (of type T). Two collections
        /// of T's are equal if they have the same number of items, and corresponding 
        /// items are equal, considered in order. This is the same notion of equality as
        /// in Algorithms.EqualCollections, but encapsulated in an IEqualityComparer&lt;IEnumerable&lt;T&gt;&gt; implementation.
        /// </summary>
        /// <example>
        /// The following code creates a Dictionary where the keys are a collection of strings.
        /// <code>
        ///     Dictionary&lt;IEnumerable&lt;string&gt;, int&gt; = 
        ///         new Dictionary&lt;IEnumerable&lt;string&gt;, int&gt;(Algorithms.GetCollectionEqualityComparer&lt;string&gt;());
        /// </code>
        /// </example>
        /// <returns>IEqualityComparer&lt;IEnumerable&lt;T&gt;&gt; implementation suitable for 
        /// comparing collections of T for equality.</returns>
        /// <seealso cref="Algorithms.EqualCollections"/>
        public static IEqualityComparer<IEnumerable<T>> GetCollectionEqualityComparer<T>()
        {
            return GetCollectionEqualityComparer(EqualityComparer<T>.Default);
        }

        /// <summary>
        /// <para>Gets an IEqualityComparer&lt;IEnumerable&lt;T&gt;&gt; implementation 
        /// that can be used to compare collections of elements (of type T). Two collections
        /// of T's are equal if they have the same number of items, and corresponding 
        /// items are equal, considered in order. This is the same notion of equality as
        /// in Algorithms.EqualCollections, but encapsulated in an IEqualityComparer&lt;IEnumerable&lt;T&gt;&gt; implementation.</para>
        /// <para>An IEqualityComparer&lt;T&gt; is used to determine if individual T's are equal</para>
        /// </summary>
        /// <example>
        /// The following code creates a Dictionary where the keys are a collection of strings, compared in a case-insensitive way
        /// <code>
        ///     Dictionary&lt;IEnumerable&lt;string&gt;, int&gt; = 
        ///         new Dictionary&lt;IEnumerable&lt;string&gt;, int&gt;(Algorithms.GetCollectionEqualityComparer&lt;string&gt;(StringComparer.CurrentCultureIgnoreCase));
        /// </code>
        /// </example>
        /// <param name="equalityComparer">An IEqualityComparer&lt;T&gt; implementation used to compare individual T's.</param>
        /// <returns>IEqualityComparer&lt;IEnumerable&lt;T&gt;&gt; implementation suitable for 
        /// comparing collections of T for equality.</returns>
        /// <seealso cref="Algorithms.EqualCollections"/>
        public static IEqualityComparer<IEnumerable<T>> GetCollectionEqualityComparer<T>(IEqualityComparer<T> equalityComparer)
        {
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            return new CollectionEqualityComparer<T>(equalityComparer);
        }

        /// <summary>
        /// A private class used to implement GetSetEqualityComparer(). This
        /// class implements IEqualityComparer&lt;IEnumerable&lt;T&gt;gt; to compare
        /// two enumerables for equality, where order is not significant.
        /// </summary>
        [Serializable]
        private class SetEqualityComparer<T> : IEqualityComparer<IEnumerable<T>>
        {
            private IEqualityComparer<T> equalityComparer;

            public SetEqualityComparer(IEqualityComparer<T> equalityComparer)
            {
                this.equalityComparer = equalityComparer;
            }

            public bool Equals(IEnumerable<T> x, IEnumerable<T> y)
            {
                return Algorithms.EqualSets<T>(x, y, equalityComparer);
            }

            public int GetHashCode(IEnumerable<T> obj)
            {
                int hash = 0x624F273C;
                foreach (T t in obj) {
                    int itemHash = Util.GetHashCode(t, equalityComparer);
                    hash += itemHash;
                }

                return hash & 0x7FFFFFFF;
            }
        }

        /// <summary>
        /// <para>Gets an IEqualityComparer&lt;IEnumerable&lt;T&gt;&gt; implementation 
        /// that can be used to compare collections of elements (of type T). Two collections
        /// of T's are equal if they have the same number of items, and corresponding 
        /// items are equal, without regard to order. This is the same notion of equality as
        /// in Algorithms.EqualSets, but encapsulated in an IEqualityComparer&lt;IEnumerable&lt;T&gt;&gt; implementation.</para>
        /// <para>An IEqualityComparer&lt;T&gt; is used to determine if individual T's are equal</para>
        /// </summary>
        /// <example>
        /// The following code creates a Dictionary where the keys are a set of strings, without regard to order
        /// <code>
        ///     Dictionary&lt;IEnumerable&lt;string&gt;, int&gt; = 
        ///         new Dictionary&lt;IEnumerable&lt;string&gt;, int&gt;(Algorithms.GetSetEqualityComparer&lt;string&gt;(StringComparer.CurrentCultureIgnoreCase));
        /// </code>
        /// </example>
        /// <returns>IEqualityComparer&lt;IEnumerable&lt;T&gt;&gt; implementation suitable for 
        /// comparing collections of T for equality, without regard to order.</returns>
        /// <seealso cref="Algorithms.EqualSets"/>
        public static IEqualityComparer<IEnumerable<T>> GetSetEqualityComparer<T>()
        {
            return GetSetEqualityComparer(EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Gets an IEqualityComparer&lt;IEnumerable&lt;T&gt;&gt; implementation 
        /// that can be used to compare collections of elements (of type T). Two collections
        /// of T's are equal if they have the same number of items, and corresponding 
        /// items are equal, without regard to order. This is the same notion of equality as
        /// in Algorithms.EqualSets, but encapsulated in an IEqualityComparer&lt;IEnumerable&lt;T&gt;&gt; implementation.
        /// </summary>
        /// <example>
        /// The following code creates a Dictionary where the keys are a set of strings, without regard to order
        /// <code>
        ///     Dictionary&lt;IEnumerable&lt;string&gt;, int&gt; = 
        ///         new Dictionary&lt;IEnumerable&lt;string&gt;, int&gt;(Algorithms.GetSetEqualityComparer&lt;string&gt;());
        /// </code>
        /// </example>
        /// <param name="equalityComparer">An IEqualityComparer&lt;T&gt; implementation used to compare individual T's.</param>
        /// <returns>IEqualityComparer&lt;IEnumerable&lt;T&gt;&gt; implementation suitable for 
        /// comparing collections of T for equality, without regard to order.</returns>
        /// <seealso cref="Algorithms.EqualSets"/>
        public static IEqualityComparer<IEnumerable<T>> GetSetEqualityComparer<T>(IEqualityComparer<T> equalityComparer)
        {
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            return new SetEqualityComparer<T>(equalityComparer);
        }

        #endregion Sorting

        #region Predicate operations

        /// <summary>
        /// Determines if a collection contains any item that satisfies the condition
        /// defined by <paramref name="predicate"/>.
        /// </summary>
        /// <param name="collection">The collection to check all the items in.</param>
        /// <param name="predicate">A delegate that defines the condition to check for.</param>
        /// <returns>True if the collection contains one or more items that satisfy the condition
        /// defined by <paramref name="predicate"/>. False if the collection does not contain
        /// an item that satisfies <paramref name="predicate"/>.</returns>
        public static bool Exists<T>(IEnumerable<T> collection, Predicate<T> predicate)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            foreach (T item in collection) {
                if (predicate(item))
                    return true;
            }

            return false;
        }

        /// <summary>
        /// Determines if all of the items in the collection satisfy the condition
        /// defined by <paramref name="predicate"/>.
        /// </summary>
        /// <param name="collection">The collection to check all the items in.</param>
        /// <param name="predicate">A delegate that defines the condition to check for.</param>
        /// <returns>True if all of the items in the collection satisfy the condition
        /// defined by <paramref name="predicate"/>, or if the collection is empty. False if one or more items
        /// in the collection do not satisfy <paramref name="predicate"/>.</returns>
        public static bool TrueForAll<T>(IEnumerable<T> collection, Predicate<T> predicate)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            foreach (T item in collection) {
                if (!predicate(item))
                    return false;
            }

            return true;
        }

        /// <summary>
        /// Counts the number of items in the collection that satisfy the condition
        /// defined by <paramref name="predicate"/>.
        /// </summary>
        /// <param name="collection">The collection to count items in.</param>
        /// <param name="predicate">A delegate that defines the condition to check for.</param>
        /// <returns>The number of items in the collection that satisfy <paramref name="predicate"/>.</returns>
        public static int CountWhere<T>(IEnumerable<T> collection, Predicate<T> predicate)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            int count = 0;
            foreach (T item in collection) {
                if (predicate(item))
                    ++count;
            }

            return count;
        }

        /// <summary>
        /// Removes all the items in the collection that satisfy the condition
        /// defined by <paramref name="predicate"/>.
        /// </summary>
        /// <remarks>If the collection if an array or implements IList&lt;T&gt;, an efficient algorithm that
        /// compacts items is used. If not, then ICollection&lt;T&gt;.Remove is used
        /// to remove items from the collection. If the collection is an array or fixed-size list,
        /// the non-removed elements are placed, in order, at the beginning of
        /// the list, and the remaining list items are filled with a default value (0 or null).</remarks>
        /// <param name="collection">The collection to check all the items in.</param>
        /// <param name="predicate">A delegate that defines the condition to check for.</param>
        /// <returns>Returns a collection of the items that were removed. This collection contains the
        /// items in the same order that they orginally appeared in <paramref name="collection"/>.</returns>
        public static ICollection<T> RemoveWhere<T>(ICollection<T> collection, Predicate<T> predicate)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (predicate == null)
                throw new ArgumentNullException("predicate");
            if (collection is T[])
                collection = new ArrayWrapper<T>((T[])collection);
            if (collection.IsReadOnly)
                throw new ArgumentException(Strings.ListIsReadOnly, "collection");

            IList<T> list = collection as IList<T>;
            if (list != null) {
                T item;
                int i = -1, j = 0;
                int listCount = list.Count;
                List<T> removed = new List<T>();

                // Remove item where predicate is true, compressing items to lower in the list. This is much more
                // efficient than the naive algorithm that uses IList<T>.Remove().
                while (j < listCount) {
                    item = list[j];
                    if (predicate(item)) {
                        removed.Add(item);
                    }
                    else {
                        ++i;
                        if (i != j)
                            list[i] = item;
                    }
                    ++j;
                }

                ++i;
                if (i < listCount) {
                    // remove items from the end.
                    if (list is IList && ((IList)list).IsFixedSize) {
                        // An array or similar. Null out the last elements.
                        while (i < listCount)
                            list[i++] = default(T);
                    }
                    else {
                        // Normal list.
                        while (i < listCount) {
                            list.RemoveAt(listCount - 1);
                            --listCount;
                        }
                    }
                }

                return removed;
            }
            else {
                // We have to copy all the items to remove to a List, because collections can't be modifed 
                // during an enumeration.
                List<T> removed = new List<T>();

                foreach (T item in collection)
                    if (predicate(item))
                        removed.Add(item);

                foreach (T item in removed)
                    collection.Remove(item);

                return removed;
            }
        }

        /// <summary>
        /// Convert a collection of items by applying a delegate to each item in the collection. The resulting collection
        /// contains the result of applying <paramref name="converter"/> to each item in <paramref name="sourceCollection"/>, in
        /// order.
        /// </summary>
        /// <typeparam name="TSource">The type of items in the collection to convert.</typeparam>
        /// <typeparam name="TDest">The type each item is being converted to.</typeparam>
        /// <param name="sourceCollection">The collection of item being converted.</param>
        /// <param name="converter">A delegate to the method to call, passing each item in <paramref name="sourceCollection"/>.</param>
        /// <returns>The resulting collection from applying <paramref name="converter"/> to each item in <paramref name="sourceCollection"/>, in
        /// order.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="sourceCollection"/> or <paramref name="converter"/> is null.</exception>
        public static IEnumerable<TDest> Convert<TSource, TDest>(IEnumerable<TSource> sourceCollection, Converter<TSource, TDest> converter)
        {
            if (sourceCollection == null)
                throw new ArgumentNullException("sourceCollection");
            if (converter == null)
                throw new ArgumentNullException("converter");

            foreach (TSource sourceItem in sourceCollection)
                yield return converter(sourceItem);
        }

        /// <summary>
        /// Creates a delegate that converts keys to values by used a dictionary to map values. Keys
        /// that a not present in the dictionary are converted to the default value (zero or null).
        /// </summary>
        /// <remarks>This delegate can be used as a parameter in Convert or ConvertAll methods to convert
        /// entire collections.</remarks>
        /// <param name="dictionary">The dictionary used to perform the conversion.</param>
        /// <returns>A delegate to a method that converts keys to values. </returns>
        public static Converter<TKey, TValue> GetDictionaryConverter<TKey, TValue>(IDictionary<TKey, TValue> dictionary)
        {
            return GetDictionaryConverter(dictionary, default(TValue));
        }

        /// <summary>
        /// Creates a delegate that converts keys to values by used a dictionary to map values. Keys
        /// that a not present in the dictionary are converted to a supplied default value.
        /// </summary>
        /// <remarks>This delegate can be used as a parameter in Convert or ConvertAll methods to convert
        /// entire collections.</remarks>
        /// <param name="dictionary">The dictionary used to perform the conversion.</param>
        /// <param name="defaultValue">The result of the conversion for keys that are not present in the dictionary.</param>
        /// <returns>A delegate to a method that converts keys to values. </returns>
        /// <exception cref="ArgumentNullException"><paramref name="dictionary"/> is null.</exception>
        public static Converter<TKey, TValue> GetDictionaryConverter<TKey, TValue>(IDictionary<TKey, TValue> dictionary, TValue defaultValue)
        {
            if (dictionary == null)
                throw new ArgumentNullException("dictionary");

            return delegate(TKey key) {
                TValue value;
                if (dictionary.TryGetValue(key, out value))
                    return value;
                else
                    return defaultValue;
            };
        }

        /// <summary>
        /// Performs the specified action on each item in a collection.
        /// </summary>
        /// <param name="collection">The collection to process.</param>
        /// <param name="action">An Action delegate which is invoked for each item in <paramref name="collection"/>.</param>
        public static void ForEach<T>(IEnumerable<T> collection, Action<T> action)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (action == null)
                throw new ArgumentNullException("action");

            foreach (T item in collection)
                action(item);
        }

        /// <summary>
        /// Partition a list or array based on a predicate. After partitioning, all items for which
        /// the predicate returned true precede all items for which the predicate returned false.
        /// </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 partition.</param>
        /// <param name="predicate">A delegate that defines the partitioning condition.</param>
        /// <returns>The index of the first item in the second half of the partition; i.e., the first item for
        /// which <paramref name="predicate"/> returned false. If the predicate was true for all items
        /// in the list, list.Count is returned.</returns>
        public static int Partition<T>(IList<T> list, Predicate<T> predicate)
        {
            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");

            // Move from opposite ends of the list, swapping when necessary.
            int i = 0, j = list.Count - 1;
            for (;;) {
                while (i <= j && predicate(list[i]))
                    ++i;
                while (i <= j && !predicate(list[j]))
                    --j;

                if (i > j)
                    break;
                else {
                    T temp = list[i];
                    list[i] = list[j];
                    list[j] = temp;
                    ++i;
                    --j;
                }
            }

            return i;
        }

        /// <summary>
        /// Partition a list or array based on a predicate. After partitioning, all items for which
        /// the predicate returned true precede all items for which the predicate returned false. 
        /// The partition is stable, which means that if items X and Y have the same result from
        /// the predicate, and X precedes Y in the original list, X will precede Y in the 
        /// partitioned 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 partition.</param>
        /// <param name="predicate">A delegate that defines the partitioning condition.</param>
        /// <returns>The index of the first item in the second half of the partition; i.e., the first item for
        /// which <paramref name="predicate"/> returned false. If the predicate was true for all items
        /// in the list, list.Count is returned.</returns>
        public static int StablePartition<T>(IList<T> list, Predicate<T> predicate)
        {
            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;
            if (listCount == 0)
                return 0;
            T[] temp = new T[listCount];

            // Copy from list to temp buffer, true items at fron, false item (in reverse order) at back.
            int i = 0, j = listCount - 1;
            foreach (T item in list) {
                if (predicate(item))
                    temp[i++] = item;
                else
                    temp[j--] = item;
            }

            // Copy back to the original list.
            int index = 0;
            while (index < i) {
                list[index] = temp[index];
                index++;
            }
            j = listCount - 1;
            while (index < listCount)
                list[index++] = temp[j--];

            return i;
        }

        #endregion Predicate operations

        #region Miscellaneous operations on IEnumerable

        /// <summary>
        /// Concatenates all the items from several collections. The collections need not be of the same type, but
        /// must have the same item type.
        /// </summary>
        /// <param name="collections">The set of collections to concatenate. In many languages, this parameter
        /// can be specified as several individual parameters.</param>
        /// <returns>An IEnumerable that enumerates all the items in each of the collections, in order.</returns>
        public static IEnumerable<T> Concatenate<T>(params IEnumerable<T>[] collections)
        {
            if (collections == null)
                throw new ArgumentNullException("collections");

            foreach (IEnumerable<T> coll in collections) {
                foreach (T item in coll)
                    yield return item;
            }
        }

        /// <summary>
        /// Determines if the two collections contain equal items in the same order. The two collections do not need
        /// to be of the same type; it is permissible to compare an array and an OrderedBag, for instance.
        /// </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>
        /// <typeparam name="T">The type of items in the collections.</typeparam>
        /// <param name="collection1">The first collection to compare.</param>
        /// <param name="collection2">The second collection to compare.</param>
        /// <returns>True if the collections have equal items in the same order. If both collections are empty, true is returned.</returns>
        public static bool EqualCollections<T>(IEnumerable<T> collection1, IEnumerable<T> collection2)
        {
            return EqualCollections(collection1, collection2, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Determines if the two collections contain equal items in the same order. The passed 
        /// instance of IEqualityComparer&lt;T&gt; is used for determining if two items are equal.
        /// </summary>
        /// <typeparam name="T">The type of items in the collections.</typeparam>
        /// <param name="collection1">The first collection to compare.</param>
        /// <param name="collection2">The second collection to compare.</param>
        /// <param name="equalityComparer">The IEqualityComparer&lt;T&gt; used to compare items for equality. 
        /// Only the Equals member function of this interface is called.</param>
        /// <returns>True if the collections have equal items in the same order. If both collections are empty, true is returned.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/>, <paramref name="collection2"/>, or
        /// <paramref name="equalityComparer"/> is null.</exception>
        public static bool EqualCollections<T>(IEnumerable<T> collection1, IEnumerable<T> collection2, IEqualityComparer<T> equalityComparer)
        {
            if (collection1 == null)
                throw new ArgumentNullException("collection1");
            if (collection2 == null)
                throw new ArgumentNullException("collection2");
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            using (IEnumerator<T> enum1 = collection1.GetEnumerator(), enum2 = collection2.GetEnumerator()) {
                bool continue1, continue2;

                for (; ; ) {
                    continue1 = enum1.MoveNext(); continue2 = enum2.MoveNext();
                    if (!continue1 || !continue2)
                        break;

                    if (!equalityComparer.Equals(enum1.Current, enum2.Current))
                        return false;     // the two items are not equal.
                }

                // If both continue1 and continue2 are false, we reached the end of both sequences at the same
                // time and found success. If one is true and one is false, the sequences were of difference lengths -- failure.
                return (continue1 == continue2);
            }
        }

        /// <summary>
        /// Determines if the two collections contain "equal" items in the same order. 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 tested
        /// for need not be equality. For example, the following code determines if each integer in
        /// list1 is less than or equal to the corresponding integer in list2.
        /// <code>
        /// List&lt;int&gt; list1, list2;
        /// if (EqualCollections(list1, list2, delegate(int x, int y) { return x &lt;= y; }) {
        ///     // the check is true...
        /// }
        /// </code>
        /// </remarks>
        /// <typeparam name="T">The type of items in the collections.</typeparam>
        /// <param name="collection1">The first collection to compare.</param>
        /// <param name="collection2">The second collection to compare.</param>
        /// <param name="predicate">The BinaryPredicate used to compare items for "equality". 
        /// This predicate can compute any relation between two items; it need not represent equality or an equivalence relation.</param>
        /// <returns>True if <paramref name="predicate"/>returns true for each corresponding pair of
        /// items in the two collections. If both collections are empty, true is returned.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection1"/>, <paramref name="collection2"/>, or
        /// <paramref name="predicate"/> is null.</exception>
        public static bool EqualCollections<T>(IEnumerable<T> collection1, IEnumerable<T> collection2, BinaryPredicate<T> predicate)
        {
            if (collection1 == null)
                throw new ArgumentNullException("collection1");
            if (collection2 == null)
                throw new ArgumentNullException("collection2");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            using (IEnumerator<T> enum1 = collection1.GetEnumerator(), enum2 = collection2.GetEnumerator()) {
                bool continue1, continue2;

                for (; ; ) {
                    continue1 = enum1.MoveNext(); continue2 = enum2.MoveNext();
                    if (!continue1 || !continue2)
                        break;

                    if (!predicate(enum1.Current, enum2.Current))
                        return false;     // the two items are not equal.
                }

                // If both continue1 and continue2 are false, we reached the end of both sequences at the same
                // time and found success. If one is true and one is false, the sequences were of difference lengths -- failure.
                return (continue1 == continue2);
            }
        }

        /// <summary>
        /// Create an array with the items in a collection.
        /// </summary>
        /// <remarks>If <paramref name="collection"/> implements ICollection&lt;T&gt;T, then 
        /// ICollection&lt;T&gt;.CopyTo() is used to fill the array. Otherwise, the IEnumerable&lt;T&gt;.GetEnumerator()
        /// is used to fill the array.</remarks>
        /// <typeparam name="T">Element type of the collection.</typeparam>
        /// <param name="collection">Collection to create array from.</param>
        /// <returns>An array with the items from the collection, in enumeration order.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
        public static T[] ToArray<T>(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            ICollection<T> coll = collection as ICollection<T>;
            if (coll != null) {
                // Use ICollection methods to do it more efficiently.
                T[] array = new T[coll.Count];
                coll.CopyTo(array, 0);
                return array;
            }
            else {
                // We can't allocate the correct size array now, because IEnumerable doesn't
                // have a Count property. We could enumerate twice, once to count and once
                // to copy. Or we could enumerate once, copying to a List, then copy the list
                // to the correct size array. The latter algorithm seems more efficient, although
                // it allocates extra memory for the list which is then discarded.
                List<T> list = new List<T>(collection);
                return list.ToArray();
            }
        }

        /// <summary>
        /// Count the number of items in an IEnumerable&lt;T&gt; collection. If 
        /// a more specific collection type is being used, it is more efficient to use
        /// the Count property, if one is provided.
        /// </summary>
        /// <remarks>If the collection implements ICollection&lt;T&gt;, this method
        /// simply returns ICollection&lt;T&gt;.Count. Otherwise, it enumerates all items
        /// and counts them.</remarks>
        /// <param name="collection">The collection to count items in.</param>
        /// <returns>The number of items in the collection.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
        public static int Count<T>(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            // If it's really an ICollection, use that Count property as it is much faster.
            if (collection is ICollection<T>)
                return ((ICollection<T>)collection).Count;

            // Traverse the collection and count the elements.
            int count = 0;

            foreach (T item in collection)
                ++count;

            return count;
        }

        /// <summary>
        /// Counts the number of items in the collection that are equal to <paramref name="find"/>.
        /// </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 count items in.</param>
        /// <param name="find">The item to compare to.</param>
        /// <returns>The number of items in the collection that are equal to <paramref name="find"/>.</returns>
        public static int CountEqual<T>(IEnumerable<T> collection, T find)
        {
            return CountEqual(collection, find, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Counts the number of items in the collection that are equal to <paramref name="find"/>.
        /// </summary>
        /// <param name="collection">The collection to count items in.</param>
        /// <param name="find">The item to compare to.</param>
        /// <param name="equalityComparer">The comparer to use to determine if two items are equal. Only the Equals
        /// member function will be called.</param>
        /// <returns>The number of items in the collection that are equal to <paramref name="find"/>.</returns>
        /// <exception cref="ArgumentException"><paramref name="collection"/> or <paramref name="equalityComparer"/>
        /// is null.</exception>
        public static int CountEqual<T>(IEnumerable<T> collection, T find, IEqualityComparer<T> equalityComparer)
        {
            if (collection == null)
                throw new ArgumentException("collection");
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            int count = 0;
            foreach (T item in collection) {
                if (equalityComparer.Equals(item, find))
                    ++count;
            }

            return count;
        }

        /// <summary>
        /// Creates an IEnumerator that enumerates a given item <paramref name="n"/> times.
        /// </summary>
        /// <example>
        /// The following creates a list consisting of 1000 copies of the double 1.0.
        /// <code>
        /// List&lt;double&gt; list = new List&lt;double&gt;(Algorithms.NCopiesOf(1000, 1.0));
        /// </code></example>
        /// <param name="n">The number of times to enumerate the item.</param>
        /// <param name="item">The item that should occur in the enumeration.</param>
        /// <returns>An IEnumerable&lt;T&gt; that yields <paramref name="n"/> copies
        /// of <paramref name="item"/>.</returns>
        /// <exception cref="ArgumentOutOfRangeException">The argument <paramref name="n"/> is less than zero.</exception>
        public static IEnumerable<T> NCopiesOf<T>(int n, T item)
        {
            if (n < 0)
                throw new ArgumentOutOfRangeException("n", n, Strings.ArgMustNotBeNegative);

            while (n-- > 0) {
                yield return item;
            }
        }

        #endregion Miscellaneous operations on IEnumerable

        #region Miscellaneous operations on IList

        /// <summary>
        /// Replaces each item in a list with a given value. The list does not change in size.
        /// </summary>
        /// <typeparam name="T">The type of items in the list.</typeparam>
        /// <param name="list">The list to modify.</param>
        /// <param name="value">The value to fill with.</param>
        /// <exception cref="ArgumentException"><paramref name="list"/> is a read-only list.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
        public static void Fill<T>(IList<T> list, T value)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (list.IsReadOnly)
                throw new ArgumentException(Strings.ListIsReadOnly, "list");
            
            int count = list.Count;
            for (int i = 0; i < count; ++i) {
                list[i] = value;
            }
        }

        /// <summary>
        /// Replaces each item in a array with a given value. 
        /// </summary>
        /// <param name="array">The array to modify.</param>
        /// <param name="value">The value to fill with.</param>
        /// <exception cref="ArgumentNullException"><paramref name="array"/> is null.</exception>
        public static void Fill<T>(T[] array, T value)
        {
            if (array == null)
                throw new ArgumentNullException("array");

            for (int i = 0; i < array.Length; ++i) {
                array[i] = value;
            }
        }

        /// <summary>
        /// Replaces each item in a part of a list with a given value.
        /// </summary>
        /// <typeparam name="T">The type of items in the list.</typeparam>
        /// <param name="list">The list to modify.</param>
        /// <param name="start">The index at which to start filling. The first index in the list has index 0.</param>
        /// <param name="count">The number of items to fill.</param>
        /// <param name="value">The value to fill with.</param>
        /// <exception cref="ArgumentException"><paramref name="list"/> is a read-only list.</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="start"/> or <paramref name="count"/> is negative, or 
        /// <paramref name="start"/> + <paramref name="count"/> is greater than <paramref name="list"/>.Count.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
        public static void FillRange<T>(IList<T> list, int start, int count, T value)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (list.IsReadOnly)
                throw new ArgumentException(Strings.ListIsReadOnly, "list");

            if (count == 0)
                return;
            if (start < 0 || start >= list.Count)
                throw new ArgumentOutOfRangeException("start");
            if (count < 0 || count > list.Count || start > list.Count - count)
                throw new ArgumentOutOfRangeException("count");
            
            for (int i = start; i < count + start; ++i) {
                list[i] = value;
            }
        }

        /// <summary>
        /// Replaces each item in a part of a array with a given value.
        /// </summary>
        /// <param name="array">The array to modify.</param>
        /// <param name="start">The index at which to start filling. The first index in the array has index 0.</param>
        /// <param name="count">The number of items to fill.</param>
        /// <param name="value">The value to fill with.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="start"/> or <paramref name="count"/> is negative, or 
        /// <paramref name="start"/> + <paramref name="count"/> is greater than <paramref name="array"/>.Length.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="array"/> is null.</exception>
        public static void FillRange<T>(T[] array, int start, int count, T value)
        {
            if (array == null)
                throw new ArgumentNullException("array");

            if (count == 0)
                return;
            if (start < 0 || start >= array.Length)
                throw new ArgumentOutOfRangeException("start");
            if (count < 0 || count > array.Length || start > array.Length - count)
                throw new ArgumentOutOfRangeException("count");

            for (int i = start; i < count + start; ++i) {
                array[i] = value;
            }
        }

        /// <summary>
        /// Copies all of the items from the collection <paramref name="source"/> to the list <paramref name="dest"/>, starting
        /// at the index <paramref name="destIndex"/>. If necessary, the size of the destination list is expanded.
        /// </summary>
        /// <param name="source">The collection that provide the source items. </param>
        /// <param name="dest">The list to store the items into.</param>
        /// <param name="destIndex">The index to begin copying items to.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="destIndex"/> is negative or 
        /// greater than <paramref name="dest"/>.Count.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="source"/> or <paramref name="dest"/> is null.</exception>
        public static void Copy<T>(IEnumerable<T> source, IList<T> dest, int destIndex)
        {
            Copy<T>(source, dest, destIndex, int.MaxValue);
        }

        /// <summary>
        /// Copies all of the items from the collection <paramref name="source"/> to the array <paramref name="dest"/>, starting
        /// at the index <paramref name="destIndex"/>. 
        /// </summary>
        /// <param name="source">The collection that provide the source items. </param>
        /// <param name="dest">The array to store the items into.</param>
        /// <param name="destIndex">The index to begin copying items to.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="destIndex"/> is negative or 
        /// greater than <paramref name="dest"/>.Length.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="source"/> or <paramref name="dest"/> is null.</exception>
        /// <exception cref="ArgumentException">The collection has more items than will fit into the array. In this case, the array
        /// has been filled with as many items as fit before the exception is thrown.</exception>
        public static void Copy<T>(IEnumerable<T> source, T[] dest, int destIndex)
        {
            if (source == null)
                throw new ArgumentNullException("source");
            if (dest == null)
                throw new ArgumentNullException("dest");

            if (destIndex < 0 || destIndex > dest.Length)
                throw new ArgumentOutOfRangeException("destIndex");

            using (IEnumerator<T> sourceEnum = source.GetEnumerator()) {
                // Overwrite items to the end of the destination array. If we hit the end, throw.
                while (sourceEnum.MoveNext()) {
                    if (destIndex >= dest.Length)
                        throw new ArgumentException(Strings.ArrayTooSmall, "array");
                    dest[destIndex++] = sourceEnum.Current;
                }
            }
        }

        /// <summary>
        /// Copies at most <paramref name="count"/> items from the collection <paramref name="source"/> to the list <paramref name="dest"/>, starting
        /// at the index <paramref name="destIndex"/>. If necessary, the size of the destination list is expanded. The source collection must not be
        /// the destination list or part thereof.
        /// </summary>
        /// <param name="source">The collection that provide the source items. </param>
        /// <param name="dest">The list to store the items into.</param>
        /// <param name="destIndex">The index to begin copying items to.</param>
        /// <param name="count">The maximum number of items to copy.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="destIndex"/> is negative or 
        /// greater than <paramref name="dest"/>.Count</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="count"/> is negative.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="source"/> or <paramref name="dest"/> is null.</exception>
        public static void Copy<T>(IEnumerable<T> source, IList<T> dest, int destIndex, int count)
        {
            if (source == null)
                throw new ArgumentNullException("source");
            if (dest == null)
                throw new ArgumentNullException("dest");
            if (dest.IsReadOnly)
                throw new ArgumentException(Strings.ListIsReadOnly, "dest");

            int destCount = dest.Count;

            if (destIndex < 0 || destIndex > destCount)
                throw new ArgumentOutOfRangeException("destIndex");
            if (count < 0)
                throw new ArgumentOutOfRangeException("count");

            using (IEnumerator<T> sourceEnum = source.GetEnumerator()) {
                // First, overwrite items to the end of the destination list.
                while (destIndex < destCount && count > 0 && sourceEnum.MoveNext()) {
                    dest[destIndex++] = sourceEnum.Current;
                    --count;
                }

                // Second, insert items until done.
                while (count > 0 && sourceEnum.MoveNext()) {
                    dest.Insert(destCount++, sourceEnum.Current);
                    --count;
                }
            }
        }

        /// <summary>
        /// Copies at most <paramref name="count"/> items from the collection <paramref name="source"/> to the array <paramref name="dest"/>, starting
        /// at the index <paramref name="destIndex"/>. The source collection must not be
        /// the destination array or part thereof.
        /// </summary>
        /// <param name="source">The collection that provide the source items. </param>
        /// <param name="dest">The array to store the items into.</param>
        /// <param name="destIndex">The index to begin copying items to.</param>
        /// <param name="count">The maximum number of items to copy. The array must be large enought to fit this number of items.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="destIndex"/> is negative or 
        /// greater than <paramref name="dest"/>.Length.</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="count"/> is negative or <paramref name="destIndex"/> + <paramref name="count"/>
        /// is greater than <paramref name="dest"/>.Length.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="source"/> or <paramref name="dest"/> is null.</exception>
        public static void Copy<T>(IEnumerable<T> source, T[] dest, int destIndex, int count)
        {
            if (source == null)
                throw new ArgumentNullException("source");
            if (dest == null)
                throw new ArgumentNullException("dest");

            int destCount = dest.Length;

            if (destIndex < 0 || destIndex > destCount)
                throw new ArgumentOutOfRangeException("destIndex");
            if (count < 0 || destIndex + count > destCount)
                throw new ArgumentOutOfRangeException("count");

            using (IEnumerator<T> sourceEnum = source.GetEnumerator()) {
                // First, overwrite items to the end of the destination array.
                while (destIndex < destCount && count > 0 && sourceEnum.MoveNext()) {
                    dest[destIndex++] = sourceEnum.Current;
                    --count;
                }
            }
        }

        /// <summary>
        /// Copies <paramref name="count"/> items from the list <paramref name="source"/>, starting at the index <paramref name="sourceIndex"/>, 
        /// to the list <paramref name="dest"/>, starting at the index <paramref name="destIndex"/>. If necessary, the size of the destination list is expanded.
        /// The source and destination lists may be the same.
        /// </summary>
        /// <param name="source">The collection that provide the source items. </param>
        /// <param name="sourceIndex">The index within <paramref name="source"/>to begin copying items from.</param>
        /// <param name="dest">The list to store the items into.</param>
        /// <param name="destIndex">The index within <paramref name="dest"/>to begin copying items to.</param>
        /// <param name="count">The maximum number of items to copy.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="sourceIndex"/> is negative or 
        /// greater than <paramref name="source"/>.Count</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="destIndex"/> is negative or 
        /// greater than <paramref name="dest"/>.Count</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="count"/> is negative or too large.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="source"/> or <paramref name="dest"/> is null.</exception>
        public static void Copy<T>(IList<T> source, int sourceIndex, IList<T> dest, int destIndex, int count)
        {
            if (source == null)
                throw new ArgumentNullException("source");
            if (dest == null)
                throw new ArgumentNullException("dest");
            if (dest.IsReadOnly)
                throw new ArgumentException(Strings.ListIsReadOnly, "dest");

            int sourceCount = source.Count;
            int destCount = dest.Count;

            if (sourceIndex < 0 || sourceIndex >= sourceCount)
                throw new ArgumentOutOfRangeException("sourceIndex");
            if (destIndex < 0 || destIndex > destCount)
                throw new ArgumentOutOfRangeException("destIndex");
            if (count < 0)
                throw new ArgumentOutOfRangeException("count");
            if (count > sourceCount - sourceIndex)
                count = sourceCount - sourceIndex;

            if (source == dest && sourceIndex > destIndex) {
                while (count > 0) {
                    dest[destIndex++] = source[sourceIndex++];
                    --count;
                }
            }
            else {
                int si, di;

                // First, insert any items needed at the end
                if (destIndex + count > destCount) {
                    int numberToInsert = destIndex + count - destCount;
                    si = sourceIndex + (count - numberToInsert);
                    di = destCount;
                    count -= numberToInsert;
                    while (numberToInsert > 0) {
                        dest.Insert(di++, source[si++]);
                        --numberToInsert;
                    }
                }
                   
                // Do the copy, from end to beginning in case of overlap.
                si = sourceIndex + count - 1;
                di = destIndex + count - 1;
                while (count > 0) {
                    dest[di--] = source[si--];
                    --count;
                }
            }
        }

        /// <summary>
        /// Copies <paramref name="count"/> items from the list or array <paramref name="source"/>, starting at the index <paramref name="sourceIndex"/>, 
        /// to the array <paramref name="dest"/>, starting at the index <paramref name="destIndex"/>. 
        /// The source may be the same as the destination array.
        /// </summary>
        /// <param name="source">The list or array that provide the source items. </param>
        /// <param name="sourceIndex">The index within <paramref name="source"/>to begin copying items from.</param>
        /// <param name="dest">The array to store the items into.</param>
        /// <param name="destIndex">The index within <paramref name="dest"/>to begin copying items to.</param>
        /// <param name="count">The maximum number of items to copy. The destination array must be large enough to hold this many items.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="sourceIndex"/> is negative or 
        /// greater than <paramref name="source"/>.Count</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="destIndex"/> is negative or 
        /// greater than <paramref name="dest"/>.Length</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="count"/> is negative or too large.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="source"/> or <paramref name="dest"/> is null.</exception>
        public static void Copy<T>(IList<T> source, int sourceIndex, T[] dest, int destIndex, int count)
        {
            if (source == null)
                throw new ArgumentNullException("source");
            if (dest == null)
                throw new ArgumentNullException("dest");

            int sourceCount = source.Count;
            int destCount = dest.Length;

            if (sourceIndex < 0 || sourceIndex >= sourceCount)
                throw new ArgumentOutOfRangeException("sourceIndex");
            if (destIndex < 0 || destIndex > destCount)
                throw new ArgumentOutOfRangeException("destIndex");
            if (count < 0 || destIndex + count > destCount)
                throw new ArgumentOutOfRangeException("count");

            if (count > sourceCount - sourceIndex)
                count = sourceCount - sourceIndex;

            if (source is T[]) {
                // Array.Copy is probably faster, and also handles any overlapping issues.
                Array.Copy((T[])source, sourceIndex, dest, destIndex, count);
            }
            else {
                int si = sourceIndex;
                int di = destIndex;
                while (count > 0) {
                    dest[di++] = source[si++];
                    --count;
                }
            }
        }

        /// <summary>
        /// Reverses a list and returns the reversed list, without changing the source list.
        /// </summary>
        /// <param name="source">The list to reverse.</param>
        /// <returns>A collection that contains the items from <paramref name="source"/> in reverse order.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="source"/> is null.</exception>
        public static IEnumerable<T> Reverse<T>(IList<T> source)
        {
            if (source == null)
                throw new ArgumentNullException("source");

            for (int i = source.Count - 1; i >= 0; --i)
                yield return source[i];
        }

        /// <summary>
        /// Reverses a list or array in place.
        /// </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 reverse.</param>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
        /// <exception cref="ArgumentException"><paramref name="list"/> is read only.</exception>
        public static void ReverseInPlace<T>(IList<T> list)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (list is T[])
                list = new ArrayWrapper<T>((T[])list);
            if (list.IsReadOnly)
                throw new ArgumentException(Strings.ListIsReadOnly, "list");

            int i, j;
            i = 0;
            j = list.Count - 1;
            while (i < j) {
                T temp = list[i];
                list[i] = list[j];
                list[j] = temp;
                i++;
                j--;
            }
        }

        /// <summary>
        /// Rotates a list and returns the rotated list, without changing the source list.
        /// </summary>
        /// <param name="source">The list to rotate.</param>
        /// <param name="amountToRotate">The number of elements to rotate. This value can be positive or negative. 
        /// For example, rotating by positive 3 means that source[3] is the first item in the returned collection.
        /// Rotating by negative 3 means that source[source.Count - 3] is the first item in the returned collection.</param>
        /// <returns>A collection that contains the items from <paramref name="source"/> in rotated order.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="source"/> is null.</exception>
        public static IEnumerable<T> Rotate<T>(IList<T> source, int amountToRotate)
        {
            if (source == null)
                throw new ArgumentNullException("source");

            int count = source.Count;
            if (count != 0) {
                amountToRotate = amountToRotate % count;
                if (amountToRotate < 0)
                    amountToRotate += count;

                // Do it in two parts.
                for (int i = amountToRotate; i < count; ++i)
                    yield return source[i];
                for (int i = 0; i < amountToRotate; ++i)
                    yield return source[i];
            }
        }

        /// <summary>
        /// Rotates a list or array in place.
        /// </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 rotate.</param>
        /// <param name="amountToRotate">The number of elements to rotate. This value can be positive or negative. 
        /// For example, rotating by positive 3 means that list[3] is the first item in the resulting list.
        /// Rotating by negative 3 means that list[list.Count - 3] is the first item in the resulting list.</param>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
        public static void RotateInPlace<T>(IList<T> list, int amountToRotate)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (list is T[])
                list = new ArrayWrapper<T>((T[])list);
            if (list.IsReadOnly)
                throw new ArgumentException(Strings.ListIsReadOnly, "list");

            int count = list.Count;
            if (count != 0) {
                amountToRotate = amountToRotate % count;
                if (amountToRotate < 0)
                    amountToRotate += count;

                int itemsLeft = count;
                int indexStart = 0;
                while (itemsLeft > 0) {
                    // Rotate an orbit of items through the list. If itemsLeft is relatively prime
                    // to count, this will rotate everything. If not, we need to do this several times until
                    // all items have been moved.
                    int index = indexStart;
                    T itemStart = list[indexStart];
                    for (;;) {
                        --itemsLeft;
                        int nextIndex = index + amountToRotate;
                        if (nextIndex >= count)
                            nextIndex -= count;
                        if (nextIndex == indexStart) {
                            list[index] = itemStart;
                            break;
                        }
                        else {
                            list[index] = list[nextIndex];
                            index = nextIndex;
                        }
                    }

                    // Move to the next orbit.
                    ++indexStart;
                }
            }
        }

        #endregion Miscellaneous operations on IList

    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Eclipse Public License 1.0

Share

About the Author

Stefan Bocutiu
Software Developer (Senior) Lab49
United Kingdom United Kingdom
No Biography provided

| Advertise | Privacy | Mobile
Web04 | 2.8.140926.1 | Last Updated 29 Jan 2009
Article Copyright 2009 by Stefan Bocutiu
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid