Changeset 0e4e43d

Timestamp:

Apr 20, 2025, 9:48:18 AM (5 weeks ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

master

Children:

65b0402

Parents:

0eacfd4

Message:

proofread list API

File:

• doc/theses/mike_brooks_MMath/list.tex (modified) (3 diffs)

doc/theses/mike_brooks_MMath/list.tex

@@ -129 +129 @@
 
 
+\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 <fstream.hfa>
+#include <list.hfa>
+
+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 = &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 +379 @@
 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 +408 @@
 
 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}
+