uber/in-n-out — pull request #4 by gshu (2013-05-29 03:53:12+00:00)
Title: Speed up geofence group lookup

This change is an attempts to speed up geofence group lookup.
The idea is to create a master grid where each tile tracks the subset
of candidate entries in the group. The master grid is updated when a
new group is joined. An entry might be in at most one of the three
states w.r.t. a specific tile:
'w': means the entry whiteout the whole tile
'b': means the entry blackout the whole tile
'?': not sure.
To do look up Ids for a given point, we will inspect all entries in
the '?' set for the point's tile, and combine that with 'w' and 'b'
set to get the answer.

The change contains the following specific changes
- Refactor Geofence gridify routine (makeGrid) so that it can be
reused by the master grid.
- Add support for removing an entry, fix a bug in original add routine.
- Implement fast lookup method. The method does not guarantee order of the returned Ids.
- Add a new test for both correctness and performance gain of the optimization.
- Add a test in test_geofence to illustrate a potential bug in geofence.inside().