properset.lua

Contents

• Class Set
• Class FrozenSet
• Set arithmetics
• Utility functions
• Constants

Modules

• properset

Topics

• README

Module properset

Handles complex sets.

Usage:

> properset = require 'properset'
> Set = properset.Set
> a = Set{1, 2, 2, 3, 3, 3}
> a
{1, 2, 3}

Info:

• Copyright: 2018 Odin Kroeger
• Release: 0.3b-1
• License: MIT
• Author: Odin Kroeger

Class Set

Class FrozenSet

Set arithmetics

Utility functions

Constants

Class Set

Set:new ([elems])

Creates a new instance of a prototype, typically Set.

a:new, where a is itself an ‘instance’ of Set, will create a new ‘instance’ of Set, not an ‘instance’ of a. That is, b = a:new(), b = Set:new(), and b = Set() are equivalent.

  > a = Set()
  > b = a:new()
  > getmetatable(a) == getmetatable(b)
  true

Parameters:

• elems table Members for the new set. (optional)

Returns:

An instance of the given prototype for sets, populated with elems, if any were given.

Usage:

> Set:new{1, 2, 3}
{1, 2, 3}
> Set{1, 2, 3}
{1, 2, 3}

Set:id ([flags=0])

Returns the ID of the set.

Parameters:

• flags number If ASNUM is set, returns the ID as a number. (default 0)

Returns:

number The ID.

Usage:

> a = Set()
> a:id()
Set: 0x7f8a555d4df0
> a:id(properset.ASNUM)
140232114392560

Set:add (elems)

Adds elements to a set.

Don’t add members to a set while you're iterating over it.

Parameters:

• elems table A list of elements to be added.

Raises:

Raises an error if you try to add a set to itself.

Usage:

> a = Set{1}
> a:add{2}
> a
{1, 2}
> a:add{2}
> a
{1, 2}

Set:remove (members)

Deletes members from a set.

Don’t remove members from a set while you're iterating over it.

Parameters:

• members table A list of members to be removed.

Usage:

> a = Set{1, 2, 3}
> a:remove{2, 3}
> a
{1}

Set:clear ()

Removes all members from the set.

Don’t remove members from a set while you're iterating over it.

Usage:

> a = Set{1, 2}
> a:clear()
> a
{}

Set:pop ()

Removes an arbitrary members from the set and returns it.

Don’t remove members from a set while you're iterating over it. If you want to iterate over the whole set, use members with the flag properset.POPOFF instead.

Usage:

> a = Set{1, 2}
> a:pop()
1
> a
{2}

Set:isempty ()

Tests whether the set is empty.

Returns:

boolean Whether the set is empty.

Usage:

> a = Set()
> a:isempty()
true
> b = Set{1}
> b:isempty()
false

Set:isfrozen ()

Tests whether the set is frozen.

Returns:

boolean false.

Usage:

> a = Set()
> a:isfrozen()
false

Set:has (obj)

Tests whether an object is a member of the set.

Parameters:

• obj An object.

Returns:

boolean Whether an object is a member of the set.

Usage:

> a = Set{1}
> a:has(1)
true
> a:has(0)
false

Set:members ([flags=0])

Iterates over all members of the set.

Parameters:

• flags number If POPOFF is set, removes from the set each member returned. (default 0)

Returns:

function A function that returns a member of the set.

Usage:

> a = Set{1, 2, 3}
> for v in a:members() do print(v) end
1
2
3

Set:power ()

The set’s power set.

Calculating a power set runs in exponential time, namely, O(2^n). Average times needed to calculate the power set of a set with n members (on an 1,6 GHz Intel Core i5 with Lua 5.3.4):

• n = 8: <0.01s
• n = 9: 0.01s
• n = 10: 0.02s,
• n = 11: 0.03s
• n = 12: 0.06s
• n = 13: 0.12s
• n = 14: 0.28s
• n = 15: 0.51s
• n = 16: 1s

Returns:

Set(Set,...) The set’s power set.

Usage:

> a = Set{0, 1}
> a:power()
{{0, 1}, {1}, {}, {0}}

Set:ofrank (n[, flags=0])

All members of rank n.

a:flattened() and a:ofrank(0, propertyset.RECURSIVE) are equivalent.

Parameters:

• n number The rank.
• flags number If RECURSIVE is set, then searches members of the set that are sets, members of those sets that are sets, …, too. (default 0)

Returns:

Set The members of rank n.

See also:

rank

Usage:

> a = Set{1, Set{2, Set{3, 4}, Set{5}}, Set{6}}
> a
{1, {2, {3, 4}, {5}}, {6}}
> a:ofrank(0)
{1}
> a:ofrank(1)
{{6}}
> a:ofrank(2)
{{2, {3, 4}, {5}}}
> a:ofrank(3)
{}
> a:ofrank(0, properset.RECURSIVE)
{1, 2, 3, 4, 5, 6}
> a:ofrank(1, properset.RECURSIVE)
{{3, 4}, {5}, {6}}
> a:ofrank(2, properset.RECURSIVE)
{{2, {3, 4}, {5}}}
> a:ofrank(3, properset.RECURSIVE)
{}

Set:atlevel (n)

All members at level n.

Levels: 1 = members of the set, 2 = members of members of the set, 3 = …

Parameters:

• n number The level.

Returns:

Set The members at level n.

Raises:

Raises an error unless n > 0.

Usage:

> a = Set{1, Set{2, Set{3, 4}, Set{5}}, Set{6}}
> a
{1, {2, {3, 4}, {5}}, {6}}
> a:atlevel(1)
{1, {2, {3, 4}, {5}}, {6}}
> a:atlevel(2)
{2, {3, 4}, {5}, 6}
> a:atlevel(3)
{3, 4, 5}
> a:atlevel(4)
{}

Set:map (func[, flags=0])

Maps a function of all values of the set onto another set.

Parameters:

• func function A function to be applied to each member.
• flags number If RECURSIVE is set, applies func to members of the set that are sets, members of those sets that are sets, …, too. (default 0)

Returns:

Set The results of applying func to the members of the set.

Usage:

> a = Set{1, 2, 3}
> a:map(function(i) return i + 1 end)
{2, 3, 4}
> a = Set{1, 2, Set{3, 4}}
> a:map(function (i) return i + 1 end, properset.RECURSIVE)
{2, 3, {4, 5}}

Set:filter (func[, flags=0])

Filters members of a set.

Parameters:

• func function A function that defines which members to return.
• flags number If RECURSIVE is set, tests members of the set that are sets, members of those sets that are sets, …, too. (default 0)

Returns:

Set The filtered set.

Usage:

> a = Set{1, 2, 3}
> a:filter(function(i) return i % 2 == 0 end)
{2}

Set:totable ([flags=0])

The members of the set as a table.

Parameters:

• flags number If RECURSIVE is set, then converts members of the set that are sets, members of those sets that are sets, …, too. (default 0)

Returns:

table All members of the set.

Usage:

> a = Set{1, 2, 3}
> r = a:totable()
> table.unpack(r)
1       2       3

Set:unpack ([flags=0])

Unpacks the members of the set.

Parameters:

• flags number If RECURSIVE is set, then unpacks not only this set, but all sets that are members of this set, members of those sets, and so forth. (default 0)

Returns:

The members of the given set unpacked.

Usage:

> a = Set{1, 2, 3}
> a:unpack()
1       2       3

Set:sorted ([func[, flags=0]])

Returns the members of the set sorted.

Keep in mind, sets may be multidimensional.

Parameters:

• func function A sorting function. (optional)
• flags number If RECURSIVE is set, then sorts not only this set, but all sets that are members of this set, members of those sets, and so forth. (default 0)

Returns:

table A list of the members of the given set, sorted.

Usage:

> a = Set{1, 3, 5, 2, 4, 6, 8, 10, 5, 9, 7}
> r = a:sorted()
> table.concat(r, ', ')
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Set:flattened ()

The non-set members of the set and its descendants.

Returns:

Set A set with all non-set members of the set and its descendants.

Usage:

> a = Set{1, Set{2, 3}, 4}
> b = a:power()
> b:flattened()
{1, 2, 3, 4}

Set:freeze ()

Makes a set immutable.

Returns:

FrozenSet The frozen set.

Usage:

> a = Set()
> a:add{0}
> a
{0}
> a:freeze()
{0}
> a:add{1}
set is frozen.
[...]

Set:unfreeze ()

Does nothing.

Returns:

Set The set.

Usage:

> a = Set()
> a:unfreeze()
{}

Set.mt:__newindex ()

Blocks accidential modifications of the set.

Raises:

An error whenever it’s invoked.

Set.mt:__call ([elems])

Easier access to new in derived prototypes.

Parameters:

• elems table Members for the new set. (optional)

