Immutable tree list implemented in C#. This is join operation based AVL tree. So that it supports fast bulk operations such as GetRange, AddRange, PushRange, RemoveRange, InsertRange and Concat. Plus, it has 'measure' field in nodes to store user-defined, bottom-up updated sub-tree property such as min, max, count, sum or stddev, or tuple of them.

MeasuredTreeList.cs

// This is free and unencumbered software released into the public domain.
// 
// Anyone is free to copy, modify, publish, use, compile, sell, or
// distribute this software, either in source code form or as a compiled
// binary, for any purpose, commercial or non-commercial, and by any
// means.
// 
// In jurisdictions that recognize copyright laws, the author or authors
// of this software dedicate any and all copyright interest in the
// software to the public domain.We make this dedication for the benefit
// of the public at large and to the detriment of our heirs and
// successors. We intend this dedication to be an overt act of
// relinquishment in perpetuity of all present and future rights to this
// software under copyright law.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
// IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
// 
// For more information, please refer to<http://unlicense.org/>

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

namespace NShibano
{
    /// <summary>
    /// Immutable tree list. Join operation based AVL tree.
    /// 
    /// Each tree node has 'value' field to store item of collection.
    /// And each tree node has 'measure' field to store property of sub-tree headed by the node,
    /// for example maximum/minimum/count/sum/average/stddev of subtree items.
    /// 
    /// The measure value for nodes are calculated at node creation using user-defined function (Func&lt;Measure, Value, Measure, Measure&gt; type),
    /// and 'zero' value (Measure type) which is corresponding to empty tree.
    /// </summary>
    public class MeasuredTreeList<Value, Measure> : IReadOnlyList<Value>
    {
        public class Node
        {
            public readonly int Height;
            public readonly int Count;
            public readonly Node Left;
            public readonly Value Value;
            public readonly Measure Measure;
            public readonly Node Right;

            public Node(int height, int count, Node left, Value value, Measure measure, Node right)
            {
                Height = height;
                Count = count;
                Left = left;
                Value = value;
                Measure = measure;
                Right = right;
            }
        }

        public static int HeightOf(Node node)
        {
            return node != null ? node.Height : 0;
        }

        public static int CountOf(Node node)
        {
            return node != null ? node.Count : 0;
        }

        public readonly Func<Measure, Value, Measure, Measure> MeasureFunc;
        public readonly Measure MeasureZero;

        public Measure MeasureOf(Node node)
        {
            return node != null ? node.Measure : MeasureZero;
        }

        Node CreateNode(Node left, Value value, Node right)
        {
            var height = Math.Max(HeightOf(left), HeightOf(right)) + 1;
            var count = CountOf(left) + 1 + CountOf(right);
            var measure = MeasureFunc(MeasureOf(left), value, MeasureOf(right));
            return new Node(height, count, left, value, measure, right);
        }

        public readonly Node Root;
        public Measure RootMeasure { get { return MeasureOf(Root); } }

        private MeasuredTreeList(Func<Measure, Value, Measure, Measure> measureFunc, Measure measureZero, Node root)
        {
            MeasureFunc = measureFunc;
            MeasureZero = measureZero;
            Root = root;
        }

        public MeasuredTreeList(Func<Measure, Value, Measure, Measure> measureFunc, Measure measureZero) : this(measureFunc, measureZero, (Node)null)
        {
        }

        public MeasuredTreeList<Value, Measure> Wrap(Node node)
        {
            return new MeasuredTreeList<Value, Measure>(MeasureFunc, MeasureZero, node);
        }

        public int Count { get { return CountOf(Root); } }

        Node GetLoop(Node node, int i)
        {
            while (true)
            {
                var left_count = CountOf(node.Left);

                if (i < left_count)
                {
                    node = node.Left;
                }
                else if (left_count < i)
                {
                    node = node.Right;
                    i = i - left_count - 1;
                }
                else
                {
                    return node;
                }
            }
        }

        public Value this[int i]
        {
            get
            {
                if (!(0 <= i && i < Count))
                    throw new IndexOutOfRangeException();

                return GetLoop(Root, i).Value;
            }
        }

