#! /usr/bin/env python

##############################################################################
##                                                                          ##
## mmstd_gen.py - Python Implementation of the MMSTD juggling Notation      ##
##                                                                          ##
##                                                                          ##
## Copyright (C) 2007  Frederic Roudaut  <frederic.roudaut@free.fr>         ##
##                                                                          ##
##                                                                          ##
## This program is free software; you can redistribute it and/or modify it  ##
## under the terms of the GNU General Public License version 2 as           ##
## published by the Free Software Foundation; version 2.                    ##
##                                                                          ##
## This program is distributed in the hope that it will be useful, but      ##
## WITHOUT ANY WARRANTY; without even the implied warranty of               ##
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU        ##
## General Public License for more details.                                 ##
##                                                                          ##
##############################################################################

MMSTD_VERSION = 'v1.5'

##
##  MMSTD graph as define by Mike Day :
##  
##    ######  --+o-->  ######
##    # Lr #           # Ll #
##    ######  <--o+--  ######   
##     ^  |             ^  |    
##     |  +             |  +    
##     o  |             o  |    
##     |  v             |  v    
##    ######  --+o-->  ######   
##    # Ul #           # Ur #   
##    ######  <--o+--  ######
##     ^  |             ^  |    
##     |  o             |  o    
##     +  |             +  |    
##     |  v             |  v    
##    ######  --+o-->  ######   
##    # Rr #           # Rl #
##    ######  <--o+--  ######
##

graph_mmstd = {'Rl' : [('Rr','+'),('Rr','o'),('Ur','+')],
               'Rr' : [('Rl','+'),('Rl','o'),('Ul','+')],
               'Ul' : [('Rr','o'),('Ur','o'),('Ur','+'),('Lr','o')],
               'Ur' : [('Ul','+'),('Ul','o'),('Rl','o'),('Ll','o')],
               'Ll' : [('Ur','+'),('Lr','o'),('Lr','+')],
               'Lr' : [('Ul','+'),('Ll','o'),('Ll','+')]}


##
##
## Throw types in O,S,U Notation (O = Over, U = Under, S = Side)
## corresponding to MMSTD States
##

throw_type = {'Rl' : 'U',
	      'Rr' : 'O',
	      'Ul' : 'S',
	      'Ur' : 'S',
	      'Ll' : 'O',
	      'Lr' : 'U'}




## Handle Python Interactive Console Completion
try:
	import sys
except ImportError:
	print "Module sys not available."


## 
## Name : __gen_pattern_from_state (init_state, end_state, cpt,cpt_states, path_len_max, path_len)
## 
## Purpose : For Internal Use only.
##           Give all Patterns from one state (init_state) to another one (end_state)
##           limited by : 
##             - cpt : counter maximum for states encountered
##             - path_len_max : length maximum for the pattern. -1 means any length
##
## parameters :
##           - init_state : The initial state for patterns
##           - end_state : The final state for patterns
##           - cpt : maximum number of times that you may encounter a node 
##           - cpt_states : current counter for encounter states
##           - path_len_max : Maximum length for the patterns to compute 
##           - path_len : current pattern length
##
## Return : A list of patterns. Each pattern is a list of possible transitions according to the
##          MMSTD graph. A transition will be a tuple (State src, State dst, exchange type)
##

def __gen_patterns_from_state (init_state, end_state, cpt, cpt_states, path_len_max, path_len):
	result = []	
	cpt_states[init_state] += 1  
	#print '============================================'
	#print 'initial state :',
	#print init_state
	#print 'mmstd transitions available',
	#print  graph_mmstd[init_state]
    

	for edge in graph_mmstd[init_state]:
		#print 'Transition Choosen : ',		
		#print init_state,
		#print ' ==> ',
		#print edge,
		#print ' From <',
		#print init_state,
		#print ' : ',
		#print graph_mmstd[init_state],
		#print '> '

		if end_state == edge[0]:
			result.append([(init_state , end_state , edge[1])])
			
		if cpt_states[edge[0]] < cpt:
			cpt_states_tmp = {'Rl':0,'Rr':0,'Ul':0,'Ur':0,'Ll':0,'Lr':0}
			for i in cpt_states:
				cpt_states_tmp[i] = cpt_states[i]
				#cpt_states_tmp[edge[0]] += 1
				#print '======== compute_pattern (',
				#print edge[0],
				#print end_state,
				#print  cpt,
				#print ')'

			path_len_tmp = path_len + 1
			if path_len_max < 0 or (path_len_max > 0 and path_len_tmp < path_len_max):
				result_tmp = __gen_patterns_from_state(edge[0], end_state, cpt, cpt_states_tmp, path_len_max, path_len_tmp)
			else: result_tmp = []
			if result_tmp != []:
				result_tmp2 = []	      
				for j in range(len(result_tmp)):
					result_tmp2 = [(init_state,edge[0],edge[1])] + result_tmp[j]
					result.append(result_tmp2)
                            
	return result


