LevelProcessor.java

package lp;

import it.unimi.dsi.fastutil.longs.Long2ByteFunction;
import it.unimi.dsi.fastutil.longs.Long2ByteOpenHashMap;
import it.unimi.dsi.fastutil.longs.LongLinkedOpenHashSet;

/**
 * Maintains a smooth gradient of some small value (the "level") in a (possibly infinite)
 * graph. The gradient must be increasing away from the manually set states, meaning that
 * manual level updates must only be able to lower the level, or raise it in a (previously
 * lowered) local minimum (see {@link #updateLevel(long, long, int, boolean)} for more
 * details).
 *
 * <h2>Implementation</h2>
 * Objects in the graph are labelled with {@code long} IDs, and the level is restricted
 * to the range {@code 0-252}. Subclasses must implement the {@link #getLevel(long)} and
 * {@link #setLevel(long, int)} methods which get and set the level in the underlying
 * storage, the {@link #propagateLevel(long, int, boolean)} method, which propagates
 * levels to adjacent objects, determining the shape of the graph, and the
 * {@link #getPropagatedLevel(long, long, int)}, which transforms the level on every
 * propagation, determining the shape of the gradient. Additionally, there is a marker
 * ID identified by the {@link #isMarker(long)} method for updates not caused by an
 * adjacent object.
 *
 * <h2>Usage</h2>
 * Level updates can be done through the {@link #updateLevel(long, long, int, boolean)}
 * and {@link #resetLevel(long)} methods. For performance, updates are not applied
 * immediately, but rather when {@link LevelPropagator#applyPendingUpdates} is called.
 *
 * <h2>Example</h2>
 * One possible application would be creating a two-dimensional boolean matrix which
 * keeps track of the Manhattan distance to the nearest set cell, up to some maximum.
 * Here, the graph would be an integer lattice of the same shape as our boolean matrix,
 * the level would be the distance to the nearest set cell, and the propagated level
 * method would simply increase the level by 1.
 * <p>
 * Whenever a cell is set, the corresponding level would be lowered to 0, causing a
 * recursive update of its neighbors. Whenever a cell is unset, the corresponding level
 * would be increased to its maximum, again causing a recursive update of its neighbours.
 */
public abstract class LevelPropagator {
    private final int levelCount;
    private final LongLinkedOpenHashSet[] pendingIdUpdatesByLevel;
    private final Long2ByteFunction pendingUpdates;
    private int minPendingLevel;
    private volatile boolean hasPendingUpdates;

    /**
     * Creates a new level propagator with {@code levelCount} levels.
     *
     * @param levelCount        the number of levels (the levels will be in the range
     *                          {@code 0} to {@code levelCount - 1})
     * @param expectedLevelSize the expected number of objects per level
     * @param expectedTotalSize tthe expected number of objects
     */
    protected LevelPropagator(int levelCount, int expectedLevelSize, int expectedTotalSize) {
        if (levelCount >= 254) {
            throw new IllegalArgumentException("Level count must be < 254.");
        }

        this.levelCount = levelCount;

        pendingIdUpdatesByLevel = new LongLinkedOpenHashSet[levelCount];
        for (int level = 0; level < levelCount; ++level) {
            pendingIdUpdatesByLevel[level] = new LongLinkedOpenHashSet(expectedLevelSize, 0.5f) {
                @Override
                protected void rehash(int newN) {
                    if (newN > expectedLevelSize) {
                        super.rehash(newN);
                    }
                }
            };
        }

        (pendingUpdates = new Long2ByteOpenHashMap(expectedTotalSize, 0.5f) {
            @Override
            protected void rehash(int newN) {
                if (newN > expectedTotalSize) {
                    super.rehash(newN);
                }
            }
        }).defaultReturnValue((byte) -1);

        minPendingLevel = levelCount;
    }

    private int minLevel(int a, int b) {
        int result = a;

        if (result > b) {
            result = b;
        }

        if (result > levelCount - 1) {
            result = levelCount - 1;
        }

        return result;
    }

