OpenNest/OpenNest.Tests/Sequencing/PlateSequencingTests.cs

using OpenNest.CNC.CuttingStrategy;
using OpenNest.Engine.CuttingPlanning;
using OpenNest.Engine.Sequencing;
using OpenNest.Geometry;
using OpenNest.IO;

namespace OpenNest.Tests.Sequencing;

public class PlateSequencingTests
{
    [Theory]
    [InlineData(1)]
    [InlineData(3)]
    public void ApplyAll_WithManagedNest_SequencesEveryPlateAndPreservesParts(int plateCount)
    {
        var nest = new Nest("sequence-all");
        var drawing = TestHelpers.MakeSquareDrawing();
        nest.Drawings.Add(drawing);
        for (var i = 0; i < plateCount; i++)
        {
            var plate = TestHelpers.MakePlate(60, 120,
                new Part(drawing, new Vector(10, 5)),
                new Part(drawing, new Vector(30, 20)),
                new Part(drawing, new Vector(20, 10)));
            plate.Quantity = i + 1;
            nest.Plates.Add(plate);
        }

        using var manager = new PlateManager(nest);
        manager.EnsureSentinel();
        manager.LoadFirst();
        var plates = nest.Plates.Take(plateCount).ToArray();
        var parameters = new SequenceParameters { Method = SequenceMethod.LeastCode };
        var expected = plates.Select(plate => Baseline(plate, parameters)).ToArray();
        var parts = plates.SelectMany(plate => plate.Parts)
            .Select(part => (Part: part, part.Program, part.Location, part.Rotation)).ToArray();
        var nested = drawing.Quantity.Nested;
        var added = new int[plateCount];
        for (var i = 0; i < plateCount; i++)
        {
            var index = i;
            plates[i].PartAdded += (_, _) => added[index]++;
        }

        PlateSequencing.ApplyAll(nest.Plates, parameters);

        Assert.Equal(plateCount + 1, nest.Plates.Count);
        Assert.Equal(plates, nest.Plates.Take(plateCount));
        Assert.Empty(nest.Plates[^1].Parts);
        Assert.Same(plates[0], manager.CurrentPlate);
        for (var i = 0; i < plateCount; i++)
        {
            Assert.Equal(expected[i], plates[i].Parts);
            Assert.Equal(expected[i].Length, added[i]);
            Assert.Equal(i + 1, plates[i].Quantity);
        }
        Assert.Equal(nested, drawing.Quantity.Nested);
        foreach (var item in parts)
        {
            Assert.Same(item.Program, item.Part.Program);
            Assert.Equal(item.Location, item.Part.Location);
            Assert.Equal(item.Rotation, item.Part.Rotation);
        }
    }

    [Fact]
    public void ApplyAll_EmptyNestAndSentinelOnly_AreUnchanged()
    {
        var nest = new Nest("empty");
        var parameters = new SequenceParameters { Method = SequenceMethod.LeastCode };
        PlateSequencing.ApplyAll(nest.Plates, parameters);
        Assert.Empty(nest.Plates);

        using var manager = new PlateManager(nest);
        manager.EnsureSentinel();
        var sentinel = Assert.Single(nest.Plates);

        PlateSequencing.ApplyAll(nest.Plates, parameters);

        Assert.Same(sentinel, Assert.Single(nest.Plates));
        Assert.Empty(sentinel.Parts);
    }

    [Fact]
    public void ApplyAll_InvalidSequenceMethod_LeavesAllPlatesUntouched()
    {
        var nest = new Nest("invalid-sequence");
        nest.Plates.Add(TestHelpers.MakePlate(60, 120, TestHelpers.MakePartAt(10, 5)));
        nest.Plates.Add(TestHelpers.MakePlate(60, 120, TestHelpers.MakePartAt(30, 20)));
        using var manager = new PlateManager(nest);
        manager.EnsureSentinel();
        var plates = nest.Plates.ToArray();
        var parts = plates.Select(plate => plate.Parts.ToArray()).ToArray();

        Assert.Throws<NotSupportedException>(() => PlateSequencing.ApplyAll(nest.Plates,
            new SequenceParameters { Method = (SequenceMethod)999 }));

        Assert.Equal(plates, nest.Plates);
        for (var i = 0; i < plates.Length; i++)
            Assert.Equal(parts[i], plates[i].Parts);
    }

