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
|
--------------------------------------------------------------------------------
--- Queue of objects sorted by priority.
-- @module lua-nucleo.priority_queue
-- This file is a part of lua-nucleo library. Note that if you wish to spread
-- the description after tags, then invoke with `not_luadoc=true`.
-- The flags here are `ldoc -X -f backtick priority_queue.lua`, which
-- also expands backticks.
-- @copyright lua-nucleo authors (see file `COPYRIGHT` for the license)
--------------------------------------------------------------------------------
local arguments,
method_arguments
= import 'lua-nucleo/args.lua'
{
'arguments',
'method_arguments'
}
local lower_bound_gt
= import 'lua-nucleo/algorithm.lua'
{
'lower_bound_gt'
}
--------------------------------------------------------------------------------
local table_insert, table_remove = table.insert, table.remove
--------------------------------------------------------------------------------
--- Priority Queue
-- @factory priority_queue
local make_priority_queue
do
local PRIORITY_KEY = 1
local VALUE_KEY = 2
local insert = function(self, priority, value)
method_arguments(
s
"number", priority
)
assert(value ~= nil, "value can't be nil") -- value may be of any type, except nil
local queue = self.queue_
local k = lower_bound_gt(queue, PRIORITY_KEY, priority)
table_insert(queue, k, { [PRIORITY_KEY] = priority, [VALUE_KEY] = value })
end
local front = function(self)
method_arguments(
self
)
local queue = self.queue_
local front_elem = queue[#queue]
if front_elem == nil then
return nil
end
return front_elem[PRIORITY_KEY], front_elem[VALUE_KEY]
end
--- pop last value.
-- @return priority
-- @return value
local pop = function(self)
method_arguments(
self
)
local front_elem = table_remove(self.queue_)
if front_elem == nil then
return nil
end
return front_elem[PRIORITY_KEY], front_elem[VALUE_KEY]
end
--- construct a `priority_queue`.
-- @constructor
make_priority_queue = function()
--- @export
return
{
insert = insert;
front = front;
pop = pop;
--
queue_ = { };
}
end
end
return
{
make_priority_queue = make_priority_queue;
}
|