    private void increaseMinPendingLevel(int maxLevel) {
        int oldMin = minPendingLevel;
        minPendingLevel = maxLevel;

        for (int level = oldMin + 1; level < maxLevel; ++level) {
            if (!pendingIdUpdatesByLevel[level].isEmpty()) {
                minPendingLevel = level;
                break;
            }
        }
    }

    protected void removePendingUpdate(long id) {
        int pendingUpdate = pendingUpdates.get(id) & 0xFF;
        if (pendingUpdate == 255) {
            return;
        }

        int level = getLevel(id);
        int minLevel = minLevel(level, pendingUpdate);
        removePendingUpdate(id, minLevel, levelCount, true);

        hasPendingUpdates = minPendingLevel < levelCount;
    }

    private void removePendingUpdate(long id, int level, int maxLevel, boolean removeFully) {
        if (removeFully) {
            pendingUpdates.remove(id);
        }

        pendingIdUpdatesByLevel[level].remove(id);

        if (pendingIdUpdatesByLevel[level].isEmpty() && minPendingLevel == level) {
            increaseMinPendingLevel(maxLevel);
        }
    }

    private void addPendingUpdate(long id, int level, int targetLevel) {
        pendingUpdates.put(id, (byte) level);
        pendingIdUpdatesByLevel[targetLevel].add(id);
        if (minPendingLevel > targetLevel) {
            minPendingLevel = targetLevel;
        }
    }

    /**
     * Schedules a reset of an object's level to ({@code levelCount - 1}). Will not be
     * applied until {@link #applyPendingUpdates(int)} is called.
     *
     * @param id the ID of the object
     */
    protected void resetLevel(long id) {
        updateLevel(id, id, levelCount - 1, false);
    }

    /**
     * Schedules an update of an object's level. Will not be applied until
     * {@link #applyPendingUpdates(int)} is called.
     *
     * @param sourceId the ID of the update's source, or the marker ID if there is none
     * @param id       the ID of the object to update
     * @param level    the level to update the object to
     * @param decrease {@code true} to decrease a level and propagate it to neighbors,
     *                 {@code false} to increase a previously lowered level by 1, or
     *                 when propagating level increases
     * @see #recalculateLevel(long, long, int)
     */
    protected void updateLevel(long sourceId, long id, int level, boolean decrease) {
        updateLevel(sourceId, id, level, getLevel(id), pendingUpdates.get(id) & 0xFF, decrease);
        hasPendingUpdates = minPendingLevel < levelCount;
    }

    private void updateLevel(long sourceId, long id, int level, int currentLevel, int pendingLevel, boolean decrease) {
        if (isMarker(id)) {
            return;
        }

        level = clamp(level, 0, levelCount - 1);
        currentLevel = clamp(currentLevel, 0, levelCount - 1);

        boolean hasEffect;
        if (pendingLevel == 255) {
            hasEffect = true;
            pendingLevel = currentLevel;
        } else {
            hasEffect = false;
        }

        int newLevel = decrease ?
                Math.min(pendingLevel, level) :
                clamp(recalculateLevel(id, sourceId, level), 0, levelCount - 1);

        int minCurrentPending = minLevel(currentLevel, pendingLevel);
        if (currentLevel != newLevel) {
            int minCurrentNew = minLevel(currentLevel, newLevel);
            if (minCurrentPending != minCurrentNew && !hasEffect) {
                removePendingUpdate(id, minCurrentPending, minCurrentNew, false);
            }

            addPendingUpdate(id, newLevel, minCurrentNew);
        } else if (!hasEffect) {
            removePendingUpdate(id, minCurrentPending, levelCount, true);
        }
    }

    /**
     * Propagates a level from a source object to a target object, using the
     * {@link #getPropagatedLevel(long, long, int)} method to transform the
     * source's level and update the target's level.
     *
     * @param sourceId the object from which the level is being propagated
     * @param targetId the object to which the level is being propagated
     * @param level    the level of the object propagating its level
     * @param decrease see {@link #updateLevel(long, long, int, boolean)}
     */
    protected final void propagateLevel(long sourceId, long targetId, int level, boolean decrease) {
        int pendingLevel = pendingUpdates.get(targetId) & 0xFF;
        int propagatedLevel = clamp(getPropagatedLevel(sourceId, targetId, level), 0, levelCount - 1);

        if (decrease) {
            updateLevel(sourceId, targetId, propagatedLevel, getLevel(targetId), pendingLevel, true);
        } else {
            boolean noPendingLevel;
            int currentLevel;
            if (pendingLevel == 255) {
                noPendingLevel = true;
                currentLevel = clamp(getLevel(targetId), 0, levelCount - 1);
            } else {
                currentLevel = pendingLevel;
                noPendingLevel = false;
            }

            if (propagatedLevel == currentLevel) {
                updateLevel(sourceId, targetId, levelCount - 1, noPendingLevel ? currentLevel : getLevel(targetId), pendingLevel, false);
            }
        }
    }

