1 package eu.fbk.knowledgestore.internal.rdf;
2
3 import java.io.Serializable;
4 import java.util.AbstractList;
5 import java.util.AbstractSet;
6 import java.util.Arrays;
7 import java.util.Iterator;
8 import java.util.List;
9 import java.util.Map;
10 import java.util.NoSuchElementException;
11 import java.util.Set;
12
13 import javax.annotation.Nullable;
14
15 import com.google.common.base.Joiner;
16 import com.google.common.base.Objects;
17 import com.google.common.collect.Iterables;
18 import com.google.common.collect.Iterators;
19 import com.google.common.collect.UnmodifiableIterator;
20
21 import org.openrdf.model.Value;
22 import org.openrdf.query.Binding;
23 import org.openrdf.query.BindingSet;
24 import org.openrdf.query.impl.BindingImpl;
25
26 public abstract class CompactBindingSet implements BindingSet, Serializable {
27
28 private static final long serialVersionUID = 1L;
29
30 private final VariableList variables;
31
32 @Nullable
33 private Set<String> names;
34
35 private int hash;
36
37 CompactBindingSet(final VariableList variableNames) {
38 this.variables = variableNames;
39 this.names = null;
40 this.hash = 0;
41 }
42
43 abstract Value get(int index);
44
45 @Override
46 public final int size() {
47 return getBindingNames().size();
48 }
49
50 @Override
51 public final Iterator<Binding> iterator() {
52 return new BindingIterator(this);
53 }
54
55 @Override
56 public final Set<String> getBindingNames() {
57 if (this.names == null) {
58 int count = 0;
59 final int size = this.variables.size();
60 for (int i = 0; i < size; ++i) {
61 if (get(i) != null) {
62 ++count;
63 }
64 }
65 final String[] array = new String[count];
66 int index = 0;
67 for (int i = 0; i < size; ++i) {
68 if (get(i) != null) {
69 array[index++] = this.variables.get(i);
70 }
71 }
72 this.names = new VariableSet(array);
73 }
74 return this.names;
75 }
76
77 @Override
78 public final boolean hasBinding(final String name) {
79 return get(this.variables.indexOf(name)) != null;
80 }
81
82 @Override
83 @Nullable
84 public final Binding getBinding(final String name) {
85 final Value value = get(this.variables.indexOf(name));
86 return value == null ? null : new BindingImpl(name, value);
87 }
88
89 @Override
90 @Nullable
91 public final Value getValue(final String name) {
92 return get(this.variables.indexOf(name));
93 }
94
95 @Override
96 public final boolean equals(final Object object) {
97 if (object == this) {
98 return true;
99 }
100 if (!(object instanceof BindingSet)) {
101 return false;
102 }
103 final BindingSet other = (BindingSet) object;
104 final int thisSize = this.variables.size();
105 if (other instanceof CompactBindingSet
106 && ((CompactBindingSet) other).variables == this.variables) {
107 final CompactBindingSet bs = (CompactBindingSet) other;
108 for (int i = 0; i < thisSize; ++i) {
109 if (!Objects.equal(get(i), bs.get(i))) {
110 return false;
111 }
112 }
113 } else {
114 final Set<String> thisNames = getBindingNames();
115 final Set<String> otherNames = other.getBindingNames();
116 if (thisNames.size() != otherNames.size()) {
117 return false;
118 }
119 final int size = this.variables.size();
120 for (int i = 0; i < size; ++i) {
121 if (!Objects.equal(get(i), other.getValue(this.variables.get(i)))) {
122 return false;
123 }
124 }
125 }
126 return true;
127 }
128
129
130
131
132 @Override
133 public final int hashCode() {
134 if (this.hash == 0) {
135 int hash = 0;
136 final int size = this.variables.size();
137 for (int i = 0; i < size; ++i) {
138 final Value value = get(i);
139 if (value != null) {
140 hash ^= this.variables.get(i).hashCode() ^ value.hashCode();
141 }
142 }
143 this.hash = hash;
144 }
145 return this.hash;
146 }
147
148
149
150
151
152 @Override
153 public final String toString() {
154 final StringBuilder builder = new StringBuilder(32 * size());
155 builder.append('[');
156 String separator = "";
157 final int size = this.variables.size();
158 for (int i = 0; i < size; ++i) {
159 final Value value = get(i);
160 if (value != null) {
161 final String variable = this.variables.get(i);
162 builder.append(separator);
163 builder.append(variable);
164 builder.append("=");
165 builder.append(value);
166 separator = ";";
167 }
168 }
169 builder.append(']');
170 return builder.toString();
171 }
172
173 public static Builder builder(final Iterable<? extends String> variables) {
174 return new Builder(variables instanceof VariableList ? (VariableList) variables
175 : new VariableList(variables));
176 }
177
178 public static final class Builder {
179
180 private final VariableList variables;
181
182 private Value[] values;
183
184 Builder(final VariableList variables) {
185 this.variables = variables;
186 this.values = new Value[variables.size()];
187 }
188
189 public Builder set(final int index, @Nullable final Value value)
190 throws IndexOutOfBoundsException {
191 checkIndex(this.variables, index);
192 this.values[index] = CompactValueFactory.getInstance().normalize(value);
193 return this;
194 }
195
196 public Builder set(final String variable, @Nullable final Value value)
197 throws NoSuchElementException {
198 final int index = indexOfVariable(this.variables, variable);
199 this.values[index] = CompactValueFactory.getInstance().normalize(value);
200 return this;
201 }
202
203 public Builder setAll(final Value... values) throws IllegalArgumentException {
204 final int size = values.length;
205 checkSize(this.variables, size);
206 for (int i = 0; i < values.length; ++i) {
207 this.values[i] = CompactValueFactory.getInstance().normalize(values[i]);
208 }
209 return this;
210 }
211
212 public Builder setAll(final Iterable<? extends Value> values)
213 throws IllegalArgumentException {
214 final int size = Iterables.size(values);
215 checkSize(this.variables, size);
216 int index = 0;
217 for (final Value value : values) {
218 this.values[index++] = CompactValueFactory.getInstance().normalize(value);
219 }
220 return this;
221 }
222
223 public Builder setAll(final Map<? extends Object, ? extends Value> values)
224 throws NoSuchElementException, IndexOutOfBoundsException {
225 Arrays.fill(this.values, null);
226 for (final Map.Entry<? extends Object, ? extends Value> entry : values.entrySet()) {
227 final Object key = entry.getKey();
228 final Value value = entry.getValue();
229 if (key instanceof Number) {
230 set(((Number) key).intValue(), value);
231 } else {
232 set(key.toString(), value);
233 }
234 }
235 return this;
236 }
237
238 public Builder setAll(final BindingSet bindings) {
239 Arrays.fill(this.values, null);
240 for (final String name : bindings.getBindingNames()) {
241 set(name, bindings.getValue(name));
242 }
243 return this;
244 }
245
246 public CompactBindingSet build() {
247 final int size = this.values.length;
248 int singletonIndex = -1;
249 Value singletonValue = null;
250 for (int i = 0; i < size; ++i) {
251 final Value value = this.values[i];
252 if (value != null) {
253 if (singletonIndex == -1) {
254 singletonIndex = i;
255 singletonValue = value;
256 } else {
257 final CompactBindingSet solution = new ArrayCompactBindingSet(
258 this.variables, this.values);
259 this.values = new Value[size];
260 return solution;
261 }
262 }
263 }
264 if (singletonIndex == -1) {
265 return new EmptyCompactBindingSet(this.variables);
266 }
267 this.values[singletonIndex] = null;
268 return new SingletonCompactBindingSet(this.variables, singletonIndex, singletonValue);
269 }
270
271 private static void checkIndex(final List<String> variables, final int index) {
272 if (index < 0 || index >= variables.size()) {
273 throw new IndexOutOfBoundsException("Invalid variable index " + index
274 + " (variables are: " + Joiner.on(", ").join(variables) + ")");
275 }
276 }
277
278 private static void checkSize(final List<String> variables, final int size) {
279 if (size != variables.size()) {
280 throw new IllegalArgumentException("Expected " + variables.size()
281 + " values, got " + size + " (variables are: "
282 + Joiner.on(", ").join(variables) + ")");
283 }
284 }
285
286 private static int indexOfVariable(final List<String> variables, final String variable) {
287 final int index = variables.indexOf(variable);
288 if (index < 0) {
289 throw new NoSuchElementException("Unknown variable '" + variable
290 + "' (variables are: " + Joiner.on(", ").join(variables) + ")");
291 }
292 return index;
293 }
294
295 }
296
297 private static final class BindingIterator extends UnmodifiableIterator<Binding> {
298
299 private final CompactBindingSet bindings;
300
301 private Binding next;
302
303 private int index;
304
305 BindingIterator(final CompactBindingSet bindings) {
306 this.bindings = bindings;
307 this.next = null;
308 this.index = 0;
309 advance();
310 }
311
312 private void advance() {
313 final int size = this.bindings.variables.size();
314 while (this.index < size) {
315 final int index = this.index++;
316 final Value value = this.bindings.get(index);
317 if (value != null) {
318 final String variable = this.bindings.variables.get(index);
319 this.next = new BindingImpl(variable, value);
320 break;
321 }
322 }
323 }
324
325 @Override
326 public boolean hasNext() {
327 return this.next != null;
328 }
329
330 @Override
331 public Binding next() {
332 final Binding result = this.next;
333 if (result == null) {
334 throw new NoSuchElementException();
335 }
336 this.next = null;
337 advance();
338 return result;
339 }
340
341 }
342
343 private static class VariableSet extends AbstractSet<String> {
344
345 private final String[] variables;
346
347 VariableSet(final String... variables) {
348 this.variables = variables;
349 }
350
351 @Override
352 public Iterator<String> iterator() {
353 return Iterators.forArray(this.variables);
354 }
355
356 @Override
357 public int size() {
358 return this.variables.length;
359 }
360
361 @Override
362 public boolean contains(final Object object) {
363 if (object instanceof String) {
364 for (int i = 0; i < this.variables.length; ++i) {
365 if (this.variables[i].equals(object)) {
366 return true;
367 }
368 }
369 }
370 return false;
371 }
372
373 }
374
375 private static final class VariableList extends AbstractList<String> {
376
377 private final String[] variables;
378
379 private final String[] variableTable;
380
381 private final int[] indexTable;
382
383 public VariableList(final Iterable<? extends String> variables) {
384 final int size = Iterables.size(variables);
385 final int tableSize = size * 4 - 1;
386 this.variables = new String[size];
387 this.variableTable = new String[tableSize];
388 this.indexTable = new int[tableSize];
389 int index = 0;
390 for (final String variable : variables) {
391 int tableIndex = (variable.hashCode() & 0x7FFFFFFF) % tableSize;
392 while (this.variableTable[tableIndex] != null) {
393 tableIndex = (tableIndex + 1) % tableSize;
394 }
395 this.variables[index] = variable;
396 this.variableTable[tableIndex] = variable;
397 this.indexTable[tableIndex] = index;
398 ++index;
399 }
400 }
401
402 @Override
403 public int size() {
404 return this.variables.length;
405 }
406
407 @Override
408 public String get(final int index) {
409 return this.variables[index];
410 }
411
412 @Override
413 public boolean contains(final Object object) {
414 return indexOf(object) != -1;
415 }
416
417 @Override
418 public int indexOf(final Object object) {
419 final int tableSize = this.variableTable.length;
420 int tableIndex = (object.hashCode() & 0x7FFFFFFF) % tableSize;
421 for (int i = 0; i < tableSize; ++i) {
422 final String candidate = this.variableTable[tableIndex];
423 if (candidate != null && candidate.equals(object)) {
424 return this.indexTable[tableIndex];
425 }
426 tableIndex = (tableIndex + 1) % tableSize;
427 }
428 return -1;
429 }
430
431 @Override
432 public int lastIndexOf(final Object object) {
433 return indexOf(object);
434 }
435
436 }
437
438 private static final class EmptyCompactBindingSet extends CompactBindingSet {
439
440 private static final long serialVersionUID = 1L;
441
442 EmptyCompactBindingSet(final VariableList variables) {
443 super(variables);
444 }
445
446 @Override
447 @Nullable
448 public Value get(final int index) {
449 return null;
450 }
451
452 }
453
454 private static final class SingletonCompactBindingSet extends CompactBindingSet {
455
456 private static final long serialVersionUID = 1L;
457
458 private final int index;
459
460 private final Value value;
461
462 SingletonCompactBindingSet(final VariableList variables, final int index,
463 final Value value) {
464 super(variables);
465 this.index = index;
466 this.value = value;
467 }
468
469 @Override
470 @Nullable
471 public Value get(final int index) {
472 return index == this.index ? this.value : null;
473 }
474
475 }
476
477 private static final class ArrayCompactBindingSet extends CompactBindingSet {
478
479 private static final long serialVersionUID = 1L;
480
481 private final Value[] values;
482
483 ArrayCompactBindingSet(final VariableList variables, final Value[] values) {
484 super(variables);
485 this.values = values;
486 }
487
488 @Override
489 @Nullable
490 public Value get(final int index) {
491 return index >= 0 && index < this.values.length ? this.values[index] : null;
492 }
493
494 }
495
496 }