Word Corrector

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package ficha4_corretor.aed;

import java.io.*;
import java.util.*;

class FicheiroTexto{

    private BufferedReader fR;
    private BufferedWriter fW;

    public void abreLeitura(String nomeDoFicheiro) throws IOException{
        fR = new BufferedReader(new FileReader(nomeDoFicheiro));
    }
    public void abreEscrita(String nomeDoFicheiro) throws IOException{
        fW = new BufferedWriter(new FileWriter(nomeDoFicheiro));
    }

    public String leLinha() throws IOException{
        return fR.readLine();
    }

    public void escreveLinha(String linha) throws IOException{
        fW.write(linha,0,linha.length());
        fW.newLine();
    }

    public void escreveNumero(int num) throws IOException{
        String st = "";
        st = st.valueOf(num);
        escreveLinha(st);
    }

    public void fechaLeitura() throws IOException {
        fR.close();
    }
    public void fechaEscrita() throws IOException {
        fW.close();
    }
}

class Word{
    public String palavra;
    public int frequencia;

    public Word(String s,int frequencia){
        this.palavra  = s;
        this.frequencia = frequencia;
    }

    @Override
    public String toString(){
        return palavra;
    }
}

class HashNodeWord{
    public Word chave;
    public int valor;

    public HashNodeWord next;

    public HashNodeWord(Word word, int valor){
        this.chave = word;
        this.valor = valor;
    }
}

class Dicio{

    public int numInicial;
    public ArrayList<HashNodeWord> listaPalavras;
    public int tamanho;

    public Dicio(){
        listaPalavras = new ArrayList<>();
        numInicial = (int) (4927*1.30);
        tamanho = 0;

        for (int i = 0; i < numInicial; i++){
            listaPalavras.add(null);
        }
    }

    public int colisao(){
        int contador = 0;
        for(HashNodeWord a : listaPalavras){
            if(a != null){
                System.out.println(a.chave);
                //contador++;
            }
        }
        return contador;
    }

    public Word[] indexes(Word word){
        Word[] Final = new Word[20];
        int bucketIndex = (int) getIndice(word.palavra);
        HashNodeWord head = listaPalavras.get(bucketIndex);
        int n=0;
        while(listaPalavras.get(bucketIndex + n) == null){
             n += 1;
             if(listaPalavras.get(bucketIndex + n) != null){
                 head = listaPalavras.get(bucketIndex + n);
             }
        }

        HashNodeWord Bk = head;

        for(int i=0;i<10;i++){
                HashNodeWord original = head;
                Final[i] = head.chave;
                head = head.next;
                if(head == null){
                    bucketIndex = (int) getIndice(original.chave.palavra);
                    n=1;
                    if(bucketIndex + n == numInicial - n){
                        break;
                    }
                    head = listaPalavras.get(bucketIndex + n);
                    while(listaPalavras.get(bucketIndex + n) == null){
                        n += 1;
                        if(listaPalavras.get(bucketIndex + n) != null){
                            head = listaPalavras.get(bucketIndex + n);
                        }
                    }

                }
        }

        for(int i=0;i<10;i++){
            Final[i+10] = Bk.chave;
            n = 1;
            bucketIndex = (int) getIndice(Bk.chave.palavra);
            if(bucketIndex - n == 1){
                break;
            }
            if(listaPalavras.get(bucketIndex - n) == null){
                while(listaPalavras.get(bucketIndex - n) == null){
                    n+=1;
                    if(listaPalavras.get(bucketIndex - n) != null){
                            Bk = listaPalavras.get(bucketIndex - n);
                    }
                }
            }
            else{
                Bk = listaPalavras.get(bucketIndex - n);
            }
        }
        return Final;
    }

    public int getIndice(String palavra){
        int hashCode = SDBMHash(palavra);
        int index = hashCode % numInicial;
        return index;
    }

    public int getFrequencia(String palavra){
         int bucketIndex = (int) getIndice(palavra);
            HashNodeWord head = listaPalavras.get(bucketIndex);
            return head.chave.frequencia;
    }