    [Fact]
    public void ApplyAll_WithManagedNest_PreservesCutOffDependenciesOnEveryPlate()
    {
        var nest = new Nest("sequence-all-cutoffs");
        var plates = new[]
        {
            TestHelpers.MakePlate(60, 120, TestHelpers.MakePartAt(10, 10, 10)),
            TestHelpers.MakePlate(60, 120, TestHelpers.MakePartAt(10, 30, 10)),
        };
        var parts = plates.Select(plate => Assert.Single(plate.Parts)).ToArray();
        foreach (var plate in plates)
        {
            plate.CutOffs.Add(new CutOff(new Vector(15, 0), CutOffAxis.Vertical));
            plate.RegenerateCutOffs(new CutOffSettings());
            nest.Plates.Add(plate);
        }
        using var manager = new PlateManager(nest);
        manager.EnsureSentinel();

        PlateSequencing.ApplyAll(nest.Plates,
            new SequenceParameters { Method = SequenceMethod.LeastCode });

        for (var i = 0; i < plates.Length; i++)
            AssertPrecedes(plates[i], Assert.Single(plates[i].CutOffs), parts[i]);
    }

    [Fact]
    public void Apply_WithoutCutOffs_PreservesExistingReversedSequencerOrder()
    {
        var plate = TestHelpers.MakePlate(60, 120,
            TestHelpers.MakePartAt(10, 5), TestHelpers.MakePartAt(30, 20),
            TestHelpers.MakePartAt(20, 10));
        var parameters = new SequenceParameters { Method = SequenceMethod.LeastCode };
        var expected = Baseline(plate, parameters);

        PlateSequencing.Apply(plate, parameters);

        Assert.Equal(expected, plate.Parts);
    }

    [Theory]
    [InlineData(CutOffAxis.Vertical, CutDirection.AwayFromOrigin)]
    [InlineData(CutOffAxis.Vertical, CutDirection.TowardOrigin)]
    [InlineData(CutOffAxis.Horizontal, CutDirection.AwayFromOrigin)]
    [InlineData(CutOffAxis.Horizontal, CutDirection.TowardOrigin)]
    public void Apply_MovesEveryCrossingCutOffBeforeEveryCrossedPart(
        CutOffAxis axis, CutDirection direction)
    {
        var drawing = TestHelpers.MakeSquareDrawing();
        var first = new Part(drawing, new Vector(10, 10));
        var second = new Part(drawing, axis == CutOffAxis.Vertical
            ? new Vector(10, 30) : new Vector(30, 10));
        var unrelated = TestHelpers.MakePartAt(60, 50);
        var plate = TestHelpers.MakePlate(60, 120, first, second, unrelated);
        plate.Quantity = 2;
        var cutA = new CutOff(new Vector(13, 13), axis);
        var cutB = new CutOff(new Vector(17, 17), axis);
        plate.CutOffs.Add(cutA);
        plate.CutOffs.Add(cutB);
        var settings = new CutOffSettings { CutDirection = direction };
        plate.RegenerateCutOffs(settings);
        var parameters = new SequenceParameters { Method = SequenceMethod.LeastCode };
        var baseline = Baseline(plate, parameters);
        var programs = plate.Parts.Select(p => (Part: p, p.Program, p.Location, p.Rotation)).ToArray();
        var nested = drawing.Quantity.Nested;

        PlateSequencing.Apply(plate, parameters);

        AssertPrecedes(plate, cutA, first, second);
        AssertPrecedes(plate, cutB, first, second);
        Assert.Equal(baseline.Where(p => !p.BaseDrawing.IsCutOff),
            plate.Parts.Where(p => !p.BaseDrawing.IsCutOff));
        Assert.Equal(programs.Length, plate.Parts.Count);
        Assert.Equal(nested, drawing.Quantity.Nested);
        foreach (var item in programs)
        {
            Assert.Contains(item.Part, plate.Parts);
            Assert.Same(item.Program, item.Part.Program);
            Assert.Equal(item.Location, item.Part.Location);
            Assert.Equal(item.Rotation, item.Part.Rotation);
        }

        var sequence = plate.Parts.Select(p => p.BaseDrawing).ToArray();
        plate.RegenerateCutOffs(settings);
        Assert.Equal(sequence, plate.Parts.Select(p => p.BaseDrawing));
        AssertPrecedes(plate, cutA, first, second);
        AssertPrecedes(plate, cutB, first, second);
    }

