State.java

//  Sokoban brute solver.
//  2021, May, B@R5uk
//  Discussion: https://dxdy.ru/topic144781.html

import java.util.*;

public class State implements Comparable <State> {

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

    private short porterCell, move, moveCount, pushCount;
    private int [] cellFlags;
    private State previousState;
    int pathCount;
    private boolean obsolete, expanded;

    public static void init (CellsAdjacency cellsAdjacency) {

        activeCellsNumber = cellsAdjacency .getActiveCellsNumber ();
        arraySize = (activeCellsNumber >> 5) + (0 == (activeCellsNumber & 31) ? 0 : 1);
        cellsAdjValues  = cellsAdjacency .getValues ();
        cellsAdjIndices = 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 = Short .MIN_VALUE;
        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;
        pathCount = 1;
        obsolete = false;
        expanded = false;
    }

    public State getPreviousState () {
        return previousState;
    }

    public short getMove () {
        return move;
    }

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

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

    public short getMoveCount () {
        return moveCount;
    }

    public short getPushCount () {
        return pushCount;
    }

    public short getPorterCell () {
        return porterCell;
    }

    public short [] getStateCells () {
        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);
                }
            }
        }

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

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

        return result;
    }

    public void updatePathCountWith (State state) {
        if (expanded) {
            throw new IllegalArgumentException ("\n\nImpossible error: expanded state was updated.\n");
        }
        pathCount += state .pathCount;
        if (0 > pathCount) {
            pathCount = Integer .MAX_VALUE;
        }
    }

    public int getPathCount () {
        return pathCount;
    }

    public State selectRandomState (State state, Random rng) {
        State result;
        if (expanded || state .expanded) {
            throw new IllegalArgumentException ("\n\nImpossible error: expanded state was updated.\n");
        }
        pathCount += state .pathCount;
        if (0 > pathCount) {
            pathCount = Integer .MAX_VALUE;
            if (0 == rng .nextInt (2)) {
                result = state;
            } else {
                result = this;
            }
        } else {
            if (state .pathCount > rng .nextInt (pathCount)) {
                result = state;
            } else {
                result = this;
            }
        }
        state .pathCount = pathCount;
        return result;
    }

    public void markObsolete () {
        if (expanded) {
            throw new IllegalArgumentException ("\n\nImpossible error: expanded state was updated.\n");
        }
        obsolete = true;
    }

    public boolean isObsolete () {
        return obsolete;
    }

    public boolean isExpanded () {
        return expanded;
    }

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

    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;

        expanded = true;

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

        while (indexLimit > positionIndex) {
            move   = cellsAdjValues [positionIndex];
            ++positionIndex;
            cell_1 = cellsAdjValues [positionIndex];
            if (activeCellsNumber <= cell_1) {
                positionIndex += 3;
                stateList .add (new State (
                        cell_1, move,
                        (short) (moveCount + 1), pushCount, cellFlags, this, pathCount));
                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, pathCount));
                continue;
            }
            ++positionIndex;
            cell_2 = cellsAdjValues [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, (short) (-move - 1),
                    (short) (moveCount + 1),
                    (short) (pushCount + 1), checkMasksCollection (newCellFlags), this, pathCount));
        }

        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;

        expanded = true;

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

        while (indexLimit > positionIndex) {
            move   = cellsAdjValues [positionIndex];
            ++positionIndex;
            cell_1 = cellsAdjValues [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, pathCount));
            positionIndex += 2;
            cell_2 = cellsAdjValues [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, pathCount));
        }

        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;
    }

    public boolean equals (State state) {

        if (porterCell != state .porterCell) {
            return false;
        }
        if (cellFlags != state .cellFlags) {
            for (int k = 0; arraySize > k; ++k) {
                if (cellFlags [k] != state .cellFlags [k]) {
                    return false;
                }
            }
        }
        return true;
    }

    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;
        }
    }

    public static class MovePriorityComparator implements Comparator <State> {

        @Override
        public int compare (State state1, State state2) {
            int value = state1 .moveCount - state2 .moveCount;
            if (0 != value) {
                return value;
            }
            return state1 .pushCount - state2 .pushCount;
        }

    }

    public static class PushPriorityComparator implements Comparator <State> {

        @Override
        public int compare (State state1, State state2) {
            int value = state1 .pushCount - state2 .pushCount;
            if (0 != value) {
                return value;
            }
            return state1 .moveCount - state2 .moveCount;
        }

    }
}