## 
## Name : __gen_purged_pattern_from_state (init_state, end_state, cpt,cpt_states, path_len_max, path_len, states_seen)
## 
## Purpose : For Internal Use only.
##           Give all Patterns from one state (init_state) to another one (end_state)
##           limited by : 
##             - cpt : counter maximum for states encountered
##             - path_len_max : length maximum for the pattern. -1 means any length
##             - states_seen : transitions that contain a least one state in this list will not be taken into account
##
## parameters :
##           - init_state : The initial state for patterns
##           - end_state : The final state for patterns
##           - cpt : maximum number of times that you may encounter a node 
##           - cpt_states : current counter for encounter states
##           - path_len_max : Maximum length for the patterns to compute 
##           - path_len : current pattern length
##           - states_seen : transitions that contain a least one state in this list will not be taken into account
##
## Return : A list of patterns. Each pattern is a list of possible transitions according to the
##          MMSTD graph. A transition will be a tuple (State src, State dst, exchange type)
##

def ____gen_purged_patterns_from_state (init_state, end_state, cpt, cpt_states, path_len_max, path_len, states_seen):
	result = []	
	cpt_states[init_state] += 1  
	#print '============================================'
	#print 'initial state :',
	#print init_state
	#print 'mmstd transitions available',
	#print  graph_mmstd[init_state]
    

	for edge in graph_mmstd[init_state]:
		if edge[0] not in states_seen:
			#print 'Transition Choosen : ',		
		        #print init_state,
		        #print ' ==> ',
		        #print edge,
		        #print ' From <',
		        #print init_state,
		        #print ' : ',
		        #print graph_mmstd[init_state],
		        #print '> '

			if end_state == edge[0]:				
				result.append([(init_state , end_state , edge[1])])
			
			if cpt_states[edge[0]] < cpt:
				cpt_states_tmp = {'Rl':0,'Rr':0,'Ul':0,'Ur':0,'Ll':0,'Lr':0}
				for i in cpt_states:
					cpt_states_tmp[i] = cpt_states[i]
				        #cpt_states_tmp[edge[0]] += 1
				        #print '======== compute_pattern (',
				        #print edge[0],
				        #print end_state,
				        #print  cpt,
				        #print ')'

				path_len_tmp = path_len + 1
				if path_len_max < 0 or (path_len_max > 0 and path_len_tmp < path_len_max):
					result_tmp = ____gen_purged_patterns_from_state(edge[0], end_state, cpt, cpt_states_tmp, path_len_max, path_len_tmp, states_seen)
				else: result_tmp = []
				if result_tmp != []:
					result_tmp2 = []	      
					for j in range(len(result_tmp)):
						result_tmp2 = [(init_state,edge[0],edge[1])] + result_tmp[j]
						result.append(result_tmp2)
                            
	return result


## 
## Name : gen_pattern_from_state (state, cpt, path_len_max)
## 
## Purpose : Give all Patterns for one state limited by : 
##             - cpt : counter maximum for states encountered
##             - path_len_max : length maximum for the pattern. -1 means any length
##
## parameters :
##           - state : The state for patterns
##           - cpt : maximum number of times that you may encounter a node 
##           - path_len_max : Maximum length for the patterns to compute 
##
## Return : A list of patterns. Each pattern is a list of possible transitions according to the
##          MMSTD graph. A transition will be a tuple (State src, State dst, exchange type)
##

def gen_patterns_from_state (state, cpt,path_len_max):    
	res =  __gen_patterns_from_state(state,state,cpt,{'Rl':0,'Rr':0,'Ul':0,'Ur':0,'Ll':0,'Lr':0},path_len_max,0)
        return res


