/
OrderedWriter.java
96 lines (85 loc) · 2.79 KB
/
OrderedWriter.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
package org.roaringbitmap;
import java.util.Arrays;
public class OrderedWriter {
private static final int WORD_COUNT = 1 << 10;
private final long[] bitmap;
private final RoaringBitmap underlying;
private short currentKey;
private boolean dirty = false;
public OrderedWriter(RoaringBitmap underlying) {
this.underlying = underlying;
this.bitmap = new long[WORD_COUNT];
}
/**
* Adds the value to the underlying bitmap.
* @param value the value to add.
*/
public void add(int value) {
short key = Util.highbits(value);
short low = Util.lowbits(value);
if (key != currentKey) {
if (Util.compareUnsigned(key, currentKey) < 0) {
throw new IllegalStateException("Must write in ascending key order");
}
flush();
}
int ulow = low & 0xFFFF;
bitmap[(ulow >>> 6)] |= (1L << ulow);
currentKey = key;
dirty = true;
}
/**
* Ensures that any buffered additions are flushed to the underlying bitmap.
*/
public void flush() {
if (dirty) {
int cardinality = computeCardinality();
RoaringArray highLowContainer = underlying.highLowContainer;
// we check that it's safe to append since RoaringArray.append does no validation
if (highLowContainer.size > 0) {
short key = highLowContainer.getKeyAtIndex(highLowContainer.size - 1);
if (Util.compareUnsigned(currentKey, key) <= 0) {
throw new IllegalStateException("Cannot write " + currentKey + " after " + key);
}
}
highLowContainer.append(currentKey, chooseBestContainer(cardinality));
clearBitmap();
dirty = false;
}
}
private Container chooseBestContainer(int cardinality) {
if (cardinality < WORD_COUNT) {
return createArrayContainer(cardinality);
}
Container bitmapContainer = new BitmapContainer(bitmap, cardinality);
Container runOptimised = bitmapContainer.runOptimize();
if (runOptimised == bitmapContainer) { // don't let our array escape
return new BitmapContainer(Arrays.copyOf(bitmap, bitmap.length), cardinality);
}
return runOptimised;
}
private ArrayContainer createArrayContainer(int cardinality) {
short[] array = new short[cardinality];
int arrIndex = 0;
for (int i = 0; i < bitmap.length; ++i) {
long word = bitmap[i];
int j = Long.numberOfTrailingZeros(word);
while (j < 64) {
word ^= (1L << j);
array[arrIndex++] = (short) ((i << 6) + j);
j = Long.numberOfTrailingZeros(word);
}
}
return new ArrayContainer(cardinality, array);
}
private void clearBitmap() {
Arrays.fill(bitmap, 0L);
}
private int computeCardinality() {
int cardinality = 0;
for (int i = 0; i < bitmap.length; ++i) {
cardinality += Long.bitCount(bitmap[i]);
}
return cardinality;
}
}