Problem #2: Sparse Matrix Class 
Problem Summary:
A Matrix is a 2dimensional type storing values indexed by a row and a
column.
For example, the following is a 3x3 Matrix (its 3 rows and columns are numbered
starting at 0; so 02).
Here, the value indexed by Row 1 and Column 2 is 3.
Indexes 
Column 0 
Column 1 
Column 2 
Row 0 
1 
0 
0 
Row 1 
0 
5 
3 
Row 2 
0 
0 
1 
We could choose to store this Matrix by using a tuple of rows; where each
row is a tuple of values in its columns.
( (1, 0, 0), (0, 5, 3), (0, 0, 1) )
But in this problem, we will use a more interesting data structure.
A Sparse Matrix stores the row and column size of a Matrix, and a
dictonary whose keys are 2tuples (row and column index) and their associated
nonzero values: any index in the Matrix that is not a key in its
dictionary stores 0 implicitly; no key in its dictionary should store
a zero value.
A Sparse Matrix would store the 9 values in the Matrix above in a dictionary of
4 index keys (and their associated non0 values).
The remaining 5 0s are stored implicitly: any index key in the Sparse
Matrix but not in the dictionary (e.g., the (0,1) tuple) implicitly
stores 0.
{(0,0): 1, (1,1): 5, (1,2): 3, (2,2): 1}
Write a class named Sparse_Matrix that represents and defines operators
for Sparse Matrix objects, which are represented by a dictionary whose keys
are 2tuples representing a row and column of the Sparse Matrix and whose
associated values are the nonzero matrix values stored at that row and colum.
Operators will typically be defined to work on Sparse_Matrix objects, or
between a Sparse_Matrix and a numeric (int or float)
value.
The Sparse_Matrix class will be be immutable except for the
__call__ method, which can change the number of rows and columns in a
matrix (and of course the __setitem__ and __delitem__ methods).
All other methods will not mutate their Sparse_Matrix objects; methods
that must return a Sparse_Matrix (like the arithmetic operators) will
return a newly_constructed Sparse Matrix storing the appropriate
values.
Details
 Define a class named Sparse_Matrix in a module named
sparsematrix.py.
 Define an __init__ method that has two required parameters (the
number of rows and columns specifying the size of the Sparse Matrix),
followed by any number (zero or more) of 3tuple arguments: each will
contain a (1) row and a (2) column index, and a (3) value that is to be
stored at that index.
For example, writing Sparse_Matrix(2, 2, (0,0,5), (1,1,5))
represents a Sparse Matrix whose value at indexes (0,0) and
(1,1) is 5, and whose values at all other indexes are 0.
The __str__ method (read its definition below) displays such a Sparse
Matrix as
2x2:[5 0
0 5]
showing it size and all its values: both non0 and 0.
The dictionary representing this Sparse_Matrix stores only the two
non0 values: {(0,0): 5, (1,1): 5}
IMPORTANT:
Store a Sparse Matrix using the attributes named rows, cols,
and matrix (which is a dictionary (dict) whose keys are
2tuples (row,column), each of which is associated with a nonzero
value).
Store only these attributes: no others.
You must set these attributes as self.rows, self.cols and
self.matrix, because I have defined the __str__ method and
various batch selftests to refer to these attributes, by these names.
This dictionary should never store an associated value of 0:
if the third value of a 3tuple supplied to __init__ is 0
ignore it: do not store it in self.matrix.
So Sparse_Matrix(2, 2, (0,0,5), (1,1,5), (0,1,0)) still stores
only the two non0 values in its dictionary:
{(0,0): 5, (1,1): 5}.
The __init__ method should raise an AssertionError with
an appropiate message if the arguments violate any of the following
conditions:
 The row and column arguments must be integers that are strictly
greater than 0.
 The row and column in each triple must be nonnegative integers that
are strictly less than the number of rows and columns in the Sparse
Matrix: e.g., if the Sparse Matrix specifies 3 rows, then all the
row indexes must be 0, 1, or 2.
 The row and column in each triple must be unique (not repeated).