Returns:

An instance of the given prototype for sets, populated with elems, if any were given.

Set.mt:__len ()

The number of elements in the set.

Returns:

number Number of elements in the set.

Usage:

> a = Set{1, 2, 3}
> #a
3

Set.mt:__ipairs ()

Iterates over the set as if it were a list.

Usage:

> a = Set{'a', 'b', 'c'}
> for i, v in ipairs(a) do print(i, v) end
1       a
2       b
3       c

Set.mt.__pairs

Iterates over the set as if it were a table.

Usage:

> a = Set{'a', 'b', 'c'}
> for k, v in pairs(a) do print(k, v) end
1       a
2       b
3       c

Set.mt:__le (other)

Tests whether the set is a subset of another set.

Parameters:

• other Set The other set.

Returns:

boolean Whether the set is a subset of another set.

Raises:

Raises an error of other is not a Set (or another implementation of its protocol).

Usage:

> a = Set{1, 2}
> b = Set{1}
> c = Set{3}
> b <= a
true
> c <= a
false

Set.mt:__lt (other)

Tests whether the set is a strict subset of another set.

Parameters:

• other Set The other set.

Returns:

boolean Whether the set is a strict subset of another set.

Raises:

Raises an error of other is not a Set (or another implementation of its protocol).

Usage:

> a = Set{1, 2}
> b = Set{1}
> c = Set{3}
> a < a
false
> a <= a
true
> b < a
true
> c < a
false

Set.mt:__eq (other)

Tests whether the set is equal to another set.

Parameters:

• other Set The other set.

Returns:

boolean Whether the set is equal to another set.

Raises:

Raises an error of other is not a Set (or another implementation of its protocol).

Usage:

> a = Set{1}
> b = Set{1}
> c = Set{2}
> a == b
true
> a ~= b
false
> a == c
false
> a ~= c
true

Set.mt:__add (other)

The union of the set and another set.

union(a, b) and a + b are equivalent.

Parameters:

• other Set The other set.

Returns:

Set The union of the two sets.

Raises:

Raises an error of other is not a Set (or another implementation of its protocol).

Usage:

> a = Set{1}
> b = Set{2}
> a + b
{1, 2}

Set.mt:__sub (other)

The complement of the set and another set.

complement(a, b) and a – b are equivalent.

Parameters:

• other Set The other set.

Returns:

Set The complement of the two sets.

Raises:

Raises an error of other is not a Set (or another implementation of its protocol).

Usage:

> a = Set{1, 2}
> b = Set{2}
> a - b
{1}

Set.mt:__pow (other)

The intersection of the set and another set.

intersection(a, b) and a ^ b are equivalent.

Parameters:

• other Set The other set.

Returns:

Set The intersection of the two sets.

Raises:

Raises an error of other is not a Set (or another implementation of its protocol).

Usage:

> a = Set{1, 2}
> b = Set{2, 3}
> a ^ b
{3}

Set.mt:__tostring (s)

A string representation of the set.

Parameters:

• s

Returns:

string A string that represents the set.

Usage:

> a = Set{1, Set{2, 3}, 4}
> tostring(a)
{1, {2, 3}, 4}

Class FrozenSet

FrozenSet:new ([elems])

Creates a new instance of a set prototype, typically FrozenSet.

Note: You cannot create instances of FrozenSet using Set.new.

Parameters:

• elems table Members for the new set. (optional)

Returns:

An instance of the given prototype for sets, populated with members, if any were given.

Usage:

> FrozenSet:new{1, 2, 3}
{1, 2, 3}
> FrozenSet{1, 2, 3}
{1, 2, 3}

FrozenSet:isfrozen ()

Tests whether the set is frozen.

Returns:

boolean true.

Usage:

> a = FrozenSet()
> a:isfrozen()
true

FrozenSet.add ()

Blocks accidential modifications of the set.

Raises:

An error whenever it’s invoked.

FrozenSet.remove ()

Blocks accidential modifications of the set.

Raises:

An error whenever it’s invoked.

FrozenSet.clear ()

Blocks accidential modifications of the set.

Raises:

An error whenever it’s invoked.

FrozenSet:freeze ()

Does nothing.

Returns:

FrozenSet The frozen set.

Usage:

> a = FrozenSet()
> a:freeze()
{}

FrozenSet:unfreeze ()

Make the set mutable.

Returns:

Set The unfrozen set.

Usage:

> a = FrozenSet()
> a:add{0}
set is frozen.
[...]
> a:unfreeze()
{}
> a:add{0}
> a
{0}

Set arithmetics

aredisjoint (sets)

Tests whether two or more sets are disjoint.

Parameters:

• sets {Set,...} A list of sets to compare.

Returns:

boolean Whether the given sets are disjoint.

Usage:

> a = Set{1}
> b = Set{1, 2}
> c = Set{2}
> d = Set{3}
> properset.aredisjoint{a, b, c}
false
> properset.aredisjoint{a, c, d}
true

complement (a, b)

The complement of two sets A and B.

complement(a, b) and a – b are equivalent.

Parameters:

• a Set Set A.
• b Set Set B.

Returns:

Set The complement of A and B.

Usage:

> a = Set{1, 2}
> b = Set{2}
> properset.complement(a, b)
{1}

union (sets)

The union of two or more sets.

a:union(b) and a + b are equivalent.

Parameters:

• sets {Set,...} A list of sets of which to form a union.

Returns:

Set The union of the given sets.

Usage:

> a = Set{1}
> b = Set{2}
> c = Set{3}
> properset.union{a, b, c}
{1, 2, 3}

intersection (sets)

The intersection of two or more sets.

Parameters:

• sets {Set,...} A list of sets to intersect.

Returns:

Set The intersection of the given sets.

Usage:

> a = Set{1}
> b = Set{1,2}
> c = Set{2}
> d = Set{1,3}
> properset.intersection{a, b, c}
{}
> properset.intersection{a, b, d}
{1}

difference (sets)

The symmetric difference of two or more sets.

The symmetric difference, Δ, of three sets A, B, and C is defined as: (A Δ B) Δ C, that is, as ‘repetition’ over a series, not as (A ∪ B ∪ C) \ (A ∩ B ∩ C), that is, as the complement of the union of A, B, and C and the intersection of A, B, and C. Make sure you understand the example below. (A friendly reminder for us non-mathematicians and non-computer science people.)

Parameters:

• sets {Set,...} A list of sets to calculate the difference of.

Returns:

Set The symmetric difference of the given sets.

Usage:

> a = Set{1, 2}
> b = Set{1, 3}
> c = Set{1, 2, 3, 4}
> properset.difference{a, b, c}
{1, 4}

Utility functions

isset (obj)

Tests whether an object behaves like a Set.

That is, tests:

1. whether an object’s metatable has all fields defined in Set.mt;
2. whether an object has all fields defined in Set.

Note: Does not test whether those fields refer to functions.

An object whose metatable provides all methods defined in Set.mt and that itself provides all methods defined in Set is said to implement the “Set protocol”.

Parameters:

• obj An object.

Returns:

1. boolean Whether obj implements the Set protocol.
2. string If it doesn’t implement the Set protocol, an error message.

Usage:

> a = Set()
> properset.isset(a)
true
> b = "I may be many things, but a Set I'm not."
> properset.isset(b)
false     expected a Set, got a string.

rank (obj)

Calculates the rank of an object.

Ranks: 0 = non-set objects, 1 = sets that don’t contain sets, 2 = sets that (also) contain sets, but only of rank 1, 3 = sets that (also) contain sets of rank 2, 4 = …

Parameters:

• obj An object.

Returns:

number The rank of obj.

Usage:

> s = "I'm nobody."
> properset.rank(s)
0
> a = Set()
> properset.rank(a)
1
> b = Set{Set{Set{Set{}}, Set{}, 1}, 2}
> properset.rank(b)
4

copy (obj)

Copies a table recursively.

Handles metatables, recursive structures, tables as keys, and avoids the __pairs and __newindex metamethods. Copies are deep.

Parameters:

• obj Object or value of an arbitrary type.

Returns:

A copy of obj.

Usage:

> a = {1, 2, 3}
> b = {a, 4}
> r = properset.copy(b)
> table.insert(a, 4)
> table.unpack(r[1])
1       2       3

Constants

emptyset

The empty set.

• emptyset The empty set (FrozenSet:new()).

ASNUM

If this flag is passed to Set:id, the set’s ID is returned as a number.

Only used by Set:id.

POPOFF

If this flag is passed to Set:members, the members returned are removed from the set.

Only used by Set:members.

RECURSIVE

If this flag is passed to a method that understands it, sets are processed recursively.

Currently used by:

• Set:ofrank
• Set:map
• Set:filter
• Set:totable
• Set:unpack
• Set:sorted