--- /dev/null
+package org.simantics.graph.store;\r
+\r
+import gnu.trove.list.array.TIntArrayList;\r
+import gnu.trove.map.hash.THashMap;\r
+import gnu.trove.map.hash.TIntIntHashMap;\r
+import gnu.trove.map.hash.TIntObjectHashMap;\r
+import gnu.trove.map.hash.TObjectIntHashMap;\r
+import gnu.trove.procedure.TIntProcedure;\r
+import gnu.trove.procedure.TObjectIntProcedure;\r
+import gnu.trove.procedure.TObjectObjectProcedure;\r
+import gnu.trove.procedure.TObjectProcedure;\r
+import gnu.trove.set.hash.THashSet;\r
+import gnu.trove.set.hash.TIntHashSet;\r
+\r
+import java.util.ArrayList;\r
+import java.util.regex.Pattern;\r
+\r
+import org.simantics.graph.query.Path;\r
+import org.simantics.graph.query.PathChild;\r
+import org.simantics.graph.query.PathRoot;\r
+import org.simantics.graph.representation.External;\r
+import org.simantics.graph.representation.Identity;\r
+import org.simantics.graph.representation.Internal;\r
+import org.simantics.graph.representation.Root;\r
+\r
+public class IdentityStore implements IStore {\r
+ \r
+ private static int[] EMPTY_INT_ARRAY = new int[0];\r
+ \r
+ public static class ConsistsOf {\r
+ public int parent;\r
+ public String name;\r
+ public int child;\r
+ \r
+ public ConsistsOf(int parent, String name, int child) {\r
+ //System.out.println(parent + "." + name + " = " + child);\r
+ this.parent = parent;\r
+ this.name = name;\r
+ this.child = child;\r
+ }\r
+ }\r
+ \r
+ TObjectIntHashMap<String> roots = new TObjectIntHashMap<String>();\r
+ TIntObjectHashMap<String> invRoots = new TIntObjectHashMap<String>();\r
+ TIntObjectHashMap<THashMap<String, ConsistsOf>> parentMap =\r
+ new TIntObjectHashMap<THashMap<String, ConsistsOf>>();\r
+ TIntObjectHashMap<ConsistsOf> childMap = new TIntObjectHashMap<ConsistsOf>();\r
+ TIntHashSet newResources = new TIntHashSet();\r
+ int resourceCount = 0;\r
+ TIntIntHashMap unifications = new TIntIntHashMap();\r
+ TIntHashSet collisions = new TIntHashSet();\r
+ \r
+ public int newResource() {\r
+ return resourceCount++;\r
+ }\r
+\r
+ public boolean markNew(int resource) {\r
+ return newResources.add(resource);\r
+ }\r
+ \r
+ public int[] getNewResources() {\r
+ return newResources.toArray();\r
+ }\r
+ \r
+ public int getResourceCount() {\r
+ return resourceCount;\r
+ }\r
+ \r
+ public void setResourceCount(int newCount) {\r
+ resourceCount = newCount;\r
+ }\r
+ \r
+ public void defineRoot(String name, int root) {\r
+ if(roots.contains(name))\r
+ unify(root, roots.get(name));\r
+ roots.put(name, root);\r
+ invRoots.put(root, name);\r
+ }\r
+ \r
+ public void defineChild(int parent, String name, int child) {\r
+ THashMap<String, ConsistsOf> map = parentMap.get(parent);\r
+ if(map == null) {\r
+ map = new THashMap<String, ConsistsOf>();\r
+ parentMap.put(parent, map); \r
+ }\r
+ ConsistsOf consistsOf = new ConsistsOf(parent, name, child);\r
+ ConsistsOf oldC = map.put(name, consistsOf);\r
+ if(oldC != null)\r
+ unify(child, oldC.child);\r
+ childMap.put(child, consistsOf);\r
+ }\r
+ \r
+ public boolean hasChild(int parent, String name) {\r
+ THashMap<String, ConsistsOf> map = parentMap.get(parent);\r
+ if(map == null)\r
+ return false;\r
+ else\r
+ return map.contains(name);\r
+ }\r
+ \r
+ public int getChild(int parent, String name) {\r
+ THashMap<String, ConsistsOf> map = parentMap.get(parent);\r
+ if(map == null) {\r
+ map = new THashMap<String, ConsistsOf>();\r
+ parentMap.put(parent, map); \r
+ }\r
+ else if(map.contains(name))\r
+ return map.get(name).child;\r
+ int child = newResource();\r
+ ConsistsOf consistsOf = new ConsistsOf(parent, name, child);\r
+ map.put(name, consistsOf);\r
+ childMap.put(child, consistsOf);\r
+ return child;\r
+ }\r
+ \r
+ public int getChildIfExists(int parent, String name) {\r
+ THashMap<String, ConsistsOf> map = parentMap.get(parent);\r
+ if(map != null && map.contains(name))\r
+ return map.get(name).child;\r
+ return -1;\r
+ }\r
+\r
+ public int getRoot(String uri) {\r
+ if(roots.contains(uri))\r
+ return roots.get(uri);\r
+ else {\r
+ int root = newResource();\r
+ roots.put(uri, root);\r
+ invRoots.put(root, uri);\r
+ return root;\r
+ }\r
+ }\r
+ \r
+ public int getRootIfExists(String uri) {\r
+ if(roots.contains(uri))\r
+ return roots.get(uri);\r
+ return -1;\r
+ }\r
+ \r
+ public int[] getChildren(int id) {\r
+ THashMap<String,ConsistsOf> map = parentMap.get(id);\r
+ if(map == null)\r
+ return EMPTY_INT_ARRAY;\r
+ final int[] result = new int[map.size()];\r
+ map.forEachValue(new TObjectProcedure<ConsistsOf>() {\r
+ int i=0;\r
+ @Override\r
+ public boolean execute(ConsistsOf object) {\r
+ result[i++] = object.child;\r
+ return true;\r
+ }\r
+ });\r
+ return result;\r
+ }\r
+ \r
+ public THashMap<String, ConsistsOf> getChildMap(int parent) {\r
+ return parentMap.get(parent); \r
+ }\r
+ \r
+ private void collectIdentities(final int parent, final ArrayList<Identity> identities) {\r
+ THashMap<String, ConsistsOf> map = parentMap.get(parent);\r
+ if(map != null) {\r
+ map.forEachEntry(new TObjectObjectProcedure<String, ConsistsOf>() {\r
+ \r
+ @Override\r
+ public boolean execute(String a, ConsistsOf b) {\r
+ if(newResources.contains(b.child))\r
+ identities.add(new Identity(b.child, new Internal(parent, a)));\r
+ else\r
+ identities.add(new Identity(b.child, new External(parent, a)));\r
+ collectIdentities(b.child, identities);\r
+ return true;\r
+ }\r
+ });\r
+ }\r
+ }\r
+ \r
+ private void collectIdentities(final ArrayList<Identity> identities) {\r
+ roots.forEachEntry(new TObjectIntProcedure<String>() { \r
+ @Override\r
+ public boolean execute(String a, int b) {\r
+ identities.add(new Identity(b, new Root(a, "")));\r
+ collectIdentities(b, identities);\r
+ return true;\r
+ } \r
+ });\r
+ }\r
+ \r
+ @Override\r
+ public void map(final TIntIntHashMap map) {\r
+ collisions = IndexMappingUtils.map(map, collisions);\r
+ newResources = IndexMappingUtils.map(map, newResources); \r
+ IndexMappingUtils.map(map, roots);\r
+ invRoots = IndexMappingUtils.map(map, invRoots, collisions);\r
+ \r
+ final ArrayList<ConsistsOf> consistsOfs = new ArrayList<ConsistsOf>(childMap.size());\r
+ childMap.forEachValue(new TObjectProcedure<IdentityStore.ConsistsOf>() { \r
+ @Override\r
+ public boolean execute(ConsistsOf c) {\r
+ if(map.contains(c.parent))\r
+ c.parent = map.get(c.parent);\r
+ if(map.contains(c.child))\r
+ c.child = map.get(c.child);\r
+ consistsOfs.add(c);\r
+ return true;\r
+ }\r
+ });\r
+ \r
+ childMap.clear();\r
+ parentMap.clear();\r
+ assert(unifications.isEmpty());\r
+ \r
+ for(ConsistsOf c : consistsOfs) {\r
+ THashMap<String, ConsistsOf> m = parentMap.get(c.parent);\r
+ if(m == null) {\r
+ m = new THashMap<String, ConsistsOf>();\r
+ parentMap.put(c.parent, m); \r
+ }\r
+ ConsistsOf oldC = m.put(c.name, c);\r
+ ConsistsOf childC = childMap.put(c.child, c);\r
+ if(childC != null && (childC.parent != c.parent || !childC.name.equals(c.name)))\r
+ collisions.add(c.child);\r
+ \r
+ if(oldC != null) \r
+ unify(oldC.child, c.child);\r
+ }\r
+ }\r
+ \r
+ public int pathToId(Path path) {\r
+ if(path instanceof PathChild) {\r
+ PathChild child = (PathChild)path;\r
+ int parent = pathToId(child.parent);\r
+ if(parent < 0)\r
+ return -1;\r
+ return getChildIfExists(parent, child.name);\r
+ }\r
+ else if(path instanceof PathRoot)\r
+ return getRootIfExists(((PathRoot)path).name);\r
+ else\r
+ throw new IllegalArgumentException();\r
+ }\r
+ \r
+ public int createPathToId(Path path) {\r
+ if(path instanceof PathChild) {\r
+ PathChild child = (PathChild)path;\r
+ return getChild(createPathToId(child.parent), child.name);\r
+ }\r
+ else if(path instanceof PathRoot)\r
+ return getRoot(((PathRoot)path).name);\r
+ else\r
+ throw new IllegalArgumentException();\r
+ }\r
+ \r
+ public Path idToPath(int id) {\r
+ ConsistsOf consistsOf = childMap.get(id);\r
+ if(consistsOf == null) {\r
+ String root = invRoots.get(id);\r
+ if(root == null)\r
+ return null;\r
+ else\r
+ return new PathRoot(root);\r
+ }\r
+ /*System.out.println("ConsistsOf(" + \r
+ consistsOf.parent + "." + consistsOf.name + \r
+ " = " + consistsOf.child + ")");\r
+ */\r
+ //if(consistsOf.parent == consistsOf.child)\r
+ // return null; \r
+ Path parentPath = idToPath(consistsOf.parent);\r
+ if(parentPath == null)\r
+ return null;\r
+ return new PathChild(consistsOf.name, parentPath);\r
+ }\r
+ \r
+ public boolean contains(Path path) {\r
+ return pathToId(path) >= 0;\r
+ }\r
+\r
+ public boolean isNewResource(int id) {\r
+ return newResources.contains(id);\r
+ }\r
+\r
+ public Identity[] toArray() {\r
+ final ArrayList<Identity> identities = new ArrayList<Identity>();\r
+ collectIdentities(identities);\r
+ return identities.toArray(new Identity[identities.size()]);\r
+ }\r
+ \r
+ public void collectReferences(final boolean[] set) {\r
+ TIntProcedure proc = new TIntProcedure() { \r
+ @Override\r
+ public boolean execute(int value) {\r
+ set[value] = true;\r
+ return true;\r
+ }\r
+ };\r
+ \r
+ roots.forEachValue(proc);\r
+ childMap.forEach(proc);\r
+ parentMap.forEach(proc);\r
+ }\r
+\r
+ public int removeIdentity(int id) {\r
+ ConsistsOf c = childMap.remove(id);\r
+ if(c != null) { \r
+ parentMap.get(c.parent).remove(c.name);\r
+ return c.parent;\r
+ }\r
+ return -1;\r
+ }\r
+\r
+ public boolean hasIdentity(int id) {\r
+ return childMap.containsKey(id);\r
+ }\r
+\r
+ public void definePath(Path path, int resource) {\r
+ if(path instanceof PathChild) {\r
+ PathChild child = (PathChild)path;\r
+ int parent = createPathToId(child.parent);\r
+ defineChild(parent, child.name, resource);\r
+ }\r
+ else if(path instanceof PathRoot) {\r
+ defineRoot(((PathRoot)path).name, resource);\r
+ }\r
+ else\r
+ throw new IllegalArgumentException(); \r
+ }\r
+ \r
+ public void printChildMap() {\r
+ System.out.println("ChildMap:");\r
+ childMap.forEachValue(new TObjectProcedure<ConsistsOf>() {\r
+\r
+ @Override\r
+ public boolean execute(ConsistsOf c) {\r
+ System.out.println(" " + \r
+ c.child + " = " + c.parent + "." + c.name);\r
+ return true;\r
+ }\r
+ \r
+ });\r
+ }\r
+ \r
+ private int canonical(int a) {\r
+ if(unifications.contains(a)) {\r
+ int b = unifications.get(a);\r
+ if(unifications.contains(b)) {\r
+ int c = canonical(b);\r
+ unifications.put(a, c);\r
+ unifications.put(b, c);\r
+ return c;\r
+ }\r
+ else \r
+ return b;\r
+ }\r
+ else\r
+ return a;\r
+ }\r
+ \r
+ public TIntIntHashMap extractUnifications() {\r
+ // This normalizes the map\r
+ for(int a : unifications.keys())\r
+ canonical(a);\r
+ \r
+ TIntIntHashMap result = unifications;\r
+ unifications = new TIntIntHashMap();\r
+ \r
+ return result;\r
+ }\r
+ \r
+ public void unify(int a, int b) {\r
+ if(a != b) {\r
+ a = canonical(a);\r
+ b = canonical(b);\r
+ if(a != b)\r
+ unifications.put(a, b);\r
+ }\r
+ }\r
+ \r
+ public TIntHashSet getCollisions() {\r
+ return collisions;\r
+ }\r
+\r
+ public String[] getRoots() {\r
+ return roots.keys(new String[roots.size()]);\r
+ }\r
+\r
+ void findChildren(int id, final Path path, final String suffix,\r
+ final Pattern pattern, final THashSet<Path> result) {\r
+ if(pattern.matcher(suffix).matches())\r
+ result.add(path);\r
+ THashMap<String,ConsistsOf> map = parentMap.get(id);\r
+ if(map != null)\r
+ map.forEachValue(new TObjectProcedure<ConsistsOf>() {\r
+ @Override\r
+ public boolean execute(ConsistsOf consistsOf) {\r
+ findChildren(consistsOf.child, new PathChild(consistsOf.name, path), \r
+ suffix + "/" + consistsOf.name, pattern, result);\r
+ return true;\r
+ }\r
+ });\r
+ }\r
+\r
+ public int[] getUnfoundedIdentities() {\r
+ TIntArrayList result = new TIntArrayList();\r
+ for(int resource : parentMap.keys()) {\r
+ if(!childMap.containsKey(resource) && !invRoots.containsKey(resource)) {\r
+ result.add(resource);\r
+ }\r
+ }\r
+ return result.toArray();\r
+ }\r
+ \r
+ public void forEachChild(TObjectProcedure<ConsistsOf> proc) {\r
+ childMap.forEachValue(proc);\r
+ }\r
+\r
+ public void setIdentity(int child, int parent, String name) {\r
+ THashMap<String, ConsistsOf> map = parentMap.get(parent);\r
+ if(map == null) {\r
+ map = new THashMap<String, ConsistsOf>();\r
+ parentMap.put(parent, map); \r
+ }\r
+ else if(map.contains(name))\r
+ throw new IllegalStateException(); \r
+ ConsistsOf consistsOf = new ConsistsOf(parent, name, child);\r
+ map.put(name, consistsOf);\r
+ childMap.put(child, consistsOf);\r
+ }\r
+ \r
+}\r