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      * Reorders elements with a minimum number of writes. The set of elements must remain the same.
 225      */
 226     public static void reorder(WriteGraph g, Resource l, Iterable<Resource> order) throws DatabaseException {
 227         Resource newPrev = l;
 228         for (Resource r : order) {
 229             Resource prev = OrderedSetUtils.prev(g, l, r);
 230             if (!prev.equals(newPrev)) {
 231                 g.deny(prev, l, r);
 232                 g.claim(newPrev, l, r);
 233             }
 234             newPrev = r;
 235         }
 236         Resource newLast = newPrev;
 237         Resource last = OrderedSetUtils.prev(g, l, l);
 238         if (!last.equals(newLast)) {
 239             g.deny(last, l, l);
 240             g.claim(newLast, l, l);
 241         }
 242     }
 243
 244     /**
 245      * Converts ordered set into a list.
 246      */
 247     public static List<Resource> toList(ReadGraph g, Resource l) throws DatabaseException {
 248         ArrayList<Resource> ret = new ArrayList<Resource>();
 249         Resource cur = l;
 250         while(true) {
 251             cur = next(g, l, cur);
 252             if(cur.equals(l))
 253                 return ret;
 254             ret.add(cur);
 255         }
 256     }
 257
 258     /**
 259      * Creates an empty ordered set.
 260      */
 261     public static Resource create(WriteOnlyGraph g, Resource type) throws DatabaseException {
 262         Layer0 l0 = g.getService(Layer0.class);
 263         Resource l = g.newResource();
 264         g.claim(l, l0.InstanceOf, null, type);
 265         g.claim(l, l0.SubrelationOf, null, l0.HasNext);
 266         Resource invL = g.newResource();
 267         g.claim(invL, l0.SubrelationOf, null, l0.HasPrevious);
 268         g.claim(l, l0.InverseOf, l0.InverseOf, invL);
 269         g.claim(l, l, invL, l);
 270         return l;
 271     }
 272
 273     /**
 274      * Creates an ordered set containing the given elements.
 275      * It is assumed that the elements do not contain duplicates.
 276      */
 277     @Deprecated
 278     public static Resource create(WriteOnlyGraph g, Resource type, Iterable<Resource> c) throws DatabaseException {
 279         Layer0 l0 = g.getService(Layer0.class);
 280         Resource l = g.newResource();
 281         g.claim(l, l0.InstanceOf, null, type);
 282         g.claim(l, l0.SubrelationOf, null, l0.HasNext);
 283         Resource invL = g.newResource();
 284         g.claim(invL, l0.SubrelationOf, null, l0.HasPrevious);
 285         g.claim(l, l0.InverseOf, l0.InverseOf, invL);
 286         Resource cur = l;
 287         for(Resource r : c) {
 288             g.claim(cur, l, invL, r);
 289             cur = r;
 290         }
 291         g.claim(cur, l, invL, l);
 292         return l;
 293     }
 294
 295     public static Resource create(WriteOnlyGraph g, Resource type, String name, Iterable<Resource> c) throws DatabaseException {
 296         return createExisting(g, g.newResource(), type, name, c);
 297     }
 298
 299     public static Resource createExisting(WriteOnlyGraph g, Resource l, Resource type, String name, Iterable<Resource> c) throws DatabaseException {
 300         Layer0 l0 = g.getService(Layer0.class);
 301         g.claim(l, l0.InstanceOf, null, type);
 302         g.claim(l, l0.SubrelationOf, null, l0.HasNext);
 303         g.addLiteral(l, l0.HasName, l0.NameOf, l0.String, name, Bindings.STRING);
 304         Resource invL = g.newResource();
 305         g.claim(invL, l0.SubrelationOf, null, l0.HasPrevious);
 306         g.addLiteral(invL, l0.HasName, l0.NameOf, l0.String, "Inverse", Bindings.STRING);
 307         g.claim(l, l0.InverseOf, l0.InverseOf, invL);
 308         g.claim(l, l0.ConsistsOf, l0.PartOf, invL);
 309         Resource cur = l;
 310         for(Resource r : c) {
 311             g.claim(cur, l, invL, r);
 312             cur = r;
 313         }
 314         g.claim(cur, l, invL, l);
 315         return l;
 316     }
 317
 318     public static Resource create(WriteOnlyGraph g, Resource type, Resource ... c) throws DatabaseException {
 319         Layer0 l0 = g.getService(Layer0.class);
 320         Resource l = g.newResource();
 321         g.claim(l, l0.InstanceOf, null, type);
 322         g.claim(l, l0.SubrelationOf, null, l0.HasNext);
 323         Resource invL = g.newResource();
 324         g.claim(invL, l0.SubrelationOf, null, l0.HasPrevious);
 325         g.claim(l, l0.InverseOf, l0.InverseOf, invL);
 326         Resource cur = l;
 327         for(Resource r : c) {
 328             g.claim(cur, l, invL, r);
 329             cur = r;
 330         }
 331         g.claim(cur, l, invL, l);
 332         return l;
 333     }
 334
 335     public static Resource createExisting(WriteGraph g, Resource l, Resource ... c) throws DatabaseException {
 336         Layer0 l0 = Layer0.getInstance(g);
 337         g.claim(l, l0.SubrelationOf, null, l0.HasNext);
 338         Resource invL = g.newResource();
 339         g.claim(invL, l0.SubrelationOf, null, l0.HasPrevious);
 340         g.claim(l, l0.InverseOf, l0.InverseOf, invL);
 341         Resource cur = l;
 342         for(Resource r : c) {
 343             g.claim(cur, l, invL, r);
 344             cur = r;
 345         }
 346         g.claim(cur, l, invL, l);
 347         return l;
 348     }
 349
 350 //    public static Resource create(GraphWriter graph, Resource type, Iterable<Resource> c) throws DatabaseException {
 351 //        ReadGraph g = w.getGraph();
 352 //        Builtins b = g.getBuiltins();
 353 //        Resource l = w.create(type).get();
 354 //        w.let(b.SubrelationOf, b.IsRelatedTo);
 355 //        w.createInverse(l).let(b.SubrelationOf, g.getInverse(b.IsRelatedTo));
 356 //
 357 //        Resource cur = l;
 358 //        for(Resource r : c) {
 359 //            w.stat(cur, l, r);
 360 //            cur = r;
 361 //        }
 362 //        w.stat(cur, l, l);
 363 //        return l;
 364 //    }
 365
 366     public static class OrderedSetIterator implements ListIterator<Resource> {
 367
 368         ReadGraph g;
 369         Resource l;
 370         Resource prev;
 371         Resource next;
 372         int index;
 373         boolean direction;
 374
 375         WriteGraph getWriteGraph() {
 376             if (!(g instanceof WriteGraph))
 377                 throw new UnsupportedOperationException("");
 378             return (WriteGraph) g;
 379         }
 380
 381         public OrderedSetIterator(ReadGraph g, Resource l) throws DatabaseException {
 382             this.g = g;
 383             this.l = l;
 384             this.prev = l;
 385             this.next = OrderedSetUtils.next(g, l, l);
 386             this.index = 0;
 387         }
 388
 389         @Override
 390         public boolean hasNext() {
 391             return !next.equals(l);
 392         }
 393
 394         @Override
 395         public Resource next() {
 396             prev = next;
 397             try {
 398                 next = OrderedSetUtils.next(g, l, next);
 399             } catch (DatabaseException e) {
 400                 throw new RuntimeDatabaseException(e);
 401             }
 402             ++index;
 403             direction = true;
 404             return prev;
 405         }
 406
 407         @Override
 408         public void remove() {
 409             try {
 410                 WriteGraph wg = getWriteGraph();
 411                 if(direction) {
 412                     OrderedSetUtils.remove(wg, l, prev);
 413                     prev = OrderedSetUtils.prev(wg, l, next);
 414                 }
 415                 else {
 416                     OrderedSetUtils.remove(wg, l, next);
 417                     next = OrderedSetUtils.next(wg, l, prev);
 418                 }
 419             } catch (DatabaseException e) {
 420                 throw new RuntimeDatabaseException(e);
 421             }
 422         }
 423
 424         @Override
 425         public void add(Resource e) {
 426             try {
 427                 WriteGraph wg = getWriteGraph();
 428                 wg.denyStatement(prev, l, next);
 429                 wg.claim(prev, l, e);
 430                 wg.claim(e, l, next);
 431                 prev = e;
 432             } catch (DatabaseException ex) {
 433                 throw new RuntimeDatabaseException(ex);
 434             }
 435         }
 436
 437         @Override
 438         public boolean hasPrevious() {
 439             return !prev.equals(l);
 440         }
 441
 442         @Override
 443         public int nextIndex() {
 444             return index;
 445         }
 446
 447         @Override
 448         public Resource previous() {
 449             try {
 450                 next = prev;
 451                 prev = OrderedSetUtils.prev(g, l, prev);
 452                 --index;
 453                 direction = false;
 454                 return next;
 455             } catch (DatabaseException ex) {
 456                 throw new RuntimeDatabaseException(ex);
 457             }
 458         }
 459
 460         @Override
 461         public int previousIndex() {
 462             return index-1;
 463         }
 464
 465         @Override
 466         public void set(Resource e) {
 467             try {
 468                 WriteGraph wg = getWriteGraph();
 469                 if(direction) {
 470                     OrderedSetUtils.replace(wg, l, prev, e);
 471                     prev = e;
 472                 }
 473                 else {
 474                     OrderedSetUtils.replace(wg, l, next, e);
 475                     next = e;
 476                 }
 477             } catch (DatabaseException ex) {
 478                 throw new RuntimeDatabaseException(ex);
 479             }
 480         }
 481
 482     }
 483
 484     public static ListIterator<Resource> iterator(ReadGraph g, Resource l) throws DatabaseException {
 485         return new OrderedSetIterator(g, l);
 486     }
 487
 488     public static boolean set(WriteGraph g, Resource l, Iterable<Resource> els) throws DatabaseException {
 489
 490         // Compute delta
 491         Set<Pair<Resource,Resource>> removed = new HashSet<Pair<Resource,Resource>>();
 492         Collection<Pair<Resource,Resource>> added = new ArrayList<Pair<Resource,Resource>>();
 493         Resource cur = l;
 494         do {
 495             Resource temp = next(g, l, cur);
 496             removed.add(new Pair<Resource,Resource>(cur, temp));
 497             cur = temp;
 498         } while(!cur.equals(l));
 499
 500         cur = l;
 501         for(Resource temp : els) {
 502             Pair<Resource,Resource> pair = new Pair<Resource, Resource>(cur, temp);
 503             if(!removed.remove(pair))
 504                 added.add(pair);
 505             cur = temp;
 506         }
 507
 508         {
 509             Pair<Resource,Resource> pair = new Pair<Resource, Resource>(cur, l);
 510             if(!removed.remove(pair))
 511                 added.add(pair);
 512         }
 513
 514         // Apply
 515         if(added.isEmpty() && removed.isEmpty())
 516                 return false;
 517         for(Pair<Resource,Resource> pair : removed)
 518             g.denyStatement(pair.first, l, pair.second);
 519         for(Pair<Resource,Resource> pair : added)
 520             g.claim(pair.first, l, pair.second);
 521         return true;
 522     }
 523
 524     /**
 525      * Retrieves the owner list the specified list element
 526      *
 527      * @param g
 528      * @param el a possible element of a list of the specified type
 529      * @param listBaseRelation a base relation of the list to look for
 530      * @return
 531      */
 532     public static Resource getSingleOwnerList(ReadGraph g, Resource el, Resource listBaseRelation) throws DatabaseException {
 533         Collection<Resource> result = getOwnerLists(g, el, listBaseRelation);
 534         if (result.size() != 1)
 535             throw new ValidationException(NameUtils.getSafeName(g, el) + " is part of " + result.size() + " lists of base type " + NameUtils.getSafeName(g, listBaseRelation) + ", expected only one list.");
 536         return result.iterator().next();
 537     }
 538
 539     public static Resource getSingleOwnerList(ReadGraph g, Resource el) throws DatabaseException {
 540         Layer0 l0 = Layer0.getInstance(g);
 541         Collection<Resource> result = getOwnerLists(g, el, l0.OrderedSet);
 542         if (result.size() != 1)
 543             throw new ValidationException(NameUtils.getSafeName(g, el) + " is part of " + result.size() + " lists of base type L0.OrderedSet, expected only one list.");
 544         return result.iterator().next();
 545     }
 546
 547     public static Collection<Resource> getSubjects(ReadGraph g, Resource object) throws DatabaseException {
 548         Collection<Resource> result = new ArrayList<Resource>(1);
 549         Layer0 l0 = Layer0.getInstance(g);
 550         for(Resource pred : g.getPredicates(object)) {
 551             if(g.isInstanceOf(pred, l0.OrderedSet) && !pred.equals(object))
 552                 result.add(pred);
 553         }
 554         return result;
 555     }
 556
 557     private static void forSubjects(ReadGraph g, Resource object, DbFunction<Resource, Boolean> consumer) throws DatabaseException {
 558         for (Resource pred : g.getPredicates(object)) {
 559             if (!pred.equals(object))
 560                 if (!consumer.apply(pred))
 561                     break;
 562         }
 563     }
 564
 565     /**
 566      * Retrieves the owner list the specified list element
 567      *
 568      * @param g
 569      * @param el a possible element of a list of the specified type
 570      * @param listBaseRelation a base relation of the list to look for
 571      * @return
 572      */
 573     public static Collection<Resource> getOwnerLists(ReadGraph g, Resource el, Resource listBaseRelation) throws DatabaseException {
 574         Collection<Resource> result = null;
 575         Collection<Resource> rs = getSubjects(g, el);
 576         for (Resource r : rs) {
 577             if (g.isInstanceOf(r, listBaseRelation)) {
 578                 if (result == null)
 579                     result = new ArrayList<Resource>(2);
 580                 result.add(r);
 581             }
 582         }
 583         if (result == null)
 584             result = Collections.emptyList();
 585         return result;
 586     }
 587
 588     private static class PossibleOwnerList implements DbFunction<Resource, Boolean> {
 589         private ReadGraph graph;
 590         private final Resource listBaseRelation;
 591         public Layer0 L0;
 592         public Resource result;
 593
 594         PossibleOwnerList(ReadGraph graph, Resource listBaseRelation) {
 595             this.graph = graph;
 596             this.listBaseRelation = listBaseRelation;
 597             this.L0 = Layer0.getInstance(graph);
 598         }
 599
 600         @Override
 601         public Boolean apply(Resource t) throws DatabaseException {
 602             Set<Resource> types = graph.getTypes(t);
 603             if (types.contains(L0.OrderedSet) && types.contains(listBaseRelation)) {
 604                 if (result != null) {
 605                     result = null;
 606                     return false;
 607                 }
 608                 result = t;
 609             }
 610             return true;
 611         }
 612     }
 613
 614     /**
 615      * Retrieves a possible single owner list the specified list element
 616      *
 617      * @param g
 618      * @param el
 619      *            a possible element of a list of the specified type
 620      * @param listBaseRelation
 621      *            a base relation of the list to look for
 622      * @return <code>null</code> if there is zero or more than one owner lists
 623      *         with specified base relation
 624      */
 625     public static Resource getPossibleOwnerList(ReadGraph g, Resource el, Resource listBaseRelation) throws DatabaseException {
 626         PossibleOwnerList proc = new PossibleOwnerList(g, listBaseRelation);
 627         forSubjects(g, el, proc);
 628         return proc.result;
 629     }
 630
 631 }