/*****************************
 * Practica 3 MP
 * Curso 2008-2009
 *
 * Vicente Lujan Mansilla
 * Lorena Margareto Bisquert
 *****************************/

#include "Busqueda.h"
#include<iostream>
#include<assert.h>
#include<math.h>
#include<fstream>
#include<time.h>

DataGenerator d;
const int REP = 40;

//TEST: Busqueda Binaria Iterativa
void Busqueda::testBB_I(int ini, int end, int inc, ostream& outComp)
{   
	int talla, comp, comp_t, comp_p;
	vector<VElement> v;	
	
	for(talla=ini; talla<=end; talla+=inc)
	{
		comp_t = 0;
		comp = 0;
		
		for(int i=1; i<=REP; i++)
		{
			v.resize(talla);
 		    d.vectorOrd(v);
			VElement valor(d.numAleat(v.size()));
            BusquedaBinaria_I(v, valor);
            comp_t += valor.getNComparison ();                    			
		}
		
		comp_p = comp_t/REP;
		outComp << talla << " " << comp_p << endl; 
	}
}
 
//TEST: Busqueda Binaria Recursiva
void Busqueda::testBB_R(int ini, int end, int inc, ostream& outComp)
{
    	int talla, comp, comp_t, comp_p;
	vector<VElement> v;
	
	
	for(talla=ini; talla<=end; talla+=inc)
	{
		comp_t = 0;
		comp = 0;
		
		for(int i=1; i<=REP; i++)
		{
            		v.resize(talla);
            		d.vectorOrd(v);
			VElement valor(d.numAleat(v.size()));
            BusquedaBinaria_R(v, 0, v.size(), valor);
            		comp_t += valor.getNComparison ();                    			
		}
		
		comp_p = comp_t/REP;
		outComp << talla << " " << comp_p << endl; 
	}
}
 
//TEST: Busqueda Ternaria Iterativa
void Busqueda::testBT(int ini, int end, int inc, ostream& outComp)
{
    	int talla, comp, comp_t, comp_p;
	vector<VElement> v;

	
	for(talla=ini; talla<=end; talla+=inc)
	{
		comp_t = 0;
		comp = 0;
		
		for(int i=1; i<=REP; i++)
		{
            		v.resize(talla);
            		d.vectorOrd(v);
            		VElement valor(d.numAleat(v.size()));
            BusquedaTernaria_I(v, valor);
            		comp_t += valor.getNComparison ();                    			
		}
		
		comp_p = comp_t/REP;
		outComp << talla << " " << comp_p << endl; 
	}
}





//TEST: Busqueda Binaria Iterativa
void Busqueda::testBB_I_real(int ini, int end, int inc, ostream& outComp)
{   
	int talla;
	vector<VElement> v;	
	clock_t ini_time, fin_time;
	float time;
	ini_time = clock();
	
	for(talla=ini; talla<=end; talla+=inc)
	{
		
		for(int i=1; i<=REP; i++)
		{
			v.resize(talla);
 		    d.vectorOrd(v);
			VElement valor(d.numAleat(v.size()));
            BusquedaBinaria_I(v, valor);                  			
		}
		
		fin_time = clock();
		time =fin_time - ini_time;
		outComp << talla << " " << time / (CLOCKS_PER_SEC * REP) << endl; 
	}
}
 
//TEST: Busqueda Binaria Recursiva
void Busqueda::testBB_R_real(int ini, int end, int inc, ostream& outComp)
{
    	int talla;
	vector<VElement> v;
	clock_t ini_time, fin_time;
	float time;
	ini_time = clock();
	
	
	for(talla=ini; talla<=end; talla+=inc)
	{		
		for(int i=1; i<=REP; i++)
		{
            v.resize(talla);
            d.vectorOrd(v);
			VElement valor(d.numAleat(v.size()));
            BusquedaBinaria_R(v, 0, v.size(), valor);
                 			
		}
		
		fin_time = clock();
		time =fin_time - ini_time;
		outComp << talla << " " << time / (CLOCKS_PER_SEC * REP) << endl; 
	}
}
 
//TEST: Busqueda Ternaria Iterativa
void Busqueda::testBT_real(int ini, int end, int inc, ostream& outComp)
{
    	int talla;
	vector<VElement> v;
	clock_t ini_time, fin_time;
	float time;
	ini_time = clock();

	
	for(talla=ini; talla<=end; talla+=inc)
	{
		for(int i=1; i<=REP; i++)
		{
            v.resize(talla);
            d.vectorOrd(v);
            VElement valor(d.numAleat(v.size()));
            BusquedaTernaria_I(v, valor);                 			
		}
		
		fin_time = clock();
		time =fin_time - ini_time;
		outComp << talla << " " << time / (CLOCKS_PER_SEC * REP) << endl;
	}
}


//Busqueda Binaria Iterativa
bool Busqueda::BusquedaBinaria_I(vector<VElement> &v, VElement x)
{
	bool enc = false;
	int izq, der, centro;

	izq = 0;
	der = v.size()-1;
	centro = (izq+der)/2;

	while(izq <= der && (v[centro]<x || v[centro]>x))
	{
        
		if(v[centro] > x)
			der = centro - 1;
		else
			izq = centro + 1;
		centro = (izq+der)/2;
	}
    
	if(izq > der)
		enc = false;
	else
		enc = true;

	return enc;
}
//Busqueda Binaria Recursiva
bool Busqueda::BusquedaBinaria_R(vector<VElement> &v, int izq, int der, VElement x)
{
    bool enc = false;
	int centro;
	 
	 
	if(izq > der)
		enc = false;
     	else
     	{
		centro = (izq+der)/2;
         if(x < v[centro])
              	BusquedaBinaria_R(v, izq, centro-1, x);
         	else if(x > v[centro])
              	BusquedaBinaria_R(v, centro+1, der, x);
         	else
             	enc = true;
     }
     
     return enc;
}
//Busqueda Ternaria Iterativa
bool Busqueda::BusquedaTernaria_I(vector<VElement> &v, VElement x)
{
	bool enc = false;
	int izq, der, tercio, dos_tercios;

	izq = 0;
	der = v.size()-1;
	tercio = izq+ ((der-izq)/3);
	dos_tercios = 2*tercio;

	while(izq <= der  && enc == false)
	{
        
		if(x < v[tercio])
			der = tercio-1;
		else if(x > v[dos_tercios])
			izq = dos_tercios+1;
		else if(x == v[tercio] || x == v[dos_tercios])
			enc = true;
		else
		{
			izq = tercio + 1;
			der = dos_tercios - 1;
		}

		tercio = izq+ ((der-izq)/3);
        dos_tercios = 2*tercio;
	}
	return enc;
}

