<|start_filename|>src/Itc4net/StampExtensions.cs<|end_filename|>
﻿using System;

namespace Itc4net
{
    public static class StampExtensions
    {
        public static Stamp Send(this Stamp source, out Stamp anonymous)
        {
            Stamp inflated = source.Event();
            anonymous = inflated.Peek();
            return inflated;
        }

        public static (Stamp inflated, Stamp anonymous) Send(this Stamp source)
        {
            Stamp inflated = source.Event();
            Stamp anonymous = inflated.Peek();
            return (inflated, anonymous);
        }

        public static Stamp Receive(this Stamp source, Stamp other)
        {
            return source.Join(other).Event();
        }

        public static (Stamp, Stamp) Sync(this Stamp source, Stamp other)
        {
            return source.Join(other).Fork();
        }

        /// <summary>
        /// Indicates whether the source stamp is concurrent with the other stamp.
        /// </summary>
        /// <param name="source">The source.</param>
        /// <param name="other">The other, for comparison.</param>
        /// <returns><c>true</c> if ¬(a.leq(b)) and ¬(b.leq(a)); otherwise, <c>false</c>.</returns>
        public static bool Concurrent(this Stamp source, Stamp other)
        {
            return !source.Leq(other) && !other.Leq(source);
        }

        /// <summary>
        /// Indicates whether the source stamp is equivalent (causally equal) with the other stamp.
        /// </summary>
        /// <param name="source">The source.</param>
        /// <param name="other">The other, for comparison.</param>
        /// <returns><c>true</c> if a.leq(b) Λ b.leq(a); otherwise <c>false</c>.</returns>
        public static bool Equivalent(this Stamp source, Stamp other)
        {
            return source.Leq(other) && other.Leq(source);
        }

        /// <summary>
        /// Fork a stamp into 3 distinct stamps (returns a 3-tuple)
        /// </summary>
        /// <param name="source">The source stamp.</param>
        /// <returns>A 3-tuple, each with a unique identity and a copy of the causal history.</returns>
        /// <remarks>
        /// A convenience method for forking 1 stamp into 3 unique stamps.
        /// </remarks>
        public static (Stamp, Stamp, Stamp) Fork3(this Stamp source)
        {
            (Stamp, Stamp) fork = source.Fork();
            Stamp a = fork.Item1;
            Stamp c = fork.Item2;

            (Stamp, Stamp) fork1 = a.Fork();
            a = fork1.Item1;
            Stamp b = fork1.Item2;

            return (a, b, c);
        }

        /// <summary>
        /// Fork a stamp into 4 distinct stamps (returns a 4-tuple)
        /// </summary>
        /// <param name="source">The source stamp.</param>
        /// <returns>A 4-tuple, each with a unique identity and a copy of the causal history.</returns>
        /// <remarks>
        /// A convenience method for forking 1 stamp into 4 unique stamps.
        /// </remarks>
        public static (Stamp, Stamp, Stamp, Stamp) Fork4(this Stamp source)
        {
            (Stamp, Stamp) fork = source.Fork();
            Stamp a = fork.Item1;
            Stamp c = fork.Item2;

            (Stamp, Stamp) fork1 = a.Fork();
            a = fork1.Item1;
            Stamp b = fork1.Item2;

            (Stamp, Stamp) fork2 = c.Fork();
            c = fork2.Item1;
            Stamp d = fork2.Item2;

            return (a, b, c, d);
        }

        /// <summary>
        /// Fork a stamp into 2 distinct stamps (as out parameters)
        /// </summary>
        /// <param name="source">The source stamp.</param>
        /// <param name="s1">1st stamp with a unique identity and a copy of the causal history.</param>
        /// <param name="s2">2nd stamp with a unique identity and a copy of the causal history.</param>
        /// <remarks>
        /// A convenience method when out parameters are preferred over a return 2-tuple.
        /// </remarks>
        public static void Fork(this Stamp source, out Stamp s1, out Stamp s2)
        {
            var forked = source.Fork();
            s1 = forked.Item1;
            s2 = forked.Item2;
        }

        /// <summary>
        /// Fork a stamp into 3 distinct stamps (as out parameters)
        /// </summary>
        /// <param name="source">The source stamp.</param>
        /// <param name="s1">1st stamp with a unique identity and a copy of the causal history.</param>
        /// <param name="s2">2nd stamp with a unique identity and a copy of the causal history.</param>
        /// <param name="s3">3rd stamp with a unique identity and a copy of the causal history.</param>
        /// <remarks>
        /// A convenience method when out parameters are preferred over a return 3-tuple.
        /// </remarks>
        public static void Fork(this Stamp source, out Stamp s1, out Stamp s2, out Stamp s3)
        {
            var forked = source.Fork3();
            s1 = forked.Item1;
            s2 = forked.Item2;
            s3 = forked.Item3;
        }

        /// <summary>
        /// Fork a stamp into 4 distinct stamps (as out parameters)
        /// </summary>
        /// <param name="source">The source stamp.</param>
        /// <param name="s1">1st stamp with a unique identity and a copy of the causal history.</param>
        /// <param name="s2">2nd stamp with a unique identity and a copy of the causal history.</param>
        /// <param name="s3">3rd stamp with a unique identity and a copy of the causal history.</param>
        /// <param name="s4">4th stamp with a unique identity and a copy of the causal history.</param>
        /// <remarks>
        /// A convenience method when out parameters are preferred over a return 4-tuple.
        /// </remarks>
        public static void Fork(this Stamp source, out Stamp s1, out Stamp s2, out Stamp s3, out Stamp s4)
        {
            var forked = source.Fork4();
            s1 = forked.Item1;
            s2 = forked.Item2;
            s3 = forked.Item3;
            s4 = forked.Item4;
        }
    }
}

<|start_filename|>src/Itc4net.Tests/ScenarioTests.cs<|end_filename|>
﻿using System;
using FluentAssertions;
using NUnit.Framework;

namespace Itc4net.Tests
{
    /// <summary>
    /// This test fixture includes examples of using interval tree clock timestamps
    /// for causality tracking in different scenarios (e.g., version vectors and vector
    /// clocks). These are far from *unit* tests, but test assertions are handy for illustrating
    /// expectations throughout the scenarios.
    /// </summary>
    [TestFixture]
    public class ScenarioTests
    {
        // Example from ITC 2008 paper, section 5.1
        //
        //                                    e
        //                             a3-----------a4----------+
        //                            /                          \                 
        //                e          /                            \          e       
        //            a1-----a2-----f                              j-----a5-----a6    
        //           /               \                            /
        //          /                 \                          /
        //         /                   c1---+              c3---+                  
        //  seed--f                          \            /
        //         \                          \          /
        //          \                          j--------f
        //           \                        /  (sync)  \
        //            \                      /            \
        //             b1-----b2-----b3-----+              b4                     
        //                 e      e
        //
        [Test(Description = "Example from ITC 2008 paper, section 5.1")]
        public void Itc2008Example()
        {
            // Start with seed stamp
            Stamp seed = new Stamp();
            seed.Should().Be(new Stamp(1, 0));

            // Fork seed stamp to create stamps for process A and B
            (Stamp a1, Stamp b1) = seed.Fork();
            a1.Should().Be(new Stamp(new Id.Node(1, 0), 0));
            b1.Should().Be(new Stamp(new Id.Node(0, 1), 0));

            // Process A suffers an event
            Stamp a2 = a1.Event();
            a2.Should().Be(new Stamp(new Id.Node(1, 0), new Event.Node(0, 1, 0)));

            // Process A forks to create stamp for new process C (dynamic number of participants)
            (Stamp a3, Stamp c1) = a2.Fork();
            a3.Should().Be(new Stamp(new Id.Node(new Id.Node(1, 0), 0), new Event.Node(0, 1, 0)));
            c1.Should().Be(new Stamp(new Id.Node(new Id.Node(0, 1), 0), new Event.Node(0, 1, 0)));

            // Process A suffers an event
            Stamp a4 = a3.Event();
            a4.Should().Be(new Stamp(new Id.Node(new Id.Node(1, 0), 0), new Event.Node(0, new Event.Node(1, 1, 0), 0)));

            // Process B suffers an event
            Stamp b2 = b1.Event();
            b2.Should().Be(new Stamp(new Id.Node(0, 1), new Event.Node(0, 0, 1)));

            // Process B suffers an event
            Stamp b3 = b2.Event();
            b3.Should().Be(new Stamp(new Id.Node(0, 1), new Event.Node(0, 0, 2)));

            // Process B and C synchronize (join and fork)
            (Stamp c3, Stamp b4) = b3.Sync(c1);
            c3.Should().Be(new Stamp(new Id.Node(new Id.Node(0, 1), 0), new Event.Node(1, 0, 1)));
            b4.Should().Be(new Stamp(new Id.Node(0, 1), new Event.Node(1, 0, 1)));

            // Process C retires and joins with process A
            Stamp a5 = a4.Join(c3);
            a5.Should().Be(new Stamp(new Id.Node(1, 0), new Event.Node(1, new Event.Node(0, 1, 0), 1)));

            // Process A suffers an event (inflates and simplifies to single integer event)
            Stamp a6 = a5.Event();
            a6.Should().Be(new Stamp(new Id.Node(1,0), 2));
        }

        // Example from ITC 2008 paper, section 5.1
        //
        //                                    e
        //                             a3-----------a4----------+
        //                            /                          \                 
        //                e          /                            \          e       
        //            a1-----a2-----f                              j-----a5-----a6    
        //           /               \                            /
        //          /                 \                          /
        //         /                   c1---+              c3---+                  
        //  seed--f                          \            /
        //         \                          \          /
        //          \                          j--------f
        //           \                        /  (sync)  \
        //            \                      /            \
        //             b1-----b2-----b3-----+              b4                     
        //                 e      e
        //
        [Test(Description = "Example from ITC 2008 paper, section 5.1 (with implicit conversion)")]
        public void Itc2008ExampleWithImplicitConversionOperators()
        {
            // Start with seed stamp
            Stamp seed = new Stamp();
            seed.Should().Be((1, 0));

            // Fork seed stamp to create stamps for process A and B
            (Stamp a1, Stamp b1) = seed.Fork();
            a1.Should().Be(((1, 0), 0));
            b1.Should().Be(((0, 1), 0));

            // Process A suffers an event
            Stamp a2 = a1.Event();
            a2.Should().Be(((1, 0), (0, 1, 0)));

            // Process A forks to create stamp for new process C (dynamic number of participants)
            (Stamp a3, Stamp c1) = a2.Fork();
            a3.Should().Be((((1, 0), 0), (0, 1, 0)));
            c1.Should().Be((((0, 1), 0), (0, 1, 0)));

            // Process A suffers an event
            Stamp a4 = a3.Event();
            a4.Should().Be((((1, 0), 0), (0, (1, 1, 0), 0)));

            // Process B suffers an event
            Stamp b2 = b1.Event();
            b2.Should().Be(((0, 1), (0, 0, 1)));

            // Process B suffers an event
            Stamp b3 = b2.Event();
            b3.Should().Be(((0, 1), (0, 0, 2)));

            // Process B and C synchronize (join and fork)
            (Stamp c3, Stamp b4) = b3.Sync(c1);
            c3.Should().Be((((0, 1), 0), (1, 0, 1)));
            b4.Should().Be(((0, 1), (1, 0, 1)));

            // Process C retires and joins with process A
            Stamp a5 = a4.Join(c3);
            a5.Should().Be(((1, 0), (1, (0, 1, 0), 1)));

            // Process A suffers an event (inflates and simplifies to single integer event)
            Stamp a6 = a5.Event();
            a6.Should().Be(((1, 0), 2));
        }

        [Test]
        public void OrderingOfEventsExample()
        {
            //         ^            ^ time ↑
            //         |            |
            // evt p3  *            |
            //         |            |
            // rcv p2  *---+    +---* q2 rcv
            //         |    \  /    |
            //         |     \/     |
            //         |     /\     |
            //         |    /  \    |
            // rcv p1  *---+    +---* q1 snd
            //         |            |

            Stamp seed = new Stamp();

            (Stamp, Stamp) fork = seed.Fork();
            Process p = new Process("p", fork.Item1);
            Process q = new Process("q", fork.Item2);

            Message msgp1 = p.Send("p1");
            Stamp p1 = p.CurrentStamp;
            Console.WriteLine($"p1:{p1} after send");

            Message msgq1 = q.Send("q1");
            Stamp q1 = q.CurrentStamp;
            Console.WriteLine($"q1:{q1} after send");

            Stamp p2 = p.Receive(msgq1);
            Console.WriteLine($"p2:{p2} after receive");

            Stamp q2 = q.Receive(msgp1);
            Console.WriteLine($"q1:{q1} after receive");

            Stamp p3 = p.Increment();
            Console.WriteLine($"p3:{p3} after event");

            p1.Leq(p2).Should().BeTrue();
            p1.Leq(p3).Should().BeTrue();
            p2.Leq(p3).Should().BeTrue();

            q1.Leq(q2).Should().BeTrue();

            p1.Leq(q2).Should().BeTrue(); // send occurs before receive
            q1.Leq(p2).Should().BeTrue(); // send occurs before receive

            p1.Concurrent(q1).Should().BeTrue();
            p2.Concurrent(q2).Should().BeTrue();
            p3.Concurrent(q2).Should().BeTrue();

            // Stamp implements IComparable<Stamp> so a collection of stamps
            // can be partially ordered using Sort methods. Note this is a
            // partial order (not total order) as CompareTo returns 0
            // for equal and concurrent stamps. 

            var arr = new[] {q2, q1, p3, p2, p1};
            Array.Sort(arr);

            arr.Should().ContainInOrder(p1, p2, p3);
            arr.Should().ContainInOrder(q1, q2);
            arr.Should().ContainInOrder(p1, q2);
            arr.Should().ContainInOrder(q1, p2, p3);
        }

        [Test(Description = "Example from Detection of Mutual Inconsistency in Distributed Systems, Fig. 1")]
        public void DetectionOfMutualInconsistencyExample()
        {
            // Source http://zoo.cs.yale.edu/classes/cs426/2013/bib/parker83detection.pdf
            // Fig. 1. Partition graph G(f) for file stored redundantly at sites A, B, C, D.
            //
            //                   +------+
            //          +--------+ ABCD +-------+
            //          |        +------+       |
            //          |                       |
            //        +-v--+                  +-v--+
            //     *1 | AB +-------+  +-------+ CD +-------+
            //        +----+       |  |       +----+       |
            //          |         +v--v+                 +-v-+
            //          |      *2 | BC |                 | D |
            //          |         +----+                 +---+
            //          |            |                     |
            //        +-v-+          |        +-----+      |
            //     *3 | A |          +--------> BCD <------+
            //        +---+                   +-----+
            //          |                        |
            //          |     *4 +------+        |
            //          +--------> ABCD <--------+
            //                   +------+
            //
            // [*#] indicates modification to file

            // Fork seed stamp into four "sites"
            Stamp a, b, c, d;
            new Stamp().Fork(out a, out b, out c, out d);
            Console.WriteLine($"Site A: {a}");
            Console.WriteLine($"Site B: {b}");
            Console.WriteLine($"Site C: {c}");
            Console.WriteLine($"Site D: {d}");

            Stamp fileStampOnA = a.Peek();
            Console.WriteLine($"Initial file A stamp: {fileStampOnA}");

            Stamp fileStampOnB = b.Peek();
            Console.WriteLine($"Initial file B stamp: {fileStampOnB}");

            Stamp fileStampOnC = c.Peek();
            Console.WriteLine($"Initial file C stamp: {fileStampOnC}");

            Stamp fileStampOnD = d.Peek();
            Console.WriteLine($"Initial file D stamp: {fileStampOnD}");

            // Due to network partitions, clusters of sites are isolated from others at
            // various times.

            // A and B can communicate (forming {AB} partition), but are isolated from C and D
            // C and D can communicate (forming {CD} partition), but are isolated from A and B

            // File is modified at site A in {AB} partition
            a = a.Event();
            fileStampOnA = a.Peek(); // update file metadata
            Console.WriteLine($"File modified on A: {fileStampOnA}");

            // Site A notifies site B about the change to the file
            Console.WriteLine("Sync A->B");
            b.Concurrent(fileStampOnA).Should().BeFalse();
            b = b.Join(fileStampOnA);
            fileStampOnB = b.Peek(); // update file metadata
            Console.WriteLine($"File synced on B: {fileStampOnB}");

            // A and B become isolated from each other
            // C and D become isolated from each other

            // B and C resume communication, forming {BC} partition
            // Site B notifies site C about the previous change to the file
            Console.WriteLine("Sync B->C");
            c.Concurrent(fileStampOnB).Should().BeFalse();
            c = c.Join(fileStampOnB);
            fileStampOnC = c.Peek(); // update file metadata
            Console.WriteLine($"File synced on C: {fileStampOnC}");

            // File is modified at site C in {BC} partition
            c = c.Event();
            fileStampOnC = c.Peek(); // update file metadata
            Console.WriteLine($"File modified on C: {fileStampOnC}");

            // Site C shares the change with site B
            // There should not be a conflict (concurrent stamp) between B and C.
            Console.WriteLine("Sync C->B");
            b.Concurrent(fileStampOnC).Should().BeFalse();
            b = b.Join(fileStampOnC);
            fileStampOnB = b.Peek(); // update file metadata
            Console.WriteLine($"File synced on B: {fileStampOnB}");

            // File is modified at site A in {A} partition
            a = a.Event();
            fileStampOnA = a.Peek();
            Console.WriteLine($"File modified on A: {fileStampOnA}");

            // B, C, and D resume communication, forming {BCD} partition
            // Since they can now communicate with each other, B and C share information
            // about the modified file with D
            Console.WriteLine("Sync C->D");
            d.Concurrent(fileStampOnC).Should().BeFalse();
            d = d.Join(fileStampOnC);
            fileStampOnD = d.Peek(); // updates file metadata
            Console.WriteLine($"File synced on D: {fileStampOnD}");

            Console.WriteLine("Sync B->D");
            d.Concurrent(fileStampOnB).Should().BeFalse();
            d = d.Join(fileStampOnB);
            fileStampOnD = d.Peek(); // updates file metadata
            Console.WriteLine($"File synced on D: {fileStampOnD}");

            // A, B, C, and D again establish communication and share information
            // about the file changes
            //
            // There should be a conflict (concurrent stamps) between A and the
            // other sites: B, C, and D
            a.Concurrent(fileStampOnB).Should().BeTrue();
            a.Concurrent(fileStampOnC).Should().BeTrue();
            a.Concurrent(fileStampOnD).Should().BeTrue();

            // The concurrent stamps indicate there is a conflict which must
            // be resolved (manual or otherwise). Once the conflict is resolved
            // the updated file is stored and a new stamp must be generated that
            // dominates the others... this can be done by joining the stamps from
            // the (previously) concurrent stamps and inflating the stamp at A.
            a = a.Join(fileStampOnB);
            a = a.Join(fileStampOnC);
            a = a.Join(fileStampOnD);
            a = a.Event(); // inflate for conflict resolution
            fileStampOnA = a.Peek(); // update file metadata
            Console.WriteLine($"Resolve conflict on A: {fileStampOnA}");

            // Site A communicates conflict resolution to other sites
            Console.WriteLine("Sync A->B");
            b.Concurrent(fileStampOnA).Should().BeFalse();
            b = b.Join(fileStampOnA);
            fileStampOnB = b.Peek();
            Console.WriteLine($"File synced on B: {fileStampOnB}");

            Console.WriteLine("Sync A->C");
            c.Concurrent(fileStampOnA).Should().BeFalse();
            c = c.Join(fileStampOnA);
            fileStampOnC = c.Peek();
            Console.WriteLine($"File synced on C: {fileStampOnC}");

            Console.WriteLine("Sync A->D");
            d.Concurrent(fileStampOnA).Should().BeFalse();
            d = d.Join(fileStampOnA);
            fileStampOnD = d.Peek();
            Console.WriteLine($"File synced on D: {fileStampOnD}");
        }
    }