    // The remnant's lines go last: the strip line stopping on the separator, then the separator.
    [Theory]
    [InlineData(SequenceMethod.RightSide)]
    [InlineData(SequenceMethod.LeftSide)]
    [InlineData(SequenceMethod.LeastCode)]
    public void Apply_RemnantLines_AreCutLastInnerFirst(SequenceMethod method)
    {
        var plate = new Plate(60, 120);
        plate.Parts.Add(TestHelpers.MakePartAt(10, 10, 10));
        plate.Parts.Add(TestHelpers.MakePartAt(50, 10, 10));
        var vertical = new CutOff(new Vector(80, 0), CutOffAxis.Vertical) { EndLimit = 30 };
        var horizontal = new CutOff(new Vector(0, 30), CutOffAxis.Horizontal);
        plate.CutOffs.Add(horizontal);
        plate.CutOffs.Add(vertical);
        plate.RegenerateCutOffs(new CutOffSettings());
        plate.Parts.Reorder([.. plate.Parts.Where(p => p.BaseDrawing.IsCutOff), .. plate.Parts.Where(p => !p.BaseDrawing.IsCutOff)]);

        PlateSequencing.Apply(plate, new SequenceParameters { Method = method });

        Assert.Same(vertical.Drawing, plate.Parts[^2].BaseDrawing);
        Assert.Same(horizontal.Drawing, plate.Parts[^1].BaseDrawing);

        // Placing them again after an edit keeps that order.
        plate.Parts.Reorder([plate.Parts[^1], plate.Parts[^2], .. plate.Parts.Take(plate.Parts.Count - 2)]);
        PlateSequencing.PlaceCutOffs(plate, [horizontal, vertical]);
        Assert.Same(vertical.Drawing, plate.Parts[^2].BaseDrawing);
        Assert.Same(horizontal.Drawing, plate.Parts[^1].BaseDrawing);
    }

    [Theory]
    [InlineData(SequenceMethod.RightSide)]
    [InlineData(SequenceMethod.LeftSide)]
    [InlineData(SequenceMethod.BottomSide)]
    [InlineData(SequenceMethod.EdgeStart)]
    [InlineData(SequenceMethod.LeastCode)]
    [InlineData(SequenceMethod.Advanced)]
    public void Apply_AllMethodsAndQuadrants_RespectCutOffDependencies(SequenceMethod method)
    {
        foreach (var quadrant in new[] { 1, 2, 3, 4 })
        {
            var plate = new Plate(60, 120) { Quadrant = quadrant };
            var bounds = plate.BoundingBox(false);
            var part = TestHelpers.MakePartAt(bounds.Left + 20, bounds.Bottom + 20, 10);
            part.Rotate(System.Math.PI / 4, part.Location);
            Assert.True(bounds.Contains(part.BoundingBox));
            plate.Parts.Add(part);
            var center = part.BoundingBox.Center;
            var vertical = new CutOff(center, CutOffAxis.Vertical);
            var horizontal = new CutOff(center, CutOffAxis.Horizontal);
            plate.CutOffs.Add(vertical);
            plate.CutOffs.Add(horizontal);
            plate.RegenerateCutOffs(new CutOffSettings());

            PlateSequencing.Apply(plate, new SequenceParameters { Method = method });

            AssertPrecedes(plate, vertical, part);
            AssertPrecedes(plate, horizontal, part);
        }
    }

