diff options
author | 2023-10-15 15:09:08 +0200 | |
---|---|---|
committer | 2023-10-15 15:09:08 +0200 | |
commit | 02733629fb2b7e0d4dd8736a2cd83a116bf7a905 (patch) | |
tree | ca2d5dcf76a43299600074cff47ca34e06689bad /subprojects/interpreter-rete/src | |
parent | Merge pull request #44 from kris7t/interpreter-performance-fix (diff) | |
download | refinery-02733629fb2b7e0d4dd8736a2cd83a116bf7a905.tar.gz refinery-02733629fb2b7e0d4dd8736a2cd83a116bf7a905.tar.zst refinery-02733629fb2b7e0d4dd8736a2cd83a116bf7a905.zip |
refactor(interpreter): generify RepresentativeElectionAlgorithm
Let representative election be used in places where IncSCCAlg was used with
generic arguments other than Object.
Diffstat (limited to 'subprojects/interpreter-rete/src')
5 files changed, 42 insertions, 42 deletions
diff --git a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/RepresentativeElectionAlgorithm.java b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/RepresentativeElectionAlgorithm.java index 4d3ad759..ac5e2082 100644 --- a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/RepresentativeElectionAlgorithm.java +++ b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/RepresentativeElectionAlgorithm.java | |||
@@ -14,13 +14,13 @@ import java.util.HashSet; | |||
14 | import java.util.Map; | 14 | import java.util.Map; |
15 | import java.util.Set; | 15 | import java.util.Set; |
16 | 16 | ||
17 | public abstract class RepresentativeElectionAlgorithm implements IGraphObserver<Object> { | 17 | public abstract class RepresentativeElectionAlgorithm<T> implements IGraphObserver<T> { |
18 | protected final Graph<Object> graph; | 18 | protected final Graph<T> graph; |
19 | protected final Map<Object, Object> representatives = new HashMap<>(); | 19 | protected final Map<T, T> representatives = new HashMap<>(); |
20 | protected final Map<Object, Set<Object>> components = new HashMap<>(); | 20 | protected final Map<T, Set<T>> components = new HashMap<>(); |
21 | private RepresentativeObserver observer; | 21 | private RepresentativeObserver<? super T> observer; |
22 | 22 | ||
23 | protected RepresentativeElectionAlgorithm(Graph<Object> graph) { | 23 | protected RepresentativeElectionAlgorithm(Graph<T> graph) { |
24 | this.graph = graph; | 24 | this.graph = graph; |
25 | initializeComponents(); | 25 | initializeComponents(); |
26 | graph.attachObserver(this); | 26 | graph.attachObserver(this); |
@@ -28,7 +28,7 @@ public abstract class RepresentativeElectionAlgorithm implements IGraphObserver< | |||
28 | 28 | ||
29 | protected abstract void initializeComponents(); | 29 | protected abstract void initializeComponents(); |
30 | 30 | ||
31 | protected void initializeSet(Set<Object> set) { | 31 | protected void initializeSet(Set<T> set) { |
32 | var iterator = set.iterator(); | 32 | var iterator = set.iterator(); |
33 | if (!iterator.hasNext()) { | 33 | if (!iterator.hasNext()) { |
34 | // Set is empty. | 34 | // Set is empty. |
@@ -45,13 +45,13 @@ public abstract class RepresentativeElectionAlgorithm implements IGraphObserver< | |||
45 | components.put(representative, set); | 45 | components.put(representative, set); |
46 | } | 46 | } |
47 | 47 | ||
48 | protected void merge(Set<Object> toMerge) { | 48 | protected void merge(Set<T> toMerge) { |
49 | if (toMerge.isEmpty()) { | 49 | if (toMerge.isEmpty()) { |
50 | return; | 50 | return; |
51 | } | 51 | } |
52 | var representativesToMerge = new HashSet<>(); | 52 | var representativesToMerge = new HashSet<T>(); |
53 | Object bestRepresentative = null; | 53 | T bestRepresentative = null; |
54 | Set<Object> bestSet = null; | 54 | Set<T> bestSet = null; |
55 | for (var object : toMerge) { | 55 | for (var object : toMerge) { |
56 | var representative = getRepresentative(object); | 56 | var representative = getRepresentative(object); |
57 | if (representativesToMerge.add(representative)) { | 57 | if (representativesToMerge.add(representative)) { |
@@ -79,7 +79,7 @@ public abstract class RepresentativeElectionAlgorithm implements IGraphObserver< | |||
79 | } | 79 | } |
80 | } | 80 | } |
81 | 81 | ||
82 | protected void merge(Object leftRepresentative, Object rightRepresentative) { | 82 | protected void merge(T leftRepresentative, T rightRepresentative) { |
83 | if (leftRepresentative.equals(rightRepresentative)) { | 83 | if (leftRepresentative.equals(rightRepresentative)) { |
84 | return; | 84 | return; |
85 | } | 85 | } |
@@ -92,8 +92,7 @@ public abstract class RepresentativeElectionAlgorithm implements IGraphObserver< | |||
92 | } | 92 | } |
93 | } | 93 | } |
94 | 94 | ||
95 | private void merge(Object preservedRepresentative, Set<Object> preservedSet, Object removedRepresentative, | 95 | private void merge(T preservedRepresentative, Set<T> preservedSet, T removedRepresentative, Set<T> removedSet) { |
96 | Set<Object> removedSet) { | ||
97 | components.remove(removedRepresentative); | 96 | components.remove(removedRepresentative); |
98 | for (var node : removedSet) { | 97 | for (var node : removedSet) { |
99 | representatives.put(node, preservedRepresentative); | 98 | representatives.put(node, preservedRepresentative); |
@@ -102,7 +101,7 @@ public abstract class RepresentativeElectionAlgorithm implements IGraphObserver< | |||
102 | } | 101 | } |
103 | } | 102 | } |
104 | 103 | ||
105 | protected void assignNewRepresentative(Object oldRepresentative, Set<Object> set) { | 104 | protected void assignNewRepresentative(T oldRepresentative, Set<T> set) { |
106 | var iterator = set.iterator(); | 105 | var iterator = set.iterator(); |
107 | if (!iterator.hasNext()) { | 106 | if (!iterator.hasNext()) { |
108 | return; | 107 | return; |
@@ -119,19 +118,19 @@ public abstract class RepresentativeElectionAlgorithm implements IGraphObserver< | |||
119 | } | 118 | } |
120 | } | 119 | } |
121 | 120 | ||
122 | public void setObserver(RepresentativeObserver observer) { | 121 | public void setObserver(RepresentativeObserver<? super T> observer) { |
123 | this.observer = observer; | 122 | this.observer = observer; |
124 | } | 123 | } |
125 | 124 | ||
126 | public Map<Object, Set<Object>> getComponents() { | 125 | public Map<T, Set<T>> getComponents() { |
127 | return components; | 126 | return components; |
128 | } | 127 | } |
129 | 128 | ||
130 | public Object getRepresentative(Object node) { | 129 | public T getRepresentative(T node) { |
131 | return representatives.get(node); | 130 | return representatives.get(node); |
132 | } | 131 | } |
133 | 132 | ||
134 | public Set<Object> getComponent(Object representative) { | 133 | public Set<T> getComponent(T representative) { |
135 | return components.get(representative); | 134 | return components.get(representative); |
136 | } | 135 | } |
137 | 136 | ||
@@ -140,15 +139,15 @@ public abstract class RepresentativeElectionAlgorithm implements IGraphObserver< | |||
140 | } | 139 | } |
141 | 140 | ||
142 | @Override | 141 | @Override |
143 | public void nodeInserted(Object n) { | 142 | public void nodeInserted(T n) { |
144 | var component = new HashSet<>(1); | 143 | var component = new HashSet<T>(1); |
145 | component.add(n); | 144 | component.add(n); |
146 | initializeSet(component); | 145 | initializeSet(component); |
147 | notifyToObservers(n, n, Direction.INSERT); | 146 | notifyToObservers(n, n, Direction.INSERT); |
148 | } | 147 | } |
149 | 148 | ||
150 | @Override | 149 | @Override |
151 | public void nodeDeleted(Object n) { | 150 | public void nodeDeleted(T n) { |
152 | var representative = representatives.remove(n); | 151 | var representative = representatives.remove(n); |
153 | if (!representative.equals(n)) { | 152 | if (!representative.equals(n)) { |
154 | throw new IllegalStateException("Trying to delete node with dangling edges"); | 153 | throw new IllegalStateException("Trying to delete node with dangling edges"); |
@@ -157,18 +156,19 @@ public abstract class RepresentativeElectionAlgorithm implements IGraphObserver< | |||
157 | notifyToObservers(n, representative, Direction.DELETE); | 156 | notifyToObservers(n, representative, Direction.DELETE); |
158 | } | 157 | } |
159 | 158 | ||
160 | protected void notifyToObservers(Object node, Object oldRepresentative, Object newRepresentative) { | 159 | protected void notifyToObservers(T node, T oldRepresentative, T newRepresentative) { |
161 | notifyToObservers(node, oldRepresentative, Direction.DELETE); | 160 | notifyToObservers(node, oldRepresentative, Direction.DELETE); |
162 | notifyToObservers(node, newRepresentative, Direction.INSERT); | 161 | notifyToObservers(node, newRepresentative, Direction.INSERT); |
163 | } | 162 | } |
164 | 163 | ||
165 | protected void notifyToObservers(Object node, Object representative, Direction direction) { | 164 | protected void notifyToObservers(T node, T representative, Direction direction) { |
166 | if (observer != null) { | 165 | if (observer != null) { |
167 | observer.tupleChanged(node, representative, direction); | 166 | observer.tupleChanged(node, representative, direction); |
168 | } | 167 | } |
169 | } | 168 | } |
170 | 169 | ||
170 | @FunctionalInterface | ||
171 | public interface Factory { | 171 | public interface Factory { |
172 | RepresentativeElectionAlgorithm create(Graph<Object> graph); | 172 | <T> RepresentativeElectionAlgorithm<T> create(Graph<T> graph); |
173 | } | 173 | } |
174 | } | 174 | } |
diff --git a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/RepresentativeObserver.java b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/RepresentativeObserver.java index 7844f1c7..2a4f7102 100644 --- a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/RepresentativeObserver.java +++ b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/RepresentativeObserver.java | |||
@@ -7,6 +7,6 @@ package tools.refinery.interpreter.rete.itc.alg.representative; | |||
7 | 7 | ||
8 | import tools.refinery.interpreter.matchers.util.Direction; | 8 | import tools.refinery.interpreter.matchers.util.Direction; |
9 | 9 | ||
10 | public interface RepresentativeObserver { | 10 | public interface RepresentativeObserver<T> { |
11 | void tupleChanged(Object node, Object representative, Direction direction); | 11 | void tupleChanged(T node, T representative, Direction direction); |
12 | } | 12 | } |
diff --git a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/StronglyConnectedComponentAlgorithm.java b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/StronglyConnectedComponentAlgorithm.java index 44afd73e..d2e524f7 100644 --- a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/StronglyConnectedComponentAlgorithm.java +++ b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/StronglyConnectedComponentAlgorithm.java | |||
@@ -13,8 +13,8 @@ import tools.refinery.interpreter.rete.itc.alg.misc.scc.SCC; | |||
13 | import java.util.Collection; | 13 | import java.util.Collection; |
14 | import java.util.Set; | 14 | import java.util.Set; |
15 | 15 | ||
16 | public class StronglyConnectedComponentAlgorithm extends RepresentativeElectionAlgorithm { | 16 | public class StronglyConnectedComponentAlgorithm<T> extends RepresentativeElectionAlgorithm<T> { |
17 | public StronglyConnectedComponentAlgorithm(Graph<Object> graph) { | 17 | public StronglyConnectedComponentAlgorithm(Graph<T> graph) { |
18 | super(graph); | 18 | super(graph); |
19 | } | 19 | } |
20 | 20 | ||
@@ -27,7 +27,7 @@ public class StronglyConnectedComponentAlgorithm extends RepresentativeElectionA | |||
27 | } | 27 | } |
28 | 28 | ||
29 | @Override | 29 | @Override |
30 | public void edgeInserted(Object source, Object target) { | 30 | public void edgeInserted(T source, T target) { |
31 | var sourceRoot = getRepresentative(source); | 31 | var sourceRoot = getRepresentative(source); |
32 | var targetRoot = getRepresentative(target); | 32 | var targetRoot = getRepresentative(target); |
33 | if (sourceRoot.equals(targetRoot)) { | 33 | if (sourceRoot.equals(targetRoot)) { |
@@ -43,7 +43,7 @@ public class StronglyConnectedComponentAlgorithm extends RepresentativeElectionA | |||
43 | } | 43 | } |
44 | 44 | ||
45 | @Override | 45 | @Override |
46 | public void edgeDeleted(Object source, Object target) { | 46 | public void edgeDeleted(T source, T target) { |
47 | var sourceRoot = getRepresentative(source); | 47 | var sourceRoot = getRepresentative(source); |
48 | var targetRoot = getRepresentative(target); | 48 | var targetRoot = getRepresentative(target); |
49 | if (!sourceRoot.equals(targetRoot)) { | 49 | if (!sourceRoot.equals(targetRoot)) { |
@@ -57,7 +57,7 @@ public class StronglyConnectedComponentAlgorithm extends RepresentativeElectionA | |||
57 | } | 57 | } |
58 | } | 58 | } |
59 | 59 | ||
60 | private void split(Object preservedRepresentative, Collection<? extends Set<Object>> sets) { | 60 | private void split(T preservedRepresentative, Collection<? extends Set<T>> sets) { |
61 | for (var set : sets) { | 61 | for (var set : sets) { |
62 | if (set.contains(preservedRepresentative)) { | 62 | if (set.contains(preservedRepresentative)) { |
63 | components.put(preservedRepresentative, set); | 63 | components.put(preservedRepresentative, set); |
diff --git a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java index 58227c44..6b6c19ed 100644 --- a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java +++ b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java | |||
@@ -11,8 +11,8 @@ import java.util.ArrayDeque; | |||
11 | import java.util.HashSet; | 11 | import java.util.HashSet; |
12 | import java.util.Set; | 12 | import java.util.Set; |
13 | 13 | ||
14 | public class WeaklyConnectedComponentAlgorithm extends RepresentativeElectionAlgorithm { | 14 | public class WeaklyConnectedComponentAlgorithm<T> extends RepresentativeElectionAlgorithm<T> { |
15 | public WeaklyConnectedComponentAlgorithm(Graph<Object> graph) { | 15 | public WeaklyConnectedComponentAlgorithm(Graph<T> graph) { |
16 | super(graph); | 16 | super(graph); |
17 | } | 17 | } |
18 | 18 | ||
@@ -28,14 +28,14 @@ public class WeaklyConnectedComponentAlgorithm extends RepresentativeElectionAlg | |||
28 | } | 28 | } |
29 | 29 | ||
30 | @Override | 30 | @Override |
31 | public void edgeInserted(Object source, Object target) { | 31 | public void edgeInserted(T source, T target) { |
32 | var sourceRoot = getRepresentative(source); | 32 | var sourceRoot = getRepresentative(source); |
33 | var targetRoot = getRepresentative(target); | 33 | var targetRoot = getRepresentative(target); |
34 | merge(sourceRoot, targetRoot); | 34 | merge(sourceRoot, targetRoot); |
35 | } | 35 | } |
36 | 36 | ||
37 | @Override | 37 | @Override |
38 | public void edgeDeleted(Object source, Object target) { | 38 | public void edgeDeleted(T source, T target) { |
39 | var sourceRoot = getRepresentative(source); | 39 | var sourceRoot = getRepresentative(source); |
40 | var targetRoot = getRepresentative(target); | 40 | var targetRoot = getRepresentative(target); |
41 | if (!sourceRoot.equals(targetRoot)) { | 41 | if (!sourceRoot.equals(targetRoot)) { |
@@ -47,7 +47,7 @@ public class WeaklyConnectedComponentAlgorithm extends RepresentativeElectionAlg | |||
47 | } | 47 | } |
48 | } | 48 | } |
49 | 49 | ||
50 | private void split(Object sourceRepresentative, Set<Object> targetReachable) { | 50 | private void split(T sourceRepresentative, Set<T> targetReachable) { |
51 | var sourceComponent = getComponent(sourceRepresentative); | 51 | var sourceComponent = getComponent(sourceRepresentative); |
52 | sourceComponent.removeAll(targetReachable); | 52 | sourceComponent.removeAll(targetReachable); |
53 | if (targetReachable.contains(sourceRepresentative)) { | 53 | if (targetReachable.contains(sourceRepresentative)) { |
@@ -58,10 +58,10 @@ public class WeaklyConnectedComponentAlgorithm extends RepresentativeElectionAlg | |||
58 | } | 58 | } |
59 | } | 59 | } |
60 | 60 | ||
61 | private Set<Object> getReachableNodes(Object source) { | 61 | private Set<T> getReachableNodes(T source) { |
62 | var retSet = new HashSet<>(); | 62 | var retSet = new HashSet<T>(); |
63 | retSet.add(source); | 63 | retSet.add(source); |
64 | var nodeQueue = new ArrayDeque<>(); | 64 | var nodeQueue = new ArrayDeque<T>(); |
65 | nodeQueue.addLast(source); | 65 | nodeQueue.addLast(source); |
66 | 66 | ||
67 | while (!nodeQueue.isEmpty()) { | 67 | while (!nodeQueue.isEmpty()) { |
diff --git a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/single/RepresentativeElectionNode.java b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/single/RepresentativeElectionNode.java index 75aa32ef..eb5ce363 100644 --- a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/single/RepresentativeElectionNode.java +++ b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/single/RepresentativeElectionNode.java | |||
@@ -23,11 +23,11 @@ import tools.refinery.interpreter.matchers.util.timeline.Timeline; | |||
23 | import java.util.Collection; | 23 | import java.util.Collection; |
24 | import java.util.Map; | 24 | import java.util.Map; |
25 | 25 | ||
26 | public class RepresentativeElectionNode extends SingleInputNode implements Clearable, RepresentativeObserver, | 26 | public class RepresentativeElectionNode extends SingleInputNode implements Clearable, RepresentativeObserver<Object>, |
27 | ReinitializedNode { | 27 | ReinitializedNode { |
28 | private final RepresentativeElectionAlgorithm.Factory algorithmFactory; | 28 | private final RepresentativeElectionAlgorithm.Factory algorithmFactory; |
29 | private Graph<Object> graph; | 29 | private Graph<Object> graph; |
30 | private RepresentativeElectionAlgorithm algorithm; | 30 | private RepresentativeElectionAlgorithm<Object> algorithm; |
31 | 31 | ||
32 | public RepresentativeElectionNode(ReteContainer reteContainer, | 32 | public RepresentativeElectionNode(ReteContainer reteContainer, |
33 | RepresentativeElectionAlgorithm.Factory algorithmFactory) { | 33 | RepresentativeElectionAlgorithm.Factory algorithmFactory) { |