        private void ToArrayLoop(Value[] ary, Node node, int i)
        {
            if (node.Left != null)
            {
                ToArrayLoop(ary, node.Left, i);
            }
            i += CountOf(node.Left);

            ary[i] = node.Value;
            i += 1;

            if (node.Right != null)
            {
                ToArrayLoop(ary, node.Right, i);
            }
        }

        public Value[] ToArray()
        {
            var ary = new Value[Count];
            if (Root != null)
            {
                ToArrayLoop(ary, Root, 0);
            }
            return ary;
        }

        public IEnumerator<Value> GetEnumerator()
        {
            return Enumerable.Range(0, Count).Select(i => this[i]).GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        /// <summary>
        /// Join two nodes (left, right) and value (center) between them. The argument nodes can be null.
        /// </summary>
        private Node Join(Node left, Value center, Node right)
        {
            var balance = HeightOf(left) - HeightOf(right);

            switch (balance)
            {
                case 0:
                case 1:
                case -1:
                    return CreateNode(left, center, right);
                case 2:
                    {
                        var leftBalance = HeightOf(left.Left) - HeightOf(left.Right);
                        if (leftBalance == -1)
                        {
                            return CreateNode(CreateNode(left.Left, left.Value, left.Right.Left), left.Right.Value, CreateNode(left.Right.Right, center, right));
                        }
                        else
                        {
                            return CreateNode(left.Left, left.Value, CreateNode(left.Right, center, right));
                        }
                    }
                case -2:
                    {
                        var rightBalance = HeightOf(right.Left) - HeightOf(right.Right);
                        if (rightBalance == 1)
                        {
                            return CreateNode(CreateNode(left, center, right.Left.Left), right.Left.Value, CreateNode(right.Left.Right, right.Value, right.Right));
                        }
                        else
                        {
                            return CreateNode(CreateNode(left, center, right.Left), right.Value, right.Right);
                        }
                    }
                default:
                    if (balance > 0)
                    {
                        return Join(left.Left, left.Value, Join(left.Right, center, right));
                    }
                    else
                    {
                        return Join(Join(left, center, right.Left), right.Value, right.Right);
                    }
            }

            throw new InvalidOperationException();
        }

        public MeasuredTreeList<Value, Measure> Add(Value x)
        {
            return Wrap(Join(Root, x, null));
        }

        public MeasuredTreeList<Value, Measure> Push(Value x)
        {
            return Wrap(Join(null, x, Root));
        }

        private Node TakeFirstLoop(Node node, int count)
        {
            if (count == 0)
            {
                return null;
            }
            else
            {
                var leftCount = CountOf(node.Left);

                if (count < leftCount)
                {
                    return TakeFirstLoop(node.Left, count);
                }
                else if (count == leftCount)
                {
                    return node.Left;
                }
                else if (count == leftCount + 1)
                {
                    return Join(node.Left, node.Value, null);
                }
                else if (count < node.Count)
                {
                    return Join(node.Left, node.Value, TakeFirstLoop(node.Right, count - CountOf(node.Left) - 1));
                }
                else if (count == node.Count)
                {
                    return node;
                }
                else
                {
                    throw new ArgumentException();
                }
            }
        }

        private Node TakeLastLoop(Node node, int count)
        {
            if (count == 0)
            {
                return null;
            }
            else
            {
                var rightCount = CountOf(node.Right);

                if (count < rightCount)
                {
                    return TakeLastLoop(node.Right, count);
                }
                else if (count == rightCount)
                {
                    return node.Right;
                }
                else if (count == rightCount + 1)
                {
                    return Join(null, node.Value, node.Right);
                }
                else if (count < node.Count)
                {
                    return Join(TakeLastLoop(node.Left, count - CountOf(node.Right) - 1), node.Value, node.Right);
                }
                else if (count == node.Count)
                {
                    return node;
                }
                else
                {
                    throw new ArgumentException();
                }
            }
        }

        /// <summary>
        /// Get new collection which contains first n items of this correction.
        /// </summary>
        public MeasuredTreeList<Value, Measure> TakeFirst(int n)
        {
            return Wrap(TakeFirstLoop(Root, n));
        }

        /// <summary>
        /// Get new collection which contains last n items of this correction.
        /// </summary>
        public MeasuredTreeList<Value, Measure> TakeLast(int n)
        {
            return Wrap(TakeLastLoop(Root, n));
        }

        Node CreateTreeFastLoop(Value[] ary, int start, int count)
        {
            switch (count)
            {
                case 0:
                    return null;
                case 1:
                    return new Node(1, 1, null, ary[start], MeasureFunc(MeasureZero, ary[start], MeasureZero), null);
                case 2:
                    {
                        var left = new Node(1, 1, null, ary[start], MeasureFunc(MeasureZero, ary[start], MeasureZero), null);
                        return new Node(2, 2, left, ary[start + 1], MeasureFunc(left.Measure, ary[start + 1], MeasureZero), null);
                    }
                case 3:
                    {
                        var left = new Node(1, 1, null, ary[start], MeasureFunc(MeasureZero, ary[start], MeasureZero), null);
                        var right = new Node(1, 1, null, ary[start + 2], MeasureFunc(MeasureZero, ary[start + 2], MeasureZero), null);
                        return new Node(2, 3, left, ary[start + 1], MeasureFunc(left.Measure, ary[start + 1], right.Measure), right);
                    }
                default:
                    {
                        var left_count = (count - 1) / 2;
                        var right_count = count - 1 - left_count;

                        var value = ary[start + left_count];
                        var left = CreateTreeFastLoop(ary, start, left_count);
                        var right = CreateTreeFastLoop(ary, start + left_count + 1, right_count);

                        return CreateNode(left, value, right);
                    }
            }
        }

        public Node CreateTreeFast(Value[] ary)
        {
            return CreateTreeFastLoop(ary, 0, ary.Length);
        }

        public MeasuredTreeList(Func<Measure, Value, Measure, Measure> measureFunc, Measure measureZero, Value[] ary) : this(measureFunc, measureZero)
        {
            Root = CreateTreeFast(ary);
        }

        public MeasuredTreeList<Value, Measure> GetRange(int start, int count)
        {
            var end = start + count;
            if (!(0 <= start && start <= Count && 0 <= count && 0 <= end && end <= Count))
            {
                throw new IndexOutOfRangeException();
            }

            return Wrap(TakeFirstLoop(TakeLastLoop(Root, Count - start), count));
        }

        private Node Concat(Node left, Node right)
        {
            var left_count = CountOf(left);

            if (left_count == 0)
            {
                return right;
            }
            else
            {
                var left_until_last = TakeFirstLoop(left, left_count - 1);
                var left_last = GetLoop(left, left_count - 1).Value;
                return Join(left_until_last, left_last, right);
            }
        }

        /// <summary>
        /// Concatenates two list. Requires two lists are created using same measure function and zero measure value.
        /// </summary>
        public static MeasuredTreeList<Value, Measure> Concat(MeasuredTreeList<Value, Measure> l1, MeasuredTreeList<Value, Measure> l2)
        {
            if (!(EqualityComparer<Func<Measure, Value, Measure, Measure>>.Default.Equals(l1.MeasureFunc, l2.MeasureFunc) &&
                  EqualityComparer<Measure>.Default.Equals(l1.MeasureZero, l2.MeasureZero)))
                throw new InvalidOperationException();

            return l1.Wrap(l1.Concat(l1.Root, l2.Root));
        }

        public MeasuredTreeList<Value, Measure> AddRange(Value[] values)
        {
            return Wrap(Concat(Root, CreateTreeFast(values)));
        }

        public MeasuredTreeList<Value, Measure> PushRange(Value[] values)
        {
            return Wrap(Concat(CreateTreeFast(values), Root));
        }

        public MeasuredTreeList<Value, Measure> RemoveRange(int start, int count)
        {
            var end = start + count;
            if (!(0 <= start && start <= Count && 0 <= count && 0 <= end && end <= Count))
            {
                throw new IndexOutOfRangeException();
            }

            return Wrap(Concat(TakeFirstLoop(Root, start), TakeLastLoop(Root, Count - (start + count))));
        }

        public MeasuredTreeList<Value, Measure> RemoveAt(int i)
        {
            if (!(0 <= i && i < Count))
                throw new IndexOutOfRangeException();

            return RemoveRange(i, 1);
        }

        public MeasuredTreeList<Value, Measure> InsertRange(int i, Value[] values)
        {
            if (!(0 <= i && i <= Count))
                throw new IndexOutOfRangeException();

            return Wrap(Concat(Concat(TakeFirstLoop(Root, i), CreateTreeFast(values)), TakeLastLoop(Root, Count - i)));
        }

        public MeasuredTreeList<Value, Measure> InsertAt(int i, Value value)
        {
            return InsertRange(i, new Value[] { value });
        }
    }

