////////////////////////////////////////////////////////////////////////////
//
// Fundamentos de Programación
// ETS Informática y Telecomunicaciones
// Universidad de Granada
// Departamento de Ciencias de la Computación e Inteligencia Artificial
// Autor: Juan Carlos Cubero
//
////////////////////////////////////////////////////////////////////////////

// Sopa de letras implementada como un vector de objetos SecuenciaCaracteres
// El método de búsqueda de una palabra dentro de otra, está implementado
// en la clase SecuenciaCaracteres

#include <iostream>
using namespace std;


struct ParFilaColumna{
   int fila;
   int columna;
};




class SecuenciaCaracteres{
private:
   static const int TAMANIO = 2e6;  // 2e6 es un real (dos millones) 
                                    // -> casting automático a int
                                    
                                    // Para poder dimensionar con un tamaño
                                    // tan grande, hay que cambiar unos parámetros
                                    // del compilador:
                                    // Herramientas -> Opciones del Compilador ->
                                    // Compilador -> Añadir las siguientes opciones
                                    // -Wl,--stack,26000000
   char v[TAMANIO];
   int utilizados;
   
   void IntercambiaComponentesDirectamente(int pos_izda, int pos_dcha){
      char intercambia;

      intercambia = v[pos_izda];
      v[pos_izda] = v[pos_dcha];
      v[pos_dcha] = intercambia;
   }
   
   bool EsCorrectaPosicion(int indice){
      return 0 <= indice && indice < utilizados;
   }
public:
   SecuenciaCaracteres()
      :utilizados(0) {
   }
   
   int Utilizados(){
      return utilizados;
   }
   
   int Capacidad(){
      return TAMANIO;
   }
   
   void EliminaTodos(){
      utilizados = 0;
   }
   
   void Aniade(char nuevo){
      if (utilizados < TAMANIO){
         v[utilizados] = nuevo;
         utilizados++;
      }
   }
   
   void Modifica(int posicion, char nuevo){
      if (EsCorrectaPosicion(posicion))      
         v[posicion] = nuevo;
   }

   char Elemento(int indice){
      return v[indice];
   }
   
   string ToString(){
      // Si el número de caracteres en memoria es muy grande,
      // es mucho más eficiente reservar memoria previamente
      // y usar push_back

      string cadena;

      cadena.reserve(utilizados);

      for (int i=0; i < utilizados; i++)
         cadena.push_back(v[i]);
         //cadena = cadena + v[i]  <- Evitarlo. Muy ineficiente para tamaños grandes;

      return cadena;
   }

   int PrimeraOcurrenciaEntre (int pos_izda, int pos_dcha, char buscado){
      int i = pos_izda;
      bool encontrado = false;

      while (i <= pos_dcha  &&  !encontrado)
         if (v[i] == buscado)
            encontrado = true;
         else
            i++;

      if (encontrado)
         return i;
      else
         return -1;
   }
   
   int PrimeraOcurrencia (char buscado){
      return PrimeraOcurrenciaEntre (0, utilizados - 1, buscado);
   }
   

   /////////////////////////////////////////////////////////////
   // Búsquedas
   
   // Precond: 0 <= izda <= dcha < utilizados
   int PosicionMinimoEntre(int izda, int dcha){
      int posicion_minimo = -1;
      char minimo;

      minimo = v[izda];
      posicion_minimo = izda;

      for (int i = izda+1 ; i <= dcha ; i++)
         if (v[i] < minimo){
            minimo = v[i];
            posicion_minimo = i;
         }

      return posicion_minimo;
   }
   
   int PosicionMinimo(){
      return PosicionMinimoEntre(0, utilizados - 1);
   }
   
   int BusquedaBinaria (char buscado){
      int izda, dcha, centro;
      bool encontrado = false;

      izda = 0;
      dcha = utilizados - 1;
      centro = (izda + dcha) / 2;

      while (izda <= dcha  &&  !encontrado){
         if (v[centro] == buscado)
            encontrado = true;
         else if (buscado < v[centro])
            dcha = centro - 1;
         else
            izda = centro + 1;

         centro = (izda + dcha) / 2;
      }

      if (encontrado)
         return centro;
      else
         return -1;
   }
   
   
   /////////////////////////////////////////////////////////////
   // Recorridos que modifican las componentes
   