    [Theory]
    [InlineData(CutOffAxis.Vertical, SequenceMethod.LeftSide)]
    [InlineData(CutOffAxis.Horizontal, SequenceMethod.BottomSide)]
    public void Apply_LimitedSameNamedCutOffs_OnlyMoveBeforePartsWithinTheirSpans(
        CutOffAxis axis, SequenceMethod method)
    {
        var first = TestHelpers.MakePartAt(10, 10, 10);
        var second = axis == CutOffAxis.Vertical
            ? TestHelpers.MakePartAt(10, 30, 10) : TestHelpers.MakePartAt(30, 10, 10);
        var plate = TestHelpers.MakePlate(60, 120, first, second);
        var lower = new CutOff(new Vector(15, 15), axis) { StartLimit = 5, EndLimit = 25 };
        var upper = new CutOff(new Vector(15, 15), axis) { StartLimit = 25, EndLimit = 45 };
        plate.CutOffs.Add(lower);
        plate.CutOffs.Add(upper);
        plate.RegenerateCutOffs(new CutOffSettings());
        Assert.Equal(lower.Drawing.Name, upper.Drawing.Name);
        // Each line is trimmed around its part into two segment parts.
        var lowerParts = TestHelpers.CutOffParts(plate, lower);
        var upperParts = TestHelpers.CutOffParts(plate, upper);
        Assert.Equal(2, lowerParts.Length);
        Assert.Equal(2, upperParts.Length);

        PlateSequencing.Apply(plate, new SequenceParameters { Method = method });

        Assert.Equal(upperParts.Append(second).Concat(lowerParts).Append(first), plate.Parts);
        Assert.Equal(new[] { lower, upper }, plate.CutOffs);
    }

    [Fact]
    public void Apply_SheetSeparatingCutOff_GoesAfterEveryPartAndCrossingCutOff()
    {
        var hazards = 0;
        foreach (var method in Enum.GetValues<SequenceMethod>())
        {
            var left = TestHelpers.MakePartAt(10, 10, 10);
            var right = TestHelpers.MakePartAt(80, 10, 10);
            var plate = TestHelpers.MakePlate(60, 120, left, right);
            var separator = new CutOff(new Vector(40, 0), CutOffAxis.Vertical);
            var crossing = new CutOff(new Vector(85, 0), CutOffAxis.Vertical);
            plate.CutOffs.Add(separator);
            plate.CutOffs.Add(crossing);
            plate.RegenerateCutOffs(new CutOffSettings());
            var parameters = new SequenceParameters { Method = method };
            var separatorPart = plate.Parts.Single(p => ReferenceEquals(p.BaseDrawing, separator.Drawing));
            List<Part> baseline;
            try
            {
                baseline = Baseline(plate, parameters).ToList();
            }
            catch (NotSupportedException)
            {
                continue;
            }
            if (baseline.IndexOf(separatorPart) < baseline.IndexOf(right)
                || baseline.IndexOf(separatorPart) < baseline.IndexOf(left))
                hazards++;

            PlateSequencing.Apply(plate, parameters);

            Assert.Same(separatorPart, plate.Parts[^1]);
            AssertPrecedes(plate, crossing, right);
            Assert.Equal(5, plate.Parts.Count); // The crossing line is two segment parts.
        }
        // Without the rule, at least one route cuts the separator before a part.
        Assert.True(hazards > 0);
    }

    [Fact]
    public void Apply_OrphanedCutOff_ConservativelyPrecedesAllParts()
    {
        var part = TestHelpers.MakePartAt(10, 10, 10);
        var orphan = TestHelpers.MakePartAt(0, 0);
        orphan.BaseDrawing.IsCutOff = true;
        var plate = TestHelpers.MakePlate(60, 120, part, orphan);

        PlateSequencing.Apply(plate,
            new SequenceParameters { Method = SequenceMethod.LeftSide });

        Assert.Equal(new[] { orphan, part }, plate.Parts);
    }

    [Fact]
    public void Apply_EmptyAndCutOffOnlyPlates_PreserveAllEntries()
    {
        var plate = new Plate(60, 120);
        var parameters = new SequenceParameters { Method = SequenceMethod.LeastCode };
        PlateSequencing.Apply(plate, parameters);
        Assert.Empty(plate.Parts);

        plate.CutOffs.Add(new CutOff(new Vector(10, 0), CutOffAxis.Vertical));
        plate.CutOffs.Add(new CutOff(new Vector(20, 0), CutOffAxis.Vertical));
        plate.RegenerateCutOffs(new CutOffSettings());
        var expected = Baseline(plate, parameters);

        PlateSequencing.Apply(plate, parameters);

        Assert.Equal(expected, plate.Parts);
    }