## 
## Name : __gen_purged_pattern_from_state (state, cpt, path_len_max, states_seen)
## 
## Purpose : For Internal Use only.
##           Give all Patterns for one state limited by : 
##             - cpt : counter maximum for states encountered
##             - path_len_max : length maximum for the pattern. -1 means any length
##             - states_seen : transitions that contain a least one state in this list will not be taken into account
##
## parameters :
##           - state : The state for patterns
##           - cpt : maximum number of times that you may encounter a node 
##           - path_len_max : Maximum length for the patterns to compute
##           - states_seen : transitions that contain a least one state in this list will not be take into account
##
## Return : A list of patterns. Each pattern is a list of possible transitions according to the
##          MMSTD graph. A transition will be a tuple (State src, State dst, exchange type)
##

def __gen_purged_patterns_from_state (state, cpt, path_len_max, states_seen):    
	res =  ____gen_purged_patterns_from_state(state,state,cpt,{'Rl':0,'Rr':0,'Ul':0,'Ur':0,'Ll':0,'Lr':0},path_len_max,0,states_seen)
        return res



## 
## Name : print_patterns_from_list (patterns_list)
## 
## Purpose : Display patterns from a patterns list.
##
## parameter :
##           - patterns_list : a patterns list. 
##           Each pattern is a list of possible transitions according to the
##           MMSTD graph. A transition will be a tuple (State src, State dst, exchange type)
##
## Return : None
##

def print_patterns_from_list (patterns_list):	
	res = {}
	for i in patterns_list :
		if i != [] : 
			if res.has_key(len(i)):
				res[len(i)].append(i)
			else:
				res[len(i)] = [i]

	for i in res.keys():
		print 'Transitions Of Length',
	       	print i,
		print ': \n'
		for j in range(len(res[i])):
			print ' \t',
			path = res[i][j]
			if path != []:				
				throw_typ = [throw_type[path[0][0]]]
				sys.stdout.write("%s "%path[0][0])
				sys.stdout.write("%s"%'-')
				sys.stdout.write("%s"%path[0][2])
				sys.stdout.write("%s"%'->')
				sys.stdout.write(" %s "%path[0][1])
				throw_typ.append(throw_type[path[0][1]])
				for k in range(len(path) -1):
					sys.stdout.write("%s"%'-')
					sys.stdout.write("%s"%path[k+1][2])
					sys.stdout.write("%s"%'->')
					sys.stdout.write(" %s "%path[k+1][1])
					throw_typ.append(throw_type[path[k+1][1]])		
			print ' [',
			for l in range (len(throw_typ) -1):
				sys.stdout.write("%s"%throw_typ[l])
			print ']',
			if(give_name(path)):
				print " : ",
				print_name(path)
			print ''
		print '' 
	

## 
## Name : print_pattern (pattern)
## 
## Purpose : Display a single pattern.
##
## parameter :
##           - pattern : a single pattern.
##           A pattern is a list of possible transitions according to the MMSTD graph.
##           One transition will be a tuple (State src, State dst, exchange type)
##
## Return : None
##

def print_pattern (pattern):
	if pattern == []: return
	path = pattern[0]
	print ' \t',
	throw_typ = [throw_type[path[0]]]
	sys.stdout.write("%s"%path[0])
	sys.stdout.write("%s"%' -')
	sys.stdout.write("%s"%path[2])
	sys.stdout.write("%s"%'-> ')
	sys.stdout.write("%s"%path[1])
	throw_typ.append(throw_type[path[1]])

	for i in range(len(pattern) - 1):
		path = pattern[i+1]
		sys.stdout.write("%s"%' -')
		sys.stdout.write("%s"%path[2])
		sys.stdout.write("%s"%'-> ')
		sys.stdout.write("%s"%path[1])
		throw_typ.append(throw_type[path[1]])

	print '   [',
	for l in range (len(throw_typ) -1):
		sys.stdout.write("%s"%throw_typ[l])
	print ']'
	
			    
## 
## Name : print_patterns_from_state_list (state_list)
## 
## Purpose : Display a list of Patterns for a list of state.
##           
## parameters :
##           - state_list : a list of Patterns for a list of state.
##           The state list is a dictionnary. Each key is a state, each value is a patterns list     
##           A pattern is a list of possible transitions according to the MMSTD graph.
##           One transition will be a tuple (State src, State dst, exchange type)
##
## Return : None
##

