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

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