Trie (Lua)

trie.lua

-- Copyright (C) 2010 Danao.org. All Rights Reserved.
-- Jon Danao | [email protected] | http://danao.org

module(..., package.seeall)

function createTrie()
	
	-- PRIVATE
	local trie = {}

	function addNode(word, position, node, wordLength)						
		local char = string.sub(word, position, position)			
		local child = node[char]

		if child == nil then			
			child = {isWord = false}
			node[char] = child
		end

		if position < wordLength then
			addNode(word, position + 1, child, wordLength)
		elseif position == wordLength then
			child.isWord = true
		elseif position == wordLength + 1 then
			return
		end			
	end

	-- PUBLIC
	function trie:addWord(word)		
		local char = string.sub(word, 1, 1)
		local rootNode = trie[char]		
		
		if rootNode == nil then			
			rootNode = {isWord = false}	
			trie[char] = rootNode		
		end
		
		addNode(word, 2, rootNode, string.len(word))		
	end
	
	function trie:isWord(word)	
		local node = trie
		
		for i = 1, string.len(word) do
			local char = string.sub(word, i, i)			
			if node[char] == nil then 
				return false
			else	
				node = node[char]
			end
		end
		
		if node.isWord then 
			return true 
		else
			return false
		end	
	end
	
	function trie:isPrefix(prefix)
		local node = trie
		local isPrefix = false
		
		for i = 1, string.len(prefix) do
			local char = string.sub(prefix, i, i)
			node = node[char]
			
			if node ~= nil then 
				isPrefix = true 
			else
				isPrefix = false	
			end
		end
		
		return isPrefix
	end	

	-- RETURN
	return trie
end

There was a small bug in the code...

in line 21 you called addNode with the following parameters... addNode(word, position + 1, node, wordLength), instead of passing in "node", you should have passed in "child".

After this adjustment the code worked perfectly.

Fixed it. Thanks!

Kind of a newb to lua, but this is just what I am looking for.

How do you call it? It tried from main.lua:

            local trie = require("trie")
    local lexicon = trie:createTrie()
    lexicon:addword("and")

But I get an error - attempt to call method 'addword' (a nil value)

any help is appreciated
daf

forget it... typo.... addWord, not addword!