# -*- coding: utf-8 -*-
# Author: Julien Moutinho <julm@autogeree.net>
# License: GNU GPLv3 (or later, at your choice)

from __future__ import unicode_literals

if 'XSCRIPTCONTEXT' in globals():
	def getModel():
		return (XSCRIPTCONTEXT.getDocument(), XSCRIPTCONTEXT.getComponentContext())
	def debug(msg):
		return
else:
	from connect_to_libre_office import getModel
	def debug(msg):
		print(msg)

def nAk(n,k):
	"""
	nAk(n,k) retourne le nombre d’arrangements
	de longueur k d’un ensemble de longueur n.
	"""
	if n<0 or k<0 or n<k:
		return None
	r = 1
	for i in range(n-k+1, n+1):
		r *= i
	#print("nAk%s = %i" % (str((n,k)), r))
	return r
def nAkLO(n,k):
	return str(nAk(int(n), int(k)))
def nCk(n,k):
	"""
	nCk(n,k) retourne le nombre de combinaisons
	de longueur k d’un ensemble de longueur n.
	"""
	if n<0 or k<0 or n<k:
		return None
	if k > n // 2:
		k = n - k # more efficient and safe with smaller numbers
	r = 1
	for i in range(1, k+1):
		r = r * (n-i+1) // i
	#print("nCk%s = %i" % (str((n,k)), r))
	return r
def nCkLO(n,k):
	return str(nCk(int(n), int(k)))
def combinOfRank(n,k,rank):
	"""
	combinOfRank(n, k, r) retourne les indices de permutation
	de la combinaison de k entiers parmi [1..n]
	au rang lexicographique r dans [0 .. nCk(n,k)-1].
	
	Construit chaque choix de la combinaison en prenant le prochain plus grand
	dont le successeur engendre un nombre de combinaisons
	qui dépasse le rang restant à atteindre.
	
	DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, p.26
	"""
	#print("combinOfRank: "+str((n,k,rank)))
	if rank<0 or nCk(n,k)<rank:
		return None
	i = 1
	j = 1
	c = []
	while True: # for1K
		if i < k:
			while True: # uptoRank
				nbCombins = nCk(n-j, k-i)
				#print("i=%i j=%i rank=%i nCk(%i-%i,%i-%i)=%i" % (i,j,rank, n,j,k,i,nbCombins))
				if nbCombins <= rank:
					j += 1
					rank -= nbCombins
					#print("rank -= %i" % nbCombins)
				else:
					c.append(j)
					#print("c = "+str(c))
					i += 1
					j += 1
					break
		elif i == k:
			c.append(j+rank) # because when i == k, nbCombins is always 1
			break
		else:
			break
	return c
def sequenceOfRank(n, k, rank):
	"""
	sequenceOfRank(n, k, r) retourne les indices de permutation
	de la combinaison de k entiers parmi [1..n]
	au rang lexicographique r dans [0 .. nAk(n,k)-1].
	
	rankOfSequence(n, sequenceOfRank(n, k, r)) == r
	sequenceOfRank(n, len(ns), rankOfSequence(n, ns)) == ns
	
	DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, p.75-77
	Computed from left to right to work on k-sequence of permutations
	instead of only full permutations.
	"""
	try:
		rank = int(rank)
	except ValueError:
		return None
	p = []
	a = nAk(n,k)
	for i in range(1,k+1): # first pass from left to right
		a //= n-(i-1) # optimized a = nAk(n-i, k-i)
		d = rank // a # greatest multiple of a, lower or equal to r
		rank = rank % a
		p.append(d+1)
	for i in range(k-1,-1,-1): # important: from right to left
		for j in range(i+1,k):
			if p[j] >= p[i]:
				p[j] += 1 # promote the positions in the good interval
	return p
def checkSequence(n,ns):
	"""
	checkSequence(n,ns) returns the range ns flattened
	if each element is with 1 and n, without repetition.
	"""
	p = []
	for row in ns: # flatten range given by LO
		for col in row:
			i = int(col)
			if not(1<=i and i<=n):
				return None
			if i in p: # duplicate
				return None
			p.append(i)
	return p
	
