Standard Library for Lua

Biblioteca para Linguagem Lua que implementa estruturas de dados mais utilizadas e algoritmos principais.

Lua: https://www.lua.org/

Library to Lua Programming Language that aims to provide most used data structures and algorithms.

---

Motivacao

Criar um repositorio independente e aberto com diversas estruturas de dados implementadas em Lua. A ideia do projeto consiste em expandir o repertorio da biblioteca atraves de contribuicoes externas.

Os contribuidores do repositorio podem ser consultados no arquivo CONTRIBUTORS.

---

Contribuicao

Qualquer um pode contribuir, basta abrir uma issue, realizar um fork e fazer um pull request. Ler CONTRUBUTING.md para todos os detalhes desse processo.

---

Utilizacao

A utilização das estruturas é bem simples. Basta baixar o arquivo ".lua" da estrutura desejada e juntar ao projeto. Após isso, importar e instanciar a classe da estrutura utilizando esse arquivo:

local classe_estrutura = require("estrutura_desejado.lua");
local objeto = classe_estrutura:new()

---

Documentacao - Estrutura de Dados

Arvore binaria

Informacoes

Estrutura basica de arvore binaria de busca. Permite inserir, remover e imprimir elementos em ordem.

Metodos

• Arvore:new(args)
  • Descricao: Metodo construtor que instancia o objeto Arvore.
  • Argumentos: (Table) Atributos desejados para a Arvore.
  • Retorno: (Object) Arvore instanciada.
• Arvore:insert(elem)
  • Descricao: Metodo insert que adiciona um elemento na arvore binaria.
  • Argumentos: (Object) Elemento desejado para incluir na arvore.
• Arvore:remove(elem)
  • Descricao: Metodo remove que exclui um elemento da arvore binaria.
  • Argumentos: (Object) Elemento desejado para remover da arvore.
• Arvore:print()
  • Descricao: Metodo que imprime os elementos da arvore em ordem.

Exemplo

local Arvore = require("arvore_binaria");
local arvore = Arvore:new();

arvore:insert(10);
arvore:insert(5);
arvore:insert(15);

arvore:remove(5);
arvore:print();

---

AVL

Informacoes

Estrutura balanceada de arvore binaria de busca. Mantem a altura controlada apos insercoes e remocoes internas.

Metodos

• Arvore:new(args)
  • Descricao: Metodo construtor que instancia o objeto Arvore AVL.
  • Argumentos: (Table) Atributos desejados para a Arvore AVL.
  • Retorno: (Object) Arvore AVL instanciada.
• Arvore:add(new_value)
  • Descricao: Metodo add que insere um novo valor na arvore AVL.
  • Argumentos: (Object) Valor desejado para incluir na arvore.
• Arvore:print()
  • Descricao: Metodo que imprime os elementos e alturas da arvore AVL em ordem.

Exemplo

local AVL = require("avl");
local arvore = AVL:new();

arvore:add(3);
arvore:add(2);
arvore:add(1);

arvore:print();

---

Fila de Prioridade (Heap)

Informacoes

Estrutura basica de fila de prioridade. A ordenacao dos elementos e controlada por uma funcao de comparacao informada na criacao.

Metodos

• Fila_Prioridade:new(args, func)
  • Descricao: Metodo construtor que instancia o objeto Fila_Prioridade.
  • Argumentos: (Table) Atributos desejados para a Fila_Prioridade.
  • (Function) Funcao de comparacao entre os elementos.
  • Retorno: (Object) Fila_Prioridade instanciada.
• Fila_Prioridade:push(objeto)
  • Descricao: Metodo push que insere um objeto na fila de prioridade.
  • Argumentos: (Object) Objeto desejado para incluir na fila.
• Fila_Prioridade:pop()
  • Descricao: Metodo pop que remove o objeto com maior prioridade.
  • Retorno: (Object) Objeto removido da fila.
• Fila_Prioridade:print()
  • Descricao: Funcao que printa toda a fila.
• Fila_Prioridade:free()
  • Descricao: Metodo para liberar a fila de prioridade.

Exemplo

local Fila_Prioridade = require("fila_prioridade");
local fila = Fila_Prioridade:new({}, function(a, b)
  return a < b;
end);

fila:push(3);
fila:push(1);
fila:push(2);

print(fila:pop()); --> 1

---

Fila

Informacoes

Estrutura basica de fila. Estrutura que segue a logica FIFO(first in, first out).