def print_patterns_from_state_list (state_list):
	for i in state_list :
		print '======================================'
		print '==             State',
		print i,
		print '            =='
		print '======================================\n'
		print_patterns_from_list (state_list[i])
            
    

## 
## gen_all_patterns_from_states (cpt, path_len_max)
## 
## Purpose : Give all Patterns available for the MMSTD diagram classified by state
##           limited by : 
##             - cpt : counter maximum for states encountered
##             - path_len_max : length maximum for the pattern. -1 means any length
##
## parameters :
##           - cpt : maximum number of times that you may encounter a node 
##           - path_len_max : Maximum length for the patterns to compute 
##
## Return : A list of patterns for a state list.
##          The state list is a dictionnary. Each key is a state, each value is a patterns list     
##          A pattern is a list of possible transitions according to the MMSTD graph.
##          One transition will be a tuple (State src, State dst, exchange type)

def gen_all_patterns_from_states (cpt,path_len_max):
	result = {'Rl' : [],
                'Rr' : [],
                'Ul' : [],
                'Ur' : [],
                'Ll' : [],
                'Lr' : []}

	for state in graph_mmstd.keys():
		result[state] = gen_patterns_from_state(state,cpt,path_len_max)
	return result	


## 
## gen_all_patterns (cpt, path_len_max)
## 
## Purpose : Give all Patterns available for the MMSTD diagram 
##           limited by : 
##             - cpt : counter maximum for states encountered
##             - path_len_max : length maximum for the pattern. -1 means any length
##
##           All equivalent patterns are removed.
##
## parameters :
##           - cpt : maximum number of times that you may encounter a node 
##           - path_len_max : Maximum length for the patterns to compute 
##
## Return : A list of patterns for a state list.
##          The state list is a dictionnary. Each key is a state, each value is a patterns list     
##          A pattern is a list of possible transitions according to the MMSTD graph.
##          One transition will be a tuple (State src, State dst, exchange type)

def gen_all_patterns (cpt,path_len_max):
	result = []
	states_seen = []
	for state in graph_mmstd.keys():
		#Avoid transitions with states already seen
		result.extend(__gen_purged_patterns_from_state(state,cpt,path_len_max,states_seen))
	        states_seen.append(state)
	return result
        


## 
## Name : reverse_pattern (pattern)
## 
## Purpose : Give the Time Reversed pattern of a single pattern.
##           
## parameter :
##           - pattern : the single pattern that you want to time reverse
##           A pattern is a list of possible transitions according to the MMSTD graph.
##           One transition will be a tuple (State src, State dst, exchange type)
##
## Return : the time Time Reversed Pattern
##

def reverse_pattern (pattern):
	if pattern == []: return []
	result = []
	for tr in pattern:
		res = [0,0,0]
		for j in range(2):
			if tr[j] == 'Rl' : res[j] = 'Rr'
			elif tr[j] == 'Rr' : res[j] = 'Rl' 
			elif tr[j] == 'Ul' : res[j] = 'Ur' 
			elif tr[j] == 'Ur' : res[j] = 'Ul' 
			elif tr[j] == 'Ll' : res[j] = 'Lr' 
			elif tr[j] == 'Lr' : res[j] = 'Ll'

		if tr[2] == '+' : res[2] = 'o'
		elif tr[2] == 'o' : res[2] = '+'
		result.append([res[1],res[0],res[2]])

	result.reverse()
	return result



## 
## Name : is_pattern_valid (pattern):
## 
## Purpose : Check if the pattern is valid according to the MMSTD graph.
##
## parameter :
##           - pattern : the single pattern that you want to check
##           A pattern is a list of possible transitions according to the MMSTD graph.
##           One transition will be a tuple (State src, State dst, exchange type)
##
## Return : a couple (bool,transitions list)
##          bool will be set to True if the pattern is valid according to the MMSTD graph;
##          False otherwise. If set to false, the transitions list will give unvalid transition
##          used. 
##

def is_pattern_valid (pattern):	
	result = [True, []]
	for edge in pattern:
		if (edge[1],edge[2]) not in graph_mmstd[edge[0]]:  
			result[0] = False
			result[1].append(edge)
	return result		


## 
## Name : is_equivalent (pattern1, pattern2)
## 
## Purpose : Check if two patterns are equivalent according to the MMSTD graph.
##
## parameter :
##           - pattern1, pattern2 : two patterns that you want to check the equivalence
##           A pattern is a list of possible transitions according to the MMSTD graph.
##           One transition will be a tuple (State src, State dst, exchange type)
##
## Return : a boolean
##          bool will be set to True if both patterns are equivalent according to the MMSTD graph;
##          False otherwise. 
##

