Software /
code /
prosody
Annotate
util/array.lua @ 13134:638f627e707f
util.datamanager: Add O(1) list indexing with on-disk index
Index file contains offsets and lengths of each item() which allows
seeking directly to each item and reading it without parsing the entire
file.
Also allows tricks like binary search, assuming items have some defined
order.
We take advantage of the 1-based indexing in tables to store a magic
header in the 0 position, so that table index 1 ends up at file index 1.
author | Kim Alvefur <zash@zash.se> |
---|---|
date | Tue, 11 May 2021 02:09:56 +0200 |
parent | 13032:ea4923bebca9 |
child | 13141:451cb119026e |
rev | line source |
---|---|
1522
569d58d21612
Add copyright header to those files missing one
Matthew Wild <mwild1@gmail.com>
parents:
1373
diff
changeset
|
1 -- Prosody IM |
2923
b7049746bd29
Update copyright headers for 2010
Matthew Wild <mwild1@gmail.com>
parents:
1934
diff
changeset
|
2 -- Copyright (C) 2008-2010 Matthew Wild |
b7049746bd29
Update copyright headers for 2010
Matthew Wild <mwild1@gmail.com>
parents:
1934
diff
changeset
|
3 -- Copyright (C) 2008-2010 Waqas Hussain |
5776
bd0ff8ae98a8
Remove all trailing whitespace
Florian Zeitz <florob@babelmonkeys.de>
parents:
5564
diff
changeset
|
4 -- |
1522
569d58d21612
Add copyright header to those files missing one
Matthew Wild <mwild1@gmail.com>
parents:
1373
diff
changeset
|
5 -- This project is MIT/X11 licensed. Please see the |
569d58d21612
Add copyright header to those files missing one
Matthew Wild <mwild1@gmail.com>
parents:
1373
diff
changeset
|
6 -- COPYING file in the source package for more information. |
569d58d21612
Add copyright header to those files missing one
Matthew Wild <mwild1@gmail.com>
parents:
1373
diff
changeset
|
7 -- |
569d58d21612
Add copyright header to those files missing one
Matthew Wild <mwild1@gmail.com>
parents:
1373
diff
changeset
|
8 |
3540
bc139431830b
Monster whitespace commit (beware the whitespace monster).
Waqas Hussain <waqas20@gmail.com>
parents:
2923
diff
changeset
|
9 local t_insert, t_sort, t_remove, t_concat |
bc139431830b
Monster whitespace commit (beware the whitespace monster).
Waqas Hussain <waqas20@gmail.com>
parents:
2923
diff
changeset
|
10 = table.insert, table.sort, table.remove, table.concat; |
12975
d10957394a3c
util: Prefix module imports with prosody namespace
Kim Alvefur <zash@zash.se>
parents:
12403
diff
changeset
|
11 local t_move = require "prosody.util.table".move; |
918 | 12 |
4449
ca74d8ed1a15
util.array: Avoid globals.
Waqas Hussain <waqas20@gmail.com>
parents:
4448
diff
changeset
|
13 local setmetatable = setmetatable; |
10592
9918b4b0cd58
util.array: Fix equality metamethod in Lua 5.3
Kim Alvefur <zash@zash.se>
parents:
9529
diff
changeset
|
14 local getmetatable = getmetatable; |
4449
ca74d8ed1a15
util.array: Avoid globals.
Waqas Hussain <waqas20@gmail.com>
parents:
4448
diff
changeset
|
15 local math_random = math.random; |
5857
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
16 local math_floor = math.floor; |
4449
ca74d8ed1a15
util.array: Avoid globals.
Waqas Hussain <waqas20@gmail.com>
parents:
4448
diff
changeset
|
17 local pairs, ipairs = pairs, ipairs; |
ca74d8ed1a15
util.array: Avoid globals.
Waqas Hussain <waqas20@gmail.com>
parents:
4448
diff
changeset
|
18 local tostring = tostring; |
6417 | 19 local type = type; |
4449
ca74d8ed1a15
util.array: Avoid globals.
Waqas Hussain <waqas20@gmail.com>
parents:
4448
diff
changeset
|
20 |
1905
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
21 local array = {}; |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
22 local array_base = {}; |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
23 local array_methods = {}; |
9528
1af7cc3b9747
util.array: Break long line
Matthew Wild <mwild1@gmail.com>
parents:
9487
diff
changeset
|
24 local array_mt = { |
1af7cc3b9747
util.array: Break long line
Matthew Wild <mwild1@gmail.com>
parents:
9487
diff
changeset
|
25 __index = array_methods; |
1af7cc3b9747
util.array: Break long line
Matthew Wild <mwild1@gmail.com>
parents:
9487
diff
changeset
|
26 __name = "array"; |
13032
ea4923bebca9
util.array: Change tostring format to [a,b,c]
Kim Alvefur <zash@zash.se>
parents:
12975
diff
changeset
|
27 __tostring = function (self) return "["..self:concat(", ").."]"; end; |
9528
1af7cc3b9747
util.array: Break long line
Matthew Wild <mwild1@gmail.com>
parents:
9487
diff
changeset
|
28 }; |
1905
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
29 |
9487
4e38121a349d
util.array: Add freeze metamethod
Kim Alvefur <zash@zash.se>
parents:
8521
diff
changeset
|
30 function array_mt:__freeze() return self; end |
4e38121a349d
util.array: Add freeze metamethod
Kim Alvefur <zash@zash.se>
parents:
8521
diff
changeset
|
31 |
5085
cbc7eb5cfa8c
util.array: Accept an iterator to the array constructor
Matthew Wild <mwild1@gmail.com>
parents:
4449
diff
changeset
|
32 local function new_array(self, t, _s, _var) |
cbc7eb5cfa8c
util.array: Accept an iterator to the array constructor
Matthew Wild <mwild1@gmail.com>
parents:
4449
diff
changeset
|
33 if type(t) == "function" then -- Assume iterator |
cbc7eb5cfa8c
util.array: Accept an iterator to the array constructor
Matthew Wild <mwild1@gmail.com>
parents:
4449
diff
changeset
|
34 t = self.collect(t, _s, _var); |
cbc7eb5cfa8c
util.array: Accept an iterator to the array constructor
Matthew Wild <mwild1@gmail.com>
parents:
4449
diff
changeset
|
35 end |
918 | 36 return setmetatable(t or {}, array_mt); |
37 end | |
38 | |
1373
120275376bbb
util.array: Add support for + operator to create a new array from two arrays joined
Matthew Wild <mwild1@gmail.com>
parents:
1372
diff
changeset
|
39 function array_mt.__add(a1, a2) |
120275376bbb
util.array: Add support for + operator to create a new array from two arrays joined
Matthew Wild <mwild1@gmail.com>
parents:
1372
diff
changeset
|
40 local res = new_array(); |
120275376bbb
util.array: Add support for + operator to create a new array from two arrays joined
Matthew Wild <mwild1@gmail.com>
parents:
1372
diff
changeset
|
41 return res:append(a1):append(a2); |
120275376bbb
util.array: Add support for + operator to create a new array from two arrays joined
Matthew Wild <mwild1@gmail.com>
parents:
1372
diff
changeset
|
42 end |
120275376bbb
util.array: Add support for + operator to create a new array from two arrays joined
Matthew Wild <mwild1@gmail.com>
parents:
1372
diff
changeset
|
43 |
7976
2a7ef5fcaa77
util.array: Add O(n) equality check metamethod
Kim Alvefur <zash@zash.se>
parents:
7700
diff
changeset
|
44 function array_mt.__eq(a, b) |
10592
9918b4b0cd58
util.array: Fix equality metamethod in Lua 5.3
Kim Alvefur <zash@zash.se>
parents:
9529
diff
changeset
|
45 if getmetatable(a) ~= array_mt or getmetatable(b) ~= array_mt then |
9918b4b0cd58
util.array: Fix equality metamethod in Lua 5.3
Kim Alvefur <zash@zash.se>
parents:
9529
diff
changeset
|
46 -- Lua 5.3+ calls this if both operands are tables, even if metatables differ |
9918b4b0cd58
util.array: Fix equality metamethod in Lua 5.3
Kim Alvefur <zash@zash.se>
parents:
9529
diff
changeset
|
47 return false; |
9918b4b0cd58
util.array: Fix equality metamethod in Lua 5.3
Kim Alvefur <zash@zash.se>
parents:
9529
diff
changeset
|
48 end |
7976
2a7ef5fcaa77
util.array: Add O(n) equality check metamethod
Kim Alvefur <zash@zash.se>
parents:
7700
diff
changeset
|
49 if #a == #b then |
2a7ef5fcaa77
util.array: Add O(n) equality check metamethod
Kim Alvefur <zash@zash.se>
parents:
7700
diff
changeset
|
50 for i = 1, #a do |
2a7ef5fcaa77
util.array: Add O(n) equality check metamethod
Kim Alvefur <zash@zash.se>
parents:
7700
diff
changeset
|
51 if a[i] ~= b[i] then |
2a7ef5fcaa77
util.array: Add O(n) equality check metamethod
Kim Alvefur <zash@zash.se>
parents:
7700
diff
changeset
|
52 return false; |
2a7ef5fcaa77
util.array: Add O(n) equality check metamethod
Kim Alvefur <zash@zash.se>
parents:
7700
diff
changeset
|
53 end |
2a7ef5fcaa77
util.array: Add O(n) equality check metamethod
Kim Alvefur <zash@zash.se>
parents:
7700
diff
changeset
|
54 end |
2a7ef5fcaa77
util.array: Add O(n) equality check metamethod
Kim Alvefur <zash@zash.se>
parents:
7700
diff
changeset
|
55 else |
2a7ef5fcaa77
util.array: Add O(n) equality check metamethod
Kim Alvefur <zash@zash.se>
parents:
7700
diff
changeset
|
56 return false; |
2a7ef5fcaa77
util.array: Add O(n) equality check metamethod
Kim Alvefur <zash@zash.se>
parents:
7700
diff
changeset
|
57 end |
2a7ef5fcaa77
util.array: Add O(n) equality check metamethod
Kim Alvefur <zash@zash.se>
parents:
7700
diff
changeset
|
58 return true; |
2a7ef5fcaa77
util.array: Add O(n) equality check metamethod
Kim Alvefur <zash@zash.se>
parents:
7700
diff
changeset
|
59 end |
2a7ef5fcaa77
util.array: Add O(n) equality check metamethod
Kim Alvefur <zash@zash.se>
parents:
7700
diff
changeset
|
60 |
9529
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
61 function array_mt.__div(a1, func) |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
62 local a2 = new_array(); |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
63 local o = 0; |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
64 for i = 1, #a1 do |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
65 local new_value = func(a1[i]); |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
66 if new_value ~= nil then |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
67 o = o + 1; |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
68 a2[o] = new_value; |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
69 end |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
70 end |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
71 return a2; |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
72 end |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
73 |
920
e302cbc9d036
util.array: Expose array.* functions, to be used for unwrapped arrays
Matthew Wild <mwild1@gmail.com>
parents:
918
diff
changeset
|
74 setmetatable(array, { __call = new_array }); |
e302cbc9d036
util.array: Expose array.* functions, to be used for unwrapped arrays
Matthew Wild <mwild1@gmail.com>
parents:
918
diff
changeset
|
75 |
4440
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
76 -- Read-only methods |
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
77 function array_methods:random() |
7019
abcd5ec3ee41
util.array: Fix minory style issues
Kim Alvefur <zash@zash.se>
parents:
6777
diff
changeset
|
78 return self[math_random(1, #self)]; |
4440
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
79 end |
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
80 |
9529
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
81 -- Return a random value excluding the one at idx |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
82 function array_methods:random_other(idx) |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
83 local max = #self; |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
84 return self[((math.random(1, max-1)+(idx-1))%max)+1]; |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
85 end |
6a1e7723208b
util.array: Add __div for parity with util.set
Matthew Wild <mwild1@gmail.com>
parents:
9528
diff
changeset
|
86 |
4440
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
87 -- These methods can be called two ways: |
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
88 -- array.method(existing_array, [params [, ...]]) -- Create new array for result |
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
89 -- existing_array:method([params, ...]) -- Transform existing array into result |
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
90 -- |
1905
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
91 function array_base.map(outa, ina, func) |
7019
abcd5ec3ee41
util.array: Fix minory style issues
Kim Alvefur <zash@zash.se>
parents:
6777
diff
changeset
|
92 for k, v in ipairs(ina) do |
1905
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
93 outa[k] = func(v); |
918 | 94 end |
1905
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
95 return outa; |
918 | 96 end |
97 | |
1905
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
98 function array_base.filter(outa, ina, func) |
1915
e9d5406caf8c
util.array: Fix for array:filter() (in-place filtering)
Matthew Wild <mwild1@gmail.com>
parents:
1905
diff
changeset
|
99 local inplace, start_length = ina == outa, #ina; |
e9d5406caf8c
util.array: Fix for array:filter() (in-place filtering)
Matthew Wild <mwild1@gmail.com>
parents:
1905
diff
changeset
|
100 local write = 1; |
7019
abcd5ec3ee41
util.array: Fix minory style issues
Kim Alvefur <zash@zash.se>
parents:
6777
diff
changeset
|
101 for read = 1, start_length do |
1915
e9d5406caf8c
util.array: Fix for array:filter() (in-place filtering)
Matthew Wild <mwild1@gmail.com>
parents:
1905
diff
changeset
|
102 local v = ina[read]; |
918 | 103 if func(v) then |
1915
e9d5406caf8c
util.array: Fix for array:filter() (in-place filtering)
Matthew Wild <mwild1@gmail.com>
parents:
1905
diff
changeset
|
104 outa[write] = v; |
e9d5406caf8c
util.array: Fix for array:filter() (in-place filtering)
Matthew Wild <mwild1@gmail.com>
parents:
1905
diff
changeset
|
105 write = write + 1; |
918 | 106 end |
107 end | |
5776
bd0ff8ae98a8
Remove all trailing whitespace
Florian Zeitz <florob@babelmonkeys.de>
parents:
5564
diff
changeset
|
108 |
1922
d5fe0f9b377a
util.array: Small logic fix for array:filter()
Matthew Wild <mwild1@gmail.com>
parents:
1915
diff
changeset
|
109 if inplace and write <= start_length then |
7019
abcd5ec3ee41
util.array: Fix minory style issues
Kim Alvefur <zash@zash.se>
parents:
6777
diff
changeset
|
110 for i = write, start_length do |
1915
e9d5406caf8c
util.array: Fix for array:filter() (in-place filtering)
Matthew Wild <mwild1@gmail.com>
parents:
1905
diff
changeset
|
111 outa[i] = nil; |
e9d5406caf8c
util.array: Fix for array:filter() (in-place filtering)
Matthew Wild <mwild1@gmail.com>
parents:
1905
diff
changeset
|
112 end |
e9d5406caf8c
util.array: Fix for array:filter() (in-place filtering)
Matthew Wild <mwild1@gmail.com>
parents:
1905
diff
changeset
|
113 end |
5776
bd0ff8ae98a8
Remove all trailing whitespace
Florian Zeitz <florob@babelmonkeys.de>
parents:
5564
diff
changeset
|
114 |
1905
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
115 return outa; |
918 | 116 end |
117 | |
11787
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
118 function array_base.slice(outa, ina, i, j) |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
119 if j == nil then |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
120 j = -1; |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
121 end |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
122 if j < 0 then |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
123 j = #ina + (j+1); |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
124 end |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
125 if i < 0 then |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
126 i = #ina + (i+1); |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
127 end |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
128 if i < 1 then |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
129 i = 1; |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
130 end |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
131 if j > #ina then |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
132 j = #ina; |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
133 end |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
134 if i > j then |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
135 for idx = 1, #outa do |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
136 outa[idx] = nil; |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
137 end |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
138 return outa; |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
139 end |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
140 |
12403
42b2713ab818
util.array: Take advantage of table.move()
Matthew Wild <mwild1@gmail.com>
parents:
11787
diff
changeset
|
141 |
42b2713ab818
util.array: Take advantage of table.move()
Matthew Wild <mwild1@gmail.com>
parents:
11787
diff
changeset
|
142 t_move(ina, i, j, 1, outa); |
11787
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
143 if ina == outa then |
12403
42b2713ab818
util.array: Take advantage of table.move()
Matthew Wild <mwild1@gmail.com>
parents:
11787
diff
changeset
|
144 -- Clear (nil) remainder of range |
42b2713ab818
util.array: Take advantage of table.move()
Matthew Wild <mwild1@gmail.com>
parents:
11787
diff
changeset
|
145 t_move(ina, #outa+1, #outa*2, 2+j-i, ina); |
11787
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
146 end |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
147 return outa; |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
148 end |
3ae6fa901a8b
util.array: Add :slice() method + tests
Matthew Wild <mwild1@gmail.com>
parents:
10895
diff
changeset
|
149 |
1905
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
150 function array_base.sort(outa, ina, ...) |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
151 if ina ~= outa then |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
152 outa:append(ina); |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
153 end |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
154 t_sort(outa, ...); |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
155 return outa; |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
156 end |
918 | 157 |
8017
ec7cab8e744d
util.array: Add method for filtering out duplicate values
Kim Alvefur <zash@zash.se>
parents:
7976
diff
changeset
|
158 function array_base.unique(outa, ina) |
ec7cab8e744d
util.array: Add method for filtering out duplicate values
Kim Alvefur <zash@zash.se>
parents:
7976
diff
changeset
|
159 local seen = {}; |
ec7cab8e744d
util.array: Add method for filtering out duplicate values
Kim Alvefur <zash@zash.se>
parents:
7976
diff
changeset
|
160 return array_base.filter(outa, ina, function (item) |
ec7cab8e744d
util.array: Add method for filtering out duplicate values
Kim Alvefur <zash@zash.se>
parents:
7976
diff
changeset
|
161 if seen[item] then |
ec7cab8e744d
util.array: Add method for filtering out duplicate values
Kim Alvefur <zash@zash.se>
parents:
7976
diff
changeset
|
162 return false; |
ec7cab8e744d
util.array: Add method for filtering out duplicate values
Kim Alvefur <zash@zash.se>
parents:
7976
diff
changeset
|
163 else |
ec7cab8e744d
util.array: Add method for filtering out duplicate values
Kim Alvefur <zash@zash.se>
parents:
7976
diff
changeset
|
164 seen[item] = true; |
ec7cab8e744d
util.array: Add method for filtering out duplicate values
Kim Alvefur <zash@zash.se>
parents:
7976
diff
changeset
|
165 return true; |
ec7cab8e744d
util.array: Add method for filtering out duplicate values
Kim Alvefur <zash@zash.se>
parents:
7976
diff
changeset
|
166 end |
ec7cab8e744d
util.array: Add method for filtering out duplicate values
Kim Alvefur <zash@zash.se>
parents:
7976
diff
changeset
|
167 end); |
ec7cab8e744d
util.array: Add method for filtering out duplicate values
Kim Alvefur <zash@zash.se>
parents:
7976
diff
changeset
|
168 end |
ec7cab8e744d
util.array: Add method for filtering out duplicate values
Kim Alvefur <zash@zash.se>
parents:
7976
diff
changeset
|
169 |
10895
5777968301e8
util.array: pluck: Support default value to avoid holes
Matthew Wild <mwild1@gmail.com>
parents:
10592
diff
changeset
|
170 function array_base.pluck(outa, ina, key, default) |
7019
abcd5ec3ee41
util.array: Fix minory style issues
Kim Alvefur <zash@zash.se>
parents:
6777
diff
changeset
|
171 for i = 1, #ina do |
10895
5777968301e8
util.array: pluck: Support default value to avoid holes
Matthew Wild <mwild1@gmail.com>
parents:
10592
diff
changeset
|
172 local v = ina[i][key]; |
5777968301e8
util.array: pluck: Support default value to avoid holes
Matthew Wild <mwild1@gmail.com>
parents:
10592
diff
changeset
|
173 if v == nil then |
5777968301e8
util.array: pluck: Support default value to avoid holes
Matthew Wild <mwild1@gmail.com>
parents:
10592
diff
changeset
|
174 v = default; |
5777968301e8
util.array: pluck: Support default value to avoid holes
Matthew Wild <mwild1@gmail.com>
parents:
10592
diff
changeset
|
175 end |
5777968301e8
util.array: pluck: Support default value to avoid holes
Matthew Wild <mwild1@gmail.com>
parents:
10592
diff
changeset
|
176 outa[i] = v; |
4439
1c8d2c0d02db
util.array: Add pluck() method to pick a given property from each item
Matthew Wild <mwild1@gmail.com>
parents:
4387
diff
changeset
|
177 end |
1c8d2c0d02db
util.array: Add pluck() method to pick a given property from each item
Matthew Wild <mwild1@gmail.com>
parents:
4387
diff
changeset
|
178 return outa; |
1c8d2c0d02db
util.array: Add pluck() method to pick a given property from each item
Matthew Wild <mwild1@gmail.com>
parents:
4387
diff
changeset
|
179 end |
1c8d2c0d02db
util.array: Add pluck() method to pick a given property from each item
Matthew Wild <mwild1@gmail.com>
parents:
4387
diff
changeset
|
180 |
5857
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
181 function array_base.reverse(outa, ina) |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
182 local len = #ina; |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
183 if ina == outa then |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
184 local middle = math_floor(len/2); |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
185 len = len + 1; |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
186 local o; -- opposite |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
187 for i = 1, middle do |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
188 o = len - i; |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
189 outa[i], outa[o] = outa[o], outa[i]; |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
190 end |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
191 else |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
192 local off = len + 1; |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
193 for i = 1, len do |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
194 outa[i] = ina[off - i]; |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
195 end |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
196 end |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
197 return outa; |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
198 end |
8613888d0f9e
util.array: Improve array:reverse() and make it work as both method and non-mutating function
Kim Alvefur <zash@zash.se>
parents:
5776
diff
changeset
|
199 |
4440
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
200 --- These methods only mutate the array |
7700
0d70410efdcf
util.array: Remove unused arguments [luacheck]
Kim Alvefur <zash@zash.se>
parents:
7699
diff
changeset
|
201 function array_methods:shuffle() |
918 | 202 local len = #self; |
7019
abcd5ec3ee41
util.array: Fix minory style issues
Kim Alvefur <zash@zash.se>
parents:
6777
diff
changeset
|
203 for i = 1, #self do |
abcd5ec3ee41
util.array: Fix minory style issues
Kim Alvefur <zash@zash.se>
parents:
6777
diff
changeset
|
204 local r = math_random(i, len); |
918 | 205 self[i], self[r] = self[r], self[i]; |
206 end | |
1372
3b13bb57002e
util.array: Make array:reverse() and array:shuffle() return the array to allow chaining
Matthew Wild <mwild1@gmail.com>
parents:
1371
diff
changeset
|
207 return self; |
918 | 208 end |
209 | |
7699
9c40d0be2295
util.array: Rename arguments to avoid name clash [luacheck]
Kim Alvefur <zash@zash.se>
parents:
7020
diff
changeset
|
210 function array_methods:append(ina) |
12403
42b2713ab818
util.array: Take advantage of table.move()
Matthew Wild <mwild1@gmail.com>
parents:
11787
diff
changeset
|
211 t_move(ina, 1, #ina, #self+1, self); |
1371
9e45bdf55353
util.array: Add array:append() method, to append a new array to an existing one
Matthew Wild <mwild1@gmail.com>
parents:
1027
diff
changeset
|
212 return self; |
9e45bdf55353
util.array: Add array:append() method, to append a new array to an existing one
Matthew Wild <mwild1@gmail.com>
parents:
1027
diff
changeset
|
213 end |
9e45bdf55353
util.array: Add array:append() method, to append a new array to an existing one
Matthew Wild <mwild1@gmail.com>
parents:
1027
diff
changeset
|
214 |
4440
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
215 function array_methods:push(x) |
4449
ca74d8ed1a15
util.array: Avoid globals.
Waqas Hussain <waqas20@gmail.com>
parents:
4448
diff
changeset
|
216 t_insert(self, x); |
4448
d745f4c28294
util.array: Make array:push() chainable.
Waqas Hussain <waqas20@gmail.com>
parents:
4440
diff
changeset
|
217 return self; |
4440
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
218 end |
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
219 |
7020
6ab9c691c4c6
util.array: Just use table.remove as array:pop()
Kim Alvefur <zash@zash.se>
parents:
7019
diff
changeset
|
220 array_methods.pop = t_remove; |
4440
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
221 |
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
222 function array_methods:concat(sep) |
4449
ca74d8ed1a15
util.array: Avoid globals.
Waqas Hussain <waqas20@gmail.com>
parents:
4448
diff
changeset
|
223 return t_concat(array.map(self, tostring), sep); |
4440
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
224 end |
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
225 |
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
226 function array_methods:length() |
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
227 return #self; |
c60ed6732b34
util.array: Expand some of the more basic methods to act more sensibly than their names suggested
Matthew Wild <mwild1@gmail.com>
parents:
4439
diff
changeset
|
228 end |
1905
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
229 |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
230 --- These methods always create a new array |
1027
fe2e3d3dba6a
util.array: Add array.collect() to collect results from iterators into an array, and use module() to correctly set the module name
Matthew Wild <mwild1@gmail.com>
parents:
922
diff
changeset
|
231 function array.collect(f, s, var) |
4387
06161b0b83f2
util.array: Fix array.collect() for iterators that expect initial value of var to be preserved
Matthew Wild <mwild1@gmail.com>
parents:
3540
diff
changeset
|
232 local t = {}; |
1027
fe2e3d3dba6a
util.array: Add array.collect() to collect results from iterators into an array, and use module() to correctly set the module name
Matthew Wild <mwild1@gmail.com>
parents:
922
diff
changeset
|
233 while true do |
fe2e3d3dba6a
util.array: Add array.collect() to collect results from iterators into an array, and use module() to correctly set the module name
Matthew Wild <mwild1@gmail.com>
parents:
922
diff
changeset
|
234 var = f(s, var); |
7019
abcd5ec3ee41
util.array: Fix minory style issues
Kim Alvefur <zash@zash.se>
parents:
6777
diff
changeset
|
235 if var == nil then break; end |
4449
ca74d8ed1a15
util.array: Avoid globals.
Waqas Hussain <waqas20@gmail.com>
parents:
4448
diff
changeset
|
236 t_insert(t, var); |
1027
fe2e3d3dba6a
util.array: Add array.collect() to collect results from iterators into an array, and use module() to correctly set the module name
Matthew Wild <mwild1@gmail.com>
parents:
922
diff
changeset
|
237 end |
fe2e3d3dba6a
util.array: Add array.collect() to collect results from iterators into an array, and use module() to correctly set the module name
Matthew Wild <mwild1@gmail.com>
parents:
922
diff
changeset
|
238 return setmetatable(t, array_mt); |
fe2e3d3dba6a
util.array: Add array.collect() to collect results from iterators into an array, and use module() to correctly set the module name
Matthew Wild <mwild1@gmail.com>
parents:
922
diff
changeset
|
239 end |
fe2e3d3dba6a
util.array: Add array.collect() to collect results from iterators into an array, and use module() to correctly set the module name
Matthew Wild <mwild1@gmail.com>
parents:
922
diff
changeset
|
240 |
1905
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
241 --- |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
242 |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
243 -- Setup methods from array_base |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
244 for method, f in pairs(array_base) do |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
245 local base_method = f; |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
246 -- Setup global array method which makes new array |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
247 array[method] = function (old_a, ...) |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
248 local a = new_array(); |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
249 return base_method(a, old_a, ...); |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
250 end |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
251 -- Setup per-array (mutating) method |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
252 array_methods[method] = function (self, ...) |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
253 return base_method(self, self, ...); |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
254 end |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
255 end |
e3e0a17e0b33
util.array: Per-array methods now always mutate the array, array.* return a mutated copy, and most methods (e.g. sort) now return the array
Matthew Wild <mwild1@gmail.com>
parents:
1522
diff
changeset
|
256 |
1027
fe2e3d3dba6a
util.array: Add array.collect() to collect results from iterators into an array, and use module() to correctly set the module name
Matthew Wild <mwild1@gmail.com>
parents:
922
diff
changeset
|
257 return array; |