#!/usr/local/bin/python
# coding: iso-8859-1
# Copyright © 2008 by Amos Newcombe
# 
# This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
# 
# 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.
# 
# You should have received a copy of the GNU General Public License along with this program.  If not, see <http://www.gnu.org/licenses/>.

'''Command-line program to test running speed of greatest common divisor algorithms.
'''

import re, time
from random import getrandbits
from gcd import dfGcd

class CartesianIter:
	'''Given a list n iterators, loop over the space of their cartesian product, with the last one on the list changing most frequently, and the first one least frequently.
	
	Beware of feeding it iterators that are infinite, or length zero: it will fail.
	'''
	
	def __init__(self, *lit):
		self.lit = lit
		self.litWork = [iter(it) for it in lit]
		self.lResult = []
	
	def __iter__(self): return self
	
	def next(self):
		i = len(self.litWork) - 1
		if not self.lResult:
			self.lResult = [it.next() for it in self.litWork]
		else:
			while True:
				try: self.lResult[i] = self.litWork[i].next()
				except StopIteration:
					self.litWork[i] = iter(self.lit[i])
					self.lResult[i] = self.litWork[i].next()
					i -= 1
					if i < 0: raise
				else: break
		return tuple(self.lResult)

class ListPairIter:
	
	def __init__(self, l):
		self.l = l
		self.i, self.j = 0, 0
		self.c = len(l)
	
	def __iter__(self): return self
	
	def next(self):
		self.j += 1
		if self.c <= self.j:
			self.i += 1
			self.j = self.i + 1
			if self.c <= self.j: raise StopIteration
		return (self.l[self.i], self.l[self.j])

from commander.commander import commander
import sys

class gcdtest(commander):
	
	# ¤ Metadata
	
	sUsage   = '''\
python %prog <options> ...
run a timing test on the gcd routines\
'''
	sVersion = '%prog 2008.08.05.0'
	
	sAlgDefault   = 'ENC'
	slBitsDefault = '16'
	sNDefault     = '5'
	
	# ¤ Creation
	
	def __init__(self, lsLine):
		commander.__init__(self, lsLine)
	
	def options(self): # called by commander.__init__()
		'populate the option parser (self.optParser) with options'
		self.optParser.add_option('-a',
			dest='sAlg', default=self.sAlgDefault, metavar='<str>',
			help='use the algorithms listed in <str> by their one-letter code:' + \
				''.join(dfGcd.keys()) + ' default ' + self.sAlgDefault
		)
		self.optParser.add_option('-b',
			dest='slBits', default=self.slBitsDefault, metavar='b,b...',
			help='use numbers of b bits, where b is from this ' + \
				'punctuation-separated list, default ' + self.slBitsDefault
		)
		self.optParser.add_option('-n',
			dest='sN', default=self.sNDefault, metavar='n',
			help='use n random numbers for the test, default ' + self.sNDefault
		)

	def ResolveOptions(self):
		'Interpret the command line options.'
		try                  : self.sAlg = self.opt.sAlg
		except AttributeError: self.sAlg = self.sAlgDefault
		try                  : slBits = self.opt.slBits
		except AttributeError: slBits = self.slBitsDefault
		self.lnBits = [int(s) for s in re.split('\W+', slBits)]
		try                  : sN = self.opt.sN
		except AttributeError: sN = self.sNDefault
		self.nN = nN = int(sN)
		self.cPairs = nN * (nN-1) / 2
	
	# ¤ Reporting
	
	def texttable(self, dResult, nWidth=5):
		print 'bits'.rjust(nWidth) + ' ' + \
			' '.join([ch.center(nWidth) for ch in self.sAlg])
		for nB in self.lnBits:
			print str(nB).rjust(nWidth) + ' ' + \
				' '.join([self.textresult(dResult[(ch, nB)], nWidth) for ch in self.sAlg])
	
	def textresult(self, Value, nWidth=5):
		if isinstance(Value, str):
			try            : sValue = '(%s)' % self.dnErrors[Value]
			except KeyError: sValue = Value
			sValue = sValue.center(nWidth)
		else:
			sValue = '%*.1f' % (nWidth, Value)
		return sValue
	
	# ¤ Operation
	
	def main(self):
		dResult = self.test()
		self.texttable(dResult, 6)
	
	def test(self):
		# generate data for each bit size
		self.dlData = dict([
			(nB, [getrandbits(nB) for i in range(self.nN)]) 
			for nB in self.lnBits
		])
		# run the test
		dResult = {}
		self.dnErrors, nFootnote = {}, 0
		isError = False
		for ch, nB in CartesianIter(self.sAlg, self.lnBits):
			fGcd = dfGcd[ch]
			itData = ListPairIter(self.dlData[nB])
			xElapsed = -time.clock()
			for n1, n2 in itData:
				try: fGcd(n1, n2)
				except RuntimeError, ex:
					isError = True
# 					print 'RuntimeError:', str(ex)
					if not self.dnErrors.has_key(str(ex)):
						nFootnote += 1
						self.dnErrors[str(ex)] = nFootnote
					dResult[(ch, nB)] = str(ex)
					break
			xElapsed += time.clock()
			if isError: isError = False
			else      : dResult[(ch, nB)] = 1e6 * xElapsed / self.cPairs
		return dResult

if __name__ == '__main__':

	gcdtest(sys.argv).main()