def test_slice(self):
     A = Matrix([1, 2, 3, 4],
                [5, 6, 7, 9],
                [1, 2, 3, 4])
     s = A.slice(0, 2)
     self.assertEqual(s, Matrix(
         [3, 4], [7, 9], [3, 4]))

class MainWindow(Frame):

    def __init__(self, master, rows, columns):
        Frame.__init__(self, master)

        self.matrix = Matrix(master, rows, columns)
        self.matrix.grid(row=0, column=0)

        self.game = Game(rows, columns)
        self.game.set_matrix(self.matrix)

        self.start_button = Button(master, text="Start")
        self.start_button.grid(row=1, column=0)
        self.start_button["command"] = self.game.start_clicked

        self.quit_button = Button(master, text="Quit")
        self.quit_button.grid(row=1, column=1)
        self.quit_button["command"] = self.quit

        self.master = master
        master.title("Life")

        # override the "X" close button
        self.master.protocol("WM_DELETE_WINDOW", self.quit)

    def quit(self):
        print "quitting"
        self.game.quit_clicked()
        self.master.quit()

   def quad(self, g, quad):
      # Enable alpha blending/transparency
      self.vbuffer.sync()

      gl.glUseProgram(self.program.id)
      gl.glEnable(gl.GL_BLEND)
      gl.glEnable(gl.GL_DEPTH_TEST)
      gl.glBlendFunc(gl.GL_SRC_ALPHA, gl.GL_ONE_MINUS_SRC_ALPHA)
      
      # Bind texture
      gl.glUniform1i(self.program.tex, 0) 
      gl.glBindTexture(gl.GL_TEXTURE_2D, quad.texture.id)
      
      # Set up geometry transforms
      worldMatrix = Matrix.scale(quad.width, quad.height, 1) 
      worldMatrix = Matrix.translate(quad.x, quad.y, 0) * worldMatrix
      worldViewProjectionMatrix = g.viewProjectionMatrix * worldMatrix
      #worldViewProjectionMatrix = g.viewProjectionMatrix
      gl.glUniformMatrix4fv(self.program.worldViewProjectionMatrix, 1, 0, 
                            worldViewProjectionMatrix.data)

      # Draw geometry
      gl.glBindVertexArray(self.vao)
      gl.glDrawArrays(gl.GL_TRIANGLE_STRIP, 0, 4)
      gl.glBindVertexArray(0)

    def makeGraphFromEdges1(self, edges):
        """
        Constructs a directional graph from edges (a list of tuple).
        Each tuple contains 2 vertices.
        For example, P -> Q is written as ('P', 'Q').

        @param edges: edges
        @type edges: list of 2-element tuple

        @status: Tested method
        @since: version 0.1
        """
        if type(edges) != list: raise GraphParameterError('Edges must be a \
                                list of tuples')
        from Set import Set
        from Matrix import Matrix
        vertices = list(Set([x[0] for x in edges] + [x[1] for x in edges]))
        adj = Matrix(len(vertices))
        adj = adj.m
        for e in edges:
            row = vertices.index(e[0])
            col = vertices.index(e[1])
            # fill values into lower triangular matrix
            adj[row][col] = adj[row][col] + 1
        adj.insert(0, vertices)
        self.makeGraphFromAdjacency(adj)

