from matutil import mat2rowdict
from triangular import triangular_solve
from QR import factor

def QR_solve(A, b):
  '''
  Input:
      - A: a Mat
      - b: a Vec
  Output:
      - vector x that minimizes norm(b - A*x)
  Example:
      >>> domain = ({'a','b','c'},{'A','B'})
      >>> A = Mat(domain,{('a','A'):-1, ('a','B'):2,('b','A'):5,
          ('b','B'):3,('c','A'):1,('c','B'):-2})
      >>> Q, R = QR.factor(A)
      >>> b = Vec(domain[0], {'a': 1, 'b': -1})
      >>> x = QR_solve(A, b)
      >>> result = A.transpose()*(b-A*x)
      >>> result * result < 1E-10
      True
  '''
  Q,R = factor(A)
  c = Q.transpose() * b
  return triangular_solve(mat2rowdict(R),sorted(A.D[1], key=repr),c)

