How to implement a queue using Lua

simwhi

Hi all,

Here's another example of a classic data structure using OOP:

Queue = Core.class()   function Queue:init(list)   if not list then self.q = {} self.first = 0 self.last = -1 else self.q = list self.first = 1 self.last = #list end end function Queue:push(item) self.last = self.last + 1 self.q[self.last] = item end function Queue:pop() --local first = self.first if self.first <= self.last then --local q = self.q local value = self.q[self.first] self.q[self.first] = nil self.first = self.first + 1 return value end end function Queue:iterator() return function() return self:pop() end end function Queue:length() return (self.last-self.first+1) end

Here is how to use it:

local q = Queue.new({"apples", "oranges", "bananas"})   q:push("strawberries") q:push("grapes")   print("The queue length: "..q:length()) print("Pop off the queue: "..q:pop())   for item in q:iterator() do   print("Pop of the queue: "..item)   end

n1cke

You cannot rely on overloaded length property (#, __len) in Gideros because it is based on Lua 5.1. That was fixed in Lua 5.2 and LuaJit. Here it always returns raw length. However Gideros Lua can be patched to get correct behaviour.

simwhi

@n1cke Thanks for the information.

How would one go about applying a patch? Is Gideros tied to Lua 5.1? Is there a reason why we can not more to Lua 5.x?

n1cke

The patch already exists for our Lua in the form of '.diff.' file. To apply it you need to modify Lua source code and rebuild it.
Yes, Gideros is tied to 5.1 because for 5.3 we will need to rewrite each plugin to be compatible with it and of course Lua should be rewritten too (Gideros needs patched Lua to work). It is hard work. However I have patched our Lua with many good things from Lua 5.3 (like utf8, int64, bitwise ops etc) so it only misses few features from newer versions e.g. this '__len' property.

n1cke

And I must say with 2016.08.2 bugfix release we will get updated macro system which makes Gideros Lua more powerful and modern language.

antix

@simwhi maybe just change the name of your function to size() or count() instead?

simwhi

@n1cke Thanks for the great info.

@antix I've removed the setmetatable call and changed the following function:

function Queue:length() return (self.last-self.first+1) end

totebo

This is great. We should put these helper classes, Pool, Stack, Query and any others, in one place for easy access.

keszegh

btw for such universal programming needs you can find examples easily when searching for lua, e.g. i also needed queues just a few days earlier and i've found this implementation:
http://www.lua.org/pil/11.4.html

simwhi

@keszegh I saw that one, too. I wanted my implementation to be more class based.

@totebo Thanks. I just wanted to share some knowledge and also learn more about Lua (especially the internal parts).

antix

Pools are totally one of the most important things you need in games!

SinisterSoft

Handy routines.

totebo

We're such nerds.