def pad(self):
     '''
     padding to incomplete matrix
     '''
     
     l_rows = len(self)
     l_cols = len(self.rows[0])
     
     i = 1
     while(i<l_rows):
         i *= 2
        
     j = 1
     while(j<l_cols):
         j *= 2
             
     order = max(i,j)
     
     if((order - l_cols ) != 0):
         col = make_vector(([0] * (order - l_cols )), zero_test) 
         cols = []
         for i in range(l_rows):
             cols.append(col)
          
         colms = make_matrix(cols)
         self.merge_cols(colms)
     
     if((order - l_rows) != 0):        
         row = make_vector(([0] * order ),zero_test)
         rws = []
         for i in range((order - l_rows)):
             rws.append(row)
             
         rws1 = make_matrix(rws)
         self.merge_rows(rws1)

 def rmul(self, vec):
     '''
     Returns a vector that is the product of 'vec' (taken as a row vector) and this matrix using the * operator
     If the two are incompatible return None
     Return vec*self
     '''
     # Your Code
     new_list = []
     list_of_vectors = []
     prod = []
     if(len(self) <> len(vec)):
         return None
     else:
         lst = []
         for i in range(len(self)):
             for j in range(len(self[0])):
                 lst.append(self[j][i])
             new_list.append(lst)
             lst = []
         for lists in new_list:
             vect = make_vector(lists ,zero_test = lambda x : (x == 0))
             list_of_vectors.append(vect)
         new_matrix = make_matrix(list_of_vectors)
         for i in range(len(new_matrix)):
             prod.append(new_matrix[i]*vec)
         final_vector = make_vector(prod , zero_test = lambda x : (x == 0))
         return final_vector

 def get_quarters(self):
     '''
     Get all 4 quarters of the matrix - get the left-right split
     Then split each part into top and bottom
     Return the 4 parts - topleft, topright, bottomleft, bottomright - in that order
     '''
     # Your Code
     ele = [[],[],[],[]]
     for i in range(len(self)/2):
         ls = []
         for j in range(0, int(float(len(self))/2.0 + 0.5)):
             ls.append(self[i][j])
         ele[0].append( make_vector(ls) )
         ls = []
         for j in range(int(len(self)/2), len(self[i])):
             ls.append(self[i][j])
         ele[1].append( make_vector(ls) )
         ls = []
         for j in range(0, int(float(len(self))/2.0 + 0.5)):
             ls.append(self[len(self)/2 + i][j])
         ele[2].append( make_vector(ls) )
         ls = []
         for j in range(int(len(self)/2), len(self[i])):
             ls.append(self[len(self)/2 + i][j])
         ele[3].append( make_vector(ls) )
         ls = []
         
     #return make_matrix(ele[0]), make_matrix(ele[1]), make_matrix(ele[2]), make_matrix(ele[3])
     return Matrix(ele[0]), Matrix(ele[1]), Matrix(ele[2]), Matrix(ele[3])

 def form_pad(self):
     org_row_length = len(self[0])
     org_col_length = len(self)
     
     num_row = self.is_valid(len(self[0]))
     num_col = self.is_valid(len(self))
     num = num_row if (num_row > num_col) else num_col
     
     if(num != 0):
         for i in range(len(self)):
             temp_list = []
             for j in range(len(self[i])):
                 temp_list.append(self[i][j])
             
             if not is_long_and_sparse(temp_list):
                 self[i].merge(make_vector([0] * (num - org_row_length)))
             else:
                 self[i].length = self[i].length + (num - org_row_length)
                 
     temp = num - org_col_length
     ls = []
     while(temp > 0):
         ls.append(make_vector([0]*(len(self[0]))))
         temp -= 1
             
     self = self.merge_rows(ls)
     
     return self, num - org_row_length, num - org_col_length

 def __getitem__(self, key):
     '''
     Overriding the default __getitem__ method with behavior specific to sparse matrices
     '''
     # Your Code
     
     if isinstance(key, int):
         if key >= len(self):
             return None
         
         if len(self.indices) == 0 or len(self.vectors) == 0:                
             return make_vector([0] * self.ncols, lambda x: x == 0)
         
         idx = bisect_left(self.indices, key)
         
         return (make_vector([0] * self.ncols)               
                 if (idx == len(self.indices) or self.indices[idx] != key)
                     else self.vectors[idx])
         
     else:
         if key[0] >= len(self):
             return None
         
         idx = bisect_left(self.indices, key[0])
         
         return (0 if (idx == len(self.vectors)
                       or self.indices[idx] != key[0])
                 else self.vectors[idx][key[1]]) 

 def get_quarters(self):
     '''
     Get all 4 quarters of the matrix - get the left-right split
     Then split each part into top and bottommake_vector
     Return the 4 parts - topleft, topright, bottomleft, bottomright - in that order
     '''
     # Your Code
     topleft = []
     topright = []
     bottomleft = []
     bottomright = []
     left, right = self.left_right_split()
     for rowno in range(0, len(self)/2):
         if rowno in left.indices:
             topleft.append(left[rowno])
         else:
             topleft.append(make_vector([0]*(self.ncols/2) , lambda x : (x == 0)))
         if rowno in right.indices:
             topright.append(right[rowno])
         else:
             topright.append(make_vector([0]*(self.ncols - self.ncols/2), lambda x : (x == 0)))
     for rowno in range(len(self)/2, len(self)):
         if rowno in left.indices:
             bottomleft.append(left[rowno])
         else:
             bottomleft.append(make_vector([0]* (self.ncols/2), lambda x : (x == 0)))
         if rowno in right.indices:
             bottomright.append(right[rowno])
         else:
             bottomright.append(make_vector([0]*(self.ncols - self.ncols/2), lambda x : (x == 0)))
     return make_matrix(topleft), make_matrix(topright), make_matrix(bottomleft), make_matrix(bottomright)

 def get_quarters(self):
     '''
     Get all 4 quarters of the matrix - get the left-right split
     Then split each part into top and bottom
     Return the 4 parts - topleft, topright, bottomleft, bottomright - in that order
     '''
     # Your Code
     left_matrix , right_matrix = self.left_right_split()
     topleft = []
     topright = []
     bottomleft = []
     bottomright = []      
     mid = len(left_matrix) / 2
     for i in range(0 , mid):
         topleft.append(make_vector((left_matrix[i]) , lambda x : (x == 0)))
     for i in range(mid , len(left_matrix)):
         bottomleft.append(make_vector((left_matrix[i]) , lambda x : (x == 0)))
         
     mid = len(right_matrix) / 2
     for i in range(0 , mid):
         topright.append(make_vector((right_matrix[i]) , lambda x : (x == 0)))
     for i in range(mid , len(left_matrix)):
         bottomright.append(make_vector((right_matrix[i]) , lambda x : (x == 0)))
         
     return make_matrix(topleft) , make_matrix(topright) , make_matrix(bottomleft) , make_matrix(bottomright)

 def pad(self, add_temp):
     zero_add = [0]*(add_temp - self.ncols)
     zero_vec = make_vector(zero_add,lambda x:x==0)
     zero_mat = [0]*add_temp
     mat_vec = make_vector(zero_mat,lambda x:x==0)
     for i in range(0,len(self)):
         self[i].merge(zero_vec)
     for i in range(add_temp - self.nrows):
         self.vectors.append(mat_vec)

 def __getitem__(self, key, ):
     '''
     Overriding the default __getitem__ method with behavior specific to sparse matrices
     '''
     # Your Code
     if key in self.indices:
         return self.vectors[self.indices.index(key)]
     elif self.vectors != []:
         return make_vector([0]*len(self.vectors[0]))
     else:
         return make_vector([0]*len(self))

 def __add__(self, mat):
     '''
     Return the sum of this matrix with 'mat' - (allows use of + operator between matrices)
     Return None if the number of rows do not match
     '''
     if len(self) != len(mat):
         return None
     s_matrix = []
     for i in range(len(self)):
         s_matrix.append(make_vector(self[i], zero_test = lambda x : (x == 0))+make_vector(mat[i],zero_test = lambda x : (x == 0) ))
     sum_mat = make_matrix(s_matrix)
     return sum_mat

 def __rmul__(self, vec):
     '''
     Returns a vector that is the product of 'vec' (taken as a row vector) and this matrix using the * operator
     If the two are incompatible return None
     Return vec*self
     '''
     if(len(vec) == self.nrows):
         transposed_matrix = make_matrix([make_vector(list(column), vec.zero_test) 
                              for column in itertools.izip(*self.components())])
         return make_vector([(vec * row) for row in transposed_matrix.components()], vec.zero_test)
     else:
         return None

 def __sub__(self, mat):
     '''
     Return the difference between this matrix and 'mat' - (allows use of - operator between matrices)
     Return None if the number of rows do not match
     '''
     if len(self) != len(mat):
         return None
     sub_mat = []
     for i in range(len(self)):
         sub_mat.append(make_vector(self[i],zero_test = lambda x : (x == 0)) - make_vector(mat[i], zero_test = lambda x : (x == 0)))
     sub_matrix = make_matrix(sub_mat)
     return sub_matrix

 def __iadd__(self, mat):
     '''
     Implements the += operator with another matrix 'mat'
     Assumes that the elements of the matrices have a + operator defined between them (if they are not numbers)
     Add corresponding elements upto the min of the number of rows in each (in case the matrices
     have different numbers of rows)
     '''
     
     lst_iadd = []
     for i in range(0 , min(len(self) , len(mat))):
         v1 = make_vector(self[i] , lambda x : (x == 0))
         v2 = make_vector(mat[i] , lambda x : (x == 0))
         v1 += v2
         lst_iadd.append(v1)
     
     return make_matrix(lst_iadd)

