#ifndef __MATH_AMV
	#define __MATH_AMV

#include <cmath>
#include "deque.h"

namespace amv	{

template <class type>
type abs(const type &t)
{
return (type(0)<t? t: -t);
}

template <class type>
deque<type> getPrimes(int n)
{
deque<type> d;
type number=2;
bool found;

d.push_back(number++);
for(int i=1; i<n;)
	{
	found=true;
	for(type j=2; j<number; ++j)
		{
		if(!(number%j==0))
			continue;
		else
			{
			++number;
			found=false;
			break;
			}
		}
	if(found)
		{
		d.push_back(number++);
		++i;
		}
	}

return d;
}

template <class type>
type mcm(deque<type> d)
{
//static deque<type> primes=getPrimes<type>(500);
static deque<int> primes=getPrimes<int>(500);
deque<type> results(d);

type mcm1=1;
deque<type>::size_type i=0;
bool still;

for(;;)
	{
	still=false;
	for(deque<type>::size_type j=0; j<d.size(); ++j)
		{
		if((d[j]%type(primes[i]))==type(0))
			d[j]=d[j]/type(primes[i]);
		}
	if(d==results)
		++i;
	else
		mcm1=mcm1*primes[i];

	results=d;

	for(deque<type>::size_type k=0; k<results.size(); ++k)
		{
		if(!(results[k]==1))
			{
			still=true;
			break;
			}
		}
	if(still)
		continue;
	else
		break;
	}

return mcm1;
}

template <class type>
inline type mcd(type a, type b)
{
type mcd,module, zero(false);

if(a<zero)
	a=-a;
if(b<zero)
	b=-b;
if(a<b)
	swap(a,b);
if(b==zero)
	return type(true);
mcd=b;
module=a%b;
while(!(module==zero))
	{
	a=b;
	mcd=b=module;
	module=a%b;
	}

return mcd;
}

template <class type>
inline const type &max(const type &a, const type &b)
{
return ((a<b)? b: a);
}

template <class type>
inline const type &min(const type &a, const type &b)
{
return ((a<b)? a: b);
}

template <class type>
type fact(const type &t)
{
type m=1;
for(type i=2; i<t; ++i)
	{
	m=m*i;
	}

return m*t;
}

template <class type>
void permut(deque<type> &d, deque<deque<type> > &results)
{
deque<type> prefix;
deque<bool> flags(d.size());
for(int i=0; i<flags.size(); ++i)
	flags[i]=true;
permut1(d,prefix,results,flags);
//permut2(d,prefix,results);
}

template <class type>
void permut1(deque<type> &d, deque<type> &prefix, deque<deque<type> > &results, deque<bool> &flags)
{//version recursiva, costosa y lenta
int nf=count(flags,true);

if(nf==1)
	{
	deque<bool>::size_type pos=findIndex(flags,true);
	prefix.push_back(d[pos]);
	results.push_back(prefix);
	prefix.pop_back();
	return;
	}

for(deque<type>::size_type i=0; i<d.size(); ++i)
	{
	if(flags[i])
		{
		prefix.push_back(d[i]);
		flags[i]=false;
		permut1(d,prefix,results,flags);
		flags[i]=true;
		prefix.pop_back();
		}
	}
}

template <class type>
void permut2(deque<type> &d, deque<type> &prefix, deque<deque<type> > &results)
{//version más costosa y más lenta
if(d.size()==1)
	{
	prefix.push_back(d[0]);
	results.push_back(prefix);
	prefix.pop_back();
	return;
	}

for(deque<type>::size_type i=0; i<d.size(); ++i)
	{
	prefix.push_back(d[i]);

	deque<type> temp;
	for(deque<type>::size_type j=0; j<d.size(); ++j)
		{
		if(j!=i)
			temp.push_back(d[j]);
		}
	permut2(temp,prefix,results);
	prefix.pop_back();
	}
}

/*
Obtiene la permutacion numero k de un arreglo de n elementos.
Esta basada en el factoradico. Es una representacion basada en una base variable correspondiente
a los valores del factorial de n. No es una base fija como la binaria.

Cada número puede representarse como una suma de productos de enteros por factoriales.
Para calcular el factoradico de 5, cuando n=3. Tenemos:

5%1, c=5, r=0
5%2, c=2, r=1
2%3, c=0, r=2
				-> [2 1 0]=5

	Notese que fuimos dividiendo por los valores de n! en forma inversa

5=(2*2!)+(1*1!)+(0*0!) -> el factorádico es [2 1 0]

El factoradico de 5 corresponde a la 5-esima permutacion de orden 3
*/
template <class type>
void permutk(const deque<type> &d, deque<type> &result, int k)
{
int n=d.size();
deque<int> factoradic(n), data(n);

for (int j=1; j<=n; ++j)
	{
	factoradic[n-j] = k%j;	
    k/=j;					
	}						

int i;
for (i=0; i<n; ++i)
	{
	++factoradic[i];
	}//incrementa en uno los valores del factoradico

data[n-1] = 1;  // right-most element is set to 1. [? ? 1]

for (i = n-2; i >= 0; --i)	//coloca los demas valores de derecha a izquierda
	{						
	data[i] = factoradic[i];
    for (int j = i+1; j < n; ++j)	//si encuentra a la derecha del nuevo valor, algun valor >=
		{							//que éste, lo incrementa
		if (data[j]>=data[i])		//se incrementa si es = porque no puede estar el mismo
			++data[j];				//elemento en dos posiciones a la vez.
		}							//y se incrementa si es mayor, para garantizar que no haya
	}								//colision (si más tarde se encuentra un elemento igual
									//y la diferencia con uno anterior es 1.
for (i = 0; i < n; ++i)  // put in 0-based form
	{
    --data[i];
	}

for(i=0; i<n; ++i)
	{
	result[i]=d[data[i]];
	}
}

int random(int max)
{
return (rand()%max);
}

}

#endif