classlib/set.lua at master · LuaDist/classlib · GitHub

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
require'tuple'

class.Set()

functionSet:__init(...)	-- Construct with initial elements
localarg= {...}
self.elem= {}
self.n=#arg
fori, vinipairs(arg) doself.elem[v] =trueend
end

functionSet:__tostring()	-- String representation
localfunctionascii(e)
returntype(e) =='string' andstring.format('%q', e) ortostring(e)
end
locals=''
foreinpairs(self.elem) do
s=#s==0andascii(e) ors..', ' ..ascii(e)
end
return'[' ..s..']'
end

functionSet:insert(e) -- Add an element
ifnotself.elem[e] then
self.elem[e] =true
self.n=self.n+1
end
end

functionSet:erase(e) -- Remove an element
ifself.elem[e] then
self.elem[e] =nil
self.n=self.n-1
end
end

functionSet:clear() -- Remove all elements
self.elem= {}
self.n=0
end

functionSet:size() -- Cardinality
returnself.n
end

functionSet:contains(e)	-- Check an element
returnself.elem[e] orfalse
end

functionSet:clone() -- Clone
localnew=Set()
new.n=self.n
foreinpairs(self.elem) donew.elem[e] =trueend
returnnew
end

functionSet:__add(r) -- Union
localnew=self:clone()
foreinpairs(r.elem) donew:insert(e) end
returnnew
end

functionSet:__sub(r) -- Difference
localnew=Set()
foreinpairs(self.elem) doifnotr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mod(r) -- Symmetric difference
return (self-r) + (r-self)
end

functionSet:__pow(r) -- Intersection
localnew=Set()
foreinpairs(self.elem) doifr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mul(r) -- Cartesian product
localnew=Set()
forfirstinpairs(self.elem) do
forsecondinpairs(r.elem) do
new:insert(Tuple(first, second))
end
end
returnnew
end

functionSet:__le(r) -- Containment
foreinpairs(self.elem) doifnotr.elem[e] thenreturnfalseendend
returntrue
end

functionSet:__lt(r) -- Strict containment
returnself<=randself.n<r.n
end

functionSet:__eq(r) -- Congruence
returnself<=randself.n==r.n
end

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
require'tuple'

class.Set()

functionSet:__init(...)	-- Construct with initial elements
localarg= {...}
self.elem= {}
self.n=#arg
fori, vinipairs(arg) doself.elem[v] =trueend
end

functionSet:__tostring()	-- String representation
localfunctionascii(e)
returntype(e) =='string' andstring.format('%q', e) ortostring(e)
end
locals=''
foreinpairs(self.elem) do
s=#s==0andascii(e) ors..', ' ..ascii(e)
end
return'[' ..s..']'
end

functionSet:insert(e) -- Add an element
ifnotself.elem[e] then
self.elem[e] =true
self.n=self.n+1
end
end

functionSet:erase(e) -- Remove an element
ifself.elem[e] then
self.elem[e] =nil
self.n=self.n-1
end
end

functionSet:clear() -- Remove all elements
self.elem= {}
self.n=0
end

functionSet:size() -- Cardinality
returnself.n
end

functionSet:contains(e)	-- Check an element
returnself.elem[e] orfalse
end

functionSet:clone() -- Clone
localnew=Set()
new.n=self.n
foreinpairs(self.elem) donew.elem[e] =trueend
returnnew
end

functionSet:__add(r) -- Union
localnew=self:clone()
foreinpairs(r.elem) donew:insert(e) end
returnnew
end

functionSet:__sub(r) -- Difference
localnew=Set()
foreinpairs(self.elem) doifnotr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mod(r) -- Symmetric difference
return (self-r) + (r-self)
end

functionSet:__pow(r) -- Intersection
localnew=Set()
foreinpairs(self.elem) doifr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mul(r) -- Cartesian product
localnew=Set()
forfirstinpairs(self.elem) do
forsecondinpairs(r.elem) do
new:insert(Tuple(first, second))
end
end
returnnew
end

functionSet:__le(r) -- Containment
foreinpairs(self.elem) doifnotr.elem[e] thenreturnfalseendend
returntrue
end

functionSet:__lt(r) -- Strict containment
returnself<=randself.n<r.n
end

functionSet:__eq(r) -- Congruence
returnself<=randself.n==r.n
end

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
require'tuple'

