'''

Create a sparse matrix using a dictionary

'''

class SparseDict(object):

def __init__(self, mtx={}, m=0, n=0):

self.matrix = {}

self.matrix.update(mtx)

self.row = m

self.col = n

def __getitem__(self, ij):

return self.matrix.get(ij,0)

def __setitem__(self, ij, val):

self.matrix[ij] = val

dd = {}

# add all keys found in self and other

keys = self.matrix.keys()

for key in keys:

dd[key] = self.matrix[key] + other.matrix.get(key, 0)

# add all keys found in other but not in self

keysOther = other.matrix.keys()

for key in keysOther:

if key not in keys:

dd[key] = other.matrix[key]

return SparseDict(dd, max(self.row, other.row), max(self.col, other.col))

keys = []

for key in self.matrix.keys()+other.matrix.keys():

if key not in keys:

keys.append(key)

dd = {}

for key in keys:

dd[key] = self.matrix.get(key,0)+other.matrix.get(key,0)

return SparseDict(dd, max([i[0] for i in keys])+1, max([j[1] for j in keys])+1)

def __str__(self):

return '[%s]' % '\n'.join([' '.join([str(self[i,j]) for j in range(self.col)]) for i in range(self.row)])

if __name__=="__main__":

x = SparseDict({(3,2):4, (2,1):5}, 7, 7)

y = SparseDict({(3,2):1, (2,1):8}, 7, 7)

print x

print y

a = x + y

print a

z = SparseDict({(3,2):1, (2,1):8, (6,4):12}, 7, 7)

w = SparseDict({(1,2):1, (3,1):8, (6,4):12}, 8, 5)

zw = z+w

zz = SparseDict({(3,2):1, (2,1):8, (6,4):12}, 7, 7)

ww = SparseDict({(1,2):1, (3,1):8, (6,4):12, (7,8):225.5}, 8, 9)

zzww = zz+ww

print zzww

''' Interactive

>>> z = SparseDict({(3,2):1, (2,1):8, (6,4):12}, 7, 7)

>>> w = SparseDict({(1,2):1, (3,1):8, (6,4):12, (7,8):225.5}, 8, 9)

>>> zw = z+w

>>> print zw

[0 0 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0 0

0 8 0 0 0 0 0 0 0

0 8 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 24 0 0 0 0

0 0 0 0 0 0 0 0 225.5]

>>>

'''