Multi-level List MLIST

Added October 2016

DIMX $M, MLIST(VARSTR)

DIMX $M, MLIST(VARX)

MLIST, short for "Multi-level LIST," is a bidirectional linked list, with the added feature that each element may contain a link to a child MLIST. Aside from the links, each element may contain a variable length string (varstr) or blob (varx). The MLIST is effectively a kind of tree structure, useful for representing a variety of real-world data such as disk directories and XML/JSON documents, where the ability to maintain a particular order and to efficiently insert, delete, and splice elements or branches at arbitrary points is required.

Unlike the ORDMAP and ORDMAPM collections, there is no direct access to an element by its key; there is only direct access to the first and last elements in the list, with the ability to iterate forwards, backwards, or down from there. The order of the elements in the list is preserved based on the order in which you build it.

The syntax for assigning and accessing elements is similar to that for ORDMAP, modeled on single-dimension array syntax. But instead of using string keys for the array index as in ORDMAP, the MLIST uses various special dot-variables which act as pseudo-keys. In addition, there are several new dot-statements and dot-functions and dot-members to perform operations particular to MLISTs that cannot be easily represented with existing statements and functions. These are summarized below, following by descriptions and syntax for the various operations..

Dot-Variable	Description
.FRONT	First element, e.g. ? $M(.FRONT).
.BACK	Last element, e.g. ? M(.BACK).
.NULL	May be assigned to an element to delete any attached sublist.
.PUSHFRONT	Add new element to front, e.g. $M(.PUSHFRONT) = X.
.PUSHBACK	Add new element to end, e.g. $M(.PUSHBACK) = X.
Dot-Statement	Description
.POPFRONT	Remove first element from list, e.g. .POPFRONT $M().
.POPBACK	Remove last element from list, e.g. .POPBACK $M().
.SPLICE	Splice elements from one list to other.
.SORT	Sort elements in list by value, e.g. .SORT $M() .SORT $kids() sorts according to the collating sequence, just as the ordered map does.
Dot-Function	Description
.BEFORE($$i)	Specify insertion position, e.g $M(.BEFORE($$i)) = X.
.EXTENT($mlist)	Return number of top-level elements in specified list.
.REF($$i)	Return a reference to iterator location, used when modifying an element by iterator, e.g. $M(.REF($$i)) = X.
Dot-Member	Description
.SUBLIST	Specify sublist of element, e.g. $$i.SUBLIST, or $M(.BACK).SUBLIST
.KEY	$$i.KEY is equivalent to .KEY($$i)

All of the following descriptions and examples will assume the prior definition of these two MLISTs:

dimx $m, MLIST(varstr)

dimx $m2, MLIST(varstr)