    class Message
    {
        public string Text { get; }
        public Stamp Stamp { get; }

        public Message(string text, Stamp stamp)
        {
            Text = text;
            Stamp = stamp;
        }
    }

    class Process
    {
        readonly string _name;
        Stamp _s;

        public Process(string name, Stamp s)
        {
            _name = name;
            _s = s;
        }

        public Stamp CurrentStamp => _s.Peek();

        public Message Send(string text)
        {
            Stamp anonymous;
            _s = _s.Send(out anonymous);

            Message msg = new Message(text, anonymous);

            // e.g., _bus.Send(message);
            Console.WriteLine($"{_name} snd '{msg.Text}' with stamp:{msg.Stamp}");
            return msg;
        }

        public Stamp Receive(Message msg)
        {
            // e.g., _bus.Receive(message);
            _s = _s.Receive(msg.Stamp);
            Console.WriteLine($"{_name} rcv '{msg.Text}' with stamp:{msg.Stamp}");
            return CurrentStamp;
        }

        public Stamp Increment()
        {
            _s = _s.Event();
            return CurrentStamp;
        }
    }
}


<|start_filename|>src/Itc4net.Tests/Binary/DecoderTests.cs<|end_filename|>
﻿using System;
using FluentAssertions;
using Itc4net.Binary;
using NUnit.Framework;

namespace Itc4net.Tests.Binary
{
    [TestFixture]
    public class DecoderTests
    {
        Decoder _decoder;

        [SetUp]
        public void SetUp()
        {
            _decoder = new Decoder();
        }

        [TearDown]
        public void TearDown()
        {
            _decoder.Dispose();
        }

        [Test]
        public void DecodeShouldReturnStampForEncodedSeedStamp()
        {
            // Arrange
            byte[] bytes = { 0x30 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp());
        }

        [Test]
        public void DecodeShouldReturnStampForEncodedAnonymousStampWithZeroEventLeaf()
        {
            // Arrange
            byte[] bytes = { 0x10 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(0, 0));
        }

        [Test]
        public void DecodeShouldReturnStampForEncodedIdNode0I()
        {
            // Arrange
            byte[] bytes = { 0x4C, 0x00 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(new Id.Node(0, 1), 0));
        }

        [Test]
        public void DecodeShouldReturnStampForEncodedIdNodeI0()
        {
            // Arrange
            byte[] bytes = { 0x8C, 0x00 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(new Id.Node(1, 0), 0));
        }

        [Test]
        public void DecodeShouldReturnStampForEncodedIdNode1001()
        {
            // Arrange
            byte[] bytes = { 0xE2, 0x98 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(new Id.Node(new Id.Node(1, 0), new Id.Node(0, 1)), 0));
        }

        [Test]
        public void DecodeShouldReturnStampForEncodedEventNode00E()
        {
            // Arrange
            byte[] bytes = { 0x02, 0x40 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(0, new Event.Node(0, 0, 1)));
        }