def is_equivalent (pattern1, pattern2):
	drap = False
	cpt = 0	
	if len(pattern1) != len(pattern2): return False
	while ((cpt < len(pattern2)) and (drap == False)):
		if (pattern1[0] != pattern2[cpt]):
			cpt = cpt+1
		else :
			pattern_tmp = []
			for i in range(len(pattern2)):
				pattern_tmp.append(pattern2[(cpt+i)%len(pattern2)])
			if (pattern_tmp == pattern1): drap = True
			else:
				cpt = cpt + 1
	return drap		


## 
## Name : print_name (pattern)
## 
## Purpose : Print the name of a single pattern
##
## parameter :
##           - pattern : the patterns that you want to get the name
##           A pattern is a list of possible transitions according to the MMSTD graph.
##           One transition will be a tuple (State src, State dst, exchange type)
##
## Return : none
##

def print_name (pattern):
	if is_equivalent (pattern,[('Ur','Ul','+'),('Ul','Ur','o')]):
		print 'Left Half-Shower [SS]',  #Ur -+-> Ul -o-> Ur    [SS]
	elif is_equivalent (pattern,[('Ur','Ul','o'),('Ul','Ur','+')]):
		print 'Right Half-Shower [SS]',  #Ur -o-> Ul -+-> Ur    [SS]	
	elif is_equivalent (pattern,[('Ur','Ul','+'),('Ul','Ur','+')]):
		print 'Cascade [SS]',  #Ur -+-> Ul -+-> Ur    [SS]	 	
	elif is_equivalent (pattern,[('Ur','Ul','o'),('Ul','Ur','o')]):
		print 'Reversed Cascade [SS]',  #Ur -o-> Ul -o-> Ur    [SS]	 		
	elif is_equivalent (pattern,[('Ur','Rl','o'),('Rl','Ur','+')]):
		print 'Windmill (Catch Over with Right Hand) [SU]',  #Ur -o-> Rl -+-> Ur    [SU]	 			
	elif is_equivalent (pattern,[('Ur','Ll','o'),('Ll','Ur','+')]):
		print 'Windmill (Catch Under with Right Hand) [SO]',  #Ur -o-> Ll -+-> Ur    [SO]
	elif is_equivalent (pattern,[('Lr','Ul','+'),('Ul','Lr','o')]):
		print 'Windmill (Catch Over with Left Hand) [SU]',  #Lr -+-> Ul -o-> Lr   [SU]	 			
	elif is_equivalent (pattern,[('Rr','Ul','+'),('Ul','Rr','o')]):
		print 'Windmill (Catch Under with Left Hand) [SO]',  #Rr -+-> Ul -o-> Rr    [SO]
	elif is_equivalent (pattern,[('Lr','Ll','+'),('Ll','Lr','+')]):
		print 'Reversed Cross Arm Cascade (Left Above) [OU]',  #Lr -+-> Ll -+-> Lr    [UO]
	elif is_equivalent (pattern,[('Rl','Rr','+'),('Rr','Rl','+')]):
		print 'Reversed Cross Arm Cascade (Right Above) [OU]',  #Rl -+-> Rr -+-> Rl    [UO]	 			
	elif is_equivalent (pattern,[('Rl','Rr','o'),('Rr','Rl','o')]):
		print 'Cross Arm Cascade (Right Above) [OU]',  #Rl -o-> Rr -o-> Rl    [UO]	 					
	elif is_equivalent (pattern,[('Lr','Ll','o'),('Ll','Lr','o')]):
		print 'Cross Arm Cascade (Left Above) [OU]',  #Lr -o-> Ll -o-> Lr    [UO]	 					
	elif is_equivalent (pattern,[('Ur','Rl','o'),('Rl','Rr','+'),('Rr','Ul','+'),('Ul','Lr','o'),('Lr','Ll','+'),('Ll','Ur','+')]):
		print 'Mill\'s Mess  [SUOSUO]',  #Ur -o-> Rl -+-> Rr -+-> Ul -o-> Lr -+-> Ll -+-> Ur    [SUOSUO]
	elif is_equivalent (pattern,[('Ur','Rl','o'),('Rl','Rr','o'),('Rr','Ul','+'),('Ul','Lr','o'),('Lr','Ll','o'),('Ll','Ur','+')]):
		print 'Time Reversed Mill\'s Mess  [SUOSUO]',  #Ur -o-> Rl -o-> Rr -+-> Ul -o-> Lr -o-> Ll -+-> Ur    [SUOSUO]
	elif is_equivalent (pattern,[('Ur','Ll','o'),('Ll','Lr','o'),('Lr','Ul','+'),('Ul','Rr','o'),('Rr','Rl','o'),('Rl','Ur','+')]):
		print 'Time Reversed Funky Mess  [SOUSOU]',  #Ur -o-> Ll -o-> Lr -+-> Ul -o-> Rr -o-> Rl -+-> Ur    [SOUSOU]
	elif is_equivalent (pattern,[('Ur','Ll','o'),('Ll','Lr','+'),('Lr','Ul','+'),('Ul','Rr','o'),('Rr','Rl','+'),('Rl','Ur','+')]):
		print 'Funky Mess  [SOUSOU]',  #Ur -o-> Ll -+-> Lr -+-> Ul -o-> Rr -+-> Rl -+-> Ur    [SOUSOU]
	elif is_equivalent (pattern,[('Ll','Lr','+'),('Lr','Ul','+'),('Ul','Ur','+'),('Ur','Ul','o'),('Ul','Lr','o'),('Lr','Ll','o')]):
		print 'Half Boston Mess (Middle Throw alternates Left Uncrossed/Right Under) [SUOUSS]',  #Ll -+-> Lr -+-> Ul -+-> Ur -o-> Ul -o-> Lr -o-> Ll    [SUOUSS]
	elif is_equivalent (pattern,[('Ul','Rr','o'),('Rr','Rl','o'),('Rl','Rr','+'),('Rr','Ul','+'),('Ul','Ur','+'),('Ur','Ul','o')]):
		print 'Half Boston Mess (Middle Throw alternates Left Uncrossed/Right Over) [SOUOSS]',  #Ul -o-> Rr -o-> Rl -+-> Rr -+-> Ul -+-> Ur -o-> Ul    [SOUOSS]
	elif is_equivalent (pattern,[('Rr','Rl','+'),('Rl','Ur','+'),('Ur','Ul','+'),('Ul','Ur','o'),('Ur','Rl','o'),('Rl','Rr','o')]):
		print 'Half Boston Mess (Middle Throw alternates Right Uncrossed/Left Under) [SUOUSS]',  #Rr -+-> Rl -+-> Ur -+-> Ul -o-> Ur -o-> Rl -o-> Rr    [SUOUSS]
	elif is_equivalent (pattern,[('Ur','Ll','o'),('Ll','Lr','o'),('Lr','Ll','+'),('Ll','Ur','+'),('Ur','Ul','+'),('Ul','Ur','o')]):
		print 'Half Boston Mess (Middle Throw alternates Right Uncrossed/Left Over) [SOUOSS]',  #Ur -o-> Ll -o-> Lr -+-> Ll -+-> Ur -+-> Ul -o-> Ur    [SOUOSS]
	elif is_equivalent (pattern,[('Ul','Rr','o'),('Rr','Ul','+'),('Ul','Ur','o'),('Ur','Ll','o'),('Ll','Ur','+'),('Ur','Ul','o')]):
		print 'Mess SOS [SOSSOS]', #Ul -o-> Rr -+-> Ul -o-> Ur -o-> Ll -+-> Ur -o-> Ul   [SOSSOS]
	elif is_equivalent (pattern,[('Ul','Lr','o'),('Lr','Ul','+'),('Ul','Ur','+'),('Ur','Rl','o'),('Rl','Ur','+'),('Ur','Ul','+')]):
		print 'Time Reversed Mess SOS [SUSSUS]', #Ul -o-> Lr -+-> Ul -+-> Ur -o-> Rl -+-> Ur -+-> Ul   [SUSSUS]
	elif is_equivalent (pattern,[('Ul','Lr','o'),('Lr','Ul','+'),('Ul','Ur','o'),('Ur','Rl','o'),('Rl','Ur','+'),('Ur','Ul','o')]):
		print 'Gillson\'s Mess (Mess SUS) [SUSSUS]', #Ul -o-> Lr -+-> Ul -o-> Ur -o-> Rl -+-> Ur -o-> Ul   [SUSSUS]
	elif is_equivalent (pattern,[('Ul','Rr','o'),('Rr','Ul','+'),('Ul','Ur','+'),('Ur','Ll','o'),('Ll','Ur','+'),('Ur','Ul','+')]):
		print 'Time Reversed Gillson\'s Mess [SOSSOS]', #Ul -o-> Rr -+-> Ul -+-> Ur -o-> Ll -+-> Ur -+-> Ul   [SOSSOS]
	else:
		print 'Unknown Pattern'
		


