[PITCH] COLABORE E APRENDA: IMPLEMENTANDO DO ZERO ESTRUTURAS DE DADOS E SEUS ALGORITMOS EM JAVA

Olá, caros leitores do tabnews. Se você gosta de algoritmos e estrutura de dados, está no lugar certo! Este é o primeiro de uma série de posts que estou planejando, onde vamos passar desde pilhas e filas, por grafos, árvores (não só as binárias, mas AVL, rubro negra e o que mais empolgar), tabelas hash e muito mais, se engajar. Outras formas de alocação também serão abordadas (encadeada, duplamente encadeada e circular). Meu objetivo não é explicar as estruturas ou os algoritmos e deixar você pular para o próximo post. Eu quero criar um espaço de aprendizado coletivo onde iremos aprender juntos tudo sobre como desenvolver do zero nossa própria biblioteca de algoritmos/estrutura de dados em Java! Apesar de parecer ambicioso, a meta não é codar nossa versão otimizada do ArrayList ou tentar competir com as implementações padrão do Java, mas sim entender e tomar as decisões de projeto para entender por debaixo dos panos como funcionam tais classes que utilizamos a todo momento. Se este ou qualquer um dos posts subsequentes fizer você revisar seu velho livro de estrutura de dados e seus algoritmos ou visitar a documentação do Java, então será uma vitória. Peço que leia até o final caso pense em pular o post, combinado?

Antes de mais nada, acesse o repositório do projeto: https://github.com/Natanf0/Lists.git

1. Flexibilidade com Generics:

Em primeiro lugar, é necessário pensar nos dados que vamos manipular nas estruturas. Se o objetivo fosse puramente implementar as operações de uma pilha, poderia considerar que todo nó é apenas um número inteiro. Mas queremos que seja flexível, onde você possa criar uma pilha de Produtos (assim como as implementações do Java). No entanto, para fins de algoritmos de ordenação, ao invés de solicitar um Comparable, e para fins de identificar se um objeto é igual ao outro (nosso famoso .equals()), quero forçar que todo objeto que possa ser armazenado em tais estrutuas precisam de um ID inteiro. Como fazer isso ? Bem, criei uma classe Node com o atributo ID e ao invés de aceitar qualquer subclasse de Object na estutura, serão aceitas apenas subclasses de Node, forçando a presença do atributo ID nas subclasses. Assim, Node é a "classe mãe" do projeto e serve também para exercício de uso de classes abstratas e limites em generics

    public abstract class Node<T> {
    private int ID;
    public Node(int id){this.ID=id;}
    public int getID(){return ID;}
    public void setID(int ID){this.ID = ID;}
}

Eis o exemplo de um nó válido para as estruturas:

    public class Product extends Node<Product> {
    String code;
    public Product(int ID, String code){
        super(ID);
        this.code=code;
    }
}

2. Gerenciando erros com exceções personalizadas

Defini uma hierarquia que faz sentido para tratar as exceções que podem ocorrer durante a execução de algum algoritmo. Sim, eu sei que não está completo principalmente pela ausência do NullPointerException nos códigos dos algoritmos, mas o objetivo é justamente incrementar o projeto caso o caminho esteja correto. Segue uma organização das exceções que defini inicialmente

classDiagram
Exception <|-- Myexception
Myexception <|-- InvalidIDException
Myexception <|-- AlreadyExistsException
Myexception <|-- OverFlowException
Myexception <|-- EmptyListException
EmptyListException <|-- UnderFlowException
EmptyListException <|-- NotFoundException                 
class NotFoundException{
+ int index
}

Decidi herdar MyException (que seria nossa classe de exceção de maior abstração) de Exception para forçar o tratamento das exceções que herdam de MyException. Não optei por RunTimeException pois acho válido forçar o programador a definir os comportamentos em cada caso. Por exemplo, poderia definir que em caso de overflow uma nova área de memória seria alocada e os dados copiados para lá ou apenas informar o erro para o usuário ao invés de "deixar este erro escondido" e ser surpreendido em tempo de execução. Entendo que UnderFlow e NotFound seriam subclasses de Emptylist, que é o caso mais genérico. Mais para frente ficará claro o motivo de NotFoundException possuir um atributo inteiro index.

