//******************************
// 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<T>,
/// ICollection<T> and IList<T>.
/// </summary>
public static class Algorithms
{
#region Collection wrappers
/// <summary>
/// The class that is used to implement IList<T> 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<T> 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<T> 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<T> 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<T> 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<T> 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<T> 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<T> 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 <TKey,TValue>.
/// </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<TKey,TValue> 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<TKey,TValue> 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<T>
/// view onto an untyped IEnumerator interface.
/// </summary>
[Serializable]
private class TypedEnumerator<T> : IEnumerator<T>
{
private IEnumerator wrappedEnumerator;
/// <summary>
/// Create a typed IEnumerator<T>
/// 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<T> view
/// onto an untyped IEnumerable interface.
/// </summary>
[Serializable]
private class TypedEnumerable<T> : IEnumerable<T>
{
private IEnumerable wrappedEnumerable;
/// <summary>
/// Create a typed IEnumerable<T> 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<T>
/// 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<T>.
/// 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<T> 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<T> view
/// onto an untyped ICollection interface. The ICollection<T>
/// is read-only.
/// </summary>
[Serializable]
private class TypedCollection<T> : ICollection<T>
{
private ICollection wrappedCollection;
/// <summary>
/// Create a typed ICollection<T> 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<T>
/// 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<T>.
/// 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<T> 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<T> 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<T> view onto
/// an untype IList interface.
/// </summary>
[Serializable]
private class TypedList<T> : IList<T>
{
private IList wrappedList;
/// <summary>
/// Create a typed IList<T> 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<T>
/// 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<T>.
/// 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<T> 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<T> interface.
/// </summary>
[Serializable]
private class UntypedCollection<T> : ICollection
{
private ICollection<T> wrappedCollection;
/// <summary>
/// Create an untyped ICollection
/// view onto a typed ICollection<T> interface.
/// </summary>
/// <param name="wrappedCollection">The ICollection<T> 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<T> 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<T> interface.
/// </summary>
[Serializable]
private class UntypedList<T> : IList
{
private IList<T> wrappedList;
/// <summary>
/// Create a non-generic IList wrapper
/// around a generic IList<T> interface.
/// </summary>
/// <param name="wrappedList">The IList<T> 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<T> 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<T> 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<T> wrapper around an array. When an array is
/// implicitely converted to an IList<T>, changes to the items in the array cannot
/// be made through the interface. This method creates a read-write IList<T> 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<T> 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<T>.</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<T> 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<T>.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<T> 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<T>.Equals or object.Equals.</para>
/// <para>Although arrays cast to IList<T> 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<T> 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<T> 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<T> 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<T>.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<T> 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<T>.Equals or object.Equals.</para>
/// <para>Although arrays cast to IList<T> 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<T> 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<T> 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<T> 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<T>.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<T> 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<T>, 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<T>, 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<T> 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<T> 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<T>.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<T> 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<T>.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<T> 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<T>.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<T> 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<T> used to compare items for equality. Only the Equals method will be called.</param>
/// <returns>An IEnumerable<T> 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<T>.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<T> 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<T>.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<T> 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<T>.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<T> 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<T> used to compare items for equality. </param>
/// <returns>An IEnumerable<T> 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<T> 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<T>.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<T> 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<T> 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<T>.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<T> 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<T>.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<T> 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<T>.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<T> 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<T>.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<T> 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<T>.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<T> 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<T>.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<T> 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 < 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<T>.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 < 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<T> 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<T>.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<T> 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<Pair<TFirst, TSecond>> 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<T> 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<T> 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<T>, 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<T>, 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<T[]> 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<T[]> 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<T> 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<T> used to compare the items.</param>
/// <returns>An IEnumerable<T[]> 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<T> 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<T> delegate used to compare the items.</param>
/// <returns>An IEnumerable<T[]> 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<T>
/// 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<T> 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<T> 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<T>
/// 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<T> 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<T> 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<T>
/// 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<T> 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<T> 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<T>
/// 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<T> 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<T> 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<T>
/// 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<T> 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<T> 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<T>
/// interfaces implementation on the type T.</para>
/// <para>Although arrays cast to IList<T> 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<T> 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<T> 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<T> 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<T> 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<T>
/// 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<T> 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<T> delegate is used
/// to compare the items in the collection.
/// </summary>
/// <remarks>Values are compared by using the IComparable<T>
/// 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<T>
/// interfaces implementation on the type T.</para>
/// <para>Although arrays cast to IList<T> 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<T> is used
/// to compare the items in the list.
/// </summary>
/// <remarks>Although arrays cast to IList<T> 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<T> delegate is used
/// to compare the items in the list.
/// </summary>
/// <remarks>Although arrays cast to IList<T> 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<T>).
/// </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<T>.
/// </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<T> 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<T>). 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<T> 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<T>. 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<T> 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<T> 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<T> 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<T> and this implementation is used
/// to compare the items. </remarks>
/// <typeparam name="T">Types of items to compare. This type must implement IComparable<T> 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<T> 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<T> 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<T> 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<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<T> and this implementation is used
/// to compare the items. </remarks>
/// <returns>At IComparer<IEnumerable<T>> 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<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<IEnumerable<T>> 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<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<IEnumerable<T>> 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<T>. 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<T> 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<T>, 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<T> 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<T> 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<T>. 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<T> 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<T> instance that performs the same comparison.
/// </summary>
/// <param name="comparison">The comparison delegate to use.</param>
/// <returns>An IComparer<T> 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<T> instenace that comparers two items from type T,
/// gets a Comparison delegate that performs the same comparison.
/// </summary>
/// <param name="comparer">The IComparer<T> instance to use.</param>
/// <returns>A Comparison<T> 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<IEnumerable<T>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<IEnumerable<T>> 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<IEnumerable<T>> implementation.
/// </summary>
/// <example>
/// The following code creates a Dictionary where the keys are a collection of strings.
/// <code>
/// Dictionary<IEnumerable<string>, int> =
/// new Dictionary<IEnumerable<string>, int>(Algorithms.GetCollectionEqualityComparer<string>());
/// </code>
/// </example>
/// <returns>IEqualityComparer<IEnumerable<T>> 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<IEnumerable<T>> 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<IEnumerable<T>> implementation.</para>
/// <para>An IEqualityComparer<T> 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<IEnumerable<string>, int> =
/// new Dictionary<IEnumerable<string>, int>(Algorithms.GetCollectionEqualityComparer<string>(StringComparer.CurrentCultureIgnoreCase));
/// </code>
/// </example>
/// <param name="equalityComparer">An IEqualityComparer<T> implementation used to compare individual T's.</param>
/// <returns>IEqualityComparer<IEnumerable<T>> 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<IEnumerable<T>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<IEnumerable<T>> 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<IEnumerable<T>> implementation.</para>
/// <para>An IEqualityComparer<T> 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<IEnumerable<string>, int> =
/// new Dictionary<IEnumerable<string>, int>(Algorithms.GetSetEqualityComparer<string>(StringComparer.CurrentCultureIgnoreCase));
/// </code>
/// </example>
/// <returns>IEqualityComparer<IEnumerable<T>> 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<IEnumerable<T>> 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<IEnumerable<T>> implementation.
/// </summary>
/// <example>
/// The following code creates a Dictionary where the keys are a set of strings, without regard to order
/// <code>
/// Dictionary<IEnumerable<string>, int> =
/// new Dictionary<IEnumerable<string>, int>(Algorithms.GetSetEqualityComparer<string>());
/// </code>
/// </example>
/// <param name="equalityComparer">An IEqualityComparer<T> implementation used to compare individual T's.</param>
/// <returns>IEqualityComparer<IEnumerable<T>> 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<T>, an efficient algorithm that
/// compacts items is used. If not, then ICollection<T>.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<T> 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<T> 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<T>.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<T> 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<T> 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<int> list1, list2;
/// if (EqualCollections(list1, list2, delegate(int x, int y) { return x <= 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<T>T, then
/// ICollection<T>.CopyTo() is used to fill the array. Otherwise, the IEnumerable<T>.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<T> 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<T>, this method
/// simply returns ICollection<T>.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<T>.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<double> list = new List<double>(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<T> 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<T> 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<T> 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
}
}
Submit an article or tip