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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
-- RST
-- set.lua
-- -------------
--
-- This adds a new data type Set.
--
-- To make this class available include this file at the beginning
-- of a script via:
--
-- .. code-block:: lua
--
-- include "scripting/set.lua"
--
-- RST
--
-- .. class:: Set(iteratable)
--
-- A set is a collection of items. Each item must compare uniquely
-- in the set, otherwise it is discarded; that is a Set never contains
-- the same item more than once.
--
-- It works with all types that are either unique (strings) or provide a
-- __hash property. :class:`wl.map.Field` and :class:`wl.map.MapObject`
-- implement such a property
-- RST
-- .. attribute:: size
--
-- (RO) Due to a bug in Lua 5.1, one cannot use the '#' operator to get
-- the number of items in a set. Use this property instead.
--
Set = {}
function Set:new(l)
local set = {
size = 0,
}
setmetatable(set, self)
self.__index = self
if l then
for _, v in ipairs(l) do
set:add(v)
end
end
return set
end
-- RST
-- .. method:: add(item)
--
-- Add this item to the set
function Set:add(item)
local hash = item.__hash or item
if not self[hash] then
self.size = self.size + 1
self[hash] = item
end
end
-- RST
-- .. method:: discard(item)
--
-- Remove this item from the set. Does nothing if the item is not in the
-- set.
function Set:discard(item)
local hash = item.__hash or item
if self[hash] then
self.size = self.size - 1
self[hash] = nil
end
end
-- RST
-- .. method:: contains(item)
--
-- Returns :const:`true` if the item is contained in this set,
-- :const:`false` otherwise
function Set:contains(item)
local hash = item.__hash or item
return self[hash] ~= nil
end
-- RST
-- .. method:: pop_at(n)
--
-- Returns the n-th item of this set and removes it. Note that the only
-- way to get to this item is by iterating, so this function scales
-- linearly with n.
function Set:pop_at(n)
assert(n <= self.size)
assert(n >= 1)
local ghash, gitem
for hash,item in pairs(self) do
if hash ~= "size" then
if n == 1 then
ghash, gitem = hash, item
break
end
n = n - 1
end
end
self:discard(gitem)
return gitem
end
-- RST
-- .. method:: items
--
-- Iterator function that allows easy iterating of all items.
--
-- .. code-block:: lua
--
-- s = Set:new{"a","b","c"}
-- for i in s:items() do print(i) end
function Set:items()
local co = coroutine.create(function ()
for hash, v in pairs(self) do
if hash ~= "size" then
coroutine.yield(v)
end
end
end)
return function () -- iterator
local code, res = coroutine.resume(co)
return res
end
end
-- RST
-- .. method:: union(other_set)
--
-- Returns a new set that is the union of both sets. This is
-- also overloaded to the '+' operator
function Set:union(b)
local rv = Set:new()
for hash,item in pairs(self) do
if hash ~= "size" then rv:add(item) end
end
for hash,item in pairs(b) do
if hash ~= "size" then rv:add(item) end
end
return rv
end
Set.__add = Set.union
-- RST
-- .. method:: subtract(other_set)
--
-- Returns a new set that contains all values of this set that
-- are not in other_set. This is also overloaded to the '-' operator.
function Set:substract(b)
local rv = Set:new()
for hash, value in pairs(self) do
if hash ~= "size" then rv:add(value) end
end
for hash, value in pairs(b) do
if hash ~= "size" then rv:discard(value) end
end
return rv
end
Set.__sub = Set.substract
-- RST
-- .. method:: intersection(other_set)
--
-- Returns a new set that contains all values of this set that are also
-- in other_set. This is also overloaded to the '*' operator.
function Set:intersection(b)
local rv = Set:new{}
for hash,value in pairs(self) do
if b[hash] and hash ~= "size" then
rv:add(value)
end
end
return rv
end
Set.__mul = Set.intersection
function Set:__eq(b)
if b.size == self.size and (self-b).size == 0 then return true end
return false
end
function Set:__tostring()
local l = {}
for hash,item in pairs(self) do
if hash ~= "size" then
l[#l + 1] = tostring(item)
end
end
table.sort(l)
return '{' .. table.concat(l, ", ") .. '}'
end
|