1
2
3
4
5
6
7
8
9
10
11
12
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
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
83
84
85 this.model = model;
86
87
88 this.propertyMask = new BitSet(PROPERTY_MASK_SIZE);
89 this.typeMask = new BitSet(TYPE_MASK_SIZE);
90
91
92 this.data = new Value[4 * stmts.size()];
93
94 int index = 0;
95 for (final Statement stmt : stmts) {
96
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
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
119 if (this.data.length == 0) {
120 return 0;
121 }
122
123
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
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
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
168 final Value[] prefix = prefixFor(subj, pred, obj);
169
170
171
172
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
181 final int startIndex = indexOf(prefix, 0, this.data.length);
182 if (startIndex < 0) {
183 return Collections.emptyIterator();
184 }
185
186
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();
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
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
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 }