class.Set()

functionSet:__init(...)	-- Construct with initial elements
localarg= {...}
self.elem= {}
self.n=#arg
fori, vinipairs(arg) doself.elem[v] =trueend
end

functionSet:__tostring()	-- String representation
localfunctionascii(e)
returntype(e) =='string' andstring.format('%q', e) ortostring(e)
end
locals=''
foreinpairs(self.elem) do
s=#s==0andascii(e) ors..', ' ..ascii(e)
end
return'[' ..s..']'
end

functionSet:insert(e) -- Add an element
ifnotself.elem[e] then
self.elem[e] =true
self.n=self.n+1
end
end

functionSet:erase(e) -- Remove an element
ifself.elem[e] then
self.elem[e] =nil
self.n=self.n-1
end
end

functionSet:clear() -- Remove all elements
self.elem= {}
self.n=0
end

functionSet:size() -- Cardinality
returnself.n
end

functionSet:contains(e)	-- Check an element
returnself.elem[e] orfalse
end

functionSet:clone() -- Clone
localnew=Set()
new.n=self.n
foreinpairs(self.elem) donew.elem[e] =trueend
returnnew
end

functionSet:__add(r) -- Union
localnew=self:clone()
foreinpairs(r.elem) donew:insert(e) end
returnnew
end

functionSet:__sub(r) -- Difference
localnew=Set()
foreinpairs(self.elem) doifnotr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mod(r) -- Symmetric difference
return (self-r) + (r-self)
end

functionSet:__pow(r) -- Intersection
localnew=Set()
foreinpairs(self.elem) doifr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mul(r) -- Cartesian product
localnew=Set()
forfirstinpairs(self.elem) do
forsecondinpairs(r.elem) do
new:insert(Tuple(first, second))
end
end
returnnew
end

functionSet:__le(r) -- Containment
foreinpairs(self.elem) doifnotr.elem[e] thenreturnfalseendend
returntrue
end

functionSet:__lt(r) -- Strict containment
returnself<=randself.n<r.n
end

functionSet:__eq(r) -- Congruence
returnself<=randself.n==r.n
end

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
require'tuple'

class.Set()

functionSet:__init(...)	-- Construct with initial elements
localarg= {...}
self.elem= {}
self.n=#arg
fori, vinipairs(arg) doself.elem[v] =trueend
end

functionSet:__tostring()	-- String representation
localfunctionascii(e)
returntype(e) =='string' andstring.format('%q', e) ortostring(e)
end
locals=''
foreinpairs(self.elem) do
s=#s==0andascii(e) ors..', ' ..ascii(e)
end
return'[' ..s..']'
end

functionSet:insert(e) -- Add an element
ifnotself.elem[e] then
self.elem[e] =true
self.n=self.n+1
end
end

functionSet:erase(e) -- Remove an element
ifself.elem[e] then
self.elem[e] =nil
self.n=self.n-1
end
end

functionSet:clear() -- Remove all elements
self.elem= {}
self.n=0
end

functionSet:size() -- Cardinality
returnself.n
end

functionSet:contains(e)	-- Check an element
returnself.elem[e] orfalse
end

functionSet:clone() -- Clone
localnew=Set()
new.n=self.n
foreinpairs(self.elem) donew.elem[e] =trueend
returnnew
end

functionSet:__add(r) -- Union
localnew=self:clone()
foreinpairs(r.elem) donew:insert(e) end
returnnew
end

functionSet:__sub(r) -- Difference
localnew=Set()
foreinpairs(self.elem) doifnotr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mod(r) -- Symmetric difference
return (self-r) + (r-self)
end

functionSet:__pow(r) -- Intersection
localnew=Set()
foreinpairs(self.elem) doifr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mul(r) -- Cartesian product
localnew=Set()
forfirstinpairs(self.elem) do
forsecondinpairs(r.elem) do
new:insert(Tuple(first, second))
end
end
returnnew
end

functionSet:__le(r) -- Containment
foreinpairs(self.elem) doifnotr.elem[e] thenreturnfalseendend
returntrue
end

functionSet:__lt(r) -- Strict containment
returnself<=randself.n<r.n
end

functionSet:__eq(r) -- Congruence
returnself<=randself.n==r.n
end

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
require'tuple'