    public static class MeasuredTreeListTests
    {
        public static void Assert(bool cond)
        {
            if (!cond)
                throw new Exception();
        }

        public static void ValidateLoop<T, U>(MeasuredTreeList<T, U>.Node node)
        {
            if (node != null)
            {
                var balance = MeasuredTreeList<T, U>.HeightOf(node.Left) - MeasuredTreeList<T, U>.HeightOf(node.Right);
                Assert(Math.Abs(balance) <= 1);

                ValidateLoop(node.Left);
                ValidateLoop(node.Right);
            }
        }

        public static void Validate<T, U>(MeasuredTreeList<T, U> list)
        {
            ValidateLoop<T, U>(list.Root);
        }

        public static void Test_Construction(int n, int m)
        {
            var all = Enumerable.Range(0, n + m).ToArray();
            var left_half = Enumerable.Range(0, n).ToArray();
            var right_half = Enumerable.Range(n, m).ToArray();

            Func<int, int, int, int> measure_func = (left, x, right) => 0;

            var list1 = new MeasuredTreeList<int, int>(measure_func, 0, all);
            var list2 = new MeasuredTreeList<int, int>(measure_func, 0, left_half).AddRange(right_half);
            var list3 = new MeasuredTreeList<int, int>(measure_func, 0, right_half).PushRange(left_half);
            var list4 = MeasuredTreeList<int, int>.Concat(new MeasuredTreeList<int, int>(measure_func, 0, left_half), new MeasuredTreeList<int, int>(measure_func, 0, right_half));

            Assert(Enumerable.SequenceEqual(all, list1));
            Assert(Enumerable.SequenceEqual(all, list1.ToArray()));
            Assert(Enumerable.SequenceEqual(all, list2));
            Assert(Enumerable.SequenceEqual(all, list3));
            Assert(Enumerable.SequenceEqual(all, list4));

            Validate(list1);
            Validate(list2);
            Validate(list3);
            Validate(list4);
        }

