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

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