    public int getNode(String palavra){
        int bucketIndex = (int) getIndice(palavra);
        HashNodeWord head = listaPalavras.get(bucketIndex);

        while (head != null){
            if (head.chave.equals(palavra)){
                return head.valor;
            }
            head = head.next;
        }

        return 0;
    }

    public int verifica(Word word){
        int bucketIndex = (int) getIndice(word.palavra);
        HashNodeWord head = listaPalavras.get(bucketIndex);
        if(head != null && word.palavra.equals(head.chave.palavra)){
            return 0;
        }
        else{
            return 1;
        }
    }

    public void add(Word word, int valor){
        int bucketIndex = (int) getIndice(word.palavra);
        HashNodeWord head = listaPalavras.get(bucketIndex);

        while (head != null){
            if (head.chave.equals(word)){
                head.valor = valor;
                return;
            }
            head = head.next;
        }

        tamanho++;
        head = listaPalavras.get(bucketIndex);
        HashNodeWord novo = new HashNodeWord(word, valor);
        novo.next = head;
        listaPalavras.set(bucketIndex, novo);

        if ((1.0*tamanho)/numInicial >= 0.7){
            tamanho = 0;
            ArrayList<HashNodeWord> temp = listaPalavras;
            listaPalavras = new ArrayList<>();
            numInicial = 2 * numInicial;
            for (int i = 0; i < numInicial; i++)
                listaPalavras.add(null);

            for (HashNodeWord headNode : temp){
                while (headNode != null){
                    add(headNode.chave, headNode.valor);
                    headNode = headNode.next;
                }
            }
        }
    }

    public int SDBMHash(String str){
      int hash = 0;

      for(int i = 0; i < str.length(); i++){
         hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
      }

      if(hash<=0){
        hash *= -1;
      }

      return hash;
   }
}


class Hist{
    public String palavra;
    public ArrayList<Word> corrigida;
    public int vezes;

    public Hist(String palavra){
        this.palavra = palavra;
        this.corrigida = new ArrayList<>();
        this.vezes = 1;
    }

    public void addCorrigida(Word corr){
        this.corrigida.add(corr);
    }

    public int getVezes(){
        return this.vezes;
    }
}

class HashNodeHist{
    public Hist chave;
    public int valor;

    public HashNodeHist next;

    public HashNodeHist(Hist chave, int valor){
        this.chave = chave;
        this.valor = valor;
    }
}

class Historico{

    public int numInicial;
    public ArrayList<HashNodeHist> listaPalavras;
    public int tamanho;

    public Historico(){
        listaPalavras = new ArrayList<>();
        numInicial = (int) (4927*1.30);
        tamanho = 0;

        for (int i = 0; i < numInicial; i++){
            listaPalavras.add(null);
        }

    }

    public int colisao(){
        int contador = 0;
        for(HashNodeHist a : listaPalavras){
            if(a != null){
                System.out.println(a.chave.palavra + " " + a.chave.corrigida + " " + a.chave.vezes);
                for(Word w:a.chave.corrigida){
                    System.out.println(w.frequencia);
                }
                contador++;
            }
        }
        return contador;
    }

    public int getIndice(String palavra){
        int hashCode = SDBMHash(palavra);
        int index = hashCode % numInicial;
        return index;
    }

    public int getNode(String palavra){
        int bucketIndex = (int) getIndice(palavra);
        HashNodeHist head = listaPalavras.get(bucketIndex);

        while (head != null){
            if (head.chave.equals(palavra)){
                return head.valor;
            }
            head = head.next;
        }
        return 0;
    }

    public HashNodeHist getNode2(Hist word){
        int bucketIndex = (int) getIndice(word.palavra);
        HashNodeHist head = listaPalavras.get(bucketIndex);

        return head;
    }

    public int verifica(Hist word){
        int bucketIndex = (int) getIndice(word.palavra);
        HashNodeHist head = listaPalavras.get(bucketIndex);
        if(head != null && word.palavra.equals(head.chave.palavra)){
            return 0;
        }
        else{
            return 1;
        }
    }