def lanczos(A):
    k = len(A)

    b = Vector.rand(n=k)
    q = [Vector.new(n=k) for i in range(2)]
    q[1] = b / abs(b)

    b = [0]
    a = [0]

    for i in range(1, int(2 * sqrt(k))):
        z = Vector((A * q[i]).transpose()[0])
        a.append(float(Matrix([q[i]]) * z))
        z = z - q[i] * a[i] - q[i-1] * b[i-1]
        for j in q:
            z -= j * (z * j)
        for j in q:
            z -= j * (z * j)
        b.append(abs(z))
        if b[i] == 0:
            break
        q.append(z / b[i])

    Q = Matrix(q[-k-1:-1]).transpose()
    T = Q.transpose() * A * Q
    return (Q, T, )

 def get_matrix(self):
     rows, cols = self.get_size()
     matrix     = Matrix(rows, cols)
     for child in self.get_children():
         box = self.find_box_child(child)
         matrix.set(child, box.left, box.top, box.right, box.bottom)
     return matrix

 def makeGraphFromEdges2(self, edges):
     """
     Constructs an un-directional graph from edges (a list of tuple).
     Each tuple contains 2 vertices.
     An un-directional graph is implemented as a directional graph where
     each edges runs both directions.
     
     @param edges: list of edges
     @type edges: list of 2-element tuples"""
     if type(edges) != list: raise GraphParameterError('Edges must be a \
                             list of tuples')
     from Set import Set
     from Matrix import Matrix
     vertices = list(Set([x[0] for x in edges] + [x[1] for x in edges]))
     adj = Matrix(len(vertices))
     adj = adj.m
     for e in edges:
         row = vertices.index(e[0])
         col = vertices.index(e[1])
         # fill values into lower triangular matrix
         adj[row][col] = adj[row][col] + 1
         # repeat on the upper triangular matrix for undirectional graph
         adj[col][row] = adj[col][row] + 1
     adj.insert(0, vertices)
     self.makeGraphFromAdjacency(adj)

 def testSubtraction(self):
     
     testMatrix1 = Matrix()
     testMatrix2 = Matrix()
     
     testMatrix3 = testMatrix1 - testMatrix2
     
     for row in range(4):
         for col in range(4):
             self.assertTrue(testMatrix3.getValue(row, col) == 0)
             
     testMatrix1.setValue(0, 3, 2.5)
     testMatrix1.setValue(2, 2, 4.2)
     testMatrix1.setValue(3, 0, -301)
     
     testMatrix2.setValue(0, 3, -1)
     testMatrix2.setValue(0, 0, -2)
     testMatrix2.setValue(3, 0, 2)
     
     testMatrix4 = testMatrix1 - testMatrix2
     
     self.assertTrue(testMatrix4.getValue(0, 3) == 3.5)
     self.assertTrue(testMatrix4.getValue(2, 2) == 4.2)
     self.assertTrue(testMatrix4.getValue(3, 0) == -303)
     self.assertTrue(testMatrix4.getValue(0, 0) == 2.0)
     self.assertTrue(testMatrix4.getValue(2, 1) == 0)

    def set_covariance(self):
        for i in self.matrices:
            a = i.subtract(self.mean)
            a_transpose = Matrix(a.get_data())
            a_transpose.transpose()
            b = a_transpose.multiply(a)
            self.covariance = self.covariance.add(b)

        self.covariance.scaler(1 / len(self.matrices))

 def __init__(self):
     self.data = []
     self.matrices = []
     self.mean = Matrix([[0, 0]])
     self.covariance = Matrix([[0, 0], [0, 0]])
     self.setup()
     self.set_mean()
     self.set_covariance()
     print(len(self.matrices))

 def test_setrowcol(self):
     A = Matrix([1, 2, 3, 4],
                [5, 6, 7, 8])
     A.set_row(0, [4, 3, 2, 1])
     self.assertEqual(A, Matrix([4, 3, 2, 1],
                                [5, 6, 7, 8]))
     A.set_col(2, [9, 8])
     self.assertEqual(A, Matrix([4, 3, 9, 1],
                                [5, 6, 8, 8]))

 def reset(self):
     '''resets the whole sugarscape'''
     self.agents = []
     self.gov.tax_rate = self.tax_rate
     Matrix.__init__(self,51,51)
     self.agents = []
     self.populate_sugarscape()
     self.timestamp = 0
     return True