Metodos

• Fila:new(args)
  • Descricao: Metodo construtor que instancia o objeto Fila.
  • Argumentos: (Table) Atributos desejados para a Fila.
  • Retorno: (Object) Fila instanciada.
• Fila:push(args)
  • Descricao: Metodo push que insere um objeto na Fila.
  • Argumentos: (Object) Objeto desejados para incluir na Fila.
• Fila:pop()
  • Descricao: Metodo pop que remove um objeto da Fila.
  • Retorno: (Object) Objeto removida da Fila.
• Fila:free()
  • Descricao: Metodo para liberar a Fila.

Implementacao pronta para operacoes basicas de insercao, remocao, leitura e liberacao da estrutura.

Exemplo

local Fila = require("fila");
local nova_fila = Fila:new();

nova_fila:push("Primeiro_Elemento");
nova_fila:push("Segundo_Elemento");

local elemento_extraido = nova_fila:pop();
print(elemento_extraido);

nova_fila:free();
nova_fila = nil;

---

Grafo

Informacoes

Estrutura basica de grafo orientado com pesos nas arestas. Cada no armazena valor e lista de adjacencia.

Metodos

• Grafo:new(args)
  • Descricao: Metodo construtor que instancia o objeto Grafo.
  • Argumentos: (Table) Atributos desejados para o Grafo.
  • Retorno: (Object) Grafo instanciado.
• Grafo:addNo(index, valor)
  • Descricao: Metodo que adiciona um novo no no grafo.
  • Argumentos: (Object) Identificador do no.
  • (Object) Valor armazenado no no.
• Grafo:removeNo(index)
  • Descricao: Metodo que remove um no do grafo.
  • Argumentos: (Object) Identificador do no.
• Grafo:addEdge(src, dest, peso)
  • Descricao: Metodo que adiciona uma aresta entre dois nos.
  • Argumentos: (Object) No de origem.
  • (Object) No de destino.
  • (Number) Peso da aresta.
• Grafo:removeEdge(src, dest)
  • Descricao: Metodo que remove uma aresta entre dois nos.
  • Argumentos: (Object) No de origem.
  • (Object) No de destino.
• Grafo:printAdjacent(index)
  • Descricao: Metodo que imprime a lista de adjacencia de um no.
  • Argumentos: (Object) Identificador do no.
• Grafo:print()
  • Descricao: Metodo que imprime todos os nos e suas adjacencias.
• Grafo:getValor(index)
  • Descricao: Metodo que retorna o valor armazenado em um no.
  • Argumentos: (Object) Identificador do no.
  • Retorno: (Object) Valor armazenado no no.

Exemplo

local Grafo = require("grafo");
local grafo = Grafo:new();

grafo:addNo(1, "A");
grafo:addNo(2, "B");
grafo:addEdge(1, 2, 5);

grafo:print();

---

Hash

Informacoes

Tabela hash simples para armazenamento de numeros inteiros, com insercao, remocao, busca interna e limpeza da estrutura.

Metodos

• TabelaHash:new(args)
  • Descricao: Metodo construtor que instancia o objeto TabelaHash.
  • Argumentos: (Table) Atributos desejados para a TabelaHash.
  • Retorno: (Object) TabelaHash instanciada.
• TabelaHash:insert(key)
  • Descricao: Metodo insert que adiciona uma chave na tabela hash.
  • Argumentos: (Number) Chave desejada para incluir.
• TabelaHash:remove(key)
  • Descricao: Metodo remove que exclui uma chave da tabela hash.
  • Argumentos: (Number) Chave desejada para remover.
• TabelaHash:clear()
  • Descricao: Funcao que remove todos os elementos da tabela hash.
• TabelaHash:print()
  • Descricao: Funcao que printa os elementos armazenados e suas posicoes.
• TabelaHash:free()
  • Descricao: Metodo para liberar a tabela hash.

Exemplo

local TabelaHash = require("hash");
local hash = TabelaHash:new({m = 10});

hash:insert(10);
hash:insert(20);
hash:print();

---

Lista

Informacoes

Estrutura basica de Lista. Seguem métodos tradicionais.

Métodos

• Lua:new(atributos)
  • Descricao: Metodo cosntrutor que instancia o objeto Lista..
  • Argumentos: (Table) Atributos desejados para a Lista.
  • Retorno: (Object) Lista instanciada.