Raise an exception on just the first duplicate index (if there are any):
you don't have to find all the duplicates, just raise an exception on
the first.
 The value in each triple must be numeric (an int or float).
For example, in my code writing Sparse_Matrix(3,2, (0,0,1), (0,0,2))
raises
AssertionError with the message
Sparse_Matrix.__init__: repeated index (0, 0).
 Define a size method that returns a 2tuple containing the row and
column size of a Sparse Matrix.
For m = Sparse_Matrix(3,2) (a Sparse Matrix filled with 0s, so
its dictionary is empty) m.size() returns (3,2).
You will find this method useful when you write later methods, to check
for compatible sizes for Sparse Matrices.
 Define a __len__ method that returns the number of values (counting
all nonzero and 0 values) in the Sparse Matrix: it returns
the product of the number of rows and columns.
 Define a __bool__ method that returns False if the
Sparse_Matrix object stores all zero values; it returns
True if it returns any nonzero values.
Recall that the dictionary stores only non0 values.
 Define a __repr__ method that returns a string, which when
passed to eval returns a newly constructed Sparse_Matrix
object that represents the same Sparse_Matrix object on which
__repr__ was called.
For example, if we define
m = Sparse_Matrix(3,3, (0,0,1), (1,1,1), (2,2,1)), calling
repr(m) returns something like
'Sparse_Matrix(3, 3, (0, 0, 1), (1, 1, 1), (2, 2, 1))', although
the order of the 3tuples doesn't matter.
Hint:I used Python's join function to construct a string of
all the 3tuple values that appear near the end of what repr
returns.
 The following three methods are all similar in structure.
You will find it useful to call these methods implicitly (using []
indexing) in other methods/operators you are asked to define below; but doing
so is not necessary.
Hint 1: d.get(key,default) returns d[key] if key
is in the dictionary d and returns default if key is
not in the dictionary d.
Hint 2: writing m[0,0] calls
Sparse_Matrix.__getitem__(m,(0,0)): i.e., the arguments 0,0
in m[...] are passed as the 2tuple (0,0) to
__getitem__.
 Define a __getitem__ method whose argument is row,column 2tuple; it
returns the value of the Sparse Matrix at that row and column.
If the type of the argument is not a 2tuple, whose first and second
indexes are integers specifying a legal row then column in the Sparse
Matrix, then raise a TypeError exception with an appropriate
message.
 Define a __setitem__ method whose arguments are a row,column 2tuple
and a value; it updates the value for that row,column.
If the type of the first argument is not a 2tuple whose first and second
indexes are integers specifying a legal row then column in the Sparse
Matrix, then raise a TypeError exception with an appropriate
message.
Also, if the value argument is not numeric (not an int or
float), then raise a TypeError exception with an
appropriate message.
Otherwise update the Sparse Matrix to store the value at the row,column key.
Hint: if the value argument is equal to 0, update the
dictionary only if it currently stores a nonzero value at that
row,column key by removing the the row,column key from the dictionary.
This method can mutate the state of a Sparse Matrix.
 Define a __delitem__ method whose argument is row,column 2tuple; it
deletes that row,column key from the Sparse Matrix; it is equivalent to
storing a zero at that row,column key.
If the type of the argument is not a 2tuple, whose first and second
indexes are integers specifying a legal row then column in the Sparse
Matrix, then raise a TypeError exception with an appropriate
message.
This method can mutate the state of a Sparse Matrix.
 The following two methods are similar in structure.
You will find it useful to call these methods in other methods/operators you
are asked to define below (specifically, in the details and
__mul__ methods); but doing so is not necessary.
In the examples directly below we define m so that str(m) is
3x3:[0 2 3
4 0 6
7 8 0]
Define the following two methods:
 The row method that takes one int argument: it returns
