State.java

//  Sokoban state space explorer.
//  Discussion: https://dxdy.ru/topic144781.html

import java.util.*;

public class State implements Comparable <State> {

    private static int activeCellsNumber, arraySize;
    private static short [] netrepValues;
    private static int   [] netrepIndices, lastEqual1, lastEqual2;
    private static SortedSet <int []> flagsCollection;
    private static List <State> stateList;

    private short porterCell, move, moveCount, pushCount;
    private int [] cellFlags;
    private State previousState;

    public static void init (CellsAdjacency cellsAdjacency) {

        activeCellsNumber = cellsAdjacency .getActiveCellsNumber ();
        arraySize = (activeCellsNumber >> 5) + (0 == (activeCellsNumber & 31) ? 0 : 1);
        netrepValues  = cellsAdjacency .getValues ();
        netrepIndices = cellsAdjacency .getIndices ();
        lastEqual1 = null;
        lastEqual2 = null;
        flagsCollection = new TreeSet   <> (new ArrayComparator ());
        stateList       = new ArrayList <> ();
    }

    public State (short porterCell, short [] stateCells) {
        int k, cell;

        this .porterCell = porterCell;
        move = -1;
        moveCount = 0;
        pushCount = 0;
        cellFlags = new int [arraySize];

        for (k = 0; stateCells .length > k; ++k) {
            cell = stateCells [k];
            cellFlags [cell >> 5] |= 1 << (cell & 31);
        }
        if (flagsCollection .isEmpty ()) {
            flagsCollection .add (cellFlags);
        } else {
            cellFlags = checkMasksCollection (cellFlags);
        }
        previousState = null;
    }

    public State previousState () {
        return previousState;
    }

    public short move () {
        return move;
    }

    public boolean isSamePlacementAs (State state) {
        return cellFlags == state .cellFlags;
    }

    public static int placementCount () {
        return flagsCollection .size ();
    }

    public short moveCount () {
        return moveCount;
    }

    public short pushCount () {
        return pushCount;
    }

    public short [] stateCells () {
        int k, value, mask;
        short cell;
        ArrayList <Short> cellsList = new ArrayList <> ();
        short [] result;

        cell = 0;
        for (k = 0; arraySize > k; ++k) {
            value = cellFlags [k];
            for (mask = 1; 0 != mask; mask <<= 1, ++cell) {
                if (0 != (value & mask)) {
                    cellsList .add (cell);
                }
            }
        }
        cellsList .add (porterCell);

        value = cellsList .size ();
        result = new short [value];

        for (k = 0; value > k; ++k) {
            result [k] = cellsList .get (k);
        }

        return result;
    }

    private State (short porterCell, short move, short moveCount, short pushCount, int [] cellFlags, State previousState) {
        this .porterCell    = porterCell;
        this .move          = move;
        this .moveCount     = moveCount;
        this .pushCount     = pushCount;
        this .cellFlags     = cellFlags;
        this .previousState = previousState;
    }

    public State [] expandForth () {
        int positionIndex, indexLimit;
        int maskAdress_1, cllFlgMask_1, flagsValue_1;
        int maskAdress_2, cllFlgMask_2, flagsValue_2;
        short move, cell_1, cell_2;
        int [] newCellFlags;

        stateList .clear ();
        positionIndex = netrepIndices [porterCell];
        indexLimit    = netrepIndices [porterCell + 1];

        while (indexLimit > positionIndex) {
            move   = netrepValues [positionIndex];
            ++positionIndex;
            cell_1 = netrepValues [positionIndex];
            if (activeCellsNumber <= cell_1) {
                positionIndex += 3;
                stateList .add (new State (
                        cell_1, move,
                        (short) (moveCount + 1), pushCount, cellFlags, this));
                continue;
            }
            maskAdress_1 = cell_1 >> 5;
            cllFlgMask_1 = 1 << (cell_1 & 31);
            flagsValue_1 = cellFlags [maskAdress_1];
            if (0 == (flagsValue_1 & cllFlgMask_1)) {
                positionIndex += 3;
                stateList .add (new State (
                        cell_1, move,
                        (short) (moveCount + 1), pushCount, cellFlags, this));
                continue;
            }
            ++positionIndex;
            cell_2 = netrepValues [positionIndex];
            positionIndex += 2;
            if (0 > cell_2) {
                continue;
            }
            maskAdress_2 = cell_2 >> 5;
            cllFlgMask_2   = 1 << (cell_2 & 31);
            if (maskAdress_1 == maskAdress_2) {
                if (0 != (flagsValue_1 & cllFlgMask_2)) {
                    continue;
                }
                newCellFlags = Arrays .copyOf (cellFlags, arraySize);
                newCellFlags [maskAdress_1] = flagsValue_1 ^ cllFlgMask_1 ^ cllFlgMask_2;
            } else {
                flagsValue_2 = cellFlags [maskAdress_2];
                if (0 != (flagsValue_2 & cllFlgMask_2)) {
                    continue;
                }
                newCellFlags = Arrays .copyOf (cellFlags, arraySize);
                newCellFlags [maskAdress_1] = flagsValue_1 ^ cllFlgMask_1;
                newCellFlags [maskAdress_2] = flagsValue_2 ^ cllFlgMask_2;
            }
            stateList .add (new State (
                    cell_1, move,
                    (short) (moveCount + 1),
                    (short) (pushCount + 1), checkMasksCollection (newCellFlags), this));
        }

        return stateList .toArray (new State [stateList .size ()]);
    }

