subdivision_tree.py

class SubdivisionTree(object):
    """docstring for SubdivisionTree"""
    def __init__(self, top, right, bottom, left, element=None):
        self.top = top
        self.right = right
        self.bottom = bottom
        self.left = left
        self.element = element
        self.subdivided = False
        
        # subdivided elements
        self.tr = None
        self.br = None
        self.bl = None
        self.tl = None
    
    # value is (x, y, thingy)
    def insert(self, value):
        mid_x = (self.left + self.right) / 2.0
        mid_y = (self.top + self.bottom) / 2.0
        
        if not self.element and not self.subdivided:
            self.element = value
        elif self.element:
            assert not self.subdivided
            self.tr = SubdivisionTree(self.top, self.right, mid_y,       mid_x)
            self.br = SubdivisionTree(mid_y,    self.right, self.bottom, mid_x)
            self.bl = SubdivisionTree(mid_y,    mid_x,      self.bottom, self.left)
            self.tl = SubdivisionTree(self.top, mid_x,      mid_y,       self.left)
            self.subdivided = True
            
            x, y, _ = self.element
            if x < mid_x and y < mid_y:
                self.bl.insert(self.element)
            elif x < mid_x: # and y >= mid_y
                self.tl.insert(self.element)
            elif y < mid_y: # and x >= mid_x
                self.br.insert(self.element)
            else:
                self.tr.insert(self.element)
            self.element = None
            
            x, y, _ = value
            if x < mid_x and y < mid_y:
                self.bl.insert(value)
            elif x < mid_x: # and y >= mid_y
                self.tl.insert(value)
            elif y < mid_y: # and x >= mid_x
                self.br.insert(value)
            else:
                self.tr.insert(value)
        else:
            assert self.subdivided
            x, y, _ = value
            if x < mid_x and y < mid_y:
                self.bl.insert(value)
            elif x < mid_x: # and y >= mid_y
                self.tl.insert(value)
            elif y < mid_y: # and x >= mid_x
                self.br.insert(value)
            else:
                self.tr.insert(value)
    
    def fold(self, cons_f, value_f, null):
        if not self.element and not self.subdivided:
            return null
        elif self.element:
            return value_f(self.element)
        else:
            return cons_f(self.tr.fold(cons_f, value_f, null),
                          self.br.fold(cons_f, value_f, null),
                          self.bl.fold(cons_f, value_f, null),
                          self.tl.fold(cons_f, value_f, null))

def main():
    s = SubdivisionTree(10.0, 10.0, 0.0, 0.0)
    s.insert((6.5, 6.5, 'Ann Arbor'))
    s.insert((7.0, 7.0, 'Detroit'))
    s.insert((1.0, 1.0, 'Mountain View'))
    print s.fold(lambda tr, br, bl, tl: tr + br + bl + tl,
                 lambda v: [v],
                 [])

if __name__ == '__main__':
    main()