From 0bd7854ae802ad04c1c9e3da4e87dde542152b46 Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Thu, 27 Jun 2024 19:47:46 +0200 Subject: refactor(store): NeighborhoodCalculator API * Use US English spelling consistently * Avoid Eclipse Collections types on API --- .../statecoding/StateCodeCalculatorFactory.java | 5 +- .../store/statecoding/StateEquivalenceChecker.java | 4 +- .../internal/StateCoderBuilderImpl.java | 4 +- .../internal/StateCoderStoreAdapterImpl.java | 6 +- .../AbstractNeighborhoodCalculator.java | 219 ++++++++++++++++++++ .../statecoding/neighborhood/IndividualsArray.java | 27 +++ .../statecoding/neighborhood/IndividualsSet.java | 26 +++ .../neighborhood/NeighborhoodCalculator.java | 55 +++++ .../statecoding/neighborhood/ObjectCodeImpl.java | 88 ++++++++ .../AbstractNeighbourhoodCalculator.java | 223 --------------------- .../neighbourhood/NeighbourhoodCalculator.java | 56 ------ .../statecoding/neighbourhood/ObjectCodeImpl.java | 88 -------- .../StateEquivalenceCheckerImpl.java | 15 +- .../store/statecoding/EquivalenceTest.java | 2 +- 14 files changed, 435 insertions(+), 383 deletions(-) create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/AbstractNeighborhoodCalculator.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/IndividualsArray.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/IndividualsSet.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/NeighborhoodCalculator.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/ObjectCodeImpl.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java (limited to 'subprojects/store/src') diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculatorFactory.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculatorFactory.java index 809205e4..5e2a94b3 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculatorFactory.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculatorFactory.java @@ -5,12 +5,13 @@ */ package tools.refinery.store.statecoding; -import org.eclipse.collections.api.set.primitive.IntSet; import tools.refinery.store.model.Interpretation; import tools.refinery.store.model.Model; +import tools.refinery.store.statecoding.neighborhood.IndividualsSet; import java.util.List; public interface StateCodeCalculatorFactory { - StateCodeCalculator create(Model model, List> interpretations, IntSet individuals); + StateCodeCalculator create(Model model, List> interpretations, + IndividualsSet individuals); } diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateEquivalenceChecker.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateEquivalenceChecker.java index 0f0023ed..ae599dff 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateEquivalenceChecker.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateEquivalenceChecker.java @@ -5,8 +5,8 @@ */ package tools.refinery.store.statecoding; -import org.eclipse.collections.api.set.primitive.IntSet; import tools.refinery.store.model.AnyInterpretation; +import tools.refinery.store.statecoding.neighborhood.IndividualsSet; import java.util.List; @@ -16,6 +16,6 @@ public interface StateEquivalenceChecker { } EquivalenceResult constructMorphism( - IntSet individuals, List interpretations1, ObjectCode code1, + IndividualsSet individuals, List interpretations1, ObjectCode code1, List interpretations2, ObjectCode code2); } diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java index 36d7d4c7..7fec59c4 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java @@ -15,7 +15,7 @@ import tools.refinery.store.statecoding.StateCodeCalculatorFactory; import tools.refinery.store.statecoding.StateCoderBuilder; import tools.refinery.store.statecoding.StateCoderStoreAdapter; import tools.refinery.store.statecoding.StateEquivalenceChecker; -import tools.refinery.store.statecoding.neighbourhood.NeighbourhoodCalculator; +import tools.refinery.store.statecoding.neighborhood.NeighborhoodCalculator; import tools.refinery.store.statecoding.stateequivalence.StateEquivalenceCheckerImpl; import tools.refinery.store.tuple.Tuple1; @@ -27,7 +27,7 @@ public class StateCoderBuilderImpl extends AbstractModelAdapterBuilder excluded = new HashSet<>(); private final MutableIntSet individuals = IntSets.mutable.empty(); - private StateCodeCalculatorFactory calculator = NeighbourhoodCalculator.factory(); + private StateCodeCalculatorFactory calculator = NeighborhoodCalculator.factory(); private StateEquivalenceChecker checker = new StateEquivalenceCheckerImpl(); @Override diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java index 2cb6f3c1..70beedae 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java @@ -14,6 +14,8 @@ import tools.refinery.store.statecoding.StateCodeCalculatorFactory; import tools.refinery.store.statecoding.StateCoderAdapter; import tools.refinery.store.statecoding.StateCoderStoreAdapter; import tools.refinery.store.statecoding.StateEquivalenceChecker; +import tools.refinery.store.statecoding.neighborhood.IndividualsSet; +import tools.refinery.store.statecoding.neighborhood.IndividualsArray; import java.util.Collection; import java.util.Objects; @@ -21,7 +23,7 @@ import java.util.Objects; public class StateCoderStoreAdapterImpl implements StateCoderStoreAdapter { final ModelStore store; final Collection> symbols; - final IntSet individuals; + final IndividualsSet individuals; final StateEquivalenceChecker equivalenceChecker; final StateCodeCalculatorFactory codeCalculatorFactory; @@ -36,7 +38,7 @@ public class StateCoderStoreAdapterImpl implements StateCoderStoreAdapter { this.equivalenceChecker = equivalenceChecker; this.store = store; this.symbols = symbols; - this.individuals = individuals; + this.individuals = new IndividualsArray(individuals.toSortedArray()); } @Override diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/AbstractNeighborhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/AbstractNeighborhoodCalculator.java new file mode 100644 index 00000000..fcc1c72d --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/AbstractNeighborhoodCalculator.java @@ -0,0 +1,219 @@ +/* + * SPDX-FileCopyrightText: 2023-2024 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding.neighborhood; + +import org.eclipse.collections.api.factory.primitive.IntLongMaps; +import org.eclipse.collections.api.map.primitive.MutableIntLongMap; +import tools.refinery.store.map.Cursor; +import tools.refinery.store.model.Model; +import tools.refinery.store.statecoding.ObjectCode; +import tools.refinery.store.statecoding.StateCodeCalculator; +import tools.refinery.store.statecoding.StateCoderResult; +import tools.refinery.store.tuple.Tuple; + +import java.util.*; + +public abstract class AbstractNeighborhoodCalculator implements StateCodeCalculator { + private final Model model; + private final IndividualsSet individuals; + private final int depth; + private List nullImpactValues; + private LinkedHashMap impactValues; + private MutableIntLongMap individualHashValues; + private ObjectCodeImpl previousObjectCode = new ObjectCodeImpl(); + private ObjectCodeImpl nextObjectCode = new ObjectCodeImpl(); + + protected static final long PRIME = 31; + + protected AbstractNeighborhoodCalculator(Model model, IndividualsSet individuals, int depth) { + this.model = model; + this.individuals = individuals; + this.depth = depth; + } + + protected Model getModel() { + return model; + } + + protected abstract List getInterpretations(); + + protected abstract int getArity(T interpretation); + + protected abstract Object getNullValue(T interpretation); + + // We need the wildcard here, because we don't know the value type. + @SuppressWarnings("squid:S1452") + protected abstract Cursor getCursor(T interpretation); + + @Override + public StateCoderResult calculateCodes() { + model.checkCancelled(); + ensureInitialized(); + previousObjectCode.clear(); + nextObjectCode.clear(); + initializeWithIndividuals(previousObjectCode); + + int rounds = 0; + do { + model.checkCancelled(); + constructNextObjectCodes(previousObjectCode, nextObjectCode); + var tempObjectCode = previousObjectCode; + previousObjectCode = nextObjectCode; + nextObjectCode = tempObjectCode; + nextObjectCode.clear(); + rounds++; + } while (rounds <= depth && rounds <= previousObjectCode.getEffectiveSize()); + + long result = calculateLastSum(previousObjectCode); + return new StateCoderResult((int) result, previousObjectCode); + } + + private void ensureInitialized() { + if (impactValues != null) { + return; + } + + nullImpactValues = new ArrayList<>(); + impactValues = new LinkedHashMap<>(); + individualHashValues = IntLongMaps.mutable.empty(); + // Random isn't used for cryptographical purposes but just to assign distinguishable identifiers to symbols. + @SuppressWarnings("squid:S2245") + Random random = new Random(1); + + individuals.stream().forEach(o -> individualHashValues.put(o, random.nextLong())); + + for (var interpretation : getInterpretations()) { + int arity = getArity(interpretation); + if (arity == 0) { + nullImpactValues.add(interpretation); + } else { + long[] impact = new long[arity]; + for (int i = 0; i < arity; i++) { + impact[i] = random.nextInt(); + } + impactValues.put(interpretation, impact); + } + + } + } + + private long calculateLastSum(ObjectCode codes) { + long result = 0; + for (var nullImpactValue : nullImpactValues) { + result = result * PRIME + Objects.hashCode(getNullValue(nullImpactValue)); + } + + for (int i = 0; i < codes.getSize(); i++) { + final long hash = codes.get(i); + result += hash*PRIME; + } + + return result; + } + + private void constructNextObjectCodes(ObjectCodeImpl previous, ObjectCodeImpl next) { + for (var impactValueEntry : this.impactValues.entrySet()) { + model.checkCancelled(); + var interpretation = impactValueEntry.getKey(); + var cursor = getCursor(interpretation); + int arity = getArity(interpretation); + long[] impactValue = impactValueEntry.getValue(); + impactCalculation(previous, next, impactValue, cursor, arity); + } + } + + protected void impactCalculation(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValue, + Cursor cursor, int arity) { + switch (arity) { + case 1 -> { + while (cursor.move()) { + impactCalculation1(previous, next, impactValue, cursor); + } + } + case 2 -> { + while (cursor.move()) { + impactCalculation2(previous, next, impactValue, cursor); + } + } + default -> { + while (cursor.move()) { + impactCalculationN(previous, next, impactValue, cursor); + } + } + } + } + + private void impactCalculation1(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues, + Cursor cursor) { + + Tuple tuple = cursor.getKey(); + int o = tuple.get(0); + Object value = cursor.getValue(); + long tupleHash = getTupleHash1(tuple, value, previous); + addHash(next, o, impactValues[0], tupleHash); + } + + private void impactCalculation2(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues, + Cursor cursor) { + final Tuple tuple = cursor.getKey(); + final int o1 = tuple.get(0); + final int o2 = tuple.get(1); + + Object value = cursor.getValue(); + long tupleHash = getTupleHash2(tuple, value, previous); + + addHash(next, o1, impactValues[0], tupleHash); + addHash(next, o2, impactValues[1], tupleHash); + } + + private void impactCalculationN(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues, + Cursor cursor) { + final Tuple tuple = cursor.getKey(); + + Object value = cursor.getValue(); + long tupleHash = getTupleHashN(tuple, value, previous); + + for (int i = 0; i < tuple.getSize(); i++) { + addHash(next, tuple.get(i), impactValues[i], tupleHash); + } + } + + protected void initializeWithIndividuals(ObjectCodeImpl previous) { + for (var entry : individualHashValues.keyValuesView()) { + previous.set(entry.getOne(), entry.getTwo()); + } + } + + protected long getTupleHash1(Tuple tuple, Object value, ObjectCode objectCodeImpl) { + long result = Objects.hashCode(value); + result = result * PRIME + objectCodeImpl.get(tuple.get(0)); + return result; + } + + protected long getTupleHash2(Tuple tuple, Object value, ObjectCode objectCodeImpl) { + long result = Objects.hashCode(value); + result = result * PRIME + objectCodeImpl.get(tuple.get(0)); + result = result * PRIME + objectCodeImpl.get(tuple.get(1)); + if (tuple.get(0) == tuple.get(1)) { + result += PRIME; + result *= PRIME; + } + return result; + } + + protected long getTupleHashN(Tuple tuple, Object value, ObjectCode objectCodeImpl) { + long result = Objects.hashCode(value); + for (int i = 0; i < tuple.getSize(); i++) { + result = result * PRIME + objectCodeImpl.get(tuple.get(i)); + } + return result; + } + + protected void addHash(ObjectCodeImpl objectCodeImpl, int o, long impact, long tupleHash) { + long x = tupleHash * impact; + objectCodeImpl.set(o, objectCodeImpl.get(o) + x); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/IndividualsArray.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/IndividualsArray.java new file mode 100644 index 00000000..107a01b8 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/IndividualsArray.java @@ -0,0 +1,27 @@ +/* + * SPDX-FileCopyrightText: 2024 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding.neighborhood; + +import java.util.Arrays; +import java.util.stream.IntStream; + +public class IndividualsArray implements IndividualsSet { + private final int[] sortedArray; + + public IndividualsArray(int[] sortedArray) { + this.sortedArray = sortedArray; + } + + @Override + public boolean isIndividual(int nodeId) { + return Arrays.binarySearch(sortedArray, nodeId) >= 0; + } + + @Override + public IntStream stream() { + return Arrays.stream(sortedArray); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/IndividualsSet.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/IndividualsSet.java new file mode 100644 index 00000000..059dad41 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/IndividualsSet.java @@ -0,0 +1,26 @@ +/* + * SPDX-FileCopyrightText: 2024 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding.neighborhood; + +import java.util.stream.IntStream; + +public interface IndividualsSet { + IndividualsSet EMPTY = new IndividualsSet() { + @Override + public boolean isIndividual(int nodeId) { + return false; + } + + @Override + public IntStream stream() { + return IntStream.empty(); + } + }; + + boolean isIndividual(int nodeId); + + IntStream stream(); +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/NeighborhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/NeighborhoodCalculator.java new file mode 100644 index 00000000..83ad133d --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/NeighborhoodCalculator.java @@ -0,0 +1,55 @@ +/* + * SPDX-FileCopyrightText: 2023-2024 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding.neighborhood; + +import tools.refinery.store.map.Cursor; +import tools.refinery.store.model.Interpretation; +import tools.refinery.store.model.Model; +import tools.refinery.store.statecoding.StateCodeCalculatorFactory; +import tools.refinery.store.tuple.Tuple; + +import java.util.List; + +public class NeighborhoodCalculator extends AbstractNeighborhoodCalculator> { + public static final int DEFAULT_DEPTH = 7; + + private final List> interpretations; + + protected NeighborhoodCalculator(Model model, List> interpretations, + IndividualsSet individuals, int depth) { + super(model, individuals, depth); + this.interpretations = List.copyOf(interpretations); + } + + @Override + public List> getInterpretations() { + return interpretations; + } + + @Override + protected int getArity(Interpretation interpretation) { + return interpretation.getSymbol().arity(); + } + + @Override + protected Object getNullValue(Interpretation interpretation) { + return interpretation.get(Tuple.of()); + } + + @Override + protected Cursor getCursor(Interpretation interpretation) { + return interpretation.getAll(); + } + + public static StateCodeCalculatorFactory factory(int depth) { + return (model, interpretations, individuals) -> new NeighborhoodCalculator(model, interpretations, + individuals, depth); + } + + public static StateCodeCalculatorFactory factory() { + return factory(DEFAULT_DEPTH); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/ObjectCodeImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/ObjectCodeImpl.java new file mode 100644 index 00000000..d6ef2e89 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighborhood/ObjectCodeImpl.java @@ -0,0 +1,88 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding.neighborhood; + +import tools.refinery.store.statecoding.ObjectCode; + +import java.util.Arrays; + +public class ObjectCodeImpl implements ObjectCode { + private long[] vector; + private int size; + private int effectiveSize; + + public ObjectCodeImpl() { + vector = new long[10]; + size = 0; + effectiveSize = 0; + } + + public ObjectCodeImpl(int size) { + this.vector = new long[size]; + this.size = size; + effectiveSize = 0; + } + + public ObjectCodeImpl(ObjectCodeImpl copy) { + this.vector = Arrays.copyOf(copy.vector, copy.size); + this.size = copy.size; + effectiveSize = copy.effectiveSize; + } + + public void clear() { + effectiveSize = 0; + for (int i = 0; i < size; i++) { + vector[i] = 0; + } + } + + public void ensureSize(int object) { + if (object >= size) { + size = object + 1; + } + + if (object >= vector.length) { + int newLength = vector.length * 2; + while (object >= newLength) { + newLength *= 2; + } + + long[] newVector = new long[newLength]; + System.arraycopy(vector, 0, newVector, 0, vector.length); + this.vector = newVector; + } + } + + public long get(int object) { + if (object < vector.length) { + return vector[object]; + } else { + return 0; + } + } + + public void set(int object, long value) { + ensureSize(object); + final long valueToPut = value == 0 ? 1 : value; + if (vector[object] == 0) effectiveSize++; + vector[object] = valueToPut; + } + + public int getSize() { + return this.size; + } + + public int getEffectiveSize() { + return this.effectiveSize; + } + + @Override + public String toString() { + return "ObjectCodeImpl{" + + "vector=" + Arrays.toString(Arrays.copyOf(vector, this.size)) + + '}'; + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java deleted file mode 100644 index a4060e74..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java +++ /dev/null @@ -1,223 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2023-2024 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.statecoding.neighbourhood; - -import org.eclipse.collections.api.factory.primitive.IntLongMaps; -import org.eclipse.collections.api.map.primitive.MutableIntLongMap; -import org.eclipse.collections.api.set.primitive.IntSet; -import tools.refinery.store.map.Cursor; -import tools.refinery.store.model.Model; -import tools.refinery.store.statecoding.ObjectCode; -import tools.refinery.store.statecoding.StateCodeCalculator; -import tools.refinery.store.statecoding.StateCoderResult; -import tools.refinery.store.tuple.Tuple; - -import java.util.*; - -public abstract class AbstractNeighbourhoodCalculator implements StateCodeCalculator { - private final Model model; - private final IntSet individuals; - private final int depth; - private List nullImpactValues; - private LinkedHashMap impactValues; - private MutableIntLongMap individualHashValues; - private ObjectCodeImpl previousObjectCode = new ObjectCodeImpl(); - private ObjectCodeImpl nextObjectCode = new ObjectCodeImpl(); - - protected static final long PRIME = 31; - - protected AbstractNeighbourhoodCalculator(Model model, IntSet individuals, int depth) { - this.model = model; - this.individuals = individuals; - this.depth = depth; - } - - protected Model getModel() { - return model; - } - - protected abstract List getInterpretations(); - - protected abstract int getArity(T interpretation); - - protected abstract Object getNullValue(T interpretation); - - // We need the wildcard here, because we don't know the value type. - @SuppressWarnings("squid:S1452") - protected abstract Cursor getCursor(T interpretation); - - @Override - public StateCoderResult calculateCodes() { - model.checkCancelled(); - ensureInitialized(); - previousObjectCode.clear(); - nextObjectCode.clear(); - initializeWithIndividuals(previousObjectCode); - - int rounds = 0; - do { - model.checkCancelled(); - constructNextObjectCodes(previousObjectCode, nextObjectCode); - var tempObjectCode = previousObjectCode; - previousObjectCode = nextObjectCode; - nextObjectCode = tempObjectCode; - nextObjectCode.clear(); - rounds++; - } while (rounds <= depth && rounds <= previousObjectCode.getEffectiveSize()); - - long result = calculateLastSum(previousObjectCode); - return new StateCoderResult((int) result, previousObjectCode); - } - - private void ensureInitialized() { - if (impactValues != null) { - return; - } - - nullImpactValues = new ArrayList<>(); - impactValues = new LinkedHashMap<>(); - individualHashValues = IntLongMaps.mutable.empty(); - // Random isn't used for cryptographical purposes but just to assign distinguishable identifiers to symbols. - @SuppressWarnings("squid:S2245") - Random random = new Random(1); - - var individualsInOrder = individuals.toSortedList(Integer::compare); - for (int i = 0; i < individualsInOrder.size(); i++) { - individualHashValues.put(individualsInOrder.get(i), random.nextLong()); - } - - for (var interpretation : getInterpretations()) { - int arity = getArity(interpretation); - if (arity == 0) { - nullImpactValues.add(interpretation); - } else { - long[] impact = new long[arity]; - for (int i = 0; i < arity; i++) { - impact[i] = random.nextInt(); - } - impactValues.put(interpretation, impact); - } - - } - } - - private long calculateLastSum(ObjectCode codes) { - long result = 0; - for (var nullImpactValue : nullImpactValues) { - result = result * PRIME + Objects.hashCode(getNullValue(nullImpactValue)); - } - - for (int i = 0; i < codes.getSize(); i++) { - final long hash = codes.get(i); - result += hash*PRIME; - } - - return result; - } - - private void constructNextObjectCodes(ObjectCodeImpl previous, ObjectCodeImpl next) { - for (var impactValueEntry : this.impactValues.entrySet()) { - model.checkCancelled(); - var interpretation = impactValueEntry.getKey(); - var cursor = getCursor(interpretation); - int arity = getArity(interpretation); - long[] impactValue = impactValueEntry.getValue(); - impactCalculation(previous, next, impactValue, cursor, arity); - } - } - - protected void impactCalculation(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValue, - Cursor cursor, int arity) { - switch (arity) { - case 1 -> { - while (cursor.move()) { - impactCalculation1(previous, next, impactValue, cursor); - } - } - case 2 -> { - while (cursor.move()) { - impactCalculation2(previous, next, impactValue, cursor); - } - } - default -> { - while (cursor.move()) { - impactCalculationN(previous, next, impactValue, cursor); - } - } - } - } - - private void impactCalculation1(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues, - Cursor cursor) { - - Tuple tuple = cursor.getKey(); - int o = tuple.get(0); - Object value = cursor.getValue(); - long tupleHash = getTupleHash1(tuple, value, previous); - addHash(next, o, impactValues[0], tupleHash); - } - - private void impactCalculation2(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues, - Cursor cursor) { - final Tuple tuple = cursor.getKey(); - final int o1 = tuple.get(0); - final int o2 = tuple.get(1); - - Object value = cursor.getValue(); - long tupleHash = getTupleHash2(tuple, value, previous); - - addHash(next, o1, impactValues[0], tupleHash); - addHash(next, o2, impactValues[1], tupleHash); - } - - private void impactCalculationN(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues, - Cursor cursor) { - final Tuple tuple = cursor.getKey(); - - Object value = cursor.getValue(); - long tupleHash = getTupleHashN(tuple, value, previous); - - for (int i = 0; i < tuple.getSize(); i++) { - addHash(next, tuple.get(i), impactValues[i], tupleHash); - } - } - - protected void initializeWithIndividuals(ObjectCodeImpl previous) { - for (var entry : individualHashValues.keyValuesView()) { - previous.set(entry.getOne(), entry.getTwo()); - } - } - - protected long getTupleHash1(Tuple tuple, Object value, ObjectCode objectCodeImpl) { - long result = Objects.hashCode(value); - result = result * PRIME + objectCodeImpl.get(tuple.get(0)); - return result; - } - - protected long getTupleHash2(Tuple tuple, Object value, ObjectCode objectCodeImpl) { - long result = Objects.hashCode(value); - result = result * PRIME + objectCodeImpl.get(tuple.get(0)); - result = result * PRIME + objectCodeImpl.get(tuple.get(1)); - if (tuple.get(0) == tuple.get(1)) { - result += PRIME; - result *= PRIME; - } - return result; - } - - protected long getTupleHashN(Tuple tuple, Object value, ObjectCode objectCodeImpl) { - long result = Objects.hashCode(value); - for (int i = 0; i < tuple.getSize(); i++) { - result = result * PRIME + objectCodeImpl.get(tuple.get(i)); - } - return result; - } - - protected void addHash(ObjectCodeImpl objectCodeImpl, int o, long impact, long tupleHash) { - long x = tupleHash * impact; - objectCodeImpl.set(o, objectCodeImpl.get(o) + x); - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java deleted file mode 100644 index 5859ccc2..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java +++ /dev/null @@ -1,56 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2023-2024 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.statecoding.neighbourhood; - -import org.eclipse.collections.api.set.primitive.IntSet; -import tools.refinery.store.map.Cursor; -import tools.refinery.store.model.Interpretation; -import tools.refinery.store.model.Model; -import tools.refinery.store.statecoding.StateCodeCalculatorFactory; -import tools.refinery.store.tuple.Tuple; - -import java.util.List; - -public class NeighbourhoodCalculator extends AbstractNeighbourhoodCalculator> { - public static final int DEFAULT_DEPTH = 7; - - private final List> interpretations; - - protected NeighbourhoodCalculator(Model model, List> interpretations, - IntSet individuals, int depth) { - super(model, individuals, depth); - this.interpretations = List.copyOf(interpretations); - } - - @Override - public List> getInterpretations() { - return interpretations; - } - - @Override - protected int getArity(Interpretation interpretation) { - return interpretation.getSymbol().arity(); - } - - @Override - protected Object getNullValue(Interpretation interpretation) { - return interpretation.get(Tuple.of()); - } - - @Override - protected Cursor getCursor(Interpretation interpretation) { - return interpretation.getAll(); - } - - public static StateCodeCalculatorFactory factory(int depth) { - return (model, interpretations, individuals) -> new NeighbourhoodCalculator(model, interpretations, - individuals, depth); - } - - public static StateCodeCalculatorFactory factory() { - return factory(DEFAULT_DEPTH); - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java deleted file mode 100644 index 422e1d73..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java +++ /dev/null @@ -1,88 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.statecoding.neighbourhood; - -import tools.refinery.store.statecoding.ObjectCode; - -import java.util.Arrays; - -public class ObjectCodeImpl implements ObjectCode { - private long[] vector; - private int size; - private int effectiveSize; - - public ObjectCodeImpl() { - vector = new long[10]; - size = 0; - effectiveSize = 0; - } - - public ObjectCodeImpl(int size) { - this.vector = new long[size]; - this.size = size; - effectiveSize = 0; - } - - public ObjectCodeImpl(ObjectCodeImpl copy) { - this.vector = Arrays.copyOf(copy.vector, copy.size); - this.size = copy.size; - effectiveSize = copy.effectiveSize; - } - - public void clear() { - effectiveSize = 0; - for (int i = 0; i < size; i++) { - vector[i] = 0; - } - } - - public void ensureSize(int object) { - if (object >= size) { - size = object + 1; - } - - if (object >= vector.length) { - int newLength = vector.length * 2; - while (object >= newLength) { - newLength *= 2; - } - - long[] newVector = new long[newLength]; - System.arraycopy(vector, 0, newVector, 0, vector.length); - this.vector = newVector; - } - } - - public long get(int object) { - if (object < vector.length) { - return vector[object]; - } else { - return 0; - } - } - - public void set(int object, long value) { - ensureSize(object); - final long valueToPut = value == 0 ? 1 : value; - if (vector[object] == 0) effectiveSize++; - vector[object] = valueToPut; - } - - public int getSize() { - return this.size; - } - - public int getEffectiveSize() { - return this.effectiveSize; - } - - @Override - public String toString() { - return "ObjectCodeImpl{" + - "vector=" + Arrays.toString(Arrays.copyOf(vector, this.size)) + - '}'; - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/StateEquivalenceCheckerImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/StateEquivalenceCheckerImpl.java index 5a62d8a0..54d6efdc 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/StateEquivalenceCheckerImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/StateEquivalenceCheckerImpl.java @@ -11,13 +11,13 @@ import org.eclipse.collections.api.factory.primitive.LongObjectMaps; import org.eclipse.collections.api.map.primitive.IntIntMap; import org.eclipse.collections.api.map.primitive.MutableIntIntMap; import org.eclipse.collections.api.map.primitive.MutableLongObjectMap; -import org.eclipse.collections.api.set.primitive.IntSet; import org.eclipse.collections.api.set.primitive.MutableIntSet; import tools.refinery.store.model.AnyInterpretation; import tools.refinery.store.model.Interpretation; import tools.refinery.store.statecoding.Morphism; import tools.refinery.store.statecoding.ObjectCode; import tools.refinery.store.statecoding.StateEquivalenceChecker; +import tools.refinery.store.statecoding.neighborhood.IndividualsSet; import tools.refinery.store.tuple.Tuple; import java.util.ArrayList; @@ -28,7 +28,7 @@ public class StateEquivalenceCheckerImpl implements StateEquivalenceChecker { public static final int LIMIT = 1000; @Override - public EquivalenceResult constructMorphism(IntSet individuals, + public EquivalenceResult constructMorphism(IndividualsSet individuals, List interpretations1, ObjectCode code1, List interpretations2, @@ -67,10 +67,10 @@ public class StateEquivalenceCheckerImpl implements StateEquivalenceChecker { } } - private MutableLongObjectMap indexByHash(ObjectCode code, IntSet individuals) { + private MutableLongObjectMap indexByHash(ObjectCode code, IndividualsSet individuals) { MutableLongObjectMap result = LongObjectMaps.mutable.empty(); for (int o = 0; o < code.getSize(); o++) { - if (!individuals.contains(o)) { + if (!individuals.isIndividual(o)) { long hash = code.get(o); if (hash != 0) { var equivalenceClass = result.get(hash); @@ -86,8 +86,9 @@ public class StateEquivalenceCheckerImpl implements StateEquivalenceChecker { } private EquivalenceResult constructPermutationNavigation( - IntSet individuals, MutableLongObjectMap map1, MutableLongObjectMap map2, - MutableIntIntMap object2OptionIndex, List> listOfOptions) { + IndividualsSet individuals, MutableLongObjectMap map1, + MutableLongObjectMap map2, MutableIntIntMap object2OptionIndex, + List> listOfOptions) { if (map1.size() != map2.size()) { return EquivalenceResult.DIFFERENT; } @@ -116,7 +117,7 @@ public class StateEquivalenceCheckerImpl implements StateEquivalenceChecker { listOfOptions.add(pairing.permutations()); } - individuals.forEach(o -> listOfOptions.add(o, List.of(IntIntMaps.immutable.of(o, o)))); + individuals.stream().forEach(o -> listOfOptions.add(o, List.of(IntIntMaps.immutable.of(o, o)))); if (allComplete) { return EquivalenceResult.ISOMORPHIC; diff --git a/subprojects/store/src/test/java/tools/refinery/store/statecoding/EquivalenceTest.java b/subprojects/store/src/test/java/tools/refinery/store/statecoding/EquivalenceTest.java index f2d2f7b5..31726133 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/statecoding/EquivalenceTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/statecoding/EquivalenceTest.java @@ -10,7 +10,7 @@ import tools.refinery.store.map.Version; import tools.refinery.store.model.Model; import tools.refinery.store.model.ModelStore; import tools.refinery.store.representation.Symbol; -import tools.refinery.store.statecoding.neighbourhood.ObjectCodeImpl; +import tools.refinery.store.statecoding.neighborhood.ObjectCodeImpl; import tools.refinery.store.tuple.Tuple; import static org.junit.jupiter.api.Assertions.assertEquals; -- cgit v1.2.3-54-g00ecf