util.set

A set is an unordered collection of unique values. Unlike an array or a list, it is very efficient at testing whether a value is currently stored in the set or not, without having to check every item.

Usage

    local set = require "util.set";
 
    local myset = set.new();
    myset:add("red");
    print(myset:contains("red")); --> true
    print(myset:contains("blue")); --> false

Reference

Construction

new(list)

Creates and returns a new set. You can optionally supply a list (or anything that can be iterated using ipairs())

For example:

    -- Creating an empty set
    local myset = set.new();
    -- Creating a set from an existing list
    local colours = set.new({ "red", "blue", "yellow", "green" });
    print(colours:contains("purple")) --> false
    print(colours:contains("yellow")) --> true

union(set1, set2)

Creates and returns a new set that contains all the items in set1 and all the items in set2.

difference(set1, set2)

Creates and returns a new set that contains all the items in set1 that are not in set2.

intersection(set1, set2)

Creates and returns a new set that contains only the items that are in both set1 and in set2.

xor(set1, set2)

Creates and returns a new set that contains only the items are in set1 or set2. Items that are in both sets will not be included.

Methods

Once a set is created, you can use these methods on them.

set:add(value)

Adds a value to the set. Any Lua value is acceptable, apart from nil.

set:remove(value)

Removes a value from the set.

set:contains(value)

Tests whether a value is currently in the set. Returns true if it is, or nil otherwise.

set:add_list(list)

Adds a list of values (a normal Lua array, util.array object, or anything that can be iterated using ipairs()) to the set.

set:include(another_set)

Adds all the values from another set to this set.

set:exclude(another_set)

Removes from this set all the values that another set contains.

set:empty()

Returns true if the set contains no values. Otherwise returns false.

set:items()

Returns the underlying data structure, a table with all the item values as keys, and boolean true as a value.

Operations

Addition

Adding two sets results in their union:

   superset = set1 + set2
   -- is the same as
   superset = set.union(set1, set2)

Subtraction

Subtracting a set results in their difference:

    newset = set1 - set2
    -- is the same as
    newset = set.difference(set1, set2)

Division

You can divide a set by a filter function, to produce a new set. The function is called once for each item, with the value as its first parameter. If the function does not return nil, the item is added to the new set.

    -- Returns true if the given number is even, or false if it is odd:
    local function is_even(number)
      if number%2 == 0 then
        return true;
      end
    end
 
    print(is_even(1), is_even(2), is_even(3), is_even(4)); --> false, true, false, true, etc.
 
    local numbers = set.new({ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
    local even_numbers = numbers / is_even;
    print(even_numbers); --> 2, 4, 6, 8, 10