Changeset 9d9fd81

Timestamp:

Apr 20, 2025, 8:28:47 PM (5 months ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

master

Children:

691a4b7

Parents:

65b0402

Message:

more proofreading of list API

File:

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

doc/theses/mike_brooks_MMath/list.tex

@@ -131 +131 @@
 \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.
+\VRef[Figure]{f:ListAPI} shows the API for the doubly-link list operations, where each is explained.
+\begin{itemize}[leftmargin=*]
+\item
+@isListed@ returns true if the node is an element of a list and false otherwise.
+\item
+@isEmpty@ returns true if the list has no nodes and false otherwise.
+\item
+@first@ returns a pointer to the first node of the list without removing it or @0p@ if the list is empty.
+\item
+@last@ returns a pointer to the last node of the list without removing it or @0p@ if the list is empty.
+\item
+@next@ returns a pointer to the next (successor, towards last) node after the specified node or @0p@ if the specified node is the last node in the list.
+\item
+@pred@ returns a pointer to the previous (predecessor, towards first) node before the specified node or @0p@ if the specified node is the first node in the list.
+\item
+@insert_before@ adds a node before the specified node and returns the added node for cascading.
+\item
+@insert_after@ adds a node after the specified node and returns the added node for cascading.
+\item
+@remove@ removes the specified node from the list (any location) and returns a pointer to the node.
+\item
+@insert_first@ adds a node to the start of the list so it becomes the first node and returns a pointer to the node for cascading.
+\item
+@insert_last@ adds a node to the end of the list so it becomes the last node and returns returns a pointer to the node for cascading.
+\item
+@insert@ is a synonym for @insert_last@.
+\item
+@remove_first@ removes the first node and returns a pointer to it or @0p@ if the list is empty.
+\item
+@remove_last@ removes the last node and returns a pointer to it or @0p@ if the list is emptyy.
+\item
+@transfer@ transfers all nodes from the @from@ list to the end of the @to@ list; the @from@ list is empty after the transfer.
+\item
+@split@ transfers the @from@ list up to node to the end of the @to@ list; the @from@ list becomes the list after the node.
+The node must be in the @from@ list.
 \end{itemize}
+
+\begin{figure}
+\begin{cfa}
+E & ?`isEmpty( dlist( E ) & list );
+E & ?`isListed( E & node );
+E & ?`first( dlist( E ) & list );
+E & ?`last( dlist( E ) & list );
+E & ?`next( E & node );
+E & ?`prev( E & node );
+E & insert_before( E & before, E & node );
+E & insert_after( E & after, E & node );
+E & remove( E & node );
+E & ?`elems( dlist( E ) & list );
+E & ?`head( dlist( E ) & list );
+bool ?`moveNext( E && refx );
+bool ?`next( E && refx );                                                       // alternate name
+bool ?`movePrev( E && refx );
+bool ?`prev( E && refx );                                                       // alternate name
+bool ?`hasNext( E & node );
+bool ?`hasPrev( E & node );
+E & insert_first( dlist( E ) & list, E & node );
+E & insert_last( dlist( E ) & list, E & node );
+E & insert( dlist( E ) & list, E & node );              // alternate name
+E & remove_first( dlist( E ) & list );
+E & remove_last( dlist( E ) & list );
+void transfer( dlist( E ) & to, dlist( E ) & from ) {
+void split( dlist( E ) & to, dlist( E ) & from, E & node ) {
+E & try_pop_front( dlist( E ) & list );
+E & try_pop_back( dlist( E ) & list );
+\end{cfa}
+\caption{\CFA List API}
+\label{f:ListAPI}
+\end{figure}
 
 
@@ -198 +207 @@
 \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}
@@ -322 +230 @@
 \label{f:IteratorExample}
 \end{figure}
+
+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.
+Finally, a predicate can be added to any of the manual iteration loops.
+\begin{cquote}
+\setlength{\tabcolsep}{15pt}
+\begin{tabular}{@{}l|l@{}}
+\begin{cfa}
+for ( node & it = list`first; &it @&& !(it.v == 3)@; &it = &it`next ) ...
+for ( node & it = list`last; &it @&& !(it.v == 1)@; &it = &it`prev ) ...
+for ( node & it = list`head; it`next @&& !(it.v == 3)@; ) ...
+for ( node & it = list`head; it`prev @&& !(it.v == 1)@; ) ...
+\end{cfa}
+&
+\begin{cfa}
+1, 2,
+4, 3, 2,
+1, 2,
+4, 3, 2,
+\end{cfa}
+\end{tabular}
+\end{cquote}
 
 \begin{comment}