bundles/org.simantics.db.common/src/org/simantics/db/common/utils/OrderedSetUtils.java

   1 /*******************************************************************************
   2  * Copyright (c) 2007, 2018 Association for Decentralized Information Management
   3  * in Industry THTH ry.
   4  * All rights reserved. This program and the accompanying materials
   5  * are made available under the terms of the Eclipse Public License v1.0
   6  * which accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *
   9  * Contributors:
  10  *     VTT Technical Research Centre of Finland - initial API and implementation
  11  *******************************************************************************/
  12 package org.simantics.db.common.utils;
  13
  14 import java.util.ArrayList;
  15 import java.util.Collection;
  16 import java.util.Collections;
  17 import java.util.HashSet;
  18 import java.util.List;
  19 import java.util.ListIterator;
  20 import java.util.Set;
  21
  22 import org.simantics.databoard.Bindings;
  23 import org.simantics.db.AsyncReadGraph;
  24 import org.simantics.db.ReadGraph;
  25 import org.simantics.db.Resource;
  26 import org.simantics.db.WriteGraph;
  27 import org.simantics.db.WriteOnlyGraph;
  28 import org.simantics.db.exception.DatabaseException;
  29 import org.simantics.db.exception.RuntimeDatabaseException;
  30 import org.simantics.db.exception.ValidationException;
  31 import org.simantics.db.function.DbFunction;
  32 import org.simantics.db.procedure.AsyncMultiProcedure;
  33 import org.simantics.layer0.Layer0;
  34 import org.simantics.utils.datastructures.Pair;
  35
  36 public class OrderedSetUtils {
  37
  38     /**
  39      * Returns true, if <tt>l</tt> contains the element <tt>el</tt>.
  40      */
  41     public static boolean contains(ReadGraph g, Resource l, Resource el) throws DatabaseException {
  42         return g.hasStatement(el, l) && !l.equals(el);
  43     }
  44
  45     /**
  46      * Returns the next element in the ordered set or <tt>l</tt>,
  47      * if <tt>el</tt> is the last element. Called for <tt>el</tt>, returns
  48      * the first element in the set.
  49      */
  50     public static Resource next(ReadGraph g, Resource l, Resource el) throws DatabaseException {
  51         Collection<Resource> nexts = g.getObjects(el, l);
  52         if(nexts.size() != 1)
  53             throw new InvalidOrderedSetException("Invalid list element: " + l + " " + el + " " + nexts.size() + " successors.");
  54         for(Resource r : nexts)
  55             return r;
  56         return null;
  57     }
  58
  59     public static void forNext(AsyncReadGraph g, final Resource l, Resource el, final AsyncMultiProcedure<Resource> procedure) {
  60         g.forEachObject(el, l, new AsyncMultiProcedure<Resource>() {
  61
  62             @Override
  63             public void exception(AsyncReadGraph graph, Throwable t) {
  64                 procedure.exception(graph, t);
  65             }
  66
  67             @Override
  68             public void finished(AsyncReadGraph graph) {
  69             }
  70
  71             @Override
  72             public void execute(AsyncReadGraph graph, Resource nel) {
  73                 if(!nel.equals(l)) {
  74                     procedure.execute(graph, nel);
  75                     forNext(graph, l, nel, procedure);
  76                 }
  77             }
  78         });
  79 //        Collection<Resource> nexts = g.getObjects(el, l);
  80 //        if(nexts.size() != 1)
  81 //            throw new NoSingleResultException("Invalid list element: " + nexts.size() + " successors.");
  82 //        for(Resource r : nexts)
  83 //            return r;
  84 //        return null;
  85     }
  86
  87     /**
  88      * Returns the previouse element in the ordered set or <tt>l</tt>,
  89      * if <tt>el</tt> is the first element. Called for <tt>el</tt>, returns
  90      * the last element in the set.
  91      */
  92     public static Resource prev(ReadGraph g, Resource l, Resource el) throws DatabaseException {
  93         Collection<Resource> prevs = g.getObjects(el, g.getInverse(l));
  94         if(prevs.size() != 1) {
  95             throw new InvalidOrderedSetException("Invalid list element, " + prevs.size() + " predecessors.");
  96         }
  97         for(Resource r : prevs)
  98             return r;
  99         return null;
 100     }
 101
 102     /**
 103      * Adds a given elements <tt>el</tt> to the list <tt>l</tt>. Returns
 104      * true, if the element was really added.
 105      */
 106     public static boolean add(WriteGraph g, Resource l, Resource el) throws DatabaseException {
 107         if(g.hasStatement(el, l))
 108             return false;
 109         Resource back = prev(g, l, l);
 110         g.denyStatement(back, l, l);
 111         g.claim(back, l, el);
 112         g.claim(el, l, l);
 113         return true;
 114     }
 115
 116     /**
 117      * Adds a given elements <tt>el</tt> to the list <tt>l</tt>. Returns
 118      * true, if the element was really added.
 119      */
 120     public static boolean addFirst(WriteGraph g, Resource l, Resource el) throws DatabaseException {
 121         return addAfter(g, l, l, el);
 122     }
 123
 124     public static boolean addAll(WriteGraph g, Resource l, Iterable<Resource> els) throws DatabaseException {
 125         for(Resource r : els)
 126             if(g.hasStatement(r, l))
 127                 return false;
 128         Resource cur = prev(g, l, l);
 129         g.denyStatement(cur, l, l);
 130         for(Resource r : els) {
 131             g.claim(cur, l, r);
 132             cur = r;
 133         }
 134         g.claim(cur, l, l);
 135         return true;
 136     }
 137
 138     public static boolean addAllNew(WriteGraph g, Resource l, Iterable<Resource> els) throws DatabaseException {
 139         Resource cur = prev(g, l, l);
 140         Resource inv = g.getInverse(l);
 141         g.deny(cur, l, inv, l);
 142         for(Resource r : els) {
 143             g.claim(cur, l, inv, r);
 144             cur = r;
 145         }
 146         g.claim(cur, l, inv, l);
 147         return true;
 148     }
 149
 150     public static boolean addAfter(WriteGraph g, Resource l, Resource pos, Resource el) throws DatabaseException {
 151         if(g.hasStatement(el, l))
 152             return false;
 153         Resource next = next(g, l, pos);
 154         g.denyStatement(pos, l, next);
 155         g.claim(pos, l, el);
 156         g.claim(el, l, next);
 157         return true;
 158     }
 159
 160     public static boolean addBefore(WriteGraph g, Resource l, Resource pos, Resource el) throws DatabaseException {
 161         if(g.hasStatement(el, l))
 162             return false;
 163         Resource prev = prev(g, l, pos);
 164         g.denyStatement(prev, l, pos);
 165         g.claim(prev, l, el);
 166         g.claim(el, l, pos);
 167         return true;
 168     }
 169
 170     /**
 171      * Removes a given elements <tt>el</tt> from the list <tt>l</tt>. Returns
 172      * true, if the element was really removed.
 173      */
 174     public static boolean remove(WriteGraph g, Resource l, Resource el) throws DatabaseException {
 175         Collection<Resource> nexts = g.getObjects(el, l);
 176         if(nexts.size() == 0)
 177             return false;
 178         if(nexts.size() != 1)
 179             throw new InvalidOrderedSetException("Invalid list element.");
 180         Collection<Resource> prevs = g.getObjects(el, g.getInverse(l));
 181         if(prevs.size() != 1)
 182             throw new InvalidOrderedSetException("Invalid list element.");
 183
 184         for(Resource p : prevs)
 185             for(Resource n : nexts) {
 186                 g.denyStatement(p, l, el);
 187                 g.denyStatement(el, l, n);
 188                 g.claim(p, l, n);
 189                 return true;
 190             }
 191         return true;
 192     }
 193
 194     public static List<Resource> removeList(WriteGraph g, Resource l) throws DatabaseException {
 195         List<Resource> els = toList(g, l);
 196         for(Resource el : els)
 197             g.deny(el, l);
 198         g.deny(l, l);
 199         Resource inv = g.getInverse(l);
 200         g.deny(l);
 201         g.deny(inv);
 202         return els;
 203     }
 204
 205     public static void replace(WriteGraph g, Resource l, Resource oldEl, Resource newEl) throws DatabaseException {
 206         Collection<Resource> nexts = g.getObjects(oldEl, l);
 207         if(nexts.size() != 1)
 208             throw new InvalidOrderedSetException("Invalid list element.");
 209         Collection<Resource> prevs = g.getObjects(oldEl, g.getInverse(l));
 210         if(prevs.size() != 1)
 211             throw new InvalidOrderedSetException("Invalid list element.");
 212
 213         for(Resource p : prevs)
 214             for(Resource n : nexts) {
 215                 g.denyStatement(p, l, oldEl);
 216                 g.denyStatement(oldEl, l, n);
 217                 g.claim(p, l, newEl);
 218                 g.claim(newEl, l, n);
 219                 return;
 220             }
 221     }
 222
 223     /**
 224      * Converts ordered set into a list.
 225      */
 226     public static List<Resource> toList(ReadGraph g, Resource l) throws DatabaseException {
 227         ArrayList<Resource> ret = new ArrayList<Resource>();
 228         Resource cur = l;
 229         while(true) {
 230             cur = next(g, l, cur);
 231             if(cur.equals(l))
 232                 return ret;
 233             ret.add(cur);
 234         }
 235     }
 236
 237     /**
 238      * Creates an empty ordered set.
 239      */
 240     public static Resource create(WriteOnlyGraph g, Resource type) throws DatabaseException {
 241         Layer0 l0 = g.getService(Layer0.class);
 242         Resource l = g.newResource();
 243         g.claim(l, l0.InstanceOf, null, type);
 244         g.claim(l, l0.SubrelationOf, null, l0.HasNext);
 245         Resource invL = g.newResource();
 246         g.claim(invL, l0.SubrelationOf, null, l0.HasPrevious);
 247         g.claim(l, l0.InverseOf, l0.InverseOf, invL);
 248         g.claim(l, l, invL, l);
 249         return l;
 250     }
 251
 252     /**
 253      * Creates an ordered set containing the given elements.
 254      * It is assumed that the elements do not contain duplicates.
 255      */
 256     @Deprecated
 257     public static Resource create(WriteOnlyGraph g, Resource type, Iterable<Resource> c) throws DatabaseException {
 258         Layer0 l0 = g.getService(Layer0.class);
 259         Resource l = g.newResource();
 260         g.claim(l, l0.InstanceOf, null, type);
 261         g.claim(l, l0.SubrelationOf, null, l0.HasNext);
 262         Resource invL = g.newResource();
 263         g.claim(invL, l0.SubrelationOf, null, l0.HasPrevious);
 264         g.claim(l, l0.InverseOf, l0.InverseOf, invL);
 265         Resource cur = l;
 266         for(Resource r : c) {
 267             g.claim(cur, l, invL, r);
 268             cur = r;
 269         }
 270         g.claim(cur, l, invL, l);
 271         return l;
 272     }
 273
 274     public static Resource create(WriteOnlyGraph g, Resource type, String name, Iterable<Resource> c) throws DatabaseException {
 275         return createExisting(g, g.newResource(), type, name, c);
 276     }
 277
 278     public static Resource createExisting(WriteOnlyGraph g, Resource l, Resource type, String name, Iterable<Resource> c) throws DatabaseException {
 279         Layer0 l0 = g.getService(Layer0.class);
 280         g.claim(l, l0.InstanceOf, null, type);
 281         g.claim(l, l0.SubrelationOf, null, l0.HasNext);
 282         g.addLiteral(l, l0.HasName, l0.NameOf, l0.String, name, Bindings.STRING);
 283         Resource invL = g.newResource();
 284         g.claim(invL, l0.SubrelationOf, null, l0.HasPrevious);
 285         g.addLiteral(invL, l0.HasName, l0.NameOf, l0.String, "Inverse", Bindings.STRING);
 286         g.claim(l, l0.InverseOf, l0.InverseOf, invL);
 287         g.claim(l, l0.ConsistsOf, l0.PartOf, invL);
 288         Resource cur = l;
 289         for(Resource r : c) {
 290             g.claim(cur, l, invL, r);
 291             cur = r;
 292         }
 293         g.claim(cur, l, invL, l);
 294         return l;
 295     }
 296
 297     public static Resource create(WriteOnlyGraph g, Resource type, Resource ... c) throws DatabaseException {
 298         Layer0 l0 = g.getService(Layer0.class);
 299         Resource l = g.newResource();
 300         g.claim(l, l0.InstanceOf, null, type);
 301         g.claim(l, l0.SubrelationOf, null, l0.HasNext);
 302         Resource invL = g.newResource();
 303         g.claim(invL, l0.SubrelationOf, null, l0.HasPrevious);
 304         g.claim(l, l0.InverseOf, l0.InverseOf, invL);
 305         Resource cur = l;
 306         for(Resource r : c) {
 307             g.claim(cur, l, invL, r);
 308             cur = r;
 309         }
 310         g.claim(cur, l, invL, l);
 311         return l;
 312     }
 313
 314     public static Resource createExisting(WriteGraph g, Resource l, Resource ... c) throws DatabaseException {
 315         Layer0 l0 = Layer0.getInstance(g);
 316         g.claim(l, l0.SubrelationOf, null, l0.HasNext);
 317         Resource invL = g.newResource();
 318         g.claim(invL, l0.SubrelationOf, null, l0.HasPrevious);
 319         g.claim(l, l0.InverseOf, l0.InverseOf, invL);
 320         Resource cur = l;
 321         for(Resource r : c) {
 322             g.claim(cur, l, invL, r);
 323             cur = r;
 324         }
 325         g.claim(cur, l, invL, l);
 326         return l;
 327     }
 328
 329 //    public static Resource create(GraphWriter graph, Resource type, Iterable<Resource> c) throws DatabaseException {
 330 //        ReadGraph g = w.getGraph();
 331 //        Builtins b = g.getBuiltins();
 332 //        Resource l = w.create(type).get();
 333 //        w.let(b.SubrelationOf, b.IsRelatedTo);
 334 //        w.createInverse(l).let(b.SubrelationOf, g.getInverse(b.IsRelatedTo));
 335 //
 336 //        Resource cur = l;
 337 //        for(Resource r : c) {
 338 //            w.stat(cur, l, r);
 339 //            cur = r;
 340 //        }
 341 //        w.stat(cur, l, l);
 342 //        return l;
 343 //    }
 344
 345     public static class OrderedSetIterator implements ListIterator<Resource> {
 346
 347         ReadGraph g;
 348         Resource l;
 349         Resource prev;
 350         Resource next;
 351         int index;
 352         boolean direction;
 353
 354         WriteGraph getWriteGraph() {
 355             if (!(g instanceof WriteGraph))
 356                 throw new UnsupportedOperationException("");
 357             return (WriteGraph) g;
 358         }
 359
 360         public OrderedSetIterator(ReadGraph g, Resource l) throws DatabaseException {
 361             this.g = g;
 362             this.l = l;
 363             this.prev = l;
 364             this.next = OrderedSetUtils.next(g, l, l);
 365             this.index = 0;
 366         }
 367
 368         @Override
 369         public boolean hasNext() {
 370             return !next.equals(l);
 371         }
 372
 373         @Override
 374         public Resource next() {
 375             prev = next;
 376             try {
 377                 next = OrderedSetUtils.next(g, l, next);
 378             } catch (DatabaseException e) {
 379                 throw new RuntimeDatabaseException(e);
 380             }
 381             ++index;
 382             direction = true;
 383             return prev;
 384         }
 385
 386         @Override
 387         public void remove() {
 388             try {
 389                 WriteGraph wg = getWriteGraph();
 390                 if(direction) {
 391                     OrderedSetUtils.remove(wg, l, prev);
 392                     prev = OrderedSetUtils.prev(wg, l, next);
 393                 }
 394                 else {
 395                     OrderedSetUtils.remove(wg, l, next);
 396                     next = OrderedSetUtils.next(wg, l, prev);
 397                 }
 398             } catch (DatabaseException e) {
 399                 throw new RuntimeDatabaseException(e);
 400             }
 401         }
 402
 403         @Override
 404         public void add(Resource e) {
 405             try {
 406                 WriteGraph wg = getWriteGraph();
 407                 wg.denyStatement(prev, l, next);
 408                 wg.claim(prev, l, e);
 409                 wg.claim(e, l, next);
 410                 prev = e;
 411             } catch (DatabaseException ex) {
 412                 throw new RuntimeDatabaseException(ex);
 413             }
 414         }
 415
 416         @Override
 417         public boolean hasPrevious() {
 418             return !prev.equals(l);
 419         }
 420
 421         @Override
 422         public int nextIndex() {
 423             return index;
 424         }
 425
 426         @Override
 427         public Resource previous() {
 428             try {
 429                 next = prev;
 430                 prev = OrderedSetUtils.prev(g, l, prev);
 431                 --index;
 432                 direction = false;
 433                 return next;
 434             } catch (DatabaseException ex) {
 435                 throw new RuntimeDatabaseException(ex);
 436             }
 437         }
 438
 439         @Override
 440         public int previousIndex() {
 441             return index-1;
 442         }
 443
 444         @Override
 445         public void set(Resource e) {
 446             try {
 447                 WriteGraph wg = getWriteGraph();
 448                 if(direction) {
 449                     OrderedSetUtils.replace(wg, l, prev, e);
 450                     prev = e;
 451                 }
 452                 else {
 453                     OrderedSetUtils.replace(wg, l, next, e);
 454                     next = e;
 455                 }
 456             } catch (DatabaseException ex) {
 457                 throw new RuntimeDatabaseException(ex);
 458             }
 459         }
 460
 461     }
 462
 463     public static ListIterator<Resource> iterator(ReadGraph g, Resource l) throws DatabaseException {
 464         return new OrderedSetIterator(g, l);
 465     }
 466
 467     public static boolean set(WriteGraph g, Resource l, Iterable<Resource> els) throws DatabaseException {
 468
 469         // Compute delta
 470         Set<Pair<Resource,Resource>> removed = new HashSet<Pair<Resource,Resource>>();
 471         Collection<Pair<Resource,Resource>> added = new ArrayList<Pair<Resource,Resource>>();
 472         Resource cur = l;
 473         do {
 474             Resource temp = next(g, l, cur);
 475             removed.add(new Pair<Resource,Resource>(cur, temp));
 476             cur = temp;
 477         } while(!cur.equals(l));
 478
 479         cur = l;
 480         for(Resource temp : els) {
 481             Pair<Resource,Resource> pair = new Pair<Resource, Resource>(cur, temp);
 482             if(!removed.remove(pair))
 483                 added.add(pair);
 484             cur = temp;
 485         }
 486
 487         {
 488             Pair<Resource,Resource> pair = new Pair<Resource, Resource>(cur, l);
 489             if(!removed.remove(pair))
 490                 added.add(pair);
 491         }
 492
 493         // Apply
 494         if(added.isEmpty() && removed.isEmpty())
 495                 return false;
 496         for(Pair<Resource,Resource> pair : removed)
 497             g.denyStatement(pair.first, l, pair.second);
 498         for(Pair<Resource,Resource> pair : added)
 499             g.claim(pair.first, l, pair.second);
 500         return true;
 501     }
 502
 503     /**
 504      * Retrieves the owner list the specified list element
 505      *
 506      * @param g
 507      * @param el a possible element of a list of the specified type
 508      * @param listBaseRelation a base relation of the list to look for
 509      * @return
 510      */
 511     public static Resource getSingleOwnerList(ReadGraph g, Resource el, Resource listBaseRelation) throws DatabaseException {
 512         Collection<Resource> result = getOwnerLists(g, el, listBaseRelation);
 513         if (result.size() != 1)
 514             throw new ValidationException(NameUtils.getSafeName(g, el) + " is part of " + result.size() + " lists of base type " + NameUtils.getSafeName(g, listBaseRelation) + ", expected only one list.");
 515         return result.iterator().next();
 516     }
 517
 518     public static Resource getSingleOwnerList(ReadGraph g, Resource el) throws DatabaseException {
 519         Layer0 l0 = Layer0.getInstance(g);
 520         Collection<Resource> result = getOwnerLists(g, el, l0.OrderedSet);
 521         if (result.size() != 1)
 522             throw new ValidationException(NameUtils.getSafeName(g, el) + " is part of " + result.size() + " lists of base type L0.OrderedSet, expected only one list.");
 523         return result.iterator().next();
 524     }
 525
 526     public static Collection<Resource> getSubjects(ReadGraph g, Resource object) throws DatabaseException {
 527         Collection<Resource> result = new ArrayList<Resource>(1);
 528         Layer0 l0 = Layer0.getInstance(g);
 529         for(Resource pred : g.getPredicates(object)) {
 530             if(g.isInstanceOf(pred, l0.OrderedSet) && !pred.equals(object))
 531                 result.add(pred);
 532         }
 533         return result;
 534     }
 535
 536     private static void forSubjects(ReadGraph g, Resource object, DbFunction<Resource, Boolean> consumer) throws DatabaseException {
 537         for (Resource pred : g.getPredicates(object)) {
 538             if (!pred.equals(object))
 539                 if (!consumer.apply(pred))
 540                     break;
 541         }
 542     }
 543
 544     /**
 545      * Retrieves the owner list the specified list element
 546      *
 547      * @param g
 548      * @param el a possible element of a list of the specified type
 549      * @param listBaseRelation a base relation of the list to look for
 550      * @return
 551      */
 552     public static Collection<Resource> getOwnerLists(ReadGraph g, Resource el, Resource listBaseRelation) throws DatabaseException {
 553         Collection<Resource> result = null;
 554         Collection<Resource> rs = getSubjects(g, el);
 555         for (Resource r : rs) {
 556             if (g.isInstanceOf(r, listBaseRelation)) {
 557                 if (result == null)
 558                     result = new ArrayList<Resource>(2);
 559                 result.add(r);
 560             }
 561         }
 562         if (result == null)
 563             result = Collections.emptyList();
 564         return result;
 565     }
 566
 567     private static class PossibleOwnerList implements DbFunction<Resource, Boolean> {
 568         private ReadGraph graph;
 569         private final Resource listBaseRelation;
 570         public Layer0 L0;
 571         public Resource result;
 572
 573         PossibleOwnerList(ReadGraph graph, Resource listBaseRelation) {
 574             this.graph = graph;
 575             this.listBaseRelation = listBaseRelation;
 576             this.L0 = Layer0.getInstance(graph);
 577         }
 578
 579         @Override
 580         public Boolean apply(Resource t) throws DatabaseException {
 581             Set<Resource> types = graph.getTypes(t);
 582             if (types.contains(L0.OrderedSet) && types.contains(listBaseRelation)) {
 583                 if (result != null) {
 584                     result = null;
 585                     return false;
 586                 }
 587                 result = t;
 588             }
 589             return true;
 590         }
 591     }
 592
 593     /**
 594      * Retrieves a possible single owner list the specified list element
 595      *
 596      * @param g
 597      * @param el
 598      *            a possible element of a list of the specified type
 599      * @param listBaseRelation
 600      *            a base relation of the list to look for
 601      * @return <code>null</code> if there is zero or more than one owner lists
 602      *         with specified base relation
 603      */
 604     public static Resource getPossibleOwnerList(ReadGraph g, Resource el, Resource listBaseRelation) throws DatabaseException {
 605         PossibleOwnerList proc = new PossibleOwnerList(g, listBaseRelation);
 606         forSubjects(g, el, proc);
 607         return proc.result;
 608     }
 609
 610 }