in core/optaplanner-core-impl/src/main/java/org/optaplanner/core/impl/heuristic/selector/move/generic/list/kopt/KOptDescriptor.java [220:339]
public <Solution_> KOptListMove<Solution_> getKOptListMove(ListVariableDescriptor<Solution_> listVariableDescriptor,
IndexVariableSupply originalIndexVariableSupply,
SingletonInverseVariableSupply inverseVariableSupply) {
if (!isFeasible()) {
// A KOptListMove move with an empty flip move list is not feasible, since if executed, it a no-op
return new KOptListMove<>(listVariableDescriptor, inverseVariableSupply, this, List.of(), 0, new int[] {});
}
MultipleDelegateList<Node_> combinedList = computeCombinedList(listVariableDescriptor, inverseVariableSupply);
IndexVariableSupply indexVariableSupply = node -> combinedList.getIndexOfValue(listVariableDescriptor,
inverseVariableSupply, originalIndexVariableSupply, node);
int entityListSize = combinedList.size();
List<FlipSublistAction> out = new ArrayList<>();
int[] originalToCurrentIndexList = new int[entityListSize];
for (int index = 0; index < entityListSize; index++) {
originalToCurrentIndexList[index] = index;
}
boolean isMoveNotDone = true;
int bestOrientedPairFirstEndpoint = -1;
int bestOrientedPairSecondEndpoint = -1;
// Copy removedEdgeIndexToTourOrder and inverseRemovedEdgeIndexToTourOrder
// to avoid mutating the original arrays (since this function mutate the arrays
// into the sorted signed permutation (+1, +2, ...)
int[] currentRemovedEdgeIndexToTourOrder =
Arrays.copyOf(removedEdgeIndexToTourOrder, removedEdgeIndexToTourOrder.length);
int[] currentInverseRemovedEdgeIndexToTourOrder =
Arrays.copyOf(inverseRemovedEdgeIndexToTourOrder, inverseRemovedEdgeIndexToTourOrder.length);
FindNextReversal: while (isMoveNotDone) {
int maximumOrientedPairCountAfterReversal = -1;
for (int firstEndpoint = 1; firstEndpoint <= 2 * k - 2; firstEndpoint++) {
int firstEndpointCurrentTourIndex = currentRemovedEdgeIndexToTourOrder[firstEndpoint];
int nextEndpointTourIndex = addedEdgeToOtherEndpoint[firstEndpointCurrentTourIndex];
int secondEndpoint = currentInverseRemovedEdgeIndexToTourOrder[nextEndpointTourIndex];
if (secondEndpoint >= firstEndpoint + 2 && (firstEndpoint & 1) == (secondEndpoint & 1)) {
int orientedPairCountAfterReversal = ((firstEndpoint & 1) == 1)
? countOrientedPairsForReversal(currentRemovedEdgeIndexToTourOrder,
currentInverseRemovedEdgeIndexToTourOrder,
firstEndpoint + 1,
secondEndpoint)
: countOrientedPairsForReversal(currentRemovedEdgeIndexToTourOrder,
currentInverseRemovedEdgeIndexToTourOrder,
firstEndpoint,
secondEndpoint - 1);
if (orientedPairCountAfterReversal > maximumOrientedPairCountAfterReversal) {
maximumOrientedPairCountAfterReversal = orientedPairCountAfterReversal;
bestOrientedPairFirstEndpoint = firstEndpoint;
bestOrientedPairSecondEndpoint = secondEndpoint;
}
}
}
if (maximumOrientedPairCountAfterReversal >= 0) {
if ((bestOrientedPairFirstEndpoint & 1) == 1) {
out.add(getListReversalMoveForEdgePair(listVariableDescriptor, inverseVariableSupply, indexVariableSupply,
combinedList, originalToCurrentIndexList,
removedEdges[currentRemovedEdgeIndexToTourOrder[bestOrientedPairFirstEndpoint + 1]],
removedEdges[currentRemovedEdgeIndexToTourOrder[bestOrientedPairFirstEndpoint]],
removedEdges[currentRemovedEdgeIndexToTourOrder[bestOrientedPairSecondEndpoint]],
removedEdges[currentRemovedEdgeIndexToTourOrder[bestOrientedPairSecondEndpoint + 1]]));
reversePermutationPart(currentRemovedEdgeIndexToTourOrder,
currentInverseRemovedEdgeIndexToTourOrder,
bestOrientedPairFirstEndpoint + 1,
bestOrientedPairSecondEndpoint);
} else {
out.add(getListReversalMoveForEdgePair(listVariableDescriptor, inverseVariableSupply, indexVariableSupply,
combinedList, originalToCurrentIndexList,
removedEdges[currentRemovedEdgeIndexToTourOrder[bestOrientedPairFirstEndpoint - 1]],
removedEdges[currentRemovedEdgeIndexToTourOrder[bestOrientedPairFirstEndpoint]],
removedEdges[currentRemovedEdgeIndexToTourOrder[bestOrientedPairSecondEndpoint]],
removedEdges[currentRemovedEdgeIndexToTourOrder[bestOrientedPairSecondEndpoint - 1]]));
reversePermutationPart(currentRemovedEdgeIndexToTourOrder,
currentInverseRemovedEdgeIndexToTourOrder,
bestOrientedPairFirstEndpoint,
bestOrientedPairSecondEndpoint - 1);
}
continue FindNextReversal;
}
// There are no oriented pairs; check for a hurdle
for (int firstEndpoint = 1; firstEndpoint <= 2 * k - 1; firstEndpoint += 2) {
int firstEndpointCurrentTourIndex = currentRemovedEdgeIndexToTourOrder[firstEndpoint];
int nextEndpointTourIndex = addedEdgeToOtherEndpoint[firstEndpointCurrentTourIndex];
int secondEndpoint = currentInverseRemovedEdgeIndexToTourOrder[nextEndpointTourIndex];
if (secondEndpoint >= firstEndpoint + 2) {
out.add(getListReversalMoveForEdgePair(listVariableDescriptor, inverseVariableSupply, indexVariableSupply,
combinedList, originalToCurrentIndexList,
removedEdges[currentRemovedEdgeIndexToTourOrder[firstEndpoint]],
removedEdges[currentRemovedEdgeIndexToTourOrder[firstEndpoint + 1]],
removedEdges[currentRemovedEdgeIndexToTourOrder[secondEndpoint]],
removedEdges[currentRemovedEdgeIndexToTourOrder[secondEndpoint - 1]]));
reversePermutationPart(currentRemovedEdgeIndexToTourOrder,
currentInverseRemovedEdgeIndexToTourOrder,
firstEndpoint + 1, secondEndpoint - 1);
continue FindNextReversal;
}
}
isMoveNotDone = false;
}
int startElementShift = -indexOf(originalToCurrentIndexList, 0);
int[] newEndIndices = new int[combinedList.delegates.length];
int totalOffset = 0;
for (int i = 0; i < newEndIndices.length; i++) {
int listSize = combinedList.delegateSizes[i];
newEndIndices[i] = totalOffset + listSize - 1;
totalOffset += listSize;
}
newEndIndices = IntStream.of(newEndIndices)
.map(index -> indexOf(originalToCurrentIndexList, index))
.sorted()
.toArray();
newEndIndices[newEndIndices.length - 1] = originalToCurrentIndexList.length - 1;
return new KOptListMove<>(listVariableDescriptor, inverseVariableSupply, this, out, startElementShift, newEndIndices);
}