class.Set()

functionSet:__init(...)	-- Construct with initial elements
localarg= {...}
self.elem= {}
self.n=#arg
fori, vinipairs(arg) doself.elem[v] =trueend
end

functionSet:__tostring()	-- String representation
localfunctionascii(e)
returntype(e) =='string' andstring.format('%q', e) ortostring(e)
end
locals=''
foreinpairs(self.elem) do
s=#s==0andascii(e) ors..', ' ..ascii(e)
end
return'[' ..s..']'
end

functionSet:insert(e) -- Add an element
ifnotself.elem[e] then
self.elem[e] =true
self.n=self.n+1
end
end

functionSet:erase(e) -- Remove an element
ifself.elem[e] then
self.elem[e] =nil
self.n=self.n-1
end
end

functionSet:clear() -- Remove all elements
self.elem= {}
self.n=0
end

functionSet:size() -- Cardinality
returnself.n
end

functionSet:contains(e)	-- Check an element
returnself.elem[e] orfalse
end

functionSet:clone() -- Clone
localnew=Set()
new.n=self.n
foreinpairs(self.elem) donew.elem[e] =trueend
returnnew
end

functionSet:__add(r) -- Union
localnew=self:clone()
foreinpairs(r.elem) donew:insert(e) end
returnnew
end

functionSet:__sub(r) -- Difference
localnew=Set()
foreinpairs(self.elem) doifnotr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mod(r) -- Symmetric difference
return (self-r) + (r-self)
end

functionSet:__pow(r) -- Intersection
localnew=Set()
foreinpairs(self.elem) doifr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mul(r) -- Cartesian product
localnew=Set()
forfirstinpairs(self.elem) do
forsecondinpairs(r.elem) do
new:insert(Tuple(first, second))
end
end
returnnew
end

functionSet:__le(r) -- Containment
foreinpairs(self.elem) doifnotr.elem[e] thenreturnfalseendend
returntrue
end

functionSet:__lt(r) -- Strict containment
returnself<=randself.n<r.n
end

functionSet:__eq(r) -- Congruence
returnself<=randself.n==r.n
end

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
require'tuple'

class.Set()

functionSet:__init(...)	-- Construct with initial elements
localarg= {...}
self.elem= {}
self.n=#arg
fori, vinipairs(arg) doself.elem[v] =trueend
end

functionSet:__tostring()	-- String representation
localfunctionascii(e)
returntype(e) =='string' andstring.format('%q', e) ortostring(e)
end
locals=''
foreinpairs(self.elem) do
s=#s==0andascii(e) ors..', ' ..ascii(e)
end
return'[' ..s..']'
end

functionSet:insert(e) -- Add an element
ifnotself.elem[e] then
self.elem[e] =true
self.n=self.n+1
end
end

functionSet:erase(e) -- Remove an element
ifself.elem[e] then
self.elem[e] =nil
self.n=self.n-1
end
end

functionSet:clear() -- Remove all elements
self.elem= {}
self.n=0
end

functionSet:size() -- Cardinality
returnself.n
end

functionSet:contains(e)	-- Check an element
returnself.elem[e] orfalse
end

functionSet:clone() -- Clone
localnew=Set()
new.n=self.n
foreinpairs(self.elem) donew.elem[e] =trueend
returnnew
end

functionSet:__add(r) -- Union
localnew=self:clone()
foreinpairs(r.elem) donew:insert(e) end
returnnew
end

functionSet:__sub(r) -- Difference
localnew=Set()
foreinpairs(self.elem) doifnotr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mod(r) -- Symmetric difference
return (self-r) + (r-self)
end

functionSet:__pow(r) -- Intersection
localnew=Set()
foreinpairs(self.elem) doifr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mul(r) -- Cartesian product
localnew=Set()
forfirstinpairs(self.elem) do
forsecondinpairs(r.elem) do
new:insert(Tuple(first, second))
end
end
returnnew
end

functionSet:__le(r) -- Containment
foreinpairs(self.elem) doifnotr.elem[e] thenreturnfalseendend
returntrue
end

functionSet:__lt(r) -- Strict containment
returnself<=randself.n<r.n
end

functionSet:__eq(r) -- Congruence
returnself<=randself.n==r.n
end

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
require'tuple'

class.Set()

