z_mirror/flib

git clone https://git.raiguard.me/z_mirror/flib

Caleb HeuerRemove require guardsa9f2be7

trunk
branchestrunkall refs →
2.8 KiB132 linesraw
1--- Lua queue implementation.
2---
3--- Based on "Queues and Double Queues" from [Programming in Lua](http://www.lua.org/pil/11.4.html).
4--- ```lua
5--- local flib_queue = require("__flib__.queue")
6--- ```
7--- @class flib_queue
8local flib_queue = {}
9
10---@class flib.Queue<T>: { [integer]: T, first: integer, last: integer }
11
12--- Create a new queue.
13--- @return flib.Queue
14function flib_queue.new()
15  return { first = 0, last = -1 }
16end
17
18--- Push an element into the front of the queue.
19--- @generic T
20--- @param self flib.Queue<T>
21--- @param value T
22function flib_queue.push_front(self, value)
23  local first = self.first - 1
24  self.first = first
25  self[first] = value
26end
27
28--- Push an element into the back of the queue.
29--- @generic T
30--- @param self flib.Queue<T>
31--- @param value `T`
32function flib_queue.push_back(self, value)
33  local last = self.last + 1
34  self.last = last
35  self[last] = value
36end
37
38--- Retrieve an element from the front of the queue.
39--- @generic T
40--- @param self flib.Queue<T>
41--- @return T?
42function flib_queue.pop_front(self)
43  local first = self.first
44  if first > self.last then
45    return
46  end
47  local value = self[first]
48  self[first] = nil
49  self.first = first + 1
50  return value
51end
52
53--- Retrieve an element from the back of the queue.
54--- @generic T
55--- @param self flib.Queue<T>
56--- @return T?
57function flib_queue.pop_back(self)
58  local last = self.last
59  if self.first > last then
60    return
61  end
62  local value = self[last]
63  self[last] = nil
64  self.last = last - 1
65  return value
66end
67
68--- Iterate over a queue's elements from the beginning to the end.
69---
70--- # Example
71---
72--- ```lua
73--- local my_queue = queue.new()
74--- for i = 1, 10 do
75---   queue.push_back(my_queue, 1)
76--- end
77---
78--- -- 1 2 3 4 5 6 7 8 9 10
79--- for num in queue.iter(my_queue) do
80---   log(i)
81--- end
82--- ```
83--- @generic T
84--- @param self flib.Queue<T>
85--- @return fun(self: flib.Queue<T>, index: integer): T
86function flib_queue.iter(self)
87  local i = self.first - 1
88  return function()
89    if i < self.last then
90      i = i + 1
91      return i, self[i]
92    end
93  end
94end
95
96--- Iterate over a queue's elements from the end to the beginning.
97---
98--- # Example
99---
100--- ```lua
101--- local my_queue = queue.new()
102--- for i = 1, 10 do
103---   queue.push_back(my_queue, 1)
104--- end
105---
106--- -- 10 9 8 7 6 5 4 3 2 1
107--- for num in queue.iter_rev(my_queue) do
108---   log(i)
109--- end
110--- ```
111--- @generic T
112--- @param self flib.Queue<T>
113--- @return fun(self: flib.Queue<T>, index: integer): T
114function flib_queue.iter_rev(self)
115  local i = self.last + 1
116  return function()
117    if i > self.first then
118      i = i - 1
119      return i, self[i]
120    end
121  end
122end
123
124--- Get the length of the queue.
125--- @generic T
126--- @param self flib.Queue<T>
127--- @return number
128function flib_queue.length(self)
129  return math.abs(self.last - self.first + 1)
130end
131
132return flib_queue