bundles/org.simantics.layer0.utils/src/org/simantics/layer0/utils/binaryPredicates/TransitiveClosure.java

   1 /*******************************************************************************\r
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
   3  * in Industry THTH ry.\r
   4  * All rights reserved. This program and the accompanying materials\r
   5  * are made available under the terms of the Eclipse Public License v1.0\r
   6  * which accompanies this distribution, and is available at\r
   7  * http://www.eclipse.org/legal/epl-v10.html\r
   8  *\r
   9  * Contributors:\r
  10  *     VTT Technical Research Centre of Finland - initial API and implementation\r
  11  *******************************************************************************/\r
  12 package org.simantics.layer0.utils.binaryPredicates;\r
  13 \r
  14 import java.util.ArrayDeque;\r
  15 import java.util.Collection;\r
  16 import java.util.Deque;\r
  17 import java.util.HashSet;\r
  18 import java.util.Set;\r
  19 \r
  20 import org.simantics.db.Resource;\r
  21 import org.simantics.db.ReadGraph;\r
  22 import org.simantics.db.WriteGraph;\r
  23 import org.simantics.db.exception.DatabaseException;\r
  24 import org.simantics.utils.datastructures.Pair;\r
  25 \r
  26 public class TransitiveClosure extends BinaryPredicate {\r
  27         IBinaryPredicate predicate;\r
  28         \r
  29 \r
  30         public TransitiveClosure(IBinaryPredicate predicate) {\r
  31                 this.predicate = predicate;\r
  32         }\r
  33 \r
  34         @Override\r
  35         public void add(WriteGraph g, Resource subject, Resource object) throws DatabaseException {\r
  36                 if(!has(g, subject, object))\r
  37                         predicate.add(g, subject, object);\r
  38         }\r
  39 \r
  40         @Override\r
  41         public Collection<Resource> getObjects(ReadGraph g, Resource subject) throws DatabaseException {\r
  42                 Deque<Resource> unprocessed = new ArrayDeque<Resource>();\r
  43                 unprocessed.add(subject);\r
  44                 Set<Resource> result = new HashSet<Resource>();\r
  45                 while(!unprocessed.isEmpty())\r
  46                         for(Resource r : predicate.getObjects(g, unprocessed.pop()))\r
  47                                 if(result.add(r))\r
  48                                         unprocessed.push(r);\r
  49                 return result;\r
  50         }\r
  51 \r
  52         @Override\r
  53         public Collection<Pair<Resource, Resource>> getStatements(ReadGraph g) {\r
  54                 // TODO Auto-generated method stub\r
  55                 return null;\r
  56         }\r
  57 \r
  58         @Override\r
  59         public Collection<Resource> getSubjects(ReadGraph g, Resource object) throws DatabaseException {\r
  60                 Deque<Resource> unprocessed = new ArrayDeque<Resource>();\r
  61                 unprocessed.add(object);\r
  62                 Set<Resource> result = new HashSet<Resource>();\r
  63                 while(!unprocessed.isEmpty())\r
  64                         for(Resource r : predicate.getSubjects(g, unprocessed.pop()))\r
  65                                 if(result.add(r))\r
  66                                         unprocessed.push(r);\r
  67                 return result;\r
  68         }\r
  69 \r
  70         @Override\r
  71         public boolean has(ReadGraph g, Resource subject, Resource object) throws DatabaseException {\r
  72                 Deque<Resource> unprocessed = new ArrayDeque<Resource>();\r
  73                 unprocessed.add(subject);\r
  74                 Set<Resource> objects = new HashSet<Resource>();\r
  75                 while(!unprocessed.isEmpty())\r
  76                         for(Resource r : predicate.getObjects(g, unprocessed.pop()))\r
  77                                 if(r.equals(object))\r
  78                                         return true;\r
  79                                 else if(objects.add(r))\r
  80                                         unprocessed.push(r);\r
  81                 return false;\r
  82         }\r
  83 \r
  84         @Override\r
  85         public void remove(WriteGraph g, Resource subject, Resource object) {\r
  86                 throw new UnsupportedOperationException();\r
  87         }\r
  88 \r
  89         @Override\r
  90         public boolean supportsAdditions() {\r
  91                 return predicate.supportsAdditions();\r
  92         }\r
  93 \r
  94         @Override\r
  95         public boolean supportsGetObjects() {\r
  96                 return predicate.supportsGetObjects();\r
  97         }\r
  98 \r
  99         @Override\r
 100         public boolean supportsGetStatements() {\r
 101                 return false; // FIXME: just unimplemented\r
 102         }\r
 103 \r
 104         @Override\r
 105         public boolean supportsGetSubjects() {\r
 106                 return predicate.supportsGetSubjects();\r
 107         }\r
 108 \r
 109         @Override\r
 110         public boolean supportsRemovals() {\r
 111                 return false;\r
 112         }\r
 113 \r
 114         @Override\r
 115         public int hashCode() {\r
 116                 final int prime = 31;\r
 117                 int result = 1;\r
 118                 result = prime * result\r
 119                                 + ((predicate == null) ? 0 : predicate.hashCode());\r
 120                 return result;\r
 121         }\r
 122 \r
 123         @Override\r
 124         public boolean equals(Object obj) {\r
 125                 if (this == obj)\r
 126                         return true;\r
 127                 if (obj == null)\r
 128                         return false;\r
 129                 if (getClass() != obj.getClass())\r
 130                         return false;\r
 131                 TransitiveClosure other = (TransitiveClosure) obj;\r
 132                 if (predicate == null) {\r
 133                         if (other.predicate != null)\r
 134                                 return false;\r
 135                 } else if (!predicate.equals(other.predicate))\r
 136                         return false;\r
 137                 return true;\r
 138         }\r
 139         \r
 140 }\r