Untitled

package Trabalho_AV3;

import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.Objects;
import java.util.Scanner;

public class ArvoreBinariaBusca {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class Nodo {

        public String elemento;
        public Nodo esquerdo;
        public Nodo direito;

        public Nodo(String elemento) {
            this.elemento = elemento;
            this.esquerdo = null;
            this.direito = null;
        }
    }

    public Nodo raiz;
    public int nElementos;
    public int contador = 0;

    public ArvoreBinariaBusca() {
        this.raiz = null;
        this.nElementos = 0;
    }

    public int tamanho() {
        return this.nElementos;
    }

    public boolean estaVazia() {
        return this.raiz == null;
    }

    public void imprimePreOrdem() {
        this.preOrdem(this.raiz);
        System.out.println();
    }

    public void imprimePosOrdem() {
        this.posOrdem(this.raiz);
        System.out.println();
    }

    public void imprimeEmOrdem() {
        this.emOrdem(this.raiz);
        System.out.println();
    }

    public void preOrdem(Nodo nodo) {

        if (nodo == null)
            return;

        System.out.print(nodo.elemento + " ");
        this.preOrdem(nodo.esquerdo);
        this.preOrdem(nodo.direito);
    }

    public void posOrdem(Nodo nodo) {

        if (nodo == null)
            return;

        this.posOrdem(nodo.esquerdo);
        this.posOrdem(nodo.direito);
        System.out.print(nodo.elemento + " ");
    }

    public void emOrdem(Nodo nodo) {

        if (nodo == null)
            return;

        this.emOrdem(nodo.esquerdo);
        System.out.print(nodo.elemento + " ");
        this.emOrdem(nodo.direito);
    }

    public void insere(String elemento) {
        this.insere(elemento, this.raiz);
    }

    public void insere(String elemento, Nodo nodo) {

        Nodo novo = new Nodo(elemento);

        if (nodo == null) {
            this.raiz = novo;
            this.nElementos++;
            return;
        }

        if (elemento.compareTo(nodo.elemento) < nodo.elemento.compareTo(elemento)) {
            if (nodo.esquerdo == null) {
                nodo.esquerdo = novo;
                this.nElementos++;
                return;
            } else {
                this.insere(elemento, nodo.esquerdo);
            }
        }

        if (elemento.compareTo(nodo.elemento) > nodo.elemento.compareTo(elemento)) {
            if (nodo.direito == null) {
                nodo.direito = novo;
                this.nElementos++;
                return;
            } else {
                this.insere(elemento, nodo.direito);
            }
        }
    }

    private Nodo maiorElemento(Nodo nodo) {
        while (nodo.direito != null) {
            nodo = nodo.direito;
        }
        return nodo;
    }

    private Nodo menorElemento(Nodo nodo) {
        while (nodo.esquerdo != null) {
            nodo = nodo.esquerdo;
        }
        return nodo;
    }

    public boolean busca(String elemento) {
        return this.busca(elemento, this.raiz);
    }

    private boolean busca(String elemento, Nodo nodo) {
        if (nodo == null) {
            return false;
        }
        if (elemento.compareTo(nodo.elemento) < 0) {
            return this.busca(elemento, nodo.esquerdo);
        } else if (elemento.compareTo(nodo.elemento) > 0) {
            return this.busca(elemento, nodo.direito);
        } else {
            return true;
        }
    }
    public int buscaLinha(){
        return contador;
    }
}
class Hash{
    static class Nodo{
        public Nodo prox, ant;
        public String elemento;

        public Nodo(String elemento){
            this.elemento = elemento;
            this.prox = null;
            this.ant = null;
        }
    }
    public Nodo primeiro;
    public Nodo ultimo;
    public Nodo[] tabela;
    public int tamanho;

    public Hash(int tam_tabela){
        primeiro = null;
        ultimo = null;
        tabela = new Nodo[tam_tabela];
        tamanho = 0;
    }

    public String insert(String valor) throws Exception {

        //int pos = hash(valor);
        //int pos = toHashKey(valor) % tabela.length;
        int hash = toHashKey(valor);
        int pos = baseHash(hash, tabela.length);
        //int pos = Math.abs(valor.hashCode()) % tabela.length;

        Nodo node = new Nodo(valor);
        Nodo start = tabela[pos];

        if (tabela[pos] == null) {
            tabela[pos] = node;
        }
        else {
            node.prox = start;
            start.ant = node;
            tabela[pos] = node;
        }
        return node.elemento;
    }

    private int hash(String x)
    {
        int valor_hash = x.hashCode();

        valor_hash %= tabela.length;

        if (valor_hash < 0)
            valor_hash += tabela.length;

        return valor_hash;
    }

