import copy

# HillClimb3.py
# A heuristic algorithm for finding a strength 3 cover.

class HillClimb:
	
	def __init__(self, dv):
		self.domainVector = dv
		self.tripleSet = []
		
	# Yields test tuples from the given domains.
	def gen(self):
		if len(self.domainVector) == 1:
			for i in self.domainVector[0]:
				yield [i]
		# TODO: What if number of domains == 2??
		else:
			# calculate all triples
			self.tripleSet = self.makeTriples()
#			print self.tripleSet
#			print len(self.tripleSet), "triples to cover."
		
			# yield first tuple and remove from triples
			tpl = [domain[0] for domain in self.domainVector]
			yield tpl
			self.removeTriples(tpl)
#			print len(self.tripleSet), "triples remaining."

			# perform hill climbing while there are triples to add
			while len(self.tripleSet) > 0:
				# create initial tuple
				p = self.tripleSet[0]
				tpl = []
				# Create a map from domain indexes -> domain values for domains in this tuple
				indexHash = dict([(d[1],d[0]) for d in p])
				for i in range(len(self.domainVector)):
					if i in indexHash:
						tpl.append(indexHash[i])
					else:
						tpl.append(self.domainVector[i][0])
			
				# see if there is a better tuple by analyzing neighbours of tpl
				numTriples = 0
				maxTuple = tpl
				maxTriples = self.numTriples(tpl)
				# print "First maxTriples " + str(maxTriples)
				while numTriples < maxTriples:
					numTriples = maxTriples
					tpl = maxTuple
					# try to find new tuple and better newTriples2
					for i in xrange(len(tpl)):
						domain = self.domainVector[i]
						for j in xrange(len(domain)):
							newTuple = copy.copy(tpl)
							newTuple[i] = domain[j]
							# OPTIMIZATION NOTE: Could cache newTriples value as it values may be recalculated many times
							newTriples = self.numTriples(newTuple)
							if newTriples > maxTriples:
								maxTriples = newTriples
								maxTuple = newTuple
								
				# yield new tuple
				yield tpl
				self.removeTriples(tpl)
	
	# Add triples generated by a new domain to the tripleSet
	def makeTriples(self):
		triples = []
		# Create the first element in the triple.
		for i in range(len(self.domainVector)-2):
			d1 = self.domainVector[i]
			for i1 in xrange(len(d1)):
				e1 = (d1[i1], i)
				# Get all possibilities for second element in the triple.
				for j in range(i+1, len(self.domainVector)-1):
					d2 = self.domainVector[j]
					for j1 in xrange(len(d2)):
						e2 = (d2[j1], j)
						# Add elements from subsequent domains.
						for k in range(j+1, len(self.domainVector)):
							d3 = self.domainVector[k]
							for k1 in xrange(len(d3)):
								e3 = (d3[k1], k)
								p = (e1, e2, e3)
								triples.append(p)
		return triples
	
	# Remove triples that are in tuple from the tripleSet
	def removeTriples(self, tpl):
		for i in xrange(len(tpl)-2):
			e1 = (tpl[i], i)
			for j in xrange(i+1, len(tpl)-1):
				e2 = (tpl[j], j)
				for k in xrange(j+1, len(tpl)):
					e3 = (tpl[k], k)
					p = (e1, e2, e3)
					try:
						self.tripleSet.remove(p)
					except ValueError:
						pass
	
	# Count triples that are in tuple from the tripleSet
	def numTriples(self, tpl):
		count = 0
		for i in xrange(len(tpl)-2):
			e1 = (tpl[i], i)
			for j in xrange(i+1, len(tpl)-1):
				e2 = (tpl[j], j)
				for k in xrange(j+1, len(tpl)):
					e3 = (tpl[k], k)
					p = (e1, e2, e3)
					if p in self.tripleSet:
						count += 1
		return count

	# Make this object iterable
	def __iter__(self):
		return self.gen()

if __name__ == "__main__":
	'''
	for numElem in xrange(10):
		for numVec in xrange(4):
			domain = range(0,numElem+1)
			domainVector = []
			for i in xrange(numVec+1):
				domainVector.append(copy.copy(domain))
			
			# Call Hillclimb
			hc = HillClimb(domainVector)
						
			for tpl in iter(hc):
				print str(tpl)
	'''
	'''
	domainVector = [
		range(100,110),
		range(200,210),
		range(300,310),
		range(400,410)
		]
	hc = HillClimb(domainVector)
	
	for tpl in iter(hc):
		print str(tpl)
	'''

	# 3-cover of this should give Cartesian product.
	domainVector = [ range(2), range(3), range(2) ]
	
	# Kuhn1
	kuhn1 = [ range(2), range(2), range(2), range(2), range(2), range(2), range(2), range(2), range(2), range(4), range(4), range(4) ]

	# Kuhn2
	kuhn2 = [ range(2), range(2), range(2), range(2), range(2), range(2), range(2), range(2), range(2), range(2), range(2), range(2) ]
	
	# Kuhn3
	kuhn3 = [ range(4), range(4), range(4), range(4), range(4), range(4), range(4), range(4), range(4), range(4), range(4), range(4) ]
	
	# Kuhn4
	kuhn4 = [ range(3), range(3), range(3), range(3), range(3), range(3), range(3), range(3), range(3), range(3), range(3), range(3) ]

#	domainVector = [range(0,4,1),range(0,6,1),range(0,6,1),range(0,4,1)]
	
	hc = HillClimb(kuhn4)
	
	# Print out results in a format compatible with hsat -----
	
	# First line is list of domain sizes
	print " ".join([str(len(dom)) for dom in kuhn4])
	
	# Subsequent lines are tuples in cover set.
	i=0
	for tpl in iter(hc):
		i += 1
		strtpl = [str(elem) for elem in tpl]
		print " ".join(strtpl)
		
#	print i, "results total."
