Namespace AS2.Suboracles.Reconfiguration

Classes

MonotoneToLine

Implements the Monotone2LineSegment algorithm (https://doi.org/10.4230/LIPIcs.SAND.2026.11). Reconfigures a monotone structure to a line structure in constant time.

The suboracle is called on its representative, but stores some data in its members ParticleAttributes.

"We call the intersection of the amoebot structure with a line parallel to the x-axis an x-section. Note that an x-section is not necessarily connected. We define y- and z-sections analogously. In particular, we also call x-sections rows, and y-sections columns. We call an amoebot structure x-monotone if and only each x-section is connected. We define y- and z-monotone analogously. We call an amoebot structure monotone if and only if it is x-monotone, y-monotone, or z-monotone."

Parallelogram

Implements the parallelogram primitive for reconfiguration. See https://doi.org/10.4230/LIPIcs.SAND.2026.11.
The reconfiguration of an parallelogram where only the two sides incident to an obtuse corner are occupied by amoebots to a configuration where the other two sides of the parallelogram are occupied.

The algorithm applies two shearing operations on the first (shorter side length + 1) amoebots starting from the outer ends and requires two rounds to complete.

Rule12

Implements rules 1 and 2 of the MonotoneToLine algorithm.

These rules handle columns where different particles hold the left and right line bonds. A shear transformation is used on the column so that both bonds end up on the same particle. Rule 1: If the left line bond is above the right line bond, shear clockwise until they are on the same particle. Rule 2: If the right line bond is above the left line bond, shear counterclockwise until the left line bond is above the right line bond, then perform a second shear clockwise until they are on the same particle.

Rule3abc

Implements rules 3a, 3b, and 3c of the MonotoneToLine algorithm.

These rules handle columns where a single particle holds both the left and right line bonds. The representative expands, performs a handover with a neighbor followed by a contraction to redistribute the line bonds to adjacent particles. Rule 3a: neighbors above and below Rule 3b: only neighbors above, uneven column count Rule 3c: only neighbors below, uneven column count

Rule3de

Implements rules 3d and 3e of the MonotoneToLine algorithm.

These rules handle columns with an even number of particles where a single particle holds both the left and right line bonds. Every second particle expands, performs a handover with its neighbor, and then contracts to create two columns with half the particles each. Rule 3d: the bond-holding particle has a neighbor above. Rule 3e: the bond-holding particle has a neighbor below.

Spiral

Implements the Spiral2LineSegment algorithm. See https://doi.org/10.4230/LIPIcs.SAND.2026.11.
Reconfigures a spiral structure into a straight line while strictly preserving the sequence order of the amoebots.

The algorithm achieves constant time by first converting the spiral into a y-monotone structure. It constructs a base line, safely disconnects outer segments into independent arms, and aligns them in parallel using shearing operations. The final monotone structure is then straightened using the Monotone2Line algorithm.

Trapezoid

Implements the trapezoid primitive for reconfiguration. See https://doi.org/10.4230/LIPIcs.SAND.2026.11.
The constant-time reconfiguration of a trapezoid where only the shorter base and the legs are occupied, and a starting point (a node on the longer base) to a configuration where the base of the trapezoid and a path between the bases from the starting point are occupied.

The algorithm consists of three phases: the first phase splits the trapezoid into a triangle and parallelogram so that the starting point is in the triangle. Then the parallelogram primitive is applied on the parallelogram to partially occupy the longer base. The second phase has two cases: the starting point is in a corner of the triangle, then we apply the triangle primitive on the triangle so that the occupied leg starts at the starting point. Then the algorithm is finished. Otherwise, we split the triangle into two triangles and a parallelogram, so that the starting point is a corner of the lower triangle and parallelogram. Then we apply the triangle primitive to the upper triangle. The lower triangle and parallelogram form a trapezoid with an attached leg. The third phase is repeating the first and second phase with the leg attached. This time the algorithm finishes.

The algorithm also has the ability to flip the created arm at the end of the algorithm with the flipArm parameter.

Triangle

Implements the triangle primitive for reconfiguration. See https://doi.org/10.4230/LIPIcs.SAND.2026.11.
The constant-time reconfiguration of an equilateral triangle where only the two sides (legs) are occupied by amoebots to a configuration where the base of the triangle and one of the legs are occupied.

The algorithm consists of four phases: the first phase iteratively reduces the triangle, the second phase performs shearing operations to occupy the base of the triangle, the third phase uses shearing operations to occupy the nodes adjacent to the base, and the fourth phase performs shearing operations to occupy one of the legs.

The algorithm also has the ability to drag an arm of amoebots attached to the "top" of the triangle along while reducing and shearing. The arm is always assumed to be in lineDir, when an arm is present rotateOtherDir is required to be true.

Unrolling

Implements the unrolling algorithm. See https://doi.org/10.4230/LIPIcs.SAND.2026.11.
The unrolling of a spiral into a line, which preserves the order of the amoebots.

The algorithm repeatedly executes the shearing primitive, starting on the outermost segment and going inward to unroll the spiral into a line. The algorithm requires O(c) rounds, where c is the number of corners in the spiral.

Enums

Trapezoid.Phase

Triangle.Phase

Phases of the algorithm based on the paper