Approximating Streaming Data with Sketching - Real-Time Analytics - page 451

The subintervals can then be computed recursively by finding the largest
dyadic interval that fits within the current interval. This interval is added to
the final output and potentially generates two further intervals, the interval
totheleftoftherangeandtheintervaltotherightattherange.Theseranges
are recursively divided in the same way until all points have been included
in one range:
public static List<DyadicInterval> createIntervals(int
a,int b) {
ArrayList<DyadicInterval> output = new
ArrayList<DyadicInterval>();
Stack<Integer> left = new Stack<Integer>();
Stack<Integer> right = new Stack<Integer>();
left.push(Math. min (a, b));
right.push(Math. max (a, b)+1);
while(left.size() > 0) {
int l = left.pop();
int r = right.pop();
for(int k = 32;k>=0;k--) {
long J = (1L << k);
long L = (int)(J*Math. ceil ((double)l/
(double)J));
long R = L + J - 1;
if(R < r) {
//Segment fits in the range
output.add(new DyadicInterval((int)k,(int)(L/
J)));
if(L > l) {
left.push(l);right.push((int)L);
}
if(R+1 < r) {
left.push((int)(R+1));right.push(r);
}
break;
}
}
}