    public void addVezes(Hist word,Word palavra){
        int bucketIndex = (int) getIndice(word.palavra);
        HashNodeHist head = listaPalavras.get(bucketIndex);
        int vezes = head.chave.getVezes();
        vezes+=1;
        int condicao = 1;
        for (Word w: head.chave.corrigida){
            if(w.palavra.equals(palavra.palavra)){
                condicao = 0;
            }
        }
        if(condicao == 1){
            head.chave.corrigida.add(palavra);
        }
        head.chave.vezes = vezes;
    }

    public void add(Hist word, int valor){
        int bucketIndex = (int) getIndice(word.palavra);
        HashNodeHist head = listaPalavras.get(bucketIndex);

        while (head != null){
            if (head.chave.equals(word)){
                head.valor = valor;
                return;
            }
            head = head.next;
        }

        tamanho++;
        head = listaPalavras.get(bucketIndex);
        HashNodeHist novo = new HashNodeHist(word, valor);
        novo.next = head;
        listaPalavras.set(bucketIndex, novo);

        if ((tamanho)/numInicial >= 0.7){
            tamanho = 0;
            ArrayList<HashNodeHist> temp = listaPalavras;
            listaPalavras = new ArrayList<>();
            numInicial = 2 * numInicial;
            for (int i = 0; i < numInicial; i++)
                listaPalavras.add(null);

            for (HashNodeHist headNode : temp){
                while (headNode != null){
                    add(headNode.chave, headNode.valor);
                    headNode = headNode.next;
                }
            }
        }
    }

    public int SDBMHash(String str){
      int hash = 0;

      for(int i = 0; i < str.length(); i++){
         hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
      }

      if(hash<=0){
            hash *= -1;
       }

      return hash;
   }
}

/**
 *
 * @author j_mig_000
 */
public class Ficha4_CorretorAED {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        // TODO code application logic here

        Scanner scanner = new Scanner(System.in);
        String input,comando,line;
        StringTokenizer st;
        FicheiroTexto f = new FicheiroTexto();

        Dicio dicio = new Dicio();
        Historico historico  = new Historico();
        int contador=0;
        Word[] palavras = new Word[20];

        f.abreLeitura("words.txt");


        try{
            while((line = f.leLinha()) != null){
                String[] split = line.split(" ");
                Word word = new Word(split[1],Integer.valueOf(split[0]));
                dicio.add(word, (int) SDBMHash(word.palavra));
            }
            f.fechaLeitura();
        }catch (IOException e){
            System.out.printf("Ocorreu a excepção %s ao ler o ficheiro\n",e);
        }catch (NumberFormatException e){
            System.out.printf("Ocorreu a %s ao ler o ficheiro\n",e);
        }

        //contador = mesa.colisao();

