ImmutableArrays

ImmutableArrays.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ImmutableArrays {
    class Program {
        static void Main() {
            const int I = 1000000;
            var sw = new Stopwatch();
            var array = new ImmutableArray<float>();
            sw.Start();
            for (var i = 0; i < I; ++i) {
                array = array.Add(i);
            }
            sw.Stop();
            Console.WriteLine(sw.ElapsedTicks);
            sw.Reset();
            var list = new List<float>();
            sw.Start();
            for (var i = 0; i < I; ++i) {
                list.Add(i);
            }
            sw.Stop();
            Console.WriteLine(sw.ElapsedTicks);
        }
    }

    class ImmutableArray<T> {
        readonly List<T[]> _arrays = new List<T[]>();
        public readonly int Length;
        public ImmutableArray() { }

        ImmutableArray(ImmutableArray<T> orig, T t) {
            _arrays = orig._arrays.ToList();
            var toAdd = new[] { t };
            for (var i = 0; i < _arrays.Count; ++i) {
                if (_arrays[i] == null) {
                    _arrays[i] = toAdd;
                    toAdd = null;
                    break;
                }
                var len = toAdd.Length;
                var toAddTemp = new T[len * 2];
                Array.Copy(_arrays[i], toAddTemp, len);
                Array.Copy(toAdd, 0, toAddTemp, len, len);
                toAdd = toAddTemp;
                _arrays[i] = null;
            }
            if (toAdd != null) {
                _arrays.Add(toAdd);
            }
            Length = orig.Length + 1;
        }


        public ImmutableArray<T> Add(T t) {
            return new ImmutableArray<T>(this, t);
        }

        public T[] ToArray() {
            var array = new T[Length];
            var tally = 0;
            for (var i = _arrays.Count-1; i >= 0; --i) {
                var t = _arrays[i];
                if (t != null) {
                    var len = t.Length;
                    Array.Copy(t, 0, array, tally, len);
                    tally += len;
                }
            }
            return array;
        }
    }
}