   // Inserta un valor en la posición especificada
   void Inserta(int pos_insercion, char valor_nuevo){
      if (utilizados < TAMANIO  &&  pos_insercion >= 0    
         &&  pos_insercion <= utilizados){

         for (int i = utilizados ; i > pos_insercion ; i--)
            v[i] = v[i-1];

         v[pos_insercion] = valor_nuevo;
         utilizados++;
      }
   }

	/*
   Tipos de borrados:
      - Lógico
         Usar un valor de componente especial y marcar la componente con dicho valor
         Un vector de edades -> valor -1
         Un vector de caracteres alfabéticos -> '@'
         Ventajas: Muy rápido

         Inconvenientes: Cualquier procesado posterior del vector
         debe tratar las componentes marcadas de una forma especial

      - Físico
         Implica desplazar 1 posición a la izquierda, todas las componentes que hay a la derecha de
			la que queremos borrar.

         Tiene justo las ventajas e incovenientes contrarias que el método anterior.

       En esta versión, implementamos el borrado físico.
	*/

   // Elimina una componente, dada por su posición
   void Elimina (int posicion){
      /*
      Algoritmo:

		   Recorremos de izquierda a derecha toda las componentes
		   que hay a la derecha de la posición a eliminar
			   Le asignamos a cada componente la que hay a su derecha
      */
      if (posicion >= 0 && posicion < utilizados){
         int tope = utilizados-1;

         for (int i = posicion ; i < tope ; i++)
            v[i] = v[i+1];

         utilizados--;
      }

      // Nota:

      // En vez de usar la asignación
      //    v[i] = v[i+1];
      // también podríamos haber puesto lo siguiente:
      //    Modifica(i, Elemento(i+1));
      // Hemos preferido acceder directamente a las componentes con la notación en corchete
      // para aumentar la eficiencia del método Elimina, ya que si el vector es muy grande
      // tendrá que realizar muchos desplazamientos.

      // En general, desde dentro de la clase, los métodos de la clase Secuencia
      // accederán directamente a las componentes con la notación corchete

      // Además, cuando entramos en la función Elimina, comprobamos con el condicional
      // que los accesos a los índices son correctos.
      // Si usamos el método Modifica, volveríamos a comprobar lo mismo.

      // Nota:

      // ¿Y si en vez de asignar v[i] = v[i+1];
      // llamamos a IntercambiaComponentesDirectamente(i, i+1) ?
      // La componente se eliminaría pero realizando el doble de asignaciones
      // Obviamente, no es necesario intercambiar las componentes.
      // Únicamente debemos ir asignando v[i] = v[i+1] de izquierda a derecha.
   }
   
   
   /////////////////////////////////////////////////////////////
   // Algoritmos de ordenación
   
   void Ordena_por_Seleccion(){
      int pos_min;

      for (int izda = 0 ; izda < utilizados ; izda++){
         pos_min = PosicionMinimoEntre(izda, utilizados - 1);
         IntercambiaComponentesDirectamente(izda, pos_min);
      }
   }
   
   void Ordena_por_Insercion(){
      int izda, i;
      char a_desplazar;

      for (izda=1; izda < utilizados; izda++){
         a_desplazar = v[izda];

         for (i=izda; i > 0 && a_desplazar < v[i-1]; i--)
            v[i] = v[i-1];

         v[i] = a_desplazar;
      }
   }
   
   void InsertaOrdenadamente(char valor_nuevo){
        int i;

        if (utilizados > TAMANIO){
           for (i=utilizados; i>0 && valor_nuevo < v[i-1]; i--)
                v[i] = v[i-1];

           v[i] = valor_nuevo;
           utilizados++;
        }
   }
   
   
   void Ordena_por_Burbuja(){
      int izda, i;

      for (izda = 0; izda < utilizados; izda++)
        for (i = utilizados-1 ; i > izda ; i--)
          if (v[i] < v[i-1])
             IntercambiaComponentesDirectamente(i, i-1);
   }
   