def make_matrix(vector_list):
    '''
    Make a matrix out of a list of vectors 'vector_list'
    Just like make_vector in the vector module, this decides whether to instantiate the FullMatrix or SparseMatrix class
    by using the is_zero method of the Vector class
    '''
    # Your Code
    
    matrix_vec_val = []
    sparse_val = []
    sparse_ind = []

    for idx , i in enumerate(vector_list):
        matrix_val = []
        for j in range(0 , len(i)):
            columns = len(i)
            matrix_val.append(i[j])
        
        if(i.is_zero() == False):
            
            sparse_val.append(i)
            sparse_ind.append(idx)
        
        matrix_vec_val.append(make_vector(matrix_val , lambda x : (x == 0)))
            
    if float(len(sparse_val))/float(len(vector_list)) < DENSITY_THRESHOLD and float(len(vector_list) * columns) > SIZE_THRESHOLD:
        obj = SparseMatrix(sparse_val , sparse_ind , len(vector_list),columns)
    else :
        obj = FullMatrix(matrix_vec_val)
         
    return obj

 def __mul__(self, mat):
     '''
     Multiplication of two matrices using Strassen's algorithm
     If either this matrix or mat is a 'small' matrix then do regular multiplication
     Else use recursive Strassen's algorithm
     '''
     matrix = []
     if (self.is_small() or mat.is_small == True):
         for i in range(len(self)):
             rows = []
             for j in range(len(mat[0])):
                 val = 0
                 for k in range(len(mat[0])):
                     val += self[i][k] * mat[k][j]
                 rows.append(val)
             matrix.append(make_vector((rows) , zero_test=lambda x : (x == 0)))
         return make_matrix(matrix)
     else:
         topleft , topright , bottomleft , bottomright = self.get_quarters()
         top_left , top_right , bottom_left , bottom_right = mat.get_quarters()
         val1 = topleft * (top_right - bottom_right)
         val2 = (topleft + topright) * bottom_right
         val3 = (bottomleft + bottomright) * top_left
         val4 = bottomright * (bottom_left - top_left)
         val5 = (topleft + bottomright) * (top_left + bottom_right)
         val6 = (topright - bottomright) * (bottom_left + bottom_right)
         val7 = (topleft - bottomleft) * ( top_left + top_right)          
         row1 = val4+val5+val6-val2
         row2 = val1+val2
         row3 = val3+val4
         row4  = val1-val3+val5-val7
         col1 = row1.merge_cols(row2)
         col2 = row3.merge_cols(row4)
         mat = col1.merge_rows(col2)
         return mat

