Lua library module "list"
Author: Hans van der Meer
The Lua modules arraylist and linkedlist are C-modules for the
manipulation of lists. Both have the same API, but in the underlying
implementation they differ fundamentally.
In the array implementation of arraylist access to the elements can be
accomplished very efficiently, as well as adding nodes at the end. But
insertion and removal of nodes can be costly, because the nodes above the
insertion or deletion point must all be moved up or down, respectively.
The doubly linked implementation of the linkedlist excels where the arraylist
has difficulties. Insertion and deletion can be effected more efficiently,
but finding the nodes to be accessed is not a one step process as with the
arraylist.
Their strong points and weaknesses complement each other more or less.
The choice between the one or the other is therefore dictated by the needs
of the program at hand.
Both share the same API, making substitution of the one for the other a
simple matter.
API
Remarks
-
Functions that return the list allow chaining of operations.
-
An index out of range or nil forces an error.
-
Negative index values are count backwards, -1 denoting the last entry.
-
The value nil is not allowed as contents of the list and will be ignored.
-
Sorted lists maintain their sort order through all additions.
Create list
list.new() |
return empty list |
list.new(name) |
optional name (string) |
list.new(capacity) |
initial capacity (positive number) |
list.new(compare) |
compare (function) |
list.new(-1) |
reverse default compare |
list.new(true) |
sorted list |
new and create are synonyms
|
The function compare(elt1, elt2) shall return integer values +1, 0
or -1 for in-order, equal and out-order results, respectively. A
return of +1 has the meaning that the values are out of order with
respect to sorting. The parameters elt1, elt2 are the two elements
to compare. If compare is not given the elements are by default
compared arithmetically. In that case an error is raised if they are
not numbers. Value true for the direction parameter choose ascending
compare results for the default compare, false selects descending.
The (name, capacity, compare, -1, true) parameters can be given in
any order and in any combination. Other parameter values or types are
acceptable, but will be silently ignored.
Add element
|
unsorted |
sorted |
l:add(value) |
add at end |
insert in order |
l:insert(value) |
insert at front |
insert in order |
l:insert(value, index) |
insert at index |
insert in order |
| all return the list |
Tables are allowed as input value and are fully expanded to include
their values.
Remove element
l:delete() |
make list empty |
l:delete(index) |
remove element at index |
| all return the list,
delete and remove are synonyms
|
Get element value
l:get(index [,index [...]]) |
return values at index |
l:get() |
return table of all values |
Requesting all values returns them in a table, because their number might
be so large as to exhaust the capacity of the return stack.
Get element iterator
l:iterator() |
return forward iterator |
l:iterator(-1) |
return reverse iterator |
Do not alter the contents of the list (add, insert, remove) while there are
active iterators: the results are unpredictable or even disastrous.
Find element
l:find(value) |
return index of value or nil |
l:find(value, index) |
start at given index |
Order of elements
l:compare(elt1, elt2) |
return result of compare |
As stated above, the compare function returns +1 for an in order result,
0 for equality and -1 for out of order compare result.
If sorted collections must be extracted, it is best to create the list
as a sorted one and extract all values in a table. Otherwise one has to
sort the extracted values oneself.
Query state
l:empty() |
true/false for list empty/not empty |
l:size(), #l |
list size |
l:sorted() |
return true if sorted list |
l:ident() |
identity stamp, name or nil |
list.version() |
version of the module |