        [Test]
        public void DecodeShouldReturnStampForEncodedEventNode0E0()
        {
            // Arrange
            byte[] bytes = { 0x06, 0x40 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(0, new Event.Node(0, 1, 0)));
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void DecodeShouldReturnStampForEncodedEventNode0EEWithNestedEventLeaf()
        {
            // Arrange
            byte[] bytes = { 0x0A, 0x64 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(0, new Event.Node(0, 1, 1)));
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void DecodeShouldReturnStampForEncodedEventNode0EEWithNestedEventNode()
        {
            // Arrange
            byte[] bytes = { 0x08, 0xCC, 0x80 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(0, new Event.Node(0, new Event.Node(0, 1, 0), 1)));
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void DecodeShouldReturnStampForEncodedEventNodeN0E()
        {
            // Arrange
            byte[] bytes = { 0x0C, 0x99 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(0, new Event.Node(1, 0, 1)));
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void DecodeShouldReturnStampForEncodedEventNodeNE0()
        {
            // Arrange
            byte[] bytes = { 0x0D, 0x99 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(0, new Event.Node(1, 1, 0)));
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void DecodeShouldReturnStampForEncodedEventNodeNEE()
        {
            // Arrange
            byte[] bytes = { 0x0F, 0x32, 0xDB, 0x90 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(0, new Event.Node(1, 1, new Event.Node(3, 1, 0))));
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void DecodeShouldReturnStampForEncodedEventNodeWithLargeNCase17()
        {
            // Arrange
            byte[] bytes = { 0x1C, 0xA0 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(0, 17));
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void DecodeShouldReturnStampForEncodedEventNodeWithLargeNCase258()
        {
            // Arrange
            byte[] bytes = { 0x1F, 0xC0, 0xC0 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(0, 258));
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void DecodeShouldReturnStampForEncodedEventNodeWithLargeNCase513()
        {

            // Arrange
            byte[] bytes = { 0x1F, 0xE0, 0x28 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            // Arrange
            s.Should().Be(new Stamp(0, 513));
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void DecodeShouldReturnStampForEncodedEventNodeWithLargeNCase21474836()
        {

            // Arrange
            byte[] bytes = { 0x1F, 0xFF, 0xFF, 0xC8, 0xF5, 0xC3, 0x00 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            // Arrange
            s.Should().Be(new Stamp(0, 21474836));
        }

        [Test]
        public void DecodeShouldReturnStampForEncodedStampWithIdNode10AndEventNode110()
        {
            // Arrange
            byte[] bytes = { 0x8B, 0x66, 0x40 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(new Id.Node(1, 0), new Event.Node(1, 1, 0)));
        }

        [Test]
        public void DecodeShouldReturnStampForEncodedStampWithIdNode01AndEventNode110()
        {
            // Arrange
            byte[] bytes = { 0x4B, 0x66, 0x40 };

            // Act
            Stamp s = _decoder.Decode(bytes);

            // Assert
            s.Should().Be(new Stamp(new Id.Node(0, 1), new Event.Node(1, 1, 0)));
        }

        [Test]
        public void DecodeShouldThrowWhenNull()
        {
            Action act = () => _decoder.Decode(null);

            act.ShouldThrow<ArgumentNullException>();
        }

        [Test]
        public void DecodeShouldThrowWhenEmpty()
        {
            Action act = () => _decoder.Decode(new byte[0]);

            act.ShouldThrow<DecoderException>().Where(
                e => e.Position == 0 // 0-based index for decoder
                && e.Expecting == null
                && e.Found == BitProcessor.EndOfStream);
        }

        [Test]
        public void DecodeShouldThrowWhenUnexpectedlyReachingEndOfStream()
        {
            // 00000000
            // ^^^      ~~> i 0
            //    ^^^   ~~> e with structure (0,0,er)
            //
            Action act = () => _decoder.Decode(new byte[] { 0x00 });

            act.ShouldThrow<DecoderException>().Where(
                e => e.Position == 8
                && e.Expecting == null
                && e.Found == BitProcessor.EndOfStream);
        }
    }
}


<|start_filename|>src/Itc4net/Binary/BitWriterExtensions.cs<|end_filename|>
﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace Itc4net.Binary
{
    static class BitWriterExtensions
    {
        public static void EncodeN(this BitWriter writer, int n)
        {
            if (writer == null) throw new ArgumentNullException(nameof(writer));

            writer.WriteBits(1, 1);
            writer.EncodeN(n, 2);
        }

        static void EncodeN(this BitWriter writer, int n, int b)
        {
            if (writer == null) throw new ArgumentNullException(nameof(writer));

            long twoB = (long)Math.Pow(2, b);

            if (n < twoB)
            {
                writer.WriteBits(0, 1);

                if (b <= 8)
                {
                    writer.WriteBits((byte)n, b);
                }
                else
                {
                    // The current implementation of BitWriter currently only supports
                    // writing 0-8 bits at a time. I may fix this in the future, but
                    // until then, just break writing 'n' into multiple writes.
                    int remainder;
                    int quotient = Math.DivRem(b, 8, out remainder);

                    if (remainder > 0)
                    {
                        byte value = (byte) ((n >> (8 * quotient)) & 0x000000FF);
                        writer.WriteBits(value, remainder);
                    }

                    for (int index = quotient - 1; index >= 0; index--)
                    {
                        byte value = (byte)((n >> (8 * index)) & 0x000000FF);
                        writer.WriteBits(value, 8);
                    }
                }
            }
            else
            {
                writer.WriteBits(1, 1);
                writer.EncodeN((int) (n - twoB), b + 1);
            }
        }
    }
}


<|start_filename|>src/Itc4net/Text/Scanner.cs<|end_filename|>
using System;
using System.IO;
using System.Text;

namespace Itc4net.Text
{
    /// <summary>
    /// A simple ITC stamp scanner (tokenizer)
    /// </summary>
    class Scanner
    {
        const int EndOfString = -1;
        readonly StringBuilder _lexeme = new StringBuilder();
        int _char;
        TokenKind _kind = TokenKind.Error;
        readonly CharEnumerator _enumerator;
        int _currentPosition;

        public Scanner(string text)
        {
            _enumerator = text.GetEnumerator();
            NextChar();
        }

        public Token Scan()
        {
            int startPosition = _currentPosition;
            _lexeme.Clear();
            _kind = ScanToken();
            int endPosition = _currentPosition;
            return new Token(_kind, _lexeme.ToString(), startPosition, endPosition);
        }

        void NextChar()
        {
            _currentPosition++;
            if (_enumerator.MoveNext())
            {
                _char = _enumerator.Current;
            }
            else
            {
                _char = EndOfString;
            }
        }

        void Take()
        {
            _lexeme.Append((char) _char);
            NextChar();
        }

        TokenKind ScanToken()
        {
            TokenKind result;

            // ignore whitespace
            while (char.IsWhiteSpace((char) _char))
            {
                NextChar();
            }

            if (char.IsNumber((char) _char))
            {
                result = ScanNumber();
            }
            else
            {
                switch (_char)
                {
                    case '(':
                        Take();
                        result = TokenKind.LParen;
                        break;
                    case ')':
                        Take();
                        result = TokenKind.RParen;
                        break;
                    case ',':
                        Take();
                        result = TokenKind.Comma;
                        break;
                    case EndOfString:
                        Take();
                        result = TokenKind.EndOfText;
                        break;
                    default:
                        result = TokenKind.Error;
                        break;
                }
            }
            return result;
        }

        TokenKind ScanNumber()
        {
            TokenKind result = TokenKind.Error;
            if (char.IsDigit((char) _char))
            {
                TakeDecimalDigits();
                result = TokenKind.IntegerLiteral;
            }
            return result;
        }

        void TakeDecimalDigits()
        {
            while (char.IsDigit((char) _char))
            {
                Take();
            }
        }
    }
}

<|start_filename|>src/Itc4net/Binary/BitProcessor.cs<|end_filename|>
using System;
using System.IO;

namespace Itc4net.Binary
{
    abstract class BitProcessor : IDisposable
    {
        public const int EndOfStream = -1;
        readonly Stream _stream;
        readonly bool _leaveOpen;
        bool _disposed;

        protected BitProcessor(Stream stream) : this(stream, false)
        {
        }

        protected BitProcessor(Stream stream, bool leaveOpen)
        {
            _stream = stream;
            _leaveOpen = leaveOpen;
        }

        protected Stream BaseStream => _stream;
        protected int RelativePosition { get; set; }
        protected int CurrentByte { get; set; }

        /// <summary>
        /// Creates a mask with the specified number of 1 bits (from the least-significant bits)
        /// </summary>
        /// <param name="bits">A count of the number of bits.</param>
        /// <returns>System.Byte.</returns>
        protected static byte CreateMask(int bits)
        {
            switch (bits)
            {
                case 0:
                    return 0x00;
                case 1:
                    return 0x01;
                case 2:
                    return 0x03;
                case 3:
                    return 0x07;
                case 4:
                    return 0x0F;
                case 5:
                    return 0x1F;
                case 6:
                    return 0x3F;
                case 7:
                    return 0x7F;
                case 8:
                    return 0xFF;
                default:
                    throw new ArgumentOutOfRangeException(nameof(bits), bits, "Must be between 0 and 8 (inclusive).");
            }
        }

        /// <summary>
        /// Closes the stream.
        /// </summary>
        public void Close()
        {
            Dispose();
        }

        /// <summary>
        /// Performs application-defined tasks associated with freeing, releasing, or
        /// resetting unmanaged resources.
        /// </summary>
        public void Dispose()
        {
            Dispose(true);
            GC.SuppressFinalize(this);
        }

        /// <summary>
        /// Finalizes an instance of the <see cref="BitWriter"/> class.
        /// </summary>
        ~BitProcessor()
        {
            Dispose(false);
        }

        /// <summary>
        /// Releases unmanaged and managed resources.
        /// </summary>
        /// <param name="disposing"><c>true</c> to release both managed and unmanaged resources;
        /// <c>false</c> to release only unmanaged resources.
        /// </param>
        protected virtual void Dispose(bool disposing)
        {
            if (!_disposed)
            {
                if (disposing)
                {
                    if (_leaveOpen)
                    {
                        _stream.Flush();
                    }
                    else
                    {
                        _stream.Dispose();
                    }
                }

                // release any unmanaged objects
                // set the object references to null

                _disposed = true;
            }
        }
    }
}

<|start_filename|>src/Itc4net/Text/ParserException.cs<|end_filename|>
using System;
using System.Runtime.Serialization;

namespace Itc4net.Text
{
    [Serializable]
    public class ParserException : Exception
    {
        public TokenKind? Expecting { get; }
        public TokenKind Found { get; }
        public int Position { get; }

        public ParserException(string message) : base(message) {}

        public ParserException(string message, TokenKind? expecting, TokenKind found, int position) : base(message)
        {
            Expecting = expecting;
            Found = found;
            Position = position;
        }

        protected ParserException(SerializationInfo info, StreamingContext context) : base(info, context)
        {
        }
    }
}

<|start_filename|>src/Itc4net/Text/Token.cs<|end_filename|>
using System;

namespace Itc4net.Text
{
    class Token
	{
	    public TokenKind Kind { get; }
	    public string Lexeme { get; }
	    public int StartPosition { get; }
        public int EndPosition { get; }

        public Token(TokenKind kind, string lexeme, int startPosition, int endPosition)
		{
			Kind = kind;
			Lexeme = lexeme;
		    StartPosition = startPosition;
		    EndPosition = endPosition;
		}
	}
}


<|start_filename|>src/Itc4net.Tests/Text/ParserTests.cs<|end_filename|>
﻿using System;
using FluentAssertions;
using Itc4net.Text;
using NUnit.Framework;

namespace Itc4net.Tests.Text
{
    [TestFixture]
    public class ParserTests
    {
        [Test]
        public void ParseStampShouldReturnStampWhenLeafIdAndLeafEvent()
        {
            Stamp s = Stamp.Parse("(1,0)");

            s.Should().Be(new Stamp(1, 0));
        }

        [Test]
        public void ParseStampShouldReturnStampWhenNodeIdAndLeafEvent()
        {
            Stamp s = Stamp.Parse("((1,0),0)");

            s.Should().Be(new Stamp(new Id.Node(1, 0), 0));
        }

        [Test]
        public void ParseStampShouldReturnStampWhenNestedNodeIdAndLeafEvent()
        {
            Stamp s = Stamp.Parse("((1,(1,0)),0)");

            s.Should().Be(new Stamp(new Id.Node(1, new Id.Node(1, 0)), 0));
        }

        [Test]
        public void ParseStampShouldReturnStampWhenLeafIdAndNodeEvent()
        {
            Stamp s = Stamp.Parse("(1,(1,0,0))");

            s.Should().Be(new Stamp(1, new Event.Node(1, 0, 0)));
        }

        [Test]
        public void ParseStampShouldReturnStampWhenLeafIdAndNestedNodeEvent()
        {
            Stamp s = Stamp.Parse("(1,(1,0,(0,2,0)))");

            s.Should().Be(new Stamp(1, new Event.Node(1, 0, new Event.Node(0, 2, 0))));
        }

        [Test]
        public void ParseStampShouldThrowWhenTextNull()
        {
            Action act = () => Stamp.Parse(null);

            act.ShouldThrow<ArgumentNullException>();
        }

        [Test]
        public void ParseStampShouldThrowWhenTextEmpty()
        {
            Action act = () => Stamp.Parse(string.Empty);

            act.ShouldThrow<ParserException>().Where(
                e => e.Position == 1
                && e.Expecting == TokenKind.LParen
                && e.Found == TokenKind.EndOfText);
        }

        [Test]
        public void ParseStampShouldThrowWhenTextMissingFirstParenthesis()
        {
            //                              00000000011111111112
            //                              12345678901234567890
            //                              ↓
            Action act = () => Stamp.Parse("1,(1,0,(0,2,0)))");

            act.ShouldThrow<ParserException>().Where(
                e => e.Position == 1
                && e.Expecting == TokenKind.LParen
                && e.Found == TokenKind.IntegerLiteral);
        }

        [Test]
        public void ParseStampShouldThrowWhenTextMissingLastParenthesis()
        {
            //                              00000000011111111112
            //                              12345678901234567890
            //                                  ↓
            Action act = () => Stamp.Parse("(1,0");

            act.ShouldThrow<ParserException>().Where(
                e => e.Position == 5
                && e.Expecting == TokenKind.RParen
                && e.Found == TokenKind.EndOfText);
        }

        [Test]
        public void ParseStampShouldThrowWhenTextMissingFirstComma()
        {
            //                              00000000011111111112
            //                              12345678901234567890
            //                                ↓
            Action act = () => Stamp.Parse("(1(1,0,(0,2,0)))");

            act.ShouldThrow<ParserException>().Where(
                e => e.Position == 3
                && e.Expecting == TokenKind.Comma
                && e.Found == TokenKind.LParen);
        }

        [Test]
        public void ParseStampShouldThrowWhenTextMissingFirstParenOfEventNode()
        {
            //                              00000000011111111112
            //                              12345678901234567890
            //                                  ↓
            Action act = () => Stamp.Parse("(1,1,0,1))");
            //                                 ↑
            //                                 └ the parser thinks this is an event leaf (int_literal)
            //                                   because of the missing '(', so it expects an RParen to
            //                                   end the stamp

            act.ShouldThrow<ParserException>().Where(
                e => e.Position == 5
                && e.Expecting == TokenKind.RParen
                && e.Found == TokenKind.Comma);

            // Future enhancement?
            //
            // You could argue a more sophisticated parser could detect the event
            // has the structure of an event node (i.e., (int,event,event)), not an
            // event leaf and could therefore determine the LParen is missing.
            //
            //            ↓ missing parethesis
            // As in: "(1,(1,0,1))"
            //
            // That would be pretty cool, and possibly a nice future enhancement,
            // but the current behavior is reasonable for a simple parser.

            /*
            //                              00000000011111111112
            //                              12345678901234567890
            //                                 ↓
            Action act = () => Stamp.Parse("(1,1,0,1))");
            act.ShouldThrow<ParserException>().Where(
                e => e.Position == 4
                && e.Expecting == TokenKind.LParen
                && e.Found == TokenKind.IntegerLiteral);
            */
        }
    }
}


<|start_filename|>package.cmd<|end_filename|>
@echo off
@cd /d "%~dp0"

echo info: Package and release Itc4net NuGet package

echo info: Download vswhere (to locate msbuild)
mkdir .\build
set VSWHERE_URL=https://github.com/Microsoft/vswhere/releases/download/1.0.62/vswhere.exe
@powershell -NoProfile -ExecutionPolicy Bypass -Command "Invoke-WebRequest -Uri %VSWHERE_URL% -OutFile '.\build\vswhere.exe'"
if ERRORLEVEL 1 (
    echo error: Failed to download vswhere
    goto EXIT
)

:: See https://github.com/Microsoft/vswhere
for /f "usebackq tokens=1* delims=: " %%i in (`.\build\vswhere -latest -requires Microsoft.Component.MSBuild`) do (
  if /i "%%i"=="installationPath" set VSCOMNTOOLS=%%j
)

echo info: Setup MSBuild environment
:: This batch script modifies the current directory
set PRESERVE_CURRENT_DIRECTORY=%~dp0
call "%VSCOMNTOOLS%\Common7\tools\VsMSBuildCmd.bat"
cd /d %PRESERVE_CURRENT_DIRECTORY%
set PRESERVE_CURRENT_DIRECTORY=

echo info: Build Itc4net
msbuild.exe ".\src\Itc4net.sln" /p:Configuration=Release /t:Rebuild
if ERRORLEVEL 1 (
    echo error: Failed to build Itc4net
    goto EXIT
)

xcopy /y /r ".\src\Itc4net\bin\Release\*.nupkg" ".\build"

:: echo info: Push NuGet nupkg
:: set /p APIKEY="Enter NuGet ApiKey:"
:: for /f %%b IN ('dir /b *.nupkg') do (
::     nuget push "%%b" -ApiKey %APIKEY% -Source https://www.nuget.org/api/v2/package
:: )

:EXIT
pause


<|start_filename|>src/Itc4net/Id.cs<|end_filename|>
﻿using System;
using Itc4net.Binary;

namespace Itc4net
{
    public abstract class Id : IEquatable<Id>
    {
        Id() { } // ensure no external classes can inherit

        internal abstract T Match<T>(Func<int, T> leaf, Func<Id, Id, T> node);
        internal abstract Id Normalize();
        internal abstract Node Split();
        internal abstract Id Sum(Id i2);
        internal abstract void Encode(BitWriter writer);

        public class Leaf : Id
        {
            public int Value { get; }

            public Leaf(int value)
            {
                if (value < 0 || value > 1)
                {
                    throw new ArgumentOutOfRangeException(nameof(value), value, "Must be 0 or 1");
                }

                Value = value;
            }

            internal override T Match<T>(Func<int, T> leaf, Func<Id, Id, T> node)
            {
                return leaf(Value);
            }

            internal override Id Normalize()
            {
                return this;
            }

            internal override Node Split()
            {
                switch (Value)
                {
                    case 0:
                        return new Node(0, 0);
                    case 1:
                        return new Node(new Node(1, 0), new Node(0, 1));
                    default:
                        throw new InvalidOperationException("Value must be 0 or 1");
                }
            }

            internal override Id Sum(Id i2)
            {
                switch (Value)
                {
                    case 0:
                        return i2;
                    case 1:
                        return 1;
                    default:
                        throw new InvalidOperationException("Value must be 0 or 1");
                }
            }

            public override string ToString()
            {
                return $"{Value}";
            }

            public override int GetHashCode()
            {
                return Value;
            }

            internal override void Encode(BitWriter writer)
            {
                writer.WriteBits(0, 2);
                writer.WriteBits((byte) Value, 1);
            }
        }

        public class Node : Id
        {
            public Id L { get; }
            public Id R { get; }

            public Node(Id left, Id right)
            {
                L = left ?? throw new ArgumentNullException(nameof(left));
                R = right ?? throw new ArgumentNullException(nameof(right));
            }

            internal override T Match<T>(Func<int, T> leaf, Func<Id, Id, T> node)
            {
                return node(L, R);
            }

            internal override Id Normalize()
            {
                if (L == 0 && R == 0)
                {
                    return 0;
                }

                if (L == 1 && R == 1)
                {
                    return 1;
                }

                return this;
            }

            internal override Node Split()
            {
                Node result;

                if (L == 0)
                {
                    Node i = R.Split();
                    result = new Node(new Node(0, i.L), new Node(0, i.R));
                }
                else if (R == 0)
                {
                    Node i = L.Split();
                    result = new Node(new Node(i.L, 0), new Node(i.R, 0));
                }
                else
                {
                    result = new Node(new Node(L, 0), new Node(0, R));
                }

                return result;
            }

            internal override Id Sum(Id i2)
            {
                var l1 = L;
                var r1 = R;

                return i2.Match(
                    v2 => v2 == 0 ? this : i2,
                    (l2, r2) => new Node(Sum(l1, l2), Sum(r1, r2)).Normalize()
                );
            }

            internal override void Encode(BitWriter writer)
            {
                if (L == 0)
                {
                    writer.WriteBits(1, 2);
                    R.Encode(writer);
                }
                else if (R == 0)
                {
                    writer.WriteBits(2, 2);
                    L.Encode(writer);
                }
                else
                {
                    writer.WriteBits(3, 2);
                    L.Encode(writer);
                    R.Encode(writer);
                }
            }

            public override string ToString()
            {
                return $"({L},{R})";
            }
        }

        public static Id Create(int value)
        {
            return new Leaf(value);
        }

        public static Id Create(Id left, Id right)
        {
            return new Node(left, right);
        }

        internal void Match(Action<int> leaf, Action<Id, Id> node)
        {
            // Adapt leaf action to func (ret null)
            object AdaptLeaf(int value)
            {
                leaf?.Invoke(value);
                return null;
            }

            // Adapt node action to func (ret null)
            object AdaptNode(Id il, Id ir)
            {
                node?.Invoke(il, ir);
                return null;
            }

            Match(AdaptLeaf, AdaptNode);
        }

        internal static Id Sum(Id i1, Id i2)
        {
            return i1.Sum(i2);
        }

        public bool Equals(Id other)
        {
            if (other == null) return false;

            return Match(
                v1 =>
                {
                    return other.Match(v2 => v1 == v2, (l2, r2) => false);
                },
                (l1, r1) =>
                {
                    return other.Match(v2 => false, (l2, r2) => l1.Equals(l2) && r1.Equals(r2));
                }
                );
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            if (ReferenceEquals(this, obj)) return true;
            var other = obj as Id;
            return other != null && Equals(other);
        }

        public override int GetHashCode()
        {
            return Match(v => v, (l, r) => unchecked (l.GetHashCode()*397 ^ r.GetHashCode()));
        }

        public static bool operator ==(Id left, Id right)
        {
            return Equals(left, right);
        }

        public static bool operator !=(Id left, Id right)
        {
            return !Equals(left, right);
        }

        public static implicit operator Id(int i)
        {
            return new Leaf(i);
        }

        public static implicit operator Id((Id left, Id right) tuple)
        {
            return new Node(tuple.left, tuple.right);
        }
    }
}


<|start_filename|>src/Itc4net/Event.cs<|end_filename|>
﻿using System;
using Itc4net.Binary;

namespace Itc4net
{
    public abstract class Event : IEquatable<Event>
    {
        Event() { } // ensure no external classes can inherit

        internal abstract T Match<T>(Func<int, T> leaf, Func<int, Event, Event, T> node);
        internal abstract bool Leq(Event e2);
        internal abstract Event Normalize();
        internal abstract Event Lift(int m);
        internal abstract Event Sink(int m);
        internal abstract int Min();
        internal abstract int Max();
        internal abstract Event Join(Event e2);
        internal abstract void Encode(BitWriter writer);

        public sealed class Leaf : Event
        {
            public int N { get; }

            public Leaf(int n)
            {
                if (n < 0) throw new ArgumentOutOfRangeException(nameof(n), n, "Must be >= 0");

                N = n;
            }

            public override string ToString()
            {
                return $"{N}";
            }

            internal override T Match<T>(Func<int, T> leaf, Func<int, Event, Event, T> node)
            {
                return leaf(N);
            }

            internal override bool Leq(Event e2)
            {
                var n1 = N;

                return e2.Match(
                    // leq(n1, n2) = n1 <= n2
                    n2 => n1 <= n2,

                    // leq(n1,(n2,l2,r2)) = n1 <= n2
                    (n2, l2, r2) => n1 <= n2
                    );
            }

            internal override Event Normalize()
            {
                return this;
            }

            internal override Event Lift(int m)
            {
                return new Leaf(N + m);
            }

            internal override Event Sink(int m)
            {
                return new Leaf(N - m);
            }

            internal override int Min()
            {
                return N;
            }

            internal override int Max()
            {
                return N;
            }

            internal override Event Join(Event e2)
            {
                int n1 = N;

                return e2.Match(
                    n2 => new Leaf(Math.Max(n1, n2)),
                    (n2, l2, r2) => Join(new Node(n1, 0, 0), e2)
                );
            }

            internal override void Encode(BitWriter writer)
            {
                writer.EncodeN(N);
            }
        }

        public sealed class Node : Event
        {
            public int N { get; }
            public Event L { get; }
            public Event R { get; }

            public Node(int n, Event left, Event right)
            {
                if (n < 0) throw new ArgumentOutOfRangeException(nameof(n), n, "Must be >= 0");

                N = n;
                L = left ?? throw new ArgumentNullException(nameof(left));
                R = right ?? throw new ArgumentNullException(nameof(right));
            }

            public override string ToString()
            {
                return $"({N},{L},{R})";
            }

            internal override T Match<T>(Func<int, T> leaf, Func<int, Event, Event, T> node)
            {
                return node(N, L, R);
            }

            internal override bool Leq(Event e2)
            {
                var n1 = N;
                var l1 = L;
                var r1 = R;

                return e2.Match(
                    // leq((n1,l1,r1),n2) = n1 <= n2 Λ leq(l1↑n1,n2) Λ leq(r1↑n1,n2)
                    n2 => n1 <= n2 && Leq(l1.Lift(n1), e2) && Leq(r1.Lift(n1), e2),

                    // leq((n1,l1,r1),(n2,l2,r2)) = n1 <= n2 Λ leq(l1↑n1,l2↑n2) Λ leq(r1↑n1,r2↑n2)
                    (n2, l2, r2) => n1 <= n2 && Leq(l1.Lift(n1), l2.Lift(n2)) && Leq(r1.Lift(n1), r2.Lift(n2))
                    );
            }

            internal override Event Normalize()
            {
                int m1 = L.Match(n => n, (n, e1, e2) => -1);
                int m2 = R.Match(n => n, (n, e1, e2) => -1);

                if (m1 > -1 && m2 > -1 && m1 == m2)
                {
                    return Create(N + m1);
                }

                int m = Math.Min(L.Min(), R.Min());
                return Create(N + m, L.Sink(m).Normalize(), R.Sink(m).Normalize());
            }

            internal override Event Lift(int m)
            {
                return new Node(N + m, L, R);
            }

            internal override Event Sink(int m)
            {
                int newN = N - m;
                if (newN < 0)
                {
                    int overflow = Math.Abs(newN);
                    return new Node(0, L.Sink(overflow), R.Sink(overflow));
                }

                return new Node(newN, L, R);
            }

            internal override int Min()
            {
                return N + Math.Min(L.Min(), R.Min());
            }

            internal override int Max()
            {
                return N + Math.Max(L.Max(), R.Max());
            }

            internal override Event Join(Event e2)
            {
                var n1 = N;
                var l1 = L;
                var r1 = R;

                return e2.Match(
                    n2 => Join(this, new Node(n2, 0, 0)),
                    (n2, l2, r2) =>
                    {
                        if (n1 > n2)
                        {
                            return Join(e2, this);
                        }

                        Event l = Join(l1, l2.Lift(n2 - n1));
                        Event r = Join(r1, r2.Lift(n2 - n1));
                        Event e = new Node(n1, l, r);
                        return e.Normalize();
                    }
                );
            }

            internal override void Encode(BitWriter writer)
            {
                if (N == 0 && L == 0)
                {
                    writer.WriteBits(0, 1);
                    writer.WriteBits(0, 2);
                    R.Encode(writer);
                }
                else if (N == 0 && R == 0)
                {
                    writer.WriteBits(0, 1);
                    writer.WriteBits(1, 2);
                    L.Encode(writer);
                }
                else if (N == 0)
                {
                    writer.WriteBits(0, 1);
                    writer.WriteBits(2, 2);
                    L.Encode(writer);
                    R.Encode(writer);
                }
                else if (L == 0)
                {
                    writer.WriteBits(0, 1);
                    writer.WriteBits(3, 2);
                    writer.WriteBits(0, 1);
                    writer.WriteBits(0, 1);
                    writer.EncodeN(N);
                    R.Encode(writer);
                }
                else if (R == 0)
                {
                    writer.WriteBits(0, 1);
                    writer.WriteBits(3, 2);
                    writer.WriteBits(0, 1);
                    writer.WriteBits(1, 1);
                    writer.EncodeN(N);
                    L.Encode(writer);
                }
                else
                {
                    writer.WriteBits(0, 1);
                    writer.WriteBits(3, 2);
                    writer.WriteBits(1, 1);
                    writer.EncodeN(N);
                    L.Encode(writer);
                    R.Encode(writer);
                }
            }
        }

        public static Event Create(int n)
        {
            return new Leaf(n);
        }

        public static Event Create(int n, Event e1, Event e2)
        {
            return new Node(n, e1, e2);
        }

        internal void Match(Action<int> leaf, Action<int, Event, Event> node)
        {
            object LeafFunc(int n)
            {
                leaf?.Invoke(n);
                return null;
            }

            object NodeFunc(int n, Event l, Event r)
            {
                node?.Invoke(n, l, r);
                return null;
            }

            Match(LeafFunc, NodeFunc);
        }

        internal static bool Leq(Event e1, Event e2)
        {
            return e1.Leq(e2);
        }

        internal static Event Join(Event e1, Event e2)
        {
            return e1.Join(e2);
        }

        public bool Equals(Event other)
        {
            if (other == null) return false;

            return Match(
                n1 =>
                {
                    return other.Match(n2 => n1 == n2, (n2, l2, r2) => false);
                },
                (n1, l1, r1) =>
                {
                    return other.Match(n2 => false, (n2, l2, r2) => n1 == n2 && l1.Equals(l2) && r1.Equals(r2));
                });
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            if (ReferenceEquals(this, obj)) return true;
            var other = obj as Event;
            return other != null && Equals(other);
        }

        public override int GetHashCode()
        {
            return Match(n => n, (n, l, r) => unchecked(n * 13 ^ l.GetHashCode() * 397 ^ r.GetHashCode()));
        }

        public static bool operator ==(Event left, Event right)
        {
            return Equals(left, right);
        }

        public static bool operator !=(Event left, Event right)
        {
            return !Equals(left, right);
        }

        public static implicit operator Event(int n)
        {
            return new Leaf(n);
        }

        public static implicit operator Event((int n, Event left, Event right) tuple)
        {
            return new Node(tuple.n, tuple.left, tuple.right);
        }
    }
}

<|start_filename|>src/Itc4net.Tests/StampConverterTests.cs<|end_filename|>
﻿using System;
using System.ComponentModel;
using FluentAssertions;
using NUnit.Framework;

namespace Itc4net.Tests
{
    [TestFixture]
    public class StampConverterTests
    {
        [Test]
        public void StampShouldDeclareTypeConverter()
        {
            TypeConverter converter = TypeDescriptor.GetConverter(typeof(Stamp));
            converter.Should().BeOfType<StampConverter>();
        }

        [Test]
        public void CanConvertToShouldReturnTrueWhenDestinationTypeIsString()
        {
            // Note, this is default TypeConverter behavior
            var converter = new StampConverter();
            converter.CanConvertTo(typeof(string)).Should().BeTrue();
        }

        [Test]
        public void CanConvertToShouldReturnFalseWhenDestinationTypeIsUnsupported()
        {
            // Note, this is default TypeConverter behavior
            var converter = new StampConverter();
            converter.CanConvertTo(typeof(int)).Should().BeFalse();
        }

        [Test]
        public void ConvertToShouldEqualStampStringRepresentationWhenDestinationTypeIsString()
        {
            // Note, this is default TypeConverter behavior (will call value.ToString method)
            Stamp stamp = new Stamp(((1, 0), 0), (0, (1, 1, 0), 0));
            var converter = new StampConverter();

            string result = (string) converter.ConvertTo(stamp, typeof(string));

            result.Should().Be(stamp.ToString());
            result.Should().Be("(((1,0),0),(0,(1,1,0),0))");
        }

        [Test]
        public void ConvertToShouldThrowWhenDestinationTypeIsUnsupported()
        {
            // Note, this is default TypeConverter behavior
            Stamp stamp = new Stamp(((1, 0), 0), (0, (1, 1, 0), 0));
            var converter = new StampConverter();

            Action act = () => converter.ConvertTo(stamp, typeof(int));
            act.ShouldThrow<NotSupportedException>();
        }

        [Test]
        public void CanConvertFromShouldReturnTrueWhenSourceTypeIsString()
        {
            var converter = new StampConverter();
            converter.CanConvertFrom(typeof(string)).Should().BeTrue();
        }

        [Test]
        public void CanConvertFromShouldReturnFalseWhenSourceTypeIsUnsupported()
        {
            // Note, this is default TypeConverter behavior
            var converter = new StampConverter();
            converter.CanConvertFrom(typeof(int)).Should().BeFalse();
        }

        [Test]
        public void ConvertFromShouldParseString()
        {
            var converter = new StampConverter();
            Stamp result = (Stamp) converter.ConvertFrom("(((1,0),0),(0,(1,1,0),0))");

            result.Should().Be(new Stamp(((1, 0), 0), (0, (1, 1, 0), 0)));
        }

        [Test]
        public void IsValidShouldReturnTrueForLegitimateStampString()
        {
            // Note, this is default TypeConverter behavior
            var converter = new StampConverter();
            bool result = converter.IsValid("(((1,0),0),(0,(1,1,0),0))");

            result.Should().BeTrue();
        }

        [Test]
        public void IsValidShouldReturnFalseForMalformedStampString()
        {
            // Note, this is default TypeConverter behavior
            var converter = new StampConverter();
            bool result = converter.IsValid("(((1,0),0),(0,(1,1,0);0))");
            //                                                    ^--- invalid char

            result.Should().BeFalse();
        }
    }
}


<|start_filename|>src/Itc4net/Stamp.cs<|end_filename|>
﻿using System;
using System.ComponentModel;
using System.Diagnostics.Contracts;
using System.IO;
using Itc4net.Binary;
using Itc4net.Text;

namespace Itc4net
{
    /// <summary>
    /// An ITC stamp (logical clock)
    /// </summary>
    [TypeConverter(typeof(StampConverter))]
    public class Stamp : IEquatable<Stamp>, IComparable<Stamp>
    {
        readonly Id _i;
        readonly Event _e;

        /// <summary>
        /// Initializes a new seed instance of the <see cref="Stamp"/> class.
        /// </summary>
        public Stamp() // seed
        {
            _i = 1;
            _e = new Event.Leaf(0);
        }

        public Stamp(Id i, Event e)
        {
            _i = i ?? throw new ArgumentNullException(nameof(i));
            _e = e ?? throw new ArgumentNullException(nameof(e));
        }

        public bool IsAnonymous => _i == 0;

        /// <summary>
        /// Happened-before relation
        /// </summary>
        public bool Leq(Stamp other)
        {
            return _e.Leq(other._e);
        }

        //// <summary>
        //// Happened-before relation
        //// </summary>
        //public static bool Leq(Stamp s1, Stamp s2)
        //{
        //    return s1._e.Leq(s2._e);
        //}

        /// <summary>
        /// Fork a stamp into 2 distinct stamps (returns a 2-tuple)
        /// </summary>
        /// <returns>
        /// A 2-tuple, each with a unique identity and a copy of the causal history.
        /// </returns>
        [Pure]
        public (Stamp, Stamp) Fork()
        {
            Id.Node i = _i.Split();
            return (
                new Stamp(i.L, _e),
                new Stamp(i.R, _e)
            );
        }

        /// <summary>
        /// Create an anonymous stamp with a copy of the causal history.
        /// </summary>
        [Pure]
        public Stamp Peek()
        {
            return new Stamp(0, _e);
        }

        /// <summary>
        /// Inflate (increment) the stamp.
        /// </summary>
        /// <remarks>
        /// In the ITC paper, this kernel operation is named "event".
        /// </remarks>
        [Pure]
        public Stamp Event()
        {
            Event fillEvent = Fill();
            if (_e != fillEvent)
            {
                return new Stamp(_i, fillEvent);
            }

            return new Stamp(_i, Grow().Item1);
        }

        /// <summary>
        /// Merge stamps.
        /// </summary>
        [Pure]
        public Stamp Join(Stamp other)
        {
            Id i = _i.Sum(other._i);
            Event e = _e.Join(other._e);

            return new Stamp(i, e);
        }

        /// <inheritdoc/>
        public override string ToString()
        {
            return $"({_i},{_e})";
        }

        /// <summary>Indicates whether the current object is structurally equal to another object of the same type.</summary>
        /// <param name="other">A stamp to compare with this stamp.</param>
        /// <returns>
        /// true if the current object is equal to the <paramref name="other">other</paramref>
        /// parameter; otherwise, false.
        /// </returns>
        /// <remarks>
        /// This method performs a structural comparison of the entire stamp (both the id and event).
        /// For a causal equality, use the Equivalent extension method.
        /// </remarks>
        public bool Equals(Stamp other)
        {
            if (ReferenceEquals(null, other)) return false;
            if (ReferenceEquals(this, other)) return true;
            return _i.Equals(other._i) && _e.Equals(other._e);
        }

        /// <inheritdoc/>
        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            if (ReferenceEquals(this, obj)) return true;
            var other = obj as Stamp;
            return other != null && Equals(other);
        }

        /// <inheritdoc/>
        public override int GetHashCode()
        {
            unchecked
            {
                return (_i.GetHashCode()*397) ^ _e.GetHashCode();
            }
        }

        public static bool operator ==(Stamp left, Stamp right)
        {
            return Equals(left, right);
        }

        public static bool operator !=(Stamp left, Stamp right)
        {
            return !Equals(left, right);
        }

        internal (Event, int cost) Grow()
        {
            (Event, int) error = ((Event)null, -1);

            (Event, int) result = _e.Match(n =>
                {
                    if (_i == 1)
                    {
                        return (n + 1, 0);
                    }

                    (Event eʹ, int c) = new Stamp(_i, new Event.Node(n, 0, 0)).Grow();
                    return (eʹ, c + 1000);
                },
                (n, el, er) =>
                {
                    return _i.Match(
                        v => error,
                        (il, ir) =>
                        {
                            if (il == 0)
                            {
                                (Event eʹr, int cr) = new Stamp(ir, er).Grow();
                                return (new Event.Node(n, el, eʹr), cr + 1);
                            }

                            if (ir == 0)
                            {
                                (Event eʹl, int cl) = new Stamp(il, el).Grow();
                                return (new Event.Node(n, eʹl, er), cl + 1);
                            }

                            {
                                (Event eʹl, int cl) = new Stamp(il, el).Grow();
                                (Event eʹr, int cr) = new Stamp(ir, er).Grow();

                                if (cl < cr)
                                {
                                    return (new Event.Node(n, eʹl, er), cl + 1);
                                }
                                else // cl >= cr
                                {
                                    return (new Event.Node(n, el, eʹr), cr + 1);
                                }
                            }
                        });
                });

            if (result.Equals(error))
            {
                throw new InvalidOperationException($"Failed to grow stamp {this}");
            }

            return result;
        }

        internal Event Fill()
        {
            Event unchanged = _e;

            return _i.Match(
                v =>
                {
                    switch (v)
                    {
                        case 0:
                            return _e;
                        case 1:
                            return Itc4net.Event.Create(_e.Max());
                        default:
                            throw new InvalidOperationException();
                    }
                },
                (il, ir) =>
                {
                    if (il == 1)
                    {
                        return _e.Match(n => unchanged, (n, el, er) =>
                        {
                            var eʹr = new Stamp(ir, er).Fill();
                            Event e = Itc4net.Event.Create(n, Itc4net.Event.Create(Math.Max(el.Max(), eʹr.Min())), eʹr);
                            return e.Normalize();
                        });
                    }

                    if (ir == 1)
                    {
                        return _e.Match(n => unchanged, (n, el, er) =>
                        {
                            var eʹl = new Stamp(il, el).Fill();
                            Event e = Itc4net.Event.Create(n, eʹl, Itc4net.Event.Create(Math.Max(er.Max(), eʹl.Min())));
                            return e.Normalize();
                        });
                    }

                    return _e.Match(n => unchanged, (n, el, er) =>
                    {
                        var eʹl = new Stamp(il, el).Fill();
                        var eʹr = new Stamp(ir, er).Fill();
                        Event e = Itc4net.Event.Create(n, eʹl, eʹr);
                        return e.Normalize();
                    });
                }
            );
        }

        /// <summary>
        /// Converts the text encoding of an ITC stamp to its object equivalent.
        /// </summary>
        /// <param name="text">A string containing an ITC stamp text encoding.</param>
        /// <returns>An ITC stamp equivalent to the text contained in <para>text</para>.</returns>
        public static Stamp Parse(string text)
        {
            var parser = new Parser();
            return parser.ParseStamp(text);
        }

        /// <summary>
        /// Converts an ITC stamp to its equivalent binary encoding.
        /// </summary>
        /// <returns>A binary encoding of the ITC stamp.</returns>
        public byte[] ToBinary()
        {
            using (var stream = new MemoryStream())
            {
                using (var writer = new BitWriter(stream, leaveOpen: true))
                {
                    _i.Encode(writer);
                    _e.Encode(writer);
                }

                return stream.ToArray();
            }
        }

        /// <summary>
        /// Converts the binary encoding of an ITC stamp to its object equivalent.
        /// </summary>
        /// <param name="bytes">A byte[] containing an ITC stamp binary encoding.</param>
        /// <returns>An ITC stamp equivalent to the bytes contained in <para>bytes</para>.</returns>
        public static Stamp FromBinary(byte[] bytes)
        {
            using (var decoder = new Decoder())
            {
                return decoder.Decode(bytes);
            }
        }

        /// <summary>
        /// Compares the current Stamp with another Stamp for a partial order.
        /// </summary>
        /// <param name="other">An object to compare with this instance.</param>
        /// <returns>
        /// A value that indicates the partial order of the objects being compared.
        /// The return value has the following meanings:
        ///
        /// <list type="table">
        ///     <listheader>
        ///         <term>Value</term>
        ///         <term>Meaning</term>
        ///     </listheader>
        ///     <item>
        ///         <term>Less than zero</term>
        ///         <term>This stamp happens before <paramref name="other" />.</term>
        ///     </item>
        ///     <item>
        ///         <term>Zero</term>
        ///         <term>This stamp is equivalent or concurrent with <paramref name="other" />.</term>
        ///     </item>
        ///     <item>
        ///         <term>Greater than zero</term>
        ///         <term>The <paramref name="other" /> stamp happens before this stamp.</term>
        ///     </item>
        /// </list>
        /// </returns>
        /// <exception cref="System.ArgumentNullException">other</exception>
        /// <remarks>
        /// ITC stamps only provide a partial order. CompareTo returns zero when the compared
        /// stamps are equivalent or concurrent. When used with Sort methods, the stamps will be
        /// partially ordered.
        /// </remarks>
        public int CompareTo(Stamp other)
        {
            if (other == null) throw new ArgumentNullException(nameof(other));

            int CompareTo(Stamp l, Stamp r)
            {
                if (l == null) throw new ArgumentNullException(nameof(l));
                if (r == null) throw new ArgumentNullException(nameof(r));

                int result = l.Leq(r)
                    ? (r.Leq(l)
                        ? 0         //  (l <= r) ?  (r <= l) = equivalent
                        : -1)       //  (l <= r) ? ¬(r <= l) = lt
                    : (r.Leq(l)
                        ? 1         // ¬(l <= r) ?  (r <= l) = gt
                        : 0);       // ¬(l <= r) ? ¬(r <= l) = concurrent
                return result;
            }

            return CompareTo(this, other);
        }

        public static implicit operator Stamp((Id i, Event e) tuple)
        {
            return new Stamp(tuple.i, tuple.e);
        }
    }
}

<|start_filename|>src/Itc4net.Tests/EventTests.cs<|end_filename|>
﻿using System;
using FluentAssertions;
using NSubstitute;
using NUnit.Framework;

namespace Itc4net.Tests
{
    [TestFixture]
    public class EventTests
    {
        [Test]
        public void ToStringShouldCorrectlyRepresentLeafWith0()
        {
            new Event.Leaf(0).ToString().Should().Be("0");
        }

        [Test]
        public void ToStringShouldCorrectlyRepresentNode()
        {
            string s = new Event.Node(0, 3, new Event.Node(1, 2, 3)).ToString();
            s.Should().Be("(0,3,(1,2,3))");
        }

        [Test]
        public void LeafCtorShouldAcceptPositiveN()
        {
            new Event.Leaf(0);
            new Event.Leaf(1);
            new Event.Leaf(5);
        }

        [Test]
        public void LeafCtorShouldThrowWhenNegativeN()
        {
            Action act = () => new Event.Leaf(-1);
            act.ShouldThrow<ArgumentOutOfRangeException>();
        }

        [Test]
        public void NodeCtorShouldAcceptPositiveN()
        {
            new Event.Node(0, 0, 0);
            new Event.Node(1, 0, 0);
            new Event.Node(5, 0, 0);
        }

        [Test]
        public void NodeCtorShouldThrowWhenNegativeN()
        {
            Action act = () => new Event.Node(-1, 0, 0);
            act.ShouldThrow<ArgumentOutOfRangeException>();
        }

        [Test]
        public void NodeCtorShouldThrowWhenLeftEventNull()
        {
            Action act = () => new Event.Node(0, null, 0);
            act.ShouldThrow<ArgumentNullException>();
        }

        [Test]
        public void NodeCtorShouldThrowWhenRightEventNull()
        {
            Action act = () => new Event.Node(0, 0, null);
            act.ShouldThrow<ArgumentNullException>();
        }

        [Test]
        public void MatchShouldInvokeLeafFuncWhenNodeRepresentsLeaf()
        {
            // Arrange
            Event e = new Event.Leaf(0);

            Func<int, object> leafFn = Substitute.For<Func<int, object>>();
            Func<int, Event, Event, object> nodeFn = Substitute.For<Func<int, Event, Event, object>>();

            // Act
            e.Match(leafFn, nodeFn);

            // Assert
            leafFn.Received().Invoke(0);
            nodeFn.DidNotReceiveWithAnyArgs();
        }

        [Test]
        public void MatchShouldInvokeNodeFuncWhenEventRepresentsNode()
        {
            // Arrange
            Event e = new Event.Node(0, 1, 2);

            Func<int, object> leafFn = Substitute.For<Func<int, object>>();
            Func<int, Event, Event, object> nodeFn = Substitute.For<Func<int, Event, Event, object>>();

            // Act
            e.Match(leafFn, nodeFn);

            // Assert
            leafFn.DidNotReceiveWithAnyArgs();
            nodeFn.Received().Invoke(0, 1, 2);
        }

        [Test]
        public void MatchShouldInvokeLeafActionWhenEventRepresentsLeaf()
        {
            // Arrange
            Event e = new Event.Leaf(0);

            Action<int> leafAction = Substitute.For<Action<int>>();
            Action<int, Event, Event> nodeAction = Substitute.For<Action<int, Event, Event>>();

            // Act
            e.Match(leafAction, nodeAction);

            // Assert
            leafAction.Received().Invoke(0);
            nodeAction.DidNotReceiveWithAnyArgs();
        }

        [Test]
        public void MatchShouldInvokeNodeActionWhenEventRepresentsNode()
        {
            // Arrange
            Event e = new Event.Node(0, 1, 2);

            Action<int> leafAction = Substitute.For<Action<int>>();
            Action<int, Event, Event> nodeAction = Substitute.For<Action<int, Event, Event>>();

            // Act
            e.Match(leafAction, nodeAction);

            // Assert
            leafAction.DidNotReceiveWithAnyArgs();
            nodeAction.Received().Invoke(0, 1, 2);
        }

        [Test]
        public void EqualsShouldReturnTrueWhenComparingLeafsWithSameValues()
        {
            // Arrange
            Event e1 = new Event.Leaf(0);
            Event e2 = new Event.Leaf(0);

            // Act & Assert
            e1.Equals(e2).Should().BeTrue();
        }

        [Test]
        public void EqualsShouldReturnFalseWhenComparingLeafsWithDifferentValues()
        {
            // Arrange
            Event e1 = new Event.Leaf(0);
            Event e2 = new Event.Leaf(1);

            // Act & Assert
            e1.Equals(e2).Should().BeFalse();
        }

        [Test]
        public void EqualsShouldReturnTrueWhenComparingNodesWithSameValues()
        {
            // Arrange
            Event e1 = new Event.Node(0, 1, 2);
            Event e2 = new Event.Node(0, 1, 2);

            // Act & Assert
            e1.Equals(e2).Should().BeTrue();
        }

        [Test]
        public void EqualsShouldReturnFalseWhenComparingNodesWithDifferentN()
        {
            // Arrange
            Event e1 = new Event.Node(0, 1, 2);
            Event e2 = new Event.Node(9, 1, 2);

            // Act & Assert
            e1.Equals(e2).Should().BeFalse();
        }

        [Test]
        public void EqualsShouldReturnFalseWhenComparingNodesWithDifferentL()
        {
            // Arrange
            Event e1 = new Event.Node(0, 1, 2);
            Event e2 = new Event.Node(0, 9, 2);

            // Act & Assert
            e1.Equals(e2).Should().BeFalse();
        }

        [Test]
        public void EqualsShouldReturnFalseWhenComparingNodesWithDifferentR()
        {
            // Arrange
            Event e1 = new Event.Node(0, 1, 2);
            Event e2 = new Event.Node(0, 1, 9);

            // Act & Assert
            e1.Equals(e2).Should().BeFalse();
        }

        [Test]
        public void EqualsShouldReturnTrueWhenComparingComplexNodesWithSameValues()
        {
            // Arrange
            Event e1 = new Event.Node(0, new Event.Node(3, 4, 5), new Event.Node(6, 7, 8));
            Event e2 = new Event.Node(0, new Event.Node(3, 4, 5), new Event.Node(6, 7, 8));

            // Act & Assert
            e1.Equals(e2).Should().BeTrue();
        }

        [Test]
        public void EqualsShouldReturnTrueWhenComparingComplexNodesWithDifferentValues()
        {
            // Arrange
            Event e1 = new Event.Node(0, new Event.Node(3, 4, 5), new Event.Node(6, 7, 8));
            Event e2 = new Event.Node(0, new Event.Node(3, 5, 4), new Event.Node(6, 7, 8));

            // Act & Assert
            e1.Equals(e2).Should().BeFalse();
        }

        [Test]
        public void GetHashCodeShouldMatchWhenLeafsHaveSameValues()
        {
            // Arrange
            Event e1 = new Event.Leaf(0);
            Event e2 = new Event.Leaf(0);

            // Act
            int hash1 = e1.GetHashCode();
            int hash2 = e2.GetHashCode();

            e1.Equals(e2).Should().BeTrue();
        }

        [Test]
        public void GetHashCodeShouldNotMatchWhenLeafsHaveDifferentValues()
        {
            // Arrange
            Event e1 = new Event.Leaf(0);
            Event e2 = new Event.Leaf(4);

            // Act
            int hash1 = e1.GetHashCode();
            int hash2 = e2.GetHashCode();

            e1.Equals(e2).Should().BeFalse();
        }

        [Test]
        public void GetHashCodeShouldMatchWhenNodesHaveSameValues()
        {
            // Arrange
            Event e1 = new Event.Node(0, 1, 2);
            Event e2 = new Event.Node(0, 1, 2);

            // Act
            int hash1 = e1.GetHashCode();
            int hash2 = e2.GetHashCode();

            e1.Equals(e2).Should().BeTrue();
        }

        [Test]
        public void GetHashCodeShouldNotMatchWhenNodesHaveDifferentValues()
        {
            // Arrange
            Event e1 = new Event.Node(0, 1, 2);
            Event e2 = new Event.Node(0, 2, 2);

            // Act
            int hash1 = e1.GetHashCode();
            int hash2 = e2.GetHashCode();

            e1.Equals(e2).Should().BeFalse();
        }

        [Test]
        public void GetHashCodeShouldMatchWhenComplexNodesHaveSameValues()
        {
            // Arrange
            Event e1 = new Event.Node(0, new Event.Node(3, 4, 5), new Event.Node(6, 7, 8));
            Event e2 = new Event.Node(0, new Event.Node(3, 4, 5), new Event.Node(6, 7, 8));

            // Act
            int hash1 = e1.GetHashCode();
            int hash2 = e2.GetHashCode();

            e1.Equals(e2).Should().BeTrue();
        }

        [Test]
        public void GetHashCodeShouldMatchWhenComplexNodesHaveDifferentValues()
        {
            // Arrange
            Event e1 = new Event.Node(0, new Event.Node(3, 4, 5), new Event.Node(6, 7, 8));
            Event e2 = new Event.Node(0, new Event.Node(3, 4, 6), new Event.Node(6, 7, 8));

            // Act
            int hash1 = e1.GetHashCode();
            int hash2 = e2.GetHashCode();

            e1.Equals(e2).Should().BeFalse();
        }

        [Test(Description = "lift := n↑m = n+m")]
        public void LiftShouldReturnDefinedValueForLeaf()
        {
            // Arrange
            int n = 2;
            int m = 1;
            Event e = new Event.Leaf(n);

            // Act
            Event result = e.Lift(m);

            // Assert
            result.Should().Be(new Event.Leaf(n+m));
        }

        [Test(Description = "lift := (n,e1,e2)↑m = (n+m,e1,e2)")]
        public void LiftShouldReturnDefinedValueForNode()
        {
            // Arrange
            int n = 2;
            int m = 1;
            Event e = new Event.Node(n, 8, 9);

            // Act
            Event result = e.Lift(m);

            // Assert
            result.Should().Be(new Event.Node(n + m, 8, 9));
        }

        [Test(Description = "sink := n↓m = n-m")]
        public void SinkShouldReturnDefinedValueForLeaf()
        {
            // Arrange
            int n = 2;
            int m = 1;
            Event e = new Event.Leaf(n);

            // Act
            Event result = e.Sink(m);

            // Assert
            result.Should().Be(new Event.Leaf(n - m));
        }

        [Test(Description = "sink := (n,e1,e2)↓m = (n-m,e1,e2)")]
        public void SinkShouldReturnDefinedValueForNode()
        {
            // Arrange
            int n = 2;
            int m = 1;
            Event e = new Event.Node(n, 8, 9);

            // Act
            Event result = e.Sink(m);

            // Assert
            result.Should().Be(new Event.Node(n - m, 8, 9));
        }

        [Test]
        public void SinkShouldCascadeToSubTreeWhenSinkingGreaterThanN()
        {
            // Arrange
            Event e = new Event.Node(2, 3, 4);

            // Act
            Event result = e.Sink(3);

            // Assert
            result.Should().Be(new Event.Node(0, 2, 3));
        }

        [Test(Description = "norm(n) = n")]
        public void NormalizeShouldReturnNWhenLeafIsN()
        {
            // Arrange
            Event e = new Event.Leaf(2);

            // Act
            Event result = e.Normalize();

            // Assert
            result.Should().Be(new Event.Leaf(2));
        }

        [Test(Description = "norm((n,m,m)) = n+m")]
        public void NormalizeShouldReturnLeafWithNPlusMWhenNodeHasSameLeftAndRightEvents()
        {
            // Arrange
            Event e = new Event.Node(2, 3, 3);

            // Act
            Event result = e.Normalize();

            // Assert
            result.Should().Be(new Event.Leaf(5));
        }

        [Test(Description = "norm((n,e1,e2)) = (n+m,e1↓m,e2↓m), where m=min(min(e1),min(e2)) for leaf")]
        public void NormalizeShouldReturnNormalizedTreeForNodeWithLeftAndRightLeafs()
        {
            // Arrange
            Event e = new Event.Node(1, 2, 3);

            // Act
            Event result = e.Normalize();

            // Assert
            result.Should().Be(new Event.Node(3, 0, 1));
        }

        [Test(Description = "norm((n,e1,e2)) = (n+m,e1↓m,e2↓m), where m=min(min(e1),min(e2)) for node")]
        public void NormalizeShouldReturnNormalizedTreeForNodeWithLeftNodeAndRightLeaf()
        {
            // This is an example from the ITC paper which assumes events are always
            // normalized (or start as normalized). In this, the tree is not normalized, but
            // the sub-trees are.

            // Arrange
            Event e = new Event.Node(2, new Event.Node(2, 1, 0), 3);

            // Act
            Event result = e.Normalize();

            // Assert
            result.Should().Be(new Event.Node(4, new Event.Node(0,1,0), 1));
        }

        [Test]
        public void NormalizeShouldReturnRecursivelyNormalizedEventTree()
        {
            // This event tree, and sub-trees, are not normalized which recursively normalized.

            // Arrange
            Event e = new Event.Node(1, new Event.Node(2, 3, 4), new Event.Node(1, 2, 4));

            // Act
            Event result = e.Normalize();

            // Assert
            result.Should().Be(new Event.Node(4, new Event.Node(2, 0, 1), new Event.Node(0, 0, 2)));
        }

        [Test(Description = "min(n) = n")]
        public void MinShouldReturnNWhenLeafN()
        {
            // Arrange
            Event e = new Event.Leaf(3);

            // Act & Assert
            e.Min().Should().Be(3);
        }

        [Test(Description = "min((n,e1,e2)) = n+min(min(e1),min(e2))")]
        public void MinShouldReturnNPlusMinOfLeftAndRightEvents()
        {
            // Arrange
            Event e = new Event.Node(1, 2, 3);

            // Act & Assert
            e.Min().Should().Be(1 + 2);
        }

        [Test(Description = "max(n) = n")]
        public void MaxShouldReturnNWhenLeafN()
        {
            // Arrange
            Event e = new Event.Leaf(3);

            // Act & Assert
            e.Max().Should().Be(3);
        }

        [Test(Description = "max((n,e1,e2)) = n+max(max(e1),max(e2))")]
        public void MaxShouldReturnNPlusMaxOfLeftAndRightEvents()
        {
            // Arrange
            Event e = new Event.Node(1, 2, 3);

            // Act & Assert
            e.Max().Should().Be(1 + 3);
        }

        [Test(Description = "leq(n1,n2) = n1<=n2, case n1 < n2")]
        public void LeqShouldReturnTrueWhenN1IsLessThenN2()
        {
            // Arrange
            Event e1 = new Event.Leaf(1);
            Event e2 = new Event.Leaf(2);

            // Act & Assert
            e1.Leq(e2).Should().BeTrue();
        }

        [Test(Description = "leq(n1,n2) = n1<=n2, case n1 == n2")]
        public void LeqShouldReturnTrueWhenN1EqualsN2()
        {
            // Arrange
            Event e1 = new Event.Leaf(1);
            Event e2 = new Event.Leaf(1);

            // Act & Assert
            e1.Leq(e2).Should().BeTrue();
        }

        [Test(Description = "leq(n1,n2) = n1<=n2, case n1 > n2")]
        public void LeqShouldReturnFalseWhenN1IsGreaterThanN2()
        {
            // Arrange
            Event e1 = new Event.Leaf(2);
            Event e2 = new Event.Leaf(1);

            // Act & Assert
            e1.Leq(e2).Should().BeFalse();
        }

        [Test(Description = "leq(n1,(n2,l2,r2)) = n1<=n2")]
        public void LeqShouldReturnTrueWhenLeafN1IsLessThanNodeN2()
        {
            // Arrange
            Event e1 = 1;
            Event e2 = new Event.Node(2, 0, 0);

            // Act & Assert
            e1.Leq(e2).Should().BeTrue();
        }

        [Test(Description = "leq((n1,l1,r2),n2) = n1<=n2 Λ leq(l1↑n1,n2) Λ leq(r1↑n1,n2), case n1 < n2")]
        public void LeqShouldReturnTrueWhenNodeN1IsLessThanLeafN2()
        {
            // Arrange
            Event e1 = new Event.Node(2, 0, 0);
            Event e2 = new Event.Leaf(3);

            // Act & Assert
            e1.Leq(e2).Should().BeTrue();
        }

        [Test(Description = "leq((n1,l1,r2),n2) = n1<=n2 Λ leq(l1↑n1,n2) Λ leq(r1↑n1,n2), case n1+l1<n2")]
        public void LeqShouldReturnTrueWhenNodeN1PlusL1IsLessThanOrEqualToLeafN2()
        {
            // Arrange
            Event e1 = new Event.Node(2, 1, 0);
            Event e2 = new Event.Leaf(3);

            // Act & Assert
            e1.Leq(e2).Should().BeTrue();
        }

        [Test(Description = "leq((n1,l1,r2),n2) = n1<=n2 Λ leq(l1↑n1,n2) Λ leq(r1↑n1,n2), case n1+r1<n2")]
        public void LeqShouldReturnTrueWhenNodeN1PlusR1IsLessThanOrEqualToLeafN2()
        {
            // Arrange
            Event e1 = new Event.Node(2, 0, 1);
            Event e2 = new Event.Leaf(3);

            // Act & Assert
            e1.Leq(e2).Should().BeTrue();
        }

        [Test(Description = "leq((n1,l1,r2),n2) = n1<=n2 Λ leq(l1↑n1,n2) Λ leq(r1↑n1,n2), case n1+l1>n2")]
        public void LeqShouldReturnFalseWhenNodeN1PlusL1IsGreaterThanLeafN2()
        {
            // Arrange
            Event e1 = new Event.Node(2, 2, 0);
            Event e2 = new Event.Leaf(3);

            // Act & Assert
            e1.Leq(e2).Should().BeFalse();
        }

        [Test(Description = "leq((n1,l1,r2),n2) = n1<=n2 Λ leq(l1↑n1,n2) Λ leq(r1↑n1,n2), case n1+r1>n2")]
        public void LeqShouldReturnFalseWhenNodeN1PlusR1IsGreaterThanLeafLeafN2()
        {
            // Arrange
            Event e1 = new Event.Node(2, 0, 2);
            Event e2 = new Event.Leaf(3);

            // Act & Assert
            e1.Leq(e2).Should().BeFalse();
        }

        [Test(Description = "leq((n1,l1,r2),(n2,l2,r2)) = n1<=n2 Λ leq(l1↑n1,l2↑n2) Λ leq(r1↑n1,r2↑n2), case n1=n2, l1<l2")]
        public void LeqShouldReturnTrueWhenNodeN1EqualsNodeN2()
        {
            // Arrange
            Event e1 = new Event.Node(2, 0, 0);
            Event e2 = new Event.Node(2, 0, 0);

            // Act & Assert
            e1.Leq(e2).Should().BeTrue();
        }

        [Test(Description = "leq((n1,l1,r2),(n2,l2,r2)) = n1<=n2 Λ leq(l1↑n1,l2↑n2) Λ leq(r1↑n1,r2↑n2), case n1=n2, l1<l2")]
        public void LeqShouldReturnTrueWhenNodeN1EqualsNodeN2AndL1LessThanL2()
        {
            // Arrange
            Event e1 = new Event.Node(2, 2, 0);
            Event e2 = new Event.Node(2, 2, 0);

            // Act & Assert
            e1.Leq(e2).Should().BeTrue();
        }

        [Test(Description = "leq((n1,l1,r2),(n2,l2,r2)) = n1<=n2 Λ leq(l1↑n1,l2↑n2) Λ leq(r1↑n1,r2↑n2), case n1=n2, l1==l2")]
        public void LeqShouldReturnTrueWhenNodeN1EqualsNodeN2AndL1EqualsL2()
        {
            // Arrange
            Event e1 = new Event.Node(2, 2, 0);
            Event e2 = new Event.Node(2, 2, 0);

            // Act & Assert
            e1.Leq(e2).Should().BeTrue();
        }

        [Test(Description = "leq((n1,l1,r2),(n2,l2,r2)) = n1<=n2 Λ leq(l1↑n1,l2↑n2) Λ leq(r1↑n1,r2↑n2), case n1=n2, l1>l2")]
        public void LeqShouldReturnFalseWhenNodeN1EqualsNodeN2AndL1GreaterThanL2()
        {
            // Arrange
            Event e1 = new Event.Node(2, 3, 0);
            Event e2 = new Event.Node(2, 2, 0);

            // Act & Assert
            e1.Leq(e2).Should().BeFalse();
        }

        [Test(Description = "join(n1,n2) = max(n1,n2)")]
        public void JoinShouldReturnMaxNWhenBothLeafs()
        {
            // Arrange
            Event e1 = new Event.Leaf(1);
            Event e2 = new Event.Leaf(2);

            // Act
            Event result = e1.Join(e2);

            // Assert
            result.Should().Be(new Event.Leaf(2));
        }

        [Test(Description = "join(n1,(n2,l2,r2)) = join((n1,0,0),(n2,l2,r2))")]
        public void JoinShouldReturnDefinedValueWhenLeafN1AndNodeN2()
        {
            // Arrange
            Event e1 = new Event.Leaf(1);
            Event e2 = new Event.Node(2, 0, 1);

            // Act
            Event result = e1.Join(e2);

            // Assert
            result.Should().Be(new Event.Node(2,0,1));
        }

        [Test(Description = "join((n1,l1,r1),n2) = join((n1,l1,r1),(n2,0,0))")]
        public void JoinShouldReturnDefinedValueWhenNodeN1AndLeafN2()
        {
            // Arrange
            Event e1 = new Event.Node(2, 0, 1);
            Event e2 = new Event.Leaf(1);

            // Act
            Event result = e1.Join(e2);

            // Assert
            result.Should().Be(new Event.Node(2, 0, 1));
        }

        [Test(Description = "join((n1,l1,r1),(n2,l2,r2)) = join((n2,l2,r2),(n1,l1,r1)), if n1>n2")]
        public void JoinShouldReturnDefinedValueWhenNodeN1AndNodeN2WithN1GreaterThanN2()
        {
            // Arrange
            Event e1 = new Event.Node(2, 0, 1);
            Event e2 = new Event.Node(1, 1, 0);

            // Act
            Event result = e1.Join(e2);

            // Assert
            result.Should().Be(new Event.Node(2, 0, 1));
        }

        [Test(Description = "join((n1,l1,r1),(n2,l2,r2)) = norm((n1,join(l1,l2↑n2-n1),join(r1,r2↑n2-n1)))")]
        public void JoinShouldReturnDefinedValueWhenNodeN1AndNodeN2WithN1LessThanN2()
        {
            // Arrange
            Event e1 = new Event.Node(1, 2, 0);
            Event e2 = new Event.Node(3, 1, 3);

            // Act
            Event result = e1.Join(e2);

            // Assert
            result.Should().Be(new Event.Node(4, 0, 2));
        }

        [Test]
        public void ImplicitConversionOperatorShouldReturnLeafWhenInteger()
        {
            Event e1 = new Event.Leaf(4);
            Event e2 = 4;

            e1.Equals(e2).Should().BeTrue();
        }

        [Test]
        public void ImplicitConversionOperatorShouldReturnNodeWhenTuple()
        {
            Event e1 = new Event.Node(0, new Event.Node(1, 1, 0), 0);
            Event e2 = (0, (1, 1, 0), 0); // combo of C#7 tuples and implicit conversion operator is wow!

            e1.Equals(e2).Should().BeTrue();
        }
    }
}

<|start_filename|>src/Itc4net/Binary/Decoder.cs<|end_filename|>
using System;

namespace Itc4net.Binary
{
    /// <summary>
    /// An ITC stamp decoder
    /// </summary>
    class Decoder : IDisposable
    {
        byte[] _bytes;
        BitReader _reader;
        bool _disposed;
        int _currentPosition;

        public Decoder()
        {
            _reader = null;
        }

        public Stamp Decode(byte[] bytes)
        {
            if (bytes == null) throw new ArgumentNullException(nameof(bytes));

            _bytes = bytes;
            _reader = new BitReader(bytes);

            Id i = DecodeId();
            Event e = DecodeEvent();

            return new Stamp(i, e);
        }

        string DescribeBytes()
        {
            if (_bytes == null)
            {
                return "(null)";
            }

            if (_bytes.Length == 0)
            {
                return "(empty)";
            }

            return BitConverter.ToString(_bytes);
        }

        void ThrowUnexpected(int unexpected)
        {
            int errorPosition = _currentPosition;
            string error = $"Error parsing {DescribeBytes()}. Unexpected value 0x{unexpected:X2} at bit index {errorPosition}.";

            throw new DecoderException(error, null, unexpected, errorPosition);
        }

        void ThrowUnexpectedEndOfStream()
        {
            int errorPosition = _currentPosition;
            string error = $"Error parsing {DescribeBytes()}. Unexpected EndOfStream at bit index {errorPosition}.";

            throw new DecoderException(error, null, BitProcessor.EndOfStream, errorPosition);
        }

        void ThrowExpected(int expecting, int found)
        {
            int errorPosition = _currentPosition;
            string error = $"Error parsing {DescribeBytes()}. Expecting value 0x{expecting:X2}"
                           + $", yet found 0x{found:X2} @ bit index {errorPosition}";

            throw new DecoderException(error, expecting, found, errorPosition);
        }

        byte Scan(int bitCount)
        {
            byte value;
            int readBits = _reader.ReadBits(bitCount, out value);
            if (readBits == bitCount)
            {
                _currentPosition += bitCount;
                return value;
            }

            _currentPosition += Math.Max(readBits, 0);
            ThrowUnexpectedEndOfStream();
            return 0;
        }

        Id DecodeId()
        {
            Id id = null;

            byte prefix1 = Scan(2);
            switch (prefix1)
            {
                case 0: // 0 | 1
                    byte v = Scan(1);
                    id = new Id.Leaf(v);
                    break;
                case 1: // (0,1)
                    id = new Id.Node(0, DecodeId());
                    break;
                case 2: // (i,0)
                    id = new Id.Node(DecodeId(), 0);
                    break;
                case 3: // (l,r)
                    id = new Id.Node(DecodeId(), DecodeId());
                    break;
                default:
                    ThrowUnexpected(prefix1);
                    break;
            }

            return id;
        }

        Event DecodeEvent()
        {
            Event e = null;

            byte prefix1 = Scan(1);
            switch (prefix1)
            {
                case 0: // node
                    e = DecodeEventNode();
                    break;
                case 1: // leaf
                    int n = DecodeN(2);
                    e = new Event.Leaf(n);
                    break;
                default:
                    ThrowUnexpected(prefix1);
                    break;
            }

            return e;
        }

        Event DecodeEventNode()
        {
            Event e = null;

            byte prefix2 = Scan(2);
            switch (prefix2)
            {
                case 0: // (0,0,er)
                    e = new Event.Node(0, 0, DecodeEvent());
                    break;
                case 1: // (0,el,0)
                    e = new Event.Node(0, DecodeEvent(), 0);
                    break;
                case 2: // (0,el,er)
                    e = new Event.Node(0, DecodeEvent(), DecodeEvent());
                    break;
                case 3: // n != 0
                    byte prefix3 = Scan(1);
                    switch (prefix3)
                    {
                        case 0:
                            byte prefix4 = Scan(1);
                            switch (prefix4)
                            {
                                case 0: // (n,0,er)
                                    e = new Event.Node(DecodeN(), 0, DecodeEvent());
                                    break;
                                case 1: // (n,el,0)
                                    e = new Event.Node(DecodeN(), DecodeEvent(), 0);
                                    break;
                                default:
                                    ThrowUnexpected(prefix4);
                                    break;
                            }
                            break;
                        case 1: // (n,el,er)
                            e = new Event.Node(DecodeN(), DecodeEvent(), DecodeEvent());
                            break;
                        default:
                            ThrowUnexpected(prefix3);
                            break;
                    }
                    break;
                default:
                    ThrowUnexpected(prefix2);
                    break;
            }

            return e;
        }

        int DecodeN()
        {
            byte scan = Scan(1);
            if (scan == 1)
            {
                return DecodeN(2);
            }

            ThrowExpected(1, scan);
            return 0;
        }

        int DecodeN(int b)
        {
            int n = 0;

            byte scan = Scan(1);
            switch (scan)
            {
                case 0:
                    if (b <= 8)
                    {
                        n = Scan(b);
                    }
                    else
                    {
                        // The current implementation of BitReader currently only supports
                        // reading 0-8 bits at a time. I may fix this in the future, but
                        // until then, just break reading 'n' into multiple writes.
                        int remainder;
                        int quotient = Math.DivRem(b, 8, out remainder);

                        if (remainder > 0)
                        {
                            int value = (Scan(remainder) & 0x000000FF) << (8 * quotient);
                            n |= value;
                        }

                        for (int index = quotient - 1; index >= 0; index--)
                        {
                            int value = (Scan(8) & 0x000000FF) << (8 * index);
                            n |= value;
                        }
                    }
                    break;
                case 1:
                    n = (int) (DecodeN((byte) (b + 1)) + Math.Pow(2, b));
                    break;
                default:
                    ThrowUnexpected(scan);
                    break;
            }

            return n;
        }

        /// <summary>
        /// Performs application-defined tasks associated with freeing, releasing, or
        /// resetting unmanaged resources.
        /// </summary>
        public void Dispose()
        {
            Dispose(true);
            GC.SuppressFinalize(this);
        }

        /// <summary>
        /// Finalizes an instance of the <see cref="BitWriter"/> class.
        /// </summary>
        ~Decoder()
        {
            Dispose(false);
        }

        /// <summary>
        /// Releases unmanaged and managed resources.
        /// </summary>
        /// <param name="disposing"><c>true</c> to release both managed and unmanaged resources;
        /// <c>false</c> to release only unmanaged resources.
        /// </param>
        protected virtual void Dispose(bool disposing)
        {
            if (!_disposed)
            {
                if (disposing)
                {
                    _reader?.Dispose();
                }

                // release any unmanaged objects
                // set the object references to null

                _disposed = true;
            }
        }
    }
}

<|start_filename|>src/Itc4net.Tests/StampExtensionsTests.cs<|end_filename|>
﻿using System;
using FluentAssertions;
using NUnit.Framework;

namespace Itc4net.Tests
{
    [TestFixture]
    public class StampExtensionsTests
    {
        [Test]
        public void SendShouldReturnInflatedStampAsReturnValue()
        {
            // Arrange
            Stamp s = new Stamp();

            // Act
            Stamp _;
            Stamp returnValue = s.Send(out _);

            // Assert
            returnValue.Should().Be(s.Event());
        }

        [Test]
        public void SendShouldReturnInflatedAnonymousStampAsOutParameter()
        {
            // Arrange
            Stamp s = new Stamp();

            // Act
            Stamp outParameter;
            s.Send(out outParameter);

            // Assert
            outParameter.IsAnonymous.Should().BeTrue();
        }

        [Test]
        public void EquivalentShouldReturnTrueWhenStampsHaveEqualEvents()
        {
            Stamp a = ((1, 0), (0, 1, 0));
            Stamp b = ((0, 1), (0, 1, 0));

            a.Equivalent(b).Should().BeTrue();
        }

        [Test]
        public void EquivalentShouldReturnFalseWhenStampsHaveConcurrentEvents()
        {
            Stamp a = ((1, 0), (0, 1, 0));
            Stamp b = ((0, 1), (0, 0, 1));

            a.Equivalent(b).Should().BeFalse();
        }

        [Test]
        public void EquivalentShouldReturnFalseWhenOneStampDominatesTheOther()
        {
            Stamp a = ((1, 0), (0, 1, 0));
            Stamp b = a.Event();

            a.Equivalent(b).Should().BeFalse();
        }
    }
}


<|start_filename|>src/Itc4net/Binary/BitWriter.cs<|end_filename|>
using System;
using System.IO;

namespace Itc4net.Binary
{
    class BitWriter : BitProcessor
    {
        public BitWriter(Stream stream) : this(stream, false)
        {
        }

        public BitWriter(Stream stream, bool leaveOpen) : base(stream, leaveOpen)
        {
            RelativePosition = 0;
            CurrentByte = 0;
        }

        public void WriteBits(byte value, int bitCount)
        {
            if (bitCount < 0 || bitCount > 8)
            {
                throw new ArgumentOutOfRangeException(nameof(bitCount), bitCount, "Must be between 0 and 8 (inclusive).");
            }

            value = (byte) (value & CreateMask(bitCount));

            int shift = 8 - RelativePosition - bitCount;
            byte writeValue = shift > 0 ? (byte)(value << shift) : (byte)(value >> Math.Abs(shift));

            CurrentByte |= writeValue;

            if (shift > 0)
            {
                RelativePosition += bitCount;
            }
            else
            {
                BaseStream.WriteByte((byte) CurrentByte);
                RelativePosition = 0;
                CurrentByte = 0;

                if (shift < 0)
                {
                    WriteBits(value, (byte)Math.Abs(shift));
                }
            }
        }

        public void Complete()
        {
            if (RelativePosition > 0)
            {
                BaseStream.WriteByte((byte) CurrentByte);
                RelativePosition = 0;
                CurrentByte = 0;
            }
        }

        /// <inheritdoc />
        protected override void Dispose(bool disposing)
        {
            if (disposing)
            {
                Complete();
            }

            base.Dispose(disposing);
        }
    }
}

<|start_filename|>src/Itc4net/Text/TokenKind.cs<|end_filename|>
using System;

namespace Itc4net.Text
{
    public enum TokenKind : byte
    {
        LParen,
        RParen,
        Comma,
        IntegerLiteral,
        EndOfText,
        Error
    };
}

<|start_filename|>src/Itc4net.Tests/StampTests.cs<|end_filename|>
﻿using System;
using System.Diagnostics.CodeAnalysis;
using FluentAssertions;
using Itc4net.Binary;
using NUnit.Framework;

namespace Itc4net.Tests
{
    [TestFixture]
    public class StampTests
    {
        [Test]
        public void DefaultCtorShouldCreateSeed()
        {
            var seed = new Stamp();

            seed.Should().Be(new Stamp(1, 0));
            seed.ToString().Should().Be("(1,0)");
        }

        //[Test]
        //public void ForkShould()
        //{
        //    var seed = new Stamp();

        //    Tuple<Stamp, Stamp> forks = seed.Fork();
        //    forks.Item1.ToString().Should().Be("((1,0),0)");
        //    forks.Item2.ToString().Should().Be("((0,1),0)");
        //}

        [Test(Description = "fill(0,e) = e")]
        public void FillShouldReturnUnchangedEventWhenAnonymousId()
        {
            // Arrange
            Stamp s = new Stamp(0, new Event.Node(1, 2, 3));

            // Act
            Event e = s.Fill();

            // Assert
            e.Should().Be(new Event.Node(1, 2, 3));
        }

        [Test(Description = "fill(1,e) = max(e), test e is leaf")]
        public void FillShouldReturnMaxEventWhenId1WithLeaf()
        {
            // Arrange
            Stamp s = new Stamp(1, new Event.Leaf(3));

            // Act
            Event e = s.Fill();

            // Assert
            e.Should().Be(new Event.Leaf(3));
        }

        [Test(Description = "fill(1,e) = max(e), test e is node")]
        public void FillShouldReturnMaxEventWhenId1WithNode()
        {
            // Arrange
            Stamp s = new Stamp(1, new Event.Node(3, 1, 0));

            // Act
            Event e = s.Fill();

            // Assert
            e.Should().Be(new Event.Leaf(4));
        }

        [Test(Description = "fill(i,n) = n, test id leaf:0")]
        public void FillShouldReturnLeafEventForId0WhenLeafEvent()
        {
            // Arrange
            Stamp s = new Stamp(new Id.Leaf(0), new Event.Leaf(3));

            // Act
            Event e = s.Fill();

            // Assert
            e.Should().Be(new Event.Leaf(3));
        }

        [Test(Description = "fill(i,n) = n, test id leafL1")]
        public void FillShouldReturnLeafEventForId1WhenLeafEvent()
        {
            // Arrange
            Stamp s = new Stamp(new Id.Leaf(1), new Event.Leaf(3));

            // Act
            Event e = s.Fill();

            // Assert
            e.Should().Be(new Event.Leaf(3));
        }

        [Test(Description = "fill(i,n) = n, test id node")]
        public void FillShouldReturnLeafEventForAnyIdWhenLeafEvent()
        {
            // Arrange
            Stamp s = new Stamp(new Id.Node(new Id.Node(1, 0), 0), new Event.Leaf(3));

            // Act
            Event e = s.Fill();

            // Assert
            e.Should().Be(new Event.Leaf(3));
        }

        [Test(Description = "fill((1,ir)) = norm((n,max(max(el),min(eʹr)),eʹr)), where eʹr=fill(ir,er)")]
        public void FillShouldReturnDefinedStructureWhenIdNodeLeft1()
        {
            // Arrange
            Stamp s = new Stamp(new Id.Node(1, 0), new Event.Node(1, new Event.Node(0, 1, 0), 1));

            // Act
            Event e = s.Fill();

            // Assert
            e.Should().Be(new Event.Leaf(2));
        }

        [Test(Description = "fill((il,1)) = norm((n,eʹl,max(max(er),min(eʹl)))), where eʹl=fill(il,el)")]
        public void FillShouldReturnDefinedStructureWhenIdNodeRight1()
        {
            // Arrange
            Stamp s = new Stamp(new Id.Node(0, 1), new Event.Node(1, 1, new Event.Node(0, 1, 0)));

            // Act
            Event e = s.Fill();

            // Assert
            e.Should().Be(new Event.Leaf(2));
        }

        [Test(Description = "fill((il,ir)) = norm(n,fill(il,el),fill(ir,er))")]
        public void FillShouldReturnDefinedStructureWhenIdNode()
        {
            // Arrange
            Stamp s = new Stamp(
                new Id.Node(new Id.Node(1, 0), new Id.Node(0, 1)),
                new Event.Node(1, new Event.Node(0, 1, 2), new Event.Node(0, 1, 2))
                );

            // Act
            Event e = s.Fill();

            // Assert
            e.Should().Be(new Event.Node(2, 1, new Event.Node(0, 0, 1)));
        }

        [Test(Description = "grow(1,n) = (n+1,0)")]
        public void GrowShouldInflateEventLeafWhenId1AndLeafEvent()
        {
            // Arrange
            Stamp s = new Stamp(1, 2);

            // Act
            var result = s.Grow();
            Event e = result.Item1;
            int cost = result.Item2;

            // Assert
            e.Should().Be(new Event.Leaf(3));
            cost.Should().Be(0);
        }

        [Test(Description = "grow(i,n), where (eʹ,c) = grow(i,(n,0,0)), test id:(0,1)")]
        public void GrowShouldInflateRightEventLeafWhenEventLeafAndLeftId0()
        {
            // Arrange
            Stamp s = new Stamp(new Id.Node(0, 1), 1);

            // Act
            var result = s.Grow();
            Event e = result.Item1;
            int cost = result.Item2;

            // Assert
            e.Should().Be(new Event.Node(1, 0, 1));
            cost.Should().Be(1001);
        }

        [Test(Description = "grow(i,n), where (eʹ,c) = grow(i,(n,0,0)), test id:(1,0)")]
        public void GrowShouldInflateLeftEventLeafWhenEventLeafAndRightId1()
        {
            // Arrange
            Stamp s = new Stamp(new Id.Node(1, 0), 1);

            // Act
            var result = s.Grow();
            Event e = result.Item1;
            int cost = result.Item2;

            // Assert
            e.Should().Be(new Event.Node(1, 1, 0));
            cost.Should().Be(1001);
        }

       [Test(Description = "grow((0,ir),(n,el,er)) = ((n,el,eʹr),cr+1), where (eʹr,cr)=grow(ir,er)")]
        public void GrowShouldInflateRightEventWhenLeftId0()
        {
            // Arrange
            Stamp s = new Stamp(new Id.Node(0, 1), new Event.Node(1, 1, 0));

            // Act
            var result = s.Grow();
            Event e = result.Item1;
            int cost = result.Item2;

            // Assert
            e.Should().Be(new Event.Node(1, 1, 1)); // TODO: shouldn't grow normalize to (2,0,0)?
            cost.Should().Be(1);
        }

        [Test(Description = "grow((il,0),(n,el,er)) = ((n,eʹl,er),cl+1), where (eʹl,cl)=grow(ilr,el)")]
        public void GrowShouldInflateLeftEventWhenRightId0()
        {
            // Arrange
            Stamp s = new Stamp(new Id.Node(1, 0), new Event.Node(1, 1, 0));

            // Act
            var result = s.Grow();
            Event e = result.Item1;
            int cost = result.Item2;

            // Assert
            e.Should().Be(new Event.Node(1, 2, 0));
            cost.Should().Be(1);
        }

        [Test]
        public void LeqShouldReturnTrueWhenComparingOriginalStampAndInflatedStamp()
        {
            // Arrange
            Stamp s1 = new Stamp();

            // Act
            Stamp s2 = s1.Event();

            // Assert
            s1.Leq(s2).Should().BeTrue();
        }

        [Test]
        public void LeqShouldReturnFalseWhenComparingInflatedStampAndOriginalStamp()
        {
            // Arrange
            Stamp s1 = new Stamp();

            // Act
            Stamp s2 = s1.Event();

            // Assert
            s2.Leq(s1).Should().BeFalse();
        }

        [Test]
        public void LeqShouldReturnTrueWhenComparingWithItself()
        {
            // Arrange
            Stamp s = new Stamp().Event().Event();

            // Act & Assert
            s.Leq(s).Should().BeTrue();
        }

        [Test]
        public void ToBinaryShouldReturnEncodedBytesForSeedStamp()
        {
            // Arrange
            Stamp s = new Stamp(); // (1,0)

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x30 });
            // 00110000 = 0x30
            // ^^^      id
            //    ^^^^  event
        }

        [Test]
        public void ToBinaryShouldReturnEncodedBytesForAnonymousStampWithZeroEventLeaf()
        {
            // Arrange
            Stamp s = new Stamp(0, 0); // (0,0)

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x10 });
            // 00010000 = 0x10
            // ^^^      id
            //    ^^^^  event
        }

        [Test]
        public void ToBinaryShouldReturnEncodedBytesForIdNode0I()
        {
            // Arrange
            Stamp s = new Stamp(new Id.Node(0, 1), 0);

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x4C, 0x00 });
            // 01001100 00000000 = 0x4C 0x00
            // ^^^^^             id
            //      ^^^ ^        event
        }

        [Test]
        public void ToBinaryShouldReturnEncodedBytesForIdNodeI0()
        {
            // Arrange
            Stamp s = new Stamp(new Id.Node(1, 0), 0);

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x8C, 0x00 });
            // 10001100 00000000 = 0x8C 0x00
            // ^^^^^             id
            //      ^^^ ^        event
        }

        [Test]
        public void ToBinaryShouldReturnEncodedBytesForIdNode1001()
        {
            // Arrange
            Stamp s = new Stamp(new Id.Node(new Id.Node(1, 0), new Id.Node(0, 1)), 0);

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0xE2, 0x98 });
            // 11100010 10011000 = 0xE2 0x98
            // ^^^^^^^^ ^^^^     id
            //              ^^^^ event
        }

