summaryrefslogtreecommitdiff
path: root/macros/luatex/generic/penlight/pl/Set.lua
diff options
context:
space:
mode:
Diffstat (limited to 'macros/luatex/generic/penlight/pl/Set.lua')
-rw-r--r--macros/luatex/generic/penlight/pl/Set.lua222
1 files changed, 222 insertions, 0 deletions
diff --git a/macros/luatex/generic/penlight/pl/Set.lua b/macros/luatex/generic/penlight/pl/Set.lua
new file mode 100644
index 0000000000..ce428f0a0d
--- /dev/null
+++ b/macros/luatex/generic/penlight/pl/Set.lua
@@ -0,0 +1,222 @@
+--- A Set class.
+--
+-- > Set = require 'pl.Set'
+-- > = Set{'one','two'} == Set{'two','one'}
+-- true
+-- > fruit = Set{'apple','banana','orange'}
+-- > = fruit['banana']
+-- true
+-- > = fruit['hazelnut']
+-- nil
+-- > colours = Set{'red','orange','green','blue'}
+-- > = fruit,colours
+-- [apple,orange,banana] [blue,green,orange,red]
+-- > = fruit+colours
+-- [blue,green,apple,red,orange,banana]
+-- [orange]
+-- > more_fruits = fruit + 'apricot'
+-- > = fruit*colours
+-- > = more_fruits, fruit
+-- [banana,apricot,apple,orange] [banana,apple,orange]
+--
+-- Dependencies: `pl.utils`, `pl.tablex`, `pl.class`, `pl.Map`, (`pl.List` if __tostring is used)
+-- @classmod pl.Set
+
+local tablex = require 'pl.tablex'
+local utils = require 'pl.utils'
+local array_tostring, concat = utils.array_tostring, table.concat
+local merge,difference = tablex.merge,tablex.difference
+local Map = require 'pl.Map'
+local class = require 'pl.class'
+local stdmt = utils.stdmt
+local Set = stdmt.Set
+
+-- the Set class --------------------
+class(Map,nil,Set)
+
+-- note: Set has _no_ methods!
+Set.__index = nil
+
+local function makeset (t)
+ return setmetatable(t,Set)
+end
+
+--- create a set. <br>
+-- @param t may be a Set, Map or list-like table.
+-- @class function
+-- @name Set
+function Set:_init (t)
+ t = t or {}
+ local mt = getmetatable(t)
+ if mt == Set or mt == Map then
+ for k in pairs(t) do self[k] = true end
+ else
+ for _,v in ipairs(t) do self[v] = true end
+ end
+end
+
+--- string representation of a set.
+-- @within metamethods
+function Set:__tostring ()
+ return '['..concat(array_tostring(Set.values(self)),',')..']'
+end
+
+--- get a list of the values in a set.
+-- @param self a Set
+-- @function Set.values
+-- @return a list
+Set.values = Map.keys
+
+--- map a function over the values of a set.
+-- @param self a Set
+-- @param fn a function
+-- @param ... extra arguments to pass to the function.
+-- @return a new set
+function Set.map (self,fn,...)
+ fn = utils.function_arg(1,fn)
+ local res = {}
+ for k in pairs(self) do
+ res[fn(k,...)] = true
+ end
+ return makeset(res)
+end
+
+--- union of two sets (also +).
+-- @param self a Set
+-- @param set another set
+-- @return a new set
+function Set.union (self,set)
+ return merge(self,set,true)
+end
+
+--- modifies '+' operator to allow addition of non-Set elements
+--- Preserves +/- semantics - does not modify first argument.
+local function setadd(self,other)
+ local mt = getmetatable(other)
+ if mt == Set or mt == Map then
+ return Set.union(self,other)
+ else
+ local new = Set(self)
+ new[other] = true
+ return new
+ end
+end
+
+--- union of sets.
+-- @within metamethods
+-- @function Set.__add
+
+Set.__add = setadd
+
+--- intersection of two sets (also *).
+-- @param self a Set
+-- @param set another set
+-- @return a new set
+-- @usage
+-- > s = Set{10,20,30}
+-- > t = Set{20,30,40}
+-- > = t
+-- [20,30,40]
+-- > = Set.intersection(s,t)
+-- [30,20]
+-- > = s*t
+-- [30,20]
+
+function Set.intersection (self,set)
+ return merge(self,set,false)
+end
+
+--- intersection of sets.
+-- @within metamethods
+-- @function Set.__mul
+Set.__mul = Set.intersection
+
+--- new set with elements in the set that are not in the other (also -).
+-- @param self a Set
+-- @param set another set
+-- @return a new set
+function Set.difference (self,set)
+ return difference(self,set,false)
+end
+
+--- modifies "-" operator to remove non-Set values from set.
+--- Preserves +/- semantics - does not modify first argument.
+local function setminus (self,other)
+ local mt = getmetatable(other)
+ if mt == Set or mt == Map then
+ return Set.difference(self,other)
+ else
+ local new = Set(self)
+ new[other] = nil
+ return new
+ end
+end
+
+--- difference of sets.
+-- @within metamethods
+-- @function Set.__sub
+Set.__sub = setminus
+
+-- a new set with elements in _either_ the set _or_ other but not both (also ^).
+-- @param self a Set
+-- @param set another set
+-- @return a new set
+function Set.symmetric_difference (self,set)
+ return difference(self,set,true)
+end
+
+--- symmetric difference of sets.
+-- @within metamethods
+-- @function Set.__pow
+Set.__pow = Set.symmetric_difference
+
+--- is the first set a subset of the second (also <)?.
+-- @param self a Set
+-- @param set another set
+-- @return true or false
+function Set.issubset (self,set)
+ for k in pairs(self) do
+ if not set[k] then return false end
+ end
+ return true
+end
+
+--- first set subset of second?
+-- @within metamethods
+-- @function Set.__lt
+Set.__lt = Set.issubset
+
+--- is the set empty?.
+-- @param self a Set
+-- @return true or false
+function Set.isempty (self)
+ return next(self) == nil
+end
+
+--- are the sets disjoint? (no elements in common).
+-- Uses naive definition, i.e. that intersection is empty
+-- @param s1 a Set
+-- @param s2 another set
+-- @return true or false
+function Set.isdisjoint (s1,s2)
+ return Set.isempty(Set.intersection(s1,s2))
+end
+
+--- size of this set (also # for 5.2).
+-- @param s a Set
+-- @return size
+-- @function Set.len
+Set.len = tablex.size
+
+--- cardinality of set (5.2).
+-- @within metamethods
+-- @function Set.__len
+Set.__len = Set.len
+
+--- equality between sets.
+-- @within metamethods
+function Set.__eq (s1,s2)
+ return Set.issubset(s1,s2) and Set.issubset(s2,s1)
+end
+
+return Set