#!/usr/bin/python

import csv;
reader = csv.reader(open("data.txt", "rb"), delimiter='\t', quoting=csv.QUOTE_NONE);
data=[]
def checktype(s) :
        for func in ( float, str):
            try:
                n = func(s)
                return n
            except:
                pass
        return s
for row in reader:
	if(len(row)):
		data=data+[[row[0],[checktype(x) for x in row[1:]] ]];
del data[0];

# DELETE THIS ########     FOR TESTING ONLY      #################################
del data[8:]
for i in range(len(data)) :
	print data[i][0];
def printdist() :
	for i in range(len(distmat)) :
		outt="";
		for j in range(len(distmat)) :
			outt = outt + ' %5.3f'	% distmat[i][j]
		print outt;
### END of DELETE ################################################################3

# ToDo more data checking here
## like delete genes with no data at all if there are any. 


#Now data is assumed sane.  Each gene has an index in range(len(data)), i.
#data[i][0] is gene name and data[i][1] are it's values.
#store these indexes ina  list of clusters later.

#This function gives distance between 2 genes.
def dist(a,b):
	if (len(a)!=len(b)) :
		raise ValueError( "a="+repr(a)+" b="+repr(b)+" do not have equal lengths");
	for i in range(len(a)) :
		if(a[i]=='' or  b[i]==''):
			a[i]=0.0;
			b[i]=0.0;
	return sum([(y-x)**2 for x,y in zip(a, b)])**0.5

#Make a cluster using every gene's index.  We will just store indexes here.
clusters=[ [i] for i in range(len(data)) ];

# These function gives distance between 2 clusters.

# take a cluster of clusters and return a plain list.
def decluster(A) :
	if (type(A)!=type([])) :
		return A;
	flag=0;
	for x in A :
		if (type(x)==type([])) :
			flag=1;
	if flag==0: 
		return A;
	B=[]
	for x in A :
		if (type(x)==type([])) :
			B=B+decluster(x);
		else:
			B=B+[x];
	return B;
		
def cl_dist(i,j):
	x=decluster(clusters[i]);
	y=decluster(clusters[j]);
	return sum([dist(data[p][1],data[q][1]) for p in x for q in y])/(len(x)+len(y));

#create cluster distance matrix
distmat=[];
for i in range(len(clusters)):
	distmat.append([100.0]*len(clusters));
for i in range(len(clusters)) :
	for j in range(i+1):
		distmat[i][j]=cl_dist(i,j);
		distmat[j][i]=distmat[i][j];

# reduce the cluster using the algo till you have just one giant cluster.
#printdist();
while(len(clusters) >1) :
#	print clusters;
	mindist=100.0
	min_i=0;
	min_j=0;
	for i in range(len(distmat)) :
		for j in range(i):
			if(distmat[i][j]<mindist) :
				mindist=distmat[i][j];
				min_i=i;
				min_j=j;
	printdist();
	print min_i,min_j;
	clusters[min_j]=[clusters[min_i],clusters[min_j]];
	del clusters[min_i];
	for j in range(len(distmat)) :
		del distmat[j][min_i];
	del distmat[min_i];
	#now correct the min_i entries.
	for i in range(len(distmat)) :
		distmat[min_j][i]=cl_dist(min_j,i);
		distmat[i][min_j]=distmat[min_j][i];

### Done! Print the output!
print clusters;

#fancyprint for debugging and actually seeing the clustering in tree format.  This was a huge waste of time but is neat. :)
def fancyprint(list,padding=' '):
	print padding[:-1] + '+-'; #+repr(list);
	padding = padding + ' ';
	count = 0;
	for x in list:
		count = count+ 1;
		print padding + '|'
		if(type(x)==type([]) and len(x)==1 and type(x[0])!=type([]) ):
			x=x[0];
		if(type(x)!=type([])):
			print padding + '+-' + str(x)+':'+ data[x][i];
		else:
			if(count == len(list)):
				fancyprint(x, padding + ' ');
			else:
				fancyprint(x, padding + '|');

fancyprint(clusters);