Howdy, Stranger!

It looks like you're new here. Sign in or register to get started.

Simple queue implementation in lua

AilishAilish Member Posts: 177 ✭✭✭
When I started writing stuff in mudlet I realized that the utter lack of anything resembling proper data types in lua is problematic.  

I wrote this simple queue implemention to simplify keeping things in a queue.  I don't know if this will be useful to anyone, but I thought I'd share.

To create a new queue, do 
your_queue=SimpleQueue:create()

to add items to the queue, do your_queue:add("some value")
to peek (look at the top element on the queue), do value=your_queue:peek()
to pop (get the top element in the queue and remove it from the queue) do value=your_queue:pop()
to get the number of items in the queue, your_queue:count()

Please let me know if this is helpful to anyone, as I plan implementing other data types.



<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE MudletPackage>
<MudletPackage version="1.0">
    <ScriptPackage>
        <Script isActive="yes" isFolder="no">
            <name>Queue</name>
            <packageName></packageName>
            <script>


SimpleQueue={}
SimpleQueue.__index=SimpleQueue

function SimpleQueue:create()
  local queue={}
  setmetatable(queue, SimpleQueue)
  queue.__data__={}
  queue.__count__=0
  return queue
end

function SimpleQueue:add(value)
  table.insert(self.__data__,value)
  self.__count__=self.__count__+1
end

function SimpleQueue:peek()
if self.__count__ &gt; 0 then
return self.__data__[1]
else
return nil
end
end

function SimpleQueue:pop()
if self.__count__ &gt; 0 then 
local value=self.__data__[1]
table.remove(self.__data__,1)
self.__count__=self.__count__-1
return value
else
return nil
end
end

function SimpleQueue:count()
return self.__count__
end

</script>
            <eventHandlerList/>
        </Script>
    </ScriptPackage>
</MudletPackage>





Comments

  • AilishAilish Member Posts: 177 ✭✭✭
    Since at least one person found this useful, here's also an implementation of a binary search tree (I'm not totally sure what possible use a BST could have in imperian programming, but apparently my imagination isn't good enough)



    Node={}
    Node.__index=Node

    function Node:create()
      local node={}
      setmetatable(node, Node)
      node.key=nil
      node.data=nil
      node.parent=nil
      node.left=nil
      node.right=nil
      return node
    end

    BSTree={}
    BSTree.__index=BSTree

    function BSTree:create()
    local tree={}
    setmetatable(tree,BSTree)
       tree.root=nil
    return tree
    end

    function BSTree:add(key, value)
    n=Node:create()
    n.key=key
    n.data=value
    if self.root==nil then
    self.root=n
    else
    insertNode(self.root,n)
    end 
    return n
    end

    function BSTree:get(key)
    if self.root.key==key then
    return self.root.data
    else
    return findNode(self.root, key).data
    end
    end


    function BSTree:delete(key)
    local n = findNode(self.root,key)
    if n==nil then 
    return nil
    end
    if n.left == nil and n.right == nil then
    local p = n.parent
    if p.left == n then
    p.left = nil
    else 
    p.right = nil
    end
    elseif n.left == nil or n.right == nil then
    local c 
    if n.left == nil then
    c = n.right
    else 
    c = n.left
    end
    local p = n.parent
    c.parent=p
    if p.left == n then
    p.left = c
    else
    p.right=c
    end
    else
    local t_key=n.right.key
    local t_data=n.right.data
    self:delete(t_key)
    n.key=t_key
    n.data=t_data
    end
    end

    function insertNode(tree,n)
    if n.key < tree.key then
    if tree.left==nil then
    tree.left=n
    n.parent=tree
    else
    insertNode(tree.left,n)
    end
    else
    if tree.right==nil then
    tree.right=n
    n.parent=tree
    else
    insertNode(tree.right,n)
    end
    end
    end
    function findNode(tree, key)
    if key == tree.key then
    return tree
    elseif key < tree.key then
    if tree.left == nil then
    return nil
    elseif tree.left.key == key then
    return tree.left
    else
    return findNode(tree.left, key)
    end
    else
    if tree.right == nil then
    return nil
    elseif tree.right.key == key then 
    return tree.right
    else
    return findNode(tree.right, key)
    end
    end
    end

    function test_tree()
    ttest=BSTree:create()
    ttest:add(4,"four")
    ttest:add(2,"two")
    ttest:add(3,"three")
    ttest:add(8,"eight")
    ttest:add(9,"nine")
    ttest:add(6,"six")
    ttest:add(7,"seven")
    ttest:add(22,"twenty two")

    end
Sign In or Register to comment.