def cg(A,b):
	#guess x all 0s
	x = Matrix(i=A.columns,j=1)

	#set r and p
	r = b.subtract(A.multiply(x))
	p = b.subtract(A.multiply(x))
	
	r_norm_inf = 0
	for i in range(1,r.rows+1):
		v = r.get(i,1)
		if (v > r_norm_inf):
			r_norm_inf = v
	r_norm_2 = 0
	r_norm_2 = math.sqrt(r.transpose().multiply(r).get(1,1))
	
	iteration = 1
	
	while( r_norm_2 > LIMITERROR):
		p_t = p.transpose()
		alpha = p_t.multiply(r).get(1,1) /  p_t.multiply(A.multiply(p)).get(1,1)
		
		
		# a_p for alpha*p
		a_p = copy.deepcopy(p)
		for i in range(1,a_p.rows+1):
			for j in range(1,a_p.columns+1):
				a_p.set(i,j,a_p.get(i,j)*alpha)
		
		x = x.add(a_p)
		
		r = b.subtract(A.multiply(x))
		beta = -1 * (p_t.multiply(A.multiply(r)).get(1,1) / p_t.multiply(A.multiply(p)).get(1,1))

		
		# b_p for beta*p
		b_p = p #no need to copy (as we update cell by cell of p to b_p and we don't need it later)
		for i in range(1,b_p.rows+1):
			for j in range(1,b_p.columns+1):
				b_p.set(i,j,p.get(i,j)*beta)
		p = r.add(b_p)
		
		# compute r norms and f.write
		r_norm_inf = 0
		for i in range(1,r.rows+1):
			v = r.get(i,1)
			if (v > r_norm_inf):
				r_norm_inf = v
		
		r_norm_2 = math.sqrt(r.transpose().multiply(r).get(1,1))
		
		f.write(str(iteration)+","+str(r_norm_inf)+","+str(r_norm_2)+"\n")
		iteration+=1
	
	f.write(",,,"+str(iteration-1))
	return x

    def test_construction(self):
        m1 = Matrix(2, 3)
        self.assertEqual(m1.size(), [2, 3])
        # Verify the matrix is filled with 0s
        self.assertEqual(m1.data, [[0 for i in range(3)] for j in range(2)])

        m2 = Matrix([0, 1, 2], [3, 4, 5], [6, 7, 8])
        self.assertEqual(m2.size(), [3, 3])
        # Verify the matrix has values 0-8
        self.assertEqual(m2.data, [[(j * 3 + i) for i in range(3)] for j in range(3)])

    def test_multplication(self):
        # Test dot products

        # Row vectors
        v1 = Matrix([1, 2])
        v2 = Matrix([5], [6])
        self.assertEqual(v1 * v2, 17)
        self.assertEqual(v1 * [5, 6], 17)
        # Column vectors
        v1 = Matrix([10], [7])
        v2 = Matrix([5 ], [8])
        self.assertEqual(v1 * v2.transposed(), Matrix([50, 80], [35, 56]))

        # Test matrix scalar multiplication
        m = Matrix([1, 4, 5, 6], [3, 8, 9, 2], [9, 12, 4, 13])
        self.assertEqual((m * 4).data, [[(m[j][i] * 4) for i in range(m.cols)] for j in range(m.rows)])

        # Test matrix multiplication
        m1 = Matrix([2, 3], [4, 5], [6, 7])
        m2 = Matrix([1, 2, 3], [4, 5, 6])
        r = Matrix([14, 19, 24], [24, 33, 42], [34, 47, 60])
        self.assertEqual(m1 * m2, r)
        self.assertEqual(m1 * [[1, 2, 3], [4, 5, 6]], r)

        # Test swapping rows of a matrix with a permutation matrix
        m = Matrix([11, 9 , 24, 2],
                   [1 , 5 , 2 , 6],
                   [3 , 17, 18, 1],
                   [2 , 5 , 7 , 1])
        p = Matrix([1, 0, 0, 0], 
                   [0, 0, 1, 0],
                   [0, 0, 0, 1],
                   [0, 1, 0, 0])
        self.assertEqual(p * m, Matrix(
                   [11, 9 , 24, 2],
                   [3 , 17, 18, 1],
                   [2 , 5 , 7 , 1],
                   [1 , 5 , 2 , 6]))
        # Test swapping of cols of a matrix with the same permutation matrix
        self.assertEqual(m * p, Matrix(
                   [11, 2, 9 , 24 ],
                   [1 , 6, 5 , 2  ],
                   [3 , 1, 17, 18 ],
                   [2 , 1, 5 , 7  ]))
        # Multiplication of matrix with a matrix of 3 columns and list of 3 components
        self.assertEqual(
            Matrix([24 , 1, 8 ],
                   [6  , 0, 2 ],
                   [-12, 1, -3]) * Matrix([1], [9], [-2]), 
                   Matrix([17], [2], [3]))
        self.assertEqual(
            Matrix([24 , 1, 8 ],
                   [6  , 0, 2 ],
                   [-12, 1, -3]) * [1, 9, -2], 
                   Matrix([17], [2], [3]))

    def add_padding(self, padding, matrix):

        #validate inputs
        if (not type(padding) is int or padding <= 0 or not type(matrix) is Matrix):
            raise LedError("Invalid inputs. Padding must be a positive, non-zero integer")

        output = Matrix(matrix.m, padding)
        output = output.concatenate(matrix)
        output = output.concatenate(matrix.m, padding)

        return output

    def convert_message_led(self):

        checker = False
        output = Matrix(1,1)
        for char in self.message:
            temp = self.char_map[char]
            if (temp):
                if (checker):
                    output = output.concatenate(temp)
                else:
                    output.copy(temp)
                    checker = True
        return output

    def testCreation(self):

        testMatrix = Matrix()
        
        for row in range(4):
            for col in range(4):
                self.assertTrue(testMatrix.getValue(row, col) == 0)
                
        testMatrix.setValue(0, 0, 1.893)
        testMatrix.setValue(2, 1, -200.1)
        testMatrix.setValue(3, 2, 4)
        
        self.assertTrue(testMatrix.getValue(0, 0) == 1.893)
        self.assertTrue(testMatrix.getValue(2, 1) == -200.1)
        self.assertTrue(testMatrix.getValue(3, 2) == 4)

 def __init__(self, num_agents = 500, max_sugar=5, sugar_growth_rate=.5,
              agent_vision=3, agent_metabolism=4, tax_rate=.5):
     ''' The sugarscape is a matrix of Location objects.'''
     Matrix.__init__(self, 51, 51)
     self.max_sugar = max_sugar
     self.sugar_growth_rate = sugar_growth_rate
     self.agent_vision = agent_vision
     self.agent_metabolism = agent_metabolism
     self.tax_rate = tax_rate
     self.agents = []
     self.total_wealth = 0
     self.num_agents = num_agents
     self.timestamp = 0
     self.gov = Government(tax_rate=self.tax_rate, sugarscape=self)
     self.populate_sugarscape()