def make_matrix(vector_list):
    '''
    Make a matrix out of a list of vectors 'vector_list'
    Just like make_vector in the vector module, this decides whether to instantiate the FullMatrix or SparseMatrix class
    by using the is_zero method of the Vector class
    '''
    # Your Code
    matrix2 = []
    count = 0
    for i in range(len(vector_list)):
        ls = []
        for j in range(len(vector_list[i])):
            ls.append( vector_list[i][j] )
        if (isinstance(ls, list)):
               ls = make_vector(ls)
        if(ls.is_zero()):
            count += 1
        matrix2.append(ls) 
    
    if float(count) / float(len(vector_list)) >= DENSITY_THRESHOLD:
        indices = []
        val_vectors = []
        for i in range(len(matrix2)):
            if(matrix2[i].is_zero() == False):
                val_vectors.append(matrix2[i])
                indices.append(i)
        mat = SparseMatrix(val_vectors, indices, len(matrix2))
    else:
        mat = FullMatrix(matrix2)
    
    return mat

def make_matrix(vector_list):
    '''
    Make a matrix out of a list of vectors 'vector_list'
    Just like make_vector in the vector module, this decides whether to instantiate the FullMatrix or SparseMatrix class
    by using the is_zero method of the Vector class
    '''
    # Your Code
    count = 0
    matrix = []
    vect_matrix = []
    for vect in vector_list:
        vect_matrix.append(make_vector(vect, zero_test = lambda x : (x == 0)))
    count = 0
    if len(vect_matrix) > 2:
        for vect in vect_matrix:
            
            if vect.is_zero():
                count += 1
        if count/len(vect_matrix) <= DENSITY_THRESHOLD:
            vect_list = []
            indices = []
            for ind in range(len(vect_matrix)):
                if vect_matrix[ind].is_zero() == False:
                    vect_list.append(vect_matrix[ind])
                    indices.append(ind)
            matrix = SparseMatrix(vect_list, indices, len(vect_matrix))
            return matrix
    
    matrix = FullMatrix(vect_matrix)
    return matrix

