using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Loyc.Collections.Impl;
using Loyc.Math;
namespace Loyc.Collections
{
/// <summary>Extension methods and helper methods for <see cref="List{T}"/>,
/// <see cref="IList{T}"/>, <see cref="IListSource<T>"/>, arrays, and for
/// related mutable interfaces such as <see cref="IArray{T}"/>.
/// </summary>
/// <remarks>Extension methods that only apply to Loyc's new interfaces will
/// go in <see cref="LCExt"/>.</remarks>
public static class ListExt
{
public static void CopyTo<T>(this IReadOnlyCollection<T> c, T[] array, int arrayIndex)
{
int space = array.Length - arrayIndex;
if (c.Count > space)
throw new ArgumentException(Localize.From("CopyTo: array is too small ({0} < {1})", space, c.Count));
foreach (var item in c)
array[arrayIndex++] = item;
}
public static T TryGet<T>(this T[] list, int index, T defaultValue)
{
if ((uint)index < (uint)list.Length)
return list[index];
return defaultValue;
}
public static T TryGet<T>(this List<T> list, int index, T defaultValue)
{
if ((uint)index < (uint)list.Count)
return list[index];
return defaultValue;
}
public static T TryGet<T>(this IList<T> list, int index, T defaultValue)
{
if ((uint)index < (uint)list.Count)
return list[index];
return defaultValue;
}
public static void RemoveRange<T>(this IList<T> list, int index, int count)
{
if (index < 0)
throw new IndexOutOfRangeException(index.ToString() + " < 0");
if (count > list.Count - index)
throw new IndexOutOfRangeException(index.ToString() + " + " + count.ToString() + " > " + list.Count.ToString());
if (count > 0) {
for (int i = index; i < list.Count - count; i++)
list[i] = list[i + count];
Resize(list, list.Count - count);
}
}
public static void Resize<T>(this List<T> list, int newSize)
{
int dif = newSize - list.Count;
if (dif > 0) {
do list.Add(default(T));
while (--dif != 0);
} else if (dif < 0) {
int i = list.Count;
do list.RemoveAt(--i);
while (++dif != 0);
}
}
public static void Resize<T>(this IList<T> list, int newSize)
{
int dif = newSize - list.Count;
if (dif > 0) {
do list.Add(default(T));
while (--dif != 0);
} else if (dif < 0) {
int i = list.Count;
do list.RemoveAt(--i);
while (++dif != 0);
}
}
public static IEnumerable<Pair<A, B>> Zip<A, B>(this IEnumerable<A> a, IEnumerable<B> b)
{
var ea = a.GetEnumerator();
var eb = b.GetEnumerator();
while (ea.MoveNext() && eb.MoveNext())
yield return Pair.Create(ea.Current, eb.Current);
}
public static IEnumerable<Pair<A, B>> ZipLonger<A, B>(this IEnumerable<A> a, IEnumerable<B> b)
{
return ZipLonger(a, b, default(A), default(B));
}
public static IEnumerable<Pair<A, B>> ZipLonger<A, B>(this IEnumerable<A> a, IEnumerable<B> b, A defaultA, B defaultB)
{
var ea = a.GetEnumerator();
var eb = b.GetEnumerator();
bool haveA, haveB;
for (; ; ) {
haveA = ea.MoveNext();
haveB = eb.MoveNext();
if (!haveA && !haveB)
break;
yield return Pair.Create(haveA ? ea.Current : defaultA, haveB ? eb.Current : defaultB);
}
}
static int[] RangeArray(int count)
{
var n = new int[count];
for (int i = 0; i < n.Length; i++) n[i] = i;
return n;
}
/// <inheritdoc cref="Sort(IList{T}, int, int, Comparison{T})"/>
public static void Sort<T>(this IList<T> list)
{
Sort(list, Comparer<T>.Default.Compare);
}
/// <inheritdoc cref="Sort(IList{T}, int, int, Comparison{T})"/>
public static void Sort<T>(this IList<T> list, Comparison<T> comp)
{
Sort(list, 0, list.Count, comp, null);
}
/// <summary>Performs a quicksort using a Comparison function.</summary>
/// <param name="index">Index at which to begin sorting a portion of the list.</param>
/// <param name="count">Number of items to sort starting at 'index'.</param>
/// <remarks>
/// This method exists because the .NET framework offers no method to
/// sort <see cref="IList{T}"/>--you can sort arrays and <see cref="List{T}"/>,
/// but not IList.
/// </remarks>
public static void Sort<T>(this IList<T> list, int index, int count, Comparison<T> comp)
{
Sort(list, index, count, comp, null);
}
/// <summary>Performs a stable sort, i.e. a sort that preserves the
/// relative order of items that compare equal.</summary>
/// <remarks>
/// This algorithm uses a quicksort and therefore runs in O(N log N) time,
/// but it requires O(N) temporary space (specifically, an array of N
/// integers) and is slower than a standard quicksort, so you should use
/// it only if you need a stable sort.
/// </remarks>
public static void StableSort<T>(this IList<T> list, Comparison<T> comp)
{
Sort(list, 0, list.Count, comp, RangeArray(list.Count));
}
public static void StableSort<T>(this IList<T> list)
{
StableSort(list, Comparer<T>.Default.Compare);
}
private static void Sort<T>(this IList<T> list, int index, int count, Comparison<T> comp, int[] indexes)
{
// This code duplicates the code in InternalList.Sort(), except
// that it also supports stable sorting. This version is slower;
// Two versions exist so that array sorting can be done faster.
CheckParam.Range("index", index, 0, list.Count);
CheckParam.Range("count", count, 0, list.Count - index);
for (;;) {
if (count < InternalList.QuickSortThreshold)
{
if (count <= 2) {
if (count == 2)
SortPair(list, index, index + 1, comp);
} else {
InsertionSort(list, index, count, comp);
}
return;
}
int iPivot = InternalList.PickPivot(list, index, count, comp);
int iBegin = index;
// Swap the pivot to the beginning of the range
T pivot = list[iPivot];
if (iBegin != iPivot) {
Swap(list, iBegin, iPivot);
if (indexes != null)
MathEx.Swap(ref indexes[iPivot], ref indexes[iBegin]);
}
int i = iBegin + 1;
int iOut = iBegin;
int iStop = index + count;
int leftSize = 0; // size of left partition
// Quick sort pass
do {
int order = comp(list[i], pivot);
if (order > 0)
continue;
if (order == 0) {
if (indexes != null) {
if (indexes[i] > indexes[iBegin])
continue;
} else if (leftSize < (count >> 1))
continue;
}
++iOut;
++leftSize;
if (i != iOut) {
Swap(list, i, iOut);
if (indexes != null)
MathEx.Swap(ref indexes[i], ref indexes[iOut]);
}
} while (++i != iStop);
// Finally, put the pivot element in the middle (at iOut)
Swap(list, iBegin, iOut);
if (indexes != null)
MathEx.Swap(ref indexes[iBegin], ref indexes[iOut]);
// Now we need to sort the left and right sub-partitions. Use a
// recursive call only to sort the smaller partition, in order to
// guarantee O(log N) stack space usage.
int rightSize = count - 1 - leftSize;
if (leftSize < rightSize)
{
// Recursively sort the left partition; iteratively sort the right
Sort(list, index, leftSize, comp, indexes);
index += leftSize + 1;
count = rightSize;
}
else
{ // Iteratively sort the left partition; recursively sort the right
count = leftSize;
Sort(list, index + leftSize + 1, rightSize, comp, indexes);
}
}
}
/// <summary>Performs an insertion sort.</summary>
/// <remarks>The insertion sort is a stable sort algorithm that is slow in
/// general (O(N^2)). It should be used only when (a) the list to be sorted
/// is short (less than 10-20 elements) or (b) the list is very nearly
/// sorted already.</remarks>
/// <seealso cref="InternalList.InsertionSort"/>
public static void InsertionSort<T>(this IList<T> array, int index, int count, Comparison<T> comp)
{
for (int i = index + 1; i < index + count; i++)
{
int j = i;
do
if (!SortPair(array, j - 1, j, comp))
break;
while (--j > index);
}
}
/// <summary>Sorts two items to ensure that list[i] is less than list[j].</summary>
/// <returns>True if the array elements were swapped, false if not.</returns>
public static bool SortPair<T>(this IList<T> list, int i, int j, Comparison<T> comp)
{
if (i != j && comp(list[i], list[j]) > 0) {
Swap(list, i, j);
return true;
}
return false;
}
/// <summary>Swaps list[i] with list[j].</summary>
public static void Swap<T>(this IList<T> list, int i, int j)
{
T tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
public static void Swap<T>(this IArray<T> list, int i, int j)
{
T tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
/// <summary>Gets the lowest index at which a condition is true, or -1 if nowhere.</summary>
public static int IndexWhere<T>(this IList<T> list, Func<T, bool> pred)
{
return LCInterfaces.IndexWhere(list.AsListSource(), pred);
}
/// <summary>Gets the highest index at which a condition is true, or -1 if nowhere.</summary>
public static int LastIndexWhere<T>(this IList<T> list, Func<T, bool> pred)
{
return LCInterfaces.LastIndexWhere(list.AsListSource(), pred);
}
public static ListSlice<T> Slice<T>(this IList<T> list, int start, int length = int.MaxValue)
{
return new ListSlice<T>(list, start, length);
}
public static ArraySlice<T> Slice<T>(this T[] list, int start, int length = int.MaxValue)
{
return new ArraySlice<T>(list, start, int.MaxValue);
}
public static Slice_<T> Slice<T>(this IListSource<T> array, int start, int count = int.MaxValue)
{
return new Slice_<T>(array, start, count);
}
public static int IndexOfMin(this IEnumerable<int> source)
{
var e = source.GetEnumerator();
if (!e.MoveNext())
return -1;
int i = 0, min_i = 0;
for (int min = e.Current; e.MoveNext(); i++) {
if (min > e.Current) {
min = e.Current;
min_i = i+1;
}
}
return min_i;
}
public static int IndexOfMin<T>(this IEnumerable<T> source, Func<T, int> selector)
{
int _;
return IndexOfMin<T>(source, selector, out _);
}
public static int IndexOfMin<T>(this IEnumerable<T> source, Func<T, int> selector, out int min)
{
min = 0;
var e = source.GetEnumerator();
if (!e.MoveNext())
return -1;
int i = 0, min_i = 0, cur;
for (min = selector(e.Current); e.MoveNext(); i++) {
if (min > (cur = selector(e.Current))) {
min = cur;
min_i = i+1;
}
}
return min_i;
}
public static int IndexOfMax(this IEnumerable<int> source)
{
var e = source.GetEnumerator();
if (!e.MoveNext())
return -1;
int i = 0, max_i = 0;
for (int max = e.Current; e.MoveNext(); i++) {
if (max < e.Current) {
max = e.Current;
max_i = i+1;
}
}
return max_i;
}
public static int IndexOfMax<T>(this IEnumerable<T> source, Func<T, int> selector)
{
int _;
return IndexOfMax<T>(source, selector, out _);
}
public static int IndexOfMax<T>(this IEnumerable<T> source, Func<T, int> selector, out int max)
{
max = 0;
var e = source.GetEnumerator();
if (!e.MoveNext())
return -1;
int i = 0, max_i = 0, cur;
for (max = selector(e.Current); e.MoveNext(); i++) {
if (max < (cur = selector(e.Current))) {
max = cur;
max_i = i+1;
}
}
return max_i;
}
public static int IndexOfMin<T>(this IEnumerable<T> source)
{
var e = source.GetEnumerator();
if (!e.MoveNext())
return -1;
Comparer<T> comparer = Comparer<T>.Default;
T min, cur;
int i = 0, min_i = 0;
for (min = e.Current; min == null; i++, min = e.Current)
if (!e.MoveNext())
return -1;
while (e.MoveNext()) {
i++;
if ((cur = e.Current) != null && comparer.Compare(cur, min) < 0) {
min = cur;
min_i = i;
}
}
return min_i;
}
public static int IndexOfMin<T, R>(this IEnumerable<T> source, Func<T, R> selector)
{
R _;
return IndexOfMin<T, R>(source, selector, out _);
}
public static int IndexOfMin<T, R>(this IEnumerable<T> source, Func<T, R> selector, out R min)
{
min = default(R);
var e = source.GetEnumerator();
if (!e.MoveNext())
return -1;
Comparer<R> comparer = Comparer<R>.Default;
R cur;
int i = 0, min_i = 0;
for (min = selector(e.Current); min == null; i++, min = selector(e.Current))
if (!e.MoveNext())
return -1;
while (e.MoveNext()) {
i++;
if ((cur = selector(e.Current)) != null && comparer.Compare(cur, min) < 0) {
min = cur;
min_i = i;
}
}
return min_i;
}
public static int IndexOfMax<T>(this IEnumerable<T> source)
{
var e = source.GetEnumerator();
if (!e.MoveNext())
return -1;
Comparer<T> comparer = Comparer<T>.Default;
T max, cur;
int i = 0, max_i = 0;
for (max = e.Current; max == null; i++, max = e.Current)
if (!e.MoveNext())
return -1;
while (e.MoveNext()) {
i++;
if ((cur = e.Current) != null && comparer.Compare(cur, max) > 0) {
max = cur;
max_i = i;
}
}
return max_i;
}
public static int IndexOfMax<T, R>(this IEnumerable<T> source, Func<T, R> selector)
{
R _;
return IndexOfMax(source, selector, out _);
}
public static int IndexOfMax<T, R>(this IEnumerable<T> source, Func<T, R> selector, out R max)
{
max = default(R);
var e = source.GetEnumerator();
if (!e.MoveNext())
return -1;
Comparer<R> comparer = Comparer<R>.Default;
R cur;
int i = 0, max_i = 0;
for (max = selector(e.Current); max == null; i++, max = selector(e.Current))
if (!e.MoveNext())
return -1;
while (e.MoveNext()) {
i++;
if ((cur = selector(e.Current)) != null && comparer.Compare(cur, max) > 0) {
max = cur;
max_i = i;
}
}
return max_i;
}
static Random _r = new Random();
public static void Randomize<T>(this IList<T> list)
{
int count = list.Count;
for (int i = 0; i < count; i++)
list.Swap(i, _r.Next(count));
}
public static void Randomize<T>(this T[] list)
{
for (int i = 0; i < list.Length; i++)
MathEx.Swap(ref list[i], ref list[_r.Next(list.Length)]);
}
/// <summary>Quickly makes a copy of a list, as an array, in random order.</summary>
public static T[] Randomized<T>(this IList<T> list)
{
T[] copy = new T[list.Count];
list.CopyTo(copy, 0);
Randomize(copy);
return copy;
}
/// <summary>Maps an array to another array of the same length.</summary>
public static R[] SelectArray<T, R>(this T[] input, Func<T,R> selector)
{
if (input == null)
return null;
R[] result = new R[input.Length];
for (int i = 0; i < input.Length; i++)
result[i] = selector(input[i]);
return result;
}
/// <summary>Removes the all the elements that match the conditions defined by the specified predicate.</summary>
/// <returns>The number of elements removed from the list</returns>
public static int RemoveAll<T>(this IList<T> list, Predicate<T> match)
{
int to = 0, c = list.Count;
for (int i = 0; i < c; i++) {
if (!match(list[i])) {
if (i != to)
list[to] = list[i];
to++;
}
}
list.RemoveRange(to, c - to);
return c - to;
}
public static void Reverse<T>(this IList<T> list)
{
int c = list.Count;
for (int i = 0; i < (c >> 1); i++)
list.Swap(i, c - i);
}
public static void Reverse<T>(this IArray<T> list)
{
int c = list.Count;
for (int i = 0; i < (c >> 1); i++)
list.Swap(i, c - i);
}
public static void AddRange<T>(this IList<T> list, IEnumerable<T> range)
{
foreach (var item in range)
list.Add(item);
}
}
}