@Test public void testWorkShyAnd() { final RoaringBitmap b1 = RoaringBitmap.bitmapOf(1, 2, 0x10001, 0x20001, 0x30001); final RoaringBitmap b2 = RoaringBitmap.bitmapOf(2, 3, 0x20002, 0x30001); final RoaringBitmap bResult = FastAggregation.workShyAnd(new long[1024], b1, b2); assertFalse(bResult.contains(1)); assertTrue(bResult.contains(2)); assertFalse(bResult.contains(3)); }
public static RoaringBitmap workShyAnd(long[] buffer, RoaringBitmap... bitmaps) { long[] words = buffer; RoaringBitmap first = bitmaps[0]; for (int i = 0; i < first.highLowContainer.size; ++i) { char key = first.highLowContainer.keys[i]; words[key >>> 6] |= 1L << key; } int numContainers = first.highLowContainer.size; for (int i = 1; i < bitmaps.length && numContainers > 0; ++i) { numContainers = Util.intersectArrayIntoBitmap(words, bitmaps[i].highLowContainer.keys, bitmaps[i].highLowContainer.size); } if (numContainers == 0) { return new RoaringBitmap(); } char[] keys = new char[numContainers]; int base = 0; int pos = 0; for (long word : words) { while (word != 0L) { keys[pos++] = (char)(base + Long.numberOfTrailingZeros(word)); word &= (word - 1); } base += 64; } Container[][] containers = new Container[numContainers][bitmaps.length]; for (int i = 0; i < bitmaps.length; ++i) { RoaringBitmap bitmap = bitmaps[i]; int position = 0; for (int j = 0; j < bitmap.highLowContainer.size; ++j) { char key = bitmap.highLowContainer.keys[j]; if ((words[key >>> 6] & (1L << key)) != 0) { containers[position++][i] = bitmap.highLowContainer.values[j]; } } } RoaringArray array = new RoaringArray(keys, new Container[numContainers], 0); for (int i = 0; i < numContainers; ++i) { Container[] slice = containers[i]; Arrays.fill(words, -1L); Container tmp = new BitmapContainer(words, -1); for (Container container : slice) { Container and = tmp.iand(container); if (and != tmp) { tmp = and; } } tmp = tmp.repairAfterLazy(); if (!tmp.isEmpty()) { array.append(keys[i], tmp instanceof BitmapContainer ? tmp.clone() : tmp); } } return new RoaringBitmap(array); }
FastAggregation { public static RoaringBitmap workShyAnd(long[] buffer, RoaringBitmap... bitmaps) { long[] words = buffer; RoaringBitmap first = bitmaps[0]; for (int i = 0; i < first.highLowContainer.size; ++i) { char key = first.highLowContainer.keys[i]; words[key >>> 6] |= 1L << key; } int numContainers = first.highLowContainer.size; for (int i = 1; i < bitmaps.length && numContainers > 0; ++i) { numContainers = Util.intersectArrayIntoBitmap(words, bitmaps[i].highLowContainer.keys, bitmaps[i].highLowContainer.size); } if (numContainers == 0) { return new RoaringBitmap(); } char[] keys = new char[numContainers]; int base = 0; int pos = 0; for (long word : words) { while (word != 0L) { keys[pos++] = (char)(base + Long.numberOfTrailingZeros(word)); word &= (word - 1); } base += 64; } Container[][] containers = new Container[numContainers][bitmaps.length]; for (int i = 0; i < bitmaps.length; ++i) { RoaringBitmap bitmap = bitmaps[i]; int position = 0; for (int j = 0; j < bitmap.highLowContainer.size; ++j) { char key = bitmap.highLowContainer.keys[j]; if ((words[key >>> 6] & (1L << key)) != 0) { containers[position++][i] = bitmap.highLowContainer.values[j]; } } } RoaringArray array = new RoaringArray(keys, new Container[numContainers], 0); for (int i = 0; i < numContainers; ++i) { Container[] slice = containers[i]; Arrays.fill(words, -1L); Container tmp = new BitmapContainer(words, -1); for (Container container : slice) { Container and = tmp.iand(container); if (and != tmp) { tmp = and; } } tmp = tmp.repairAfterLazy(); if (!tmp.isEmpty()) { array.append(keys[i], tmp instanceof BitmapContainer ? tmp.clone() : tmp); } } return new RoaringBitmap(array); } }
FastAggregation { public static RoaringBitmap workShyAnd(long[] buffer, RoaringBitmap... bitmaps) { long[] words = buffer; RoaringBitmap first = bitmaps[0]; for (int i = 0; i < first.highLowContainer.size; ++i) { char key = first.highLowContainer.keys[i]; words[key >>> 6] |= 1L << key; } int numContainers = first.highLowContainer.size; for (int i = 1; i < bitmaps.length && numContainers > 0; ++i) { numContainers = Util.intersectArrayIntoBitmap(words, bitmaps[i].highLowContainer.keys, bitmaps[i].highLowContainer.size); } if (numContainers == 0) { return new RoaringBitmap(); } char[] keys = new char[numContainers]; int base = 0; int pos = 0; for (long word : words) { while (word != 0L) { keys[pos++] = (char)(base + Long.numberOfTrailingZeros(word)); word &= (word - 1); } base += 64; } Container[][] containers = new Container[numContainers][bitmaps.length]; for (int i = 0; i < bitmaps.length; ++i) { RoaringBitmap bitmap = bitmaps[i]; int position = 0; for (int j = 0; j < bitmap.highLowContainer.size; ++j) { char key = bitmap.highLowContainer.keys[j]; if ((words[key >>> 6] & (1L << key)) != 0) { containers[position++][i] = bitmap.highLowContainer.values[j]; } } } RoaringArray array = new RoaringArray(keys, new Container[numContainers], 0); for (int i = 0; i < numContainers; ++i) { Container[] slice = containers[i]; Arrays.fill(words, -1L); Container tmp = new BitmapContainer(words, -1); for (Container container : slice) { Container and = tmp.iand(container); if (and != tmp) { tmp = and; } } tmp = tmp.repairAfterLazy(); if (!tmp.isEmpty()) { array.append(keys[i], tmp instanceof BitmapContainer ? tmp.clone() : tmp); } } return new RoaringBitmap(array); } private  FastAggregation(); }
FastAggregation { public static RoaringBitmap workShyAnd(long[] buffer, RoaringBitmap... bitmaps) { long[] words = buffer; RoaringBitmap first = bitmaps[0]; for (int i = 0; i < first.highLowContainer.size; ++i) { char key = first.highLowContainer.keys[i]; words[key >>> 6] |= 1L << key; } int numContainers = first.highLowContainer.size; for (int i = 1; i < bitmaps.length && numContainers > 0; ++i) { numContainers = Util.intersectArrayIntoBitmap(words, bitmaps[i].highLowContainer.keys, bitmaps[i].highLowContainer.size); } if (numContainers == 0) { return new RoaringBitmap(); } char[] keys = new char[numContainers]; int base = 0; int pos = 0; for (long word : words) { while (word != 0L) { keys[pos++] = (char)(base + Long.numberOfTrailingZeros(word)); word &= (word - 1); } base += 64; } Container[][] containers = new Container[numContainers][bitmaps.length]; for (int i = 0; i < bitmaps.length; ++i) { RoaringBitmap bitmap = bitmaps[i]; int position = 0; for (int j = 0; j < bitmap.highLowContainer.size; ++j) { char key = bitmap.highLowContainer.keys[j]; if ((words[key >>> 6] & (1L << key)) != 0) { containers[position++][i] = bitmap.highLowContainer.values[j]; } } } RoaringArray array = new RoaringArray(keys, new Container[numContainers], 0); for (int i = 0; i < numContainers; ++i) { Container[] slice = containers[i]; Arrays.fill(words, -1L); Container tmp = new BitmapContainer(words, -1); for (Container container : slice) { Container and = tmp.iand(container); if (and != tmp) { tmp = and; } } tmp = tmp.repairAfterLazy(); if (!tmp.isEmpty()) { array.append(keys[i], tmp instanceof BitmapContainer ? tmp.clone() : tmp); } } return new RoaringBitmap(array); } private  FastAggregation(); static RoaringBitmap and(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap and(RoaringBitmap... bitmaps); static RoaringBitmap and(long[] aggregationBuffer, RoaringBitmap... bitmaps); @Deprecated static RoaringBitmap horizontal_or(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap horizontal_or(List<? extends RoaringBitmap> bitmaps); static RoaringBitmap horizontal_or(RoaringBitmap... bitmaps); static RoaringBitmap horizontal_xor(RoaringBitmap... bitmaps); static RoaringBitmap naive_and(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap naive_and(RoaringBitmap... bitmaps); static RoaringBitmap workShyAnd(long[] buffer, RoaringBitmap... bitmaps); static RoaringBitmap workAndMemoryShyAnd(long[] buffer, RoaringBitmap... bitmaps); static RoaringBitmap naive_or(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap naive_or(RoaringBitmap... bitmaps); static RoaringBitmap naive_xor(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap naive_xor(RoaringBitmap... bitmaps); static RoaringBitmap or(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap or(RoaringBitmap... bitmaps); static RoaringBitmap priorityqueue_or(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap priorityqueue_or(RoaringBitmap... bitmaps); static RoaringBitmap priorityqueue_xor(RoaringBitmap... bitmaps); static RoaringBitmap xor(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap xor(RoaringBitmap... bitmaps); }
FastAggregation { public static RoaringBitmap workShyAnd(long[] buffer, RoaringBitmap... bitmaps) { long[] words = buffer; RoaringBitmap first = bitmaps[0]; for (int i = 0; i < first.highLowContainer.size; ++i) { char key = first.highLowContainer.keys[i]; words[key >>> 6] |= 1L << key; } int numContainers = first.highLowContainer.size; for (int i = 1; i < bitmaps.length && numContainers > 0; ++i) { numContainers = Util.intersectArrayIntoBitmap(words, bitmaps[i].highLowContainer.keys, bitmaps[i].highLowContainer.size); } if (numContainers == 0) { return new RoaringBitmap(); } char[] keys = new char[numContainers]; int base = 0; int pos = 0; for (long word : words) { while (word != 0L) { keys[pos++] = (char)(base + Long.numberOfTrailingZeros(word)); word &= (word - 1); } base += 64; } Container[][] containers = new Container[numContainers][bitmaps.length]; for (int i = 0; i < bitmaps.length; ++i) { RoaringBitmap bitmap = bitmaps[i]; int position = 0; for (int j = 0; j < bitmap.highLowContainer.size; ++j) { char key = bitmap.highLowContainer.keys[j]; if ((words[key >>> 6] & (1L << key)) != 0) { containers[position++][i] = bitmap.highLowContainer.values[j]; } } } RoaringArray array = new RoaringArray(keys, new Container[numContainers], 0); for (int i = 0; i < numContainers; ++i) { Container[] slice = containers[i]; Arrays.fill(words, -1L); Container tmp = new BitmapContainer(words, -1); for (Container container : slice) { Container and = tmp.iand(container); if (and != tmp) { tmp = and; } } tmp = tmp.repairAfterLazy(); if (!tmp.isEmpty()) { array.append(keys[i], tmp instanceof BitmapContainer ? tmp.clone() : tmp); } } return new RoaringBitmap(array); } private  FastAggregation(); static RoaringBitmap and(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap and(RoaringBitmap... bitmaps); static RoaringBitmap and(long[] aggregationBuffer, RoaringBitmap... bitmaps); @Deprecated static RoaringBitmap horizontal_or(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap horizontal_or(List<? extends RoaringBitmap> bitmaps); static RoaringBitmap horizontal_or(RoaringBitmap... bitmaps); static RoaringBitmap horizontal_xor(RoaringBitmap... bitmaps); static RoaringBitmap naive_and(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap naive_and(RoaringBitmap... bitmaps); static RoaringBitmap workShyAnd(long[] buffer, RoaringBitmap... bitmaps); static RoaringBitmap workAndMemoryShyAnd(long[] buffer, RoaringBitmap... bitmaps); static RoaringBitmap naive_or(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap naive_or(RoaringBitmap... bitmaps); static RoaringBitmap naive_xor(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap naive_xor(RoaringBitmap... bitmaps); static RoaringBitmap or(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap or(RoaringBitmap... bitmaps); static RoaringBitmap priorityqueue_or(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap priorityqueue_or(RoaringBitmap... bitmaps); static RoaringBitmap priorityqueue_xor(RoaringBitmap... bitmaps); static RoaringBitmap xor(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap xor(RoaringBitmap... bitmaps);  }