1   /*
2    * RDFpro - An extensible tool for building stream-oriented RDF processing libraries.
3    * 
4    * Written in 2015 by Francesco Corcoglioniti with support by Alessio Palmero Aprosio and Marco
5    * Rospocher. Contact info on http://rdfpro.fbk.eu/
6    * 
7    * To the extent possible under law, the authors have dedicated all copyright and related and
8    * neighboring rights to this software to the public domain worldwide. This software is
9    * distributed without any warranty.
10   * 
11   * You should have received a copy of the CC0 Public Domain Dedication along with this software.
12   * If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
13   */
14  package eu.fbk.rdfpro.util;
15  
16  import java.util.BitSet;
17  import java.util.Collection;
18  import java.util.Collections;
19  import java.util.Iterator;
20  import java.util.NoSuchElementException;
21  import java.util.Objects;
22  import java.util.Set;
23  
24  import javax.annotation.Nullable;
25  
26  import com.google.common.collect.Iterators;
27  
28  import org.openrdf.model.Namespace;
29  import org.openrdf.model.Resource;
30  import org.openrdf.model.Statement;
31  import org.openrdf.model.URI;
32  import org.openrdf.model.Value;
33  import org.openrdf.model.vocabulary.RDF;
34  
35  final class QuadModelSubModel extends QuadModel {
36  
37      private static final long serialVersionUID = 1;
38  
39      private static final int PROPERTY_MASK_SIZE = 8 * 8 * 1024 - 1;
40  
41      private static final int TYPE_MASK_SIZE = 8 * 8 * 1024 - 1;
42  
43      private static final int TYPE_HASH = hash(RDF.TYPE);
44  
45      private static final Sorting.ArrayComparator<Value> VALUE_ARRAY_COMPARATOR //
46      = new Sorting.ArrayComparator<Value>() {
47  
48          @Override
49          public int size() {
50              return 4;
51          }
52  
53          @Override
54          public int compare(final Value[] leftArray, final int leftIndex, final Value[] rightArray,
55                  final int rightIndex) {
56              // POSC order
57              int result = hash(leftArray[leftIndex + 1]) - hash(rightArray[rightIndex + 1]);
58              if (result == 0) {
59                  result = hash(leftArray[leftIndex + 2]) - hash(rightArray[rightIndex + 2]);
60                  if (result == 0) {
61                      result = hash(leftArray[leftIndex]) - hash(rightArray[rightIndex]);
62                      if (result == 0) {
63                          result = hash(leftArray[leftIndex + 3]) - hash(rightArray[rightIndex + 3]);
64                      }
65                  }
66              }
67              return result;
68          }
69  
70      };
71  
72      private final QuadModel model;
73  
74      private final BitSet propertyMask;
75  
76      private final BitSet typeMask;
77  
78      private final Value[] data;
79  
80      QuadModelSubModel(final QuadModel model, final Collection<Statement> stmts) {
81  
82          // stmts must not contain duplicates!
83  
84          // Store model and size parameters
85          this.model = model;
86  
87          // Initialize bitmasks for properties and types
88          this.propertyMask = new BitSet(PROPERTY_MASK_SIZE);
89          this.typeMask = new BitSet(TYPE_MASK_SIZE);
90  
91          // Initialize storage for delta statements
92          this.data = new Value[4 * stmts.size()];
93  
94          int index = 0;
95          for (final Statement stmt : stmts) {
96              // Store statement
97              this.data[index] = stmt.getSubject();
98              this.data[index + 1] = stmt.getPredicate();
99              this.data[index + 2] = stmt.getObject();
100             this.data[index + 3] = stmt.getContext();
101             index += 4;
102 
103             // Update masks
104             final int predHash = hash(stmt.getPredicate());
105             this.propertyMask.set(predHash % PROPERTY_MASK_SIZE);
106             if (predHash == TYPE_HASH) {
107                 final int objHash = hash(stmt.getObject());
108                 this.typeMask.set(objHash % TYPE_MASK_SIZE);
109             }
110         }
111         Sorting.sort(VALUE_ARRAY_COMPARATOR, this.data);
112     }
113 
114     @Override
115     protected int doSizeEstimate(@Nullable final Resource subj, @Nullable final URI pred,
116             @Nullable final Value obj, @Nullable final Resource ctx) {
117 
118         // Return 0 if view is empty
119         if (this.data.length == 0) {
120             return 0;
121         }
122 
123         // Check masks, if possible
124         if (pred != null) {
125             final int predHash = hash(pred);
126             if (!this.propertyMask.get(predHash % PROPERTY_MASK_SIZE)) {
127                 return 0;
128             }
129             if (obj != null && predHash == TYPE_HASH) {
130                 final int objHash = hash(obj);
131                 if (!this.typeMask.get(objHash % TYPE_MASK_SIZE)) {
132                     return 0;
133                 }
134             }
135         }
136 
137         // Otherwise, simply delegate to the wrapped model, limiting the result to this size
138         return Math.min(this.data.length / 4, this.model.sizeEstimate(subj, pred, obj,
139                 ctx == null ? CTX_ANY : new Resource[] { ctx }));
140     }
141 
142     @Override
143     protected Iterator<Statement> doIterator(@Nullable final Resource subj,
144             @Nullable final URI pred, @Nullable final Value obj, final Resource[] ctxs) {
145 
146         // In case of a wildcard <?s ?p ?o ?c> returns all the statements in the delta
147         if (subj == null && pred == null && obj == null && ctxs.length == 0) {
148             return new Iterator<Statement>() {
149 
150                 private int offset = 0;
151 
152                 @Override
153                 public boolean hasNext() {
154                     return this.offset < QuadModelSubModel.this.data.length;
155                 }
156 
157                 @Override
158                 public Statement next() {
159                     final Statement stmt = statementAt(this.offset);
160                     this.offset += 4;
161                     return stmt;
162                 }
163 
164             };
165         }
166 
167         // Compute prefix
168         final Value[] prefix = prefixFor(subj, pred, obj);
169 
170         // Delegate to model without filtering (thus going towards a naive approach) in case
171         // there is no way to exploit the order of quads and their number in the model is less
172         // than the delta size
173         if (prefix.length == 0) {
174             final int estimate = this.model.sizeEstimate(subj, pred, obj, ctxs);
175             if (estimate < this.data.length / 4) {
176                 return this.model.iterator(subj, pred, obj, ctxs);
177             }
178         }
179 
180         // Compute start index in the value array
181         final int startIndex = indexOf(prefix, 0, this.data.length);
182         if (startIndex < 0) {
183             return Collections.emptyIterator();
184         }
185 
186         // Otherwise, iterate starting at computed index, stopping when prefix does not match
187         return new Iterator<Statement>() {
188 
189             private int offset = startIndex;
190 
191             private Statement next = null;
192 
193             @Override
194             public boolean hasNext() {
195                 if (this.next != null) {
196                     return true;
197                 }
198                 final Value[] data = QuadModelSubModel.this.data;
199                 while (this.offset < data.length) {
200                     if (prefixCompare(prefix, this.offset) != 0) {
201                         this.offset = data.length;
202                         return false;
203                     }
204                     if ((subj == null || subj.equals(data[this.offset]))
205                             && (pred == null || pred.equals(data[this.offset + 1]))
206                             && (obj == null || obj.equals(data[this.offset + 2]))) {
207                         if (ctxs.length == 0) {
208                             this.next = statementAt(this.offset);
209                             this.offset += 4;
210                             return true;
211                         }
212                         final Resource c = (Resource) data[this.offset + 3];
213                         for (final Resource ctx : ctxs) {
214                             if (Objects.equals(c, ctx)) {
215                                 this.next = statementAt(this.offset);
216                                 this.offset += 4;
217                                 return true;
218                             }
219                         }
220                     }
221                     this.offset += 4;
222                 }
223                 return false;
224             }
225 
226             @Override
227             public Statement next() {
228                 if (!hasNext()) {
229                     throw new NoSuchElementException();
230                 }
231                 final Statement stmt = this.next;
232                 this.next = null;
233                 return stmt;
234             }
235 
236         };
237     }
238 
239     @Override
240     protected Set<Namespace> doGetNamespaces() {
241         return this.model.getNamespaces();
242     }
243 
244     @Override
245     protected Namespace doGetNamespace(final String prefix) {
246         return this.model.getNamespace(prefix);
247     }
248 
249     @Override
250     protected Namespace doSetNamespace(final String prefix, final String name) {
251         throw new UnsupportedOperationException();
252     }
253 
254     @Override
255     protected int doSize(final Resource subj, final URI pred, final Value obj,
256             final Resource[] ctxs) {
257         if (subj == null && pred == null && obj == null && ctxs.length == 0) {
258             return this.data.length / 4;
259         } else if (sizeEstimate(subj, pred, obj, ctxs) == 0) {
260             return 0;
261         } else {
262             return Iterators.size(iterator(subj, pred, obj, ctxs));
263         }
264     }
265 
266     @Override
267     protected boolean doAdd(final Resource subj, final URI pred, final Value obj,
268             final Resource[] ctxs) {
269         throw new UnsupportedOperationException();
270     }
271 
272     @Override
273     protected boolean doRemove(final Resource subj, final URI pred, final Value obj,
274             final Resource[] ctxs) {
275         throw new UnsupportedOperationException(); // not invoked
276     }
277 
278     @Override
279     protected Value doNormalize(final Value value) {
280         return this.model.normalize(value);
281     }
282 
283     private Value[] prefixFor(@Nullable final Resource subj, @Nullable final URI pred,
284             @Nullable final Value obj) {
285 
286         // Compute prefix length
287         int prefixLength = 0;
288         if (pred != null) {
289             ++prefixLength;
290             if (obj != null) {
291                 ++prefixLength;
292                 if (subj != null) {
293                     ++prefixLength;
294                 }
295             }
296         }
297 
298         // Compute prefix
299         final Value[] prefix = new Value[prefixLength];
300         if (prefixLength >= 1) {
301             prefix[0] = pred;
302         }
303         if (prefixLength >= 2) {
304             prefix[1] = obj;
305         }
306         if (prefixLength >= 3) {
307             prefix[2] = subj;
308         }
309         return prefix;
310     }
311 
312     private int prefixCompare(final Value[] prefix, final int offset) {
313         int result = 0;
314         if (prefix.length >= 1) {
315             result = hash(this.data[offset + 1]) - hash(prefix[0]);
316             if (result == 0 && prefix.length >= 2) {
317                 result = hash(this.data[offset + 2]) - hash(prefix[1]);
318                 if (result == 0 && prefix.length >= 3) {
319                     result = hash(this.data[offset]) - hash(prefix[2]);
320                 }
321             }
322         }
323         return result;
324     }
325 
326     private Statement statementAt(final int offset) {
327         final Resource subj = (Resource) QuadModelSubModel.this.data[offset];
328         final URI pred = (URI) QuadModelSubModel.this.data[offset + 1];
329         final Value obj = QuadModelSubModel.this.data[offset + 2];
330         final Resource ctx = (Resource) QuadModelSubModel.this.data[offset + 3];
331         return ctx == null ? Statements.VALUE_FACTORY.createStatement(subj, pred, obj)
332                 : Statements.VALUE_FACTORY.createStatement(subj, pred, obj, ctx);
333     }
334 
335     private int indexOf(final Value[] prefix, final int lo, final int hi) {
336         if (lo >= hi) {
337             return -1;
338         }
339         if (prefix.length == 0) {
340             return lo;
341         }
342         final int mid = (lo >>> 2) + (hi >>> 2) >>> 1 << 2;
343         final int c = prefixCompare(prefix, mid);
344         if (c < 0) {
345             return indexOf(prefix, mid + 4, hi);
346         } else if (c > 0) {
347             return indexOf(prefix, lo, mid);
348         } else if (mid > lo) {
349             final int index = indexOf(prefix, lo, mid);
350             return index >= 0 ? index : mid;
351         }
352         return mid;
353     }
354 
355     private static int hash(@Nullable final Value value) {
356         return value == null ? 0 : value.hashCode() & 0x7FFFFFFF;
357     }
358 
359 }