   void Ordena_por_BurbujaMejorado(){
      int izda, i;
      bool cambio;

      cambio= true;

      for (izda=0; izda < utilizados && cambio; izda++){
        cambio=false;

        for (i=utilizados-1 ; i>izda ; i--)
          if (v[i] < v[i-1]){
             IntercambiaComponentesDirectamente(i, i-1);
             cambio=true;
          }
      }
   }
   
   void AniadeVarios(SecuenciaCaracteres nuevos){
      int totales_a_aniadir = nuevos.Utilizados();
      
      for (int i = 0; i < totales_a_aniadir; i++)
         Aniade(nuevos.Elemento(i)); // Es importante entender
   }


   SecuenciaCaracteres ToUpper(){
      SecuenciaCaracteres en_mayuscula;
      
      for(int i = 0; i < utilizados; i++)
         en_mayuscula.Aniade(toupper(v[i]));

      return en_mayuscula;
   }


   
   
   // Busca una sub-secuencia
   // Las posiciones deben estar en orden y consecutivas
   int PosContiene ( int izda, int dcha, SecuenciaCaracteres a_buscar) {
      int  inicio;
      int  ultima_componente;
      bool encontrado;
      int  posicion_contiene;
      bool va_coincidiendo;
      int  utilizados_a_buscar;

      /*
      Tenemos una secuencia "grande" de tamaño G y otra pequeña de tamaño P

      Recorrer la secuencia "grande" fijando una posición inicial inicio
      La última posición inicial a probar será G-P
         A partir de inicio recorrer en paralelo las
         dos secuencias "grande" y "pequeña"
         Si no coinciden todas las componentes, hay que
         empezar de nuevo a partir de inicio + 1.
      */

      utilizados_a_buscar = a_buscar.Utilizados();

      if (utilizados_a_buscar > 0){
         ultima_componente = dcha + 1 - utilizados_a_buscar;
         encontrado = false;

         for (inicio = izda; inicio <= ultima_componente && !encontrado; inicio++){
            va_coincidiendo = true;

            for (int i = 0; i < utilizados_a_buscar && va_coincidiendo; i++)
               va_coincidiendo = v[inicio + i] == a_buscar.Elemento(i);

            if (va_coincidiendo){
               posicion_contiene = inicio;
               encontrado = true;
            }
         }
      }
      else
         encontrado = false;

      if (encontrado)
         return posicion_contiene;
      else
         return -1;
   /*
   Batería de pruebas:
      Los dos vectores vacíos.
      Alguno de ellos vacío.
      Los dos vectores iguales.  atti / atti
      Que no se encuentre.   atti / tj
      Que se encuentre al principio.  atti / at
      Que se encuentre justo al final. atti / ti
      Que haya un emparejamiento parcial pero no total,
      aunque luego sí se encuentre.  atttij / ti
   */
   }
   
   
   
   // Busca una sub-secuencia
   // Las posiciones deben estar en orden y consecutivas
   int PosContiene (SecuenciaCaracteres a_buscar){
      return PosContiene(0, utilizados - 1, a_buscar);
   }
};




/*
LectorSecuencias:
   Permite la lectura de objetos de la clase SecuenciaCaracteres.
   Condiciones de parada que se pueden establecer (conjuntamente):
      - Hasta llegar a un terminador
      - Hasta completar un número fijo de caracteres
     
     
LectorSecuencias{
   void SetTerminador (char terminador_entrada)
   void SetTope(int num_valores_a_leer)
   void ResetRestricciones()
   SecuenciaCaracteres Lee()
}
*/
class LectorSecuencias{
private:
   char terminador;
   int tope;
   int capacidad_maxima;

   bool FlujoAbierto(){
      return !cin.fail();
   }
   
public:
   LectorSecuencias(){
      ResetRestricciones();
   }
   
   void SetTerminador (char terminador_entrada){
      terminador = terminador_entrada;
   }
   
   void SetTope(int num_valores_a_leer){
      if (0 < num_valores_a_leer && num_valores_a_leer <= capacidad_maxima)
         tope = num_valores_a_leer;
   }
   
   void ResetRestricciones(){
      SecuenciaCaracteres cualquiera;
      
      capacidad_maxima = cualquiera.Capacidad();
      tope = capacidad_maxima;
      terminador = '\n';
   }
   