## 
## Name : def give_name (pattern)
## 
## Purpose : Give True if mmstd_gen knowns the name of a single pattern
##
## parameter :
##           - pattern : the patterns that you want to get the name
##           A pattern is a list of possible transitions according to the MMSTD graph.
##           One transition will be a tuple (State src, State dst, exchange type)
##
## Return : True if name is known, false otherwise
##

def give_name (pattern):
	found = False
	if(is_equivalent (pattern,[('Ur','Ul','+'),('Ul','Ur','o')]) or 
	   is_equivalent (pattern,[('Ur','Ul','o'),('Ul','Ur','+')]) or
	   is_equivalent (pattern,[('Ur','Ul','+'),('Ul','Ur','+')]) or 
	   is_equivalent (pattern,[('Ur','Ul','o'),('Ul','Ur','o')]) or
	   is_equivalent (pattern,[('Lr','Ul','+'),('Ul','Lr','o')]) or		
	   is_equivalent (pattern,[('Rr','Ul','+'),('Ul','Rr','o')]) or
	   is_equivalent (pattern,[('Ur','Rl','o'),('Rl','Ur','+')]) or
	   is_equivalent (pattern,[('Ur','Ll','o'),('Ll','Ur','+')]) or
	   is_equivalent (pattern,[('Lr','Ll','+'),('Ll','Lr','+')]) or	   
	   is_equivalent (pattern,[('Rl','Rr','+'),('Rr','Rl','+')]) or	 
	   is_equivalent (pattern,[('Rl','Rr','o'),('Rr','Rl','o')]) or
	   is_equivalent (pattern,[('Lr','Ll','o'),('Ll','Lr','o')]) or
	   is_equivalent (pattern,[('Ur','Rl','o'),('Rl','Rr','+'),('Rr','Ul','+'),('Ul','Lr','o'),('Lr','Ll','+'),('Ll','Ur','+')]) or
	   is_equivalent (pattern,[('Ur','Rl','o'),('Rl','Rr','o'),('Rr','Ul','+'),('Ul','Lr','o'),('Lr','Ll','o'),('Ll','Ur','+')]) or
	   is_equivalent (pattern,[('Ur','Ll','o'),('Ll','Lr','o'),('Lr','Ul','+'),('Ul','Rr','o'),('Rr','Rl','o'),('Rl','Ur','+')]) or 
	   is_equivalent (pattern,[('Ur','Ll','o'),('Ll','Lr','+'),('Lr','Ul','+'),('Ul','Rr','o'),('Rr','Rl','+'),('Rl','Ur','+')]) or
	   is_equivalent (pattern,[('Ll','Lr','+'),('Lr','Ul','+'),('Ul','Ur','+'),('Ur','Ul','o'),('Ul','Lr','o'),('Lr','Ll','o')]) or
	   is_equivalent (pattern,[('Ul','Rr','o'),('Rr','Rl','o'),('Rl','Rr','+'),('Rr','Ul','+'),('Ul','Ur','+'),('Ur','Ul','o')]) or
	   is_equivalent (pattern,[('Rr','Rl','+'),('Rl','Ur','+'),('Ur','Ul','+'),('Ul','Ur','o'),('Ur','Rl','o'),('Rl','Rr','o')]) or
	   is_equivalent (pattern,[('Ur','Ll','o'),('Ll','Lr','o'),('Lr','Ll','+'),('Ll','Ur','+'),('Ur','Ul','+'),('Ul','Ur','o')]) or
	   is_equivalent (pattern,[('Ul','Rr','o'),('Rr','Ul','+'),('Ul','Ur','o'),('Ur','Ll','o'),('Ll','Ur','+'),('Ur','Ul','o')]) or
	   is_equivalent (pattern,[('Ul','Lr','o'),('Lr','Ul','+'),('Ul','Ur','+'),('Ur','Rl','o'),('Rl','Ur','+'),('Ur','Ul','+')]) or
	   is_equivalent (pattern,[('Ul','Lr','o'),('Lr','Ul','+'),('Ul','Ur','o'),('Ur','Rl','o'),('Rl','Ur','+'),('Ur','Ul','o')]) or
	   is_equivalent (pattern,[('Ul','Rr','o'),('Rr','Ul','+'),('Ul','Ur','+'),('Ur','Ll','o'),('Ll','Ur','+'),('Ur','Ul','+')])):
		found = True

	else:
		found = False
	return found


