////////////////////////////////////////////////////////////////////////////////
// Tecnologico de Costa Rica
// Escuela de Ingenieria en Computación
// Estructuras de Datos
//
// Edward Ovares Villegas
////////////////////////////////////////////////////////////////////////////////

/*  Descripcion:
    Multi búsqueda: Escriba un método int[] multiBusqueda(int[] datos, string[] buscados)
*/

//--> defines and macros names
#define cantElem(x) (sizeof(x)/sizeof(x[0]))
//--> Importaciones de librerias

#include <iostream>
#include <stdlib.h>
#include <malloc.h>

// siganacion de namespace

using namespace std;


/*
    Metodo que imprime un arreglo.
    Entradas: Un arreglo y un tamaño.
    Salida: La impresion del arreglo.
*/
void mostrarArreglo(const int arreglo[], int tamano)
{
    cout << "\n\n LA LISTA ES LA SIGUIENTE:\n" << endl;
    cout << "-------------------------" << endl;
    cout << "\tPOS" << "\tELEM"<< "\t|" << endl;
    for (int i = 0 ; i < tamano ; i++)
        cout << "\t[" << i << "]\t" << arreglo[i] << "\t|" << endl;

    cout << "-------------------------" << endl;
}

/*
    Metodo que hace una Busqueda Binaria dentro del Arreglo

*/
int busquedaBinaria(const int  vector[], int n, int dato)
{
    int centro,inf=0,sup=n-1;

    while(inf<=sup)
    {
        centro=(sup+inf)/2;
        if(vector[centro]==dato)
            return centro;
        else if(dato < vector [centro] )
        {
            sup=centro-1;
        }
        else
        {
            inf=centro+1;
        }
    }
    return -1;
}

/*
    Metodo de Multi Busqueda
*/
int* multiBusqueda(const int datos[],const string buscados[],int pLargoDato,int pLargoBusq)
{
    int LARGO = pLargoBusq;

    int *array_out = new int[LARGO];

// Reserva de Memoria
    //array_out = (int *)malloc(LARGO*sizeof(int*));


    for(int j = 0; j<LARGO ;j++)
    {
        string cadena = buscados[j];
        int x = atoi(cadena.c_str());

        x = busquedaBinaria(datos,pLargoDato,x);

        array_out[j] = x;
        cout << "Elemento:\t" << cadena << "\tPosicion:\t"<< x << endl;
    }


    return array_out;
}


// ***********************************************
// Funcion: Principal
// Entrada: null
// Salida: entero
// ***********************************************
int main()
{
    int arreglo_datos [] = {10,12,13,17,16,21,25,32,41,54,63,78,84,95,115};

    string arreglo_buscados [] = {"17","32","100","95"};


    cout << "\n IMPRESION DE LA LISTA ORIGINAL DE ELEMENTOS:" << endl;
    mostrarArreglo(arreglo_datos,cantElem(arreglo_datos));

    // Aplicacion del metodo de Multi Busqueda
    int *array = multiBusqueda(arreglo_datos,arreglo_buscados,cantElem(arreglo_datos),cantElem(arreglo_buscados));

    cout << "\n\n\nIMPRESION DE LAS POSICIONES DE LA LISTA DE BUSCADOS:" << endl;
    mostrarArreglo(array,cantElem(arreglo_buscados));

    return EXIT_SUCCESS;

} // End Main