    /**
     * Returns whether there are updates that are still pending and will not be visible
     * until {@link #applyPendingUpdates(int)} is called.
     *
     * @return whether there are any pending updates
     */
    protected final boolean hasPendingUpdates() {
        return hasPendingUpdates;
    }

    /**
     * Applies pending updates and propagates levels to neighbors repeatedly, until there
     * are no pending updates left or {@code steps} is exceeded.
     *
     * @param steps the maximum number of iterations of the apply-propagate loop to do
     *              (can be {@link Integer#MAX_VALUE})
     * @return the number of unused steps ({@code steps} minus the number of iterations
     * actually done)
     */
    protected final int applyPendingUpdates(int steps) {
        if (minPendingLevel >= levelCount) {
            return steps;
        }

        while (minPendingLevel < levelCount && steps > 0) {
            --steps;

            LongLinkedOpenHashSet updatedIds = pendingIdUpdatesByLevel[minPendingLevel];
            long updatedId = updatedIds.removeFirstLong();
            int currentLevel = clamp(getLevel(updatedId), 0, levelCount - 1);

            if (updatedIds.isEmpty()) {
                increaseMinPendingLevel(levelCount);
            }

            int update = pendingUpdates.remove(updatedId) & 0xFF;
            if (update < currentLevel) {
                setLevel(updatedId, update);
                propagateLevel(updatedId, update, true);
            } else {
                if (update <= currentLevel) {
                    continue;
                }

                addPendingUpdate(updatedId, update, minLevel(levelCount - 1, update));
                setLevel(updatedId, levelCount - 1);
                propagateLevel(updatedId, currentLevel, false);
            }
        }

        hasPendingUpdates = minPendingLevel < levelCount;
        return steps;
    }

    /**
     * Returns whether a given ID is the marker ID, used for manual updates which are
     * not caused by an adjacent object.
     *
     * @param id an ID
     * @return whether the given ID is the marker ID
     */
    protected abstract boolean isMarker(long id);

    /**
     * Recalculates the the maximum possible level for an object based on its neighbors.
     * Called when an object is being updated to a higher level and neighbors need to be
     * recalculated. Implementation should use the {@link #getLevel(long)} method to get
     * the values of the neighbors, and {@link #getPropagatedLevel(long, long, int)} to
     * calculate the level propageted to them by each neighbor.
     *
     * @param id         the ID of the object whose level needs to be recalculated
     * @param excludedId the ID of the neighbor to exclude
     * @param maxLevel   the maximum level the method should return
     * @return the minimum of the levels propageted by each neighbor excluding one, or
     * {@code maxLevel} if lower
     */
    protected abstract int recalculateLevel(long id, long excludedId, int maxLevel);

    /**
     * Updates the neighbors of an object. Implementing methods should call the
     * {@link #propagateLevel(long, long, int, boolean)} method for each neighbor
     * object, with this object as the source, the neighbor as the target, and the
     * same {@code decrease} parameter.
     *
     * @param id       the ID of the object which should propagate its level
     * @param level    the level of the object
     * @param decrease see {@link #updateLevel(long, long, int, boolean)}
     */
    protected abstract void propagateLevel(long id, int level, boolean decrease);

    /**
     * Gets the level of an object from the underlying storage, or returns the initial
     * level if the ID is the marker ID.
     *
     * @param id the ID of an object, or the marker ID
     * @return the level of the object with the specified ID, or the initial
     * level if the ID is the marker ID
     */
    protected abstract int getLevel(long id);