• Lista:append(objeto)
  • Descricao: Metodo append que insere um objeto no fim da Lista.
  • Argumentos: (Object) Objeto desejados para incluir na Lista.
• Lista:insert(objeto, i)
  • Descricao: Metodo append que insere um objeto em uma posição específica da Lista.
  • Argumentos: (Object) Objeto desejados para incluir na Lista.
  • (Int) Índice da posição para inserir na lista.
• Lista:pop(i)
  • Descricao: Metodo pop que remove um objeto específico da Lista.
  • Argumentos: (Int) Índice da posição para remover da lista.
  • Retorno: (Object) Objeto removida da Lista.
• Lista:print()
  • Descricao: Funcao que printa toda a lista
• Lista:count()
  • Descricao: Funcao que retorna a quantidade de elementos na lista.
  • Retorno: (Int) Quantidade de elementos da lista.
• Lista:extend(lista_base)
  • Descricao: Funcao que extende uma lista em outra. Concatena no fim. Ou seja, adiciona a lista_base no fim da lista.
  • Argumentos: (Lista) Lista a ser adicionada.
• Lista:clear()
  • Descricao: Funcao que remove todos os elementos de uma Lista.
• Lista:index(elemento)
  • Descricao: Funcao que retorna o índice do primeiro elemento com o valor especificado.
  • Argumentos: (Object) elemento a ser identificado na lista.
  • Retorno: (Int) Índice correspondente. Quando não há um elemento, retorna -1;
• Lista:remove(elemento)
  • Descricao: Funcao que remove o primeiro elemento com o valor especificado.
  • Retorno: (Object) elemento a ser identificado na lista.
• Lista:copy()
  • Descricao: Funcao que retorna a cópia de uma lista.
  • Argumentos: (Object) elemento a ser identificado na lista.
• Lista:reverse()
  • Descricao: Funcao que reverte a ordem dos elementos de uma lista.
• Lista:sort()
  • Descricao: Funcao que ordena uma Lista.
• Lista:free()
  • Descricao: Metodo para liberar a Lista.

Exemplo

local Lista = require("lista");
local aux = Lista:new();

aux:append("test");
aux:append(17);
aux:append(true);
aux:append("fim");

--Para printar a lista:
aux:print();

aux:free();
aux = nil;

---

Matriz

Informacoes

Estrutura basica de matriz com acesso por linha, coluna e posicao, alem de suporte a troca de elementos.

Metodos

• Matriz:new(args, rows, cols)
  • Descricao: Metodo construtor que instancia o objeto Matriz.
  • Argumentos: (Table) Atributos desejados para a Matriz.
  • (Int) Quantidade de linhas.
  • (Int) Quantidade de colunas.
  • Retorno: (Object) Matriz instanciada.
• Matriz:getLine(line)
  • Descricao: Metodo que retorna uma linha da matriz.
  • Argumentos: (Int) Linha desejada.
  • Retorno: (Table) Linha requisitada.
• Matriz:getCol(col)
  • Descricao: Metodo que retorna uma coluna da matriz.
  • Argumentos: (Int) Coluna desejada.
  • Retorno: (Table) Coluna requisitada.
• Matriz:swap(first_row, first_col, second_row, second_col)
  • Descricao: Metodo que troca dois elementos da matriz.
  • Argumentos: (Int) Linha do primeiro elemento.
  • (Int) Coluna do primeiro elemento.
  • (Int) Linha do segundo elemento.
  • (Int) Coluna do segundo elemento.
• Matriz:getPos(row, col)
  • Descricao: Metodo que retorna o elemento de uma posicao da matriz.
  • Argumentos: (Int) Linha desejada.
  • (Int) Coluna desejada.
  • Retorno: (Object) Elemento da posicao.
• Matriz:setPos(item, row, col)
  • Descricao: Metodo que atribui um elemento em uma posicao da matriz.
  • Argumentos: (Object) Item desejado.
  • (Int) Linha desejada.
  • (Int) Coluna desejada.
• Matriz:free()
  • Descricao: Metodo para liberar a Matriz.

Exemplo

local Matriz = require("matriz");
local matriz = Matriz:new({}, 2, 2);

matriz:setPos(10, 1, 1);
matriz:setPos(20, 1, 2);

print(matriz:getPos(1, 2)); --> 20

---

Pilha

Informacoes

Estrutura básica de Pilha. Estrutura de dados que segue a logica LIFO(last in, first out).

Metodos

• Pilha:new(args)
  • Descricao: Metodo construtor que instancia o objeto Pilha.
  • Argumentos: (Table) Atributos desejados para a Pilha.
  • Retorno: (Object) Pilha instanciada.
• Pilha:push(args)
  • Descricao: Metodo push que insere um objeto na Pilha.
  • Argumentos: (Object) Objeto desejados para incluir na Pilha.
• Pilha:pop()
  • Descricao: Metodo pop que remove um objeto da Pilha.
  • Retorno: (Object) Objeto removido da Pilha.
• Pilha:free()
  • Descricao: Metodo para liberar a Pilha.

Exemplo

local Pilha = require("pilha");
local nova_pilha = Pilha:new();

nova_pilha:push("Primeiro_Elemento");
nova_pilha:push("Segundo_Elemento");

local elemento_extraido = nova_pilha:pop();
print(elemento_extraido);

nova_pilha:free();
nova_pilha = nil;

---

Vetor

Informacoes

Estrutura basica de Vetor. Segue metodos tradicionais.

Metodos

• Vetor:new(args)
  • Descricao: Metodo construtor que instancia o objeto Vetor.
  • Argumentos: (Table) Atributos desejados para o Vetor.
  • Retorno: (Object) Vetor instanciado.
• Vetor:insert(objeto)
  • Descricao: Metodo insert que insere um objeto no Vetor.
  • Argumentos: (Object) Objeto desejados para incluir no Vetor.
• Vetor:at(index)
  • Descricao: Metodo at que acessa um objeto do Vetor.
  • Argumentos: (Int) Indice qual se deseja acessar
  • Retorno: (Object) Objeto acessado do Vetor.
• Vetor:tam()
  • Descricao: Metodo que retorna o tamanho do Vetor.
  • Retorno: (Int)Tamanho do Vetor.
• Vetor:front()
  • Descricao: Metodo front que acessa o primeiro objeto do Vetor.
  • Retorno: (Object) Objeto da primeira posicao do Vetor.
• Vetor:back()
  • Descricao: Metodo back que acessao ultimo objeto do Vetor.
  • Retorno: (Object) Objeto da ultima posicao do Vetor.
• Vetor:begin()
  • Descricao: Metodo begin que seta o iterador para o primeira posicao do Vetor.
• Vetor:finale()
  • Descricao: Metodo finale que seta o iterador para a ultima posicao do Vetor.
• Vetor:setIt(index)
  • Metodo setIt que seta o iterador para uma posicao arbitraria do Vetor.
  • Argumentos: (Int) Indice qual se deseja setar o iterador.
• Vetor:after()
  • Descricao: Metodo after que busca o proximo elemento do vetor baseando-se no iterador.
  • Retorno: (Object) Objeto da posicao iterada.
• Vetor:before()
  • Descricao: Metodo before que busca o elemento anterior do vetor baseando-se no iterador.
  • Retorno: (Object) Objeto da posicao iterada.
• Vetor:swap(vetor_base)
  • Descricao: Metodo swap que troca todo conteudo do Vetor pelo conteudo de outro Vetor.
  • Argumentos: (Vetor) Vetor base para o swap
  • Retorno: (Int) Numero de posicoes copiadas
• Vetor:free()
  • Descricao: Metodo para liberar o Vetor.

Implementacao pronta para acesso por indice, iteracao simples e troca de conteudo da estrutura.

Exemplo

local Vetor = require("vetor");
local aux = Vetor:new();

aux:insert("test");
aux:insert(17);
aux:insert(true);
aux:insert("fim");

print("Item na posicao 1 do vetor: " .. aux:at(1)); --> Item na posicao 1 do vetor: test
print("Inicio do vetor: " .. aux:front()); --> Inicio do vetor: test
print("Final do vetor: " .. aux:back()) --> Final do vetor: fim

--Para printar a lista:
aux:begin()
for i=1, aux:tam() do
  print(aux:after()) -->test 17 true fim
end

aux:swap({1, "trocado", 124, false});

--Para printar a lista:
aux:finale()
for i=1, aux:tam() do
  print(aux:before()) -->false 124 trocado 1
end

aux:free();
aux = nil;

---

---

Documentacao - Algoritmos

Busca Binaria

Informacoes

Algoritmo de busca em vetor ordenado. Retorna a posicao do valor buscado ou -1 quando o valor nao existe.

Metodos