        [Test]
        public void ToBinaryShouldReturnEncodedBytesForEventNode00E()
        {
            // Arrange
            Stamp s = new Stamp(0, new Event.Node(0, 0, 1));

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x02, 0x40 });
            // 00000010 01000000 = 0x02 0x40
            // ^^^               id
            //    ^^^^^ ^^       event
        }

        [Test]
        public void ToBinaryShouldReturnEncodedBytesForEventNode0E0()
        {
            // Arrange
            Stamp s = new Stamp(0, new Event.Node(0, 1, 0));

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x06, 0x40 });
            // 00000110 01000000 = 0x06 0x40
            // ^^^               id
            //    ^^^^^ ^^       event
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void ToBinaryShouldReturnEncodedBytesForEventNode0EEWithNestedEventLeaf()
        {
            // Arrange
            Stamp s = new Stamp(0, new Event.Node(0, 1, 1));

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x0A, 0x64 });
            // 00001010 01100100 = 0x0A 0x64
            // ^^^               id
            //    ^^^^^ ^^^^^^   event
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void ToBinaryShouldReturnEncodedBytesForEventNode0EEWithNestedEventNode()
        {
            // Arrange
            Stamp s = new Stamp(0, new Event.Node(0, new Event.Node(0, 1, 0), 1));

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x08, 0xCC, 0x80 });
            // 00001000 11001100 10000000 = 0x08 0xCC 0x80
            // ^^^                        id
            //    ^^^^^ ^^^^^^^^ ^        event
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void ToBinaryShouldReturnEncodedBytesForEventNodeN0E()
        {
            // Arrange
            Stamp s = new Stamp(0, new Event.Node(1, 0, 1));

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x0C, 0x99 });
            // 00001100 10011001 = 0x0C 0x99
            // ^^^               id
            //    ^^^^^ ^^^^^^^^ event
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void ToBinaryShouldReturnEncodedBytesForEventNodeNE0()
        {
            // Arrange
            Stamp s = new Stamp(0, new Event.Node(1, 1, 0));

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x0D, 0x99 });
            // 00001101 10011001 = 0x0D 0x99
            // ^^^               id
            //    ^^^^^ ^^^^^^^^ event
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void ToBinaryShouldReturnEncodedBytesForEventNodeNEE()
        {
            // Arrange
            Stamp s = new Stamp(0, new Event.Node(1, 1, new Event.Node(3, 1, 0)));

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x0F, 0x32, 0xDB, 0x90 });
            // 00001111 00110010 11011011 10010000 = 0x0F 0x32 0xDB 0x90
            // ^^^                                 id
            //    ^^^^^ ^^^^^^^^ ^^^^^^^^ ^^^^     event
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void ToBinaryShouldReturnEncodedBytesForEventNodeWithLargeNCase17()
        {
            // Arrange
            Stamp s = new Stamp(0, 17);

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x1C, 0xA0 });
            // 00011100 10100000 = 0x1C 0xA0
            // ^^^               id
            //    ^^^^^ ^^^^     event
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void ToBinaryShouldReturnEncodedBytesForEventNodeWithLargeNCase258()
        {
            // Arrange
            Stamp s = new Stamp(0, 258);

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x1F, 0xC0, 0xC0 });
            // 00011111 11000000 11000000 = 0x1F 0xC0 0xC0
            // ^^^                        id
            //    ^^^^^ ^^^^^^^^ ^^^      event
        }

        [Test]
        // ReSharper disable once InconsistentNaming
        public void ToBinaryShouldReturnEncodedBytesForEventNodeWithLargeNCase513()
        {
            // Arrange
            Stamp s = new Stamp(0, 513);

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x1F, 0xE0, 0x28 });
            // 00011111 11100000 00101000 = 0x1F 0xE0 0x28
            // ^^^                        id
            //    ^^^^^ ^^^^^^^^ ^^^^^    event
        }

        [Test]
        public void ToBinaryShouldReturnEncodedBytesForEventNodeWithLargeNCase21474836()
        {
            // This value of N requires 24 bits (3 bytes) to encode and exposed an issue
            // related to encoding values that byte boundaries

            // Arrange
            Stamp s = new Stamp(0, 21474836);

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x1F, 0xFF, 0xFF, 0xC8, 0xF5, 0xC3, 0x00 });

            //

            // 00011111 11111111 11111111 110‭01000 11110101 11000011 000‬00000 = 0x1F 0xFF 0xFF 0xC8 0xF5 0xC3 0x00
            // ^^^                                                            id
            //    ^^^^^ ^^^^^^^^ ^^^^^^^^ ^^^^^^^^ ^^^^^^^^ ^^^^^^^^ ^^^      event
        }

        [Test]
        public void ToBinaryShouldReturnEncodedBytesForStampWithIdNode10AndEventNode110()
        {
            // Arrange
            Stamp s = new Stamp(new Id.Node(1, 0), new Event.Node(1, 1, 0));

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x8B, 0x66, 0x40 });
            // 10001011 01100110 01000000 = 0x8B 66 40
            // ^^^^^                      id
            //      ^^^ ^^^^^^^^ ^^       event
        }

        [Test]
        public void ToBinaryShouldReturnEncodedBytesForStampWithIdNode01AndEventNode110()
        {
            // Arrange
            Stamp s = new Stamp(new Id.Node(0, 1), new Event.Node(1, 1, 0));

            // Act
            byte[] bytes = s.ToBinary();

            // Assert
            bytes.ShouldBeEquivalentTo(new byte[] { 0x4B, 0x66, 0x40 });
            // 01001011 01100110 01000000 = 0x4B 66 40
            // ^^^^^                      id
            //      ^^^ ^^^^^^^^ ^^       event
        }

        [TestCase(0)]
        [TestCase(21474836)] // yes, this exposed an issue
        [TestCase(int.MaxValue)]
        public void StampShouldBeAbleToRoundTripBinaryEncoding(int n)
        {
            // Arrange
            Stamp original = new Stamp(0, n);

            // Act
            byte[] bytes = original.ToBinary();

            Decoder decoder = new Decoder();
            Stamp decoded = decoder.Decode(bytes);

            // Assert
            decoded.Should().Be(original);
        }

        [Test]
        public void CompareToShouldReturnZeroWhenComparingSeedStamps()
        {
            Stamp s1 = new Stamp();
            Stamp s2 = new Stamp();

            s1.CompareTo(s2).Should().Be(0);
        }

        [Test]
        public void CompareToShouldReturnZeroWhenComparingCausallyEqualStampsWithDifferentIds()
        {
            // Bug fix: The initial implementation used the Equal method to perform the compare
            // as equal (0); however, that method performs a structural comparison of both the
            // id and event. CompareTo must return 0 when 2 stamps are equivalent (causally equal).

            Stamp s1 = ((1, 0), (0, 1, 0));
            Stamp s2 = ((0, 1), (0, 1, 0));

            s1.CompareTo(s2).Should().Be(0);
        }

        [Test]
        public void CompareToShouldReturnNegativeValueWhenLeftHappensBeforeRight()
        {
            Stamp s1 = new Stamp();
            Stamp s2 = s1.Event();

            s1.CompareTo(s2).Should().BeLessThan(0);
        }

        [Test]
        public void CompareToShouldReturnPositiveValueWhenRightHappensBeforeLeft()
        {
            Stamp s1 = new Stamp();
            Stamp s2 = s1.Event();

            s2.CompareTo(s1).Should().BeGreaterThan(0);
        }

        [Test]
        public void CompareShouldReturnZeroWhenStampsCausallyConcurrent()
        {
            Stamp s1;
            Stamp s2;
            new Stamp().Fork(out s1, out s2);

            s1 = s1.Event();
            s2 = s2.Event();

            s1.Concurrent(s2).Should().BeTrue();
            s1.CompareTo(s2).Should().Be(0);
        }

        [Test]
        [SuppressMessage("ReSharper", "ReturnValueOfPureMethodIsNotUsed")]
        public void CompareShouldThrowWhenArgumentIsNull()
        {
            Action act = () => { new Stamp().CompareTo(null); };

            act.ShouldThrow<ArgumentNullException>();
        }

        [Test]
        public void ImplicitConversionOperationShouldReturnStampWhenTuple()
        {
            // (((0,(1,0)),(1,0)),(1,2,(0,(1,0,2),0)))
            Stamp s1 = new Stamp(
                new Id.Node(
                    new Id.Node(0, new Id.Node(1, 0)),
                    new Id.Node(1, 0)
                    ),
                new Event.Node(
                    1, 2, new Event.Node(0, new Event.Node(1, 0, 2), 0))
                    );
            Stamp s2 = (((0,(1,0)),(1,0)),(1,2,(0,(1,0,2),0)));
            //         |<----- id ----->| |<----- event ---->|

            s1.Equals(s2).Should().BeTrue();
        }
    }
}

