Implementation of summed area table / integral image in python.

SummedAreaTable.py

class SummedAreaTable(object):
  def __init__(self, size, data):
    """
    Just because I dislike a 2d array / list.
    data should be a List of Integer.
    """   
    width, height = size 
    assert width * height == len(data), "invalid data length and or data size"
    self.size = size 
    self.data = data    
    self.memo = [None for _ in xrange(width * height)]
    self.generate()  

  def get(self, x, y):
    """
    get the value of self, at point x, y.
    it's possible for the value at that point hadn't been generated.
    """
    width, height = self.size
    index = y * width + x    
    if(x < 0 or y < 0):
      # value at negative-indexed point is always 0
      return 0
    elif self.memo[index] is not None:
      # if the value at point x, y has already been generated
      return self.memo[index]
    else:
      # calculate the value at point x, y if it hasn't been generated
      cummulative = self.get(x - 1, y) + self.get(x, y - 1) - self.get(x - 1, y - 1) + self.data[index]
      self.memo[index] = cummulative
      return cummulative

  def total(self, x0, y0, x1, y1):
    """
    get the cummulative value of this instance from point (x0, y0) to (x1, y1)
    """
    a = self.get(x0 - 1, y0 - 1)
    b = self.get(x0 - 1, y1)
    c = self.get(x1, y0 - 1)
    d = self.get(x1, y1)
    return d - b - c + a

  def generate(self):    
    width, height = self.size      
    self.memo = [self.get(x, y) for y in xrange(height) for x in xrange(width)]    
    

def example():  
  w = h = 10
  haar = SummedAreaTable(size=(w, h), data=range(w * h))  
  print haar.total(2, 2, 4, 4)
  print sum((y * w + x for y in xrange(h) for x in xrange(w) if 2 <= y <= 4 and 2 <= x <= 4))

if __name__ == '__main__':
  example()