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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
-- deque from https://github.com/catwell/cw-lua/tree/master/deque
-- under MIT license
local push_right = function(self, x)
assert(x ~= nil)
self.tail = self.tail + 1
self[self.tail] = x
end
local push_left = function(self, x)
assert(x ~= nil)
self[self.head] = x
self.head = self.head - 1
end
local peek_right = function(self)
return self[self.tail]
end
local peek_left = function(self)
return self[self.head+1]
end
local pop_right = function(self)
if self:is_empty() then return nil end
local r = self[self.tail]
self[self.tail] = nil
self.tail = self.tail - 1
return r
end
local pop_left = function(self)
if self:is_empty() then return nil end
local r = self[self.head+1]
self.head = self.head + 1
local r = self[self.head]
self[self.head] = nil
return r
end
local rotate_right = function(self, n)
n = n or 1
if self:is_empty() then return nil end
for i=1,n do self:push_left(self:pop_right()) end
end
local rotate_left = function(self, n)
n = n or 1
if self:is_empty() then return nil end
for i=1,n do self:push_right(self:pop_left()) end
end
local _remove_at_internal = function(self, idx)
for i=idx, self.tail do self[i] = self[i+1] end
self.tail = self.tail - 1
end
local remove_right = function(self, x)
for i=self.tail,self.head+1,-1 do
if self[i] == x then
_remove_at_internal(self, i)
return true
end
end
return false
end
local remove_left = function(self, x)
for i=self.head+1,self.tail do
if self[i] == x then
_remove_at_internal(self, i)
return true
end
end
return false
end
local length = function(self)
return self.tail - self.head
end
local is_empty = function(self)
return self:length() == 0
end
local contents = function(self)
local r = {}
for i=self.head+1,self.tail do
r[i-self.head] = self[i]
end
return r
end
local iter_right = function(self)
local i = self.tail+1
return function()
if i > self.head+1 then
i = i-1
return self[i]
end
end
end
local iter_left = function(self)
local i = self.head
return function()
if i < self.tail then
i = i+1
return self[i]
end
end
end
local methods = {
push_right = push_right,
push_left = push_left,
peek_right = peek_right,
peek_left = peek_left,
pop_right = pop_right,
pop_left = pop_left,
rotate_right = rotate_right,
rotate_left = rotate_left,
remove_right = remove_right,
remove_left = remove_left,
iter_right = iter_right,
iter_left = iter_left,
length = length,
is_empty = is_empty,
contents = contents,
}
local new = function()
local r = {head=0,tail=0}
return setmetatable(r, {__index=methods})
end
return {
new = new,
}
|