• busca_binaria(array, valor)
  • Descricao: Funcao que realiza busca binaria em um vetor ordenado.
  • Argumentos: (Table) Vetor ordenado para consulta.
  • (Object) Valor desejado.
  • Retorno: (Int) Posicao encontrada ou -1.

Exemplo

local busca_binaria = require("binarysearch");
local pos = busca_binaria({1, 3, 5, 7}, 5);
print(pos); --> 3

---

Bubble Sort

Informacoes

Algoritmo de ordenacao simples baseado em trocas sucessivas entre elementos adjacentes.

Metodos

• bubbleSort(arr)
  • Descricao: Funcao que ordena um vetor em ordem crescente.
  • Argumentos: (Table) Vetor desejado para ordenacao.
  • Retorno: (Table) Vetor ordenado.

Exemplo

local bubbleSort = require("bubblesort");
local resultado = bubbleSort({5, 4, 3, 2, 1});
print(resultado[1]); --> 1

---

Dijkstra

Informacoes

Algoritmo para caminho minimo em grafos ponderados sem pesos negativos. Aceita a estrutura Grafo do repositorio ou uma matriz de adjacencia.

Metodos

• dijkstra(grafo, de, para)
  • Descricao: Funcao que calcula a menor distancia entre dois vertices.
  • Argumentos: (Object) Grafo ou matriz de adjacencia.
  • (Object) Vertice de origem.
  • (Object) Vertice de destino.
  • Retorno: (Number) Distancia encontrada.
  • (Table) Tabela de predecessores do caminho.

Exemplo

local Dijkstra = require("dijkstra");
local Grafo = require("grafo");
local grafo = Grafo:new();

grafo:addNo(1, "A");
grafo:addNo(2, "B");
grafo:addNo(3, "C");
grafo:addEdge(1, 2, 1);
grafo:addEdge(2, 3, 2);
grafo:addEdge(1, 3, 4);

local distancia = Dijkstra.dijkstra(grafo, 1, 3);
print(distancia); --> 3

---

Insertion Sort

Informacoes

Algoritmo de ordenacao por insercao que organiza os elementos no proprio vetor.

Metodos

• insertionsort(tabela)
  • Descricao: Funcao que ordena um vetor em ordem crescente.
  • Argumentos: (Table) Vetor desejado para ordenacao.
  • Retorno: (Table) Vetor ordenado.

Exemplo

local insertionsort = require("insertionsort");
local resultado = insertionsort({4, 2, 3, 1});
print(resultado[1]); --> 1

---

Merge Sort

Informacoes

Algoritmo de ordenacao por intercalação que divide o vetor em partes menores e depois recombina os resultados.

Metodos

• mergeSort(vetor)
  • Descricao: Funcao que ordena um vetor por intercalação.
  • Argumentos: (Table) Vetor desejado para ordenacao.
  • Retorno: (Table) Vetor ordenado.

Exemplo

local MergeSort = require("mergesort");
local resultado = MergeSort.mergeSort({4, 1, 3, 2});
print(resultado[1]); --> 1

---

Quick Sort

Informacoes

Algoritmo de ordenacao que escolhe um pivo e particiona o vetor em elementos menores e maiores.

Metodos

• quicksort(tabela)
  • Descricao: Funcao que ordena um vetor em ordem crescente.
  • Argumentos: (Table) Vetor desejado para ordenacao.
  • Retorno: (Table) Novo vetor ordenado.

Exemplo

local quicksort = require("quicksort");
local resultado = quicksort({4, 2, 3, 1});
print(resultado[1]); --> 1

---

Tarjan

Informacoes

Algoritmo para identificacao de componentes fortemente conexas em grafos orientados. Aceita a estrutura Grafo do repositorio ou uma lista de adjacencia.

Metodos

• tarjan(grafo)
  • Descricao: Funcao que calcula as componentes fortemente conexas de um grafo.
  • Argumentos: (Object) Grafo ou lista de adjacencia do grafo.
  • Retorno: (Table) Lista de componentes encontradas.

Exemplo

local Tarjan = require("tarjan");
local Grafo = require("grafo");
local grafo = Grafo:new();

grafo:addNo(1, "A");
grafo:addNo(2, "B");
grafo:addNo(3, "C");
grafo:addEdge(1, 2, 1);
grafo:addEdge(2, 1, 1);
grafo:addEdge(2, 3, 1);

local componentes = Tarjan.tarjan(grafo);

print(#componentes);

Este projeto está em desenvolvimento...