<s> '''<STR_LIT>''' <EOL> import math <EOL> import geo <EOL> class Bins ( object ) : <EOL> def __init__ ( self , diameter ) : <EOL> self . diameter = diameter <EOL> self . bins = { } <EOL> def _index ( self , coord ) : <EOL> return int ( math . floor ( coord / self . diameter ) ) <EOL> def _index2 ( self , point ) : <EOL> x , y = point <EOL> return ( self . _index ( x ) , self . _index ( y ) ) <EOL> def add ( self , point , value ) : <EOL> bin = self . bins . setdefault ( self . _index2 ( point ) , [ ] ) <EOL> bin . append ( ( point , value ) ) <EOL> def in_rect ( self , rect ) : <EOL> x0 , y0 , x1 , y1 = rect <EOL> ix0 = self . _index ( x0 ) <EOL> iy0 = self . _index ( y0 ) <EOL> ix1 = self . _index ( x1 ) <EOL> iy1 = self . _index ( y1 ) <EOL> results = [ ] <EOL> for ix in range ( ix0 , ix1 + <NUM_LIT:1> ) : <EOL> for iy in range ( iy0 , iy1 + <NUM_LIT:1> ) : <EOL> if self . bins . has_key ( ( ix , iy ) ) : <EOL> for point , value in self . bins [ ( ix , iy ) ] : <EOL> if geo . point_in_rect_q ( point , rect ) : results . append ( ( point , value ) ) <EOL> return results <EOL> def in_radius ( self , point , r ) : <EOL> px , py = point <EOL> results = [ ] <EOL> for p2 , value in self . in_rect ( ( px - r , py - r , px + r , py + r ) ) : <EOL> if geo . distance ( point , p2 ) < r : results . append ( ( p2 , value ) ) <EOL> return results <EOL> def test ( ) : <EOL> b = Bins ( <NUM_LIT:100> ) <EOL> b . add ( ( <NUM_LIT:1> , <NUM_LIT:1> ) , '<STR_LIT:a>' ) <EOL> b . add ( ( <NUM_LIT:2> , <NUM_LIT:3> ) , '<STR_LIT:b>' ) <EOL> b . add ( ( <NUM_LIT:1000> , <NUM_LIT> ) , '<STR_LIT>' ) <EOL> assert len ( b . in_rect ( ( <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:50> , <NUM_LIT:50> ) ) ) == <NUM_LIT:2> <EOL> assert len ( b . in_rect ( ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) ) ) == <NUM_LIT:1> <EOL> assert len ( b . in_radius ( ( <NUM_LIT:1> , <NUM_LIT:1> ) , <NUM_LIT:0.5> ) ) == <NUM_LIT:1> <EOL> assert len ( b . in_radius ( ( <NUM_LIT:1> , <NUM_LIT:1> ) , <NUM_LIT:100> ) ) == <NUM_LIT:2> <EOL> assert len ( b . in_radius ( ( <NUM_LIT> , <NUM_LIT> ) , <NUM_LIT:10> ) ) == <NUM_LIT:1> <EOL> assert len ( b . in_radius ( ( - <NUM_LIT:1> , <NUM_LIT:0> ) , <NUM_LIT> ) ) == <NUM_LIT:0> <EOL> print '<STR_LIT>' <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> test ( ) </s>
