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

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