##
## 
## A Few Examples on how to use this tool 
##
##
##

##pattern_example = [('Rl', 'Rr', 'o'), ('Rr', 'Ul', '+'), ('Ul', 'Lr', 'o'),
##		   ('Lr', 'Ll', '+'), ('Ll', 'Ur', '+'), ('Ur', 'Rl', 'o')]

##pattern_invalid_example = [('Rl', 'Rr', 'o'), ('Rl', 'Lr', '+'), ('Ul', 'Lr', 'o'),
##			   ('Lr', 'Ll', '+'), ('Ll', 'Ur', '+'), ('Ur', 'Rl', 'o'),('Lr','Rl','o')] 


## Internal Use normally. Print all Patterns by states from Rl to Rr with the restriction
## of not going through a state more than twice. 
##
#print_patterns_from_list(__gen_patterns_from_state ('Rl', 'Rr', 2,{'Rl':0,'Rr':0,'Ul':0,'Ur':0,'Ll':0,'Lr':0},-1,0))
#print(__gen_patterns_from_state ('Rl', 'Rr', 2,{'Rl':0,'Rr':0,'Ul':0,'Ur':0,'Ll':0,'Lr':0},-1,0))


## Print all Patterns from Rl without going  through a state more than twice.
##
#print_patterns_from_list(gen_patterns_from_state('Rl',2,-1))