<|start_filename|>src/Itc4net.Tests/Binary/BitWriterTests.cs<|end_filename|>
﻿using System;
using System.IO;
using FluentAssertions;
using Itc4net.Binary;
using NUnit.Framework;

namespace Itc4net.Tests.Binary
{
    [TestFixture]
    public class BitWriterTests
    {
        [Test]
        public void WriteBitsShouldBeAbleToWrite8Bits()
        {
            byte[] bytes = new byte[2];
            using (var writer = new BitWriter(new MemoryStream(bytes)))
            {
                writer.WriteBits(0xFF, 8); // 11111111
                //                            ^^^^^^^^
            }

            bytes[0].Should().Be(0xFF);
            bytes[1].Should().Be(0x00);
        }

        [Test]
        public void WriteBitsShouldBeAbleToWriteSuccessive8Bits()
        {
            byte[] bytes = new byte[2];
            using (var writer = new BitWriter(new MemoryStream(bytes)))
            {
                writer.WriteBits(0xFF, 8); // 11111111
                //                            ^^^^^^^^

                writer.WriteBits(0xAA, 8); // 10101010
                //                            ^^^^^^^^
            }

            bytes[0].Should().Be(0xFF);
            bytes[1].Should().Be(0xAA);
        }

        [Test]
        public void WriteBitsShouldBeAbleToWrite5Bits()
        {
            byte[] bytes = new byte[2];
            using (var writer = new BitWriter(new MemoryStream(bytes)))
            {
                writer.WriteBits(0xFF, 5); // 11111111
                //                               ^^^^^
            }

            // 11111000 = 0xF8
            // ^^^^^    = 1st 5 bits

            bytes[0].Should().Be(0xF8);
            bytes[1].Should().Be(0x00);
        }

