RedstoneWireTurbo.java

package carpet.helpers;
//Author: theosib

import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.concurrent.ThreadLocalRandom;
import net.minecraft.core.BlockPos;
import net.minecraft.core.Direction;
import net.minecraft.world.level.Level;
import net.minecraft.world.level.block.Block;
import net.minecraft.world.level.block.Blocks;
import net.minecraft.world.level.block.RedStoneWireBlock;
import net.minecraft.world.level.block.state.BlockState;
import carpet.fakes.RedstoneWireBlockInterface;

public class RedstoneWireTurbo
{
    /*
     * This is Helper class for RedstoneWireBlock.  It implements a minimially-invasive
     * bolt-on accelerator that performs a breadth-first search through redstone wire blocks
     * in order to more efficiently and deterministicly compute new redstone wire power levels
     * and determine the order in which other blocks should be updated.  
     *
     * Features:
     * - Changes to RedstoneWireBlock are very limited, no other classes are affected, and the 
     *   choice between old and new redstone wire update algorithms is switchable on-line.
     * - The vanilla implementation relied on World.notifyNeighborsOfStateChange for redstone 
     *   wire blocks to communicate power level changes to each other, generating 36 block 
     *   updates per call.  This improved implementation propagates power level changes directly
     *   between redstone wire blocks.  Redstone wire power levels are therefore computed more quickly, 
     *   and block updates are sent only to non-redstone blocks, many of which may perform an 
     *   action when informed of a change in redstone power level.  (Note:  Block updates are not
     *   the same as state changes to redstone wire.  Wire block states are updated as soon
     *   as they are computed.)
     * - Of the 36 block updates generated by a call to World.notifyNeighborsOfStateChange,
     *   12 of them are obviously redundant (e.g. the west neighbor of the east neighbor).
     *   These are eliminated.
     * - Updates to redstone wire and other connected blocks are propagated in a breath-first
     *   manner, radiating out from the initial trigger (a block update to a redstone wire
     *   from something other than redstone wire).
     * - Updates are scheduled both deterministicly and in an intuitive order, addressing bug
     *   MC-11193. 
     * - All redstone behavior that used to be locational now works the same in all locations.
     * - All behaviors of redstone wire that used to be orientational now work the same in all
     *   orientations, as long as orientation can be determined; random otherwise.  Some other
     *   redstone components still update directionally (e.g. switches), and this code can't
     *   compensate for that.
     * - Information that is otherwise computed over and over again or which is expensive to 
     *   to compute is cached for faster lookup.  This includes coordinates of block position 
     *   neighbors and block states that won't change behind our backs during the execution of 
     *   this search algorithm.
     * - Redundant block updates (both to redstone wire and to other blocks) are heavily 
     *   consolidated.  For worst-case scenarios (depowering of redstone wire) this results
     *   in a reduction of block updates by as much as 95% (factor of 1/21).  Due to overheads, 
     *   empirical testing shows a speedup better than 10x.  This addresses bug MC-81098.
     *
     * Extensive testing has been performed to ensure that existing redstone contraptions still
     * behave as expected.  Results of early testing that identified undesirable behavior changes
     * were addressed.  Additionally, real-time performance testing revealed compute inefficiencies
     * With earlier implementations of this accelerator.  Some compatibility adjustments and 
     * performance optimizations resulted in harmless increases in block updates above the 
     * theoretical minimum.
     * 
     * Only a single redstone machine was found to break:  An instant dropper line hack that
     * relies on powered rails and quasiconnectivity but doesn't work in all directions.  The 
     * replacement is to lay redstone wire directly on top of the dropper line, which now works
     * reliably in any direction.
     * 
     * There are numerous other optimization that can be made, but those will be provided later in
     * separate updates.  This version is designed to be minimalistic.
     *
     * Many thanks to the following individuals for their help in testing this functionality:
     * - pokechu22, _MethodZz_, WARBEN, NarcolepticFrog, CommandHelper (nessie), ilmango,
     *   OreoLamp, Xcom6000, tryashtar, RedCMD, Smokey95Dog, EDDxample, Rays Works,
     *   Nodnam, BlockyPlays, Grumm, NeunEinser, HelVince.
     */
     
     
    /* Reference to RedstoneWireBlock object, which uses this accelerator */
    private final RedStoneWireBlock wire;
     
     
    /*
     * Implementation:
     *  
     * RedstoneWire Blocks are updated in concentric rings or "layers" radiating out from the 
     * initial block update that came from a call to RedstoneWireBlock.neighborChanged().
     * All nodes put in Layer N are those with Manattan distance N from the trigger
     * position, reachable through connected redstone wire blocks.
     *
     * Layer 0 represents the trigger block position that was input to neighborChanged.
     * Layer 1 contains the immediate neighbors of that position.
     * Layer N contains the neighbors of blocks in layer N-1, not including
     *    those in previous layers.
     * 
     * Layers enforce an update order that is a function of Manhattan distance
     * from the initial coordinates input to neighborChanged.  The same 
     * coordinates may appear in multiple layers, but redundant updates are minimized.  
     * Block updates are sent layer-by-layer.  If multiple of a block's neighbors experience 
     * redstone wire changes before its layer is processed, then those updates will be merged.
     * If a block's update has been sent, but its neighboring redstone changes
     * after that, then another update will be sent.  This preserves compatibility with
     * machines that rely on zero-tick behavior, except that the new functionality is non-
     * locational.
     *
     * Within each layer, updates are ordered left-to-right relative to the direction of
     * information flow.  This makes the implementation non-orientational.  Only when
     * this direction is ambiguous is randomness applied (intentionally).
     */
    //private final List<List<UpdateNode>> updateLayers = new ArrayList<>();
    private List<UpdateNode> updateQueue0 = new ArrayList<>();
    private List<UpdateNode> updateQueue1 = new ArrayList<>();
    private List<UpdateNode> updateQueue2 = new ArrayList<>();
     
     
    public RedstoneWireTurbo(RedStoneWireBlock wire) {
        this.wire = wire;
    }
 
     
    /* 
     * Compute neighbors of a block.  When a redstone wire value changes, previously it called
     * World.notifyNeighborsOfStateChange.  That lists immediately neighboring blocks in
     * west, east, down, up, north, south order.  For each of those neighbors, their own
     * neighbors are updated in the same order.  This generates 36 updates, but 12 of them are
     * redundant; for instance the west neighbor of a block's east neighbor.
     *
     * Note that this ordering is only used to create the initial list of neighbors.  Once
     * the direction of signal flow is identified, the ordering of updates is completely 
     * reorganized.
    */
    public static BlockPos[] computeAllNeighbors(final BlockPos pos) {
        final int x = pos.getX();
        final int y = pos.getY();
        final int z = pos.getZ();
        final BlockPos[] n = new BlockPos[24];
 
        // Immediate neighbors, in the same order as 
        // World.notifyNeighborsOfStateChange, etc.:
        // west, east, down, up, north, south
        n[ 0] = new BlockPos(x-1, y  , z  ); 
        n[ 1] = new BlockPos(x+1, y  , z  ); 
        n[ 2] = new BlockPos(x  , y-1, z  ); 
        n[ 3] = new BlockPos(x  , y+1, z  ); 
        n[ 4] = new BlockPos(x  , y  , z-1); 
        n[ 5] = new BlockPos(x  , y  , z+1); 
     
        // Neighbors of neighbors, in the same order,
        // except that duplicates are not included
        n[ 6] = new BlockPos(x-2, y  , z  );  
        n[ 7] = new BlockPos(x-1, y-1, z  );
        n[ 8] = new BlockPos(x-1, y+1, z  );
        n[ 9] = new BlockPos(x-1, y  , z-1);
        n[10] = new BlockPos(x-1, y  , z+1);
        n[11] = new BlockPos(x+2, y  , z  );
        n[12] = new BlockPos(x+1, y-1, z  );
        n[13] = new BlockPos(x+1, y+1, z  );
        n[14] = new BlockPos(x+1, y  , z-1);
        n[15] = new BlockPos(x+1, y  , z+1);
        n[16] = new BlockPos(x  , y-2, z  );
        n[17] = new BlockPos(x  , y-1, z-1);
        n[18] = new BlockPos(x  , y-1, z+1);
        n[19] = new BlockPos(x  , y+2, z  );
        n[20] = new BlockPos(x  , y+1, z-1);
        n[21] = new BlockPos(x  , y+1, z+1);
        n[22] = new BlockPos(x  , y  , z-2);
        n[23] = new BlockPos(x  , y  , z+2);
        return n;
    }
 