    [Fact]
    public void Apply_SaveAndReload_PreservesCorrectedMixedSequence()
    {
        var nest = new Nest("sequenced-cutoffs");
        var drawing = TestHelpers.MakeSquareDrawing();
        nest.Drawings.Add(drawing);
        var part = new Part(drawing, new Vector(10, 10));
        var plate = TestHelpers.MakePlate(60, 120, part);
        nest.Plates.Add(plate);
        var crossing = new CutOff(new Vector(15, 0), CutOffAxis.Vertical);
        var tail = new CutOff(new Vector(40, 0), CutOffAxis.Vertical);
        plate.CutOffs.Add(crossing);
        plate.CutOffs.Add(tail);
        plate.RegenerateCutOffs(new CutOffSettings());
        PlateSequencing.Apply(plate,
            new SequenceParameters { Method = SequenceMethod.LeftSide });
        AssertPrecedes(plate, crossing, part);
        Assert.Equal(2, TestHelpers.CutOffParts(plate, crossing).Length); // Trimmed around the part.
        Assert.Same(part, plate.Parts[2]);
        var expected = plate.Parts.Select(p => p.BaseDrawing.Name).ToArray();

        using var stream = new MemoryStream();
        new NestWriter(nest).Write(stream);
        stream.Position = 0;
        var loaded = new NestReader(stream).Read();

        Assert.Equal(expected, loaded.Plates[0].Parts.Select(p => p.BaseDrawing.Name));
    }

    [Fact]
    public void Apply_InvalidSequenceMethod_LeavesPlateUntouched()
    {
        var plate = TestHelpers.MakePlate(60, 120, TestHelpers.MakePartAt(10, 5));
        var before = plate.Parts.ToArray();

        Assert.Throws<NotSupportedException>(() => PlateSequencing.Apply(plate,
            new SequenceParameters { Method = (SequenceMethod)999 }));

        Assert.Equal(before, plate.Parts);
    }

    [Theory]
    [InlineData(SequenceMethod.RightSide)]
    [InlineData(SequenceMethod.LeftSide)]
    [InlineData(SequenceMethod.BottomSide)]
    [InlineData(SequenceMethod.EdgeStart)]
    [InlineData(SequenceMethod.LeastCode)]
    [InlineData(SequenceMethod.Advanced)]
    public void Apply_CutFirstDrawing_SequencesItsPartsBeforeEveryOtherPart(SequenceMethod method)
    {
        var squares = TestHelpers.MakeSquareDrawing(1.5);
        squares.CutFirst = true;
        var parts = TestHelpers.MakeSquareDrawing();
        var plate = new Plate(60, 120);
        for (var i = 0; i < 10; i++)
            plate.Parts.Add(new Part(squares, new Vector(2 + i * 5, 50 + (i % 2) * 4)));
        for (var i = 0; i < 6; i++)
            plate.Parts.Add(new Part(parts, new Vector(5 + (i % 3) * 15, 5 + (i / 3) * 15)));
        var parameters = new SequenceParameters { Method = method };
        var others = plate.Parts.Where(p => !p.BaseDrawing.CutFirst).ToList();
        var expectedRest = PartSequencerFactory.Create(parameters).Sequence(others, plate)
            .Select(p => p.Part).Reverse().ToArray();

        PlateSequencing.Apply(plate, parameters);

        Assert.All(plate.Parts.Take(10), p => Assert.Same(squares, p.BaseDrawing));
        Assert.Equal(expectedRest, plate.Parts.Skip(10));
    }

    [Fact]
    public void Apply_CutFirstDrawing_StillFollowsCutOffsThatCrossIt()
    {
        var square = TestHelpers.MakePartAt(10, 10, 1.5);
        square.BaseDrawing.CutFirst = true;
        var other = TestHelpers.MakePartAt(30, 30, 10);
        var plate = TestHelpers.MakePlate(60, 120, other, square);
        var crossing = new CutOff(square.BoundingBox.Center, CutOffAxis.Vertical)
        { StartLimit = 0, EndLimit = 20 };
        plate.CutOffs.Add(crossing);
        plate.RegenerateCutOffs(new CutOffSettings());

        PlateSequencing.Apply(plate, new SequenceParameters { Method = SequenceMethod.LeftSide });

        AssertPrecedes(plate, crossing, square);
        Assert.Same(square, plate.Parts.First(p => !p.BaseDrawing.IsCutOff));
    }

