bundles/org.simantics.graph/src/org/simantics/graph/store/IdentityStore.java

   1 package org.simantics.graph.store;\r
   2 \r
   3 import gnu.trove.list.array.TIntArrayList;\r
   4 import gnu.trove.map.hash.THashMap;\r
   5 import gnu.trove.map.hash.TIntIntHashMap;\r
   6 import gnu.trove.map.hash.TIntObjectHashMap;\r
   7 import gnu.trove.map.hash.TObjectIntHashMap;\r
   8 import gnu.trove.procedure.TIntProcedure;\r
   9 import gnu.trove.procedure.TObjectIntProcedure;\r
  10 import gnu.trove.procedure.TObjectObjectProcedure;\r
  11 import gnu.trove.procedure.TObjectProcedure;\r
  12 import gnu.trove.set.hash.THashSet;\r
  13 import gnu.trove.set.hash.TIntHashSet;\r
  14 \r
  15 import java.util.ArrayList;\r
  16 import java.util.regex.Pattern;\r
  17 \r
  18 import org.simantics.graph.query.Path;\r
  19 import org.simantics.graph.query.PathChild;\r
  20 import org.simantics.graph.query.PathRoot;\r
  21 import org.simantics.graph.representation.External;\r
  22 import org.simantics.graph.representation.Identity;\r
  23 import org.simantics.graph.representation.Internal;\r
  24 import org.simantics.graph.representation.Root;\r
  25 \r
  26 public class IdentityStore implements IStore {\r
  27         \r
  28         private static int[] EMPTY_INT_ARRAY = new int[0];\r
  29         \r
  30         public static class ConsistsOf {\r
  31                 public int parent;\r
  32                 public String name;\r
  33                 public int child;\r
  34                 \r
  35                 public ConsistsOf(int parent, String name, int child) {\r
  36                         //System.out.println(parent + "." + name + " = " + child);\r
  37                         this.parent = parent;\r
  38                         this.name = name;\r
  39                         this.child = child;\r
  40                 }\r
  41         }\r
  42         \r
  43         TObjectIntHashMap<String> roots = new TObjectIntHashMap<String>();\r
  44         TIntObjectHashMap<String> invRoots = new TIntObjectHashMap<String>();\r
  45         TIntObjectHashMap<THashMap<String, ConsistsOf>> parentMap =\r
  46                 new TIntObjectHashMap<THashMap<String, ConsistsOf>>();\r
  47         TIntObjectHashMap<ConsistsOf> childMap = new TIntObjectHashMap<ConsistsOf>();\r
  48         TIntHashSet newResources = new TIntHashSet();\r
  49         int resourceCount = 0;\r
  50         TIntIntHashMap unifications = new TIntIntHashMap();\r
  51         TIntHashSet collisions = new TIntHashSet();\r
  52         \r
  53         public int newResource() {\r
  54                 return resourceCount++;\r
  55         }\r
  56 \r
  57         public boolean markNew(int resource) {\r
  58                 return newResources.add(resource);\r
  59         }\r
  60         \r
  61         public int[] getNewResources() {\r
  62                 return newResources.toArray();\r
  63         }\r
  64         \r
  65         public int getResourceCount() {\r
  66                 return resourceCount;\r
  67         }\r
  68         \r
  69         public void setResourceCount(int newCount) {\r
  70                 resourceCount = newCount;\r
  71         }\r
  72                 \r
  73         public void defineRoot(String name, int root) {\r
  74                 if(roots.contains(name))\r
  75                         unify(root, roots.get(name));\r
  76                 roots.put(name, root);\r
  77                 invRoots.put(root, name);\r
  78         }\r
  79         \r
  80         public void defineChild(int parent, String name, int child) {\r
  81                 THashMap<String, ConsistsOf> map = parentMap.get(parent);\r
  82                 if(map == null) {\r
  83                         map = new THashMap<String, ConsistsOf>();\r
  84                         parentMap.put(parent, map);                     \r
  85                 }\r
  86                 ConsistsOf consistsOf = new ConsistsOf(parent, name, child);\r
  87                 ConsistsOf oldC = map.put(name, consistsOf);\r
  88                 if(oldC != null)\r
  89                         unify(child, oldC.child);\r
  90                 childMap.put(child, consistsOf);\r
  91         }\r
  92         \r
  93         public boolean hasChild(int parent, String name) {\r
  94             THashMap<String, ConsistsOf> map = parentMap.get(parent);\r
  95         if(map == null)\r
  96             return false;\r
  97         else\r
  98             return map.contains(name);\r
  99         }\r
 100         \r
 101         public int getChild(int parent, String name) {\r
 102                 THashMap<String, ConsistsOf> map = parentMap.get(parent);\r
 103                 if(map == null) {\r
 104                         map = new THashMap<String, ConsistsOf>();\r
 105                         parentMap.put(parent, map);                     \r
 106                 }\r
 107                 else if(map.contains(name))\r
 108                         return map.get(name).child;\r
 109                 int child = newResource();\r
 110                 ConsistsOf consistsOf = new ConsistsOf(parent, name, child);\r
 111                 map.put(name, consistsOf);\r
 112                 childMap.put(child, consistsOf);\r
 113                 return child;\r
 114         }\r
 115         \r
 116         public int getChildIfExists(int parent, String name) {\r
 117                 THashMap<String, ConsistsOf> map = parentMap.get(parent);\r
 118                 if(map != null && map.contains(name))\r
 119                         return map.get(name).child;\r
 120                 return -1;\r
 121         }\r
 122 \r
 123         public int getRoot(String uri) {\r
 124                 if(roots.contains(uri))\r
 125                         return roots.get(uri);\r
 126                 else {\r
 127                         int root = newResource();\r
 128                         roots.put(uri, root);\r
 129                         invRoots.put(root, uri);\r
 130                         return root;\r
 131                 }\r
 132         }\r
 133         \r
 134         public int getRootIfExists(String uri) {\r
 135                 if(roots.contains(uri))\r
 136                         return roots.get(uri);\r
 137                 return -1;\r
 138         }\r
 139         \r
 140         public int[] getChildren(int id) {\r
 141                 THashMap<String,ConsistsOf> map = parentMap.get(id);\r
 142                 if(map == null)\r
 143                         return EMPTY_INT_ARRAY;\r
 144                 final int[] result = new int[map.size()];\r
 145                 map.forEachValue(new TObjectProcedure<ConsistsOf>() {\r
 146                         int i=0;\r
 147                         @Override\r
 148                         public boolean execute(ConsistsOf object) {\r
 149                                 result[i++] = object.child;\r
 150                                 return true;\r
 151                         }\r
 152                 });\r
 153                 return result;\r
 154         }\r
 155         \r
 156         public THashMap<String, ConsistsOf> getChildMap(int parent) {\r
 157         return parentMap.get(parent);       \r
 158         }\r
 159         \r
 160         private void collectIdentities(final int parent, final ArrayList<Identity> identities) {\r
 161                 THashMap<String, ConsistsOf> map = parentMap.get(parent);\r
 162                 if(map != null) {\r
 163                         map.forEachEntry(new TObjectObjectProcedure<String, ConsistsOf>() {\r
 164                                 \r
 165                                 @Override\r
 166                                 public boolean execute(String a, ConsistsOf b) {\r
 167                                         if(newResources.contains(b.child))\r
 168                                                 identities.add(new Identity(b.child, new Internal(parent, a)));\r
 169                                         else\r
 170                                                 identities.add(new Identity(b.child, new External(parent, a)));\r
 171                                         collectIdentities(b.child, identities);\r
 172                                         return true;\r
 173                                 }\r
 174                         });\r
 175                 }\r
 176         }\r
 177         \r
 178         private void collectIdentities(final ArrayList<Identity> identities) {\r
 179                 roots.forEachEntry(new TObjectIntProcedure<String>() {                  \r
 180                         @Override\r
 181                         public boolean execute(String a, int b) {\r
 182                                 identities.add(new Identity(b, new Root(a, "")));\r
 183                                 collectIdentities(b, identities);\r
 184                                 return true;\r
 185                         }                       \r
 186                 });\r
 187         }\r
 188         \r
 189         @Override\r
 190         public void map(final TIntIntHashMap map) {\r
 191                 collisions = IndexMappingUtils.map(map, collisions);\r
 192                 newResources = IndexMappingUtils.map(map, newResources);                \r
 193                 IndexMappingUtils.map(map, roots);\r
 194                 invRoots = IndexMappingUtils.map(map, invRoots, collisions);\r
 195                 \r
 196                 final ArrayList<ConsistsOf> consistsOfs = new ArrayList<ConsistsOf>(childMap.size());\r
 197                 childMap.forEachValue(new TObjectProcedure<IdentityStore.ConsistsOf>() {                        \r
 198                         @Override\r
 199                         public boolean execute(ConsistsOf c) {\r
 200                                 if(map.contains(c.parent))\r
 201                                         c.parent = map.get(c.parent);\r
 202                                 if(map.contains(c.child))\r
 203                                         c.child = map.get(c.child);\r
 204                                 consistsOfs.add(c);\r
 205                                 return true;\r
 206                         }\r
 207                 });\r
 208                 \r
 209                 childMap.clear();\r
 210                 parentMap.clear();\r
 211                 assert(unifications.isEmpty());\r
 212                 \r
 213                 for(ConsistsOf c : consistsOfs) {\r
 214                         THashMap<String, ConsistsOf> m = parentMap.get(c.parent);\r
 215                         if(m == null) {\r
 216                                 m = new THashMap<String, ConsistsOf>();\r
 217                                 parentMap.put(c.parent, m);                     \r
 218                         }\r
 219                         ConsistsOf oldC = m.put(c.name, c);\r
 220                         ConsistsOf childC = childMap.put(c.child, c);\r
 221                         if(childC != null && (childC.parent != c.parent || !childC.name.equals(c.name)))\r
 222                                 collisions.add(c.child);\r
 223                         \r
 224                         if(oldC != null) \r
 225                                 unify(oldC.child, c.child);\r
 226                 }\r
 227         }\r
 228         \r
 229         public int pathToId(Path path) {\r
 230                 if(path instanceof PathChild) {\r
 231                         PathChild child = (PathChild)path;\r
 232                         int parent = pathToId(child.parent);\r
 233                         if(parent < 0)\r
 234                                 return -1;\r
 235                         return getChildIfExists(parent, child.name);\r
 236                 }\r
 237                 else if(path instanceof PathRoot)\r
 238                         return getRootIfExists(((PathRoot)path).name);\r
 239                 else\r
 240                         throw new IllegalArgumentException();\r
 241         }\r
 242         \r
 243         public int createPathToId(Path path) {\r
 244                 if(path instanceof PathChild) {\r
 245                         PathChild child = (PathChild)path;\r
 246                         return getChild(createPathToId(child.parent), child.name);\r
 247                 }\r
 248                 else if(path instanceof PathRoot)\r
 249                         return getRoot(((PathRoot)path).name);\r
 250                 else\r
 251                         throw new IllegalArgumentException();\r
 252         }\r
 253         \r
 254         public Path idToPath(int id) {\r
 255                 ConsistsOf consistsOf = childMap.get(id);\r
 256                 if(consistsOf == null) {\r
 257                         String root = invRoots.get(id);\r
 258                         if(root == null)\r
 259                                 return null;\r
 260                         else\r
 261                                 return new PathRoot(root);\r
 262                 }\r
 263                 /*System.out.println("ConsistsOf(" + \r
 264                                 consistsOf.parent + "." + consistsOf.name + \r
 265                                 " = " + consistsOf.child + ")");\r
 266                                 */\r
 267                 //if(consistsOf.parent == consistsOf.child)\r
 268                 //    return null; \r
 269                 Path parentPath = idToPath(consistsOf.parent);\r
 270                 if(parentPath == null)\r
 271                         return null;\r
 272                 return new PathChild(consistsOf.name, parentPath);\r
 273         }\r
 274         \r
 275         public boolean contains(Path path) {\r
 276                 return pathToId(path) >= 0;\r
 277         }\r
 278 \r
 279         public boolean isNewResource(int id) {\r
 280                 return newResources.contains(id);\r
 281         }\r
 282 \r
 283         public Identity[] toArray() {\r
 284                 final ArrayList<Identity> identities = new ArrayList<Identity>();\r
 285                 collectIdentities(identities);\r
 286                 return identities.toArray(new Identity[identities.size()]);\r
 287         }\r
 288         \r
 289         public void collectReferences(final boolean[] set) {\r
 290                 TIntProcedure proc = new TIntProcedure() {                      \r
 291                         @Override\r
 292                         public boolean execute(int value) {\r
 293                                 set[value] = true;\r
 294                                 return true;\r
 295                         }\r
 296                 };\r
 297                 \r
 298                 roots.forEachValue(proc);\r
 299                 childMap.forEach(proc);\r
 300                 parentMap.forEach(proc);\r
 301         }\r
 302 \r
 303         public int removeIdentity(int id) {\r
 304                 ConsistsOf c = childMap.remove(id);\r
 305                 if(c != null) {             \r
 306                     parentMap.get(c.parent).remove(c.name);\r
 307                     return c.parent;\r
 308                 }\r
 309                 return -1;\r
 310         }\r
 311 \r
 312         public boolean hasIdentity(int id) {\r
 313                 return childMap.containsKey(id);\r
 314         }\r
 315 \r
 316         public void definePath(Path path, int resource) {\r
 317                 if(path instanceof PathChild) {\r
 318                         PathChild child = (PathChild)path;\r
 319                         int parent = createPathToId(child.parent);\r
 320                         defineChild(parent, child.name, resource);\r
 321                 }\r
 322                 else if(path instanceof PathRoot) {\r
 323                         defineRoot(((PathRoot)path).name, resource);\r
 324                 }\r
 325                 else\r
 326                         throw new IllegalArgumentException();           \r
 327         }\r
 328         \r
 329         public void printChildMap() {\r
 330                 System.out.println("ChildMap:");\r
 331                 childMap.forEachValue(new TObjectProcedure<ConsistsOf>() {\r
 332 \r
 333                         @Override\r
 334                         public boolean execute(ConsistsOf c) {\r
 335                                 System.out.println("    " + \r
 336                                                 c.child + " = " + c.parent + "." + c.name);\r
 337                                 return true;\r
 338                         }\r
 339                         \r
 340                 });\r
 341         }\r
 342         \r
 343         private int canonical(int a) {\r
 344                 if(unifications.contains(a)) {\r
 345                         int b = unifications.get(a);\r
 346                         if(unifications.contains(b)) {\r
 347                                 int c = canonical(b);\r
 348                                 unifications.put(a, c);\r
 349                                 unifications.put(b, c);\r
 350                                 return c;\r
 351                         }\r
 352                         else \r
 353                                 return b;\r
 354                 }\r
 355                 else\r
 356                         return a;\r
 357         }\r
 358         \r
 359         public TIntIntHashMap extractUnifications() {\r
 360                 // This normalizes the map\r
 361                 for(int a : unifications.keys())\r
 362                         canonical(a);\r
 363                 \r
 364                 TIntIntHashMap result = unifications;\r
 365                 unifications = new TIntIntHashMap();\r
 366                 \r
 367                 return result;\r
 368         }\r
 369         \r
 370         public void unify(int a, int b) {\r
 371                 if(a != b) {\r
 372                         a = canonical(a);\r
 373                         b = canonical(b);\r
 374                         if(a != b)\r
 375                                 unifications.put(a, b);\r
 376                 }\r
 377         }\r
 378         \r
 379         public TIntHashSet getCollisions() {\r
 380                 return collisions;\r
 381         }\r
 382 \r
 383         public String[] getRoots() {\r
 384                 return roots.keys(new String[roots.size()]);\r
 385         }\r
 386 \r
 387         void findChildren(int id, final Path path, final String suffix,\r
 388                         final Pattern pattern, final THashSet<Path> result) {\r
 389                 if(pattern.matcher(suffix).matches())\r
 390                         result.add(path);\r
 391                 THashMap<String,ConsistsOf> map = parentMap.get(id);\r
 392                 if(map != null)\r
 393                         map.forEachValue(new TObjectProcedure<ConsistsOf>() {\r
 394                                 @Override\r
 395                                 public boolean execute(ConsistsOf consistsOf) {\r
 396                                         findChildren(consistsOf.child, new PathChild(consistsOf.name, path), \r
 397                                                         suffix + "/" + consistsOf.name, pattern, result);\r
 398                                         return true;\r
 399                                 }\r
 400                         });\r
 401         }\r
 402 \r
 403     public int[] getUnfoundedIdentities() {\r
 404         TIntArrayList result = new TIntArrayList();\r
 405         for(int resource : parentMap.keys()) {\r
 406             if(!childMap.containsKey(resource) && !invRoots.containsKey(resource)) {\r
 407                 result.add(resource);\r
 408             }\r
 409         }\r
 410         return result.toArray();\r
 411     }\r
 412     \r
 413     public void forEachChild(TObjectProcedure<ConsistsOf> proc) {\r
 414         childMap.forEachValue(proc);\r
 415     }\r
 416 \r
 417     public void setIdentity(int child, int parent, String name) {\r
 418         THashMap<String, ConsistsOf> map = parentMap.get(parent);\r
 419         if(map == null) {\r
 420             map = new THashMap<String, ConsistsOf>();\r
 421             parentMap.put(parent, map);         \r
 422         }\r
 423         else if(map.contains(name))\r
 424             throw new IllegalStateException();        \r
 425         ConsistsOf consistsOf = new ConsistsOf(parent, name, child);\r
 426         map.put(name, consistsOf);\r
 427         childMap.put(child, consistsOf);\r
 428     }\r
 429         \r
 430 }\r