def rankOfCombin(n,ns):
	"""
	rankOfCombin(n, ns) retourne le rang lexicographique dans [0 .. nCk(n, length ns)-1]
	de la combinaison ns d’entiers parmi [1..n].
	
	WARNING: ns doit être triée de manière ascendante.
	
	Compte le nombre de combinaisons précédant celle de rang r.
	
	DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, pp.24-25
	
	rankOfCombin(n, combinOfRank(n, k, r)) == r
	combinOfRank(n, len(ns), rankOfCombin(n, ns)) == ns
	"""
	ns = checkSequence(n, ns)
	if ns == None:
		return None
	ns.sort()
	k = len(ns)
	i = 1
	rank = 0
	x1 = 0
	for x in ns:
		for j in range(x1+1,x-1 +1):
			rank += nCk(n-j, k-i)
		i += 1
		x1 = x
	return str(rank)
def rankOfSequence(n, ns):
	"""
	rankOfSequence(n, ns) retourne le rang lexicographique dans [0 .. nAk(n, len(ns))-1]
	de la combinaison ns d’entiers parmi [1..n].
	
	Compte le nombre d’arrangements précédant celui de rang r.
	
	DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, pp.74
	"""
	rank = 0
	ns = checkSequence(n, ns)
	if ns == None:
		return None
	k = len(ns)
	a = nAk(n,k)
	for i in range(1,k+1):
		a //= n-(i-1) # optimized a = nAk(n-i, k-i)
		nsi = ns[i-1]
		#print("ns = "+str(ns))
		#print("rank += %i * nAk(%i,%i)" % (nsi - 1, n - (i+1), k - (i+1)))
		rank += (nsi - 1) * nAk(n-i, k-i)
		for j in range(i,k):
			if nsi < ns[j]:
				ns[j] -= 1
	return str(rank)
def bitSize(n):
	"""
	bitSize(n) retourne le nombre de bits servant à encoder n.
	"""
	try:
		n = int(n)
	except ValueError:
		return None
	if n<0:
		return None
	r = 0
	while n > 0:
		r += 1
		n //= 2
	return r
def equiprobableBits(n):
	"""
	equiprobableBits(n) retourne le nombre maximal de bits de i
	équiprobables quand i parcourt [0 .. n-1].
	
	Ce nombre est le plus grand 'b' dans [0 .. ] tel que 2**b-1 <= n.
	
	map(equiprobableBits, range(0, 17+1)) == [0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4]
	"""
	return str(bitSize(n)-1)
def equiprobableRank(n):
	"""
	equiprobableRank(n) retourne le rang maximal imposé
	par le nombre de résultats possibles n,
	c’est à dire le nombre précédant la plus grande puissance de 2
	inférieure ou égale à n.
	
	list(map(int,map(equiprobableRank, range(1, 17+1)))) ==
	[0, 1, 1, 3, 3, 3, 3, 7, 7, 7, 7, 7, 7, 7, 7, 15, 15]
	#1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15, 16, 17
	"""
	return str(2**(bitSize(n)-1)-1)
def bitsOfInteger(m, n):
	"""
	bitsOfInteger(m, n) retourne les m premiers bits de poids faible
	encodant le nombre n.
	"""
	m = int(m)
	n = int(n)
	if not(0<=m and 0<=n):
		return None
	bs = ""
	while m > 0:
		(q,r) = (n//2, n%2)
		bs = ("1" if r else "0") + bs
		m -= 1
		n = q
	return bs
def interleave(cols):
	"""
	interleave(cols) return a string interleaving the characters
	of the strings within cols.
	"""
	m = 0
	for rows in cols:
		for cell in rows:
			try:
				m = max(m, len(cell))
			except TypeError:
				return None
	s = ""
	for idx in range(0, m):
		for rows in cols:
			for cell in rows:
				try:
					s+=cell[idx]
				except IndexError:
					continue
	return s
def inBase(base, digits):
	acc = 0
	for digit in digits:
		acc = int(digit) + (base * acc)
	return acc
def randomIntegerOfBits(n, bs):
	"""
	randomIntegerOfBits(n, bs) retourne le premier entier i formé par les bits bs
	qui a le potentiel d’atteindre un entier dans [0 .. n-1],
	ou recommence en ignorant le premier bit si n <= i.
	"""
	n = int(n)
	if bs == None:
		return None
	#print("randomIntegerOfBits: "+str((n, bs)))
	enough = bitSize(str(n - 1))
	#print("randomIntegerOfBits: enough="+str(enough))
	while True:
		bits  = bs[0:enough]
		given = len(bits)
		bs_   = bs[enough:]
		i     = inBase(2, bits)
		if given < enough:
			return None
		if n <= i:
			bs = bits[1:] + bs_
		else:
			return str(i)

g_exportedScripts = ()