#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <string.h>
using namespace std;

struct NODO
{
    int *X;
    int k;
    float cota;
};
void quicksort(int *V, int izq, int der)
{
    int i, d, p;
    int pivote;
    int aux;
    p=(izq+der)/2;
    if(p>0)
    {
        pivote=V[p];
        i=izq;
        d=der;
        while(i<=d)
        {
            while(V[i]<pivote)
            {
                i++;
            }
            while(V[d]>pivote)
            {
                d--;
            }
            if(i<=d)
            {
                aux=V[i];
                V[i]=V[d];
                V[d]=aux;
                i++;
                d--;
            }
        }
        if(izq<d)
        {
            quicksort(V, izq, d);
        }
        if(i<der)
        {
            quicksort(V, i, der);
        }
    }
}
int tecnicos()
{
	int tecnicos;
	cout<<"Introduzca el numero de tecnicos: "<<endl;
	cin>>tecnicos;
	return tecnicos;
}
int leer(int &numRep, int* &tiempos)
{
	char *linea;
	int i=1;
	cout<<"Introduce el nombre del fichero .txt"<<endl;
	char nombre[100];
	cin>>nombre;
	strcat(nombre, ".txt");
	ifstream f;
	f.open(nombre);
	if (f.is_open()==0)
	{
		cout<<"No se encontro el archivo"<<endl;
		return -1;
	}
	f.getline(linea,999);
	numRep=atoi(linea);
	tiempos=(int*)malloc((numRep+1) * sizeof(int));
	while(f.eof()==0)
    {
        for(i=1;i<=numRep;i++)
        {
            f.getline(linea,999);
            tiempos[i]=atoi(linea);
        }
    }
	f.close();
}
int CalcularCota(NODO nodo, int *V, int numTec, int numRep)
{
    cout<<"k"<<nodo.k<<"k";
    int i, j, k, sumaTec, sumatotal;
    int cota;
    int *veces;
    sumatotal=0;
    veces=new int[numTec+1];
    for(i=1;i<=numTec;i++)
    {
        veces[i]=0;
    }
    for(i=1;i<=numTec;i++)
    {
        for(j=1;j<=nodo.k;j++)
        {
            if (nodo.X[j]==i)
            {
                veces[i]++;
            }
        }
    }
    int *T;
    for(i=1;i<=numTec;i++)
    {
        k=0;
        sumaTec=0;
        T=new int[veces[i]+1];
        for(j=1;j<=veces[i];j++)
        {
            T[i]=0;
        }
        for(j=1;j<=nodo.k;j++)
        {
            if (nodo.X[j]==i)
            {
                k++;
                if(k==1)
                {
                    T[k]=V[j];
                }
                else
                {
                    T[k]=T[k-1]+V[j];
                }
            }
        }
        for(j=1;j<=veces[i];j++)
        {
            if(j<=nodo.k)
            {
                sumatotal+=T[j];
            }
        }
    }
    cota=sumatotal/numTec;
    cout<<"calculamos cota"<<cota<<"cota"<<endl;
    return cota;
}
NODO NodoInicial(int *V, int numRep, int numTec, int &numnodos)
{
    NODO nodo;
    int *X;
    X=new int[numRep+1];
    nodo.X=X;
    nodo.k=0;
    nodo.cota=CalcularCota(nodo, V, numTec, numRep);
    numnodos++;
    cout<<endl<<"inicial"<<numnodos<<"nodos";
    return nodo;
}
NODO Seleccionar(NODO *lista, int &numnodos, int *V, int numTec, int numRep)
{
    int i;
    int j=1;
    int posicion=1;
    int minimo=CalcularCota(lista[1], V, numTec, numRep);
    NODO *aux;
    NODO nodoseleccionado;
    aux=new NODO[numnodos+1];
    for(i=2;i<=numnodos;i++)
    {
        if(CalcularCota(lista[i], V, numTec, numRep)<minimo)
        {
            posicion=1;
        }
    }
    for(i=1;i<=numnodos;i++)
    {
        aux[i]=lista[i];
    }
    lista=new NODO[numnodos];
    for(i=1;i<numnodos;i++)
    {
        if(i==posicion)
        {
            nodoseleccionado=aux[j];
            j++;
        }
        lista[i]=aux[j];
        j++;
    }
    numnodos--;
    cout<<endl<<"seleccionar"<<numnodos<<"nodos left";
    cout<<endl<<"seleccionamos nodo"<<nodoseleccionado.cota;
    return nodoseleccionado;

}
int Expandir(NODO nodo, NODO *hijos, int *V, int numTec, int numRep)
{
    cout<<endl<<"comienza expandir";
    int numhijos, xi;
    int i;
    NODO nodohijo;
    numhijos=0;
    for(xi=1;xi<=numTec;xi++)
    {

        nodohijo.X=nodo.X;
        nodohijo.k=nodo.k+1;
        nodohijo.X[nodohijo.k]=xi;
        for(i=1;i<=nodohijo.k;i++)
        {
            cout<<"vector"<<nodohijo.X[i]<<"vector";
        }
        nodohijo.cota=CalcularCota(nodohijo, V, numTec, numRep);
        numhijos++;
        hijos[numhijos]=nodohijo;
    }
    cout<<endl<<"fin expandir";
    return numhijos;
}
int Admisible(NODO nodo, int valorsolucion)
{
    cout<<endl<<"comprueba admisible";
    if(nodo.cota<valorsolucion)
    {
        return 1;
    }
    else return 0;
}
int Solucion(NODO nodo, int numRep)