a tuple containing all the values in that row (from left to right).
Using m defined above, m.row(0) returns (0, 2, 3);
m.row(1) returns (4, 0, 6); and
m.row(2) returns (7, 8, 0).
If the row argument is not an integer whose values specify a legal
row in the Sparse Matrix, raise an AssertionError with an
appropriate message.
 The col method that takes one int argument: it returns
a tuple containing all the values in that column (from top to bottom).
Using m defined above, m.col(0) returns (0, 4, 7);
m.col(1) returns (2, 0, 8); and
m.col(2) returns (3, 6, 0).
If the col argument is not an integer whose values specifies a legal
column in the Sparse Matrix, raise an AssertionError with an
appropriate message.
 Define the details method that returns a string of three pieces of
information about a Sparse_Matrix object, separated by > :
the size, the dictionary, and a tuple of all the rows (see the row
method above): row 0, row 1, etc.
If we define
m = Sparse_Matrix(3,3, (0,0,1), (1,1,5), (2,2,1)),
then the of calling m.details() is
'3x3 > {(0, 0): 1, (1, 1): 5, (2, 2): 1} > ((1, 0, 0), (0, 5, 0), (0, 0, 1))'
Of course, the keys in the dictionary (2nd part) can appear in any order, but
the tuples (3rd part) must occur in the exact order shown.
 I have defined a __str__ method that returns a string that nicely
displays a Sparse Matrix in a 2dimensional form.
I wrote this method to work even if __getitem__ is not
implemented correctly; it calls self.matrix.get((r,c),0), but if
__getitem were correctly implemented it would call only
self[r,c].
 Define a __call__ method that takes two int arguments,
specifying the new number of rows and columns in a Sparse Matrix; these
must each be integers that are strictly greater than 0; if not,
raise an AssertionError, similarly to what you did in the
__init__ method.
It modifies the Sparse Matrix by resetting its row and column size and
deleting all values from the dictionary whose indexes lie
outside the new size of the resized Sparse Matrix.
For example if we define
m = Sparse_Matrix(2, 2, (0,0,1),(0,1,1),(1,0,1),(1,1,1))
(a 2x2 Sparse Matrix filled with 1s) and we call m(1,1) then
m becomes a 1x1 Sparse Matrix whose dict matrix stores just
{(0,0): 1} because all the other indexes (that used to be in the
dict matrix) are now outside the size of Sparse Matrix.
This method mutates the state of a Sparse Matrix.
Hint: You cannot delete any keys in a dictionary while iterating
over it: iterate over a copy.
 Define an __iter__ method that produces 3tuples containing
the row, column, and value for each index in the Sparse Matrix that
stores a non0 value.
These values must be sorted by the value (from smallest to biggest).
For example, if we define
m = Sparse_Matrix(2, 2, (0,0,1),(0,1,3), (1,0,4), (1,1,2)))
which prints as
2x2:[1 3
4 2]
then iterating through it produces the tuples (0,0,1),
(1,1,2), (0,1,3), (1,0,4) in this order.
Hint: Write this method as a generator (covered in Friday's lecture
in Week 4).
 Define all the underscore methods needed to ensure the prefix +/ and
abs work correctly: + returns a new Sparse Matrix with the
same values;  returns a new Sparse Matrix with negated values
(not that 0 == 0); abs returns a new Sparse Matrix
with all nonnegative values.
Hint: I wrote each in 1 line, using a comprehension, and using
* to turn a list into arguments for a function call.
 Define all the underscore methods needed to ensure that the add, subtract,
and multiply operators produce the correct answers when their operands
are any combination of a Sparse_Matrix object with a
Sparse_Matrix, int, or float object.
If Python tries to apply an arithmetic operator to a Sparse_Matrix
object and any other type of value, raise the standard TypeError
exception with the standard messsage about unsupported operand types: see
what 1+'a' produces in the Python interpreter.
Recall that none of these operators mutate their operands: each produces a new
Sparse Matrix and returns it as a result.
Note that both + and * (but not ) are commutative when
applied to a Sparse Matrix and a numeric value.
Commutivity with numeric values can make programming these methods simpler;
so can using the infix  operator.
Hint: Create a Sparse Matrix that is the appropriate size, with no
initial non0 values; then fill in all its indexes with the correct
values: using __getitem__ and __setitem__ is simplest, for
computing the resulting Sparse Matrix, ensuring that the dictionary contains
no 0 values.
 To add two Sparse_Matrix objects, their sizes must be the
