/ Code author: Yunyue Zhu, 09/2002.
/ Joint work with Dennis Shasha.
/	Server for Query by Humming

\l musicsearch_new.k
\m i 2001

nmin:15;nmax:20
N:128;nn:8;k:_ N%nn
delta:0.1

CurDir:"C:\\QbH\\"
RtreeDir:"C:\\programs\\test\\Debug\\test "

getmelody:{[song_i]
	a:0:($song_i),".txt"
	nolist:dulist:nos:dus:sep:()
	i:0;j:0
	do[#a 
		b:a[i]
	 	c:*&b=","
	 	if[c>0
		 	no:0$b[!c]
		 	du:0$b[c+1+!(#b)-c+1]
		 	nos,:no;	dus,:du
		]
		if[c=0				//empty line, add a new phrase
			nolist,:,nos;nos:()
			dulist,:,dus;dus:()
		]
	 	i+:1
	]
	if[0<#nos;nolist,:,nos;dulist,:,dus]		/clean up
	
	Hno:();Hdu:()
	i:0
	do[#nolist
		cur_no:cur_du:()
		cur_no,:nolist[i];cur_du,:dulist[i]
		j:i+1
		while[((#cur_no)<nmin)&(j<#nolist)
			cur_no,:nolist[j];cur_du,:dulist[j]
			j+:1
		]
		if[(#cur_no)>nmin-1;Hno,:,cur_no;Hdu,:,cur_du]
		while[((#cur_no)<nmax)&(j<#nolist)
			cur_no,:nolist[j];cur_du,:dulist[j]
			if[(#cur_no)<nmax;Hno,:,cur_no;Hdu,:,cur_du]
			j+:1
		]
		i+:1
	]
	:(Hno;Hdu)
}

//aproximately streching q to be of length N
MapToUniformAxis:{[q;N]
	:q[_ (!N)*(#q)%N]
}

BuildDB:{
	//the original melody (discret notes) and the one after transformation(normailized time series) and after reduction
	DB_o:DB_s:DB_t:DB_r:DB_n:()
	i:0
	do[34
		g : getmelody[i];Hno:g[0];Hdu:g[1]
		j : 0
		do[#Hno
			note:(,Hno[j]),,Hdu[j]
			DB_o,:,note		
			DB_s,:,(<':note[0])+(2*(=':note[0]))+3*>':note[0]
			q:vectorize2[note]
			q-:(+/q)%#q
			q:MapToUniformAxis[q;N]
			DB_t,:,q
			DB_r,:,(+/+(-1;k) # q)%k
			DB_n,:i
			j+:1
		]
		i+:1
	]	 
	"DB3"1:DB_o
	"DB4"1:DB_t
	"DB5"1:DB_r
	"DB6"1:DB_n
	"DB7"1:DB_s
}

	DB_o:1:"DB3"
	DB_t:1:"DB4"
	DB_r:1:"DB5"
	DB_n:1:"DB6"
	DB_s:1:"DB7"
	songname: 0:"songs.txt"

PutToFile:{[outfile]
	i:0;s:""
	do[#DB_r	
		s,:,/("\""),(,/" ",/:$DB_r[i]),("\" \""),($i),("\"\n")
		i+:1
	]
	outfile 0:s
}

createIndex:{[indexfile;datafile]
	PutToFile[datafile]
	`4:RtreeDir, "create ", CurDir,indexfile," ",CurDir,datafile
}
/createIndex["beatles.index";"beatles.ts"]

//the following two lines measure the T
//\l c:\k\dwt\tsdata\dtw_new
//data:DB_t;N:128;k:16;n:_ N%k;MeasureT[]

Query2:{[x;delta;topk]
	data::x
	queries::queries,,data
	\topk:topk
	x:x[&x>40]
 	x:MapToUniformAxis[x;N]
	x-:(+/x)%#x
	x:_ x+0.5
	\s:FilterTopQuery[DB_t;DB_r;x;delta;topk]
	b:`$songname[DB_n[s[0]]]
	:s,,b
}

ToEnvelopeString:{[le;ue;epsilon]
	:,/" ",/:$,/+(le-epsilon;ue+epsilon)
}

//NN query, using Rtree
Query4:{[x;delta;topk]
	data::x
	x:x[&x>40]
 	query:MapToUniformAxis[x;N]
	query-:(+/query)%#query
	
	width :_ delta*N
	le:LowerEnvelop[query;width]
	ue:UpperEnvelop[query;width]
	reduce_le:(+/+(-1;k) # le)%k
	reduce_ue:(+/+(-1;k) # ue)%k
	
	thresh :2
	cadidate:RtreeSearch["beatles.index";reduce_le;reduce_ue;thresh]
	toplist:topk # -1
	topdist:topk # INF
	
	i:0
	do[#cadidate
			dist:Dist_Env[le;ue;DB_t[cadidate[i]]]%N
			if[dist<topdist[topk-1]
				dist:LocalDTW[query;DB_t[cadidate[i]];delta]%N
				if[(dist<topdist[topk-1])
					pos: topdist _bin dist
					toplist:toplist[!pos],cadidate[i],toplist[pos+!topk-pos+1]
					topdist:topdist[!pos],dist, topdist[pos+!topk-pos+1]
				]
			]
		i+:1
	]
	s:(toplist;topdist)
	b:`$songname[DB_n[s[0]]]
	:s,,b
}

//range query, using Rtree
Query5:{[x;delta;topk]
	data::x
	x:x[&x>40]
 	query:MapToUniformAxis[x;N]
	query-:(+/query)%#query
	
	width :_ delta*N
	le:LowerEnvelop[query;width]
	ue:UpperEnvelop[query;width]
	reduce_le:(+/+(-1;k) # le)%k
	reduce_ue:(+/+(-1;k) # ue)%k
	
	thresh :2
	toplist:RtreeSearch["beatles.index";reduce_le;reduce_ue;thresh]
	topdist:()
	i:0
	do[#toplist
		topdist,:LocalDTW[query;DB_t[toplist[i]];delta]%N
		i+:1
	]
	order:<topdist;order:order[!topk]
	s:(toplist[order];topdist[order])
	b:`$songname[DB_n[s[0]]]
	:s,,b
}

//range query, using linear scan
Query4:{[x;delta;topk]
	count1:0;count2:0
	data::x
	x:x[&x>40]
 	query:MapToUniformAxis[x;N]
	query-:(+/query)%#query
	
	width :_ delta*N
	le:LowerEnvelop[query;width]
	ue:UpperEnvelop[query;width]
	reduce_le:(+/+(-1;k) # le)%k
	reduce_ue:(+/+(-1;k) # ue)%k
	thresh:2
	
	topdist:toplist:()
	i:0
	do[#DB_t
		//dist:Dist_Env[reduce_le;reduce_ue;DB_r[i]]%nn		/Envelope with dimension reduction using my method :PAA
		//if[dist<thresh
		//	count1+:1
			dist:Dist_Env[le;ue;DB_t[i]]%N
			if[dist<thresh
				count2+:1
				dist:LocalDTW[query;DB_t[i];delta]%N
				if[(dist<thresh)
					toplist,:i
					topdist,:dist
				]
		//	]
		]
		i+:1
	]
	\g:topdist
	order:<topdist;order:order[!topk]
	s:(toplist[order];topdist[order])
	b:`$songname[DB_n[s[0]]]
	\s:("count1:"),($count1),("count2:"),($count2)
	:s,,b
}
RtreeSearch:{[indexfile;le;ue;epsilon]
	"mybat.bat" 0:RtreeDir,"search ", CurDir,indexfile," \"< r ",(ToEnvelopeString[le;ue;epsilon]),"\"\n"
	a:`4:"mybat.bat"
	:0$ 2 _ a
}

//given a coutor symbol list query,
QueryS:{[filename;topk]
	q:("FF";,",")0:filename
	q:+q[1]
	x:q[&q[;1]>0.08;0]
	query:(<':x)+(2*(=':x))+3*>':x
	
	toplist:topk # -1
	topdist:topk # INF
	
	i:0
	do[#DB_s
		dist:LocalDTW[query;DB_s[i];0.2]
		if[(dist<topdist[topk-1])
			pos: topdist _bin dist
			toplist:toplist[!pos],i,toplist[pos+!topk-pos+1]
			topdist:topdist[!pos],dist, topdist[pos+!topk-pos+1]
			//\s:("i:"),($i)," dist:",($dist)
		]
		i+:1
	]
	s:(toplist;topdist)
	b:`$songname[DB_n[s[0]]]
	:s,,b
}

//given a coutor symbol list query,
QueryS2:{[x;topk]
	query:(<':x)+(2*(=':x))+3*>':x
	
	toplist:topk # -1
	topdist:topk # INF
	
	i:0
	do[#DB_s
		dist:LocalDTW[query;DB_s[i];0.2]
		if[(dist<topdist[topk-1])
			pos: topdist _bin dist
			toplist:toplist[!pos],i,toplist[pos+!topk-pos+1]
			topdist:topdist[!pos],dist, topdist[pos+!topk-pos+1]
			//\s:("i:"),($i)," dist:",($dist)
		]
		i+:1
	]
	s:(toplist;topdist)
	\b:`$songname[DB_n[s[0]]]
	/:s,,b
}