        do{
            input = readLn(200);
            st= new StringTokenizer(input.trim());
            comando = st.nextToken();
            if(comando.equals("FIMFIM")){
                return;
            }
            else{
                Word word = new Word(comando,0);
                palavras = dicio.indexes(word);

                if(dicio.verifica(word) == 0){
                    System.out.println("Palavra no dicio");
                }
                else{
                    LinkedList<Word> primario = new LinkedList<>();//1º metodo
                    LinkedList<Word> secundario = new LinkedList<>();//2º metodo
                    LinkedList <Word> story = new LinkedList<>(); //historico
                    LinkedList<Word> last = new LinkedList<>(); //palavras para mostrar

                    Add(dicio,word,primario);
                    Sub(dicio,word,primario);
                    Change(dicio,word,primario);
                    Switch(dicio,word,primario);

                    if(primario.size()>1) QuickSort(primario,0,primario.size()-1);

                    /*System.out.println("\n");
                    for(Word s:primario){
                        System.out.println(s.palavra + " " + s.frequencia);
                    }*/

                    for(int i = 0;i<palavras.length;i++){
                        if(palavras[i] != null && secundario != null){
                            int condicao = 0;
                            for(Word s: secundario){
                                if(((Word) s).equals(palavras[i])){
                                    condicao = 1;
                                }
                            }
                            if(condicao == 0){
                                secundario.add(palavras[i]);
                            }
                        }
                    }

                    if(secundario.size()>1) QuickSort(secundario,0,secundario.size()-1);

                    /*System.out.println("\n");
                    for(Word s:secundario){
                        System.out.println(s.palavra + " " + s.frequencia);
                    }*/

                    Hist hist = new Hist(comando);
                    if(historico.verifica(hist) == 0){
                        for(Word w: historico.getNode2(hist).chave.corrigida){
                            story.add(w);
                        }
                    }

                    /*if(story != null){
                        for(Word s:story){
                            System.out.println(s.palavra + " " + s.frequencia);
                        }
                    }*/

                    if(story.size() > 1){
                        QuickSort(story,0,story.size()-1);
                    }

                    for(Word s:story){
                        int condicao  = 1;
                        for(Word k:last){
                            if (s.palavra.equals(k.palavra)) condicao = 0;
                        }
                        if(condicao == 1){
                            last.add(s);
                        }
                    }

                    if(last.size()<5){
                        for(Word s:primario){
                            int condicao  = 1;
                            for(Word k:last){
                                if (s.palavra.equals(k.palavra)) condicao = 0;
                            }
                            if(condicao == 1){
                                last.add(s);
                            }
                            if(last.size() == 5){
                                break;
                            }
                        }
                    }

                    if(last.size()<5){
                        for(Word s:secundario){
                            int condicao  = 1;
                            for(Word k:last){
                                if (s.palavra.equals(k.palavra)) condicao = 0;
                            }
                            if(condicao == 1){
                                last.add(s);
                            }
                            if(last.size() == 5){
                                break;
                            }
                        }
                    }

                    System.out.println("Palavra nao encontrada no dicionario");
                    for(int i = 0;i<5;i++){
                        System.out.println("Trocar com " + "'" + last.get(i)+ "'" + "? Prima 1 para aceitar e 2 para recusar");
                        int resposta = scanner.nextInt();
                        if(resposta == 1){
                            System.out.println("Palavra corrigida");
                            hist.addCorrigida(last.get(i));
                            if(historico.verifica(hist) == 0){
                                historico.addVezes(hist,last.get(i));
                            }
                            else{
                                historico.add(hist,(int) SDBMHash(comando));
                            }
                            //contador = historico.colisao();
                            break;
                        }
                        if(resposta == 2){
                            if(resposta == 2 && i == 4){
                                System.out.println("Deseja adicionar a palavra ao dicionario? Prima 1 para adicionar");
                                resposta = scanner.nextInt();
                                if(resposta == 1){
                                    Word nova = new Word(comando,0);
                                    dicio.add(nova, (int) SDBMHash(word.palavra));
                                    System.out.println("Palavra adicionado");
                                }
                                else break;
                            }
                            else continue;
                        }
                        if(resposta != 1 && resposta != 2){
                            System.out.println("Insira outro numero");
                            i = i-1;
                        }
                    }
                }
            }
        }while(true);
    }

    static String readLn (int maxLg){
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        String line = "";
        try {
            while (lg < maxLg){
                car = System.in.read();
                if ((car < 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }
        catch (IOException e){
            return (null);
        }
        if ((car < 0) && (lg == 0)) return (null);
        return (new String (lin, 0, lg));
    }

    static long SDBMHash(String str){
      long hash = 0;

      for(int i = 0; i < str.length(); i++){
         hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
      }
      if(hash<-1){
          hash *=-1;
      }
      return hash;
   }

    static void Switch(Dicio dicio,Word word,LinkedList<Word> Lista){
        for(int i = 0 ;i < word.palavra.length()-1;i++){
            for (int j = 0; j < word.palavra.length(); j++) {
                char[] letras = word.palavra.toCharArray();
                char temp = letras[j];
                letras[j] = letras[i];
                letras[i] = temp;

                Word nova = new Word(new String(letras),0);
                //System.out.println(nova.palavra);
                if(dicio.verifica(nova) == 0){
                    int condicao = 1;
                    for (Word s:Lista){
                        if(s.palavra.equals(nova.palavra)){
                            condicao = 0;
                        }
                    }
                    if(condicao == 1){
                        //System.out.println(nova.palavra);
                        nova.frequencia = dicio.getFrequencia(nova.palavra);
                        Lista.add(nova);
                    }
                }
                Add2(dicio,nova,Lista);
                Change2(dicio,nova,Lista);
                Sub2(dicio,nova,Lista);

            }
        }
    }

    static void Switch2(Dicio dicio,Word word,LinkedList<Word> Lista){
        for(int i = 0 ;i < word.palavra.length()-1;i++){
            for (int j = 0; j < word.palavra.length(); j++) {
                char[] letras = word.palavra.toCharArray();
                char temp = letras[j];
                letras[j] = letras[i];
                letras[i] = temp;

                Word nova = new Word(new String(letras),0);
                //System.out.println(nova.palavra);
                if(dicio.verifica(nova) == 0){
                    int condicao = 1;
                    for (Word s:Lista){
                        if(s.palavra.equals(nova.palavra)){
                            condicao = 0;
                        }
                    }
                    if(condicao == 1){
                        //System.out.println(nova.palavra);
                        nova.frequencia = dicio.getFrequencia(nova.palavra);
                        Lista.add(nova);
                    }
                }
            }
        }
    }

    static void Change(Dicio dicio,Word word,LinkedList<Word> Lista){
        String letras = "abcdefghijklmnopqrstuvwxyz";
        for(int i =0 ;i<word.palavra.length();i++){
            for (int j = 0; j < letras.length(); j++) {
                Word temp;
                if(i == 0){
                    temp = new Word(letras.charAt(j) + word.palavra.substring(i+1, word.palavra.length()),0);
                }
                if(i>0 && i < word.palavra.length()){
                    temp = new Word(word.palavra.substring(0, i-1) + letras.charAt(j) + word.palavra.substring(i, word.palavra.length()),0);
                }
                else{
                    temp = new Word(word.palavra.substring(0, word.palavra.length()-1) + letras.charAt(j),0);
                }
                //System.out.println(nova.palavra);
                if(dicio.verifica(temp) == 0){
                    int condicao = 1;
                    for (Word s:Lista){
                        if(s.palavra.equals(temp.palavra)){
                            condicao = 0;
                        }
                    }
                    if(condicao == 1){
                        //System.out.println(nova.palavra);
                        temp.frequencia = dicio.getFrequencia(temp.palavra);
                        Lista.add(temp);
                    }
                }

                Add2(dicio,temp,Lista);
                Switch2(dicio,temp,Lista);
                Change2(dicio,temp,Lista);
                Sub2(dicio,temp,Lista);
            }
        }
    }

    static void Change2(Dicio dicio,Word word,LinkedList<Word> Lista){
        String letras = "abcdefghijklmnopqrstuvwxyz";
        for(int i =0 ;i<word.palavra.length();i++){
            for (int j = 0; j < letras.length(); j++) {
                Word temp;
                if(i == 0){
                    temp = new Word(letras.charAt(j) + word.palavra.substring(i+1, word.palavra.length()),0);
                }
                if(i>0 && i < word.palavra.length()){
                    temp = new Word(word.palavra.substring(0, i-1) + letras.charAt(j) + word.palavra.substring(i, word.palavra.length()),0);
                }
                else{
                    temp = new Word(word.palavra.substring(0, word.palavra.length()-1) + letras.charAt(j),0);
                }
                //System.out.println(nova.palavra);
                if(dicio.verifica(temp) == 0){
                    int condicao = 1;
                    for (Word s:Lista){
                        if(s.palavra.equals(temp.palavra)){
                            condicao = 0;
                        }
                    }
                    if(condicao == 1){
                        //System.out.println(nova.palavra);
                        temp.frequencia = dicio.getFrequencia(temp.palavra);
                        Lista.add(temp);
                    }
                }
            }
        }
    }

    static void Add(Dicio dicio,Word word,LinkedList<Word> Lista){
        String letras = "abcdefghijklmnopqrstuvwxyz";
        for(int i =0 ;i<word.palavra.length();i++){
            for (int j = 0; j < letras.length(); j++) {
                Word temp = new Word(word.palavra.substring(0, i) + letras.charAt(j) + word.palavra.substring(i, word.palavra.length()),0);
                //System.out.println(nova.palavra);
                if(dicio.verifica(temp) == 0){
                    int condicao = 1;
                    for (Word s:Lista){
                        if(s.palavra.equals(temp.palavra)){
                            condicao = 0;
                        }
                    }
                    if(condicao == 1){
                        //System.out.println(nova.palavra);
                        temp.frequencia = dicio.getFrequencia(temp.palavra);
                        Lista.add(temp);
                    }
                }
                Add2(dicio,temp,Lista);
                Switch2(dicio,temp,Lista);
                Change2(dicio,temp,Lista);
            }
        }
    }

    static void Add2(Dicio dicio,Word word,LinkedList<Word> Lista){
        String letras = "abcdefghijklmnopqrstuvwxyz";
        for(int i =0 ;i<word.palavra.length();i++){
            for (int j = 0; j < letras.length(); j++) {
                Word temp = new Word(word.palavra.substring(0, i) + letras.charAt(j) + word.palavra.substring(i, word.palavra.length()),0);
                //System.out.println(nova.palavra);
                if(dicio.verifica(temp) == 0){
                    int condicao = 1;
                    for (Word s:Lista){
                        if(s.palavra.equals(temp.palavra)){
                            condicao = 0;
                        }
                    }
                    if(condicao == 1){
                        //System.out.println(nova.palavra);
                        temp.frequencia = dicio.getFrequencia(temp.palavra);
                        Lista.add(temp);
                    }
                }
            }
        }
    }

    static void Sub(Dicio dicio,Word word,LinkedList<Word> Lista){
        if(word.palavra.length() > 2){
            for(int i=0;i<word.palavra.length();i++){
                Word temp = new Word(word.palavra.substring(0,i) + word.palavra.substring(i+1,word.palavra.length()),0);
                //System.out.println(nova.palavra);
                if(dicio.verifica(temp) == 0){
                    int condicao = 1;
                    for (Word s:Lista){
                        if(s.palavra.equals(temp.palavra)){
                            condicao = 0;
                        }
                    }
                    if(condicao == 1){
                        //System.out.println(nova.palavra);
                        temp.frequencia = dicio.getFrequencia(temp.palavra);
                        Lista.add(temp);
                    }
                }
                Switch2(dicio,temp,Lista);
                Change2(dicio,temp,Lista);
                Sub2(dicio,temp,Lista);
            }
        }
    }

    static void Sub2(Dicio dicio,Word word,LinkedList<Word> Lista){
        if(word.palavra.length() > 2){
            for(int i=0;i<word.palavra.length();i++){
                Word nova = new Word(word.palavra.substring(0,i) + word.palavra.substring(i+1,word.palavra.length()),0);
                //System.out.println(nova.palavra);
                if(dicio.verifica(nova) == 0){
                    int condicao = 1;
                    for (Word s:Lista){
                        if(s.palavra.equals(nova.palavra)){
                            condicao = 0;
                        }
                    }
                    if(condicao == 1){
                        //System.out.println(nova.palavra);
                        nova.frequencia = dicio.getFrequencia(nova.palavra);
                        Lista.add(nova);
                    }
                }
            }
        }
    }

    static void QuickSort(LinkedList<Word> Array,int minimo,int maximo){
        int i = minimo;
        int j = maximo;
        Word pivot = Array.get(minimo + ((maximo-minimo)/2));

        while (i <= j) {
            while(Array.get(i).frequencia > pivot.frequencia) {
                i++;
            }
            while(Array.get(j).frequencia < pivot.frequencia) {
                j--;
            }
            if (i <= j) {
                Word temp = Array.get(i);
                Array.set(i, Array.get(j));
                Array.set(j, temp);
                i++;
                j--;
            }
        }
        if (minimo < j){
            QuickSort(Array,minimo,j);
        }
        if (i < maximo){
            QuickSort(Array,i,maximo);
        }
    }
}