    int toHashKey(String s)
    {
        int A = 1952786893;
        int B = 367257;
        int v = B;
        for (int j = 0; j < s.length(); j++)
        {
            char c = s.charAt(j);
            v = A * (v + (int) c + j) + B;
        }

        if (v < 0) v = -v;
        return v;
    }

    int baseHash(int hashKey,int length)
    {
        double constant = (Math.sqrt(3) - 1);
        int base =  (int) Math.floor((length * ((constant* hashKey) - Math.floor(constant* hashKey))));
        return base;
    }

    public void mostra() throws Exception {
        for(int i = 0; i < tabela.length; i++){
            Nodo aux = tabela[i];
            while (aux != null){
                if(aux.elemento != null){
                    System.out.print(aux.elemento);
                    //return aux.elemento;
                }
                aux = aux.prox;
                System.out.println();
            }
        }
        //return null;
    }
}
class Hash_Int{
    static class No{
        public int dado;
        public No anterior;
        public No proximo;

        public No(int dado){
            this.dado = dado;
            this.anterior = null;
            this.proximo = null;
        }
    }

    public No primeiro;
    public No ultimo;

    public No[] tabela;
    public int tamanho;

    Hash_Int(int tamanho_hash){
        primeiro = null;
        ultimo = null;
        tabela = new No[tamanho_hash];
        tamanho = 0;
    }

    public boolean estaVazia(){
        return tamanho == 0;
    }

    public int getTamanho(){
        return tamanho;
    }

    public void adicionar(int valor){
        No novo = new No(valor);
        int pos = funcao_hashing(valor);
        No aux = tabela[pos];

        if(tabela[pos] == null){ //lista vazia
            tabela[pos] = novo;
            ultimo = novo;
        }
        else if (novo.dado <= tabela[pos].dado){
            novo.proximo = aux;
            aux.anterior = novo;
            tabela[pos] = novo;
        }
//        else if (novo.dado >= ultimo.dado){
//            tabela[pos].proximo = novo;
//            ultimo = novo;
//        }
        else{
            No anterior = null;
            No atual = tabela[pos];
            while (atual.proximo != null && atual.proximo.dado < novo.dado){
                atual = atual.proximo;
            }
            novo.proximo = atual.proximo;
            if(atual.proximo != null){
                novo.proximo.anterior = novo;
            }
            atual.proximo = novo;
            novo.anterior = atual;
        }
        tamanho++;
    }

    private int h(int valor){
        int hash = valor % tabela.length;
        hash %= tabela.length;
        if(hash < 0){
            hash += tabela.length;
        }
        return hash;
    }

    private int funcao_hashing(int valor){
        return valor % tabela.length;
    }
}
class AppMain{
    public static int contadorLinha(String text){
        return text.split("\r\n").length;
    }
    public static String lerArquivoString(String fileName)throws Exception {
        String dado = "";
        dado = new String(Files.readAllBytes(Paths.get(fileName)));
        return dado;
    }
    public static int contador_index(String regex) throws Exception {
        String dado = lerArquivoString("C:\\Users\\bruno\\Desktop\\test.txt");
        String[] str = dado.split(String.valueOf(regex));
        return str.length - 1;
    }

    public static void palavra_chave(String diretorio) throws Exception {
        String dado = lerArquivoString(diretorio);
        String[] slice = dado.split("[ ,.$\r\n]");
        for(int i = 0; i < slice.length; i++){
            ArvoreBinariaBusca g = new ArvoreBinariaBusca();
            g.insere(slice[i]);
            g.imprimeEmOrdem();
        }
    }

    public static void indice_remissivo(String dir_entrada, String dir_pc) throws Exception {
        String palchave = lerArquivoString(dir_pc);
        String dado = lerArquivoString(dir_entrada);

        String[] pc_split = palchave.split("[ ,.$\r\n]");
        String[] slice = dado.split("\r\n");

        for(int k = 0; k < pc_split.length; k++){

            for(int i = 0; i < slice.length ; i++){ //linhas

                String[] col = slice[i].split("[ ,.$]"); //colunas

                for(int j = 0; j < col.length; j++){

                    Hash h = new Hash(col.length);
                    ArvoreBinariaBusca e = new ArvoreBinariaBusca();

                    if(col[j] != "" || pc_split[k] != ""){
                        e.insere(col[j]);
                        h.insert(pc_split[k]);
                    }

                    if(e.busca(h.insert(pc_split[k]))){ //se achou o valor
                        System.out.println(pc_split[k]+" "+(i+1));
                    }
                }
                //System.out.println();
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Hash h = new Hash(26);
        ArvoreBinariaBusca a = new ArvoreBinariaBusca();
        indice_remissivo("C:\\Users\\bruno\\Desktop\\test2.txt","C:\\Users\\bruno\\Desktop\\pc2.txt");
        //palavra_chave("C:\\Users\\bruno\\Desktop\\pc.txt");
    }
}