lua-algorithms

This library was developed with the purpose of making general algorithms and data structures available in Java language also available in Lua.

Features

The library covers commonly used data structures (ArrayList, Stack, Queue, Priority Queue, Balanced Search Tree, HashMap, Set, Tries) and algorithms (various sorting and search algorithms, shuffling, union find, etc)

For developers on Windows platform, a Vagrantfile is provided in the source code to allow them to run luarocks under window environment.

Install

luarocks install lualgorithms

Usage

Common Data Structures

Stack

localstack=require'lualgorithms.data.stack'locals=stack.create()
s:push(1)
s:push(2)
s:push(3)
print(s:size())
print(s:isEmpty())
print(s:pop())
forindex,valinpairs(s:enumerate()) doprint(index, val)
end

ArrayList

The list behaves the same as the Java ArrayList API, and is zero-based indexing.

locallist=require'lualgorithms.data.list'locals=list.create()
s:add(1) -- s becomes [1]s:add(2) -- s becomes [1, 2]s:add(3) -- s becomes [1, 2, 3]s:set(2, 4) -- s becomes [1, 2, 4]forindex,valinpairs(s:enumerate()) doprint(index, val)
endfori=0,s:size()-1doprint(s:get(i))
endprint(s:size())
print(s:isEmpty())
s:removeAt(0) -- s becomes [2, 4]s:remove(2) -- s becomes [4]s:removeAt(0) -- s is now empty

Queue

localqueue=require('lualgorithms.data.queue')
locals=queue.create()
s:enqueue(10)
s:enqueue(20)
s:enqueue(30)
print(s:size()) -- return 3print(s:isEmpty()) -- return falseforkey,valueinpairs(s:enumerate()) doprint(key, value)
endprint(s:dequeue()) -- return 10print(s:dequeue()) -- return 20print(s:dequeue()) -- return 30

MinPQ

localminpq=require('lualgorithms.data.minpq')
localcomparer=function(a1, a2) returna1-a2end-- method that return negative value if if a1 < a2; 0 if a1 == a2; positive otherwiselocals=minpq.create(comparer)
s:enqueue(10)
s:enqueue(100)
s:enqueue(20)
s:enqueue(50)
print(s:size()) -- return 4print(s:isEmpty()) -- return falseprint(s:delMin()) -- return 10print(s:delMin()) -- return 20print(s:delMin()) -- return 50print(s:delMin()) -- return 100print(s:isEmpty()) -- return true

MaxPQ

localmaxpq=require('lualgorithms.data.maxpq')
localcomparer=function(a1, a2) returna1-a2end-- method that return negative value if if a1 < a2; 0 if a1 == a2; positive otherwiselocals=maxpq.create(comparer)
s:enqueue(10)
s:enqueue(100)
s:enqueue(20)
s:enqueue(50)
print(s:size()) -- return 4print(s:isEmpty()) -- return falseprint(s:delMax()) -- return 100print(s:delMax()) -- return 50print(s:delMax()) -- return 20print(s:delMax()) -- return 10print(s:isEmpty()) -- return true

HashSet

localhashset=require('lualgorithms.data.hashset')
localhash_func=function(x) returnx%1000endlocals=hashset.create(hash_func)
s:add(100, 2)
s:add(200, 4)
s:add(450, 2)
print(s:contains(99)) -- return falseprint(s:contains(100)) -- return trueprint(s:size()) -- return 3print(s:isEmpty()) -- return falses:remove(100)
print(s:contains(100)) -- return false)

HashMap

localhashmap=require('lualgorithms.data.hashmap')
localhash_func=function(x) returnx%1000endlocals=hashmap.create(hash_func)
s:put(100, 2)
s:put(200, 4)
s:put(450, 2)
print(s:get(100)) -- return 2print(s:get(200)) -- return 4print(s:get(450)) -- return 2print(s:get(99)) -- return nilprint(s:containsKey(99)) -- return falseprint(s:containsKey(100)) -- return trueprint(s:size()) -- return 3print(s:isEmpty()) -- return falseprint(s:remove(100)) -- return 2print(s:containsKey(100)) -- return falseprint(s:size()) -- return 2s:remove(200)
s:remove(450)
print(s:isEmpty()) -- return true

SortedMap (Left-Leaning Red Black Tree)

localmap=require('lualgorithms.data.redblacktree')
localcomparator=function(a1, a2) returna1-a2endlocals=map.create(comparator)
s:put(100, 2)
s:put(200, 4)
s:put(450, 2)
print(s:minKey()) -- return 100print(s:maxKey()) -- return 450print(s:get(100)) -- return 2print(s:get(200)) -- return 4print(s:get(450)) -- return 2print(s:get(99)) -- return nilprint(s:containsKey(99)) -- return falseprint(s:containsKey(100)) -- return trueprint(s:size()) -- return 3print(s:isEmpty()) -- return falseprint(s:remove(100)) -- return 2print(s:containsKey(100)) -- return falseprint(s:size()) -- return 2s:remove(200)
s:remove(450)
print(s:isEmpty()) -- return true

Tries (R-way Tries)

