package org.eda.practica02.ejercicio03;

import java.util.ArrayList;
import java.util.Iterator;
import java.io.*;
import java.util.*;

import org.eda.estructurasdatos.AVLTree;
import org.eda.estructurasdatos.BinarySearchTree;

public class CorrectorOrtografico {

	private AVLTree<String>tree;

	public CorrectorOrtografico(){
		tree = new AVLTree<String>();
	}

	public int computeLevenshteinDistance(String s, String t) {
		if (s == null || t == null) {
			throw new IllegalArgumentException("Strings must not be null");
		}

		/*
		 * The difference between this impl. and the previous is that, rather
		 * than creating and retaining a matrix of size s.length()+1 by
		 * t.length()+1, we maintain two single-dimensional arrays of length
		 * s.length()+1. The first, d, is the 'current working' distance array
		 * that maintains the newest distance cost counts as we iterate through
		 * the characters of String s. Each time we increment the index of
		 * String t we are comparing, d is copied to p, the second int[]. Doing
		 * so allows us to retain the previous cost counts as required by the
		 * algorithm (taking the minimum of the cost count to the left, up one,
		 * and diagonally up and to the left of the current cost count being
		 * calculated). (Note that the arrays aren't really copied anymore, just
		 * switched...this is clearly much better than cloning an array or doing
		 * a System.arraycopy() each time through the outer loop.)
		 *
		 * Effectively, the difference between the two implementations is this
		 * one does not cause an out of memory condition when calculating the LD
		 * over two very large strings.
		 */

		int n = s.length(); // length of s
		int m = t.length(); // length of t

		if (n == 0) {
			return m;
		} else if (m == 0) {
			return n;
		}

		int p[] = new int[n + 1]; // 'previous' cost array, horizontally
		int d[] = new int[n + 1]; // cost array, horizontally
		int _d[]; // placeholder to assist in swapping p and d

		// indexes into strings s and t
		int i; // iterates through s
		int j; // iterates through t

		char t_j; // jth character of t

		int cost; // cost

		for (i = 0; i <= n; i++) {
			p[i] = i;
		}

		for (j = 1; j <= m; j++) {
			t_j = t.charAt(j - 1);
			d[0] = j;

			for (i = 1; i <= n; i++) {
				cost = s.charAt(i - 1) == t_j ? 0 : 1;
				// minimum of cell to the left+1, to the top+1, diagonally left
				// and up +cost
				d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1]
						+ cost);
			}

			// copy current distance counts to 'previous row' distance counts
			_d = p;
			p = d;
			d = _d;
		}

		// our last action in the above loop was to switch d and p, so p now
		// actually has the most recent cost counts
		return p[n];
	}

	public void cargarDiccionario(String archivoEntrada) {
		// TODO Auto-generated method stub
		try{
			File f = new File(archivoEntrada);
			FileReader fr = new FileReader(f);
			BufferedReader br = new BufferedReader(fr);
			String entrada = br.readLine();

			while(entrada!=null){
				tree.add(entrada);
				entrada = br.readLine();
			}

			br.close();
		}catch(Exception e){
			e.printStackTrace();
		}
	}

	public ArrayList<String> listaSugerencias(int num, String word) {
		ArrayList<String> lista = new ArrayList<String>();
		String palabraNodo,palabra = "";
		PalabraPrioridad pP, top;
		int distancia;
		PriorityQueue<PalabraPrioridad> pQ = new PriorityQueue<PalabraPrioridad>(num);
		for (Iterator<String> iterator = tree.iterator(); iterator.hasNext();) {
			palabraNodo = iterator.next();
			distancia = this.computeLevenshteinDistance(word,palabraNodo);
			pP = new PalabraPrioridad(palabraNodo, distancia);
			if (pQ.size()==num){
				top = pQ.peek();
				if(pP.getDistancia() < top.getDistancia()){
					pQ.poll();
					pQ.add(pP);
				}
			}
			else
				pQ.add(pP);
		}

		for (int i = 0; i<num;i++)
			lista.add(pQ.poll().getPalabra());
		for (Iterator<String> iterator = lista.iterator(); iterator.hasNext();)
			palabra = iterator.next();
			lista.remove(palabra);
			lista.add(palabra);

		return lista;
	}

	public void addPalabra(String string) {
		if(tree.contains(string)==false){
			tree.add(string);
		}
	}

}