def QRalg(m):
    from copy import deepcopy as copy
    from math import cos, sin, atan, pi
    def get_rotate_matrix(n, i, j, angle):
        m = Matrix.new(n, n)
        for k in range(n):
            if k not in [i, j]:
                m[k][k] = 1
        s = sin(angle)
        c = cos(angle)
        m[i][j] = -s
        m[j][i] = s
        m[i][i] = c
        m[j][j] = c
        return m

    m = copy(m)
    n = len(m)

    u = Matrix.new(n, n)
    for i in range(n):
        u[i][i] = 1

    iter_n = 1
    f = True
    while f and iter_n < 1000:
        q = 0
        qi, qj = 0, 0
        for i in range(n):
            for j in range(n):
                if i != j and abs(m[i][j]) > q:
                    q, qi, qj = abs(m[i][j]), i, j
        angle = pi / 4
        if abs(m[qi][qi] - m[qj][qj]) > 0.000001:
            angle = atan(2 * m[qi][qj] / (m[qi][qi] - m[qj][qj])) / 2
        
        rm = get_rotate_matrix(n, qi, qj, angle)
        rmt = rm.transpose()
        nm = rmt * m * rm

        u = u * rm 

       #l.write('{}: '.format(iter_n))
       #l.write(nm)
        s = 0
        for i in range(n):
            for j in range(n):
                if i != j:
                    s += nm[i][j] ** 2

        f = abs(s) > (0.1 ** 5)
        m = copy(nm)
        iter_n += 1

    values = Vector([m[i][i] for i in range(n)])
    vectors = u.transpose()
    for i in range(len(vectors)):
        if abs(vectors[i][-1]) > 0.001:
            vectors[i] *= 1/vectors[i][-1]
    return (values, vectors, )