MultiSourceStoppingCriterion.java

package org.heigit.ors.routing.graphhopper.extensions.util;

import com.carrotsearch.hppc.IntHashSet;
import com.carrotsearch.hppc.IntObjectHashMap;
import com.carrotsearch.hppc.IntObjectMap;
import com.carrotsearch.hppc.cursors.IntCursor;
import com.carrotsearch.hppc.cursors.IntObjectCursor;
import org.heigit.ors.routing.graphhopper.extensions.storages.AveragedMultiTreeSPEntry;

import java.util.PriorityQueue;

public class MultiSourceStoppingCriterion {
    private final int treeEntrySize;
    private AveragedMultiTreeSPEntry combinedUnsettled;
    private final IntHashSet targetSet;
    IntObjectMap<AveragedMultiTreeSPEntry> targetMap;
    IntObjectMap<Boolean> allTargetsForSourceFound;


    public MultiSourceStoppingCriterion(IntHashSet targetSet, IntObjectMap<AveragedMultiTreeSPEntry> targetMap, int treeEntrySize) {
        this.targetSet = targetSet;
        this.targetMap = targetMap;
        this.treeEntrySize = treeEntrySize;
        this.allTargetsForSourceFound = new IntObjectHashMap<>(treeEntrySize);
    }

    public boolean isFinished(AveragedMultiTreeSPEntry currEdge, PriorityQueue<AveragedMultiTreeSPEntry> prioQueue) {
        if (combinedUnsettled != null && checkAllTargetsForAllSourcesFound())
            return !queueHasSmallerWeight(combinedUnsettled, prioQueue);

        if (!targetSet.contains(currEdge.getAdjNode()))
            return false;

        setSourceTargetsFound();
        createCombinedUnsettled();

        return false;
    }

    /**
     * Create a single non-real target entry that combines all individual max weights of the unsettled nodes
     * This is done to minimize the iterations over the unsettled targets, which need to be done for correctness
     * until the prioQueue has no more possible better values
     */
    private void createCombinedUnsettled() {
        if (this.combinedUnsettled == null)
            this.combinedUnsettled = initCombinedUnsettled();
        updateCombinedUnsettled();
    }

    private AveragedMultiTreeSPEntry initCombinedUnsettled() {
        AveragedMultiTreeSPEntry combinedUnsettledTarget = new AveragedMultiTreeSPEntry(-1, -1, -1.0, false, null, treeEntrySize);
        //Set all weights to low start weight
        for (int i = 0; i < treeEntrySize; ++i)
            combinedUnsettledTarget.getItem(i).setWeight(-1.0);

        return combinedUnsettledTarget;
    }

    public void updateCombinedUnsettled() {
        if (combinedUnsettled == null)
            return;
        for (IntObjectCursor<AveragedMultiTreeSPEntry> entry : targetMap) {
            for (int source = 0; source < treeEntrySize; ++source) {
                if (allTargetsForSourceFound.getOrDefault(source, false)) {

                    double entryWeight = entry.value.getItem(source).getWeight();

                    if (entryWeight > this.combinedUnsettled.getItem(source).getWeight()) {
                        this.combinedUnsettled.getItem(source).setWeight(entryWeight);
                    }
                }
            }
        }
    }

    /**
     * Check whether the priorityqueue has an entry that could possibly lead to a shorter path for any of the subItems
     *
     * @return
     */
    private boolean queueHasSmallerWeight(AveragedMultiTreeSPEntry target, PriorityQueue<AveragedMultiTreeSPEntry> prioQueue) {
        for (AveragedMultiTreeSPEntry entry : prioQueue) {
            for (int i = 0; i < treeEntrySize; ++i) {
                if (entry.getItem(i).getWeight() < target.getItem(i).getWeight())
                    return true;
            }
        }
        return false;
    }

    private boolean checkAllTargetsForAllSourcesFound() {
        for (int source = 0; source < treeEntrySize; source++) {
            if (combinedUnsettled.getItem(source).getWeight() == -1.0)
                return false;
        }
        return true;
    }

    private void setSourceTargetsFound() {
        for (int source = 0; source < treeEntrySize; source += 1) {
            if (allTargetsForSourceFound.getOrDefault(source, false))
                continue;
            boolean allFound = true;
            for (IntCursor targetId : targetSet) {
                //The target has not been reached yet
                if (!targetMap.containsKey(targetId.value))
                    return;
                AveragedMultiTreeSPEntry target = targetMap.get(targetId.value);
                if (target.getItem(source).getWeight() == Double.POSITIVE_INFINITY) {
                    allFound = false;
                    break;
                }

            }
            allTargetsForSourceFound.put(source, allFound);
        }
    }

    public boolean isEntryLargerThanAllTargets(int source, double weight) {
        return combinedUnsettled != null
                && combinedUnsettled.getItem(source).getWeight() != -1.0
                && weight > combinedUnsettled.getItem(source).getWeight();
    }
}