    [Fact]
    public void PlaceCutOffs_PlacesEachSegmentBeforeTheFirstPartInItsSpan()
    {
        var upper = TestHelpers.MakePartAt(10, 30, 10);
        var lower = TestHelpers.MakePartAt(10, 10, 10);
        var plate = TestHelpers.MakePlate(60, 120, upper, lower);
        var cutOff = new CutOff(new Vector(15, 0), CutOffAxis.Vertical);
        plate.CutOffs.Add(cutOff);
        plate.RegenerateCutOffs(new CutOffSettings());
        var segments = CutOffSegments.Of(plate, cutOff).Select(s => s.Part).ToArray();
        Assert.Equal(new[] { upper, lower, segments[0], segments[1], segments[2] }, plate.Parts);

        PlateSequencing.PlaceCutOffs(plate, [cutOff]);

        // The bottom segment is beside the lower part only; the middle one beside both.
        Assert.Equal(new[] { segments[1], segments[2], upper, segments[0], lower }, plate.Parts);
    }

    [Fact]
    public void PlaceCutOffs_MovesOnlyTheGivenCutOffsWhereTheRulesNeedThem()
    {
        var a = TestHelpers.MakePartAt(10, 10, 10);
        var b = TestHelpers.MakePartAt(40, 10, 10);
        var c = TestHelpers.MakePartAt(70, 10, 10);
        var plate = TestHelpers.MakePlate(60, 120, a, b, c);
        var settings = new CutOffSettings();
        var existingSeparator = new CutOff(new Vector(110, 0), CutOffAxis.Vertical);
        plate.CutOffs.Add(existingSeparator);
        plate.RegenerateCutOffs(settings);
        var crossing = new CutOff(new Vector(45, 0), CutOffAxis.Vertical);
        var limited = new CutOff(new Vector(60, 0), CutOffAxis.Vertical) { EndLimit = 30 };
        var separator = new CutOff(new Vector(100, 0), CutOffAxis.Vertical);
        // As staging adds them: appended after everything, the existing separator included.
        plate.CutOffs.AddRange([crossing, limited, separator]);
        plate.RegenerateCutOffs(settings);
        Part[] Cut(CutOff cutOff) => TestHelpers.CutOffParts(plate, cutOff);
        Assert.Equal(2, Cut(crossing).Length); // Trimmed around b: two segment parts.
        Assert.Equal(new[] { a, b, c }.Concat(Cut(existingSeparator)).Concat(Cut(crossing)).Concat(Cut(limited))
            .Concat(Cut(separator)), plate.Parts);
        var removed = 0;
        plate.PartRemoved += (_, e) => Assert.True(e.Item.BaseDrawing.IsCutOff, "Only cut-off parts move.");
        plate.PartRemoved += (_, _) => removed++;

        PlateSequencing.PlaceCutOffs(plate, [crossing, limited, separator]);

        Assert.Equal(new[] { a }.Concat(Cut(crossing)).Concat([b, c]).Concat(Cut(limited)).Concat(Cut(existingSeparator))
            .Concat(Cut(separator)), plate.Parts);
        Assert.Equal(4, removed);
    }

    private static Part[] Baseline(Plate plate, SequenceParameters parameters) =>
        PartSequencerFactory.Create(parameters).Sequence(plate.Parts.ToList(), plate)
            .Select(p => p.Part).Reverse().ToArray();

    // Each of the cut-off's segment parts precedes the crossed parts in its span of the line,
    // and every crossed part follows at least one segment.
    private static void AssertPrecedes(Plate plate, CutOff cutOff, params Part[] crossed)
    {
        var bounds = plate.BoundingBox(includeParts: false);
        var segments = CutOffSegments.Of(plate, cutOff);
        Assert.NotEmpty(segments);
        foreach (var part in crossed)
        {
            var beside = segments.Where(segment => CuttingDependencyGraph.CutOffCrosses(cutOff.Axis, cutOff.Position,
                segment.SpanStart, segment.SpanEnd, part.BoundingBox, bounds)).ToList();
            Assert.NotEmpty(beside);
            foreach (var segment in beside)
                Assert.True(plate.Parts.IndexOf(segment.Part) < plate.Parts.IndexOf(part),
                    $"{cutOff.Drawing.Name} [{segment.Start}, {segment.End}] must precede the part at {part.Location}.");
        }
    }
}