        [Test]
        public void WriteBitsShouldBeAbleToWriteSuccessive5Bits()
        {
            byte[] bytes = new byte[2];
            using (var writer = new BitWriter(new MemoryStream(bytes)))
            {
                writer.WriteBits(0xFF, 5); // 11111111
                //                               ^^^^^

                writer.WriteBits(0xAA, 5); // 10101010
                //                               ^^^^^
            }

            // 11111010 10000000 = 0xFA 0x80
            // ^^^^^             = 1st 5 bits
            //      ^^^ ^^       = 2nd 5 bits

            bytes[0].Should().Be(0xFA);
            bytes[1].Should().Be(0x80);
        }

        [Test]
        public void WriteBitsShouldBeAbleToWrite3Bits()
        {
            byte[] bytes = new byte[2];
            using (var writer = new BitWriter(new MemoryStream(bytes)))
            {
                writer.WriteBits(0xFF, 3);  // 11111111
                //                                  ^^^
            }

            bytes[0].Should().Be(0xE0);
            bytes[1].Should().Be(0x00);
        }

        [Test]
        public void WriteBitsShouldBeAbleToWriteSuccessive3Bits()
        {
            byte[] bytes = new byte[2];
            using (var writer = new BitWriter(new MemoryStream(bytes)))
            {
                writer.WriteBits(0xFF, 3);  // 11111111
                //                                  ^^^

                writer.WriteBits(0xAA, 3);  // 10101010
                //                                  ^^^
            }

            // 11101000 = 0xE8
            // ^^^      = 1st 3 bits
            //    ^^^   = 2nd 3 bits

            bytes[0].Should().Be(0xE8);
            bytes[1].Should().Be(0x00);
        }

