#!/usr/bin/python

import DNASim
import string

def assembleGraph( v, a0, a1 ):
	graph = {}
	for i in range( 0, len(v)-1 ):
		vi = v[ i ]
		a0i = a0[ i ]
		a1i = a1[ i ]
		vi1 = v[ i+1 ]
		graph[ vi ] = [ a0i, a1i ]
		graph[ a0i ] = [ vi1 ]
		graph[ a1i ] = [ vi1 ]
	return graph
		
def filterNOT( isnot, i, a0, a1, patterns, N ):
	if isnot:
		pattern = patterns[ a0[ i ] ]
	else:
		pattern = patterns[ a1[ i ] ]
	N1 = []
	N2 = []
	DNASim.seperate( N, DNASim.contains, pattern, N1, N2 )
	return N1

def toBooleans( a0, a1, patterns, strand ):
	indices = DNASim.sequence( strand, patterns )
	bools = []
	for i in indices:
		if i in a0:
			bools.append( 0 )
		elif i in a1:
			bools.append( 1 )
	return bools

def extractVariables( formula ):
	vars = []
	for clause in formula:
		for literal in clause:
			if string.find( literal, "~" ) == 0:
				var = literal[1:]
			else:
				var = literal
			if not var in vars:
				vars.append( var )
	return vars

# form of ( clause, clause, clause, ... ) [ or's ]
# clause = ( literal, notliteral, ... ) [ and's ]
#
def run( formula = [ [ "x1", "x2", "~x3" ] ] ):
	

	print formula 
	vars = extractVariables( formula )
	print vars
	
	numValues = len( vars )
	v = range( 0, numValues+1 )
	a0 = range( numValues+1, 2*numValues +1 )
	a1 = range( 2*numValues +1, 3*numValues +1 )
	numVertices = len( v ) + len( a0 ) + len( a1 )
	
	print "Assembling graph"
	graph = assembleGraph( v, a0, a1 )
	print graph
	
	patterns = []
	for i in range( 0, numVertices ):
		patterns.append( DNASim.randomStrand( 20 ) )
		
	# make all paths
	print "Generating all paths"	
	N = DNASim.generateAllVertexEdgePatterns( patterns, range( 0, numVertices ), graph )
	
	print "%d candidates" % len(N)
	
	print "Filter by start pattern"

	N1 = []
	N2 = []
	DNASim.seperate( N, DNASim.startsWith, patterns[ v[ 0 ] ], N1, N2 )
	N = N1
	
	print "%d candidates" % len(N)	
	
	print "Filter by end pattern"

	N1 = []
	N2 = []
	DNASim.seperate( N, DNASim.endsWith, patterns[ v[ -1 ] ], N1, N2 )
	N = N1
	
	print "%d candidates" % len(N)	
	
	FN = []
	
	for clause in formula:
		CN = N[:]
		for literal in clause:
			if string.find( literal, "~" ) == 0:
				var = literal[1:]
				pattern = patterns[ a0[ vars.index( var ) ] ]
			else:
				var = literal
				pattern = patterns[ a1[ vars.index( var ) ] ]
				
			N1 = []
			N2 = []
			DNASim.seperate( CN, DNASim.contains, pattern, N1, N2 )
			CN = N1
		FN = DNASim.merge( FN, CN )
	
	N = DNASim.removeDuplicates( FN )
	
	for strand in N:
		bools = toBooleans( a0, a1, patterns, strand )
		assignment = ""
		for i in range( 0, len( vars ) ):
			assignment = assignment + vars[ i ] + "=" + str( bools[ i ] ) + " "
		print assignment