    /**
     * Sets the level of an object in the underlying storage.
     *
     * @param id    an object ID
     * @param level the level of the object with the specified ID
     */
    protected abstract void setLevel(long id, int level);

    /**
     * Determines how a level is transformed when it's propagated from an object with
     * to a neighbor object. The transformed value must always be larger than the input
     * level.
     *
     * @param sourceId the ID of the source object
     * @param targetId the ID of the target object
     * @param level    the level of the source object
     * @return the level that should be propagated to the target object (will be clamped
     * if out of range)
     */
    protected abstract int getPropagatedLevel(long sourceId, long targetId, int level);

    private static int clamp(int value, int min, int max) {
        return Math.max(Math.min(value, max), min);
    }
}

package lp;

import it.unimi.dsi.fastutil.longs.LongArrayList;
import it.unimi.dsi.fastutil.longs.LongList;

import java.util.Arrays;

public class ArrayLevelPropagator extends LevelPropagator {
    private static final int MARKER = -1;
    private final int[][] data;
    private final int levelCount;
    private final int width;
    private final int height;

    public ArrayLevelPropagator(int levelCount, int width, int height) {
        super(levelCount, 10, 10);
        this.levelCount = levelCount;
        data = new int[width][height];
        this.width = width;
        this.height = height;

        for (int[] row : data) {
            Arrays.fill(row, levelCount - 1);
        }
    }

    public int[][] data() {
        applyPendingUpdates(Integer.MAX_VALUE);
        return data.clone();
    }

    public void lower(int x, int y, int value) {
        updateLevel(-1, getId(x, y), value, true);
    }

    public void reset(int x, int y) {
        resetLevel(getId(x, y));
    }

    private long[] getNeighbors(long id) {
        int x = getX(id);
        int y = getY(id);

        LongList neighbors = new LongArrayList(8);
        for (int xo = -1; xo <= 1; xo++) {
            for (int yo = -1; yo <= 1; yo++) {
                if (xo == 0 && yo == 0) {
                    continue;
                }

                int nx = x + xo;
                int ny = y + yo;
                if (nx >= 0 && nx < width && ny >= 0 && ny < height) {
                    neighbors.add(getId(nx, ny));
                }
            }
        }

        return neighbors.toLongArray();
    }

    private int getX(long id) {
        return (int) (id % width);
    }

    private int getY(long id) {
        return (int) (id / width);
    }

    private long getId(int x, int y) {
        return x + y * width;
    }

    @Override
    protected boolean isMarker(long id) {
        return id == MARKER;
    }

    @Override
    protected int recalculateLevel(long id, long excludedId, int maxLevel) {
        int level = maxLevel;

        level = Math.min(level, getPropagatedLevel(-1, id, getLevel(-1)));

        for (long neighbor : getNeighbors(id)) {
            if (neighbor != excludedId) {
                level = Math.min(level, getPropagatedLevel(neighbor, id, getLevel(neighbor)));
            }
        }

        return level;
    }

    @Override
    protected void propagateLevel(long id, int level, boolean decrease) { // update neighbors?
        for (long neighbor : getNeighbors(id)) {
            propagateLevel(id, neighbor, level, decrease);
        }
    }

    @Override
    protected int getLevel(long id) {
        if (id == -1) {
            return levelCount;
        }

        return data[getX(id)][getY(id)];
    }

    @Override
    protected void setLevel(long id, int level) {
        data[getX(id)][getY(id)] = level;
    }

    @Override
    protected int getPropagatedLevel(long sourceId, long targetId, int level) {
        if (sourceId == MARKER) {
            return levelCount;
        }

        return level + 1;
    }
}

class ArrayLevelPropagatorTest {
    public static void main(String[] args) {
        ArrayLevelPropagator lp = new ArrayLevelPropagator(10, 10, 10);
        print(lp.data());

        lp.lower(5, 5, 4);
        print(lp.data());

        lp.lower(2, 2, 5);
        print(lp.data());

        lp.reset(2, 2);
        print(lp.data());

        lp.reset(5, 5);
        print(lp.data());
    }

    private static void print(int[][] data) {
        for (int[] row : data) {
            for (int value : row) {
                System.out.print(value + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}