    public State [] expandBack () {
        int positionIndex, indexLimit;
        int maskAdress_1, cllFlgMask_1, flagsValue_1;
        int maskAdress_2, cllFlgMask_2, flagsValue_2;
        int maskAdress_3, cllFlgMask_3;
        short move, cell_1, cell_2;
        int [] newCellFlags;

        stateList .clear ();
        positionIndex = netrepIndices [porterCell];
        indexLimit    = netrepIndices [porterCell + 1];

        while (indexLimit > positionIndex) {
            move   = netrepValues [positionIndex];
            ++positionIndex;
            cell_1 = netrepValues [positionIndex];
            maskAdress_1 = -1;
            flagsValue_1 = 0;
            if (activeCellsNumber > cell_1) {
                maskAdress_1 = cell_1 >> 5;
                cllFlgMask_1 = 1 << (cell_1 & 31);
                flagsValue_1 = cellFlags [maskAdress_1];
                if (0 != (flagsValue_1 & cllFlgMask_1)) {
                    positionIndex += 3;
                    continue;
                }
            }
            stateList .add (new State (
                    cell_1, move,
                    (short) (moveCount + 1), pushCount, cellFlags, this));
            positionIndex += 2;
            cell_2 = netrepValues [positionIndex];
            ++positionIndex;
            if (0 > cell_2) {
                continue;
            }
            maskAdress_2 = cell_2 >> 5;
            cllFlgMask_2 = 1 << (cell_2 & 31);
            if (maskAdress_1 == maskAdress_2) {
                flagsValue_2 = flagsValue_1;
            } else {
                flagsValue_2 = cellFlags [maskAdress_2];
            }
            if (0 == (flagsValue_2 & cllFlgMask_2)) {
                continue;
            }
            newCellFlags = Arrays .copyOf (cellFlags, arraySize);
            maskAdress_3 = porterCell >> 5;
            cllFlgMask_3 = 1 << (porterCell & 31);
            if (maskAdress_2 == maskAdress_3) {
                newCellFlags [maskAdress_2] = flagsValue_2 ^ cllFlgMask_2 ^ cllFlgMask_3;
            } else {
                newCellFlags [maskAdress_2] = flagsValue_2 ^ cllFlgMask_2;
                newCellFlags [maskAdress_3] ^=               cllFlgMask_3;
            }
            stateList .add (new State (
                    cell_1, (short) (-move - 1),
                    (short) (moveCount + 1),
                    (short) (pushCount + 1), checkMasksCollection (newCellFlags), this));
        }

        return stateList .toArray (new State [stateList .size ()]);
    }

    @Override
    public int compareTo (State state) {
        int k, value1, value2;

        if (cellFlags != state .cellFlags) {
            for (k = 0; arraySize > k; ++k) {
                value1 =        cellFlags [k];
                value2 = state .cellFlags [k];
                if (value1 > value2) {
                    return 1;
                }
                if (value1 < value2) {
                    return -1;
                }
            }
        }
        if (porterCell > state .porterCell) {
            return 1;
        }
        if (porterCell < state .porterCell) {
            return -1;
        }
        return 0;
    }

    private static int [] checkMasksCollection (int [] newMask) {

        if (flagsCollection .contains (newMask)) {
            if (newMask == lastEqual1) {
                return lastEqual2;
            }
            return lastEqual1;
        }
        flagsCollection .add (newMask);
        return newMask;
    }

    private static class ArrayComparator implements Comparator <int []> {

        @Override
        public int compare (int [] array1, int [] array2) {
            int k, value1, value2;

            for (k = 0; arraySize > k; ++k) {
                value1 = array1 [k];
                value2 = array2 [k];
                if (value1 > value2) {
                    return 1;
                }
                if (value1 < value2) {
                    return -1;
                }
            }
            lastEqual1 = array1;
            lastEqual2 = array2;
            return 0;
        }
    }
}