diff options
Diffstat (limited to 'subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/operations/extend/ExtendBinaryTransitiveClosure.java')
-rw-r--r-- | subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/operations/extend/ExtendBinaryTransitiveClosure.java | 185 |
1 files changed, 185 insertions, 0 deletions
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/operations/extend/ExtendBinaryTransitiveClosure.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/operations/extend/ExtendBinaryTransitiveClosure.java new file mode 100644 index 00000000..1250e84e --- /dev/null +++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/operations/extend/ExtendBinaryTransitiveClosure.java | |||
@@ -0,0 +1,185 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2013, Zoltan Ujhelyi, Istvan Rath and Daniel Varro | ||
3 | * This program and the accompanying materials are made available under the | ||
4 | * terms of the Eclipse Public License v. 2.0 which is available at | ||
5 | * http://www.eclipse.org/legal/epl-v20.html. | ||
6 | * | ||
7 | * SPDX-License-Identifier: EPL-2.0 | ||
8 | *******************************************************************************/ | ||
9 | package tools.refinery.viatra.runtime.localsearch.operations.extend; | ||
10 | |||
11 | import java.util.Arrays; | ||
12 | import java.util.HashSet; | ||
13 | import java.util.Iterator; | ||
14 | import java.util.LinkedList; | ||
15 | import java.util.List; | ||
16 | import java.util.Queue; | ||
17 | import java.util.Set; | ||
18 | import java.util.function.Function; | ||
19 | |||
20 | import tools.refinery.viatra.runtime.localsearch.MatchingFrame; | ||
21 | import tools.refinery.viatra.runtime.localsearch.matcher.ISearchContext; | ||
22 | import tools.refinery.viatra.runtime.localsearch.operations.IPatternMatcherOperation; | ||
23 | import tools.refinery.viatra.runtime.localsearch.operations.ISearchOperation; | ||
24 | import tools.refinery.viatra.runtime.localsearch.operations.util.CallInformation; | ||
25 | import tools.refinery.viatra.runtime.matchers.backend.IQueryResultProvider; | ||
26 | import tools.refinery.viatra.runtime.matchers.tuple.Tuple; | ||
27 | |||
28 | /** | ||
29 | * Checking for a transitive closure expressed as a local search pattern matcher. The matched pattern must have two | ||
30 | * parameters of the same model type. | ||
31 | * | ||
32 | * @author Zoltan Ujhelyi | ||
33 | * @since 1.7 | ||
34 | * | ||
35 | */ | ||
36 | public abstract class ExtendBinaryTransitiveClosure implements ISearchOperation, IPatternMatcherOperation { | ||
37 | |||
38 | private class Executor extends SingleValueExtendOperationExecutor<Object> { | ||
39 | |||
40 | public Executor(int position) { | ||
41 | super(position); | ||
42 | } | ||
43 | |||
44 | @Override | ||
45 | public Iterator<?> getIterator(MatchingFrame frame, ISearchContext context) { | ||
46 | // Note: second parameter is NOT bound during execution, but the first is | ||
47 | IQueryResultProvider matcher = context.getMatcher(information.getCallWithAdornment()); | ||
48 | |||
49 | Queue<Object> seedsToEvaluate = new LinkedList<>(); | ||
50 | final Object seedValue = frame.get(seedPosition); | ||
51 | seedsToEvaluate.add(seedValue); | ||
52 | Set<Object> seedsEvaluated = new HashSet<>(); | ||
53 | Set<Object> targetsFound = new HashSet<>(); | ||
54 | if (reflexive) { | ||
55 | targetsFound.add(seedValue); | ||
56 | } | ||
57 | |||
58 | while(!seedsToEvaluate.isEmpty()) { | ||
59 | Object currentValue = seedsToEvaluate.poll(); | ||
60 | seedsEvaluated.add(currentValue); | ||
61 | final Object[] mappedFrame = calculateCallFrame(currentValue); | ||
62 | matcher.getAllMatches(mappedFrame).forEach(match -> { | ||
63 | Object foundTarget = getTarget(match); | ||
64 | targetsFound.add(foundTarget); | ||
65 | if (!seedsEvaluated.contains(foundTarget)) { | ||
66 | seedsToEvaluate.add(foundTarget); | ||
67 | } | ||
68 | }); | ||
69 | } | ||
70 | |||
71 | return targetsFound.iterator(); | ||
72 | } | ||
73 | |||
74 | @Override | ||
75 | public ISearchOperation getOperation() { | ||
76 | return ExtendBinaryTransitiveClosure.this; | ||
77 | } | ||
78 | } | ||
79 | |||
80 | /** | ||
81 | * Calculates the transitive closure of a pattern match in a forward direction (first parameter bound, second | ||
82 | * unbound). | ||
83 | * </p> | ||
84 | * <strong>Note</strong>: In case the call is reflexive, it is expected that the bound parameter already matches the universe type of the call. | ||
85 | * | ||
86 | * @since 1.7 | ||
87 | */ | ||
88 | public static class Forward extends ExtendBinaryTransitiveClosure { | ||
89 | |||
90 | private Object[] seedFrame = new Object[2]; | ||
91 | |||
92 | /** | ||
93 | * @since 2.0 | ||
94 | */ | ||
95 | public Forward(CallInformation information, int sourcePosition, int targetPosition, boolean reflexive) { | ||
96 | super(information, sourcePosition, targetPosition, reflexive); | ||
97 | } | ||
98 | |||
99 | protected Object[] calculateCallFrame(Object seed) { | ||
100 | seedFrame[0] = seed; | ||
101 | seedFrame[1] = null; | ||
102 | return seedFrame; | ||
103 | } | ||
104 | |||
105 | protected Object getTarget(Tuple frame) { | ||
106 | return frame.get(1); | ||
107 | } | ||
108 | } | ||
109 | |||
110 | /** | ||
111 | * Calculates the transitive closure of a pattern match in a backward direction (first parameter unbound, second | ||
112 | * bound) | ||
113 | * </p> | ||
114 | * <strong>Note</strong>: In case the call is reflexive, it is expected that the bound parameter already matches the universe type of the call. | ||
115 | * | ||
116 | * @since 2.0 | ||
117 | */ | ||
118 | public static class Backward extends ExtendBinaryTransitiveClosure { | ||
119 | private Object[] seedFrame = new Object[2]; | ||
120 | |||
121 | /** | ||
122 | * @since 2.0 | ||
123 | */ | ||
124 | public Backward(CallInformation information, int sourcePosition, int targetPosition, boolean reflexive) { | ||
125 | super(information, targetPosition, sourcePosition, reflexive); | ||
126 | } | ||
127 | |||
128 | protected Object[] calculateCallFrame(Object seed) { | ||
129 | seedFrame[0] = null; | ||
130 | seedFrame[1] = seed; | ||
131 | return seedFrame; | ||
132 | } | ||
133 | |||
134 | protected Object getTarget(Tuple frame) { | ||
135 | return frame.get(0); | ||
136 | } | ||
137 | } | ||
138 | |||
139 | private final int seedPosition; | ||
140 | private final int targetPosition; | ||
141 | private final CallInformation information; | ||
142 | private final boolean reflexive; | ||
143 | |||
144 | /** | ||
145 | * The source position will be matched in the called pattern to the first parameter; while target to the second. | ||
146 | * @since 2.0 | ||
147 | */ | ||
148 | protected ExtendBinaryTransitiveClosure(CallInformation information, int seedPosition, int targetPosition, boolean reflexive) { | ||
149 | this.information = information; | ||
150 | this.seedPosition = seedPosition; | ||
151 | this.targetPosition = targetPosition; | ||
152 | this.reflexive = reflexive; | ||
153 | } | ||
154 | |||
155 | protected abstract Object[] calculateCallFrame(Object seed); | ||
156 | |||
157 | protected abstract Object getTarget(Tuple frame); | ||
158 | |||
159 | @Override | ||
160 | public ISearchOperationExecutor createExecutor() { | ||
161 | return new Executor(targetPosition); | ||
162 | } | ||
163 | |||
164 | @Override | ||
165 | public String toString() { | ||
166 | return toString(Object::toString); | ||
167 | } | ||
168 | |||
169 | @Override | ||
170 | public String toString(Function<Integer, String> variableMapping) { | ||
171 | String c = information.toString(variableMapping); | ||
172 | int p = c.indexOf('('); | ||
173 | return "extend find " + c.substring(0, p) + "+" + c.substring(p); | ||
174 | } | ||
175 | |||
176 | @Override | ||
177 | public List<Integer> getVariablePositions() { | ||
178 | return Arrays.asList(seedPosition, targetPosition); | ||
179 | } | ||
180 | |||
181 | @Override | ||
182 | public CallInformation getCallInformation() { | ||
183 | return information; | ||
184 | } | ||
185 | } | ||