#ifndef ARCHIVO_HASH
#define ARCHIVO_HASH

#include <iostream>
#include <fstream>
#include <string>
#include <stack>

using namespace std;

template <class tipo> class ArchivoHash {
/* Atributos de la clase */
protected:
	typedef struct t_comp {
		 bool libre;
		 tipo registro;
		 long proximo;
		 t_comp(){
			 libre = true;
			 proximo = -1;
		 }
	 };
	 long numMaxRegPrincipal;
	 long numMaxRegDesborde;
	 long numRegOcupPrincipal;
	 long numRegOcupDesborde;
	 fstream principal;
	 fstream desborde;
	 string nombreArchPrinc;
	 string nombreArchDesb;
	 stack<long> disponibles;


	/* Metodos de la clase */

	virtual bool Leer(fstream&, long, t_comp&) = 0;
	virtual bool Escribir(fstream&, long, t_comp) = 0;
	virtual long tamanoRegistro() = 0;

private:
	void Guardar_espacio(const long);
	long Buscar_espacio();

public:
	ArchivoHash();
	bool Crear(string, string, long);
	bool Abrir(string, string);
	bool Buscar(tipo&);
	bool Buscar(bool, long, tipo&);
	bool Agregar(tipo);
	bool Eliminar(tipo);
	bool Modificar(tipo, tipo);
	long numMaxRegPric();
	long numMaxRegDes();
	long numRegOcupadosPric();
	long numRegOcupadosDesb();
	string nombrePrincipal();
	string nombreDesborde();
	virtual long hash(tipo) = 0;
	~ArchivoHash();
};

/* Constructor */

template <class tipo> ArchivoHash<tipo>::ArchivoHash(){
	numMaxRegPrincipal = numRegOcupPrincipal = 0;
	numMaxRegDesborde = numRegOcupDesborde = 0;
}

/* Metodo para crear un archivo Hash */

template <class tipo> bool ArchivoHash<tipo>::Crear(string n_p, string n_d, long tam){
	if (tam < 0)
		return false;
	t_comp comp;
	/* Se crear el archivo principal
	*  con un 30% más de capacidad
	*/
	numMaxRegPrincipal = (long)(tam * 1.3);
	/* El archivo de desborde se crea
	 * con un tamano igual a un tercio
	 * del archivo principal
	 */
	numMaxRegDesborde = (long)(numMaxRegPrincipal * 0.3);
	numRegOcupPrincipal = numRegOcupDesborde = 0;
	nombreArchPrinc = n_p;
	nombreArchDesb = n_d;
	principal.clear();
	desborde.clear();

	/* Se rellena el archivo principal */
	principal.open(nombreArchPrinc.c_str(), ios::out | ios::binary);
	for (long i = 0; i < numMaxRegPrincipal; i++)
		Escribir(principal,i,comp);
	principal.close();

	/* Se rellena el archivo de desborde */
	desborde.open(nombreArchDesb.c_str(), ios::out | ios::binary);
	for (long i = 0; i < numMaxRegDesborde; i++){
		Guardar_espacio(i);
		Escribir(desborde,i,comp);
	}
	desborde.close();
	return true;
}


/* Metodo para abrir un archivo */

template <class tipo> bool ArchivoHash<tipo>::Abrir(string n_p, string n_d){
	principal.clear();
	desborde.clear();

	/* Se abre el archivo principal */
	principal.open(n_p.c_str(), ios::in | ios::binary | ios::ate);
	if (principal.fail())
		return false;
	/* Se abre el archivo de desborde */
	desborde.open(n_d.c_str(), ios::in | ios::binary | ios::ate);
	if (desborde.fail()){
		principal.close();
		return false;
	}
	t_comp comp;
	numMaxRegPrincipal = numMaxRegDesborde = numRegOcupPrincipal = numRegOcupDesborde = 0;

	/* Calculo del numero de registros */

	/* Cuantos bytes tiene el archivo */
	long tamano = principal.tellg();
	numMaxRegPrincipal = tamano / tamanoRegistro();

	/* Ubicacion del apt al principio del
	 * del archivo 
	 */
	principal.seekg(0,ios :: beg);

	for (long i = 0; i < numMaxRegPrincipal; i++){
		Leer(principal,i,comp);
		if (!comp.libre)
			numRegOcupPrincipal++;
	}

	tamano = desborde.tellg();
	desborde.seekg(0,ios::beg);
	numMaxRegDesborde = tamano / tamanoRegistro();
	for (long i = 0; i < numMaxRegDesborde; i++){
		Leer(desborde,i,comp);
		if (comp.libre)
			Guardar_espacio(i);
		else
			numRegOcupDesborde++;
	}

	nombreArchPrinc = n_p;
	nombreArchDesb = n_d;
	principal.close();
	desborde.close();
	return true;
}


