Click here to Skip to main content
11,484,402 members (64,140 online)
Click here to Skip to main content
Articles » Languages » C# » General » Downloads
Add your own
alternative version

LINQ for Immutable Arrays

, 28 Dec 2012 MIT 9K 126 13
A library of extension methods similar to IEnumerable for working with immutable arrays.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Runtime.Serialization;

namespace CDiggins.Sequences.Immutable
{
    /// <summary>
    /// Represents an immutable array. 
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public interface IArray<T>
    {
        /// <summary>
        /// Returns the number of elements in the array. Must guarantee O(1) complexity in the worst case.
        /// </summary>
        int Count { get; }

        /// <summary>
        /// Returns the nth element in the array. Must guarantee O(1) complexity in the worst case.
        /// </summary>
        T this[int n] { get; }

        /// <summary>
        /// Copies a range of elements to a System.Array and returns that array. Must guarantee O(N) complexity in the worst case. 
        /// </summary>
        T[] CopyTo(int srcIndex, T[] dest, int destIndex, int len);
    }

    /// <summary>
    /// Represents a sorted IArray. This is returned from the OrderBy() extension methods of IArray.
    /// The extension methods Contains() and IndexOf() have O(LogN) complexity on average when called 
    /// on an ISortedArray as opposed to O(N) complexity when called on an 
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public interface ISortedArray<T> : IArray<T> where T : IComparable<T>
    {
    }
    public interface IIterator<T>
    {
        bool HasValue { get; }
        T Value { get; }
        IIterator<T> Next { get; }
    }
    public interface IArrayGroup<K, V> : IArray<V>
    {
        K Key { get; }
    }
    public interface IArrayLookup<K, V>
    {
        IArray<K> Keys { get; }
        bool Contains(K k);
        IArray<IArrayGroup<K, V>> Groups { get; }
        IArray<V> this[K k] { get; }
    }
    public static class ImmutableArray
    {
        private sealed class SortedArrayAdapter<T> : ISortedArray<T> where T : IComparable<T>
        {
            IArray<T> a;
            public SortedArrayAdapter(IArray<T> xs)
            {
                Debug.Assert(xs.IsOrdered());
                a = xs;
            }
            public int Count
            {
                get { return a.Count; }
            }
            public T this[int n]
            {
                get { return a[n]; }
            }
            public T[] CopyTo(int srcIndex, T[] dest, int destIndex, int len)
            {
                return a.CopyTo(srcIndex, dest, destIndex, len);
            }
        }
        private sealed class ArrayGroup<K, V> : IArrayGroup<K, V>
        {
            public K Key
            {
                get;
                private set;
            }
            public IArray<V> Values
            {
                get;
                private set;
            }
            public int Count
            {
                get { return Values.Count; }
            }
            public V this[int n]
            {
                get { return Values[n]; }
            }
            public ArrayGroup(K key, IArray<V> values)
            {
                Key = key;
                Values = values;
            }
            public V[] CopyTo(int srcIndex, V[] dest, int destIndex, int len)
            {
                for (int i = 0; i < len; ++i)
                    dest[i + destIndex] = this[i + srcIndex];
                return dest;
            }
        }
        private sealed class ArrayLookup<K, V> : IArrayLookup<K, V>
        {
            readonly Dictionary<K, IArray<V>> d;
            public IArray<K> Keys { get; private set; }
            public IArray<IArrayGroup<K, V>> Groups { get; private set; }
            public IArray<V> this[K k] { get { return d[k]; } }
            public bool Contains(K k) { return d.ContainsKey(k); }
            public ArrayLookup(IArray<IArrayGroup<K, V>> groups)
            {
                this.d = groups.ToEnumerable().ToDictionary(g => g.Key, g => (IArray<V>)g);
                Keys = groups.Select(g => g.Key);
                Groups = groups;
            }
        }
        private sealed class ArrayLookupBuilder<K, V>
        {
            Dictionary<K, List<V>> d = new Dictionary<K, List<V>>();
            public ArrayLookupBuilder<K, V> Add(K k, V v)
            {
                if (!d.ContainsKey(k)) d.Add(k, new List<V>() { v });
                else d[k].Add(v);
                return this;
            }
            public ArrayLookupBuilder() { }
            public ArrayLookupBuilder(Dictionary<K, List<V>> d) { this.d = d; }
            public ArrayLookupBuilder<K, V> Merge(ArrayLookupBuilder<K, V> other)
            {
                return new ArrayLookupBuilder<K, V>(
                    d.Keys.ToDictionary(
                    k => k,
                    k => other.d.ContainsKey(k)
                        ? d[k].Concat(other.d[k]).ToList()
                        : new List<V>(d[k])));
            }
            public IArrayLookup<K, V> ToLookup()
            {
                return new ArrayLookup<K, V>(d.ToIArray().Select(kv => (IArrayGroup<K, V>)new ArrayGroup<K, V>(kv.Key, new ListAdapter<V>(kv.Value))));
            }
        }
        private sealed class EmptyArray<T> : IArray<T>
        {
            public int Count { get { return 0; } }
            public T this[int n] { get { throw new IndexOutOfRangeException(); } }
            public T[] CopyTo(int srcIndex, T[] dest, int destIndex, int len) { return dest; }
        }
        private sealed class UnitArray<T> : IArray<T>
        {
            public readonly T X;
            public UnitArray(T x) { X = x; }
            public int Count { get { return 1; } }
            public T this[int n] { get { if (n != 0) throw new IndexOutOfRangeException(); return X; } }
            public T[] CopyTo(int srcIndex, T[] dest, int destIndex, int len) { for (int i = 0; i < len; ++i) dest[destIndex + i] = this[srcIndex + i]; return dest; }
        }
        private sealed class ArrayAdapter<T> : IArray<T>
        {
            public readonly T[] array;
            public ArrayAdapter(T[] xs) { this.array = xs; }
            public int Count { get { return array.Length; } }
            public T this[int n] { get { return array[n]; } }
            public T[] CopyTo(int srcIndex, T[] dest, int destIndex, int len) { System.Array.Copy(array, srcIndex, dest, destIndex, len); return dest; }
        }
        private sealed class ListAdapter<T> : IArray<T>
        {
            public readonly List<T> xs;
            public ListAdapter(List<T> xs) { this.xs = xs; }
            public int Count { get { return xs.Count; } }
            public T this[int n] { get { return xs[n]; } }
            public T[] CopyTo(int srcIndex, T[] dest, int destIndex, int len) { xs.CopyTo(srcIndex, dest, destIndex, len); return dest; }
        }
        private sealed class RangeArray : IArray<int>
        {
            public readonly int from;
            public readonly int count;
            public RangeArray(int from, int count) { this.from = from; this.count = count; }
            public int Count { get { return count; } }
            public int this[int n] { get { return from + n; } }
            public int[] CopyTo(int srcIndex, int[] dest, int destIndex, int len) { for (int i = 0; i < len; ++i) dest[i + destIndex] = this[i]; return dest; }
        }
        private sealed class Repeater<T> : IArray<T>
        {
            public readonly T x;
            public readonly int count;
            public Repeater(T x, int count) { this.x = x; this.count = count; }
            public int Count { get { return count; } }
            public T this[int n] { get { return x; } }
            public T[] CopyTo(int srcIndex, T[] dest, int destIndex, int len) { for (int i = 0; i < len; ++i) dest[i + destIndex] = x; return dest; }
        }
        public static IArray<T> ToIArray<T>(this T[] xs) { return Create(xs); }
        public static IArray<T> ToIArray<T>(this List<T> xs) { return Create(xs); }
        public static IArray<T> ToIArray<T>(this IEnumerable<T> xs) { return Create(xs); }
        public static IArray<T> Create<T>(IEnumerable<T> xs)
        {
            return new ArrayAdapter<T>(xs.ToArray());
        }
        public static IArray<T> Create<T>(List<T> xs)
        {
            return new ListAdapter<T>(xs);
        }
        public static IArray<T> Create<T>(params T[] args) 
        {
            return new ArrayAdapter<T>((T[])args.Clone());
        }       
        public static IArray<T> Nil<T>()
        {
            return new EmptyArray<T>();
        }
        public static IArray<T> Nil<T>(this IArray<T> self) 
        { 
            return Nil<T>(); 
        }
        public static IArray<T> Unit<T>(T x)
        {
            return new UnitArray<T>(x);
        }
        public static IArray<int> Range(int count)
        {
            return new RangeArray(0, count);
        }
        public static IArray<int> Range(int from, int count)
        {
            return new RangeArray(from, count);
        }
        public static IArray<T> Repeat<T>(T x, int count)
        {
            return new Repeater<T>(x, count);
        }
        public static IArray<T> Repeat<T>(Func<T> f, int count)
        {
            return Range(count).Select(x => f());
        }
        public static IArray<U> Select<T, U>(this IArray<T> self, Func<T, U> map)
        {
            int n = self.Count;
            var r = new U[n];
            for (int i = 0; i < n; ++i)
                r[i] = map(self[i]);
            return new ArrayAdapter<U>(r);
        }
        public static IArray<U> Select<T, U>(this IArray<T> self, Func<T, int, U> map)
        {
            int n = self.Count;
            var r = new U[n];
            for (int i = 0; i < n; ++i)
                r[i] = map(self[i], i);
            return new ArrayAdapter<U>(r);
        }
        public static IArray<T> Where<T>(this IArray<T> self, Func<T, bool> f)
        {
            var n = self.Count;
            var r = new List<T>();
            for (int i = 0; i < n; ++i)
            {
                var tmp = self[i];
                if (f(tmp))
                    r.Add(tmp);
            }
            return new ListAdapter<T>(r);
        }
        public static IArray<T> Where<T>(this IArray<T> self, Func<T, int, bool> f)
        {
            var n = self.Count;
            var r = new List<T>();
            for (int i = 0; i < n; ++i)
            {
                var tmp = self[i];
                if (f(tmp, i))
                    r.Add(tmp);
            }
            return new ListAdapter<T>(r);
        }
        public static IArray<T> Flatten<T>(this IArray<IArray<T>> seqs)
        {
            var tmp = seqs.Select(xs => xs.Count).PartialSums();
            var r = new T[tmp.Last()];
            tmp = tmp.DropSuffix(1);
            for (int i=0; i < seqs.Count; ++i)
                seqs[i].CopyTo(r, (int)tmp[i]);
            return new ArrayAdapter<T>(r);
         }
        public static IArray<T> Concat<T>(params IList<T>[] lists)
        {
            return lists.Select(x => x.ToIArray()).ToIArray().Flatten();
        }
        public static IArray<T> Concat<T>(this IArray<T> self, IArray<T> other) 
        { 
            return Concat(new [] { self, other }) ; 
        }
        public static IArray<T> Concat<T>(params IArray<T>[] seqs)
        {
            return new ArrayAdapter<IArray<T>>(seqs).Flatten();
        }
        public static IArray<U> FlatMap<T, U>(this IArray<IArray<T>> seqs, Func<T, U> map)
        {
            return seqs.Flatten().Select(map);
        }
        public static T[] CopyTo<T>(this IArray<T> self, T[] dest, int destIndex = 0)
        {
            return self.CopyTo(0, dest, destIndex, self.Count);
        }
        public static T[] ToArray<T>(this IArray<T> self)
        {
            var r = new T[self.Count];
            self.CopyTo(r);
            return r;
        }
        public static T[] ToArraySlice<T>(this IArray<T> self, int from, int count)
        {
            if (from < 0) from = 0;
            var n = from + count > self.Count ? self.Count - from : count;
            if (n <= 0) return new T[0];
            return self.CopyTo(from, new T[n], 0, n);
        }
        public static IArray<T> Slice<T>(this IArray<T> self, int from, int count)
        {
            return new ArrayAdapter<T>(self.ToArraySlice(from, count));
        }
        public static IArray<T> Stride<T>(this IArray<T> self, int from, int sz)
        {
            if (sz == 0) return self.Nil();
            if (sz == 1) return self.Skip(from);
            var tmp = (self.Count - from);
            var n =  tmp / sz;
            if (tmp % sz != 0)
                n++;
            var r = new T[n];
            for (int i = 0, j = from; i < n && j < self.Count; i++, j += sz)
                r[i] = self[j];
            return new ArrayAdapter<T>(r);
        }
        public static IArray<T> Stride<T>(this IArray<T> self, int sz)
        {
            return self.Stride(0, sz);
        }
        public static T Aggregate<T>(this IArray<T> self, Func<T, T, T> f)
        {
            return Aggregate(self, default(T), f);
        }
        public static U Aggregate<T, U>(this IArray<T> self, U init, Func<U, T, U> f)
        {
            for (int i = 0; i < self.Count; ++i)
                init = f(init, self[i]);
            return init;
        }
        public static U Aggregate<T, U>(this IArray<T> self, U init, Func<U, T, int, U> f)
        {
            for (int i = 0; i < self.Count; ++i)
                init = f(init, self[i], i);
            return init;
        }
        public static int CountWhile<T>(this IArray<T> self, Func<T, bool> p)
        {
            for (int i = 0; i < self.Count; ++i)
                if (!p(self[i]))
                    return i;
            return self.Count;
        }
        public static int CountWhile<T>(this IArray<T> self, Func<T, int, bool> p)
        {
            for (int i = 0; i < self.Count; ++i)
                if (!p(self[i], i))
                    return i;
            return self.Count;
        }
        public static bool Any<T>(this IArray<T> self, Func<T, bool> p)
        {
            for (int i = 0; i < self.Count; ++i)
                if (!p(self[i]))
                    return true;
            return false;
        }
        public static bool Any(this IArray<bool> self)
        {
            return self.Any(x => x);
        }
        public static bool All<T>(this IArray<T> self, Func<T, bool> p)
        {
            return self.CountWhile(p) == self.Count;
        }
        public static bool All<T>(this IArray<T> self, Func<T, int, bool> p)
        {
            return self.CountWhile(p) == self.Count;
        }
        public static bool All(this IArray<bool> self)
        {
            return self.All(x => x);
        }
        public static bool Contains<T>(this IArray<T> self, T x)
        {
            return IndexOf(self, x) != -1;
        }
        public static bool Contains<T>(this ISortedArray<T> self, T x) where T : IComparable<T>
        {
            return IndexOf(self, x) != -1;
        }
        public static IArray<T> Suffix<T>(this IArray<T> self, int count)
        {
            var n = self.Count - count; if (n < 0) return self; else return self.Skip(n);
        }
        public static IArray<T> TakeWhile<T>(this IArray<T> self, Func<T, bool> p)
        {
            return Take(self, self.CountWhile(p));
        }
        public static IArray<T> SkipWhile<T>(this IArray<T> self, Func<T, bool> p)
        {
            return Skip(self, self.CountWhile(p));
        }
        public static IArray<T> Take<T>(this IArray<T> self, int n)
        {
            return self.Slice(0, n);
        }
        public static IArray<T> TakeHalf<T>(this IArray<T> self) 
        { 
            return self.Take(self.Count / 2);  
        }
        public static IArray<T> Skip<T>(this IArray<T> self, int n)
        {
            return self.Slice(n, self.Count);
        }
        public static IArray<T> SkipHalf<T>(this IArray<T> self) 
        { 
            return self.Skip(self.Count / 2); 
        }
        public static IArray<T> DropSuffix<T>(this IArray<T> self, int n)
        {
            return self.Take(self.Count - n);
        }
        public static Tuple<IArray<T>, IArray<T>> SplitAt<T>(this IArray<T> self, int n)
        {
            return Tuple.Create(self.Take(n), self.Skip(n));
        }
        public static bool AreSequenceEqual<T>(this IArray<T> self, IArray<T> xs)
        {
            return self.Zip(xs, (a, b) => a.Equals(b)).All();
        }
        public static int Count<T>(this IArray<T> self, Func<T, bool> p)
        {
            return self.Aggregate(0, (a, b) => a + (p(b) ? 1 : 0));
        }
        public static void ForEach<T>(this IArray<T> self, Action<T> a)
        {
            for (int i=0; i < self.Count; ++i)
                a(self[i]);
        }
        public static void ForEach<T>(this IArray<T> self, Action<T, int> a)
        {
            for (int i = 0; i < self.Count; ++i)
                a(self[i], i);
        }
        public static T Min<T>(this IArray<T> self) where T : IComparable<T>
        {
            if (self.IsEmpty()) throw new Exception();
            return self.Tail().Aggregate(self.First(), (x, y) => x.CompareTo(y) <= 0 ? x : y);
        }
        public static T Max<T>(this IArray<T> self) where T : IComparable<T>
        {
            if (self.IsEmpty()) throw new Exception();
            return self.Tail().Aggregate(self.First(), (x, y) => x.CompareTo(y) > 0 ? x : y);
        }
        public static IArray<T> Reverse<T>(this IArray<T> self)
        {
            var r = new T[self.Count];
            for (int i = 0; i < self.Count; ++i) r[self.Count - i - 1] = self[i];
            return new ArrayAdapter<T>(r);
        }
        public static IArray<IArray<T>> Group<T>(this IArray<T> self, int n)
        {
            if (n == 0) return Nil<IArray<T>>();
            return Range(self.Count / n).Select(x => self.Slice(x * n, n));
        }
        public static IArray<IArray<T>> Strides<T>(this IArray<T> self, int n)
        {
            return Range(n).Select(x => self.Stride(x, n));
        }
        public static IArray<T> SelectByIndex<T>(this IArray<T> self, IArray<int> indices)
        {
            return indices.Select(x => self[x]);
        }
        public static IArray<T> SelectByIndex<T>(this IArray<T> self, params int[] indices)
        {
            return self.SelectByIndex(indices.ToIArray());
        }
        public static IArray<V> Zip<T, U, V>(this IArray<T> self, IArray<U> xs, Func<T, U, V> f)
        {
            var cnt = (int)Math.Min(self.Count, xs.Count);
            var result = new V[cnt];
            for (int i=0; i < cnt; ++i)
                result[i] = f(self[i], xs[i]);
            return new ArrayAdapter<V>(result);
        }
        public static IArray<Tuple<T, U>> Zip<T, U>(this IArray<T> self, IArray<U> xs)
        {
            return self.Zip(xs, (x, y) => Tuple.Create(x, y));
        }
        public static int Sum(this IArray<int> self)
        {
            return self.Aggregate(0, (a, b) => a + b);
        }
        public static long Sum(this IArray<long> self)
        {
            return self.Aggregate(0L, (a, b) => a + b);
        }
        public static float Sum(this IArray<float> self)
        {
            return self.Aggregate(0.0f, (a, b) => a + b);
        }
        public static double Sum(this IArray<double> self)
        {
            return self.Aggregate(0.0, (a, b) => a + b);
        }
        public static long Dot(this IArray<int> self, IArray<int> that)
        {
            return self.Zip(that, (a, b) => (long)a * (long)b).Sum();
        }
        public static long Dot(this IArray<long> self, IArray<long> that)
        {
            return self.Zip(that, (a, b) => a * b).Sum();
        }
        public static float Dot(this IArray<float> self, IArray<float> that)
        {
            return self.Zip(that, (a, b) => a * b).Sum();
        }
        public static double Dot(this IArray<double> self, IArray<double> that)
        {
            return self.Zip(that, (a, b) => a * b).Sum();
        }
        public static double Average(this IArray<float> self)
        {
            return self.Sum() / self.Count;
        }
        public static double Average(this IArray<double> self)
        {
            return self.Sum() / self.Count;
        }
        public static int Average(this IArray<int> self)
        {
            return self.Sum() / self.Count;
        }
        public static long Average(this IArray<long> self)
        {
            return self.Sum() / self.Count;
        }
        public static bool IsEmpty<T>(this IArray<T> self)
        {
            return self.Count == 0;
        }
        public static T First<T>(this IArray<T> self)
        {
            return self[0];
        }
        public static T FirstOrDefault<T>(this IArray<T> self)
        {
            return self.IsEmpty() ? default(T) : self.First();
        }
        public static T Last<T>(this IArray<T> self)
        {
            return self[self.Count - 1];
        }
        public static T LastOrDefault<T>(this IArray<T> self)
        {
            return self.IsEmpty() ? default(T) : self.Last();
        }
        public static IArray<T> Tail<T>(this IArray<T> self)
        {
            return self.Skip(1);
        }
        public static IArray<String> ToStrings<T>(this IArray<T> self)
        {
            return self.Select(x => x.ToString());
        }
        public static Tuple<IArray<T>, IArray<T>> Partition<T>(this IArray<T> self, Func<T, bool> p)
        {
            return Tuple.Create(self.Where(p), self.Where(x => !p(x)));
        }
        public static IEnumerable<T> ToEnumerable<T>(this IArray<T> self)
        {
            for (int i = 0; i < self.Count; ++i)
                yield return self[i];
        }
        public static Tuple<IArray<T>, IArray<T>> Split<T>(this IArray<T> self, int n)
        {
            return Tuple.Create(self.Take(n), self.Skip(n));
        }
        public static Tuple<IArray<T>, IArray<T>> Split<T>(this IArray<T> self)
        {
            return self.Split(self.Count / 2);
        }
        public static IArray<int> Indices<T>(this IArray<T> self)
        {
            return Range(self.Count);
        }
        public static IArray<long> PartialSums(this IArray<int> self)
        {
            var r = new long[self.Count + 1]; r[0] = 0; for (int i = 0; i < self.Count; ++i) r[i + 1] = r[i] + self[i]; return new ArrayAdapter<long>(r);
        }
        public static IArray<int> AdjacentDifferences(this IArray<int> self)
        {
            return self.Skip(1).Zip(self.DropSuffix(1), (a, b) => a - b);
        }
        public static ISortedArray<T> OrderBy<T>(this IArray<T> self) where T : IComparable<T>
        {
            var xs = self.ToArray();
            System.Array.Sort(xs);
            return new SortedArrayAdapter<T>(new ArrayAdapter<T>(xs));
        }
        public static ISortedArray<T> OrderBy<T>(this ISortedArray<T> self) where T : IComparable<T>
        {
            return self;
        }
        public static IArrayLookup<K, T> GroupBy<T, K>(this IArray<T> self, Func<T, K> keySelector)
        {
            return self.Aggregate(new ArrayLookupBuilder<K, T>(), (gb, x) => gb.Add(keySelector(x), x)).ToLookup();
        }
        public static IArrayLookup<K, T> GroupBy<T, K>(this IArray<T> self, Func<T, int, K> keySelector)
        {
            return self.Aggregate(new ArrayLookupBuilder<K, T>(), (gb, x, i) => gb.Add(keySelector(x, i), x)).ToLookup();
        }
        public static IArrayLookup<K, U> GroupBy<T, U, K>(this IArray<T> self, Func<T, K> keySelector, Func<T, U> elementSelector)
        {
            return self.Aggregate(new ArrayLookupBuilder<K, U>(), (gb, x) => gb.Add(keySelector(x), elementSelector(x))).ToLookup();
        }
        public static IArrayLookup<K, U> GroupBy<T, U, K>(this IArray<T> self, Func<T, int, K> keySelector, Func<T, int, U> elementSelector)
        {
            return self.Aggregate(new ArrayLookupBuilder<K, U>(), (gb, x, i) => gb.Add(keySelector(x, i), elementSelector(x, i))).ToLookup();
        }
        public static IArrayLookup<T, int> ReverseLookup<T>(this IArray<T> self)
        {
            return self.GroupBy((x, i) => x, (x, i) => i);
        }
        public static IArray<R> Unzip<T0, T1, R>(this IArray<Tuple<T0, T1>> self, Func<T0, T1, R> map)
        {
            return self.Select(x => map(x.Item1, x.Item2));
        }
        public static Tuple<IArray<T0>, IArray<T1>> Unzip<T0, T1>(this IArray<Tuple<T0, T1>> self)
        {
            return Tuple.Create(self.Select(x => x.Item1), self.Select(x => x.Item2));
        }
        public static bool Equals<T>(this IArray<T> self, IArray<T> other)
        {
            return self.Zip(other, (a, b) => a.Equals(b)).All();
        }
        public static string JoinStrings<T>(this IArray<T> self, string sep = ",")
        {
            return self.Aggregate(new StringBuilder(), (sb, x, i) => (i > 0 ? sb.Append(sep) : sb).Append(x)).ToString();
        }
        public static IArray<T> RotateRight<T>(this IArray<T> self, int n)
        {
            return self.Skip(n).Concat(self.Take(n));
        }
        public static IArray<T> RotateLeft<T>(this IArray<T> self, int n)
        {
            return self.Suffix(n).Concat(self.Skip(n));
        }
        public static IArray<T> Rotate<T>(this IArray<T> self, int n)
        {
            return n < 0 ? self.RotateLeft(-n) : self.RotateRight(n);
        }
        public static IArray<T> Generate<T>(T first, Func<T, bool> invariant, Func<T, T> next)
        {
            var r = new List<T>();
            for (var i = first; invariant(i); i = next(i))
                r.Add(i);
            return new ListAdapter<T>(r);
        }
        public static List<T> ToList<T>(this IArray<T> self)
        {
            var n = self.Count;
            var r = new List<T>(n);
            for (int i = 0; i < n; ++i)
                r.Add(self[i]);
            return r;
        }
        public static bool SequenceEqual<T>(this IArray<T> xs, IArray<T> ys)
        {
            if (xs.Count != ys.Count) return false;
            int n = xs.Count;
            for (int i = 0; i < n; ++i)
                if (!xs[i].Equals(ys[i]))
                    return false;
            return true;
        }
        public static bool IsOrdered<T>(this IArray<T> xs) where T : IComparable<T>
        {
            int n = xs.Count;
            for (int i = 1; i < n; ++i)
            {
                if (xs[i].CompareTo(xs[i-1]) < 0)
                    return false;
            }
            return true;
        }
        public static bool IsOrdered<T>(this ISortedArray<T> xs) where T : IComparable<T>
        {
            return true;
        }
        public static T ElementAt<T>(this IArray<T> xs, int n) 
        {
            return xs[n];
        }
        public static int IndexOf<T>(this IArray<T> xs, T x)
        {
            int n = xs.Count;
            for (int i = 0; i < n; ++i)
                if (xs[i].Equals(x)) return i;
            return -1;
        }
        public static int IndexOf<T>(this ISortedArray<T> xs, T x) where T : IComparable<T>
        {
            var min = 0;
            var max = xs.Count;
            while (min <= max)
            {
                var mid = min + max - 2;
                var tmp = x.CompareTo(xs[mid]);
                if (tmp == 0)
                {
                    return mid;
                }
                if (tmp > 0)
                {
                    min = mid + 1;
                }
                else if (tmp < 0)
                {
                    max = mid - 1;
                }
            }
            return -1;
        }
    }
}

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

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

License

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

Share

About the Author

Christopher Diggins
Software Developer Autodesk
Canada Canada
This article was written by Christopher Diggins, a computer science nerd who currently works at Autodesk as an SDK specialist.
Follow on   Twitter   Google+   LinkedIn

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150520.1 | Last Updated 29 Dec 2012
Article Copyright 2012 by Christopher Diggins
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid