StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Pay particular attention to the encode method. It has some bithacks =).</p> <pre><code>import java.util.*; class MortonQuadTree<E> { List<E> data = new ArrayList<E>(); public E insert(int x, int y, E e) { int pos = encode(x,y); ensureCapacity(pos); return data.set(pos,e); } public E query(int x, int y) { int pos = encode(x,y); return data.get(pos); } private void ensureCapacity(int size) { while(data.size() < size + 1) data.add(null); } // technically the values here aren't final... don't overwrite them :) static final int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF}; static final int S[] = {1, 2, 4, 8}; /** * Interleave lower 16 bits of x and y, so the bits of x * are in the even positions and bits from y in the odd; * x and y must initially be less than 65536. * Adapated from http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN */ private static int encode(int x, int y) { x = (x | (x << S[3])) & B[3]; x = (x | (x << S[2])) & B[2]; x = (x | (x << S[1])) & B[1]; x = (x | (x << S[0])) & B[0]; y = (y | (y << S[3])) & B[3]; y = (y | (y << S[2])) & B[2]; y = (y | (y << S[1])) & B[1]; y = (y | (y << S[0])) & B[0]; return x | (y << 1); } public static void main(String[] args) { MortonQuadTree<String> tree = new MortonQuadTree<String>(); tree.insert(1,4,"Hello"); tree.insert(6,8,"World"); System.out.println(tree.query(1,4)); // should be hello System.out.println(tree.query(6,8)); // should be world System.out.println(tree.query(9,6)); // should be null System.out.println(tree.query(900,600)); // should be index error } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload