bzr branch
http://9ix.org/bzr/ld28
|
2
by Josh C
basic delayed movement |
1 |
-- deque from https://github.com/catwell/cw-lua/tree/master/deque |
2 |
-- under MIT license |
|
3 |
||
4 |
local push_right = function(self, x) |
|
5 |
assert(x ~= nil) |
|
6 |
self.tail = self.tail + 1 |
|
7 |
self[self.tail] = x |
|
8 |
end |
|
9 |
||
10 |
local push_left = function(self, x) |
|
11 |
assert(x ~= nil) |
|
12 |
self[self.head] = x |
|
13 |
self.head = self.head - 1 |
|
14 |
end |
|
15 |
||
16 |
local peek_right = function(self) |
|
17 |
return self[self.tail] |
|
18 |
end |
|
19 |
||
20 |
local peek_left = function(self) |
|
21 |
return self[self.head+1] |
|
22 |
end |
|
23 |
||
24 |
local pop_right = function(self) |
|
25 |
if self:is_empty() then return nil end |
|
26 |
local r = self[self.tail] |
|
27 |
self[self.tail] = nil |
|
28 |
self.tail = self.tail - 1 |
|
29 |
return r |
|
30 |
end |
|
31 |
||
32 |
local pop_left = function(self) |
|
33 |
if self:is_empty() then return nil end |
|
34 |
local r = self[self.head+1] |
|
35 |
self.head = self.head + 1 |
|
36 |
local r = self[self.head] |
|
37 |
self[self.head] = nil |
|
38 |
return r |
|
39 |
end |
|
40 |
||
41 |
local rotate_right = function(self, n) |
|
42 |
n = n or 1 |
|
43 |
if self:is_empty() then return nil end |
|
44 |
for i=1,n do self:push_left(self:pop_right()) end |
|
45 |
end |
|
46 |
||
47 |
local rotate_left = function(self, n) |
|
48 |
n = n or 1 |
|
49 |
if self:is_empty() then return nil end |
|
50 |
for i=1,n do self:push_right(self:pop_left()) end |
|
51 |
end |
|
52 |
||
53 |
local _remove_at_internal = function(self, idx) |
|
54 |
for i=idx, self.tail do self[i] = self[i+1] end |
|
55 |
self.tail = self.tail - 1 |
|
56 |
end |
|
57 |
||
58 |
local remove_right = function(self, x) |
|
59 |
for i=self.tail,self.head+1,-1 do |
|
60 |
if self[i] == x then |
|
61 |
_remove_at_internal(self, i) |
|
62 |
return true |
|
63 |
end |
|
64 |
end |
|
65 |
return false |
|
66 |
end |
|
67 |
||
68 |
local remove_left = function(self, x) |
|
69 |
for i=self.head+1,self.tail do |
|
70 |
if self[i] == x then |
|
71 |
_remove_at_internal(self, i) |
|
72 |
return true |
|
73 |
end |
|
74 |
end |
|
75 |
return false |
|
76 |
end |
|
77 |
||
78 |
local length = function(self) |
|
79 |
return self.tail - self.head |
|
80 |
end |
|
81 |
||
82 |
local is_empty = function(self) |
|
83 |
return self:length() == 0 |
|
84 |
end |
|
85 |
||
86 |
local contents = function(self) |
|
87 |
local r = {}
|
|
88 |
for i=self.head+1,self.tail do |
|
89 |
r[i-self.head] = self[i] |
|
90 |
end |
|
91 |
return r |
|
92 |
end |
|
93 |
||
94 |
local iter_right = function(self) |
|
95 |
local i = self.tail+1 |
|
96 |
return function() |
|
97 |
if i > self.head+1 then |
|
98 |
i = i-1 |
|
99 |
return self[i] |
|
100 |
end |
|
101 |
end |
|
102 |
end |
|
103 |
||
104 |
local iter_left = function(self) |
|
105 |
local i = self.head |
|
106 |
return function() |
|
107 |
if i < self.tail then |
|
108 |
i = i+1 |
|
109 |
return self[i] |
|
110 |
end |
|
111 |
end |
|
112 |
end |
|
113 |
||
114 |
local methods = {
|
|
115 |
push_right = push_right, |
|
116 |
push_left = push_left, |
|
117 |
peek_right = peek_right, |
|
118 |
peek_left = peek_left, |
|
119 |
pop_right = pop_right, |
|
120 |
pop_left = pop_left, |
|
121 |
rotate_right = rotate_right, |
|
122 |
rotate_left = rotate_left, |
|
123 |
remove_right = remove_right, |
|
124 |
remove_left = remove_left, |
|
125 |
iter_right = iter_right, |
|
126 |
iter_left = iter_left, |
|
127 |
length = length, |
|
128 |
is_empty = is_empty, |
|
129 |
contents = contents, |
|
130 |
} |
|
131 |
||
132 |
local new = function() |
|
133 |
local r = {head=0,tail=0}
|
|
134 |
return setmetatable(r, {__index=methods})
|
|
135 |
end |
|
136 |
||
137 |
return {
|
|
138 |
new = new, |
|
139 |
} |