import copy

# HillClimb.py
# A heuristic search for finding the optimal solution for a pairwise (strength 2) cover.

STRENGTH = 2

class HillClimb:
	def __init__(self, dv):
		self.domainVector = dv
		self.pairSet = []
		
	# Yields test tuples from the given domains.
	def gen(self):
		if len(self.domainVector) == 1:
			for i in self.domainVector[0]:
				yield [i]
		else:
			# calculate all pairs
			self.pairSet = self.makePairs()
			# yield first tuple and remove from pairs
			tpl = [domain[0] for domain in self.domainVector]
			yield tpl
			self.removePairs(tpl)

			# perform hill climbing while there are pairs to add
			while len(self.pairSet) > 0:
				# create initial tuple
				p = self.pairSet[0]
				tpl = []
				indices = [d[1] for d in p]
				values = [d[0] for d in p]
				for i in xrange(len(self.domainVector)):
					if i in indices:
						tpl.append( values[indices.index(i)] )
					else:
						tpl.append(self.domainVector[i][0])
			
				# see if there is a better tuple by analyzing neighbours of tpl
				numPairs = 0
				maxTuple = tpl
				maxPairs = self.numPairs(tpl)
				# print "First maxPairs " + str(maxPairs)
				while numPairs < maxPairs:
					numPairs = maxPairs
					tpl = maxTuple
					# try to find new tuple and better newPairs2
					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 newPairs value as it may be recalculated many times
							newPairs = self.numPairs(newTuple)
							if newPairs > maxPairs:
								maxPairs = newPairs
								maxTuple = newTuple
								
				# yield new tuple
				yield tpl
#				print self.pairSet
#				print len(self.pairSet)
#				raise SystemExit, 1
				self.removePairs(tpl)
	
	# Add pairs generated by a new domain to the pairSet
	def makePairs(self):
		pairs = []
		# Create the first element in the pair.
		for i in xrange(len(self.domainVector)-STRENGTH+1):
			d1 = self.domainVector[i]
			for i1 in xrange(len(d1)):
				e1 = (d1[i1], i)
				# Add elements from subsequent domains.
				for j in xrange(i+1, len(self.domainVector)):
					d2 = self.domainVector[j]
					for j1 in xrange(len(d2)):
						e2 = (d2[j1], j)
						p = (e1, e2)
						pairs.append(p)
		return pairs
	
	# Remove pairs that are in tuple from the pairSet
	def removePairs(self, tpl):
		for i in xrange(len(tpl)-1):
			e1 = (tpl[i], i)
			for j in xrange(i+1, len(tpl)):
				e2 = (tpl[j], j)
				p = (e1, e2)
				try:
					self.pairSet.remove(p)
				except ValueError:
					pass
	
	# Count pairs that are in tuple from the pairSet
	def numPairs(self, tpl):
		count = 0
		for i in xrange(len(tpl)-1):
			e1 = (tpl[i], i)
			for j in xrange(i+1, len(tpl)):
				e2 = (tpl[j], j)
				p = (e1, e2)
				if p in self.pairSet:
					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)
	'''

	domainVector = [
		range(0,4,2),
		range(0,6,2),
		range(0,6,2),
		range(0,4,2)
		]
	hc = HillClimb(domainVector)
	
	for tpl in iter(hc):
		print str(tpl)

				