Ordered Set

`loop.collection.OrderedSet`

Class of objects that store a set of values arranged in a particular order. As a usual set, it does not allow duplicates and checks for containment efficiently. The values are stored like a linked list, therefore the sequence can only be iterated in a single direction, i.e. cannot get the previous value. Insertions and removals at any point of the sequence are done efficiently. This class is useful for storing a large set of values without repetitions that are organized in a particular order and accepts frequent insertions and removals at any point of the sequence during iterations.

Stores each value of the set by mapping it to its successor. Therefore, all values are stored as mapped keys. The only exception is the last value that provides no successor. Each instance maps two special values, one to the first value of the sequence and other to the last value. Instances behave like linked lists that does not allow repeated values.

Behavior

Fields

firstkey: userdata: Special value used as the key that maps the first value of the set.

Methods

contains(value): Return true if a value belongs to the set or false otherwise.
empty(): Return true if there is no value inserted in the set or false otherwise.
first(): Returns the first value of the set.
insert(value [, previous]): Inserts value in the set after the value previous. If previous is not provided then value is inserted as the last value of the set. value is returned if successfully inserted. If previous does not belong to the set or value is already inserted then the call has no effect and no value is returned.
last(): Returns the last value of the set.
popfront(): Removes the first value of the set and then returns it. If the set is empty this function has no effect.
previous(value [, start]): Searches for the previous value of value starting from start. If start is not provided the search is done through the entire set. If value is the first value of the set then the special key that holds the first value is returned. If value is found in the set, its previous value is returned, otherwise no value is returned.
pushback(value): Adds value to the end of the set. value is returned if successfully added. If value is already inserted then the call has no effect and no value is returned.
pushfront(value): Adds value to the start of the set. value is returned if successfully added. If value is already inserted then the call has no effect and no value is returned.
remove(value [, start]): Searches for value and removes it from the set starting the search after the value of start. If start is not provided the search is done through the entire set. The removed value is returned or no value is returned if value is not found.
replace(old, new [, start]): Searches for value old and replaces it by value new starting the search after the value of start. If start is not provided the search is done through the entire set. The replaced value is returned or no value is returned if old is not found or if new already belongs to the set.
sequence(): Returns an iterator for use with the for statement of Lua. The for variables receive the current value and the previous value, respectively.

Remarks

Instances cannot store the name of class members as strings. To do so, use the class operations over an empty table like in the following example:

OrderedSet = require "loop.collection.OrderedSet"
set = {}
OrderedSet.insert(set, "first")
OrderedSet.insert(set, "insert")
OrderedSet.insert(set, "last")
OrderedSet.insert(set, "previous")
OrderedSet.insert(set, "sequence")
for word in OrderedSet.sequence(set) do
 io.write(word, " ")
end

This class provides operations of some traditional data structures as aliases of its methods.
Set operations
- add(value) alias for pushback(value)
Stack operations
- push(value) alias for pushfront(value)
- pop() alias for popfront()
- top() alias for first()
Queue operations
- enqueue(value) alias for pushback(value)
- dequeue() alias for popfront()
- head() alias for first()
- tail() alias for last()

Examples

Broad-first and depth-first searches for directed graphs.

local oo = require "loop.base"
local OrderedSet = require "loop.collection.OrderedSet"
local function inbroad(queue, head)
 head = queue[head]
 if head then
 for _, node in ipairs(head) do
 queue:enqueue(node)
 end
 return head
 end end function broadsearch(node)
 queue = OrderedSet()
 queue:enqueue(node)
 return inbroad, queue, OrderedSet.firstkey end local function indepth(stack, top)
 top = stack[top]
 if top then
 for _, node in ipairs(top) do
 stack:insert(node, top)
 end
 return top
 end end function depthsearch(node)
 stack = OrderedSet()
 stack:push(node)
 return indepth, stack, OrderedSet.firstkey end Node = oo.class()
function Node:goesto(...)
 for i=1, select("#", ...) do
 self[#self + 1] = select(i, ...)
 end end A = Node{ name = "A" }
B = Node{ name = "B" }
C = Node{ name = "C" }
D = Node{ name = "D" }
A:goesto(B,C)
B:goesto(D)
C:goesto(D)
D:goesto(A)
io.write("broad-first search:")
for node in broadsearch(A) do
 io.write(" ", node.name)
end print()
io.write("depth-first search:")
for node in depthsearch(A) do
 io.write(" ", node.name)
end print()