//#define __MonoCS__
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace miew.Enumerable
{
using String = System.String;
public static class Extensions
{
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// .NET 4.0 has String.Join(String, IEnumerable<String>)
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public static String StringJoin<T>(this IEnumerable<T> ie, String sep)
{
return String.Join(sep, ie as IEnumerable<String> ?? ie.Select(e => e.ToString()));
}
public static HashSet<T> ToHashSet<T>(this IEnumerable<T> ie)
{
return new HashSet<T>(ie);
}
/// <summary>
/// Append one element to the end of a sequence.
/// </summary>
/// <param name="seq">The original sequence. Can be null.</param>
/// <param name="element">An element to append.</param>
public static IEnumerable<T> Append<T>(this IEnumerable<T> seq, T element)
{
if (seq != null)
{
foreach (T t in seq)
yield return t;
}
yield return element;
}
/// <summary>
/// Prepend one element to the beginning of a sequence.
/// </summary>
/// <param name="seq">The original sequence. Can be null.</param>
/// <param name="element">An element to prepend.</param>
public static IEnumerable<T> Prepend<T>(this IEnumerable<T> seq, T element)
{
yield return element;
if (seq != null)
{
foreach (T t in seq)
yield return t;
}
}
//struct SingleItemEnumerable<T> : IEnumerable<T>
//{
// T t;
// public SingleItemEnumerable(T t)
// {
// this.t = t;
// }
// struct _enum : IEnumerator<T>
// {
// T t;
// int ix;
// public _enum(T t)
// {
// this.t = t;
// this.ix = -1;
// }
// public T Current { get { return t; } }
// object IEnumerator.Current { get { return t; } }
// public bool MoveNext() { return ++ix == 0; }
// public void Reset() { ix = -1; }
// public void Dispose() { }
// };
// public IEnumerator<T> GetEnumerator() { return new _enum(t); }
// IEnumerator IEnumerable.GetEnumerator() { return new _enum(t); }
//};
public static IEnumerable<T> AsSingleton<T>(this T t)
{
//return new SingleItemEnumerable<T>(t);
return new T[] { t };
}
public static IEnumerable<T> TakeLast<T>(this IEnumerable<T> source, int n)
{
if (source == null)
throw new ArgumentNullException("source");
if (n < 0)
throw new ArgumentOutOfRangeException("must not be negative", "n");
if (n > 0)
{
T[] result = new T[n];
int i = 0;
int count = 0;
foreach (T t in source)
{
result[i] = t;
i = (i + 1) % n;
count++;
}
if (count < n)
{
n = count;
i = 0;
}
for (int j = 0; j < n; j++)
yield return result[(i + j) % n];
}
}
public static Double WeightedAverage<T>(this IEnumerable<T> seq, Func<T, double> value_selector, Func<T, double> weight_selector)
{
Double sum = seq.Sum(weight_selector);
Double avg = 0;
foreach (T t in seq)
avg += value_selector(t) * weight_selector(t) / sum;
return avg;
}
public static T Middle<T>(this IEnumerable<T> seq)
{
var ie1 = seq.GetEnumerator();
if (!ie1.MoveNext())
throw new ArgumentException();
T current = ie1.Current;
var ie2 = seq.GetEnumerator();
ie2.MoveNext();
while (ie2.MoveNext())
{
if (!ie2.MoveNext())
break;
ie1.MoveNext();
current = ie1.Current;
}
return current;
}
public static bool Any<T>(this IEnumerable<T> seq, Func<T, int, bool> predicate)
{
int i = 0;
foreach (T t in seq)
if (predicate(t, i++))
return true;
return false;
}
/// <summary>
/// Return the (distinct) set union of all elements of type TDst generated by a selector which projects each
/// source element of type TSrc from the sequence into a new sequence of zero or more elements of type
/// TDst
/// </summary>
public static HashSet<TDst> UnionMany<TSrc, TDst>(this IEnumerable<TSrc> seq, Func<TSrc, IEnumerable<TDst>> selector)
{
HashSet<TDst> hs = new HashSet<TDst>();
foreach (TSrc t in seq)
hs.UnionWith(selector(t));
return hs;
}
/// <summary>
/// Although there's no problem on .NET, the 'GroupBy' extension method is unusably slow on Mono. Below, we
/// implement a usable version from scratch
/// </summary>
public static IEnumerable<IGrouping<TKey, TSrc>> _GroupBy<TSrc, TKey>(this IEnumerable<TSrc> ie, Func<TSrc, TKey> fn)
{
#if __MonoCS__
Dictionary<TKey, _grouping<TKey, TSrc>> d = new Dictionary<TKey, _grouping<TKey, TSrc>>();
foreach (TSrc src in ie)
{
TKey k = fn(src);
_grouping<TKey, TSrc> l;
if (!d.TryGetValue(k, out l))
d.Add(k, l = new _grouping<TKey, TSrc>(k));
l.Add(src);
}
return d.Values;
#else
return ie.GroupBy(fn);
#endif
}
public static IEnumerable<IGrouping<TKey, TSrc>> _GroupBy<TSrc, TKey>(this IEnumerable<TSrc> ie, Func<TSrc, TKey> fn, IEqualityComparer<TKey> c)
{
#if __MonoCS__
Dictionary<TKey, _grouping<TKey, TSrc>> d = new Dictionary<TKey, _grouping<TKey, TSrc>>(c);
foreach (TSrc src in ie)
{
TKey k = fn(src);
_grouping<TKey, TSrc> l;
if (!d.TryGetValue(k, out l))
d.Add(k, l = new _grouping<TKey, TSrc>(k));
l.Add(src);
}
return d.Values;
#else
return ie.GroupBy(fn, c);
#endif
}
#if __MonoCS__
class _grouping<TKey, TSrc> : List<TSrc>, IGrouping<TKey, TSrc>
{
public TKey _key;
public _grouping(TKey k) { _key = k; }
public TKey Key
{
get { return _key; }
}
}
#endif
/// <summary>
///
/// </summary>
public static IEnumerable<T> Sort<T>(this IEnumerable<T> seq)
where T : IComparable<T>
{
return seq.OrderBy(_t => _t);
}
/// <summary>
///
/// </summary>
public static IEnumerable<T> OrderByDistinct<T>(this IEnumerable<T> seq)
where T : IComparable<T>
{
IEnumerator<T> iei = seq.OrderBy(_t => _t).GetEnumerator();
if (!iei.MoveNext())
yield break;
T t, t2;
yield return t = iei.Current;
while (iei.MoveNext())
{
if (!t.Equals(t2 = iei.Current))
yield return t = t2;
}
}
/// <summary>
///
/// </summary>
public static IEnumerable<T> OrderByDistinct<T, TKey>(this IEnumerable<T> seq, Func<T, TKey> selector)
where TKey : IComparable<TKey>
{
IEnumerator<T> iei = seq.OrderBy(selector).GetEnumerator();
if (!iei.MoveNext())
yield break;
T t, t2;
yield return t = iei.Current;
while (iei.MoveNext())
{
if (!t.Equals(t2 = iei.Current))
yield return t = t2;
}
}
/// <summary>
/// Reduce a sequence of 'n' elements to 'n-1' by combining adjacent elements
/// </summary>
public static IEnumerable<TDst> ReduceAdjacent<TSrc, TDst>(this IEnumerable<TSrc> seq, Func<TSrc, TSrc, TDst> combiner)
{
IEnumerator<TSrc> iei = seq.GetEnumerator();
if (!iei.MoveNext())
yield break;
TSrc i_prev = iei.Current;
while (iei.MoveNext())
yield return combiner(i_prev, i_prev = iei.Current);
}
/// <summary>
/// Exclude all instances of element <paramref name="element"/> from the sequence <paramref name="seq"/>.
/// </summary>
/// <param name="seq">The original sequence.</param>
/// <param name="element">The element to exclude.</param>
public static IEnumerable<T> Exclude<T>(this IEnumerable<T> seq, T element)
{
foreach (T t in seq)
if (!t.Equals(element))
yield return t;
}
public static IEnumerable<T> ExceptElementAt<T>(this IEnumerable<T> seq, int ix)
{
int i = 0;
foreach (T t in seq)
{
if (i != ix)
yield return t;
i++;
}
}
public static IEnumerable<T> OfExactType<T>(this IEnumerable seq)
{
foreach (Object t in seq)
if (t.GetType() == typeof(T))
yield return (T)t;
}
/// <summary>
/// Return one source element from each range result mapped by the selector function
/// </summary>
#if true
public static IEnumerable<TSrc> Distinct<TSrc, TKey>(this IEnumerable<TSrc> seq, Converter<TSrc, TKey> keySelector)
{
if (seq == null)
throw new ArgumentNullException("source");
return seq._GroupBy(e => keySelector(e)).Select(g => g.First());
}
#else
public static IEnumerable<TSrc> Distinct<TSrc, TKey>(this IEnumerable<TSrc> source, Converter<TSrc, TKey> keySelector)
{
if (source == null)
throw new ArgumentNullException("source");
return source.Distinct<TSrc>(new LambdaComparer<TSrc>((s1, s2) =>
{
return keySelector(s1).Equals(keySelector(s2));
}, h => 0));
}
#endif
class distinct_grouping<TKey, TSrc> : HashSet<TSrc>, IGrouping<TKey, TSrc>
{
public TKey _key;
public distinct_grouping(TKey k) { _key = k; }
public TKey Key
{
get { return _key; }
}
}
/// <summary>
/// Group elements of the sequence according to the key generated by keySelector, where each group contains a distinct
/// set of elements projected by elementSelector.
/// </summary>
public static IEnumerable<IGrouping<TKey, TElement>> GroupByDistinct<TSrc, TKey, TElement>(
this IEnumerable<TSrc> seq,
Func<TSrc, TKey> keySelector,
Func<TSrc, TElement> elementSelector)
{
var ie = seq.GetEnumerator();
if (!ie.MoveNext())
return System.Linq.Enumerable.Empty<IGrouping<TKey, TElement>>();
Dictionary<TKey, distinct_grouping<TKey, TElement>> d = new Dictionary<TKey, distinct_grouping<TKey, TElement>>();
do
{
TSrc t = ie.Current;
TKey k = keySelector(t);
distinct_grouping<TKey, TElement> l;
if (!d.TryGetValue(k, out l))
d.Add(k, l = new distinct_grouping<TKey, TElement>(k));
l.Add(elementSelector(t));
}
while (ie.MoveNext());
return d.Values;
}
public static int CountDistinct<TSrc, TDst>(this IEnumerable<TSrc> seq, Func<TSrc, TDst> selector)
{
var ie = seq.GetEnumerator();
if (!ie.MoveNext())
return 0;
HashSet<TDst> hs = new HashSet<TDst>();
do
hs.Add(selector(ie.Current));
while (ie.MoveNext());
return hs.Count;
}
public static int CountDistinct<TSrc>(this IEnumerable<TSrc> seq)
{
var ie = seq.GetEnumerator();
if (!ie.MoveNext())
return 0;
HashSet<TSrc> hs = new HashSet<TSrc>();
do
hs.Add(ie.Current);
while (ie.MoveNext());
return hs.Count;
}
public static int CountDistinctValues<K, V>(this IDictionary<K, V> seq)
{
var ie = seq.GetEnumerator();
if (!ie.MoveNext())
return 0;
HashSet<V> hs = new HashSet<V>();
do
hs.Add(ie.Current.Value);
while (ie.MoveNext());
return hs.Count;
}
public static bool IsDistinct<T>(this IEnumerable<T> seq)
{
var ie = seq.GetEnumerator();
if (ie.MoveNext())
{
HashSet<T> hs = new HashSet<T>();
do
{
T t = ie.Current;
if (hs.Contains(t))
return false;
hs.Add(t);
}
while (ie.MoveNext());
}
return true;
}
/// <summary>
/// Return a sequence where only the elements from the original sequence which match the predicate are transformed.
/// </summary>
/// <param name="seq">The original sequence.</param>
/// <param name="filter">A predicate for matching elements from the original sequence.</param>
/// <param name="selector">A transformation which will be applied to matching elements.</param>
public static IEnumerable<TResult> WhereSelect<TSrc, TResult>(this IEnumerable<TSrc> seq, Predicate<TSrc> filter, Converter<TSrc, TResult> selector)
{
foreach (TSrc t in seq)
if (filter(t))
yield return selector(t);
}
/// <summary>
/// Returns true if the sequence is empty, that is, if it has no elements. Also returns null if <paramref name="seq"/> is <i>null</i>.
/// </summary>
/// <param name="seq">The sequence to examine, or null.</param>
/// <returns>True if the sequence is empty or null.</returns>
public static bool None<T>(this IEnumerable<T> seq)
{
if (seq == null)
return true;
ICollection<T> ic = seq as ICollection<T>;
if (ic != null)
return ic.Count == 0;
return !seq.GetEnumerator().MoveNext();
}
/// <summary>
/// Returns true if the sequence is empty, that is, if it has no elements. Also returns null if <paramref name="seq"/> is <i>null</i>.
/// </summary>
/// <param name="seq">The sequence to examine, or null.</param>
/// <param name="predicate">A filter function which identifies elements to ignore when considering if the list is empty</param>
/// <returns>True if the sequence is empty or null.</returns>
public static bool None<T>(this IEnumerable<T> seq, Func<T, bool> predicate)
{
return seq == null ? true : !seq.Any(predicate);
}
/// <summary>
/// Returns the element from a sequence that maximizes the function <paramref name="objective"/>.
/// </summary>
/// <typeparam name="TArg">A type which implements IComparable<T></typeparam>
/// <param name="seq">A sequence of at least one element.</param>
/// <param name="objective">An objective function to maximize. <paramref name="objective"/> will not be called more than once per element.</param>
/// <returns>The element in the sequence that maximizes the function. If more than one element equivalently maximize the function, the first such element is returned.</returns>
/// <remarks>There must be at least one element in the sequence. If there is exactly one element, <paramref name="objective"/> will not be called, so do not expect
/// its side-effects to occur.</remarks>
public static TSrc ArgMax<TSrc, TArg>(this IEnumerable<TSrc> seq, Converter<TSrc, TArg> objective) where TArg : IComparable<TArg>
{
IEnumerator<TSrc> e = seq.GetEnumerator();
if (!e.MoveNext())
throw new InvalidOperationException("Sequence has no elements.");
TSrc t = e.Current;
if (e.MoveNext())
{
TArg v, max_val = objective(t);
do
{
TSrc t_try;
if ((v = objective(t_try = e.Current)).CompareTo(max_val) > 0)
{
t = t_try;
max_val = v;
}
}
while (e.MoveNext());
}
return t;
}
public static bool TryArgMax<TSrc, TArg>(this IEnumerable<TSrc> seq, Converter<TSrc, TArg> objective, out TSrc t) where TArg : IComparable<TArg>
{
IEnumerator<TSrc> e = seq.GetEnumerator();
if (!e.MoveNext())
{
t = default(TSrc);
return false;
}
t = e.Current;
if (e.MoveNext())
{
TArg max_val = objective(t);
do
{
TArg v;
TSrc t_try;
if ((v = objective(t_try = e.Current)).CompareTo(max_val) > 0)
{
t = t_try;
max_val = v;
}
}
while (e.MoveNext());
}
return true;
}
/// <summary>
/// Returns the element from a sequence that minimizes the function <paramref name="objective"/>.
/// </summary>
/// <typeparam name="TArg">A type which implements IComparable<T></typeparam>
/// <param name="seq">A sequence of at least one element.</param>
/// <param name="objective">An objective function to minimize. <paramref name="objective"/> will not be called more than once per element.</param>
/// <returns>The element in the sequence that maximizes the function. If more than one element equivalently minimize the function, the first such element is returned.</returns>
/// <remarks>There must be at least one element in the sequence. If there is exactly one element, <paramref name="objective"/> will not be called, so do not expect
/// its side-effects to occur.</remarks>
public static TSrc ArgMin<TSrc, TArg>(this IEnumerable<TSrc> seq, Converter<TSrc, TArg> objective) where TArg : IComparable<TArg>
{
IEnumerator<TSrc> e = seq.GetEnumerator();
if (!e.MoveNext())
throw new InvalidOperationException("Sequence has no elements.");
TSrc t = e.Current;
if (e.MoveNext())
{
TArg v, min_val = objective(t);
do
{
TSrc t_try;
if ((v = objective(t_try = e.Current)).CompareTo(min_val) < 0)
{
t = t_try;
min_val = v;
}
}
while (e.MoveNext());
}
return t;
}
/// <summary>
/// Returns the index of the first element in a sequence that satisfies the predicate.
/// </summary>
public static int IndexOfFirst<TSrc>(this IEnumerable<TSrc> seq, Func<TSrc, bool> predicate)
{
int i = 0;
foreach (TSrc t in seq)
{
if (predicate(t))
return i;
i++;
}
return -1;
}
/// <summary>
/// Returns the index of the only element in a sequence that satisfies the predicate, or -1 if there is not exactly one such element.
/// </summary>
public static int IndexOfOnly<TSrc>(this IEnumerable<TSrc> seq, Func<TSrc, bool> predicate)
{
int i = 0;
int i_found = -1;
foreach (TSrc t in seq)
{
if (predicate(t))
{
if (i_found != -1)
return -1;
i_found = i;
}
i++;
}
return i_found;
}
public static bool TryMax(this IEnumerable<int> seq, out int t)
{
IEnumerator<int> e = seq.GetEnumerator();
if (!e.MoveNext())
{
t = int.MinValue;
return false;
}
t = e.Current;
if (!e.MoveNext())
return true;
do
{
int tx = e.Current;
if (tx > t)
t = tx;
}
while (e.MoveNext());
return true;
}
public static bool TryMax<TSrc>(this IEnumerable<TSrc> seq, Converter<TSrc, int> objective, out int t)
{
IEnumerator<TSrc> e = seq.GetEnumerator();
if (!e.MoveNext())
{
t = int.MinValue;
return false;
}
t = objective(e.Current);
if (e.MoveNext())
{
do
{
int tx = objective(e.Current);
if (tx > t)
t = tx;
}
while (e.MoveNext());
}
return true;
}
/// <summary>
/// Returns the index of the element in a sequence that maximizes the function <paramref name="objective"/>.
/// </summary>
/// <typeparam name="TArg">A type which implements IComparable<T></typeparam>
/// <param name="seq">A sequence of zero or more elements.</param>
/// <param name="objective">An objective function to maximize. <paramref name="objective"/> will not be called more than once per element.</param>
/// <returns>The index of the element in the sequence that maximizes the function, or <value>-1</value> if the sequence has no elements. If more than one element
/// equivalently maximize the function, the index of the first such element is returned.</returns>
public static int IndexOfMax<TSrc, TArg>(this IEnumerable<TSrc> seq, Converter<TSrc, TArg> objective) where TArg : IComparable<TArg>
{
IEnumerator<TSrc> e = seq.GetEnumerator();
if (!e.MoveNext())
return -1;
int max_ix = 0;
TSrc t = e.Current;
if (!e.MoveNext())
return max_ix;
TArg tx, max_val = objective(t);
int i = 1;
do
{
if ((tx = objective(e.Current)).CompareTo(max_val) > 0)
{
max_val = tx;
max_ix = i;
}
i++;
}
while (e.MoveNext());
return max_ix;
}
/// <summary>
/// Returns the index of the element in a sequence that minimizes the function <paramref name="objective"/>.
/// </summary>
/// <typeparam name="TArg">A type which implements IComparable<T></typeparam>
/// <param name="seq">A sequence of zero or more elements.</param>
/// <param name="objective">An objective function to minimize. <paramref name="objective"/> will not be called more than once per element.</param>
/// <returns>The index of the element in the sequence that minimize the function, or <value>-1</value> if the sequence has no elements. If more than one element
/// equivalently minimize the function, the index of the first such element is returned.</returns>
public static int IndexOfMin<TSrc, TArg>(this IEnumerable<TSrc> seq, Converter<TSrc, TArg> objective) where TArg : IComparable<TArg>
{
IEnumerator<TSrc> e = seq.GetEnumerator();
if (!e.MoveNext())
return -1;
int min_ix = 0;
TSrc t = e.Current;
if (!e.MoveNext())
return min_ix;
TArg tx, min_val = objective(t);
int i = 1;
do
{
if ((tx = objective(e.Current)).CompareTo(min_val) < 0)
{
min_val = tx;
min_ix = i;
}
i++;
}
while (e.MoveNext());
return min_ix;
}
/// <summary>
/// Pair-up the elements of a vector of elements of type T
/// </summary>
public static IEnumerable<KeyValuePair<T, T>> PairOff<T>(this IEnumerable<T> seq)
{
IEnumerator<T> e = seq.GetEnumerator();
while (e.MoveNext())
{
T first = e.Current;
if (e.MoveNext())
yield return new KeyValuePair<T, T>(first, e.Current);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public static IList<T> Shuffle<T>(this IEnumerable<T> source)
{
if (source == null)
throw new ArgumentNullException("source");
Random rnd = new Random();
List<T> result = source.ToList();
int c = result.Count;
for (int i = 0; i < c; i++)
miew.Array.Extensions.Swap<T>(result, i, rnd.Next(c));
return result;
}
public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey>(
this IEnumerable<TSource> seq,
Func<TSource, TKey> keySelector,
Func<TKey, TKey, bool> comparer)
{
return seq._GroupBy(keySelector, new LambdaComparer<TKey>(comparer));
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// Filter for non-default(T) values (i.e. non-null references, non-default values)
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public static IEnumerable<T> NotDefault<T>(this IEnumerable<T> source)
{
return source.Where(e => !Object.Equals(e, default(T)));
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// Filter for non-default(T) values (i.e. non-null references, non-default values)
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public static IEnumerable<TSrc> NotDefault<TSrc, TAny>(this IEnumerable<TSrc> source, Converter<TSrc, TAny> selector)
{
return source.Where(e => !Object.Equals(selector(e), default(TAny)));
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public static IEnumerable<TDst> SelectNotNull<TSrc, TDst>(this IEnumerable<TSrc> source, Func<TSrc, TDst> selector) where TDst : class
{
IEnumerator<TSrc> ie = source.GetEnumerator();
TDst e;
while (ie.MoveNext())
if ((e = selector(ie.Current)) != null)
yield return e;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
class LambdaComparer<T> : IEqualityComparer<T>
{
private readonly Func<T, T, bool> c;
private readonly Func<T, int> h;
public LambdaComparer(Func<T, T, bool> lambdaComparer) :
this(lambdaComparer, o => o.GetHashCode())
{
}
public LambdaComparer(Func<T, T, bool> lambdaComparer, Func<T, int> lambdaHash)
{
if (lambdaComparer == null)
throw new ArgumentNullException("lambdaComparer");
if (lambdaHash == null)
throw new ArgumentNullException("lambdaHash");
c = lambdaComparer;
h = lambdaHash;
}
public bool Equals(T x, T y)
{
return c(x, y);
}
public int GetHashCode(T obj)
{
return h(obj);
}
};
};
}