localrwaytries=require('lualgorithms.tries.rwaytries')
locals=rwaytries.create()
s:put("Hello", "World")
s:put("Hi", "Morning")
s:put("How", "are you?")
print(s:isEmpty()) -- return falseprint(s:size()) -- return 3print(s:get("Hello")) -- return "World"print(s:get("Hi")) -- return "Morning"print(s:get("How")) -- return "are you?"print(s:containsKey("Hello")) -- return trueprint(s:containsKey("hello")) -- return falses:remove("Hello")
print(s:containsKey("Hello")) -- return falseprint(s:size()) -- return 2localkeys=s:keys()
fori=0, keys:size()-1doprint(keys:get(i))
ends:put('there', 'is')
s:put('the', 'ninja')
s:put('those', 'turtles')
s:put('these', 'ducks')
s:put('turles', 'ducks')
keys=s:keysWithPrefix('th')
fori=0, keys:size()-1doprint(keys:get(i))
end

Sorting

As in Java, the sorting is performed on ArrayList by default (which is lualgorithms.data.list).

Note that the default is to sort ascendingly, which can be reversed via the comparator function pass in as the second parameter.

Sorting (Selection Sort)

locallist=require("lualgorithms.data.list")
locala=list.create()
a:add(100)
a:add(200)
a:add(300)
a:add(600)
a:add(200)
a:add(400)
a:add(340)
a:add(120)
a:add(10)
localselection=require("lualgorithms.sorting.selection")
selection.sort(a, function(a1, a2) returna1-a2end)
fori=0,(a:size()-1) doprint(a:get(i))
end

Sorting (Insertion Sort)

locallist=require("lualgorithms.data.list")
locala=list.create()
a:add(100)
a:add(200)
a:add(300)
a:add(600)
a:add(200)
a:add(400)
a:add(340)
a:add(120)
a:add(10)
localinsertion=require("lualgorithms.sorting.insertion")
insertion.sort(a, function(a1, a2) returna1-a2end)
fori=0,(a:size()-1) doprint(a:get(i))
end

Sorting (Shell Sort)

locallist=require("lualgorithms.data.list")
locala=list.create()
a:add(100)
a:add(200)
a:add(300)
a:add(600)
a:add(200)
a:add(400)
a:add(340)
a:add(120)
a:add(10)
localshellsort=require("lualgorithms.sorting.shellsort")
shellsort.sort(a, function(a1, a2) returna1-a2end)
fori=0,(a:size()-1) doprint(a:get(i))
end

Sorting (Merge Sort)

locallist=require("lualgorithms.data.list")
locala=list.create()
a:add(100)
a:add(200)
a:add(300)
a:add(600)
a:add(200)
a:add(400)
a:add(340)
a:add(120)
a:add(10)
localmergesort=require("lualgorithms.sorting.mergesort")
mergesort.sort(a, function(a1, a2) returna1-a2end)
fori=0,(a:size()-1) doprint(a:get(i))
end

Sorting (Quick Sort)

locallist=require("lualgorithms.data.list")
locala=list.create()
a:add(100)
a:add(200)
a:add(300)
a:add(600)
a:add(200)
a:add(400)
a:add(340)
a:add(120)
a:add(10)
localquicksort=require("lualgorithms.sorting.quicksort")
quicksort.sort(a, function(a1, a2) returna1-a2end)
fori=0,(a:size()-1) doprint(a:get(i))
end

Sorting (3-ways Quick Sort)

locallist=require("lualgorithms.data.list")
locala=list.create()
a:add(100)
a:add(200)
a:add(300)
a:add(600)
a:add(200)
a:add(400)
a:add(340)
a:add(120)
a:add(10)
localquicksort3ways=require("lualgorithms.sorting.quicksort3ways")
quicksort3ways.sort(a, function(a1, a2) returna1-a2end)
fori=0,(a:size()-1) doprint(a:get(i))
end

Sorting (Heap Sort)

locallist=require("lualgorithms.data.list")
locala=list.create()
a:add(100)
a:add(200)
a:add(300)
a:add(600)
a:add(200)
a:add(400)
a:add(340)
a:add(120)
a:add(10)
localheapsort=require("lualgorithms.sorting.heapsort")
heapsort.sort(a, function(a1, a2) returna1-a2end)
fori=0,(a:size()-1) doprint(a:get(i))
end

Shuffling

locallist=require('lualgorithms.data.list')
locals=list.create()
fori=1,10dos:add(i)
endlocalshuffling=require('lualgorithms.shuffling')
shuffling.shuffle(s)
fori=0,(s:size()-1) doprint(s:get(i))
end

Binary Search on Sorted ArrayList

localcomparator=function(a1, a2) returna1-a2endlocals=create_a_list_that_sorts_ascendingly(comparator)
ifs.isSortedAscedningly() thenlocalbinarysearch=require('lualgorithms.binarysearch')
print(binarysearch.indexOf(s, 10, comparator)) -- return the index of value 10 in the array list selseprint('error! list must be sorted before performing binary search') end

Union Find

localunionfind=require('lualgorithms.unionfind').create()
unionfind:union(1, 2)
unionfind:union(4, 6)
unionfind:union(7, 4)
print(unionfind:connected(6, 7)) -- return trueprint(unionfind:connected(4, 7)) -- return trueprint(unionfind:connected(6, 4)) -- return trueprint(unionfind:connected(6, 1)) -- return falseprint(unionfind:connected(7, 2)) -- return false