--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/SMART/Java/Python/FindOverlapsOptim.py	Fri Jan 18 04:54:14 2013 -0500
@@ -0,0 +1,343 @@
+#! /usr/bin/env python
+#
+# Copyright INRA-URGI 2009-2012
+# 
+# This software is governed by the CeCILL license under French law and
+# abiding by the rules of distribution of free software. You can use,
+# modify and/ or redistribute the software under the terms of the CeCILL
+# license as circulated by CEA, CNRS and INRIA at the following URL
+# "http://www.cecill.info".
+# 
+# As a counterpart to the access to the source code and rights to copy,
+# modify and redistribute granted by the license, users are provided only
+# with a limited warranty and the software's author, the holder of the
+# economic rights, and the successive licensors have only limited
+# liability.
+# 
+# In this respect, the user's attention is drawn to the risks associated
+# with loading, using, modifying and/or developing or reproducing the
+# software by the user in light of its specific status of free software,
+# that may mean that it is complicated to manipulate, and that also
+# therefore means that it is reserved for developers and experienced
+# professionals having in-depth computer knowledge. Users are therefore
+# encouraged to load and test the software's suitability as regards their
+# requirements in conditions enabling the security of their systems and/or
+# data to be ensured and, more generally, to use and operate it in the
+# same conditions as regards security.
+# 
+# The fact that you are presently reading this means that you have had
+# knowledge of the CeCILL license and that you accept its terms.
+#
+
+import os, struct, time, shutil
+from optparse import OptionParser
+from commons.core.parsing.ParserChooser import ParserChooser
+from commons.core.writer.Gff3Writer import Gff3Writer
+from SMART.Java.Python.structure.Transcript import Transcript
+from SMART.Java.Python.structure.Interval import Interval
+from SMART.Java.Python.ncList.NCList import NCList
+from SMART.Java.Python.ncList.ConvertToNCList import ConvertToNCList
+from SMART.Java.Python.ncList.NCListParser import NCListParser
+from SMART.Java.Python.ncList.NCListCursor import NCListCursor
+from SMART.Java.Python.ncList.NCListFilePickle import NCListFilePickle, NCListFileUnpickle
+from SMART.Java.Python.ncList.NCListHandler import NCListHandler
+from SMART.Java.Python.misc.Progress import Progress
+from SMART.Java.Python.misc.UnlimitedProgress import UnlimitedProgress
+try:
+   import cPickle as pickle
+except:
+   import pickle
+
+REFERENCE = 0
+QUERY = 1
+TYPES = (REFERENCE, QUERY)
+TYPETOSTRING = {0: "reference", 1: "query"}
+
+class FindOverlapsOptim(object):
+	
+	def __init__(self, verbosity = 1):
+		self._parsers				  = {}
+		self._sortedFileNames		  = {}
+		self._outputFileName		  = "outputOverlaps.gff3"
+		self._iWriter				  = None
+		self._inputFileNames		  = {REFERENCE: None,  QUERY: None}
+		self._convertedFileNames      = {REFERENCE: False, QUERY: False}
+		self._inputFileFormats		  = {REFERENCE: None,  QUERY: None}
+		self._converted			      = {REFERENCE: False, QUERY: False}
+		self._ncListHandlers          = {REFERENCE: None,  QUERY: None}
+		self._splittedFileNames	      = {REFERENCE: {},	QUERY: {}}
+		self._nbOverlappingQueries	  = 0
+		self._nbOverlaps			  = 0
+		self._nbLines				  = {REFERENCE: 0, QUERY: 0}
+		self._sorted                  = False
+		self._index                   = False
+		self._verbosity			      = verbosity
+		self._ncLists				  = {}
+		self._cursors				  = {}
+		self._nbElementsPerChromosome = {}
+		self._tmpDirectories		  = {REFERENCE: False, QUERY: False}
+		
+	def close(self):
+		self._iWriter.close()
+		for fileName in (self._sortedFileNames.values()):
+			if os.path.exists(fileName):
+				os.remove(fileName)
+		for fileName in self._convertedFileNames.values():
+			if fileName:
+				os.remove(fileName)
+		
+	def setRefFileName(self, fileName, format):
+		self.setFileName(fileName, format, REFERENCE)
+		
+	def setQueryFileName(self, fileName, format):
+		self.setFileName(fileName, format, QUERY)
+
+	def setFileName(self, fileName, format, type):
+		self._inputFileNames[type] = fileName
+		self._inputFileFormats[type] = format
+		if format.lower() != "nclist":
+			self._converted[type] = True
+		
+	def setOutputFileName(self, outputFileName):
+		self._outputFileName = outputFileName
+		self._iWriter = Gff3Writer(self._outputFileName)
+	
+	def setSorted(self, sorted):
+		self._sorted = sorted
+
+	def setIndex(self, index):
+		self._index = index
+
+	def createNCLists(self):
+		startTime = time.time()
+		if self._verbosity > 1:
+			print "Building database"
+		self._ncLists = dict([type, {}] for type in TYPES)
+		self._indices = dict([type, {}] for type in TYPES)
+		self._cursors = dict([type, {}] for type in TYPES)
+		for type in TYPES:
+			self._ncListHandlers[type] = NCListHandler(self._verbosity-3)
+			if self._converted[type]:
+				self._convertedFileNames[type] = "%s_%d.ncl" % (os.path.splitext(self._inputFileNames[type])[0], type)
+				ncLists = ConvertToNCList(self._verbosity-3)
+				ncLists.setInputFileName(self._inputFileNames[type], self._inputFileFormats[type])
+				ncLists.setSorted(self._sorted)
+				ncLists.setOutputFileName(self._convertedFileNames[type])
+				if type == REFERENCE and self._index:
+					ncLists.setIndex(True)
+				ncLists.run()
+				self._ncListHandlers[type].setFileName(self._convertedFileNames[type])
+			else:
+				self._ncListHandlers[type].setFileName(self._inputFileNames[type])
+			self._ncListHandlers[type].loadData()
+			self._nbLines[type]				    = self._ncListHandlers[type].getNbElements()
+			self._nbElementsPerChromosome[type] = self._ncListHandlers[type].getNbElementsPerChromosome()
+			self._ncLists[type]				    = self._ncListHandlers[type].getNCLists()
+			for chromosome, ncList in self._ncLists[type].iteritems():
+				self._cursors[type][chromosome] = NCListCursor(None, ncList, 0, self._verbosity)
+				if type == REFERENCE and self._index:
+					self._indices[REFERENCE][chromosome] = ncList.getIndex()
+		endTime = time.time()
+		if self._verbosity > 1:
+			print "done (%.2gs)" % (endTime - startTime)
+
+	def compare(self):
+		nbSkips, nbMoves   = 0, 0
+		previousChromosome = None
+		done			   = False
+		startTime		   = time.time()
+		progress		   = Progress(len(self._ncLists[QUERY].keys()), "Checking overlap", self._verbosity)
+		#print "query:", self._ncLists[QUERY].keys()
+		#print "reference:", self._ncLists[REFERENCE].keys()
+		for chromosome, queryNCList in self._ncLists[QUERY].iteritems():
+			queryParser = self._ncListHandlers[QUERY].getParser(chromosome)
+			queryCursor = self._cursors[QUERY][chromosome]
+			if chromosome != previousChromosome:
+				skipChromosome	  = False
+				previousChromosome  = chromosome
+				if chromosome not in self._ncLists[REFERENCE]:
+					#print "out ", chromosome
+					continue
+				refNCList = self._ncLists[REFERENCE][chromosome]
+				refCursor = self._cursors[REFERENCE][chromosome]
+			#print "starting", chromosome
+			while True:
+				queryTranscript = queryCursor.getTranscript()
+				newRefLaddr = self.checkIndex(queryTranscript, refCursor)
+				#print "query is", queryTranscript
+				if newRefLaddr != None:
+					nbMoves += 1
+					refCursor.setLIndex(newRefLaddr)
+					#print "skipping to", refCursor
+					done = False
+				refCursor, done, unmatched = self.findOverlapIter(queryTranscript, refCursor, done)
+				#print "completed with", refCursor, done, unmatched
+				if refCursor.isOut():
+					#print "exiting 1", chromosome
+					break
+				if unmatched or not queryCursor.hasChildren():
+					queryCursor.moveNext()
+					#print "moving next to", queryCursor
+					nbSkips += 1
+				else:
+					queryCursor.moveDown()
+					#print "moving down to", queryCursor
+				if queryCursor.isOut():
+					#print "exiting 2", chromosome
+					break
+			progress.inc()
+		progress.done()
+		endTime = time.time()
+		self._timeSpent = endTime - startTime
+		if self._verbosity >= 10:
+			print "# skips:   %d" % (nbSkips)
+			print "# moves:   %d" % (nbMoves)
+
+	def findOverlapIter(self, queryTranscript, cursor, done):
+		chromosome = queryTranscript.getChromosome()
+		if chromosome not in self._ncLists[REFERENCE]:
+			return False, None
+		ncList = self._ncLists[REFERENCE][chromosome]
+		overlappingNames = {}
+		nextDone = False
+		firstOverlapLAddr = NCListCursor(cursor)
+		firstOverlapLAddr.setLIndex(-1)
+		if cursor.isOut():
+			return firstOverlapLAddr, False
+		parentCursor = NCListCursor(cursor)
+		parentCursor.moveUp()
+		firstParentAfter = False
+		#print "query transcript 1", queryTranscript
+		#print "cursor 1", cursor
+		#print "parent 1", parentCursor
+		while not parentCursor.isOut(): 
+			if self.isOverlapping(queryTranscript, parentCursor) == 0:
+				#print "overlap parent choice 0"
+				overlappingNames.update(self._extractID(parentCursor.getTranscript()))
+				if firstOverlapLAddr.isOut():
+					#print "overlap parent 2"
+					firstOverlapLAddr.copy(parentCursor)
+					nextDone = True # new
+			elif self.isOverlapping(queryTranscript, parentCursor) == 1:
+				#print "overlap parent choice 1"
+				firstParentAfter = NCListCursor(parentCursor)
+			parentCursor.moveUp()
+			#print "parent 2", parentCursor
+		if firstParentAfter:
+			#print "exit parent", firstParentAfter, overlappingNames
+			self._writeIntervalInNewGFF3(queryTranscript, overlappingNames)
+			return firstParentAfter, False, not overlappingNames
+		#This loop finds the overlaps with currentRefLAddr.#
+		while True:
+			#print "ref cursor now is", cursor
+			parentCursor = NCListCursor(cursor)
+			parentCursor.moveUp()
+			#In case: Query is on the right of the RefInterval and does not overlap.
+			overlap = self.isOverlapping(queryTranscript, cursor)
+			if overlap == -1:
+				cursor.moveNext()
+			#In case: Query overlaps with RefInterval.	
+			elif overlap == 0:
+				#print "choice 2"
+				overlappingNames.update(self._extractID(cursor.getTranscript()))
+				if firstOverlapLAddr.compare(parentCursor):
+					firstOverlapLAddr.copy(cursor)
+					nextDone = True # new
+				if done:
+					cursor.moveNext()
+				else:
+					if not cursor.hasChildren():
+						cursor.moveNext()
+						if cursor.isOut():
+							#print "break 1"
+							break
+					else:
+						cursor.moveDown()
+			#In case: Query is on the left of the RefInterval and does not overlap.		
+			else:
+				#print "choice 3"
+				if firstOverlapLAddr.isOut() or firstOverlapLAddr.compare(parentCursor):
+					#print "changing nfo 2"
+					firstOverlapLAddr.copy(cursor)
+					nextDone = False # new
+				#print "break 2"
+				break
+			
+			done = False
+			if cursor.isOut():
+				#print "break 3"
+				break
+		self._writeIntervalInNewGFF3(queryTranscript, overlappingNames)
+		return firstOverlapLAddr, nextDone, not overlappingNames
+	
+	def isOverlapping(self, queryTranscript, refTranscript):
+		if (queryTranscript.getStart() <= refTranscript.getEnd() and queryTranscript.getEnd() >= refTranscript.getStart()):
+			return 0   
+		if queryTranscript.getEnd() < refTranscript.getStart():
+			return 1
+		return -1
+
+	def checkIndex(self, transcript, cursor):
+		if not self._index:
+			return None
+		chromosome = transcript.getChromosome()
+		nextLIndex = self._indices[REFERENCE][chromosome].getIndex(transcript)
+		if nextLIndex == None:
+			return None
+		ncList		 = self._ncLists[REFERENCE][chromosome]
+		nextGffAddress = ncList.getRefGffAddr(nextLIndex)
+		thisGffAddress = cursor.getGffAddress()
+		if nextGffAddress > thisGffAddress:
+			return nextLIndex
+		return None
+		
+	def _writeIntervalInNewGFF3(self, transcript, names):
+		nbOverlaps = 0
+		for cpt in names.values():
+			nbOverlaps += cpt
+		if not names:
+			return
+		transcript.setTagValue("overlapsWith", "--".join(sorted(names.keys())))
+		transcript.setTagValue("nbOverlaps", nbOverlaps)
+		self._iWriter.addTranscript(transcript)
+		self._iWriter.write()
+		self._nbOverlappingQueries += 1
+		self._nbOverlaps		   += nbOverlaps
+		
+	def _extractID(self, transcript):
+		nbElements = float(transcript.getTagValue("nbElements")) if "nbElements" in transcript.getTagNames() else 1
+		id		   = transcript.getTagValue("ID")				 if "ID"		 in transcript.getTagNames() else transcript.getUniqueName()
+		return {id: nbElements}
+		
+	def run(self):
+		self.createNCLists()
+		self.compare()
+		self.close()
+		if self._verbosity > 0:
+			print "# queries: %d" % (self._nbLines[QUERY])
+			print "# refs:    %d" % (self._nbLines[REFERENCE])
+			print "# written: %d (%d overlaps)" % (self._nbOverlappingQueries, self._nbOverlaps)
+			print "time:      %.2gs" % (self._timeSpent)
+
+
+if __name__ == "__main__":
+	description = "Find Overlaps Optim v1.0.0: Finds overlaps with several query intervals. [Category: Data Comparison]"
+
+	parser = OptionParser(description = description)
+	parser.add_option("-i", "--query",	     dest="inputQueryFileName", action="store",			            type="string", help="query input file [compulsory] [format: file in transcript or other format given by -f]")
+	parser.add_option("-f", "--queryFormat", dest="queryFormat",		action="store",			            type="string", help="format of previous file (possibly in NCL format) [compulsory] [format: transcript or other file format]")
+	parser.add_option("-j", "--ref",		 dest="inputRefFileName",   action="store",			            type="string", help="reference input file [compulsory] [format: file in transcript or other format given by -g]")
+	parser.add_option("-g", "--refFormat",   dest="refFormat",		    action="store",			            type="string", help="format of previous file (possibly in NCL format) [compulsory] [format: transcript or other file format]")
+	parser.add_option("-o", "--output",	     dest="outputFileName",	    action="store",			            type="string", help="output file [compulsory] [format: output file in GFF3 format]")
+	parser.add_option("-d", "--index",	     dest="index",	            action="store_true", default=False,	               help="add an index to the reference file (faster but more memory) [format: boolean] [default: False]")
+	parser.add_option("-s", "--sorted",	     dest="sorted",	            action="store_true", default=False,	               help="input files are already sorted [format: boolean] [default: False]")
+	parser.add_option("-v", "--verbosity",   dest="verbosity",		    action="store",      default=1,     type="int",	   help="Trace level [format: int] [default: 1]")
+	(options, args) = parser.parse_args()
+	
+	iFOO = FindOverlapsOptim(options.verbosity)
+	iFOO.setRefFileName(options.inputRefFileName, options.refFormat)
+	iFOO.setQueryFileName(options.inputQueryFileName, options.queryFormat)
+	iFOO.setOutputFileName(options.outputFileName)
+	iFOO.setIndex(options.index)
+	iFOO.setSorted(options.sorted)
+	iFOO.run()