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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
local select , setmetatable = select , setmetatable
local function is_integer(x)
return x % 1 == 0
end
local fifo = {}
local fifo_mt = {
__index = fifo ;
__newindex = function ( f , k , v )
error("Tried to set table field in fifo")
end ;
}
local empty_default = function ( _ ) error ( "Fifo empty" ) end
function fifo.new ( ... )
return setmetatable({
empty = empty_default;
head = 1;
tail = select("#",...);
data = {...};
}, fifo_mt)
end
function fifo:length ( )
return self.tail - self.head + 1
end
fifo_mt.__len = fifo.length
-- Peek at the nth item
function fifo:peek ( n )
n = n or 1
assert(is_integer(n), "bad index to :peek()")
local index = self.head - 1 + n
if index > self.tail then
return nil, false
else
return self.data[index], true
end
end
function fifo:push ( v )
self.tail = self.tail + 1
self.data[self.tail] = v
end
function fifo:pop ( )
local head , tail = self.head , self.tail
if head > tail then return self:empty() end
local v = self.data[head]
self.data[head] = nil
self.head = head + 1
return v
end
function fifo:insert ( n , v )
local head , tail = self.head , self.tail
if n <= 0 or head + n > tail + 2 or not is_integer(n) then
error("bad index to :insert()")
end
local p = head + n - 1
if p <= (head + tail)/2 then
for i = head , p do
self.data[i- 1] = self.data[i]
end
self.data[p- 1] = v
self.head = head - 1
else
for i = tail , p , -1 do
self.data[i+ 1] = self.data[i]
end
self.data[p] = v
self.tail = tail + 1
end
end
function fifo:remove ( n )
local head , tail = self.head , self.tail
if n <= 0 or not is_integer(n) then
error("bad index to :remove()")
end
if head + n - 1 > tail then return self:empty() end
local p = head + n - 1
local v = self.data[p]
if p <= (head + tail)/2 then
for i = p , head , -1 do
self.data[i] = self.data[i-1]
end
self.head = head + 1
else
for i = p , tail do
self.data[i] = self.data[i+1]
end
self.tail = tail - 1
end
return v
end
function fifo:setempty ( func )
self.empty = func
return self
end
return fifo.new
|
