<commit_before>package algorithms.vertexanya;

import grid.GridGraph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import algorithms.PathFindingAlgorithm;
import algorithms.anya.Fraction;
import algorithms.datatypes.Memory;
import algorithms.datatypes.SnapshotItem;
import algorithms.priorityqueue.FastVariableSizeIndirectHeap;
import algorithms.priorityqueue.ReusableIndirectHeap;

public class VertexAnyaMarkingV3 extends PathFindingAlgorithm {
    private static final float EPSILON = 0.0001f;
    
    private final Fraction RIGHT_END;
    private final Fraction LEFT_END;
    
    private ScanInterval[] states;
    private FastVariableSizeIndirectHeap statesPQ;
    private ReusableIndirectHeap vertexPQ;
    private Memory memory;
    
    private int start;
    private int finish;

    public VertexAnyaMarkingV3(GridGraph graph, int sx, int sy, int ex, int ey) {
        super(graph, graph.sizeX, graph.sizeY, sx, sy, ex, ey);
        RIGHT_END = new Fraction(graph.sizeX+1);
        LEFT_END = new Fraction(-1);
    }

    @Override
    public void computePath() {
        int totalSize = (graph.sizeX+1) * (graph.sizeY+1);
        this.initialiseMemory(totalSize, Float.POSITIVE_INFINITY, -1, false);

        start = graph.toOneDimIndex(sx, sy);
        finish = graph.toOneDimIndex(ex, ey);

        vertexPQ = new ReusableIndirectHeap(totalSize);
        statesPQ = new FastVariableSizeIndirectHeap();
        states = new ScanInterval[11];
        
        memory.setDistance(start, 0);
        memory.setParent(start, -1);
        memory.setVisited(start, true);
        if (start == finish) return;
        generateStartSuccessors();

        while (!vertexPQ.isEmpty() || !statesPQ.isEmpty()) {
            if (!vertexPQ.isEmpty() && (statesPQ.isEmpty() || vertexPQ.getMinValue() + EPSILON < statesPQ.getMinValue())) {
                // Pop vertex
                maybeSaveSearchSnapshot();
                int current = vertexPQ.popMinIndex();
                memory.setVisited(current, true);
                
                if (current == finish) {
                    // Done
                    break;
                }
                //System.out.println("Generate " + toTwoDimX(current) + ", " + toTwoDimY(current) + " from " + toTwoDimX(memory.parent(current)) + ", " + toTwoDimY(memory.parent(current)));
                generateSuccessors(current, memory.parent(current));
            } else {
                // Pop state
                maybeSaveSearchSnapshot();
                int currentID = statesPQ.popMinIndex();
                ScanInterval currState = states[currentID];
                //System.out.println("Generate " + currState);

                generateSuccessors(currState);
            }
        }
    }

    private final void addToOpen(int baseIndex, ScanInterval successor) {
        //System.out.println("ADDTOOPEN " + successor);
        // set heuristic and f-value
        float hValue = heuristic(successor);
        float fValue = memory.distance(baseIndex) + hValue;
        
        int handle = statesPQ.insert(fValue);
        if (handle >= states.length) {
            states = Arrays.copyOf(states, states.length*2);
        }
        states[handle] = successor;
    }
    
    private final void tryRelax(int parentIndex, int parX, int parY, int x, int y) {
        //System.out.println("RELAX " + x + ", " + y);
        // return true iff relaxation is done.
        int targetIndex = graph.toOneDimIndex(x, y);
        
        float parentDistance = memory.distance(parentIndex);
        float targetDistance = memory.distance(targetIndex);
        
        float newWeight = parentDistance + graph.distance(parX, parY, x, y);
        if (!memory.visited(targetIndex) && newWeight < targetDistance) {
            memory.setDistance(targetIndex, newWeight);
            if (graph.isOuterCorner(x, y) || (y == ey && x == ex)) {
                memory.setParent(targetIndex, parentIndex); // optional for non-outer-corners
                vertexPQ.decreaseKey(targetIndex, newWeight + graph.distance(x, y, ex, ey));
            }
        }
        return parentDistance - targetDistance;
    }
    
   
    private final void generateSuccessors(ScanInterval currState) {
        exploreState(currState);
    }

