Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/mike_brooks_MMath/list.tex

    r65b0402 r9d9fd81  
    131131\section{List API}
    132132
    133 
    134 \begin{cfa}
    135         void insert_after( tE & list_pos, tE & to_insert ) {
    136         void insert_before( tE & list_pos, tE &to_insert ) {
    137         tE & remove( tE & list_pos ) {
    138         tE & ?`first( dlist(tE, tLinks) &lst ) {
    139         tE & ?`last( dlist(tE, tLinks) &lst ) {
    140         bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
    141         bool ?`isListed( tE & e ) {
    142         tE & ?`elems( dlist(tE, tLinks) & lst ) {
    143         tE & ?`head( dlist(tE, tLinks) & lst ) {
    144         bool ?`moveNext( tE && refx ) {
    145         bool ?`next( tE && refx ) {                                                     // alternate name
    146         bool ?`movePrev( tE && refx ) {
    147         bool ?`prev( tE && refx ) {                                                     // alternate name
    148         bool ?`hasNext( tE & e ) {
    149         bool ?`hasPrev( tE & e ) {
    150         tE & ?`next( tE & e ) {
    151         tE & ?`prev( tE & e ) {
    152         void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
    153         void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
    154         void insert( dlist(tE, tLinks) &lst, tE & e ) {         // alternate name
    155         tE & try_pop_front( dlist(tE, tLinks) &lst ) {
    156         tE & try_pop_back( dlist(tE, tLinks) &lst ) {
    157 \end{cfa}
    158 
    159 \begin{itemize}
    160 \item
    161 The member routine @empty@ returns true if the sequence has no nodes and false otherwise.
    162 \item
    163 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.
    164 \item
    165 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.
    166 \item
    167 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.
    168 \item
    169 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.
    170 \item
    171 The member routine insertBef adds a node before the specified node or at the end (tail) if bef is nullptr.
    172 \item
    173 The member routine insertAft adds a node after the specified node or at the beginning (head) if aft is nullptr .
    174 \item
    175 The member routine addHead adds a node to the head or front of the sequence and returns a pointer to the node.
    176 \item
    177 The member routine addTail adds a node to the tail or end of the sequence and returns returns a pointer to the node.
    178 \item
    179 The member routine add is a synonym for addTail.
    180 \item
    181 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.
    182 \item
    183 The member routine drop is a synonym for dropHead.
    184 \item
    185 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.
    186 \item
    187 The member routine remove removes the specified node from the sequence (any location) and returns a pointer to the node.
    188 \item
    189 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.
    190 \item
    191 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.
     133\VRef[Figure]{f:ListAPI} shows the API for the doubly-link list operations, where each is explained.
     134\begin{itemize}[leftmargin=*]
     135\item
     136@isListed@ returns true if the node is an element of a list and false otherwise.
     137\item
     138@isEmpty@ returns true if the list has no nodes and false otherwise.
     139\item
     140@first@ returns a pointer to the first node of the list without removing it or @0p@ if the list is empty.
     141\item
     142@last@ returns a pointer to the last node of the list without removing it or @0p@ if the list is empty.
     143\item
     144@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.
     145\item
     146@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.
     147\item
     148@insert_before@ adds a node before the specified node and returns the added node for cascading.
     149\item
     150@insert_after@ adds a node after the specified node and returns the added node for cascading.
     151\item
     152@remove@ removes the specified node from the list (any location) and returns a pointer to the node.
     153\item
     154@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.
     155\item
     156@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.
     157\item
     158@insert@ is a synonym for @insert_last@.
     159\item
     160@remove_first@ removes the first node and returns a pointer to it or @0p@ if the list is empty.
     161\item
     162@remove_last@ removes the last node and returns a pointer to it or @0p@ if the list is emptyy.
     163\item
     164@transfer@ transfers all nodes from the @from@ list to the end of the @to@ list; the @from@ list is empty after the transfer.
     165\item
     166@split@ transfers the @from@ list up to node to the end of the @to@ list; the @from@ list becomes the list after the node.
     167The node must be in the @from@ list.
    192168\end{itemize}
     169
     170\begin{figure}
     171\begin{cfa}
     172E & ?`isEmpty( dlist( E ) & list );
     173E & ?`isListed( E & node );
     174E & ?`first( dlist( E ) & list );
     175E & ?`last( dlist( E ) & list );
     176E & ?`next( E & node );
     177E & ?`prev( E & node );
     178E & insert_before( E & before, E & node );
     179E & insert_after( E & after, E & node );
     180E & remove( E & node );
     181E & ?`elems( dlist( E ) & list );
     182E & ?`head( dlist( E ) & list );
     183bool ?`moveNext( E && refx );
     184bool ?`next( E && refx );                                                       // alternate name
     185bool ?`movePrev( E && refx );
     186bool ?`prev( E && refx );                                                       // alternate name
     187bool ?`hasNext( E & node );
     188bool ?`hasPrev( E & node );
     189E & insert_first( dlist( E ) & list, E & node );
     190E & insert_last( dlist( E ) & list, E & node );
     191E & insert( dlist( E ) & list, E & node );              // alternate name
     192E & remove_first( dlist( E ) & list );
     193E & remove_last( dlist( E ) & list );
     194void transfer( dlist( E ) & to, dlist( E ) & from ) {
     195void split( dlist( E ) & to, dlist( E ) & from, E & node ) {
     196E & try_pop_front( dlist( E ) & list );
     197E & try_pop_back( dlist( E ) & list );
     198\end{cfa}
     199\caption{\CFA List API}
     200\label{f:ListAPI}
     201\end{figure}
    193202
    194203
     
    198207\VRef[Figure]{f:IteratorExample} shows the iterator template, managing a list of nodes, used throughout the following iterator examples.
    199208Each example assumes its loop body prints the value in the current node.
    200 
    201 The manual method is low level but allows complete control of the iteration.
    202 The list cursor (index) can be either a pointer or a reference to a node in the list.
    203 The choice depends on how the programmer wants to access the fields: @it->f@ or @it.f@.
    204 The following examples use a reference because the loop body manipulates the node values rather than the list pointers.
    205 The end of iteration is denoted by the loop cursor having the null pointer, denoted @0p@ in \CFA.
    206 
    207 \noindent
    208 Iterating forward and reverse through the entire list.
    209 \begin{cquote}
    210 \setlength{\tabcolsep}{15pt}
    211 \begin{tabular}{@{}l|l@{}}
    212 \begin{cfa}
    213 for ( node & it = list`@first@; &it /* != 0p */ ; &it = &it`@next@ ) ...
    214 for ( node & it = list`@last@; &it; &it = &it`@prev@ ) ...
    215 \end{cfa}
    216 &
    217 \begin{cfa}
    218 1, 2, 3, 4,
    219 4, 3, 2, 1,
    220 \end{cfa}
    221 \end{tabular}
    222 \end{cquote}
    223 Iterating forward and reverse from a starting node through the remaining list.
    224 \begin{cquote}
    225 \setlength{\tabcolsep}{15pt}
    226 \begin{tabular}{@{}l|l@{}}
    227 \begin{cfa}
    228 for ( node & it = @n2@; &it; &it = &it`@next@ ) ...
    229 for ( node & it = @n3@; &it; &it = &it`@prev@ ) ...
    230 \end{cfa}
    231 &
    232 \begin{cfa}
    233 2, 3, 4,
    234 3, 2, 1,
    235 \end{cfa}
    236 \end{tabular}
    237 \end{cquote}
    238 Iterating forward and reverse from a starting node to an ending node through the remaining list.
    239 \begin{cquote}
    240 \setlength{\tabcolsep}{15pt}
    241 \begin{tabular}{@{}l|l@{}}
    242 \begin{cfa}
    243 for ( node & it = @n2@; &it @!= &n4@; &it = &it`@next@ ) ...
    244 for ( node & it = @n4@; &it @!= &n2@; &it = &it`@prev@ ) ...
    245 \end{cfa}
    246 &
    247 \begin{cfa}
    248 2, 3,
    249 4, 3,
    250 \end{cfa}
    251 \end{tabular}
    252 \end{cquote}
    253 Iterating forward and reverse through the entire list using the shorthand start at the list head and pick a direction.
    254 In this case, @next@ and @prev@ return a boolean, like \CC @while ( cin >> i )@.
    255 \begin{cquote}
    256 \setlength{\tabcolsep}{15pt}
    257 \begin{tabular}{@{}l|l@{}}
    258 \begin{cfa}
    259 for ( node & it = list`@head@; it`@next@; ) ...
    260 for ( node & it = list`@head@; it`@prev@; ) ...
    261 \end{cfa}
    262 &
    263 \begin{cfa}
    264 1, 2, 3, 4,
    265 4, 3, 2, 1,
    266 \end{cfa}
    267 \end{tabular}
    268 \end{cquote}
    269 Finally, there are convenience macros that look like @foreach@ in other programming languages.
    270 Iterating forward and reverse through the entire list.
    271 \begin{cquote}
    272 \setlength{\tabcolsep}{15pt}
    273 \begin{tabular}{@{}l|l@{}}
    274 \begin{cfa}
    275 FOREACH( list, it ) ...
    276 FOREACH_REV( list, it ) ...
    277 \end{cfa}
    278 &
    279 \begin{cfa}
    280 1, 2, 3, 4,
    281 4, 3, 2, 1,
    282 \end{cfa}
    283 \end{tabular}
    284 \end{cquote}
    285 Iterating forward and reverse through the entire list or until a predicate is triggered.
    286 \begin{cquote}
    287 \setlength{\tabcolsep}{15pt}
    288 \begin{tabular}{@{}l|l@{}}
    289 \begin{cfa}
    290 FOREACH_COND( list, it, @it.v == 3@ ) ...
    291 FOREACH_REV_COND( list, it, @it.v == 1@ ) ...
    292 \end{cfa}
    293 &
    294 \begin{cfa}
    295 1, 2,
    296 4, 3, 2,
    297 \end{cfa}
    298 \end{tabular}
    299 \end{cquote}
    300 The ability to provide a language-level @foreach@ is a future \CFA project.
    301209
    302210\begin{figure}
     
    322230\label{f:IteratorExample}
    323231\end{figure}
     232
     233The manual method is low level but allows complete control of the iteration.
     234The list cursor (index) can be either a pointer or a reference to a node in the list.
     235The choice depends on how the programmer wants to access the fields: @it->f@ or @it.f@.
     236The following examples use a reference because the loop body manipulates the node values rather than the list pointers.
     237The end of iteration is denoted by the loop cursor having the null pointer, denoted @0p@ in \CFA.
     238
     239\noindent
     240Iterating forward and reverse through the entire list.
     241\begin{cquote}
     242\setlength{\tabcolsep}{15pt}
     243\begin{tabular}{@{}l|l@{}}
     244\begin{cfa}
     245for ( node & it = list`@first@; &it /* != 0p */ ; &it = &it`@next@ ) ...
     246for ( node & it = list`@last@; &it; &it = &it`@prev@ ) ...
     247\end{cfa}
     248&
     249\begin{cfa}
     2501, 2, 3, 4,
     2514, 3, 2, 1,
     252\end{cfa}
     253\end{tabular}
     254\end{cquote}
     255Iterating forward and reverse from a starting node through the remaining list.
     256\begin{cquote}
     257\setlength{\tabcolsep}{15pt}
     258\begin{tabular}{@{}l|l@{}}
     259\begin{cfa}
     260for ( node & it = @n2@; &it; &it = &it`@next@ ) ...
     261for ( node & it = @n3@; &it; &it = &it`@prev@ ) ...
     262\end{cfa}
     263&
     264\begin{cfa}
     2652, 3, 4,
     2663, 2, 1,
     267\end{cfa}
     268\end{tabular}
     269\end{cquote}
     270Iterating forward and reverse from a starting node to an ending node through the remaining list.
     271\begin{cquote}
     272\setlength{\tabcolsep}{15pt}
     273\begin{tabular}{@{}l|l@{}}
     274\begin{cfa}
     275for ( node & it = @n2@; &it @!= &n4@; &it = &it`@next@ ) ...
     276for ( node & it = @n4@; &it @!= &n2@; &it = &it`@prev@ ) ...
     277\end{cfa}
     278&
     279\begin{cfa}
     2802, 3,
     2814, 3,
     282\end{cfa}
     283\end{tabular}
     284\end{cquote}
     285Iterating forward and reverse through the entire list using the shorthand start at the list head and pick a direction.
     286In this case, @next@ and @prev@ return a boolean, like \CC @while ( cin >> i )@.
     287\begin{cquote}
     288\setlength{\tabcolsep}{15pt}
     289\begin{tabular}{@{}l|l@{}}
     290\begin{cfa}
     291for ( node & it = list`@head@; it`@next@; ) ...
     292for ( node & it = list`@head@; it`@prev@; ) ...
     293\end{cfa}
     294&
     295\begin{cfa}
     2961, 2, 3, 4,
     2974, 3, 2, 1,
     298\end{cfa}
     299\end{tabular}
     300\end{cquote}
     301Finally, there are convenience macros that look like @foreach@ in other programming languages.
     302Iterating forward and reverse through the entire list.
     303\begin{cquote}
     304\setlength{\tabcolsep}{15pt}
     305\begin{tabular}{@{}l|l@{}}
     306\begin{cfa}
     307FOREACH( list, it ) ...
     308FOREACH_REV( list, it ) ...
     309\end{cfa}
     310&
     311\begin{cfa}
     3121, 2, 3, 4,
     3134, 3, 2, 1,
     314\end{cfa}
     315\end{tabular}
     316\end{cquote}
     317Iterating forward and reverse through the entire list or until a predicate is triggered.
     318\begin{cquote}
     319\setlength{\tabcolsep}{15pt}
     320\begin{tabular}{@{}l|l@{}}
     321\begin{cfa}
     322FOREACH_COND( list, it, @it.v == 3@ ) ...
     323FOREACH_REV_COND( list, it, @it.v == 1@ ) ...
     324\end{cfa}
     325&
     326\begin{cfa}
     3271, 2,
     3284, 3, 2,
     329\end{cfa}
     330\end{tabular}
     331\end{cquote}
     332The ability to provide a language-level @foreach@ is a future \CFA project.
     333Finally, a predicate can be added to any of the manual iteration loops.
     334\begin{cquote}
     335\setlength{\tabcolsep}{15pt}
     336\begin{tabular}{@{}l|l@{}}
     337\begin{cfa}
     338for ( node & it = list`first; &it @&& !(it.v == 3)@; &it = &it`next ) ...
     339for ( node & it = list`last; &it @&& !(it.v == 1)@; &it = &it`prev ) ...
     340for ( node & it = list`head; it`next @&& !(it.v == 3)@; ) ...
     341for ( node & it = list`head; it`prev @&& !(it.v == 1)@; ) ...
     342\end{cfa}
     343&
     344\begin{cfa}
     3451, 2,
     3464, 3, 2,
     3471, 2,
     3484, 3, 2,
     349\end{cfa}
     350\end{tabular}
     351\end{cquote}
    324352
    325353\begin{comment}
Note: See TracChangeset for help on using the changeset viewer.