    /*
     * We only want redstone wires to update redstone wires that are
     * immediately adjacent.  Some more distant updates can result
     * in cross-talk that (a) wastes time and (b) can make the update
     * order unintuitive.  Therefore (relative to the neighbor order
     * computed by computeAllNeighbors), updates are not scheduled
     * for redstone wire in those non-connecting positions.  On the
     * other hand, updates will always be sent to *other* types of blocks
     * in any of the 24 neighboring positions.
     */
    private static final boolean[] update_redstone = {
        true, true, false, false, true, true,     // 0 to 5
        false, true, true, false, false, false, // 6 to 11
        true, true, false, false, false, true,  // 12 to 17
        true, false, true, true, false, false}; // 18 to 23
 
    // Internal numbering for cardinal directions
    private static final int North = 0;
    private static final int East = 1;
    private static final int South = 2;
    private static final int West = 3;
 
    // Names for debug print statements
    private static final char[] dirname = {'N', 'E', 'S', 'W'};
 
    /* 
     * These lookup tables completely remap neighbor positions into a left-to-right
     * ordering, based on the cardinal direction that is determined to be forward.  
     * See below for more explanation.
     */
    private static final int[] forward_is_north = {2, 3, 16, 19, 0, 4, 1, 5, 7, 8, 17, 20, 12, 13, 18, 21, 6, 9, 22, 14, 11, 10, 23, 15};
    private static final int[] forward_is_east  = {2, 3, 16, 19, 4, 1, 5, 0, 17, 20, 12, 13, 18, 21, 7, 8, 22, 14, 11, 15, 23, 9, 6, 10};
    private static final int[] forward_is_south = {2, 3, 16, 19, 1, 5, 0, 4, 12, 13, 18, 21, 7, 8, 17, 20, 11, 15, 23, 10, 6, 14, 22, 9};
    private static final int[] forward_is_west =  {2, 3, 16, 19, 5, 0, 4, 1, 18, 21, 7, 8, 17, 20, 12, 13, 23, 10, 6, 9, 22, 15, 11, 14};
 
    /* For any orientation, we end up with the update order defined below.  This order is relative to any redstone wire block
     * that is itself having an update computed, and this center position is marked with C.
     * - The update position marked 0 is computed first, and the one marked 23 is last.
     * - Forward is determined by the local direction of information flow into position C from prior updates.
     * - The first updates are scheduled for the four positions below and above C.
     * - Then updates are scheduled for the four horizontal neighbors of C, followed by the positions below and above those neighbors.
     * - Finally, updates are scheduled for the remaining positions with Manhattan distance 2 from C (at the same Y coordinate).
     * - For a given horizontal distance from C, updates are scheduled starting from directly left and stepping clockwise to directly 
     *   right.  The remaining positions behind C are scheduled counterclockwise so as to maintain the left-to-right ordering.
     * - If C is in layer N of the update schedule, then all 24 positions may be scheduled for layer N+1.  For redstone wire, no
     *   updates are scheduled for positions that cannot directly connect.  Additionally, the four positions above and below C
     *   are ALSO scheduled for layer N+2.
     * - This update order was selected after experimenting with a number of alternative schedules, based on its compatibility
     *   with existing redstone designs and behaviors that were considered to be intuitive by various testers.  WARBEN in particular
     *   made some of the most challenging test cases, but the 3-tick clocks (made by RedCMD) were also challenging to fix,
     *   along with the rail-based instant dropper line built by ilmango.  Numerous others made test cases as well, including
     *   NarcolepticFrog, nessie, and Pokechu22.
     *
     * - The forward direction ls determined locally.  So when there are branches in the redstone wire, the left one will get updated
     *   before the right one.  Each branch can have its own relative forward direction, resulting in the left side of a left branch
     *   having priority over the right branch of a left branch, which has priority over the left branch of a right branch, followed
     *   by the right branch of a right branch.  And so forth.  Since redstone power reduces to zero after a path distance of 15,
     *   that imposes a practical limit on the branching.  Note that the branching is not tracked explicitly -- relative forward
     *   directions dictate relative sort order, which maintains the proper global ordering.  This also makes it unnecessary to be 
     *   concerned about branches meeting up with each other.
     *
     *     ^
     *     |
     *  Forward 
     *                           <-- Left   Right -->
     *
     *                                    18
     *                     10          17 5  19          11
     *      2           8  0  12    16 4  C  6  20    9  1  13          3
     *                     14          21 7  23          15
     *    Further                         22                          Further
     *     Down           Down                           Up             Up
     *
     *  Backward
     *     |
     *     V
     */
 
    // This allows the above remapping tables to be looked up by cardial direction index
    private static final int[][] reordering = {forward_is_north, forward_is_east, forward_is_south, forward_is_west};
     
    /*
     * Input:  Array of UpdateNode objects in an order corresponding to the positions 
     *         computed by computeAllNeighbors above.
     * Output: Array of UpdateNode objects oriented using the above remapping tables
     *         corresponding to the identified heading (direction of information flow).
     */
    private static void orientNeighbors(final UpdateNode[] src, final UpdateNode[] dst, final int heading) {
        final int[] re = reordering[heading];
        for (int i=0; i<24; i++) {
            dst[i] = src[re[i]];
        }
    }
 
    /*
     * Structure to keep track of redstone wire blocks and
     * neighbors that will receive updates.
     */
    private static class UpdateNode {
        public enum Type {
            UNKNOWN, REDSTONE, OTHER
        }
         
        BlockState currentState;       // Keep track of redstone wire value
        UpdateNode[] neighbor_nodes;    // References to neighbors (directed graph edges)
        BlockPos self;                  // UpdateNode's own position
        BlockPos parent;                // Which block pos spawned/updated this node
        Type type = Type.UNKNOWN;       // unknown, redstone wire, other type of block
        int layer;                      // Highest layer this node is scheduled in
        boolean visited;                // To keep track of information flow direction, visited restone wire is marked
        int xbias, zbias;               // Remembers directionality of ancestor nodes; helps eliminate directional ambiguities.
    }
     
     
    /*
     * Keep track of all block positions discovered during search and their current states.
     * We want to remember one entry for each position.
     */
    private final Map<BlockPos, UpdateNode> nodeCache = new HashMap<>();
 
 
    /*
     * For a newly created UpdateNode object, determine what type of block it is.
     */
    private void identifyNode(final Level worldIn, final UpdateNode upd1) {
        final BlockPos pos = upd1.self;
        final BlockState oldState = worldIn.getBlockState(pos);
        upd1.currentState = oldState;
 
        // Some neighbors of redstone wire are other kinds of blocks.
        // These need to receive block updates to inform them that
        // redstone wire values have changed.                              
        final Block block = oldState.getBlock();
        if (block != wire) {
            // Mark this block as not redstone wire and therefore
            // requiring updates
            upd1.type = UpdateNode.Type.OTHER;
             
            // Non-redstone blocks may propagate updates, but those updates
            // are not handled by this accelerator.  Therefore, we do not
            // expand this position's neighbors.
            return;
        }
 
        // One job of RedstoneWireBlock.neighborChanged is to convert 
        // redstone wires to items if the block beneath was removed.
        // With this accelerator, RedstoneWireBlock.neighborChanged
        // is only typically called for a single wire block, while
        // others are processed internally by the breadth first search
        // algorithm.  To preserve this game behavior, this check must
        // be replicated here.
        if (!oldState.canSurvive(worldIn, pos)) {
            // Pop off the redstone dust
            Block.dropResources(oldState, worldIn, pos);
            worldIn.removeBlock(pos, false);
             
            // Mark this position as not being redstone wire
            upd1.type = UpdateNode.Type.OTHER;
             
            // Note: Sending updates to air blocks leads to an empty method.
            // Testing shows this to be faster than explicitly avoiding updates to
            // air blocks.
            return;
        }
 
        // If the above conditions fail, then this is a redstone wire block.
        upd1.type = UpdateNode.Type.REDSTONE;
    }
 
 
    /*
     * Given which redstone wire blocks have been visited and not visited
     * around the position currently being updated, compute the cardinal
     * direction that is "forward."
     *
     * rx is the forward direction along the West/East axis
     * rz is the forward direction along the North/South axis
     */
    static private int computeHeading(final int rx, final int rz) {
        // rx and rz can only take on values -1, 0, and 1, so we can
        // compute a code number that allows us to use a single switch
        // to determine the heading.
        final int code = (rx + 1) + 3*(rz + 1);
        switch (code) {
            case 0: {
                // Both rx and rz are -1 (northwest)
                // Randomly choose one to be forward.
                final int j = ThreadLocalRandom.current().nextInt(0, 1);
                return (j==0) ? North : West;
            }
            case 1: {
                // rx=0, rz=-1
                // Definitively North
                return North;
            }
            case 2: {
                // rx=1, rz=-1 (northeast)
                // Choose randomly between north and east
                final int j = ThreadLocalRandom.current().nextInt(0, 1);
                return (j==0) ? North : East;
            }
            case 3: {
                // rx=-1, rz=0
                // Definitively West
                return West;
            }
            case 4: {
                // rx=0, rz=0
                // Heading is completely ambiguous.  Choose
                // randomly among the four cardinal directions.
                return ThreadLocalRandom.current().nextInt(0, 4);
            }
            case 5: {
                // rx=1, rz=0
                // Definitively East
                return East;
            }
            case 6: {
                // rx=-1, rz=1 (southwest)
                // Choose randomly between south and west
                final int j = ThreadLocalRandom.current().nextInt(0, 1);
                return (j==0) ? South : West;
            }
            case 7: {
                // rx=0, rz=1
                // Definitively South
                return South;
            }
            case 8: {
                // rx=1, rz=1 (southeast)
                // Choose randomly between south and east
                final int j = ThreadLocalRandom.current().nextInt(0, 1);
                return (j==0) ? South : East;
            }
        }
 
        // We should never get here
        return ThreadLocalRandom.current().nextInt(0, 4);
    }
 
    // Select whether to use updateSurroundingRedstone from RedstoneWireBlock (old)
    // or this helper class (new)
    private static final boolean old_current_change = false;
 
    /*
     * Process a node whose neighboring redstone wire has experienced value changes.
     */
    private void updateNode(final Level worldIn, final UpdateNode upd1, final int layer) {
        final BlockPos pos = upd1.self;
 
        // Mark this redstone wire as having been visited so that it can be used
        // to calculate direction of information flow.
        upd1.visited = true;
 
        // Look up the last known state.
        // Due to the way other redstone components are updated, we do not
        // have to worry about a state changing behind our backs.  The rare
        // exception is handled by scheduleReentrantNeighborChanged.
        final BlockState oldState = upd1.currentState;
     
        // Ask the wire block to compute its power level from its neighbors.
        // This will also update the wire's power level and return a new
        // state if it has changed.  When a wire power level is changed, 
        // calculateCurrentChanges will immediately update the block state in the world
        // and return the same value here to be cached in the corresponding
        // UpdateNode object.  
        BlockState newState;
        if (old_current_change) {
            newState = ((RedstoneWireBlockInterface)wire).updateLogicPublic(worldIn, pos, oldState);
        } else {
            // Looking up block state is slow.  This accelerator includes a version of
            // calculateCurrentChanges that uses cahed wire values for a
            // significant performance boost.
            newState = this.calculateCurrentChanges(worldIn, upd1);
        }
 
        // Only inform neighors if the state has changed
        if (newState != oldState) {
            // Store the new state
            upd1.currentState = newState;
 
            // Inform neighbors of the change
            propagateChanges(worldIn, upd1, layer);
        }
    }
 
    /*
     * This identifies the neighboring positions of a new UpdateNode object,
     * determines their types, and links those to into the graph.  Then based on
     * what nodes in the redstone wire graph have been visited, the neighbors
     * are reordered left-to-right relative to the direction of information flow.
     */
    private void findNeighbors(final Level worldIn, final UpdateNode upd1) {
        final BlockPos pos = upd1.self;
 
        // Get the list of neighbor coordinates
        final BlockPos[] neighbors = computeAllNeighbors(pos);
 
        // Temporary array of neighbors in cardinal ordering
        final UpdateNode[] neighbor_nodes = new UpdateNode[24];
 
        // Target array of neighbors sorted left-to-right
        upd1.neighbor_nodes = new UpdateNode[24];
 
        for (int i=0; i<24; i++) {
            // Look up each neighbor in the node cache
            final BlockPos pos2 = neighbors[i];
            UpdateNode upd2 = nodeCache.get(pos2);
            if (upd2 == null) {
                // If this is a previously unreached position, create
                // a new update node, add it to the cache, and identify what it is.
                upd2 = new UpdateNode();
                upd2.self = pos2;
                upd2.parent = pos;
                nodeCache.put(pos2, upd2);
                identifyNode(worldIn, upd2);
            }
 
            // For non-redstone blocks, any of the 24 neighboring positions
            // should receive a block update.  However, some block coordinates
            // may contain a redstone wire that does not directly connect to the
            // one being expanded.  To avoid redundant calculations and confusing
            // cross-talk, those neighboring positions are not included.
            if (update_redstone[i] || upd2.type != UpdateNode.Type.REDSTONE) {
                neighbor_nodes[i] = upd2;
            }
        }
 
        // Determine the directions from which the redstone signal may have come from.  This
        // checks for redstone wire at the same Y level and also Y+1 and Y-1, relative to the
        // block being expanded.
        final boolean fromWest = (neighbor_nodes[0].visited || neighbor_nodes[7].visited || neighbor_nodes[8].visited);
        final boolean fromEast = (neighbor_nodes[1].visited || neighbor_nodes[12].visited || neighbor_nodes[13].visited);
        final boolean fromNorth = (neighbor_nodes[4].visited || neighbor_nodes[17].visited || neighbor_nodes[20].visited);
        final boolean fromSouth = (neighbor_nodes[5].visited || neighbor_nodes[18].visited || neighbor_nodes[21].visited);
 
        int cx = 0, cz = 0;
        if (fromWest) cx += 1;
        if (fromEast) cx -= 1;
        if (fromNorth) cz += 1;
        if (fromSouth) cz -= 1;
 
        int heading;
        if (cx==0 && cz==0) {
            // If there is no clear direction, try to inherit the heading from ancestor nodes.
            heading = computeHeading(upd1.xbias, upd1.zbias);
 
            // Propagate that heading to descendent nodes.
            for (int i=0; i<24; i++) {
                final UpdateNode nn = neighbor_nodes[i];
                if (nn != null) {
                    nn.xbias = upd1.xbias;
                    nn.zbias = upd1.zbias;
                }
            }
        } else {
            if (cx != 0 && cz != 0) {
                // If the heading is somewhat ambiguous, try to disambiguate based on 
                // ancestor nodes.
                if (upd1.xbias != 0) cz = 0;
                if (upd1.zbias != 0) cx = 0;
            }
            heading = computeHeading(cx, cz);
             
            // Propagate that heading to descendent nodes.
            for (int i=0; i<24; i++) {
                final UpdateNode nn = neighbor_nodes[i];
                if (nn != null) {
                    nn.xbias = cx;
                    nn.zbias = cz;
                }
            }
        }
 
        // Reorder neighboring UpdateNode objects according to the forward direction
        // determined above.
        orientNeighbors(neighbor_nodes, upd1.neighbor_nodes, heading);
    }
 
    /*
     * For any redstone wire block in layer N, inform neighbors to recompute their states
     * in layers N+1 and N+2;
     */
    private void propagateChanges(final Level worldIn, final UpdateNode upd1, final int layer) {
        if (upd1.neighbor_nodes == null) {
            // If this node has not been expanded yet, find its neigbors
            findNeighbors(worldIn, upd1);
        }
 
        final BlockPos pos = upd1.self;
        final int x = pos.getX();
        final int y = pos.getY();
        final int z = pos.getZ();
 
        // Make sure there are enough layers in the list
        //while (updateLayers.size() <= layer+2) updateLayers.add(new ArrayList<UpdateNode>());
 
        // All neighbors may be scheduled for layer N+1
        final int layer1 = layer + 1;
 
        // If the node being updated (upd1) has already been expanded, then merely
        // schedule updates to its neighbors.
        for (int i=0; i<24; i++) {
            final UpdateNode upd2 = upd1.neighbor_nodes[i];
 
            // This test ensures that an UpdateNode is never scheduled to the same layer
            // more than once.  Also, skip non-connecting redstone wire blocks
            if (upd2 != null && layer1 > upd2.layer) {
                upd2.layer = layer1;
                updateQueue1.add(upd2);
 
                // Keep track of which block updated this neighbor
                upd2.parent = pos;
            }
        }
 
        // Nodes above and below are scheduled ALSO for layer N+2
        final int layer2 = layer + 2;
 
        // Repeat of the loop above, but only for the first four (above and below) neighbors
        // and for layer N+2;
        for (int i=0; i<4; i++) {
            final UpdateNode upd2 = upd1.neighbor_nodes[i];
            if (upd2 != null && layer2 > upd2.layer) {
                upd2.layer = layer2;
                updateQueue2.add(upd2);
                upd2.parent = pos;
            }
        }
    }
 
 
    // The breadth-first search below will send block updates to blocks
    // that are not redstone wire.  If one of those updates results in 
    // a distant redstone wire getting an update, then this.neighborChanged
    // will get called.  This would be a reentrant call, and 
    // it is necessary to properly integrate those updates into the 
    // on-going search through redstone wire.  Thus, we make the layer
    // currently being processed visible at the object level.
     
    // The current layer being processed by the breadth-first search
    private int currentWalkLayer = 0;
 
    private void shiftQueue() {
        final List<UpdateNode> t = updateQueue0;
        t.clear();
        updateQueue0 = updateQueue1;
        updateQueue1 = updateQueue2;
        updateQueue2 = t;
    }
 
    /*
     * Perform a breadth-first (layer by layer) traversal through redstone
     * wire blocks, propagating value changes to neighbors in an order
     * that is a function of distance from the initial call to 
     * this.neighborChanged.
     */
    private void breadthFirstWalk(final Level worldIn) {
        shiftQueue();
        currentWalkLayer = 1;
 
        // Loop over all layers
        while (updateQueue0.size()>0 || updateQueue1.size()>0) {
            // Get the set of blocks in this layer
            final List<UpdateNode> thisLayer = updateQueue0;
            //if (thisLayer.size() < 1) {
                //shiftQueue();
                //currentWalkLayer++;
                //continue;
            //}
 
            // Loop over all blocks in the layer.  Recall that
            // this is a List, preserving the insertion order of
            // left-to-right based on direction of information flow.
            for (UpdateNode upd : thisLayer) {
                if (upd.type == UpdateNode.Type.REDSTONE) {
                    // If the node is is redstone wire, 
                    // schedule updates to neighbors if its value
                    // has changed.  
                    updateNode(worldIn, upd, currentWalkLayer);
                } else {
                    // If this block is not redstone wire, send a block update.
                    // Redstone wire blocks get state updates, but they don't
                    // need block updates.  Only non-redstone neighbors need updates.
                     
                    // The following function is called "neighborChanged" in the latest
                    // deobfuscated names.  World.func_190524_a is called from
                    // World.notifyNeighborsOfStateChange, and 
                    // notifyNeighborsOfStateExcept.  We don't use 
                    // World.notifyNeighborsOfStateChange here, since we are
                    // already keeping track of all of the neighbor positions
                    // that need to be updated.  All on its own, handling neighbors 
                    // this way reduces block updates by 1/3 (24 instead of 36).
//                    worldIn.neighborChanged(upd.self, wire, upd.parent);

                    // [Space Walker]
                    // The neighbor update system got a significant overhaul in 1.19.
                    // Shape and block updates are now added to a stack before being
                    // processed. These changes make it so any neighbor updates emitted
                    // by this accelerator will not be processed until after the entire
                    // wire network has updated. This has a significant impact on the
                    // behavior and introduces Vanilla parity issues.
                    // To circumvent this issue we bypass the neighbor update stack and
                    // call BlockStateBase#neighborChanged directly. This change mostly
                    // restores old behavior, at the cost of bypassing the
                    // max-chained-neighbor-updates server property.
                    worldIn.getBlockState(upd.self).handleNeighborChanged(worldIn, upd.self, wire, upd.parent, false);
                }
            }
 
            // Move on to the next layer
            shiftQueue();
            currentWalkLayer++;
        }
 
        currentWalkLayer = 0;
    }
 
 
    /*
     * Normally, when Minecraft is computing redstone wire power changes, and a wire power level
     * change sends a block update to a neighboring functional component (e.g. piston, repeater, etc.),
     * those updates are queued.  Only once all redstone wire updates are complete will any component
     * action generate any further block updates to redstone wire.  Instant repeater lines, for instance,
     * will process all wire updates for one redstone line, after which the pistons will zero-tick, 
     * after which the next redstone line performs all of its updates.  Thus, each wire is processed in its
     * own discrete wave.
     *
     * However, there are some corner cases where this pattern breaks, with a proof of concept discovered
     * by Rays Works, which works the same in vanilla.  The scenario is as follows:
     * (1) A redstone wire is conducting a signal.
     * (2) Partway through that wave of updates, a neighbor is updated that causes an update to a completely
     *     separate redstone wire.
     * (3) This results in a call to RedstoneWireBlock.neighborChanged for that other wire, in the middle of 
     *     an already on-going propagation through the first wire.
     *
     * The vanilla code, being depth-first, would end up fully processing the second wire before going back
     * to finish processing the first one.  (Although technically, vanilla has no special concept of "being
     * in the middle" of processing updates to a wire.)  For the breadth-first algorithm, we give this
     * situation special handling, where the updates for the second wire are incorporated into the schedule
     * for the first wire, and then the callstack is allowed to unwind back to the on-going search loop in
     * order to continue processing both the first and second wire in the order of distance from the initial
     * trigger.
     */
    private BlockState scheduleReentrantNeighborChanged(final Level worldIn, final BlockPos pos, final BlockState newState, final BlockPos source)
    {
        if (source != null) {
            // If the cause of the redstone wire update is known, we can use that to help determine
            // direction of information flow.
            UpdateNode src = nodeCache.get(source);
            if (src == null) {
                src = new UpdateNode();
                src.self = source;
                src.parent = source;
                src.visited = true;
                identifyNode(worldIn, src);
                nodeCache.put(source, src);
            }
        }
 
        // Find or generate a node for the redstone block position receiving the update
        UpdateNode upd = nodeCache.get(pos);
        if (upd == null) {
            upd = new UpdateNode();
            upd.self = pos;
            upd.parent = pos;
            upd.visited = true;
            identifyNode(worldIn, upd);
            nodeCache.put(pos, upd);
        }
        upd.currentState = newState;
 
        // Receiving this block update may mean something in the world changed.
        // Therefore we clear the cached block info about all neighbors of
        // the position receiving the update and then re-identify what they are.
        if (upd.neighbor_nodes != null) {
            for (int i=0; i<24; i++) {
                final UpdateNode upd2 = upd.neighbor_nodes[i];
                if (upd2 == null) continue;
                upd2.type = UpdateNode.Type.UNKNOWN;
                upd2.currentState = null;
                identifyNode(worldIn, upd2);
            }
        }
 
        // The block at 'pos' is a redstone wire and has been updated already by calling
        // wire.calculateCurrentChanges, so we don't schedule that.  However, we do need
        // to schedule its neighbors.  By passing the current value of 'currentWalkLayer' to
        // propagateChanges, the neighbors of 'pos' are schedule for layers currentWalkLayer+1
        // and currentWalkLayer+2.
        propagateChanges(worldIn, upd, currentWalkLayer);
 
        // Return here.  The call stack will unwind back to the first call to
        // updateSurroundingRedstone, whereupon the new updates just scheduled will
        // be propagated.  This also facilitates elimination of superfluous and
        // redundant block updates.
        return newState;
    }
 
    /*
     * New version of pre-existing updateSurroundingRedstone, which is called from
     * wire.updateSurroundingRedstone, which is called from wire.neighborChanged and a 
     * few other methods in RedstoneWireBlock.  This sets off the breadth-first 
     * walk through all redstone dust connected to the initial position triggered.
     */
    public BlockState updateSurroundingRedstone(final Level worldIn, final BlockPos pos, final BlockState state, final BlockPos source)
    {
        // Check this block's neighbors and see if its power level needs to change
        // Use the calculateCurrentChanges method in RedstoneWireBlock since we have no
        // cached block states at this point.
        final BlockState newState = ((RedstoneWireBlockInterface)wire).updateLogicPublic(worldIn, pos, state);
         
        // If no change, exit
        if (newState == state) {
            return state;
        }
 
        // Check to see if this update was received during an on-going breadth first search
        if (currentWalkLayer>0 || nodeCache.size()>0) {
            // As breadthFirstWalk progresses, it sends block updates to neighbors.  Some of those
            // neighbors may affect the world so as to cause yet another redstone wire block to receive
            // an update.  If that happens, we need to integrate those redstone wire updates into the
            // already on-going graph walk being performed by breadthFirstWalk. 
            return scheduleReentrantNeighborChanged(worldIn, pos, newState, source);
        }
        // If there are no on-going walks through redstone wire, then start a new walk.
 
        // If the source of the block update to the redstone wire at 'pos' is known, we can use
        // that to help determine the direction of information flow.
        if (source != null) {
            final UpdateNode src = new UpdateNode();
            src.self = source;
            src.parent = source;
            src.visited = true;
            nodeCache.put(source, src);
            identifyNode(worldIn, src);
        }
 
        // Create a node representing the block at 'pos', and then propagate updates
        // to its neighbors.  As stated above, the call to wire.calculateCurrentChanges
        // already performs the update to the block at 'pos', so it is not added to the schedule.
        final UpdateNode upd = new UpdateNode();
        upd.self = pos;
        upd.parent = source!=null ? source : pos;
        upd.currentState = newState;
        upd.type = UpdateNode.Type.REDSTONE;
        upd.visited = true;
        nodeCache.put(pos, upd);
        propagateChanges(worldIn, upd, 0);
     
        // Perform the walk over all directly reachable redstone wire blocks, propagating wire value 
        // updates in a breadth first order out from the initial update received for the block at 'pos'.
        breadthFirstWalk(worldIn);
 
        // With the whole search completed, clear the list of all known blocks.
        // We do not want to keep around state information that may be changed by other code.
        // In theory, we could cache the neighbor block positions, but that is a separate
        // optimization.
        nodeCache.clear();
 
        return newState;
    }
 
 
    // For any array of neighbors in an UpdateNode object, these are always
    // the indices of the four immediate neighbors at the same Y coordinate.
    private static final int[] rs_neighbors =    {4, 5, 6, 7};
    private static final int[] rs_neighbors_up = {9, 11, 13, 15};
    private static final int[] rs_neighbors_dn = {8, 10, 12, 14};
 
    /*
     * Updated calculateCurrentChanges that is optimized for speed and uses
     * the UpdateNode's neighbor array to find the redstone states of neighbors
     * that might power it.
     */
    private BlockState calculateCurrentChanges(final Level worldIn, final UpdateNode upd)
    {
        BlockState state = upd.currentState;
        final int i = state.getValue(RedStoneWireBlock.POWER);
        int j = 0;
        j = getMaxCurrentStrength(upd, j);
        int l = 0;
 
        ((RedstoneWireBlockInterface)wire).setWiresGivePower(false);
        // Unfortunately, World.isBlockIndirectlyGettingPowered is complicated,
        // and I'm not ready to try to replicate even more functionality from
        // elsewhere in Minecraft into this accelerator.  So sadly, we must
        // suffer the performance hit of this very expensive call.  If there
        // is consistency to what this call returns, we may be able to cache it.
        final int k = worldIn.getBestNeighborSignal(upd.self);
        ((RedstoneWireBlockInterface)wire).setWiresGivePower(true);
 
        // The variable 'k' holds the maximum redstone power value of any adjacent blocks.
        // If 'k' has the highest level of all neighbors, then the power level of this 
        // redstone wire will be set to 'k'.  If 'k' is already 15, then nothing inside the 
        // following loop can affect the power level of the wire.  Therefore, the loop is 
        // skipped if k is already 15. 
        if (k<15) {
            if (upd.neighbor_nodes == null) {
                // If this node's neighbors are not known, expand the node
                findNeighbors(worldIn, upd);
            }
 
            // These remain constant, so pull them out of the loop.
            // Regardless of which direction is forward, the UpdateNode for the
            // position directly above the node being calculated is always
            // at index 1.
            UpdateNode center_up = upd.neighbor_nodes[1];
            boolean center_up_is_cube = center_up.currentState.isRedstoneConductor(worldIn, center_up.self);  //isSimpleFUllBLock
 
            for (int m=0; m<4; m++) {
                // Get the neighbor array index of each of the four cardinal
                // neighbors.
                int n = rs_neighbors[m];
 
                // Get the max redstone power level of each of the cardinal
                // neighbors
                UpdateNode neighbor = upd.neighbor_nodes[n];
                l = getMaxCurrentStrength(neighbor, l);
 
                // Also check the positions above and below the cardinal
                // neighbors
                boolean neighbor_is_cube = neighbor.currentState.isRedstoneConductor(worldIn, neighbor.self);  //isSimpleFUllBLock
                if (!neighbor_is_cube) {
                    UpdateNode neighbor_down = upd.neighbor_nodes[rs_neighbors_dn[m]];
                    l = getMaxCurrentStrength(neighbor_down, l);
                } else
                if (!center_up_is_cube) {
                    UpdateNode neighbor_up = upd.neighbor_nodes[rs_neighbors_up[m]];
                    l = getMaxCurrentStrength(neighbor_up, l);
                }
            }
        }
 
        // The new code sets this redstonewire block's power level to the highest neighbor
        // minus 1.  This usually results in wire power levels dropping by 2 at a time.
        // This optimization alone has no impact on opdate order, only the number of updates.
        j = l-1;
             
        // If 'l' turns out to be zero, then j will be set to -1, but then since 'k' will
        // always be in the range of 0 to 15, the following if will correct that.
        if (k>j) j=k;
 
        if (i != j) {
            // If the power level has changed from its previous value, compute a new state
            // and set it in the world.  
            // Possible optimization:  Don't commit state changes to the world until they
            // need to be known by some nearby non-redstone-wire block.
            state = state.setValue(RedStoneWireBlock.POWER, j);
            // [gnembon] added state check cause other things in the tick may have popped it up already
            // https://github.com/gnembon/fabric-carpet/issues/117
            if (worldIn.getBlockState(upd.self).getBlock() == Blocks.REDSTONE_WIRE)
                // [Space Walker] suppress shape updates and emit those manually to
                // bypass the new neighbor update stack.
                if (worldIn.setBlock(upd.self, state, Block.UPDATE_KNOWN_SHAPE | Block.UPDATE_CLIENTS))
                    updateNeighborShapes(worldIn, upd.self, state);
        }
 
        return state;
    }

    /*
     * [Space Walker]
     * This method emits shape updates around the given block,
     * bypassing the new neighbor update stack. Diagonal shape
     * updates are omitted, as they are mostly unnecessary.
     * Diagonal shape updates are emitted exclusively to other
     * redstone wires, in order to update their connection properties.
     * Wire connections should never change as a result of power
     * changes, so the only behavioral change will be in scenarios
     * where earlier shape updates have been suppressed to keep a
     * redstone wire in an invalid state.
     */
    public void updateNeighborShapes(Level level, BlockPos pos, BlockState state) {
        // these updates will be added to the stack and processed after the entire network has updated
        state.updateIndirectNeighbourShapes(level, pos, Block.UPDATE_KNOWN_SHAPE | Block.UPDATE_CLIENTS);

        for (Direction dir : Block.UPDATE_SHAPE_ORDER) {
            BlockPos neighborPos = pos.relative(dir);
            BlockState neighborState = level.getBlockState(neighborPos);

            BlockState newState = neighborState.updateShape(dir.getOpposite(), state, level, neighborPos, pos);
            Block.updateOrDestroy(neighborState, newState, level, neighborPos, Block.UPDATE_CLIENTS);
        }
    }

    /*
     * Optimized function to compute a redstone wire's power level based on cached
     * state.
     */
    private static int getMaxCurrentStrength(final UpdateNode upd, final int strength) {   
        if (upd.type != UpdateNode.Type.REDSTONE) return strength;
        final int i = upd.currentState.getValue(RedStoneWireBlock.POWER);
        return Math.max(i, strength);
    }
}