@Test public void priorityqueue_or2() { RoaringBitmap rb1 = RoaringBitmap.bitmapOf(0, 1, 2); RoaringBitmap rb2 = RoaringBitmap.bitmapOf(0, 5, 6); RoaringBitmap rb3 = RoaringBitmap.bitmapOf(1<<16, 2<<16); RoaringBitmap result = FastAggregation.priorityqueue_or(rb1, rb2, rb3); RoaringBitmap expected = RoaringBitmap.bitmapOf(0, 1, 2, 5, 6, 1<<16, 2<<16); assertEquals(expected, result); }
public static RoaringBitmap priorityqueue_or(Iterator<? extends RoaringBitmap> bitmaps) { if (!bitmaps.hasNext()) { return new RoaringBitmap(); } ArrayList<RoaringBitmap> buffer = new ArrayList<>(); while (bitmaps.hasNext()) { buffer.add(bitmaps.next()); } final long[] sizes = new long[buffer.size()]; final boolean[] istmp = new boolean[buffer.size()]; for (int k = 0; k < sizes.length; ++k) { sizes[k] = buffer.get(k).getLongSizeInBytes(); } PriorityQueue<Integer> pq = new PriorityQueue<>(128, new Comparator<Integer>() { @Override public int compare(Integer a, Integer b) { return (int) (sizes[a] - sizes[b]); } }); for (int k = 0; k < sizes.length; ++k) { pq.add(k); } while (pq.size() > 1) { Integer x1 = pq.poll(); Integer x2 = pq.poll(); if (istmp[x2] && istmp[x1]) { buffer.set(x1, RoaringBitmap.lazyorfromlazyinputs(buffer.get(x1), buffer.get(x2))); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); istmp[x1] = true; pq.add(x1); } else if (istmp[x2]) { buffer.get(x2).lazyor(buffer.get(x1)); sizes[x2] = buffer.get(x2).getLongSizeInBytes(); pq.add(x2); } else if (istmp[x1]) { buffer.get(x1).lazyor(buffer.get(x2)); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); pq.add(x1); } else { buffer.set(x1, RoaringBitmap.lazyor(buffer.get(x1), buffer.get(x2))); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); istmp[x1] = true; pq.add(x1); } } RoaringBitmap answer = buffer.get(pq.poll()); answer.repairAfterLazy(); return answer; }
FastAggregation { public static RoaringBitmap priorityqueue_or(Iterator<? extends RoaringBitmap> bitmaps) { if (!bitmaps.hasNext()) { return new RoaringBitmap(); } ArrayList<RoaringBitmap> buffer = new ArrayList<>(); while (bitmaps.hasNext()) { buffer.add(bitmaps.next()); } final long[] sizes = new long[buffer.size()]; final boolean[] istmp = new boolean[buffer.size()]; for (int k = 0; k < sizes.length; ++k) { sizes[k] = buffer.get(k).getLongSizeInBytes(); } PriorityQueue<Integer> pq = new PriorityQueue<>(128, new Comparator<Integer>() { @Override public int compare(Integer a, Integer b) { return (int) (sizes[a] - sizes[b]); } }); for (int k = 0; k < sizes.length; ++k) { pq.add(k); } while (pq.size() > 1) { Integer x1 = pq.poll(); Integer x2 = pq.poll(); if (istmp[x2] && istmp[x1]) { buffer.set(x1, RoaringBitmap.lazyorfromlazyinputs(buffer.get(x1), buffer.get(x2))); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); istmp[x1] = true; pq.add(x1); } else if (istmp[x2]) { buffer.get(x2).lazyor(buffer.get(x1)); sizes[x2] = buffer.get(x2).getLongSizeInBytes(); pq.add(x2); } else if (istmp[x1]) { buffer.get(x1).lazyor(buffer.get(x2)); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); pq.add(x1); } else { buffer.set(x1, RoaringBitmap.lazyor(buffer.get(x1), buffer.get(x2))); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); istmp[x1] = true; pq.add(x1); } } RoaringBitmap answer = buffer.get(pq.poll()); answer.repairAfterLazy(); return answer; } }
FastAggregation { public static RoaringBitmap priorityqueue_or(Iterator<? extends RoaringBitmap> bitmaps) { if (!bitmaps.hasNext()) { return new RoaringBitmap(); } ArrayList<RoaringBitmap> buffer = new ArrayList<>(); while (bitmaps.hasNext()) { buffer.add(bitmaps.next()); } final long[] sizes = new long[buffer.size()]; final boolean[] istmp = new boolean[buffer.size()]; for (int k = 0; k < sizes.length; ++k) { sizes[k] = buffer.get(k).getLongSizeInBytes(); } PriorityQueue<Integer> pq = new PriorityQueue<>(128, new Comparator<Integer>() { @Override public int compare(Integer a, Integer b) { return (int) (sizes[a] - sizes[b]); } }); for (int k = 0; k < sizes.length; ++k) { pq.add(k); } while (pq.size() > 1) { Integer x1 = pq.poll(); Integer x2 = pq.poll(); if (istmp[x2] && istmp[x1]) { buffer.set(x1, RoaringBitmap.lazyorfromlazyinputs(buffer.get(x1), buffer.get(x2))); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); istmp[x1] = true; pq.add(x1); } else if (istmp[x2]) { buffer.get(x2).lazyor(buffer.get(x1)); sizes[x2] = buffer.get(x2).getLongSizeInBytes(); pq.add(x2); } else if (istmp[x1]) { buffer.get(x1).lazyor(buffer.get(x2)); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); pq.add(x1); } else { buffer.set(x1, RoaringBitmap.lazyor(buffer.get(x1), buffer.get(x2))); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); istmp[x1] = true; pq.add(x1); } } RoaringBitmap answer = buffer.get(pq.poll()); answer.repairAfterLazy(); return answer; } private  FastAggregation(); }
FastAggregation { public static RoaringBitmap priorityqueue_or(Iterator<? extends RoaringBitmap> bitmaps) { if (!bitmaps.hasNext()) { return new RoaringBitmap(); } ArrayList<RoaringBitmap> buffer = new ArrayList<>(); while (bitmaps.hasNext()) { buffer.add(bitmaps.next()); } final long[] sizes = new long[buffer.size()]; final boolean[] istmp = new boolean[buffer.size()]; for (int k = 0; k < sizes.length; ++k) { sizes[k] = buffer.get(k).getLongSizeInBytes(); } PriorityQueue<Integer> pq = new PriorityQueue<>(128, new Comparator<Integer>() { @Override public int compare(Integer a, Integer b) { return (int) (sizes[a] - sizes[b]); } }); for (int k = 0; k < sizes.length; ++k) { pq.add(k); } while (pq.size() > 1) { Integer x1 = pq.poll(); Integer x2 = pq.poll(); if (istmp[x2] && istmp[x1]) { buffer.set(x1, RoaringBitmap.lazyorfromlazyinputs(buffer.get(x1), buffer.get(x2))); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); istmp[x1] = true; pq.add(x1); } else if (istmp[x2]) { buffer.get(x2).lazyor(buffer.get(x1)); sizes[x2] = buffer.get(x2).getLongSizeInBytes(); pq.add(x2); } else if (istmp[x1]) { buffer.get(x1).lazyor(buffer.get(x2)); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); pq.add(x1); } else { buffer.set(x1, RoaringBitmap.lazyor(buffer.get(x1), buffer.get(x2))); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); istmp[x1] = true; pq.add(x1); } } RoaringBitmap answer = buffer.get(pq.poll()); answer.repairAfterLazy(); return answer; } 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 priorityqueue_or(Iterator<? extends RoaringBitmap> bitmaps) { if (!bitmaps.hasNext()) { return new RoaringBitmap(); } ArrayList<RoaringBitmap> buffer = new ArrayList<>(); while (bitmaps.hasNext()) { buffer.add(bitmaps.next()); } final long[] sizes = new long[buffer.size()]; final boolean[] istmp = new boolean[buffer.size()]; for (int k = 0; k < sizes.length; ++k) { sizes[k] = buffer.get(k).getLongSizeInBytes(); } PriorityQueue<Integer> pq = new PriorityQueue<>(128, new Comparator<Integer>() { @Override public int compare(Integer a, Integer b) { return (int) (sizes[a] - sizes[b]); } }); for (int k = 0; k < sizes.length; ++k) { pq.add(k); } while (pq.size() > 1) { Integer x1 = pq.poll(); Integer x2 = pq.poll(); if (istmp[x2] && istmp[x1]) { buffer.set(x1, RoaringBitmap.lazyorfromlazyinputs(buffer.get(x1), buffer.get(x2))); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); istmp[x1] = true; pq.add(x1); } else if (istmp[x2]) { buffer.get(x2).lazyor(buffer.get(x1)); sizes[x2] = buffer.get(x2).getLongSizeInBytes(); pq.add(x2); } else if (istmp[x1]) { buffer.get(x1).lazyor(buffer.get(x2)); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); pq.add(x1); } else { buffer.set(x1, RoaringBitmap.lazyor(buffer.get(x1), buffer.get(x2))); sizes[x1] = buffer.get(x1).getLongSizeInBytes(); istmp[x1] = true; pq.add(x1); } } RoaringBitmap answer = buffer.get(pq.poll()); answer.repairAfterLazy(); return answer; } 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);  }