        public static void Test1()
        {
            for (var n = 0; n < 20; n++)
            {
                for (var m = 0; m < 20; m++)
                {
                    Test_Construction(n, m);
                }
            }

            for (var n = 0; n < 1000; n++)
            {
                Test_Construction(n / 2, n - n / 2);
            }
        }

        public static void Test2()
        {
            var rand = new Random();
            var ary = Enumerable.Range(0, 100).Select(x => rand.Next()).ToArray();

            for (var i = 0; i < 100; i++)
            {
                var l1 = new List<int>(ary);
                var l2 = new MeasuredTreeList<int, long>((left_sum, x, right_sum) => left_sum + x + right_sum, 0L, ary);

                for (var j = 0; j < 10; j++)
                {
                    var remove_count = rand.Next(101);
                    var remove_pos = rand.Next(l1.Count - remove_count + 1);

                    l1.RemoveRange(remove_pos, remove_count);
                    l2 = l2.RemoveRange(remove_pos, remove_count);

                    var insert_count = remove_count;
                    var insert_items = Enumerable.Range(0, insert_count).Select(x => rand.Next()).ToArray();
                    var insert_pos = rand.Next(l1.Count + 1);

                    l1.InsertRange(insert_pos, insert_items);
                    l2 = l2.InsertRange(insert_pos, insert_items);
                }

                Validate(l2);

                Assert(Enumerable.SequenceEqual(l1, l2.ToArray()));
                Assert(l1.Select(x => (long)x).Sum() == l2.RootMeasure);
            }
        }
    }
}