    private final void generateStartSuccessors() {
        boolean bottomLeftOfBlocked = graph.bottomLeftOfBlockedTile(sx, sy);
        boolean bottomRightOfBlocked = graph.bottomRightOfBlockedTile(sx, sy);
        boolean topLeftOfBlocked = graph.topLeftOfBlockedTile(sx, sy);
        boolean topRightOfBlocked = graph.topRightOfBlockedTile(sx, sy);
        
        // Generate up
        if (!bottomLeftOfBlocked || !bottomRightOfBlocked) {
            Fraction leftExtent, rightExtent;
            <commit_msg>Fix error in relax method for VertexAnyaMarkingV3<commit_after>package algorithms.vertexanya;

import grid.GridGraph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import algorithms.PathFindingAlgorithm;
import algorithms.anya.Fraction;
import algorithms.datatypes.Memory;
import algorithms.datatypes.SnapshotItem;
import algorithms.priorityqueue.FastVariableSizeIndirectHeap;
import algorithms.priorityqueue.ReusableIndirectHeap;

public class VertexAnyaMarkingV3 extends PathFindingAlgorithm {
    private static final float EPSILON = 0.0001f;
    
    private final Fraction RIGHT_END;
    private final Fraction LEFT_END;
    
    private ScanInterval[] states;
    private FastVariableSizeIndirectHeap statesPQ;
    private ReusableIndirectHeap vertexPQ;
    private Memory memory;
    
    private int start;
    private int finish;

    public VertexAnyaMarkingV3(GridGraph graph, int sx, int sy, int ex, int ey) {
        super(graph, graph.sizeX, graph.sizeY, sx, sy, ex, ey);
        RIGHT_END = new Fraction(graph.sizeX+1);
        LEFT_END = new Fraction(-1);
    }

    @Override
    public void computePath() {
        int totalSize = (graph.sizeX+1) * (graph.sizeY+1);
        this.initialiseMemory(totalSize, Float.POSITIVE_INFINITY, -1, false);

        start = graph.toOneDimIndex(sx, sy);
        finish = graph.toOneDimIndex(ex, ey);

        vertexPQ = new ReusableIndirectHeap(totalSize);
        statesPQ = new FastVariableSizeIndirectHeap();
        states = new ScanInterval[11];
        
        memory.setDistance(start, 0);
        memory.setParent(start, -1);
        memory.setVisited(start, true);
        if (start == finish) return;
        generateStartSuccessors();

        while (!vertexPQ.isEmpty() || !statesPQ.isEmpty()) {
            if (!vertexPQ.isEmpty() && (statesPQ.isEmpty() || vertexPQ.getMinValue() + EPSILON < statesPQ.getMinValue())) {
                // Pop vertex
                maybeSaveSearchSnapshot();
                int current = vertexPQ.popMinIndex();
                memory.setVisited(current, true);
                
                if (current == finish) {
                    // Done
                    break;
                }
                //System.out.println("Generate " + toTwoDimX(current) + ", " + toTwoDimY(current) + " from " + toTwoDimX(memory.parent(current)) + ", " + toTwoDimY(memory.parent(current)));
                generateSuccessors(current, memory.parent(current));
            } else {
                // Pop state
                maybeSaveSearchSnapshot();
                int currentID = statesPQ.popMinIndex();
                ScanInterval currState = states[currentID];
                //System.out.println("Generate " + currState);

                generateSuccessors(currState);
            }
        }
    }

    private final void addToOpen(int baseIndex, ScanInterval successor) {
        //System.out.println("ADDTOOPEN " + successor);
        // set heuristic and f-value
        float hValue = heuristic(successor);
        float fValue = memory.distance(baseIndex) + hValue;
        
        int handle = statesPQ.insert(fValue);
        if (handle >= states.length) {
            states = Arrays.copyOf(states, states.length*2);
        }
        states[handle] = successor;
    }
    
    private final void tryRelax(int parentIndex, int parX, int parY, int x, int y) {
        //System.out.println("RELAX " + x + ", " + y);
        // return true iff relaxation is done.
        int targetIndex = graph.toOneDimIndex(x, y);
        if (memory.visited(targetIndex)) return;
        
        float newWeight = memory.distance(parentIndex) + graph.distance(parX, parY, x, y);
        if (newWeight < memory.distance(targetIndex)) {
            if (graph.isOuterCorner(x, y) || (y == ey && x == ex)) {
                memory.setParent(targetIndex, parentIndex);
                vertexPQ.decreaseKey(targetIndex, newWeight + graph.distance(x, y, ex, ey));
            }
        }
    }
    
   
    private final void generateSuccessors(ScanInterval currState) {
        exploreState(currState);
    }

    private final void generateStartSuccessors() {
        boolean bottomLeftOfBlocked = graph.bottomLeftOfBlockedTile(sx, sy);
        boolean bottomRightOfBlocked = graph.bottomRightOfBlockedTile(sx, sy);
        boolean topLeftOfBlocked = graph.topLeftOfBlockedTile(sx, sy);
        boolean topRightOfBlocked = graph.topRightOfBlockedTile(sx, sy);
        
        // Generate up
        if (!bottomLeftOfBlocked || !bottomRightOfBlocked) {
            Fraction leftExtent, rightExtent;
            
{'fraction_non_alphanumeric': 0.10240963855421686, 'fraction_numerical': 0.003699006552525893, 'mean_word_length': 2.4002874595759973, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5445176', 'n_tokens_mistral': 2738, 'n_tokens_neox': 2610, 'n_words': 584}