/* Metodo para buscar un registro */

template <class tipo> bool ArchivoHash<tipo>::Buscar(tipo &reg){
	principal.clear();
	desborde.clear();
	principal.open(nombreArchPrinc.c_str(),ios::in | ios::binary);
	long pos = hash(reg);
	if (pos < 0 || pos >= numMaxRegPrincipal)
		return false;
	t_comp comp;
	Leer(principal,pos,comp);
	if (!comp.libre){
	   if (comp.registro == reg){
	      reg = comp.registro;
	      principal.close();
	      return true;
	   }
	   else {
	      if ( comp.proximo != -1){
	         desborde.open(nombreArchDesb.c_str(),
	                       ios::in | ios::binary);
	         bool sw = true;
		 while (sw){
		    Leer(desborde,comp.proximo,comp);
		    if (comp.proximo == -1)
		       sw = false;
		       if (comp.registro == reg){
			  reg = comp.registro;
			  desborde.close();
			  principal.close();
			  return true;
		       }
		 }
		 desborde.close();
	     }
	  }
	}
	principal.close();
	return false;
}

//----------------------BUSCAR-------------------

template <class tipo> bool ArchivoHash<tipo>::Buscar(bool archivo, long posicion, tipo &reg){
	if ((posicion < 0 || posicion >= numMaxRegPrincipal) && archivo)
		return false;
	if ((posicion < 0 || posicion >= numMaxRegDesborde) && !archivo)
		return false;
	t_comp comp;
	principal.clear();
	desborde.clear();
	if (archivo){
		principal.open(nombreArchPrinc.c_str(), ios::in | ios::binary);
		if (principal.fail())
			return false;
		Leer(principal,posicion,comp);
		if (!comp.libre){
			reg = comp.registro;
			principal.close();
			return true;
		}
		principal.close();
	}
	else {
		desborde.open(nombreArchDesb.c_str(), ios::in | ios::binary);
		if (desborde.fail())
			return false;
		Leer(desborde,posicion,comp);
		if (!comp.libre){
			reg = comp.registro;
			desborde.close();
			return true;
		}
		desborde.close();
	}
	return false;
}

/* Metodo para insertar un registro */

template <class tipo> bool ArchivoHash<tipo>::Agregar(tipo reg){
   principal.clear();
   desborde.clear();

   principal.open(nombreArchPrinc.c_str(), ios::in | ios::out | ios::binary);
   long pos = hash(reg);
   if (pos < 0 || pos >= numMaxRegPrincipal)
      return false;
   t_comp comp1, comp2;
   comp1.libre = false;
   comp1.registro = reg;
   Leer(principal,pos,comp2);
   if (comp2.libre){
      Escribir(principal,pos,comp1);
      principal.close();
      numRegOcupPrincipal++;
      return true;
   }
   else {
      desborde.open(nombreArchDesb.c_str(),ios::in | ios::out | ios::binary);
      // Se verifica si se ha insertado un registro
      // anteriormente en la misma posicion
      if (comp2.proximo == -1){
         // Buscar espacio en el archivo de desborde
         comp2.proximo = Buscar_espacio();

         // Si no se encuentra espacio
         // se devuelve falso
         if (comp2.proximo == -1){
            principal.close();
            desborde.close();
            return false;
         }
         // Si hay espacio se inserta el registro
         // en el archivo de desborde
         Escribir(principal,pos,comp2);
         principal.close();
      }
      else {
         long anterior = comp2.proximo;
         // Se lee el archivo de desborde hasta
         // encontrar el último registro
         while (comp2.proximo != -1){
            anterior = comp2.proximo;
            Leer(desborde,comp2.proximo,comp2);
         }
         // Se busca espacio en el archiov de desbor
         comp2.proximo = Buscar_espacio();
         // Si no hay se retorna falso
         if (comp2.proximo == -1){
            desborde.close();
            principal.close();
            return false;
         }
         // Si hay espacio se escribe el registro
         // en el desborde
         Escribir(desborde,anterior,comp2);
         principal.close();
      }
      numRegOcupDesborde++;
      Escribir(desborde,comp2.proximo,comp1);
      desborde.close();
   }
   return true;
}

/* Metodo para eliminar un registro */