        [Test]
        public void WriteBitsShouldBeAbleToWrite0Bits()
        {
            byte[] bytes = new byte[2];
            using (var writer = new BitWriter(new MemoryStream(bytes)))
            {
                writer.WriteBits(0xFF, 0); // 11111111
            }

            bytes[0].Should().Be(0x00);
            bytes[1].Should().Be(0x00);
        }

        [Test]
        public void WriteBitsShouldBeAbleToWriteSuccesive5BitsThen4BitsThen2Bits()
        {
            byte[] bytes = new byte[2];
            using (var writer = new BitWriter(new MemoryStream(bytes)))
            {
                writer.WriteBits(0xAA, 5); // 10101010
                //                               ^^^^^
                writer.WriteBits(0xAA, 4); // 10101010
                //                                ^^^^
                writer.WriteBits(0xAA, 2); // 10101010
                //                                  ^^
            }

            // 01010101 010xxxxx = 0x55 0x40
            // ^^^^^             = 1st 5 bits
            //      ^^^ ^        = 2nd 4 bits
            //           ^^      = 3rd 2 bits

            bytes[0].Should().Be(0x55);
            bytes[1].Should().Be(0x40);
        }
    }
}


<|start_filename|>src/Itc4net/Text/Parser.cs<|end_filename|>
using System;

namespace Itc4net.Text
{
    /// <summary>
    /// A simple recursive-descent ITC stamp parser
    /// </summary>
    class Parser
    {
        string _text;
	    Token _currentToken;
	    Scanner _scanner;

		public Parser()
		{
			_currentToken = null;
			_scanner = null;
		}

	    public Stamp ParseStamp(string text)
	    {
	        if (text == null) throw new ArgumentNullException(nameof(text));

	        _text = text;
	        _scanner = new Scanner(text);
	        _currentToken = _scanner.Scan();

	        return ParseStamp();
	    }

        void ThrowUnexpectedToken(TokenKind unexpected)
        {
            int errorPosition = _currentToken.StartPosition;
            string error = $"Error parsing \"{_text}\". Unexpected token {unexpected} at index {errorPosition}.";

            throw new ParserException(error, null, _currentToken.Kind, errorPosition);
        }

        void ThrowExpectedToken(TokenKind expecting)
        {
            int errorPosition = _currentToken.StartPosition;
            string error = $"Error parsing \"{_text}\". Expecting token {expecting}"
                + $", yet found {_currentToken.Kind} @ index {errorPosition}";

            throw new ParserException(error, expecting, _currentToken.Kind, errorPosition);
        }

        void Accept()
		{
            _currentToken = _scanner.Scan();
        }

	    void Accept(TokenKind expected)
		{
			if (_currentToken.Kind == expected)
			{
				Accept();
			}
			else
			{
                ThrowExpectedToken(expected);
			}
		}

        /// <summary>
        /// Stamp := '(' Id ',' Event ')'
        /// </summary>
	    Stamp ParseStamp()
		{
			Accept(TokenKind.LParen);
		    Id i = ParseId();
            Accept(TokenKind.Comma);
		    Event e = ParseEvent();
            Accept(TokenKind.RParen);

            Accept(TokenKind.EndOfText);

            return new Stamp(i, e);
		}

        /// <summary>
        /// Id := IdLeaf | IdNode
        /// </summary>
	    Id ParseId()
	    {
	        Id i = null;
			switch (_currentToken.Kind)
			{
				case TokenKind.IntegerLiteral:
			        i = ParseIdLeaf();
					break;
				case TokenKind.LParen:
			        i = ParseIdNode();
			        break;
			    default:
			        ThrowUnexpectedToken(_currentToken.Kind);
			        break;
			}

	        return i;
	    }

        /// <summary>
        /// IdLeaf := INT_LITERAL
        /// </summary>
	    Id ParseIdLeaf()
	    {
            int n = int.Parse(_currentToken.Lexeme);
            Accept(TokenKind.IntegerLiteral);

            return new Id.Leaf(n);
        }

        /// <summary>
        /// IdNode := '(' Id ',' Id ')'
        /// </summary>
	    Id ParseIdNode()
	    {
	        Accept(TokenKind.LParen);

	        Id l = ParseId();

            Accept(TokenKind.Comma);

	        Id r = ParseId();

            Accept(TokenKind.RParen);

	        return new Id.Node(l, r);
	    }

        /// <summary>
        /// Event := EventLeaf | EventNode
        /// </summary>
	    Event ParseEvent()
	    {
	        Event e = null;
            switch (_currentToken.Kind)
            {
                case TokenKind.IntegerLiteral:
                    e = ParseEventLeaf();
                    break;
                case TokenKind.LParen:
                    e = ParseEventNode();
                    break;
                default:
                    ThrowUnexpectedToken(_currentToken.Kind);
                    break;
            }

	        return e;
	    }

        /// <summary>
        /// EventLeaf := INT_LITERAL
        /// </summary>
        Event ParseEventLeaf()
	    {
	        int n = int.Parse(_currentToken.Lexeme);
            Accept(TokenKind.IntegerLiteral);

            return new Event.Leaf(n);
	    }

        /// <summary>
        /// EventNode := '(' INT_LITERAL ',' Event ',' Event ')'
        /// </summary>
	    Event ParseEventNode()
	    {
	        Accept(TokenKind.LParen);

	        int n = int.Parse(_currentToken.Lexeme);
            Accept(TokenKind.IntegerLiteral);

            Accept(TokenKind.Comma);

	        Event l = ParseEvent();

            Accept(TokenKind.Comma);

	        Event r = ParseEvent();

            Accept(TokenKind.RParen);

            return new Event.Node(n, l, r);
	    }
	}
}


<|start_filename|>src/Itc4net/Binary/DecoderException.cs<|end_filename|>
using System;
using System.Runtime.Serialization;

namespace Itc4net.Binary
{
    [Serializable]
    public class DecoderException : Exception
    {
        public int? Expecting { get; }
        public int Found { get; }
        public int Position { get; }

        public DecoderException(string message) : base(message)
        {
        }

        public DecoderException(string message, int? expecting, int found, int position) : base(message)
        {
            Expecting = expecting;
            Found = found;
            Position = position;
        }

        protected DecoderException(
            SerializationInfo info,
            StreamingContext context) : base(info, context)
        {
        }
    }
}

<|start_filename|>src/Itc4net.Tests/Binary/BitReaderTests.cs<|end_filename|>
﻿using System;
using System.IO;
using FluentAssertions;
using Itc4net.Binary;
using NUnit.Framework;

namespace Itc4net.Tests.Binary
{
    [TestFixture]
    public class BitReaderTests
    {
        [Test]
        public void ReadBitsShouldBeAbleToReadSuccessive8Bits()
        {
            byte[] bytes = { 0x55, 0xAA };
            using (var reader = new BitReader(new MemoryStream(bytes)))
            {
                byte b1;
                reader.ReadBits(8, out b1); // 01010101 10101010
                                            // ^^^^^^^^          ~~> 01010101 = 0x55
                b1.Should().Be(0x55);

                byte b2;
                reader.ReadBits(8, out b2); // 01010101 10101010
                                            //          ^^^^^^^^ ~~> 10101010 = 0xAA
                b2.Should().Be(0xAA);
            }
        }

        [Test]
        public void ReadBitsShouldBeAbleToReadSuccessive5Bits()
        {
            byte[] bytes = { 0x55, 0xAA };
            using (var reader = new BitReader(new MemoryStream(bytes)))
            {
                byte b1;
                reader.ReadBits(5, out b1); // 01010101 10101010
                                            // ^^^^^             ~~> 00001010 = 0x0A
                b1.Should().Be(0x0A);

                byte b2;
                reader.ReadBits(5, out b2); // 01010101 10101010
                                            //      ^^^ ^^       ~~> 00010110 = 0x16
                b2.Should().Be(0x16);
            }
        }

        [Test]
        public void ReadBitsShouldBeAbleToReadSuccessive5BitsThen4BitsThen2Bits()
        {
            byte[] bytes = { 0x55, 0xAA };
            using (var reader = new BitReader(new MemoryStream(bytes)))
            {
                byte b1;
                reader.ReadBits(5, out b1); // 01010101 10101010
                                            // ^^^^^             ~~> 00001010 = 0x0A
                b1.Should().Be(0x0A);

                byte b2;
                reader.ReadBits(4, out b2); // 01010101 10101010
                                            //      ^^^ ^        ~~> 00001011 = 0x0B
                b2.Should().Be(0x0B);

                byte b3;
                reader.ReadBits(2, out b3); // 01010101 10101010
                                            //           ^^      ~~> 00000001 = 0x01
                b3.Should().Be(0x01);
            }
        }

        [Test]
        public void ReadBitsShouldReturnActualBitsRead()
        {
            byte[] bytes = { 0x55, 0xAA };
            using (var reader = new BitReader(new MemoryStream(bytes)))
            {
                byte b1;
                int bitsRead1 = reader.ReadBits(5, out b1);
                bitsRead1.Should().Be(5);

                byte b2;
                int bitsRead2 = reader.ReadBits(4, out b2);
                bitsRead2.Should().Be(4);

                byte b3;
                int bitsRead3 = reader.ReadBits(2, out b3);
                bitsRead3.Should().Be(2);
            }
        }

        [Test]
        public void ReadBitsShouldReturnActualBitsReadWhenReadingEndOfStream()
        {
            byte[] bytes = { 0x55 };
            using (var reader = new BitReader(new MemoryStream(bytes)))
            {
                byte b1;
                int bitsRead1 = reader.ReadBits(5, out b1); // 01010101 --------
                                                            // ^^^^^    ~~> 00001010 = 0x0A
                b1.Should().Be(0x0A);
                bitsRead1.Should().Be(5);

                byte b2;
                int bitsRead2 = reader.ReadBits(5, out b2); // 01010101 --------
                                                            //      ^^^ ^^
                                                            // Possible alternatives:
                                                            // 1. 00000101 = 0x05 (right-aligned)
                                                            //         ^^^
                                                            // 2. 00010100 = 0x14 (zero padded)
                                                            //       ^^^^^
                                                            // Using option #2
                b2.Should().Be(0x14);
                bitsRead2.Should().Be(3);
            }
        }

        [Test]
        public void ReadBitsShouldReturnEndOfStreamConstReadWhenReadingBeyondEndOfStream()
        {
            byte[] bytes = { 0x55 };
            using (var reader = new BitReader(new MemoryStream(bytes)))
            {
                byte b1;
                int bitsRead1 = reader.ReadBits(5, out b1); // 01010101 --------
                                                            // ^^^^^    ~~> 00001010 = 0x0A
                b1.Should().Be(0x0A);
                bitsRead1.Should().Be(5);

                byte b2;
                int bitsRead2 = reader.ReadBits(5, out b2); // 01010101 -------- (reach end of stream)
                                                            //      ^^^ ^^ ~~> 00010100 = 0x14
                b2.Should().Be(0x14);
                bitsRead2.Should().Be(3);

                byte b3;
                int bitsRead3 = reader.ReadBits(5, out b3); // 01010101 -------- (beyond end of stream)
                                                            //            ^^^^^^ ~~> 0x00
                b3.Should().Be(0x00);
                bitsRead3.Should().Be(0);
            }
        }
    }
}


<|start_filename|>src/Itc4net/Binary/BitReader.cs<|end_filename|>
using System;
using System.IO;

namespace Itc4net.Binary
{
    class BitReader : BitProcessor
    {
        public BitReader(byte[] bytes) : this(new MemoryStream(bytes))
        {
        }

        public BitReader(Stream stream) : this(stream, false)
        {
        }

