Index: doc/theses/mike_brooks_MMath/list.tex =================================================================== --- doc/theses/mike_brooks_MMath/list.tex (revision 47402817ce36fb288ba6e57c10f27213a364344c) +++ doc/theses/mike_brooks_MMath/list.tex (revision 0e4e43dc3938ca1279a84c98fd7d8edc4ea9e5d8) @@ -129,7 +129,199 @@ +\section{List API} + + +\begin{cfa} + void insert_after( tE & list_pos, tE & to_insert ) { + void insert_before( tE & list_pos, tE &to_insert ) { + tE & remove( tE & list_pos ) { + tE & ?`first( dlist(tE, tLinks) &lst ) { + tE & ?`last( dlist(tE, tLinks) &lst ) { + bool ?`isEmpty( dlist(tE, tLinks) & lst ) { + bool ?`isListed( tE & e ) { + tE & ?`elems( dlist(tE, tLinks) & lst ) { + tE & ?`head( dlist(tE, tLinks) & lst ) { + bool ?`moveNext( tE && refx ) { + bool ?`next( tE && refx ) { // alternate name + bool ?`movePrev( tE && refx ) { + bool ?`prev( tE && refx ) { // alternate name + bool ?`hasNext( tE & e ) { + bool ?`hasPrev( tE & e ) { + tE & ?`next( tE & e ) { + tE & ?`prev( tE & e ) { + void insert_first( dlist(tE, tLinks) &lst, tE & e ) { + void insert_last( dlist(tE, tLinks) &lst, tE & e ) { + void insert( dlist(tE, tLinks) &lst, tE & e ) { // alternate name + tE & try_pop_front( dlist(tE, tLinks) &lst ) { + tE & try_pop_back( dlist(tE, tLinks) &lst ) { +\end{cfa} + +\begin{itemize} +\item +The member routine @empty@ returns true if the sequence has no nodes and false otherwise. +\item +The member routine head returns a pointer to the head or first node of the sequence without removing it or nullptr if the sequence has no nodes. +\item +The member routine tail returns a pointer to the tail or last node of the sequence without removing it or nullptr if the sequence has no nodes. +\item +The member routine succ returns a pointer to the successor node after the specified node (toward the tail) or nullptr if the specified node is the last node in the sequence. +\item +The member routine pred returns a pointer to the predecessor node before the specified node (toward the head) or nullptr if the specified node is the first node in the sequence. +\item +The member routine insertBef adds a node before the specified node or at the end (tail) if bef is nullptr. +\item +The member routine insertAft adds a node after the specified node or at the beginning (head) if aft is nullptr . +\item +The member routine addHead adds a node to the head or front of the sequence and returns a pointer to the node. +\item +The member routine addTail adds a node to the tail or end of the sequence and returns returns a pointer to the node. +\item +The member routine add is a synonym for addTail. +\item +The member routine dropHead removes a node from the head or front of the sequence and returns a pointer to it or nullptr if the sequence has no nodes. +\item +The member routine drop is a synonym for dropHead. +\item +The member routine dropTail removes a node from the tail or end of the sequence and returns a pointer to it or nullptr if the sequence has no nodes. +\item +The member routine remove removes the specified node from the sequence (any location) and returns a pointer to the node. +\item +The member routine transfer transfers all nodes from the "from" list to the tail or end of the specified sequence; the "from" list is empty after the transfer. +\item +The member routine split transfer the "from" list up to node "n" to the end of the specified sequence; the "from" list becomes the list after node "n". Node "n" must be in the "from" list. +\end{itemize} + \subsection{Iteration} +It is possible to iterate through a list manually or using a set of standard macros. +\VRef[Figure]{f:IteratorExample} shows the iterator template, managing a list of nodes, used throughout the following iterator examples. +Each example assumes its loop body prints the value in the current node. + +The manual method is low level but allows complete control of the iteration. +The list cursor (index) can be either a pointer or a reference to a node in the list. +The choice depends on how the programmer wants to access the fields: @it->f@ or @it.f@. +The following examples use a reference because the loop body manipulates the node values rather than the list pointers. +The end of iteration is denoted by the loop cursor having the null pointer, denoted @0p@ in \CFA. + +\noindent +Iterating forward and reverse through the entire list. +\begin{cquote} +\setlength{\tabcolsep}{15pt} +\begin{tabular}{@{}l|l@{}} +\begin{cfa} +for ( node & it = list`@first@; &it /* != 0p */ ; &it = &it`@next@ ) ... +for ( node & it = list`@last@; ⁢ &it = &it`@prev@ ) ... +\end{cfa} +& +\begin{cfa} +1, 2, 3, 4, +4, 3, 2, 1, +\end{cfa} +\end{tabular} +\end{cquote} +Iterating forward and reverse from a starting node through the remaining list. +\begin{cquote} +\setlength{\tabcolsep}{15pt} +\begin{tabular}{@{}l|l@{}} +\begin{cfa} +for ( node & it = @n2@; ⁢ &it = &it`@next@ ) ... +for ( node & it = @n3@; ⁢ &it = &it`@prev@ ) ... +\end{cfa} +& +\begin{cfa} +2, 3, 4, +3, 2, 1, +\end{cfa} +\end{tabular} +\end{cquote} +Iterating forward and reverse from a starting node to an ending node through the remaining list. +\begin{cquote} +\setlength{\tabcolsep}{15pt} +\begin{tabular}{@{}l|l@{}} +\begin{cfa} +for ( node & it = @n2@; &it @!= &n4@; &it = &it`@next@ ) ... +for ( node & it = @n4@; &it @!= &n2@; &it = &it`@prev@ ) ... +\end{cfa} +& +\begin{cfa} +2, 3, +4, 3, +\end{cfa} +\end{tabular} +\end{cquote} +Iterating forward and reverse through the entire list using the shorthand start at the list head and pick a direction. +In this case, @next@ and @prev@ return a boolean, like \CC @while ( cin >> i )@. +\begin{cquote} +\setlength{\tabcolsep}{15pt} +\begin{tabular}{@{}l|l@{}} +\begin{cfa} +for ( node & it = list`@head@; it`@next@; ) ... +for ( node & it = list`@head@; it`@prev@; ) ... +\end{cfa} +& +\begin{cfa} +1, 2, 3, 4, +4, 3, 2, 1, +\end{cfa} +\end{tabular} +\end{cquote} +Finally, there are convenience macros that look like @foreach@ in other programming languages. +Iterating forward and reverse through the entire list. +\begin{cquote} +\setlength{\tabcolsep}{15pt} +\begin{tabular}{@{}l|l@{}} +\begin{cfa} +FOREACH( list, it ) ... +FOREACH_REV( list, it ) ... +\end{cfa} +& +\begin{cfa} +1, 2, 3, 4, +4, 3, 2, 1, +\end{cfa} +\end{tabular} +\end{cquote} +Iterating forward and reverse through the entire list or until a predicate is triggered. +\begin{cquote} +\setlength{\tabcolsep}{15pt} +\begin{tabular}{@{}l|l@{}} +\begin{cfa} +FOREACH_COND( list, it, @it.v == 3@ ) ... +FOREACH_REV_COND( list, it, @it.v == 1@ ) ... +\end{cfa} +& +\begin{cfa} +1, 2, +4, 3, 2, +\end{cfa} +\end{tabular} +\end{cquote} +The ability to provide a language-level @foreach@ is a future \CFA project. + +\begin{figure} +\begin{cfa} +#include +#include + +struct node { + int v; + inline dlink(node); +}; +int main() { + dlist(node) list; + node n1 = { 1 }, n2 = { 2 }, n3 = { 3 }, n4 = { 4 }; + insert( list, n1 ); insert( list, n2 ); insert( list, n3 ); insert( list, n4 ); + sout | nlOff; + for ( node & it = list`first; ⁢ &it = &it`next ) @sout | it.v | ","; sout | nl;@ + // other iterator examples + remove( n1 ); remove( n2 ); remove( n3 ); remove( n4 ); +} +\end{cfa} +\caption{Iterator Example} +\label{f:IteratorExample} +\end{figure} + +\begin{comment} Many languages offer an iterator interface for collections, and a corresponding for-each loop syntax for consuming the items through implicit interface calls. \CFA does not yet have a general-purpose form of such a feature, though it has a form that addresses some use cases. @@ -187,5 +379,5 @@ by having a list operator @<=@ that just looks for equality, and @+=@ that moves to the next node, \etc. -However, the list usage is contrived, because a list does use its data values for relational comparison, only links for equality comprison. +However, the list usage is contrived, because a list does use its data values for relational comparison, only links for equality comparison. Hence, the focus of a list iterator's stopping condition is fundamentally different. So, iteration of a linked list via the existing loop syntax is to ask whether this syntax can also do double-duty for iterating values. @@ -216,4 +408,6 @@ TODO: deal with spontaneous simultaneity, like a single-axis req, put into an array: which ``axis'' is @&req++@ navigating: array-adjacency vs link dereference. It should sick according to how you got it in the first place: navigating dlist(req, req.pri) vs navigating array(req, 42). (prob. future work) +\end{comment} +