/ld28

To get this branch, use:
bzr branch http://9ix.org/bzr/ld28

« back to all changes in this revision

Viewing changes to deque.lua

  • Committer: Josh C
  • Date: 2013-12-14 02:57:47 UTC
  • Revision ID: josh@9ix.org-20131214025747-etw31g9vii33qvey
zoetrope 1.4

Show diffs side-by-side

added added

removed removed

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