same; the the new resulting Sparse Matrix will be the same size as
both its operand Sparse Matrices, and its values are the pairwise
addition of the two Sparse Matrix values.
If we define m1 (on the left) and m2 (on the right) as follows
2x3:[1 2 3 2x3:[1 2 3
4 5 6] 4 5 1]
Then the result of adding these two Sparse Matrix objects (either m1+m2
or m2+m1) is the new Sparse Matrix object
2x3:[0 4 0
8 0 7]
For example, the value (0) in the resulting Sparse Matrix at row 0 and
column 0 is the sum of the value (1) in m1 at row 0 and column 0
plus the value (1) in m2 at row 0 and column 0.
This pattern repeats for all the other rows and columns in the resulting Sparse
Matrix.
To add a numeric value to a Sparse Matrix, the new resulting Sparse Matrix
will be the same size as the one operand that is a Sparse Matrix, and have
that numeric value added to each of the values in the argument Sparse Matrix.
If we define the Sparse Matrix m as follows
2x3:[1 0 1
2 0 2]
Then the result of adding 1 to this Sparse Matrix (1+m or
m+1: adding 1 on the left or on the right) is the new Sparse
Matrix
2x3:[ 0 1 2
1 1 3]
If the argument is not a Sparse Matrix or numeric value, raise a
TypeError with the appropriate information; if the argument is a
Sparse Matrix of a different size (see the size method), raise an
AssertionError with the appropriate information.
 To subtract two Sparse_Matrix objects, use the identity that
m1m2 = m1 + m2: the difference between m1 and
m2 is the sum of m1 and the negation (see part 13) of
m2.
 To multiply two Sparse Matrix objects, their sizes must be
compatible: the number of columns in the left Sparse
Matrix must be the same as the number of rows in the right Sparse
Matrix; the new resulting Sparse Matrix will have the number of
rows of the left Sparse Matrix and the number of
columns of the right Sparse Matrix.
The value in the resulting Sparse Matrix at row r and column c is
computed by adding together the pairwise products of all the values in row
r in the left Sparse Matrix and in column c in the right Sparse
Matrix.
If we define m1 (left) and m2 (right) as follows
2x3:[1 2 1 3x2:[0 1
2 1 2] 2 0
1 1]
Then the result of multiplying these two Sparse Matrix objects is the new Sparse
Matrix object
2x2:[5 2
4 4]
 The value at index (0,0) is the sum of the pairwise multiplication of
row 0 in m1 (1, 2, 1) and column 0 in m2 (0, 2, 1):
1*0 + 2*2 + 1*1 = 5.
 The value at index (0,1) is the sum of the pairwise multiplication of
row 0 in m1 (1, 2, 1) and column 1 in m2 (1, 0, 1):
1*1 + 2*0 + 1*1 = 2.
 The value at index (1,0) is the sum of the pairwise multiplication of
row 1 in m1 (2, 1, 2) and column 0 in m2 (0, 2, 1):
2*0 + 1*2 + 2*1 = 4.
 The value at index (1,1) is the sum of the pairwise multiplication of
row 1 in m1 (1, 2, 1) and column 1 in m2 (1, 0, 1):
1*1 + 2*0 + 1*1 = 4.
Hint: Use the row and col method specified in part 8.
To multiply a numeric value by a Sparse Matrix, the new resulting Sparse Matrix
will have that numeric value multiplied by each of the non0 values in
the Sparse Matrix.
If we define the Sparse Matrix m as follows
2x3:[1 0 1
2 0 2]
Then the result of multiplying 2 by this Sparse Matrix
(either 2*m or m*2; multiplying on the left or right)
is the new Sparse Matrix
2x3:[2 0 2
4 0 4]
Note that if the numeric value is 0 the Sparse Matrix will store all
0s.
If the argument is not a Sparse Matrix or numeric value, raise a
TypeError with the appropriate information; if the argument is a
Sparse Matrix that is not of a compatible size (see the size method),
raise an AssertionError with the appropriate information.
 Define all the underscore method needed to ensure that the power
