-- "Abstract" common base "class" for dynamic sorted sets;
-- serves code and documentation deduplication purposes
local sorted_set = {}
function sorted_set.less_than(a, b)
return a < b
end
-- "Abstract" functions for documentation purposes
--> a sorted set instance containing all `keys` and ordered by `less_than`
--: keys optional list of keys (defaults to `{}`), **must be sorted ascendingly by `less_than`**
--: less_than optional comparator `function(a, b)`, defaults to `sorted_set.less_than`
--$ function sorted_set.new(keys, less_than)
--> whether the sorted set is empty
--$ function sorted_set:empty()
-- Clears (empties) the sorted set
--$ function sorted_set:clear()
-- Copies the sorted set, but does not copy the keys
--$ function sorted_set:copy()
-- Find a key in the sorted set
--> the equal (as per `self.less_than`) key in the set if found
--> `nil` if not found
--$ function sorted_set:find(key)
--> whether `key` is in the sorted set
function sorted_set:has(key)
return self:find(key) ~= nil
end
--> `nil` if `self` is empty
--> the smallest key (per `self.less_than`) otherwise
--$ function sorted_set:min()
--> `nil` if `self` is empty
--> the largest key (per `self.less_than`) otherwise
--$ function sorted_set:max()
--: key optional key
--> `self:min()` if `key == nil`
--> the smallest key in `self` which is larger than `key`
--> `nil` if `self` is empty or `key` is at least `self:max()`
--! Prefer `self:range_ascending` or `self:ascending` over repeatedly calling this for iteration
--$ function sorted_set:succ(key)
--: key optional key
--> `self:max()` if `key == nil`
--> the largest key in `self` which is smaller than `key`
--> `nil` if `self` is empty or `key` is at most `self:min()`
--! Prefer `self:range_descending` or `self:descending` over repeatedly calling this for iteration
--$ function sorted_set:pred(key)
--: from start element, defaults to `self:min()`
--: to end element, defaults to `self:max()`
--> non-restartable iterator over all elements in the inclusive range [from, to] in ascending order
--> non-restartable empty iterator if `to < from`
--$ function sorted_set:range_ascending(from, to)
--: from start element, defaults to `self:min()`
--: to end element, defaults to `self:max()`
--> non-restartable iterator over all elements in the inclusive range [from, to] in descending order
--> non-restartable empty iterator if `to < from`
--$ function sorted_set:range_descending(from, to)
--> non-restartable iterator over all elements in `self` in ascending order
--$ function sorted_set:ascending()
--> non-restartable iterator over all elements in `self` in descending order
--$ function sorted_set:descending()
--: key the key to insert
--: upsert optional, whether to replace an existing key, `false` by default
--> the value of `self:find(key)` before the insertion
--! Do not use this for filling empty sets. Instead, directly build the set from a list.
--$ function sorted_set:insert(key, upsert)
--: key the key to remove
--> the value of `self:find(key)` before the removal
--$ function sorted_set:remove(key)
-- Uses a simple sorted merge
local function setop(
self, -- determines the resulting class
other,
add_self, -- whether to add elements in `self` but not in `other`
add_common, -- whether to add elements common to both sets
add_other -- whether to add elements in `self` but not in `self`
)
assert(self.less_than == other.less_than, "inequal orderings")
local less_than = self.less_than
-- Note: This assumes that the iterators are closures and don't rely on an invariant state / control variable.
local next_self = self:ascending()
local next_other = other:ascending()
local elems = {}
local elem_self, elem_other = next_self(), next_other()
while elem_self ~= nil and elem_other ~= nil do
if less_than(elem_self, elem_other) then
if add_self then
table.insert(elems, elem_self)
end
elem_self = next_self()
elseif less_than(elem_other, elem_self) then
if add_other then
table.insert(elems, elem_other)
end
elem_other = next_other()
else -- equal
if add_common then
table.insert(elems, elem_self)
end
elem_self, elem_other = next_self(), next_other()
end
end
if add_self then
while elem_self ~= nil do
table.insert(elems, elem_self)
elem_self = next_self()
end
end
if add_other then
while elem_other ~= nil do
table.insert(elems, elem_other)
elem_other = next_other()
end
end
return self.new(elems)
end
--> sorted set containing the keys of `self` and `other`; uses the class of `self`
function sorted_set:union(other)
return setop(self, other, true, true, true)
end
--> sorted set containing the keys of `self` and `other`; uses the class of `self`
function sorted_set:difference(other)
return setop(self, other, true, false, false)
end
--> sorted set containing the keys which are exclusively in `self` or `other`
function sorted_set:symmetric_difference(other)
return setop(self, other, true, false, true)
end
--> sorted set containing the keys of `self` which are also in `other`
function sorted_set:intersection(other)
return setop(self, other, false, true, false)
end
return sorted_set