#!/usr/bin/python

import string
import random

# translation table for complementing strands
COMPL_TR = string.maketrans("AGCT", "TCGA")
BASES = [ "A", "G", "C", "T" ]

def randomStrand( length ):
	strand = ""
	for n in range( 0, length ):
		strand = strand + random.choice( BASES )
	return strand

# returns the "complement" of the DNA strand given
def complement(strand):
	return string.translate(strand, COMPL_TR)

# returns true if the strand starts with the given pattern
def startsWith(strand, pattern):
	return string.find(strand, pattern) == 0

# returns true if the stand ends with the given pattern
def endsWith(strand, pattern):
	return string.rfind(strand, pattern) + len(pattern) == len(strand)

# return true if the strand contains the given pattern
def contains(strand, pattern):
	return string.find( strand, pattern ) != -1

def lengthEquals(strand, length):
	return len( strand ) == length
	
def lengthGreaterThan(strand, length):
	return len( strand ) > length

def lengthLessThan(strand, length):
	return len( strand ) < length

def seperate( testtube, matchFunc, arg, matching, notmatching ):
	for strand in testtube:
		if matchFunc( strand, arg ):
			matching.append( strand )
		else:
			notmatching.append( strand )

def merge( testtube1, testtube2 ):
	return testtube1 + testtube2
	
def removeDuplicates( testtube ):
	strands = {}
	for strand in testtube:
		strands[ strand ] = ""
	return strands.keys()

def generateAllPathsWithCache( vertices, edgeMap, subPathCache ):
	allPaths = []
	
	# should probably just use a tuple for vertices instead of a list
	# it would help speed thing up a bit
	if len( vertices ) != 0:
		for vi in range( 0, len( vertices ) ):
			vertex = vertices[ vi ]
			allPaths.append( [ vertex ] )
			if edgeMap.has_key( vertex ):
				remainingVertices = vertices[:] # copy vertices
				del remainingVertices[ vi ]
				# can't use a list as a key, must be a list
				vertTuple = tuple( remainingVertices )
				if not subPathCache.has_key( vertTuple ):
					remainingPaths = generateAllPathsWithCache( remainingVertices, edgeMap, subPathCache )
					subPathCache[ vertTuple ] = remainingPaths
				else:
					remainingPaths = subPathCache[ vertTuple ]
				for path in remainingPaths:
					pathStart = path[ 0 ]
					# see if this vertex is connected to the path
					if pathStart in edgeMap[ vertex ]:
						allPaths.append( [ vertex ] + path )
	
	return allPaths

def generateAllPaths( vertices, edgeMap ):
	return generateAllPathsWithCache( vertices, edgeMap, {} )

def generateAllVertexEdgePatterns( vertexPatterns, vertices, edgeMap ):
	allPaths = generateAllPaths( vertices, edgeMap )
	allPatterns = [];
	for path in allPaths:
		allPatterns.append( string.join( map( (lambda x, patterns=vertexPatterns: patterns[ x ]), path ) , "" ) )
	return allPatterns

# returns a list with the index of the patterns as they appear in the strand
def sequence( strand, patterns ):
	indices = []
	while len( strand ) > 0:
		for i in range( 0, len( patterns ) ):
			pattern = patterns[ i ]
			if startsWith( strand, pattern ):
				indices.append( i )
				strand = strand[ len( pattern ): ]
				# maybe should break here, but not essential
	return indices