operator (**) produces the correct answers when its left operand is a
square Sparse_Matrix object (same number of rows as columns) and
its right operand is restricted to be a nonnegative int object.
Compute the answer by using repeated multiplication.
If the power is not an int raise a TypeError; if the power is
less than 1 or the Sparse Matrix is not square, raise an
AssertionError.
 Python automatically provides meanings for +=, =,
*=, and **=.
 Define the relational operator == and !=.
These operators must work correctly when one operand is a Sparse Matrix and the
the other operand is a Sparse Matrix or a numeric value
(int or float).
For any other operands, return False for == and True for
!=.
Two Sparse_Matrix objects are considered equal if they have the
same sizes (see the size method) and pairwise the same values:
i.e., the value in row r,column c in one Sparse Matrix is equal to the value
in row r,column c in the other Sparse Matrix, for all rows and columns.
A Sparse Matrix is considered equal to a numeric value if the Sparse Matrix is
any size, but all its values are all equal to the numeric value; otherwise
they are unequal.
Hint for the numeric value comparison with ==:
 If the value to check is 0, there must be no values stored in the
dictionary representing the non0 values in the Sparse Matrix.
 If the value to check is non0, that value must be stored in every
index in the Sparse Matrix with this value: that is, every index must appear
in the matrix dict, because there must be no 0 values in the
Sparse Matrix.
 Define a __setattr__ method that ensures objects in the
Sparse_Matrix class cannot store new attributes: they store
only rows, cols, and matrix.
The methods you will write should never bind any instance names
(except in __init__, which initializes rows, cols,
and matrix) but exclusively returns newly constructed
Sparse_Matrix objects with the correct values.
If an attempt is made to add new attributes to an object (by defining a new
attribute or rebinding an existing attribute), raise an
AssertionError with an appropriate message.
Do not attempt to solve this part of the problem until all other parts
are working correctly.
Important: To solve this problem correctly, you must also find a way to
allow the __call__ method (which mutates rows and cols)
to work correctly; this is hard to do.
If you cannot, it best just to not write the __setattr__ method.
Testing
The Sparse_Matrix.py module includes a script that does some simple
matrix calculations and then calls driver.driver().
The project folder contains a bsc1.txt file (examine it) to use for
batchselfchecking your class.
These are rigorous but not exhaustive tests.
Incrementally write and test your class: for example, getting one arithmetic
operator working correctly will create a pattern for the others.
Note that when exceptions are raised, they are printed by the driver but the
Command: prompt sometimes appears misplaced.
You can also test code you type into the driver as illustrated below; but if you
want to perform the same test over and over again when debugging, it it
better to put this code in the script before the driver is called.
Notice the default for each command (printed in the square brackets) is the
command previously entered.
Driver started
Command[!]: from sparse_matrix import Sparse_Matrix as SM
Command[from sparse_matrix import Sparse_Matrix as SM]: m = SM(2,2,(0,0,0),(0,1,1),(1,0,2),(1,1,3))
Command[m = SM(2,2,(0,0,0),(0,1,1),(1,0,2),(1,1,3))]: print(m)
2x2:[0 1
2 3]
Command[print(m)]: print(m.details())
2x2 > {(0, 1): 1, (1, 0): 2, (1, 1): 3} > ((0, 1), (2, 3))
Command[print(m.details())]: print(m+m)
2x2:[0 2
4 6]
Command[print(m+m)]: print(m+1)
2x2:[1 2
3 4]
Command[print(m+1)]: print(m*m)
2x2:[ 2 3
6 11]
Command[print(m*m)]: quit
Driver stopped
