# based on Allison, Powell Monash Ukkonen suffix tree javascript implementation

import sys

# root of the suffix tree
nForks=0;  # number of branching nodes in the suffix tree

class String: # represents Txt[left..right]
	def __init__(self, left, right, type):
		self.left = left
		self.right = right
		self.type = type
	def isEmptyStrng(self):
		return self.right < self.left 	

class State: # i.e. a new leaf node in the suffix tree
	def __init__(self,nodecount):
		self.nodecount = nodecount
		self.hash = {}
		self.isLeaf = True
	def addTransition(self, left, right, s, type):
		# this['a'] >---(left..right)---> s
		# add a transition to `this' state
		self.hash[data[left]] = [String(left,right,type), s]
   		self.isLeaf = False

def datastring(l,r):
	s = ''
	for i in range(l,r):
		if i<len(data):
			s = s + data[i]
	return s

def show(T, sstr, arc): # print the suffix tree
	global nForks
	if(T == None):#should not happen!
		print (sstr+arc+'NULL !!!\n')
		return #should not be here
	#else
	if hasattr(T,'isLeaf') and T.isLeaf:
		print (sstr+arc+'leaf\n')
		return
	#else
	nForks = nForks + 1
	iter = 0
	spaces = ''
	for i in range(len(arc)):
		spaces = spaces + ' '
	spaces = spaces + '|'   # |spaces|==|arc|
	str2 = sstr+spaces
	#each subtree
	#print "ATTR",
	#print T.hash.keys()	
	for attr in T.hash.keys():
		iter = iter + 1
		#print "ATTR " + attr + str(iter)
		[w,T2] = T.hash[attr]
		myStr = '('+w.type+':'+str(w.left+1)+':'+str(w.right+1)+':'+datastring(w.left, w.right+1)+':'+str(T2.nodecount)+')|'
		if iter > 1: #must get to at least 2 if suffix tree is correct.
			if iter == 2:
				print sstr + arc + '\n'
			else:
				print str2 + '\n'
		show(T2, str2, myStr)

def upDate(s, k, i): 
	# (s, (k, i-1)) is the canonical reference pair for the active point
	global nodecount	
	print("update:ski:" + str(s.nodecount) + str(k) + str(i)) 
	oldr = root
	(endPoint,r) = test_and_split(s, k, i-1, data[i])
	
	while not endPoint:
		nodecount = nodecount + 1
		r.addTransition(i, infinity, State(nodecount), 'up')
		if oldr != root:
			oldr.sLink = r
		oldr = r
		print("update:slink:" + str(s.nodecount) + "->" + str(s.sLink.nodecount))
		(s,k) = canonize(s.sLink, k, i-1)
		(endPoint,r) = test_and_split(s, k, i-1, data[i])
	if not oldr == root:
		oldr.sLink = s
	return (s, k)

def test_and_split(s, k, p, t):
	global nodecount
	print("test_and_split:skp/" + str(s.nodecount) + str(k) + str(p))
	if k<=p:
		#find the t_k transition g'(s,(k',p'))=s' from s
		# k1 is k'  p1 is p' 
		(w1,s1) = s.hash[data[k]];  # s --(w1)--> s1
		k1 = w1.left
		p1 = w1.right
		print ("test_and_split:k<=p:Txt.charAt" + data[k1+p-k+1])
		if t == data[k1 + p - k + 1]:
			print("test_and_split:branch:endpoint")
			return (True, s);
		else:
			nodecount = nodecount + 1
			r = State(nodecount)
			s.addTransition(k1, k1+p-k,   r, 't1');  # s ----> r ----> s1
			r.addTransition(    k1+p-k+1, p1, s1, 't2')
			print("test_and_split:branch:split")
			return (False, r)
   	else: # k > p;  ? is there a t-transition from s ?
		boo = ''
		if s.hash.has_key(t):
			boo = "ttrans"
		else:
			boo = "no-ttrans"
		print("test_and_split:branch:empty:" + boo)
		return (s.hash.has_key(t), s)

def canonize(s, k, p):
	print("canonize:skp:" + str(s.nodecount) + str(k) + str(p)) 
	if p < k:
		return (s, k)
	# find the t_k transition g'(s,(k',p'))=s' from s
	# k1 is k',  p1 is p'
   	(w1,s1) = s.hash[data[k]];    # s --(w1)--> s1
   	k1 = w1.left
	p1 = w1.right
	while p1-k1 <= p-k:    # s --(w1)--> s1 ---> ...
		k = k + p1 - k1 + 1;   # remove |w1| chars from front of w
		s = s1
		print("canonize:iter:s1:p1:" + str(p1) + str(s1.nodecount))
		if k <= p:
			(w1,s1) = s.hash[data[k]];   # s --(w1)--> s1
			k1 = w1.left
			p1 = w1.right
			if (p1 == None):
				p1string = "null"
			else:
				p1string = str(p1)
			print("canonize:new edge:s1k1p1:TxtcharAt:" \
				+ str(s1.nodecount) + ':' + str(k1) + ':' + p1string + ':' + data[k]) 
	return (s, k)

# ----------------------------------------------------------------------------

def build(d): 
	global data, root, nodecount, nForks, infinity, bt
	data = d	
	print "Data length: " + str(len(data))
	infinity = len(data) + 1000
	nForks = 0
	bt = State(1)  # bt (bottom or _|_)
	root = State(2)
	nodecount = 2
	# Want to create transitions for all possible chars
	# from bt to root
	for i in range(len(data)):
		bt.addTransition(i,i, root,'bo')

	root.sLink = bt
	s=root; k=0;  # NB. Start k=0, unlike Ukkonen paper our strings are 0 based
	
	for i in range(len(data)): 
		print("\nmain: new online input:" + str(i) + data[i])
		(s,k) = upDate(s, k, i);   # (s,k) < - upDate(...)
		print("main:after update:sk:" + str(s.nodecount) + str(k))
		(s,k) = canonize(s, k, i);     # (s,k) < - canonize(...)
		print("main:after canonize:sk:" + str(s.nodecount) + str(k))

	#show(bt, '', 'tree:|')

def supermax(T, sstr, arc,visible): # print the suffix tree
	global nForks
	allLeafs = 1
	for attr in T.hash.keys():
		[w,T2] = T.hash[attr]
		if not T2.isLeaf:
			allLeafs = 0
	if T.isLeaf: 
		allLeafs = 0
	if (allLeafs == 1):
		print "FOUND SUPERMAX"
	visible = allLeafs 	
	if(T == None):#should not happen!
		print (sstr+arc+'NULL !!!\n')
		return #should not be here
	#else
	if hasattr(T,'isLeaf') and T.isLeaf:
		if visible == 1:
			print (sstr+arc+'leaf\n')
		return
	#else
	iter = 0
	spaces = ''
	for i in range(len(arc)):
		spaces = spaces + ' '
	spaces = spaces + '|'   # |spaces|==|arc|
	str2 = sstr+spaces
	#each subtree
	#print "ATTR",
	#print T.hash.keys()	
	for attr in T.hash.keys():
		iter = iter + 1
		#print "ATTR " + attr + str(iter)
		[w,T2] = T.hash[attr]
		myStr = '('+w.type+':'+str(w.left+1)+':'+str(w.right+1)+':'+str(T2.nodecount)+')|'
		if iter > 1: #must get to at least 2 if suffix tree is correct.
			if iter == 2:
				if visible == 1:
					print sstr + arc + '\n'
			else:
				if visible == 1:
					print str2 + '\n'
		supermax(T2, str2, myStr,visible)