def pad_matrix(vector_list):
    '''
    To pad the matrix
    '''
    nrow_pad = int(pow(2, ceil(log(len(vector_list), 2))))
    ncol_pad = int(pow(2, ceil(log(len(vector_list[0]), 2))))
    zero_append.append(len(vector_list)) 
    zero_append.append(len(vector_list[0])) 
    if nrow_pad == len(vector_list) and ncol_pad == len(vector_list[0]):
        return vector_list
    new_list = [[0]*ncol_pad]*len(vector_list)
    
    for i in range(len(vector_list)):
        for j in range(len(vector_list[0])):
            new_list[i][j] = vector_list[i][j]
    
    i = 0
    while( i < nrow_pad-len(vector_list)):
        new_list.append([0]*len(new_list[0]))
        i += 1
    
    vect_list = []
    for i in new_list:
        vect_list.append(make_vector(i, zero_test = lambda x : (x == 0)))
            
    return vect_list

 def pad_row(self):
     '''
     Pad the rows of this matrix to the nearest power of 2 
     '''
     
     pad = 2             
     
     while pad < self.nrows:
         pad = pad << 1
            
     pad -= self.nrows
     
     if var_globals.FLAG_ROW == 0:
         var_globals.FLAG_ROW += 1
         var_globals.ROW_LENGTH = self.nrows
    
     if pad != 0:
         if var_globals.ROW_PAD == 0:
             var_globals.ROW_PAD = pad
         
         pad_vector = [make_vector([0] * self.ncols)
                     for _ in range(pad)]                
         
         new_mat = self.merge_rows(make_matrix(pad_vector))
         t_list = [new_mat[i] for i in range(len(new_mat))]
         
         return make_matrix(t_list)
     
     else:
         return self        

 def pad_col(self):
     '''
     Pad the columns of this matrix to the nearest power of 2
     '''
             
     pad = 2               
     
     while pad < self.ncols:
         pad = pad << 1
          
     pad -= self.ncols
     
     if var_globals.FLAG_COL == 1:
         var_globals.COL_LENGTH = self.ncols
     
     var_globals.FLAG_COL += 1
    
     if pad != 0:
         var_globals.COL_PAD = pad
                   
         pad_vector = [make_vector([0] * pad)
                     for _ in range(self.nrows)]
         
         new_mat = self.merge_cols(make_matrix(pad_vector))
         
         t_list = [new_mat[i] for i in range(len(new_mat))]
         
         return make_matrix(t_list)
     
     else:
         return self