Implementação

Não irei estender muito os detalhes das implementações porque são códigos simples e o projeto está disponível, mas acho interesante expôr meu raciocínio por trás para que este possa ser criticado aqui por vocês. Bem, para isto vou falar sobre as funções de busca e inserção em uma lista sequencial. Antes de avançarmos, sei que talvez surjam dúvidas como: como sua inserção é ordenada, por que não utilizou uma busca binária? Por que a inserção é ordenada? Não é melhor inserir diretamente após o último nó inserido para aproveitar o rápido acesso dado a lista em alocação sequencial? E para estas e as demais perguntas sobre escolha dos algoritmos, a resposta é: porque não está completo e o objetivo é justamente praticar/aprender. Este é só o pontapé inicial. Todas as escolhas de projeto que antecedem isto são, por hora, mais relevantes. Afinal, independente dos algoritmos, é válido lembrar que todos já existem e não há porquê ter pressa em implementá-los. Não é uma descoberta.

 public int busca(T node) throws EmptyListException, InvalidIDException {
        if(size==0){throw new EmptyListException("Empty list");}
        if(node.getID()<0){throw new InvalidIDException("Invalid ID. Should be positive number");}

        int index; // Se o objeto existir no array, retorna seu índice. Se não, retorna o índice (negativo) referente a posição onde seve ser inserido um novo objeto
        for(index = 0; nodes[index] != null && index < size-1; index++){
            if(nodes[index].equals(node)){ break; } // Encontrou!
        }

        if(nodes[index]==null) {
            index *= -1;
            throw new NotFoundException(index); // Não encontrou, mas retorna a posição que deve se inserir o novo objeto
        }

        return index;
    }

1. Validações iniciais para o caso da lista estar vazia ou o ID do nó a ser buscado ser negativo (inventei esta regra de negócio do ID positivo apenas para ilustrar um caso mais particular de exceção). Quem chamar a função de busca deverá tratá-las.
2. O laço for percorre o array buscando o nó. Caso encontre, encerra o loop e o retorna.
3. Caso não encontre o nó buscado, após verificado que há espaço no array, retorna um índice negativo da posição onde o próximo nó deve ser inserido (quando a função de inserção a chamar). O retorno é através da exceção NotFoundException. Neste ponto, fiquei inclinado a trocar isto por um atributo inteiro, na classe ArrayImp, que represente a posição atual do último elemento. Mas não vi diferença entre as duas, então segui este caminho mesmo.

public void insert(T node) throws InvalidIDException, AlreadyExistsException, OverFlowException {
        // Insere na ordem crescente pelo ID
        // ID inválido e OverFlow devem ser administrado por quem chama a função
        int index = 0;
        try {
            index = busca(node);
            if(index==size-1){throw new OverFlowException("Full");}
            if(index>=0){throw new AlreadyExistsException("node already exists");}
        }catch(NotFoundException nfe){
            index = nfe.getIndex()*(-1); // Se não encontrar, calcula o índice a inserir
        }catch(EmptyListException ignore){
            // Lista vazia --> insere no index = 0, ja inicializado
        }
        nodes[index] = node;
    }

1. A função rejeita inserção de nós com mesmo ID, lançando a exceção.

2. Em caso de OverFlow, assim como as outras exceções que são lançadas, fica a critério da função chamadora resolver.

3. Se a lista está vazia, basta ignorar a exceção neste caso visto que o index já foi inicializado com zero.

4. Finalmente, se a busca lançar a exceção de NotFoundException, então resgato o índice negativo e o torno positivo válido para a inserção.

Bem, por enquanto é isso e espero que acessem o projeto. Com sua ajuda, isto pode se tornar uma comunidade que estuda em conjunto sobre algoritmos, estrutura de dados, java e o que mais vier. Quem sabe não vira um projeto open source ou mesmo um grupo de estudos? Se você é iniciante, tem bastante espaço para aprender. Se é mais experiente, planejo trazer temas mais complexos como citados inicialmente no post (mas principalmente conto com sua ajuda nas críticas).

Agradeço seu tempo!