'''

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

 

    def __add__(self, other):

        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))

 

    def __add__(self, other):

        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]

>>>

'''