template <class tipo> bool ArchivoHash<tipo>::Eliminar(tipo reg){
   principal.clear();
   desborde.clear();
   principal.open(nombreArchPrinc.c_str(),ios::in | ios::out | ios::binary);
   // Hallar la posicion del registro 
   long pos = hash(reg);
   // Validar si la posicion esta dentro del 
   // rango registros del archivo
   if (pos < 0 || pos >= numMaxRegPrincipal)
      return false;
   t_comp comp1, comp2;

   // Si el registro esta libre entonces no 
   // existe y se retorna falso
   Leer(principal,pos,comp1);
   if (comp1.libre){
      principal.close();
      return false;
   }

   // Se compara el registro y si es igual 
   // simplemente se coloca el campo de libre
   // en verdadero (se elimina el registro)
   if (comp1.registro == reg){
      // Si no hay mas registros insertados en esa
      // posicion se elimina
      if (comp1.proximo == -1){
         comp1.libre = true;
         Escribir(principal,pos,comp1);
         principal.close();
         numRegOcupPrincipal--;
         return true;
      }
      // Si hay mas registros, entonces de bede
      // realizar un desplazamiento
      else {
         desborde.open(nombreArchDesb.c_str(),ios::in | ios::out | ios::binary);
         Leer(desborde,comp1.proximo,comp2);
         Escribir(principal,pos,comp2);
         comp2.libre = true;
         comp2.proximo = -1;
         Escribir(desborde,comp1.proximo,comp2);
         numRegOcupDesborde--;
         Guardar_espacio(comp1.proximo);
         principal.close();
         desborde.close();
         return true;
      }
   }
   // Si el registro a eliminar no es el que esta
   // en el archivo principal se busca en el 
   // archivo de desborde
   else {
      desborde.open(nombreArchDesb.c_str(),ios::in | ios::out | ios::binary);
      bool sw = comp1.proximo != -1, encontro = false, p = true;
      long anterior = pos, actual = comp1.proximo;
      while (sw && !encontro){
         anterior = actual;
         actual = comp1.proximo;
         Leer(desborde,comp1.proximo,comp1);
         if (comp1.proximo == -1)
            sw = false;
         if (comp1.registro == reg)
            encontro = true;
         else
            p = false;
      }
      // Si no se encontro luego del recorrido
      // se retorna falso
      if (!encontro){
         principal.close();
         desborde.close();
         return false;
      }
      if (p){
         Leer(principal,pos,comp2);
         comp2.proximo = comp1.proximo;
         Escribir(principal,pos,comp2);
      }
      else {
         Leer(desborde,anterior,comp2);
         comp2.proximo = comp1.proximo;
         Escribir(desborde,anterior,comp2);
      }
      comp1.libre = true;
      comp1.proximo = -1;
      Escribir(desborde,actual,comp1);
      numRegOcupDesborde--;
      Guardar_espacio(actual);
      desborde.close();
   }
   principal.close();
   return true;
}

/* Metodo para modificar un registro */

template <class tipo> bool ArchivoHash<tipo>::Modificar(tipo reg1, tipo reg2){
	if (Eliminar(reg1))
		return Agregar(reg2);
	return false;
}

/* Metodo para buscar espacio para un registro */

template <class tipo> long ArchivoHash<tipo>::Buscar_espacio(){
	long res = -1;
	if (!disponibles.empty()){
		res = disponibles.top();
		disponibles.pop();
	}
	return res;
}

/* Metodo para guardar espacio para un registro */

template <class tipo> void ArchivoHash<tipo>::Guardar_espacio(const long espacio){
	disponibles.push(espacio);
}

// Metodos de lectura de atributos

template <class tipo> long ArchivoHash<tipo>::numMaxRegPric(){
	return numMaxRegPrincipal;
}

template <class tipo> long ArchivoHash<tipo>::numMaxRegDes(){
	return numMaxRegDesborde;
}

template <class tipo> long ArchivoHash<tipo>::numRegOcupadosPric(){
	return numRegOcupPrincipal;
}

template <class tipo> long ArchivoHash<tipo>::numRegOcupadosDesb(){
	return numRegOcupDesborde;
}

template <class tipo> string ArchivoHash<tipo>::nombrePrincipal(){
	return nombreArchPrinc;
}

template <class tipo> string ArchivoHash<tipo>::nombreDesborde(){
	return nombreArchDesb;
}

template <class tipo> ArchivoHash<tipo>::~ArchivoHash(){
	if (principal.is_open())
		principal.close();
	if (desborde.is_open())
		desborde.close();
}

# endif