1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
-- a simple first-in-first-out queue
-- very similar to the one in https://github.com/minetest/minetest/pull/7683
local fifo_queue = {}
local metatable = {__index = fifo_queue}
-- creates a new empty queue
function fifo_queue.new()
local q = {n_in = 0, n_out = 0, i_out = 1, buf_in = {}, buf_out = {}}
setmetatable(q, metatable)
return q
end
-- adds an element to the queue
function fifo_queue.add(self, v)
local n = self.n_in + 1
self.n_in = n
self.buf_in[n] = v
end
-- removes and returns the next element, or nil of empty
function fifo_queue.take(self)
local i_out = self.i_out
if i_out <= self.n_out then
local v = self.buf_out[i_out]
self.i_out = i_out + 1
self.buf_out[i_out] = true
return v
end
-- buf_out is empty, try to swap
self.i_out = 1
self.n_out = 0
if self.n_in == 0 then
return nil -- empty
end
-- swap
self.n_out = self.n_in
self.n_in = 0
self.buf_out, self.buf_in = self.buf_in, self.buf_out
local v = self.buf_out[1]
self.i_out = 2
self.buf_out[1] = true
return v
end
-- returns whether the queue is empty
function fifo_queue.is_empty(self)
return self.n_out == self.i_out + 1 and self.n_in == 0
end
-- returns stuff for iteration in a for loop, like pairs
-- adding new elements while iterating is no problem
function fifo_queue.iter(self)
return fifo_queue.take, self, nil
end
return fifo_queue
|