        public BitReader(Stream stream, bool leaveOpen) : base(stream, leaveOpen)
        {
            RelativePosition = 0;
            CurrentByte = EndOfStream;
        }

        public int ReadBits(int bitCount, out byte value)
        {
            if (bitCount < 0 || bitCount > 8)
            {
                throw new ArgumentOutOfRangeException(nameof(bitCount), bitCount, "Must be between 0 and 8 (inclusive).");
            }

            // Attempt to read the next byte to prime CurrentByte
            if (CurrentByte == EndOfStream)
            {
                CurrentByte = BaseStream.ReadByte();
            }

            value = 0;
            int actualBitsRead = 0;
            if (CurrentByte != EndOfStream)
            {
                int shift = 8 - RelativePosition - bitCount;
                value = shift > 0 ? (byte)(CurrentByte >> shift) : (byte)(CurrentByte << Math.Abs(shift));
                value = (byte) (value & CreateMask(bitCount));
                actualBitsRead += bitCount;

                if (shift > 0)
                {
                    RelativePosition += bitCount;
                }
                else // reached or exceeded byte boundary
                {
                    RelativePosition = 0;
                    CurrentByte = BaseStream.ReadByte();

                    if (shift < 0)
                    {
                        actualBitsRead = bitCount + shift;

                        byte remainingValue;
                        actualBitsRead += ReadBits((byte) Math.Abs(shift), out remainingValue);
                        value |= remainingValue;
                    }
                }
            }

            return actualBitsRead;
        }
    }
}

<|start_filename|>src/Itc4net.Tests/IdTests.cs<|end_filename|>
﻿using System;
using System.Diagnostics.CodeAnalysis;
using FluentAssertions;
using NSubstitute;
using NUnit.Framework;

namespace Itc4net.Tests
{
    [SuppressMessage("ReSharper", "InconsistentNaming")]
    [TestFixture]
    public class IdTests
    {
        [Test]
        public void ToStringShouldCorrectlyRepresentLeafWith0()
        {
            new Id.Leaf(0).ToString().Should().Be("0");
        }

        [Test]
        public void ToStringShouldCorrectlyRepresentLeafWith1()
        {
            new Id.Leaf(1).ToString().Should().Be("1");
        }

        [Test]
        public void ToStringShouldCorrectlyRepresentNode()
        {
            var id = new Id.Node(1, new Id.Node(0, 1));

            id.ToString().Should().Be("(1,(0,1))");
        }

        [Test]
        public void LeafCtorShouldAccept0()
        {
            new Id.Leaf(0).Value.Should().Be(0);
        }

        [Test]
        public void LeafCtorShouldAccept1()
        {
            new Id.Leaf(1).Value.Should().Be(1);
        }

        [Test]
        public void LeafCtorShouldThrowWhenLessThan0()
        {
            // ReSharper disable once ObjectCreationAsStatement
            Action act = () => new Id.Leaf(-1);
            act.ShouldThrow<ArgumentOutOfRangeException>();
        }

        [Test]
        public void LeafCtorShouldThrowWhenGreaterThan1()
        {
            // ReSharper disable once ObjectCreationAsStatement
            Action act = () => new Id.Leaf(2);
            act.ShouldThrow<ArgumentOutOfRangeException>();
        }

        [Test]
        public void NodeCtorShouldThrowWhenLeftIdNull()
        {
            Action act = () => new Id.Node(null, 0);
            act.ShouldThrow<ArgumentNullException>();
        }

        [Test]
        public void NodeCtorShouldThrowWhenRightIdNull()
        {
            Action act = () => new Id.Node(0, null);
            act.ShouldThrow<ArgumentNullException>();
        }

        [Test]
        public void MatchShouldInvokeLeafFuncWhenIdRepresentsLeaf()
        {
            // Arrange
            Id id = new Id.Leaf(0);

            Func<int, object> leafFn = Substitute.For<Func<int, object>>();
            Func<Id, Id, object> nodeFn = Substitute.For<Func<Id, Id, object>>();

            // Act
            id.Match(leafFn, nodeFn);

            // Assert
            leafFn.Received().Invoke(0);
            nodeFn.DidNotReceiveWithAnyArgs();
        }

        [Test]
        public void MatchShouldInvokeNodeFuncWhenIdRepresentsNode()
        {
            // Arrange
            Id id = new Id.Node(0, 1);

            Func<int, object> leafFn = Substitute.For<Func<int, object>>();
            Func<Id, Id, object> nodeFn = Substitute.For<Func<Id, Id, object>>();

            // Act
            id.Match(leafFn, nodeFn);

            // Assert
            leafFn.DidNotReceiveWithAnyArgs();
            nodeFn.Received().Invoke(0, 1);
        }

        [Test]
        public void MatchShouldInvokeLeafActionWhenIdRepresentsLeaf()
        {
            // Arrange
            Id id = new Id.Leaf(0);

            Action<int> leafAction = Substitute.For<Action<int>>();
            Action<Id, Id> nodeAction = Substitute.For<Action<Id, Id>>();

            // Act
            id.Match(leafAction, nodeAction);

            // Assert
            leafAction.Received().Invoke(0);
            nodeAction.DidNotReceiveWithAnyArgs();
        }

        [Test]
        public void MatchShouldInvokeNodeActionWhenIdRepresentsNode()
        {
            // Arrange
            Id id = new Id.Node(0, 1);

            Action<int> leafAction = Substitute.For<Action<int>>();
            Action<Id, Id> nodeAction = Substitute.For<Action<Id, Id>>();

            // Act
            id.Match(leafAction, nodeAction);

            // Assert
            leafAction.DidNotReceiveWithAnyArgs();
            nodeAction.Received().Invoke(0, 1);
        }

        [Test(Description = "norm(i) = i")]
        public void NormalizeShouldReturniWhenLeafIsi()
        {
            // Arrange
            Id id = new Id.Leaf(1);

            // Act
            Id normalized = id.Normalize();

            // Assert
            normalized.Should().Be((Id)1);
        }

        [Test(Description = "norm((0,0)) = 0")]
        public void NormalizeShouldReturn0WhenNodeIs0and0()
        {
            // Arrange
            Id id = new Id.Node(0, 0);

            // Act
            Id normalized = id.Normalize();

            // Assert
            normalized.Should().Be((Id)0);
        }

        [Test(Description = "norm((1,1)) = 1")]
        public void NormalizeShouldReturn1WhenNodeIs1and1()
        {
            // Arrange
            Id id = new Id.Node(1, 1);

            // Act
            Id normalized = id.Normalize();

            // Assert
            normalized.Should().Be((Id)1);
        }

        [Test]
        public void NormalizeShouldReturnUnchangedWhenNodeCannotBeSimplifiedLike0and1()
        {
            // Arrange
            Id id = new Id.Node(0, 1);

            // Act
            Id normalized = id.Normalize();

            // Assert
            normalized.Should().Be(id);
        }

        [Test]
        public void NormalizeShouldReturnUnchangedWhenNodeCannotBeSimplifiedLike1and0()
        {
            // Arrange
            Id id = new Id.Node(1, 0);

            // Act
            Id normalized = id.Normalize();

            // Assert
            normalized.Should().Be(id);
        }

        [Test]
        public void EqualsShouldReturnTrueWhenComparingLeafsWithSameValues()
        {
            // Arrange
            Id i1 = new Id.Leaf(0);
            Id i2 = new Id.Leaf(0);

            // Act & Assert
            i1.Equals(i2).Should().BeTrue();
        }

        [Test]
        public void EqualsShouldReturnFalseWhenComparingLeafsWithDifferentValues()
        {
            // Arrange
            Id i1 = new Id.Leaf(0);
            Id i2 = new Id.Leaf(1);

            // Act & Assert
            i1.Equals(i2).Should().BeFalse();
        }

        [Test]
        public void EqualsShouldReturnTrueWhenComparingNodesWithSameValues()
        {
            // Arrange
            Id i1 = new Id.Node(0, 1);
            Id i2 = new Id.Node(0, 1);

            // Act & Assert
            i1.Equals(i2).Should().BeTrue();
        }

        [Test]
        public void EqualsShouldReturnFalseWhenComparingNodesWithDifferentValues()
        {
            // Arrange
            Id i1 = new Id.Node(0, 0);
            Id i2 = new Id.Node(0, 1);

            // Act & Assert
            i1.Equals(i2).Should().BeFalse();
        }

        [Test]
        public void EqualsShouldReturnTrueWhenComparingComplexNodesWithSameValues()
        {
            // Arrange
            Id i1 = new Id.Node(new Id.Node(0, new Id.Node(1, 0)), new Id.Node(1, 0)); // ((0,(1,0)),(1,0))
            Id i2 = new Id.Node(new Id.Node(0, new Id.Node(1, 0)), new Id.Node(1, 0)); // ((0,(1,0)),(1,0))

            // Act & Assert
            i1.Equals(i2).Should().BeTrue();
        }

        [Test]
        public void EqualsShouldReturnFalseWhenComparingComplexNodesWithDifferentValues()
        {
            // Arrange
            Id i1 = new Id.Node(new Id.Node(0, new Id.Node(1, 0)), new Id.Node(1, 0)); // ((0,(1,0)),(1,0))
            Id i2 = new Id.Node(new Id.Node(0, new Id.Node(1, 1)), new Id.Node(1, 0)); // ((0,(1,1)),(1,0))

            // Act & Assert
            i1.Equals(i2).Should().BeFalse();
        }

        [Test]
        public void GetHashCodeShouldMatchWhenLeafsHaveSameValues()
        {
            // Arrange
            // Arrange
            Id i1 = new Id.Leaf(0);
            Id i2 = new Id.Leaf(0);

            // Act
            int hash1 = i1.GetHashCode();
            int hash2 = i2.GetHashCode();

            // Assert
            hash1.Should().Be(hash2);
        }

        [Test]
        public void GetHashCodeShouldNotMatchWhenLeafsHaveDifferentValues()
        {
            // Arrange
            // Arrange
            Id i1 = new Id.Leaf(0);
            Id i2 = new Id.Leaf(1);

            // Act
            int hash1 = i1.GetHashCode();
            int hash2 = i2.GetHashCode();

            // Assert
            hash1.Should().NotBe(hash2);
        }

        [Test]
        public void GetHashCodeShouldMatchWhenNodesHaveSameValues()
        {
            // Arrange
            Id i1 = new Id.Node(0, 1);
            Id i2 = new Id.Node(0, 1);

            // Act
            int hash1 = i1.GetHashCode();
            int hash2 = i2.GetHashCode();

            // Assert
            hash1.Should().Be(hash2);
        }

        [Test]
        public void GetHashCodeShouldNotMatchWhenNodesHaveDifferentValues()
        {
            // Arrange
            Id i1 = new Id.Node(0, 0);
            Id i2 = new Id.Node(0, 1);

            // Act
            int hash1 = i1.GetHashCode();
            int hash2 = i2.GetHashCode();

            // Assert
            hash1.Should().NotBe(hash2);
        }

        [Test]
        public void GetHashCodeShouldMatchWhenComplexNodesHaveSameValues()
        {
            // Arrange
            Id i1 = new Id.Node(new Id.Node(0, new Id.Node(1, 0)), new Id.Node(1, 0)); // ((0,(1,0)),(1,0))
            Id i2 = new Id.Node(new Id.Node(0, new Id.Node(1, 0)), new Id.Node(1, 0)); // ((0,(1,0)),(1,0))

            // Act
            int hash1 = i1.GetHashCode();
            int hash2 = i2.GetHashCode();

            // Assert
            hash1.Should().Be(hash2);
        }

        [Test]
        public void GetHashCodeShouldNotMatchWhenComplexNodesHaveDifferentValues()
        {
            // Arrange
            Id i1 = new Id.Node(new Id.Node(0, new Id.Node(1, 0)), new Id.Node(1, 0)); // ((0,(1,0)),(1,0))
            Id i2 = new Id.Node(new Id.Node(0, new Id.Node(1, 1)), new Id.Node(1, 0)); // ((0,(1,1)),(1,0))

            // Act
            int hash1 = i1.GetHashCode();
            int hash2 = i2.GetHashCode();

            // Assert
            hash1.Should().NotBe(hash2);
        }

        [Test(Description = "split(0) = (0,0)")]
        public void SplitShouldReturnNode00WhenLeaf0()
        {
            // split(0) = (0,0)
            Id zero = new Id.Leaf(0);
            zero.Split().Should().Be(new Id.Node(0,0));
        }

        [Test(Description = "split(1) = ((1,0),(0,1))")]
        public void SplitShouldReturnNode1001WhenLeaf1()
        {
            // split(1) = ((1,0),(0,1))
            Id one = new Id.Leaf(1);
            one.Split().Should().Be(new Id.Node(new Id.Node(1, 0), new Id.Node(0, 1)));
        }

        [Test(Description = "split((0,i)) = ((0,i1),(0,i2)) where (i1,i2) = split(i)")]
        public void SplitShouldReturnNode0i0iWhenLeftLeaf0()
        {
            // split((0,1)) = ((0,(1,0)),(0,(0,1)))
            Id id1 = new Id.Node(0, 1);
            id1.Split().Should().Be(
                new Id.Node(
                    new Id.Node(0, new Id.Node(1, 0)),
                    new Id.Node(0, new Id.Node(0, 1))
                )
            );

            // split((0,(0,1))) = ((0,(0,(1,0))),(0,(0,(0,1))))
            Id id2 = new Id.Node(0, new Id.Node(0, 1));
            id2.Split().Should().Be(
                new Id.Node(
                    new Id.Node(0, new Id.Node(0, new Id.Node(1, 0))),
                    new Id.Node(0, new Id.Node(0, new Id.Node(0, 1)))
                ));
        }

        [Test(Description = "split((i,0)) = ((i1,0),(i2,0)) where (i1,i2) = split(i)")]
        public void SplitShouldReturnNodei0i0WhenRightLeaf0()
        {
            // split((1,0)) = (((1,0),0),((0,1),0))
            Id id1 = new Id.Node(1, 0);
            id1.Split().Should().Be(
                new Id.Node(
                    new Id.Node(new Id.Node(1, 0), 0),
                    new Id.Node(new Id.Node(0, 1), 0)
                )
            );

            // split(((1,0),0)) = ((((1,0),0),0),(((0,1),0),0))
            Id id2 = new Id.Node(new Id.Node(1, 0), 0);
            id2.Split().Should().Be(
                new Id.Node(
                    new Id.Node(new Id.Node(new Id.Node(1, 0), 0), 0),
                    new Id.Node(new Id.Node(new Id.Node(0, 1), 0), 0)
                )
            );
        }

        [Test(Description = "split((i1,i2) = ((i1,0),(0,i2))")]
        public void SplitShouldReturnNodei00iWhenLeftAndRightNodes()
        {
            // split(((0,1),(1,0))) = (((0,1),0),((0,(1,0)))
            Id id = new Id.Node(new Id.Node(0,1), new Id.Node(1,0));
            id.Split().Should().Be(
                new Id.Node(
                    new Id.Node(new Id.Node(0, 1), 0),
                    new Id.Node(0, new Id.Node(1, 0))
                )
            );
        }

        [Test(Description = "sum(0,i) = i")]
        public void SumShouldReturniWhenLeftLeaf0()
        {
            Id sum1 = Id.Sum(0, 0);
            sum1.Should().Be(new Id.Leaf(0));

            Id sum2 = Id.Sum(0, 1);
            sum2.Should().Be(new Id.Leaf(1));

            Id sum3 = Id.Sum(0, new Id.Node(1, 0));
            sum3.Should().Be(new Id.Node(1, 0));

            Id sum4 = Id.Sum(0, new Id.Node(0, 1));
            sum4.Should().Be(new Id.Node(0, 1));
        }

        [Test(Description = "sum(i,0) = i")]
        public void SumShouldReturniWhenRightLeaf0()
        {
            Id sum1 = Id.Sum(0, 0);
            sum1.Should().Be(new Id.Leaf(0));

            Id sum2 = Id.Sum(1, 0);
            sum2.Should().Be(new Id.Leaf(1));

            Id sum3 = Id.Sum(new Id.Node(1, 0), 0);
            sum3.Should().Be(new Id.Node(1, 0));

            Id sum4 = Id.Sum(new Id.Node(0, 1), 0);
            sum4.Should().Be(new Id.Node(0, 1));
        }

        [Test(Description = "sum((l1,r1),(l2,r2)) = norm(sum(l1,l2),sum(r1,r2))")]
        public void SumShouldReturnSuml1l2Sumr1r2WhenLeftAndRightNodes()
        {
            Id sum1 = Id.Sum(new Id.Node(0, 1), new Id.Node(0, 1));
            sum1.Should().Be(new Id.Node(0, 1));

            Id sum2 = Id.Sum(new Id.Node(0, 1), new Id.Node(1, 0));
            sum2.Should().Be(new Id.Leaf(1)); // Id.Node(1,1) normalizes to 1

            Id sum3 = Id.Sum(new Id.Node(1, 0), new Id.Node(1, 0));
            sum3.Should().Be(new Id.Node(1, 0));

            Id sum4 = Id.Sum(new Id.Node(1, 0), new Id.Node(0, 1));
            sum4.Should().Be(new Id.Leaf(1)); // Id.Node(1,1) normalizes to 1
        }

        [Test]
        public void SumShouldReturnNode10WhenLeftNode100AndRightNode010()
        {
            // Arrange
            Id i1 = new Id.Node(new Id.Node(1, 0), 0);
            Id i2 = new Id.Node(new Id.Node(0, 1), 0);

            // Act
            Id sum = i1.Sum(i2);

            // Assert
            sum.Should().Be(new Id.Node(1, 0));
        }

        [Test]
        public void ImplicitConversionOperatorShouldReturnLeafWhenInteger()
        {
            Id i1 = new Id.Leaf(1);
            Id i2 = 1;

            i1.Equals(i2).Should().BeTrue();
        }

        [Test]
        public void ImplicitConversionOperatorShouldReturnNodeWhenTuple()
        {
            // Arrange
            Id i1 = new Id.Node(new Id.Node(0, new Id.Node(1, 0)), new Id.Node(1, 0)); // ((0,(1,0)),(1,0))
            Id i2 = ((0,(1,0)),(1,0)); // combo of C#7 tuples and implicit conversion operator is wow!

            // Act & Assert
            i1.Equals(i2).Should().BeTrue();
        }
    }
}


<|start_filename|>src/Itc4net/StampConverter.cs<|end_filename|>
﻿using System;
using System.ComponentModel;
using System.Globalization;

namespace Itc4net
{
    /// <summary>
    /// The <see cref="T:Itc4net.StampConverter" /> class is used to convert from one data type to 
    /// another. Access this class through the <see cref="T:System.ComponentModel.TypeDescriptor" /> object.
    /// </summary>
    public class StampConverter : TypeConverter
    {
        /// <inheritdoc/>
        public override bool CanConvertFrom(ITypeDescriptorContext context, Type sourceType)
        {
            if (sourceType == typeof(string))
            {
                return true;
            }

            return base.CanConvertFrom(context, sourceType);
        }

        /// <inheritdoc/>
        public override object ConvertFrom(ITypeDescriptorContext context, CultureInfo culture, object value)
        {
            string text = value as string;
            if (text != null)
            {
                return Stamp.Parse(text);
            }

            return base.ConvertFrom(context, culture, value);
        }
    }
}