## Generate all Patterns classified by states from all states without going through a state more than twice.
## And print this list
##
#print_patterns_from_state_list(gen_all_patterns_from_states (2,-1))


## Generate all Patterns classified by states from all states without going through a state more than once.
## And print this list . These pattern are called unit patterns
##
#print_patterns_from_state_list(gen_all_patterns_from_states (1,-1))


## Generate all Patterns from all states without going through a state more than once.
## And print this list . These pattern are called unit patterns
##
#print_patterns_from_list(gen_all_patterns(1,-1))


## Print a single pattern example
##
#print_pattern(pattern_example)


## Reverse a single pattern example and print it
##
#print_pattern(reverse_pattern (pattern_example))


## Check if some patterns are valid and print the result
##
#print(is_pattern_valid(pattern_example))
#print(is_pattern_valid(pattern_invalid_example))


## Check the equivalence between two patterns :
##   Ll -+-> Ur -+-> Ul -o-> Lr -o-> Ll
##   Ul -o-> Lr -o-> Ll -+-> Ur -+-> Ul
##
##pattern_example1 = [('Ll', 'Ur', '+'), ('Ur', 'Ul', '+'), ('Ul', 'Lr', 'o'),
##  		   ('Lr', 'Ll', 'o')]

##pattern_example2 = [('Ul', 'Lr', 'o'), ('Lr', 'Ll', 'o'), ('Ll', 'Ur', '+'),
##		   ('Ur', 'Ul', '+')]

#print(is_equivalent(pattern_example1,pattern_example2))


## Print the name of patterns
##
#print_name([('Ur','Rl','o'),('Rl','Rr','+'),('Rr','Ul','+'),('Ul','Lr','o'),('Lr','Ll','+'),('Ll','Ur','+')])
#print_name([('Ur','Rl','o'),('Rl','Rr','+'),('Rr','Ul','+'),('Ul','Rr','o'),('Rr','Ll','+'),('Ll','Ur','+')])


	
## Set MMSTD Commands for Interactive Console
import __builtin__
__builtin__.__dict__.update(globals())


## Handle Python Interactive Console Completion
try:
	import readline
except ImportError:
	print "Module readline not available."
else:
	import rlcompleter
	readline.parse_and_bind("tab: complete")
	readline


## Set Python Interactive Console 
import code
#c = code.InteractiveConsole()
#c.interact(banner='Welcome to the MMSTD Notation Tool ' + MMSTD_VERSION)