functionSet:__init(...)	-- Construct with initial elements
localarg= {...}
self.elem= {}
self.n=#arg
fori, vinipairs(arg) doself.elem[v] =trueend
end

functionSet:__tostring()	-- String representation
localfunctionascii(e)
returntype(e) =='string' andstring.format('%q', e) ortostring(e)
end
locals=''
foreinpairs(self.elem) do
s=#s==0andascii(e) ors..', ' ..ascii(e)
end
return'[' ..s..']'
end

functionSet:insert(e) -- Add an element
ifnotself.elem[e] then
self.elem[e] =true
self.n=self.n+1
end
end

functionSet:erase(e) -- Remove an element
ifself.elem[e] then
self.elem[e] =nil
self.n=self.n-1
end
end

functionSet:clear() -- Remove all elements
self.elem= {}
self.n=0
end

functionSet:size() -- Cardinality
returnself.n
end

functionSet:contains(e)	-- Check an element
returnself.elem[e] orfalse
end

functionSet:clone() -- Clone
localnew=Set()
new.n=self.n
foreinpairs(self.elem) donew.elem[e] =trueend
returnnew
end

functionSet:__add(r) -- Union
localnew=self:clone()
foreinpairs(r.elem) donew:insert(e) end
returnnew
end

functionSet:__sub(r) -- Difference
localnew=Set()
foreinpairs(self.elem) doifnotr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mod(r) -- Symmetric difference
return (self-r) + (r-self)
end

functionSet:__pow(r) -- Intersection
localnew=Set()
foreinpairs(self.elem) doifr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mul(r) -- Cartesian product
localnew=Set()
forfirstinpairs(self.elem) do
forsecondinpairs(r.elem) do
new:insert(Tuple(first, second))
end
end
returnnew
end

functionSet:__le(r) -- Containment
foreinpairs(self.elem) doifnotr.elem[e] thenreturnfalseendend
returntrue
end

functionSet:__lt(r) -- Strict containment
returnself<=randself.n<r.n
end

functionSet:__eq(r) -- Congruence
returnself<=randself.n==r.n
end

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
require'tuple'

class.Set()

functionSet:__init(...)	-- Construct with initial elements
localarg= {...}
self.elem= {}
self.n=#arg
fori, vinipairs(arg) doself.elem[v] =trueend
end

functionSet:__tostring()	-- String representation
localfunctionascii(e)
returntype(e) =='string' andstring.format('%q', e) ortostring(e)
end
locals=''
foreinpairs(self.elem) do
s=#s==0andascii(e) ors..', ' ..ascii(e)
end
return'[' ..s..']'
end

functionSet:insert(e) -- Add an element
ifnotself.elem[e] then
self.elem[e] =true
self.n=self.n+1
end
end

functionSet:erase(e) -- Remove an element
ifself.elem[e] then
self.elem[e] =nil
self.n=self.n-1
end
end

functionSet:clear() -- Remove all elements
self.elem= {}
self.n=0
end

functionSet:size() -- Cardinality
returnself.n
end

functionSet:contains(e)	-- Check an element
returnself.elem[e] orfalse
end

functionSet:clone() -- Clone
localnew=Set()
new.n=self.n
foreinpairs(self.elem) donew.elem[e] =trueend
returnnew
end

functionSet:__add(r) -- Union
localnew=self:clone()
foreinpairs(r.elem) donew:insert(e) end
returnnew
end

functionSet:__sub(r) -- Difference
localnew=Set()
foreinpairs(self.elem) doifnotr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mod(r) -- Symmetric difference
return (self-r) + (r-self)
end

functionSet:__pow(r) -- Intersection
localnew=Set()
foreinpairs(self.elem) doifr.elem[e] thennew:insert(e) endend
returnnew
end

functionSet:__mul(r) -- Cartesian product
localnew=Set()
forfirstinpairs(self.elem) do
forsecondinpairs(r.elem) do
new:insert(Tuple(first, second))
end
end
returnnew
end

functionSet:__le(r) -- Containment
foreinpairs(self.elem) doifnotr.elem[e] thenreturnfalseendend
returntrue
end

functionSet:__lt(r) -- Strict containment
returnself<=randself.n<r.n
end

functionSet:__eq(r) -- Congruence
returnself<=randself.n==r.n
end