   SecuenciaCaracteres Lee(){   
      SecuenciaCaracteres a_leer;
      char caracter;      
      bool parar_lectura;
      bool es_terminador;
      int total_leidos = 0;
      
      do{            
         if (FlujoAbierto()){            
            caracter = cin.get();  
            total_leidos++;
            es_terminador = caracter == terminador;
                                  
            if (!es_terminador) 
               a_leer.Aniade(caracter); 
            
            parar_lectura = es_terminador || total_leidos == tope;                           
         }
      }while (!parar_lectura);
      
      return a_leer;
   }
};




class SopaLetras{
private:
   static const int MAX_FIL = 50;
   SecuenciaCaracteres v[MAX_FIL];
   int util_fil;
   int util_col;   // Podría ponerse const int
public:
   // Prec: 0 < numero_de_columnas <= Capacidad de SecuenciaCaracteres
   SopaLetras(int numero_de_columnas)
      :util_fil(0), util_col(numero_de_columnas)
   {
   }
   SopaLetras(SecuenciaCaracteres primera_fila)
      :SopaLetras(primera_fila.Utilizados())
   {
      Aniade(primera_fila);
   }
   int CapacidadFilas(){
      return MAX_FIL;
   }
   int FilasUtilizadas(){
      return util_fil;
   }
   int ColUtilizadas(){
      return util_col;
   }
   char Elemento(int fil, int col){
      return v[fil].Elemento(col);
      // return Fila(fil).Elemento(col);
   }
   SecuenciaCaracteres Fila(int fil){
      return v[fil];
   }
   void Aniade(SecuenciaCaracteres  fila_nueva){
      if (util_fil < MAX_FIL &&
         fila_nueva.Utilizados() == util_col){
            v[util_fil] = fila_nueva;
            util_fil++;
         }
   }

   ParFilaColumna BuscaPalabra (SecuenciaCaracteres a_buscar){
      bool encontrado;
      ParFilaColumna pos_encontrado;
      int  tamanio_a_buscar;
      SecuenciaCaracteres fila;
      int col_encontrado;

      encontrado = false;
      pos_encontrado.fila = pos_encontrado.columna = -1;
      tamanio_a_buscar = a_buscar.Utilizados();

      if (tamanio_a_buscar <= util_col){
         for (int i = 0; i < util_fil && !encontrado; i++){
            fila = v[i];
            col_encontrado = fila.PosContiene(a_buscar);
            
            if (col_encontrado != -1){
               encontrado = true;
               pos_encontrado.fila = i;
               pos_encontrado.columna = col_encontrado;
            }  
         }
      }      
      
      return pos_encontrado;
   }
};




int main(){
   const char TERMINADOR = '#';
   char letra;
   int  num_columnas, num_filas;   
   ParFilaColumna encontrado;
   SecuenciaCaracteres secuencia, a_buscar;
   LectorSecuencias lector;
   
   cout << "\nSopa de letras. Introduzca los datos en el siguiente orden: "
        << "\nEl número de columnas de la sopa"
        << "\nEl número de filas"
        << "\nLos caracteres de cada fila con un espacio en blanco al final\n";
        
   cin >> num_columnas;
   cin >> num_filas;
   
   SopaLetras sopa(num_columnas);
   lector.SetTope(num_columnas);
   
   for (int i=0 ; i<num_filas; i++){   
      char blanco;
      secuencia = lector.Lee();
      sopa.Aniade(secuencia);
      secuencia.EliminaTodos();
      blanco = cin.get();
   }

   // cout << "\nSOPA:\n" << sopa.ToString();
   
   cout << "\n\nIntroduzca los caracteres de la palabra a buscar: ";
   cout << "Use el carácter " << TERMINADOR << " para terminar\n";

   lector.ResetRestricciones();
   lector.SetTerminador(TERMINADOR);
   a_buscar = lector.Lee();
   
   encontrado = sopa.BuscaPalabra(a_buscar);
   cout << "\nPosición encontrado:\n" << encontrado.fila << " " << encontrado.columna;
   
   // 
   /*
   6 5ACEROS LASERY TIOJDE ADPNED RAZONT LASER#      
   
   Salida:
   1 0
   */
   
   /*
   6 5ACEROS LASERY TIOJDE ADPNED RAZONT LASEO#
   
   Salida:
   -1 -1
   */
}