1 package org.simantics.graph.store;
3 import gnu.trove.list.array.TIntArrayList;
4 import gnu.trove.map.hash.THashMap;
5 import gnu.trove.map.hash.TIntIntHashMap;
6 import gnu.trove.map.hash.TIntObjectHashMap;
7 import gnu.trove.map.hash.TObjectIntHashMap;
8 import gnu.trove.procedure.TIntProcedure;
9 import gnu.trove.procedure.TObjectIntProcedure;
10 import gnu.trove.procedure.TObjectObjectProcedure;
11 import gnu.trove.procedure.TObjectProcedure;
12 import gnu.trove.set.hash.THashSet;
13 import gnu.trove.set.hash.TIntHashSet;
15 import java.util.ArrayList;
16 import java.util.regex.Pattern;
18 import org.simantics.graph.query.Path;
19 import org.simantics.graph.query.PathChild;
20 import org.simantics.graph.query.PathRoot;
21 import org.simantics.graph.representation.External;
22 import org.simantics.graph.representation.Identity;
23 import org.simantics.graph.representation.Internal;
24 import org.simantics.graph.representation.Root;
26 public class IdentityStore implements IStore {
28 private static int[] EMPTY_INT_ARRAY = new int[0];
30 public static class ConsistsOf {
35 public ConsistsOf(int parent, String name, int child) {
36 //System.out.println(parent + "." + name + " = " + child);
43 TObjectIntHashMap<String> roots = new TObjectIntHashMap<String>();
44 TIntObjectHashMap<String> invRoots = new TIntObjectHashMap<String>();
45 TIntObjectHashMap<THashMap<String, ConsistsOf>> parentMap =
46 new TIntObjectHashMap<THashMap<String, ConsistsOf>>();
47 TIntObjectHashMap<ConsistsOf> childMap = new TIntObjectHashMap<ConsistsOf>();
48 TIntHashSet newResources = new TIntHashSet();
49 int resourceCount = 0;
50 TIntIntHashMap unifications = new TIntIntHashMap();
51 TIntHashSet collisions = new TIntHashSet();
53 public int newResource() {
54 return resourceCount++;
57 public boolean markNew(int resource) {
58 return newResources.add(resource);
61 public int[] getNewResources() {
62 return newResources.toArray();
65 public int getResourceCount() {
69 public void setResourceCount(int newCount) {
70 resourceCount = newCount;
73 public void defineRoot(String name, int root) {
74 if(roots.contains(name))
75 unify(root, roots.get(name));
76 roots.put(name, root);
77 invRoots.put(root, name);
80 public void defineChild(int parent, String name, int child) {
81 THashMap<String, ConsistsOf> map = parentMap.get(parent);
83 map = new THashMap<String, ConsistsOf>();
84 parentMap.put(parent, map);
86 ConsistsOf consistsOf = new ConsistsOf(parent, name, child);
87 ConsistsOf oldC = map.put(name, consistsOf);
89 unify(child, oldC.child);
90 childMap.put(child, consistsOf);
93 public boolean hasChild(int parent, String name) {
94 THashMap<String, ConsistsOf> map = parentMap.get(parent);
98 return map.contains(name);
101 public int getChild(int parent, String name) {
102 THashMap<String, ConsistsOf> map = parentMap.get(parent);
104 map = new THashMap<String, ConsistsOf>();
105 parentMap.put(parent, map);
107 else if(map.contains(name))
108 return map.get(name).child;
109 int child = newResource();
110 ConsistsOf consistsOf = new ConsistsOf(parent, name, child);
111 map.put(name, consistsOf);
112 childMap.put(child, consistsOf);
116 public int getChildIfExists(int parent, String name) {
117 THashMap<String, ConsistsOf> map = parentMap.get(parent);
118 if(map != null && map.contains(name))
119 return map.get(name).child;
123 public int getRoot(String uri) {
124 if(roots.contains(uri))
125 return roots.get(uri);
127 int root = newResource();
128 roots.put(uri, root);
129 invRoots.put(root, uri);
134 public int getRootIfExists(String uri) {
135 if(roots.contains(uri))
136 return roots.get(uri);
140 public int[] getChildren(int id) {
141 THashMap<String,ConsistsOf> map = parentMap.get(id);
143 return EMPTY_INT_ARRAY;
144 final int[] result = new int[map.size()];
145 map.forEachValue(new TObjectProcedure<ConsistsOf>() {
148 public boolean execute(ConsistsOf object) {
149 result[i++] = object.child;
156 public THashMap<String, ConsistsOf> getChildMap(int parent) {
157 return parentMap.get(parent);
160 private void collectIdentities(final int parent, final ArrayList<Identity> identities) {
161 THashMap<String, ConsistsOf> map = parentMap.get(parent);
163 map.forEachEntry(new TObjectObjectProcedure<String, ConsistsOf>() {
166 public boolean execute(String a, ConsistsOf b) {
167 if(newResources.contains(b.child))
168 identities.add(new Identity(b.child, new Internal(parent, a)));
170 identities.add(new Identity(b.child, new External(parent, a)));
171 collectIdentities(b.child, identities);
178 private void collectIdentities(final ArrayList<Identity> identities) {
179 roots.forEachEntry(new TObjectIntProcedure<String>() {
181 public boolean execute(String a, int b) {
182 identities.add(new Identity(b, new Root(a, "")));
183 collectIdentities(b, identities);
190 public void map(final TIntIntHashMap map) {
191 collisions = IndexMappingUtils.map(map, collisions);
192 newResources = IndexMappingUtils.map(map, newResources);
193 IndexMappingUtils.map(map, roots);
194 invRoots = IndexMappingUtils.map(map, invRoots, collisions);
196 final ArrayList<ConsistsOf> consistsOfs = new ArrayList<ConsistsOf>(childMap.size());
197 childMap.forEachValue(new TObjectProcedure<IdentityStore.ConsistsOf>() {
199 public boolean execute(ConsistsOf c) {
200 if(map.contains(c.parent))
201 c.parent = map.get(c.parent);
202 if(map.contains(c.child))
203 c.child = map.get(c.child);
211 assert(unifications.isEmpty());
213 for(ConsistsOf c : consistsOfs) {
214 THashMap<String, ConsistsOf> m = parentMap.get(c.parent);
216 m = new THashMap<String, ConsistsOf>();
217 parentMap.put(c.parent, m);
219 ConsistsOf oldC = m.put(c.name, c);
220 ConsistsOf childC = childMap.put(c.child, c);
221 if(childC != null && (childC.parent != c.parent || !childC.name.equals(c.name)))
222 collisions.add(c.child);
225 unify(oldC.child, c.child);
229 public int pathToId(Path path) {
230 if(path instanceof PathChild) {
231 PathChild child = (PathChild)path;
232 int parent = pathToId(child.parent);
235 return getChildIfExists(parent, child.name);
237 else if(path instanceof PathRoot)
238 return getRootIfExists(((PathRoot)path).name);
240 throw new IllegalArgumentException();
243 public int createPathToId(Path path) {
244 if(path instanceof PathChild) {
245 PathChild child = (PathChild)path;
246 return getChild(createPathToId(child.parent), child.name);
248 else if(path instanceof PathRoot)
249 return getRoot(((PathRoot)path).name);
251 throw new IllegalArgumentException();
254 public Path idToPath(int id) {
255 ConsistsOf consistsOf = childMap.get(id);
256 if(consistsOf == null) {
257 String root = invRoots.get(id);
261 return new PathRoot(root);
263 /*System.out.println("ConsistsOf(" +
264 consistsOf.parent + "." + consistsOf.name +
265 " = " + consistsOf.child + ")");
267 //if(consistsOf.parent == consistsOf.child)
269 Path parentPath = idToPath(consistsOf.parent);
270 if(parentPath == null)
272 return new PathChild(consistsOf.name, parentPath);
275 public boolean contains(Path path) {
276 return pathToId(path) >= 0;
279 public boolean isNewResource(int id) {
280 return newResources.contains(id);
283 public Identity[] toArray() {
284 final ArrayList<Identity> identities = new ArrayList<Identity>();
285 collectIdentities(identities);
286 return identities.toArray(new Identity[identities.size()]);
289 public void collectReferences(final boolean[] set) {
290 TIntProcedure proc = new TIntProcedure() {
292 public boolean execute(int value) {
298 roots.forEachValue(proc);
299 childMap.forEach(proc);
300 parentMap.forEach(proc);
303 public int removeIdentity(int id) {
304 ConsistsOf c = childMap.remove(id);
306 parentMap.get(c.parent).remove(c.name);
312 public boolean hasIdentity(int id) {
313 return childMap.containsKey(id);
316 public void definePath(Path path, int resource) {
317 if(path instanceof PathChild) {
318 PathChild child = (PathChild)path;
319 int parent = createPathToId(child.parent);
320 defineChild(parent, child.name, resource);
322 else if(path instanceof PathRoot) {
323 defineRoot(((PathRoot)path).name, resource);
326 throw new IllegalArgumentException();
329 public void printChildMap() {
330 System.out.println("ChildMap:");
331 childMap.forEachValue(new TObjectProcedure<ConsistsOf>() {
334 public boolean execute(ConsistsOf c) {
335 System.out.println(" " +
336 c.child + " = " + c.parent + "." + c.name);
343 private int canonical(int a) {
344 if(unifications.contains(a)) {
345 int b = unifications.get(a);
346 if(unifications.contains(b)) {
347 int c = canonical(b);
348 unifications.put(a, c);
349 unifications.put(b, c);
359 public TIntIntHashMap extractUnifications() {
360 // This normalizes the map
361 for(int a : unifications.keys())
364 TIntIntHashMap result = unifications;
365 unifications = new TIntIntHashMap();
370 public void unify(int a, int b) {
375 unifications.put(a, b);
379 public TIntHashSet getCollisions() {
383 public String[] getRoots() {
384 return roots.keys(new String[roots.size()]);
387 void findChildren(int id, final Path path, final String suffix,
388 final Pattern pattern, final THashSet<Path> result) {
389 if(pattern.matcher(suffix).matches())
391 THashMap<String,ConsistsOf> map = parentMap.get(id);
393 map.forEachValue(new TObjectProcedure<ConsistsOf>() {
395 public boolean execute(ConsistsOf consistsOf) {
396 findChildren(consistsOf.child, new PathChild(consistsOf.name, path),
397 suffix + "/" + consistsOf.name, pattern, result);
403 public int[] getUnfoundedIdentities() {
404 TIntArrayList result = new TIntArrayList();
405 for(int resource : parentMap.keys()) {
406 if(!childMap.containsKey(resource) && !invRoots.containsKey(resource)) {
407 result.add(resource);
410 return result.toArray();
413 public void forEachChild(TObjectProcedure<ConsistsOf> proc) {
414 childMap.forEachValue(proc);
417 public void setIdentity(int child, int parent, String name) {
418 THashMap<String, ConsistsOf> map = parentMap.get(parent);
420 map = new THashMap<String, ConsistsOf>();
421 parentMap.put(parent, map);
423 else if(map.contains(name))
424 throw new IllegalStateException();
425 ConsistsOf consistsOf = new ConsistsOf(parent, name, child);
426 map.put(name, consistsOf);
427 childMap.put(child, consistsOf);