/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 05:13:09 UTC
  • Revision ID: josh@9ix.org-20131214051309-4gos06aw3r5amsyi
build system

Show diffs side-by-side

added added

removed removed

Lines of Context:
deque.lua
 
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
}