Morris Sequence

MorrisList.cs

using System;
using System.Collections.Generic;

namespace Morris
{
    public sealed class MorrisList : IEnumerable<byte>
    {
        private sealed class MorrisNode
        {
            public const int Size = 80000;
            public readonly byte[] Value = new byte[Size];
            public MorrisNode Next;
        }
        
        private readonly MorrisNode FirstBucket;
        private MorrisNode LastBucket;
        
        private long BucketCount;        // The total number of buckets
        private int LastBucketCount;     // The number of filled bytes in the last bucket
        private byte LastByteCount;      // The number of values in the current byte of the last bucket
        
        public MorrisList()
        {
            var node = new MorrisNode();
            FirstBucket = node;
            LastBucket = node;
            BucketCount = 1;
            LastBucketCount = 0;
            LastByteCount = 0;
        }
        
        public void Clear()
        {
            LastBucket = FirstBucket;
            LastBucketCount = 0;
            LastByteCount = 0;
            BucketCount = 1;
        }
        
        private void EnsureLastBucketCapacity()
        {
            if (LastBucketCount == MorrisNode.Size)
            {
                var node = LastBucket.Next ?? new MorrisNode();
                LastBucket.Next = node;
                LastBucket = node;
                LastBucketCount = 0;
                LastByteCount = 0;
                BucketCount++;
            }
        }
        
        public void Add(byte value)
        {
            // Argument validation removed for speed:
            // if (0 >= value || value >= 4) throw new ArgumentOutOfRangeException(nameof(value));
            
            EnsureLastBucketCapacity();
            
            switch (LastByteCount)
            {
                case 0:
                {
                    ref byte b = ref LastBucket.Value[LastBucketCount];
                    b = value;
                    LastByteCount++;
                    break;
                }
                case 1:
                {
                    ref byte b = ref LastBucket.Value[LastBucketCount];
                    b |= (byte)(value << 2);
                    LastByteCount++;
                    break;
                }
                case 2:
                {
                    ref byte b = ref LastBucket.Value[LastBucketCount];
                    b |= (byte)(value << 4);
                    LastByteCount++;
                    break;
                }
                case 3:
                {
                    ref byte b = ref LastBucket.Value[LastBucketCount];
                    b |= (byte)(value << 6);
                    LastByteCount = 0;
                    LastBucketCount++;
                    break;
                }
            }
        }
        
        public long Count 
        {
            get
            {
                long result = LastByteCount;
                if (LastBucketCount != 0)
                {
                    result += LastBucketCount * 4;
                }
                if (BucketCount != 0L)
                {
                    result += (BucketCount - 1L) * MorrisNode.Size * 4;
                }
                
                return result;
            }
        }
        
        public IEnumerator<byte> GetEnumerator()
        {
            var node = FirstBucket;
            
            while (node != LastBucket)
            {
                for (int index = 0; index < node.Value.Length; index++)
                {
                    byte b = node.Value[index];
                    yield return (byte)(b & 0b11);
                    yield return (byte)((b >> 2) & 0b11);
                    yield return (byte)((b >> 4) & 0b11);
                    yield return (byte)((b >> 6) & 0b11);
                }
                
                node = node.Next;
            }
            
            for (int index = 0; index < LastBucketCount; index++)
            {
                byte b = node.Value[index];
                yield return (byte)(b & 0b11);
                yield return (byte)((b >> 2) & 0b11);
                yield return (byte)((b >> 4) & 0b11);
                yield return (byte)((b >> 6) & 0b11);
            }
            
            if (LastByteCount != 0)
            {
                byte lastByte = node.Value[LastBucketCount];
                switch (LastByteCount)
                {
                    case 1:
                    {
                        yield return (byte)(lastByte & 0b11);
                        break;
                    }
                    case 2:
                    {
                        yield return (byte)(lastByte & 0b11);
                        yield return (byte)((lastByte >> 2) & 0b11);
                        break;
                    }
                    case 3:
                    {
                        yield return (byte)(lastByte & 0b11);
                        yield return (byte)((lastByte >> 2) & 0b11);
                        yield return (byte)((lastByte >> 4) & 0b11);
                        break;
                    }
                }
            }
        }
        
        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
        
        public override string ToString() => string.Concat(this);
    }
}

MorrisSequence.cs

using System;
using System.Collections.Generic;

namespace Morris
{
    public static class MorrisSequence
    {
        public static IEnumerable<MorrisList> Generate()
        {
            var current = new MorrisList { 1 };
            yield return current;
            
            var previous = current;
            current = new MorrisList();
            
            FillNextItem(current, previous);
            yield return current;
            
            while (true)
            {
                var temp = previous;
                previous = current;
                current = temp;
                
                FillNextItem(current, previous);
                yield return current;
            }
        }
        
        private static void FillNextItem(MorrisList result, MorrisList previous)
        {
            result.Clear();
            
            using (var enumerator = previous.GetEnumerator())
            {
                enumerator.MoveNext();
                byte number = enumerator.Current;
                byte numberCount = 1;
                
                while (enumerator.MoveNext())
                {
                    if (enumerator.Current == number)
                    {
                        numberCount++;
                    }
                    else
                    {
                        result.Add(numberCount);
                        result.Add(number);
                        
                        number = enumerator.Current;
                        numberCount = 1;
                    }
                }
                
                result.Add(numberCount);
                result.Add(number);
            }
        }
    }
}

MorrisSequenceTest.cs

using System;
using System.Linq;

namespace Morris.Tests
{
    static class MorrisSequenceTest
    {
        /* https://oeis.org/A005341/list */
        private static readonly long[] ExpectedLengths =
        {
            1,
            2,
            2,
            4,
            6,
            6,
            8,
            10,
            14,
            20,
            26,
            34,
            46,
            62,
            78,
            102,
            134,
            176,
            226,
            302,
            408,
            528,
            678,
            904,
            1182,
            1540,
            2012,
            2606,
            3410,
            4462,
            5808,
            7586,
            9898,
            12884,
            16774,
            21890,
            28528,
            37158,
            48410,
            63138,
            82350,
            107312,
            139984,
            182376,
            237746,
            310036,
            403966,
            526646,
            686646,    
        };
        
        public static void VerifyExpectedLengths()
        {
            int index = 1;
            bool success = true;
            var results = ExpectedLengths.Zip(MorrisSequence.Generate(), (l, s) => (expected: l, actual: s.Count));
            foreach (var pair in results)
            {
                if (pair.expected != pair.actual)
                {
                    Console.WriteLine($"FAIL at {index}: Expected {pair.expected}, got {pair.actual}");
                    success = false;
                }
                
                index++;
            }
            
            if (success)
            {
                Console.WriteLine("Success");
            }
        }
    }
}