lunarmodules / Penlight / 474

Committed 01 Feb 2024 02:24PM UTC coverage: 89.675% (+0.8%) from 88.873%

Build # 474

Build Type

push

appveyor

Committed by

web-flow

Commit Message

docs: Fix typos (#462)

Run Details

7 of 7 new or added lines in 2 files covered. (100.0%)

140 existing lines in 18 files now uncovered.

5489 of 6121 relevant lines covered (89.67%)

345.29 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.53

/lua/pl/permute.lua

--- Permutation operations.
--
-- Dependencies: `pl.utils`, `pl.tablex`
-- @module pl.permute
local tablex = require 'pl.tablex'
local utils = require 'pl.utils'
local copy = tablex.deepcopy
local append = table.insert
local assert_arg = utils.assert_arg


local permute = {}


--- an iterator over all order-permutations of the elements of a list.
-- Please note that the same list is returned each time, so do not keep references!
-- @param a list-like table
-- @return an iterator which provides the next permutation as a list
function permute.order_iter(a)
    assert_arg(1,a,'table')

    local t = #a
    local stack = { 1 }
    local function iter()
        local h = #stack
        local n = t - h + 1

        local i = stack[h]
        if i > t then
            return
        end

        if n == 0 then
            table.remove(stack)
            h = h - 1

            stack[h] = stack[h] + 1
            return a

        elseif i <= n then

            -- put i-th element as the last one
            a[n], a[i] = a[i], a[n]

            -- generate all permutations of the other elements
            table.insert(stack, 1)

        else

            table.remove(stack)
            h = h - 1

            n = n + 1
            i = stack[h]

            -- restore i-th element
            a[n], a[i] = a[i], a[n]

            stack[h] = stack[h] + 1
        end
        return iter() -- tail-call
    end

    return iter
end


--- construct a table containing all the order-permutations of a list.
-- @param a list-like table
-- @return a table of tables
-- @usage permute.order_table {1,2,3} --> {{2,3,1},{3,2,1},{3,1,2},{1,3,2},{2,1,3},{1,2,3}}
function permute.order_table (a)
    assert_arg(1,a,'table')
    local res = {}
    for t in permute.iter(a) do
        append(res,copy(t))
    end
    return res
end



--- an iterator over all permutations of the elements of the given lists.
-- @param ... list-like tables, they are nil-safe if a length-field `n` is provided (see `utils.pack`)
-- @return an iterator which provides the next permutation as return values in the same order as the provided lists, preceded by an index
-- @usage
-- local strs = utils.pack("one", nil, "three")  -- adds an 'n' field for nil-safety
-- local bools = utils.pack(true, false)
-- local iter = permute.list_iter(strs, bools)
--
-- print(iter())    --> 1, one, true
-- print(iter())    --> 2, nil, true
-- print(iter())    --> 3, three, true
-- print(iter())    --> 4, one, false
-- print(iter())    --> 5, nil, false
-- print(iter())    --> 6, three, false
function permute.list_iter(...)
  local elements = {...}
  local pointers = {}
  local sizes = {}
  local size = #elements
  for i, list in ipairs(elements) do
    assert_arg(i,list,'table')
    pointers[i] = 1
    sizes[i] = list.n or #list
  end
  local count = 0

  return function()
    if pointers[size] > sizes[size] then return end -- we're done
    count = count + 1
    local r = { n = #elements }
    local cascade_up = true
    for i = 1, size do
      r[i] = elements[i][pointers[i]]
      if cascade_up then
        pointers[i] = pointers[i] + 1
        if pointers[i] <= sizes[i] then
          -- this list is not done yet, stop cascade
          cascade_up = false
        else
          -- this list is done
          if i ~= size then
            -- reset pointer
            pointers[i] = 1
          end
        end
      end
    end
    return count, utils.unpack(r)
  end
end



--- construct a table containing all the permutations of a set of lists.
-- @param ... list-like tables, they are nil-safe if a length-field `n` is provided
-- @return a list of lists, the sub-lists have an 'n' field for nil-safety
-- @usage
-- local strs = utils.pack("one", nil, "three")  -- adds an 'n' field for nil-safety
-- local bools = utils.pack(true, false)
-- local results = permute.list_table(strs, bools)
-- -- results = {
-- --   { "one, true, n = 2 }
-- --   { nil, true, n = 2 },
-- --   { "three, true, n = 2 },
-- --   { "one, false, n = 2 },
-- --   { nil, false, n = 2 },
-- --   { "three", false, n = 2 },
-- -- }
function permute.list_table(...)
  local iter = permute.list_iter(...)
  local results = {}
  local i = 1
  while true do
    local values = utils.pack(iter())
    if values[1] == nil then return results end
    for i = 1, values.n do values[i] = values[i+1] end
    values.n = values.n - 1
    results[i] = values
    i = i + 1
  end
end


-- backward compat, to be deprecated

--- deprecated.
-- @param ...
-- @see permute.order_iter
function permute.iter(...)
  utils.raise_deprecation {
    source = "Penlight " .. utils._VERSION,
    message = "function 'iter' was renamed to 'order_iter'",
    version_removed = "2.0.0",
    deprecated_after = "1.9.2",
  }

  return permute.order_iter(...)
end

--- deprecated.
-- @param ...
-- @see permute.order_iter
function permute.table(...)
  utils.raise_deprecation {
    source = "Penlight " .. utils._VERSION,
    message = "function 'table' was renamed to 'order_table'",
    version_removed = "2.0.0",
    deprecated_after = "1.9.2",
  }

  return permute.order_table(...)
end

return permute

1	--- Permutation operations.
2	--
3	-- Dependencies: `pl.utils`, `pl.tablex`
4	-- @module pl.permute
5	local tablex = require 'pl.tablex'	8✔
6	local utils = require 'pl.utils'	8✔
7	local copy = tablex.deepcopy	8✔
8	local append = table.insert	8✔
9	local assert_arg = utils.assert_arg	8✔
10
11
12	local permute = {}	8✔
13
14
15	--- an iterator over all order-permutations of the elements of a list.
16	-- Please note that the same list is returned each time, so do not keep references!
17	-- @param a list-like table
18	-- @return an iterator which provides the next permutation as a list
19	function permute.order_iter(a)	8✔
20	assert_arg(1,a,'table')	32✔
21
22	local t = #a	32✔
23	local stack = { 1 }	32✔
24	local function iter()
25	local h = #stack	512✔
26	local n = t - h + 1	512✔
27
28	local i = stack[h]	512✔
29	if i > t then	512✔
30	return	32✔
31	end
32
33	if n == 0 then	480✔
34	table.remove(stack)	96✔
35	h = h - 1	96✔
36
37	stack[h] = stack[h] + 1	96✔
38	return a	96✔
39
40	elseif i <= n then	384✔
41
42	-- put i-th element as the last one
43	a[n], a[i] = a[i], a[n]	240✔
44
45	-- generate all permutations of the other elements
46	table.insert(stack, 1)	240✔
47
48	else
49
50	table.remove(stack)	144✔
51	h = h - 1	144✔
52
53	n = n + 1	144✔
54	i = stack[h]	144✔
55
56	-- restore i-th element
57	a[n], a[i] = a[i], a[n]	144✔
58
59	stack[h] = stack[h] + 1	144✔
60	end
61	return iter() -- tail-call	384✔
62	end
63
64	return iter	32✔
65	end
66
67
68	--- construct a table containing all the order-permutations of a list.
69	-- @param a list-like table
70	-- @return a table of tables
71	-- @usage permute.order_table {1,2,3} --> {{2,3,1},{3,2,1},{3,1,2},{1,3,2},{2,1,3},{1,2,3}}
72	function permute.order_table (a)	8✔
73	assert_arg(1,a,'table')	16✔
74	local res = {}	16✔
75	for t in permute.iter(a) do	104✔
76	append(res,copy(t))	72✔
77	end
78	return res	16✔
79	end
80
81
82
83	--- an iterator over all permutations of the elements of the given lists.
84	-- @param ... list-like tables, they are nil-safe if a length-field `n` is provided (see `utils.pack`)
85	-- @return an iterator which provides the next permutation as return values in the same order as the provided lists, preceded by an index
86	-- @usage
87	-- local strs = utils.pack("one", nil, "three") -- adds an 'n' field for nil-safety
88	-- local bools = utils.pack(true, false)
89	-- local iter = permute.list_iter(strs, bools)
90	--
91	-- print(iter()) --> 1, one, true
92	-- print(iter()) --> 2, nil, true
93	-- print(iter()) --> 3, three, true
94	-- print(iter()) --> 4, one, false
95	-- print(iter()) --> 5, nil, false
96	-- print(iter()) --> 6, three, false
97	function permute.list_iter(...)	8✔
98	local elements = {...}	48✔
99	local pointers = {}	48✔
100	local sizes = {}	48✔
101	local size = #elements	48✔
102	for i, list in ipairs(elements) do	144✔
103	assert_arg(i,list,'table')	96✔
104	pointers[i] = 1	96✔
105	sizes[i] = list.n or #list	96✔
106	end
107	local count = 0	48✔
108
109	return function()
110	if pointers[size] > sizes[size] then return end -- we're done	480✔
111	count = count + 1	432✔
112	local r = { n = #elements }	432✔
113	local cascade_up = true	432✔
114	for i = 1, size do	1,584✔
115	r[i] = elements[i][pointers[i]]	1,152✔
116	if cascade_up then	1,152✔
117	pointers[i] = pointers[i] + 1	608✔
118	if pointers[i] <= sizes[i] then	608✔
119	-- this list is not done yet, stop cascade
120	cascade_up = false	400✔
121	else
122	-- this list is done
123	if i ~= size then	208✔
124	-- reset pointer
125	pointers[i] = 1	176✔
126	end
127	end
128	end
129	end
130	return count, utils.unpack(r)	648✔
131	end
132	end
133
134
135
136	--- construct a table containing all the permutations of a set of lists.
137	-- @param ... list-like tables, they are nil-safe if a length-field `n` is provided
138	-- @return a list of lists, the sub-lists have an 'n' field for nil-safety
139	-- @usage
140	-- local strs = utils.pack("one", nil, "three") -- adds an 'n' field for nil-safety
141	-- local bools = utils.pack(true, false)
142	-- local results = permute.list_table(strs, bools)
143	-- -- results = {
144	-- -- { "one, true, n = 2 }
145	-- -- { nil, true, n = 2 },
146	-- -- { "three, true, n = 2 },
147	-- -- { "one, false, n = 2 },
148	-- -- { nil, false, n = 2 },
149	-- -- { "three", false, n = 2 },
150	-- -- }
151	function permute.list_table(...)	8✔
152	local iter = permute.list_iter(...)	24✔
153	local results = {}	24✔
154	local i = 1	24✔
155	while true do
156	local values = utils.pack(iter())	360✔
157	if values[1] == nil then return results end	240✔
158	for i = 1, values.n do values[i] = values[i+1] end	873✔
159	values.n = values.n - 1	216✔
160	results[i] = values	216✔
161	i = i + 1	216✔
162	end
163	end
164
165
166	-- backward compat, to be deprecated
167
168	--- deprecated.
169	-- @param ...
170	-- @see permute.order_iter
171	function permute.iter(...)	8✔
172	utils.raise_deprecation {	32✔
173	source = "Penlight " .. utils._VERSION,	16✔
174	message = "function 'iter' was renamed to 'order_iter'",	8✔
175	version_removed = "2.0.0",	8✔
176	deprecated_after = "1.9.2",	8✔
177	}
178
179	return permute.order_iter(...)	16✔
180	end
181
182	--- deprecated.
183	-- @param ...
184	-- @see permute.order_iter
185	function permute.table(...)	8✔
UNCOV 186	utils.raise_deprecation {	×
187	source = "Penlight " .. utils._VERSION,
188	message = "function 'table' was renamed to 'order_table'",
189	version_removed = "2.0.0",
190	deprecated_after = "1.9.2",
191	}
192
UNCOV 193	return permute.order_table(...)	×
194	end
195
196	return permute	8✔

lunarmodules / Penlight / 474

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous