Index: doc/theses/mike_brooks_MMath/list.tex =================================================================== --- doc/theses/mike_brooks_MMath/list.tex (revision 65b0402655546e1fea596afe650e9a1b34129bd8) +++ doc/theses/mike_brooks_MMath/list.tex (revision 9d9fd819a2c497a3cd2037e48f9c2112d0d4e0e5) @@ -131,64 +131,73 @@ \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,105 +207,4 @@ \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,4 +230,124 @@ \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}