{
    cout<<endl<<"comprueba solucion";
    if(nodo.k==numRep)
    {
        return 1;
    }
    else return 0;
}
NODO maria(int numTec, int numRep, int* tiempos)
{
    int i, j;
	int *V;
	int solucionoptima;
	int numnodos=0;
    NODO nodo;
    NODO *lista;
    NODO nodosolucion;
    NODO hijos[numTec+1];
    int totalhijos;
	V=new int[numRep+1];
	for(i=1;i<=numRep;i++)
    {
        V[i]=tiempos[i];
    }
    quicksort(V, 1, numRep);
    nodo=NodoInicial(V, numRep, numTec, numnodos);
    lista=new NODO[numnodos+1];
    lista[numnodos]=nodo;
    solucionoptima=2147483647;
    cout<<endl<<"DECLARACION DE VARIABLES TERMINADA"<<endl;
    while(numnodos>0)
    {
        nodo=Seleccionar(lista, numnodos, V, numTec, numRep);
        //AQUI HAY QUE HACER UNA FUNCION QUE COMPARE TODOS LOS NODOS DE LA LISTA Y ELIJA EL DE MENOR COTA, EXTRAYENDOLO DE LA LISTA
        if(CalcularCota(nodo, V, numTec, numRep)<solucionoptima)
        {
            totalhijos=Expandir(nodo, hijos, V, numTec, numRep);
            for(i=1;i<=totalhijos;i++)
            {
                cout<<endl<<"EJECUTAMOS EL FOR"<<endl;
                if(Admisible(hijos[i], solucionoptima))
                {
                    if(Solucion(hijos[i], numRep))
                    {
                        cout<<endl<<"POSIBLE SOLUCION"<<endl;
                        if(hijos[i].cota<solucionoptima)
                        {
                            cout<<endl<<"SOLUCION ENCONTRADA"<<endl;
                            nodosolucion=hijos[i];
                            solucionoptima=hijos[i].cota;
                        }
                    }
                    else
                    {
                        NODO *aux;
                        aux=new NODO[numnodos+1];
                        for(j=1;j<=numnodos;j++)
                        {
                            aux[j]=lista[j];
                        }
                        lista=new NODO[numnodos+2];
                        for(j=1;j<numnodos;j++)
                        {
                            lista[i]=aux[j];
                        }
                        lista[j]=hijos[j];
                        numnodos++;
                        cout<<endl<<"numnodos aumenta ahora es"<<numnodos<<endl;
                    }
                    cout<<endl<<"numnodos es"<<numnodos<<endl;
                }
            }
        }
        //AQUI COMPROBAR SI LA COTA DEL NODO ES MAS OPTIMA QUE VALORSOLUCION
            //SI SE CUMPLE, EJECUTAMOS EXPANDIR
            //BUCLE FOR QUE SE EJECUTA TANTAS VECES COMO HIJOS HAY
            //COMPROBAR SI EL HIJO ES MAS OPTIMO QUE LA COTA
                //SI LO ES COMPROBAR SI ES SOLUCION (SI ESTA EL VECTOR LLENO)
                    //SI LO ES, COMPARAR SU VALOR CON LA COTA Y CAMBIAR LA COTA SI ES MAS OPTIMO
                //SI NO ES SOLUCION, ANYADIRLO A LA LISTA DE NODOS VIVOSN


    }
    return nodosolucion;
}
int main()
{
	int numTec;
	int numRep;
	int* tiempos;
	string comando;
	NODO nodofinal;
	while(1)
	{
		cout<<"1.- Obtener listado de reparaciones."<<endl<<"2.- Numero de tecnicos de la empresa."<<endl<<"3.- Calcular distribucion."<<endl<<"4.- Salir."<<endl;
		cin>>comando;
		if(comando.compare("1")==0)
			{
				int i=1;
				if (leer(numRep, tiempos)==-1)
					{
						continue;
					}
				cout<<numRep<<endl;
				for(i=1;i<=numRep;i++)
				{
					cout<<tiempos[i]<<endl;
				}
			}
		else if(comando.compare("2")==0)
				{
					numTec=tecnicos();
				}
		else if(comando.compare("3")==0)
				{
					nodofinal=maria(numTec, numRep, tiempos);
					cout<<"RESULTADOFINAL"<<nodofinal.cota<<endl;
				}
		else if(comando.compare("4")==0)
				{
					return 0;
				}
	}
	system("pause");
	return 0;
}