diff options
Diffstat (limited to 'subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RepresentativeElectionAlgorithm.java')
-rw-r--r-- | subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RepresentativeElectionAlgorithm.java | 137 |
1 files changed, 137 insertions, 0 deletions
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RepresentativeElectionAlgorithm.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RepresentativeElectionAlgorithm.java new file mode 100644 index 00000000..ff5c7158 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RepresentativeElectionAlgorithm.java | |||
@@ -0,0 +1,137 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.query.viatra.internal.rete.network; | ||
7 | |||
8 | import org.eclipse.viatra.query.runtime.base.itc.graphimpl.Graph; | ||
9 | import org.eclipse.viatra.query.runtime.base.itc.igraph.IGraphObserver; | ||
10 | import org.eclipse.viatra.query.runtime.matchers.util.Direction; | ||
11 | |||
12 | import java.util.*; | ||
13 | |||
14 | public abstract class RepresentativeElectionAlgorithm implements IGraphObserver<Object> { | ||
15 | protected final Graph<Object> graph; | ||
16 | protected final Map<Object, Object> representatives = new HashMap<>(); | ||
17 | protected final Map<Object, Set<Object>> components = new HashMap<>(); | ||
18 | private RepresentativeElectionNode observer; | ||
19 | |||
20 | protected RepresentativeElectionAlgorithm(Graph<Object> graph) { | ||
21 | this.graph = graph; | ||
22 | initializeComponents(); | ||
23 | graph.attachObserver(this); | ||
24 | } | ||
25 | |||
26 | protected abstract void initializeComponents(); | ||
27 | |||
28 | protected void initializeSet(Set<Object> set) { | ||
29 | var iterator = set.iterator(); | ||
30 | if (!iterator.hasNext()) { | ||
31 | // Set is empty. | ||
32 | return; | ||
33 | } | ||
34 | var representative = iterator.next(); | ||
35 | for (var node : set) { | ||
36 | var oldRepresentative = representatives.put(node, representative); | ||
37 | if (oldRepresentative != null && !representative.equals(oldRepresentative)) { | ||
38 | throw new IllegalStateException("Node %s is already in a set represented by %s, cannot add it to %s" | ||
39 | .formatted(node, oldRepresentative, set)); | ||
40 | } | ||
41 | } | ||
42 | components.put(representative, set); | ||
43 | } | ||
44 | |||
45 | protected void merge(Object leftRepresentative, Object rightRepresentative) { | ||
46 | if (leftRepresentative.equals(rightRepresentative)) { | ||
47 | return; | ||
48 | } | ||
49 | var leftSet = getComponent(leftRepresentative); | ||
50 | var rightSet = getComponent(rightRepresentative); | ||
51 | if (leftSet.size() < rightSet.size()) { | ||
52 | merge(rightRepresentative, rightSet, leftRepresentative, leftSet); | ||
53 | } else { | ||
54 | merge(leftRepresentative, leftSet, rightRepresentative, rightSet); | ||
55 | } | ||
56 | } | ||
57 | |||
58 | private void merge(Object preservedRepresentative, Set<Object> preservedSet, Object removedRepresentative, | ||
59 | Set<Object> removedSet) { | ||
60 | components.remove(removedRepresentative); | ||
61 | for (var node : removedSet) { | ||
62 | representatives.put(node, preservedRepresentative); | ||
63 | preservedSet.add(node); | ||
64 | notifyToObservers(node, removedRepresentative, preservedRepresentative); | ||
65 | } | ||
66 | } | ||
67 | |||
68 | protected void assignNewRepresentative(Object oldRepresentative, Set<Object> set) { | ||
69 | var iterator = set.iterator(); | ||
70 | if (!iterator.hasNext()) { | ||
71 | return; | ||
72 | } | ||
73 | var newRepresentative = iterator.next(); | ||
74 | components.put(newRepresentative, set); | ||
75 | for (var node : set) { | ||
76 | var oldRepresentativeOfNode = representatives.put(node, newRepresentative); | ||
77 | if (!oldRepresentative.equals(oldRepresentativeOfNode)) { | ||
78 | throw new IllegalArgumentException("Node %s was not represented by %s but by %s" | ||
79 | .formatted(node, oldRepresentative, oldRepresentativeOfNode)); | ||
80 | } | ||
81 | notifyToObservers(node, oldRepresentative, newRepresentative); | ||
82 | } | ||
83 | } | ||
84 | |||
85 | public void setObserver(RepresentativeElectionNode observer) { | ||
86 | this.observer = observer; | ||
87 | } | ||
88 | |||
89 | public Map<Object, Set<Object>> getComponents() { | ||
90 | return components; | ||
91 | } | ||
92 | |||
93 | public Object getRepresentative(Object node) { | ||
94 | return representatives.get(node); | ||
95 | } | ||
96 | |||
97 | public Set<Object> getComponent(Object representative) { | ||
98 | return components.get(representative); | ||
99 | } | ||
100 | |||
101 | public void dispose() { | ||
102 | graph.detachObserver(this); | ||
103 | } | ||
104 | |||
105 | @Override | ||
106 | public void nodeInserted(Object n) { | ||
107 | var component = new HashSet<>(1); | ||
108 | component.add(n); | ||
109 | initializeSet(component); | ||
110 | notifyToObservers(n, n, Direction.INSERT); | ||
111 | } | ||
112 | |||
113 | @Override | ||
114 | public void nodeDeleted(Object n) { | ||
115 | var representative = representatives.remove(n); | ||
116 | if (!representative.equals(n)) { | ||
117 | throw new IllegalStateException("Trying to delete node with dangling edges"); | ||
118 | } | ||
119 | components.remove(representative); | ||
120 | notifyToObservers(n, representative, Direction.DELETE); | ||
121 | } | ||
122 | |||
123 | protected void notifyToObservers(Object node, Object oldRepresentative, Object newRepresentative) { | ||
124 | notifyToObservers(node, oldRepresentative, Direction.DELETE); | ||
125 | notifyToObservers(node, newRepresentative, Direction.INSERT); | ||
126 | } | ||
127 | |||
128 | protected void notifyToObservers(Object node, Object representative, Direction direction) { | ||
129 | if (observer != null) { | ||
130 | observer.tupleChanged(node, representative, direction); | ||
131 | } | ||
132 | } | ||
133 | |||
134 | interface Factory { | ||
135 | RepresentativeElectionAlgorithm create(Graph<Object> graph); | ||
136 | } | ||
137 | } | ||