"""
Lattice class

"""

from vector import Vector
class LatticeError(Exception):
	"""Exception thrown by the Lattice class"""
	pass

class Lattice(object):
	"""Lattice given by a basis"""
#	from vector import Vector

	basis = None

	def __init__(self, basis):
		"""Initializes the lattice."basis" must be a non empty list of
		   vectors representing a basis"""
		if type(basis) is not list or \
			0 > len or \
			type(basis[0]) is not Vector :
			raise LatticeError("basis must be a non empty list of vectors representing a basis")
		else :
			self.basis = basis

	def dim(self):
		"Returns the lattice dimension"
		return len(self.basis)

	def gram_schmidt_coeffs(self):
		"""computes the Gram-Schmidt coefficients of this lattice"""
		# dimension of this lattice
		d = self.dim()
		# the orthogonalized basis
		bo = [None] * d
		# the Gram-Schmidt coefficients
		m = [[float(0) for i in xrange(d)] for j in xrange(d)]
		r = [None] * d
		
		s = None
		bo[0] = self.basis[0]
		r[0] = bo[0]*bo[0]
		for i in xrange(1,d):
			s = Vector([0]*d)
			for j in xrange(i):	
				m[i][j] = float((self.basis[i] * bo[j])) / float(r[j])
				s += m[i][j] * bo[j]
			bo[i] = self.basis[i] - s
			r[i] = bo[i] * bo[i]
		return (r, m, bo)

	def lll_reduced(self, delta, eta): 
		"Checks if the basis of this lattice is lll-reduced"
		reduced = True
		(r, m, bo) = lattice.gram_schmidt_coeffs()
		d = len(bo)
		for i in xrange(1,d):
			v = bo[i] + m[i][i-1]*bo[i-1]
			reduced &= \
				(delta * r[i-1]) <= (v * v)
			for j in xrange(i):
				reduced &= \
					abs(m[i][j]) < eta
		return reduced
	
	def __str__(self):
		"converts lattice basis to a string"
		s = "[\n"
		for i in xrange(self.dim()):
			s += " " + str(self.basis[i]) + "\n"
		s += "]"
		return s

	def __repr__(self): return NotImplemented

if __name__ == "__main__" :
#	from vector import Vector
	from test_bases import test_bases
	n = len(test_bases)
	for i in xrange(n):
		lattice = Lattice(test_bases[i])
		print "Dimension: "+str(len(test_bases[i]))
		n = 1; d = .5
		print "is ("+str(n)+", "+str(d)+")-lll-reduced: "+str(lattice.lll_reduced(n, d))
		#print lattice
		(r, m, bo) = lattice.gram_schmidt_coeffs()
		#print (r, m)
		d = len(bo)
		for k in xrange(d):
			for l in xrange(k):
				assert 0.0001 > bo[l] * bo[k]