Changes in / [b19fdb9:ee56a4f]


Ignore:
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • libcfa/src/bits/queue.hfa

    rb19fdb9 ree56a4f  
    3434                } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q
    3535
    36                 void addHead( Queue(T) & q, T & n ) with( q ) {
     36                T & addHead( Queue(T) & q, T & n ) with( q ) {
    3737                        #ifdef __CFA_DEBUG__
    3838                        if ( listed( &n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, &n );
     
    4545                                Next( &n ) = &n;                                                // last node points to itself
    4646                        }
     47                        return n;
    4748                }
    4849
    49                 void addTail( Queue(T) & q, T & n ) with( q ) {
     50                T & addTail( Queue(T) & q, T & n ) with( q ) {
    5051                        #ifdef __CFA_DEBUG__
    5152                        if ( listed( &n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, &n );
     
    5556                        last = &n;
    5657                        Next( &n ) = &n;                                                        // last node points to itself
     58                        return n;
    5759                }
    5860
    59                 void add( Queue(T) & q, T & n ) with( q ) {
    60                         addTail( q, n );
     61                T & add( Queue(T) & q, T & n ) with( q ) {
     62                        return addTail( q, n );
    6163                }
    6264
     
    7779                }
    7880
    79                 void remove( Queue(T) & q, T & n ) with( q ) {  // O(n)
     81                T & remove( Queue(T) & q, T & n ) with( q ) {   // O(n)
    8082                        #ifdef __CFA_DEBUG__
    8183                        if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, &n );
     
    103105                                curr = Next( curr );
    104106                        }
     107                        return n;
    105108                } // post: ! listed( n )
    106109
  • libcfa/src/bits/sequence.hfa

    rb19fdb9 ree56a4f  
    7777
    7878                // Insert *n into the sequence before *bef, or at the end if bef == 0.
    79                 void insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s
     79                T & insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s
    8080                        #ifdef __CFA_DEBUG__
    8181                        if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef );
     
    105105                                Next( Back( &n ) ) = &n;
    106106                        } // if
     107                        return n;
    107108                }       // post: n->listed() & *n in *s & succ(n) == bef
    108109
    109110
    110111                // Insert *n into the sequence after *aft, or at the beginning if aft == 0.
    111                 void insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) {   // pre: !n->listed() & *aft in *s
     112                T & insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) {    // pre: !n->listed() & *aft in *s
    112113                        #ifdef __CFA_DEBUG__
    113114                        if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n );
     
    135136                                Next( &aft ) = &n;
    136137                        } // if
     138                        return n;
    137139                }         // post: n->listed() & *n in *s & succ(n) == bef
    138140               
    139141                // pre: n->listed() & *n in *s
    140                 void remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
     142                T & remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
    141143                        #ifdef __CFA_DEBUG__
    142144                        if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n );
     
    149151                        Next( Back( &n ) ) = Next( &n );
    150152                        Next( &n ) = Back( &n ) = 0p;
     153                        return n;
    151154                }                                                       // post: !n->listed().
    152155
    153156                // Add an element to the head of the sequence.
    154                 void addHead( Sequence(T) & s, T & n ) {                // pre: !n->listed(); post: n->listed() & head() == n
    155                         insertAft( s, *0p, n );
     157                T & addHead( Sequence(T) & s, T & n ) {                 // pre: !n->listed(); post: n->listed() & head() == n
     158                        return insertAft( s, *0p, n );
    156159                }
    157160                // Add an element to the tail of the sequence.
    158                 void addTail( Sequence(T) & s, T & n ) {                // pre: !n->listed(); post: n->listed() & head() == n
    159                         insertBef( s, n, *0p );
     161                T & addTail( Sequence(T) & s, T & n ) {                 // pre: !n->listed(); post: n->listed() & head() == n
     162                        return insertBef( s, n, *0p );
    160163                }
    161164                // Add an element to the tail of the sequence.
    162                 void add( Sequence(T) & s, T & n ) {                    // pre: !n->listed(); post: n->listed() & head() == n
    163                         addTail( s, n );
     165                T & add( Sequence(T) & s, T & n ) {                             // pre: !n->listed(); post: n->listed() & head() == n
     166                        return addTail( s, n );
    164167                }
    165168                // Remove and return the head element in the sequence.
  • libcfa/src/bits/stack.hfa

    rb19fdb9 ree56a4f  
    2525                }
    2626
    27                 void addHead( Stack(T) & s, T & n ) with( s ) {
     27                T & addHead( Stack(T) & s, T & n ) with( s ) {
    2828                        #ifdef __CFA_DEBUG__
    2929                        if ( listed( (Colable &)(n) ) ) abort( "(Stack &)%p.addHead( %p ) : Node is already on another list.", &s, n );
     
    3131                        Next( &n ) = &head( s ) ? &head( s ) : &n;
    3232                        root = &n;
     33                        return n;
    3334                }
    3435
    35                 void add( Stack(T) & s, T & n ) with( s ) {
    36                         addHead( s, n );
     36                T & add( Stack(T) & s, T & n ) with( s ) {
     37                        return addHead( s, n );
    3738                }
    3839
    39                 void push( Stack(T) & s, T & n ) with( s ) {
    40                         addHead( s, n );
     40                T & push( Stack(T) & s, T & n ) with( s ) {
     41                        return addHead( s, n );
    4142                }
    4243
  • tests/collections/.expect/queue.txt

    rb19fdb9 ree56a4f  
    11empty
    2 0
    3 18
     20 18
    430 2 4 6 8 10 12 14 16 18
    5418
    6 18
     5-1 18 -2
     6-1 18 1 3 5 7 9 11 13 15 17 19 -2
    7718 1 3 5 7 9 11 13 15 17
     818 1 3 5 7
     9empty
    8100 1 2 3 4 5 6 7 8 9
    9 6 7 8 9
    10 0 1 2 3 4 5
    11 6 7 8 9 0 1 2 3 4 5
     115 6 7 8 9
     120 1 2 3 4
     135 6 7 8 9 0 1 2 3 4
    1214empty
     150 18
    13160 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18
    141718 18
    15 18 18 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19
     18-1 18 -1
     1918 18 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17
     200 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
     215 5 6 6 7 7 8 8 9 9
     220 0 1 1 2 2 3 3 4 4
     235 5 6 6 7 7 8 8 9 9 0 0 1 1 2 2 3 3 4 4
  • tests/collections/.expect/sequence.txt

    rb19fdb9 ree56a4f  
    11empty
     20 18
    230 2 4 6 8 10 12 14 16 18
    3418
    4 18 1 3 5 7 9 11 13 15 17 19
    5 18 1
     5-1 18 -2
     6-1 18 1 3 5 7 9 11 13 15 17 19 -2
     718 1 3 5 7 9 11 13 15 17
     818 1 3 5 7
     9empty
    6100 1 2 3 4 5 6 7 8 9
    7 9
    8 9 8 7 6 5 4 3 1 -2 0
    9 4 3 1 -2 0
     11-1 -2 0
     12-1 -2 9 8 7 6 5 4 3 2 1 0
     139 8 7 6 5 4 3 2 1
     144 3 2 1
    10159 8 7 6 5
    11 4 3 1 -2 0 9 8 7 6 5
     164 3 2 1 9 8 7 6 5
    1217empty
     180 18
    13190 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18
    142018 18
    15 18 18 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19
    16 18 18 1 1
    17 empty
    18 18 18 1 1 0 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18
     21-1 18 -1
     2218 18 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17
     230 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
     245 5 6 6 7 7 8 8 9 9
     250 0 1 1 2 2 3 3 4 4
     265 5 6 6 7 7 8 8 9 9 0 0 1 1 2 2 3 3 4 4
  • tests/collections/queue.cfa

    rb19fdb9 ree56a4f  
    3333        }
    3434
    35         sout | head(fred).i | nl;
    36         sout | tail(fred).i | nl;
     35        sout | head( fred ).i | tail( fred ).i | nl;
    3736
    3837        for ( QueueIter(Fred) iter = { fred }; iter >> f; ) {
     
    5453        }
    5554
    56         Fred * front = new( -1 );
    57         addHead( fred, *front );
    58         sout | succ( fred, front )->i | nl;
    59         remove( fred, *front );
    60         delete( front );
    61 
    62         Fred & end = dropTail( fred );
    63         delete( &end );
    64 
    65         for ( over( fredIter, fred ); fredIter >> f; ) {
    66                 sout | f.i | ' ';
    67         }
    68         sout | nl;
    69 
    70         for ( over( fredIter, fred ); fredIter >> f; ) {
    71                 delete( &f );
    72         }
    73 
    74         Queue(Fred) fred0;
    75         Fred * middle;
    76         for ( i; 10 ) {
    77                 if( i == 5) {
    78                         middle = new( i );
    79                         add( fred0, *middle );
    80                         continue;
     55        Fred * head = new( -1 ), tail = { -2 };
     56        addHead( fred, *head );
     57        addTail( fred, tail );
     58
     59        sout | head( fred ).i | succ( fred, head )->i | tail( fred ).i | nl;
     60        for ( over( fredIter, fred ); fredIter >> f; ) {
     61                sout | f.i | ' ';
     62        }
     63        sout | nl;
     64
     65        remove( fred, *head );
     66        remove( fred, tail );
     67        delete( head );
     68        delete( &dropTail( fred ) );
     69
     70        for ( over( fredIter, fred ); fredIter >> f; ) {
     71                sout | f.i | ' ';
     72        }
     73        sout | nl;
     74
     75        for ( i; 5 ) {
     76                delete( &dropTail( fred ) );
     77        }
     78        for ( over( fredIter, fred ); fredIter >> f; ) {
     79                sout | f.i | ' ';
     80        }
     81        sout | nl;
     82
     83        for ( over( fredIter, fred ); fredIter >> f; ) {
     84                delete( &remove( fred, f ) );
     85        }
     86        for ( over( fredIter, fred ); fredIter >> f; ) {
     87                sout | f.i | ' ';
     88        }
     89        sout | "empty" | nl;
     90
     91        Fred & middle;
     92        for ( i; 10 ) {
     93                add( fred, *new( i ) );
     94                if ( i == 4 ) {
     95                        &middle = &tail( fred );
    8196                }
    82                 add( fred0, *new( i ) );
    83         }
    84 
    85         for ( QueueIter(Fred) iter = { fred0 }; iter >> f; ) {
     97        }
     98        for ( QueueIter(Fred) iter = { fred }; iter >> f; ) {
    8699                sout | f.i | ' ';
    87100        }
     
    90103        Queue(Fred) fred2;
    91104
    92         split( fred2, fred0, *middle);
    93 
    94         for ( over( fredIter, fred0 ); fredIter >> f; ) {
     105        split( fred2, fred, middle );
     106
     107        for ( over( fredIter, fred ); fredIter >> f; ) {
    95108                sout | f.i | ' ';
    96109        }
     
    102115        sout | nl;
    103116
    104         transfer( fred0, fred2);
    105 
    106         for ( over( fredIter, fred0 ); fredIter >> f; ) {
    107                 sout | f.i | ' ';
    108         }
    109         sout | nl;
    110 
    111         for ( over( fredIter, fred0 ); fredIter >> f; ) {
     117        transfer( fred, fred2 );
     118
     119        for ( over( fredIter, fred ); fredIter >> f; ) {
     120                sout | f.i | ' ';
     121        }
     122        sout | nl;
     123
     124        for ( over( fredIter, fred ); fredIter >> f; ) {
    112125                delete( &f );
    113126        }
     
    122135        void ?{}( Mary & mary, int p ) with( mary ) {
    123136                ((Fred &)mary){ p };
    124                 j = i = p;
    125         }
    126 
     137                j = p;
     138        }
    127139        Mary *& Next( Mary * n ) {
    128140                return (Mary *)Next( (Fred *)n );
     
    142154        }
    143155
     156        sout | head( mary ).i | tail( mary ).i | nl;
     157
    144158        for ( QueueIter(Mary) iter = { mary }; iter >> m; ) {
    145159                sout | m.i | m.j | ' ';
     
    159173                add( mary, *new( 2 * i + 1 ) );
    160174        }
    161         for ( over( maryIter, mary ); maryIter >> m; ) {
    162                 sout | m.i | m.j | ' ';
    163         }
    164         sout | nl;
    165 
     175
     176        Mary * head = new( -1 ), tail = { -1 };
     177        addHead( mary, *head );
     178        addTail( mary, tail );
     179        sout | head( mary ).i | succ( mary, head )->i | tail( mary ).i | nl;
     180        remove( mary, *head );
     181        remove( mary, tail );
     182        delete( (Mary *)head );
     183        delete( &dropTail( mary ) );
     184
     185        for ( over( maryIter, mary ); maryIter >> m; ) {
     186                sout | m.i | m.j | ' ';
     187        }
     188        sout | nl;
     189
     190        for ( over( maryIter, mary ); maryIter >> m; ) {
     191                delete( &remove( mary, m ) );
     192        }
     193
     194        Mary & middle;
     195        for ( i; 10 ) {
     196                add( mary, *new( i ) );
     197                if ( i == 4 ) {
     198                        &middle = &tail( mary );
     199                }
     200        }
     201        for ( QueueIter(Mary) iter = { mary }; iter >> m; ) {
     202                sout | m.i | m.j | ' ';
     203        }
     204        sout | nl;
     205
     206        Queue(Mary) mary2;
     207
     208        split( mary2, mary, middle );
     209
     210        for ( over( maryIter, mary ); maryIter >> m; ) {
     211                sout | m.i | m.j | ' ';
     212        }
     213        sout | nl;
     214        for ( over( maryIter, mary2 ); maryIter >> m; ) {
     215                sout | m.i | m.j | ' ';
     216        }
     217        sout | nl;
     218
     219        transfer( mary, mary2 );
     220
     221        for ( over( maryIter, mary ); maryIter >> m; ) {
     222                sout | m.i | m.j | ' ';
     223        }
     224        sout | nl;
    166225        for ( over( maryIter, mary ); maryIter >> m; ) {
    167226                delete( &m );
  • tests/collections/sequence.cfa

    rb19fdb9 ree56a4f  
    1414                i = p;
    1515        }
    16 
    1716        Fred *& Back( Fred * n ) {
    1817                return (Fred *)Back( (Seqable *)n );
    1918        }
    20 
    2119        Fred *& Next( Fred * n ) {
    2220                return (Fred *)Next( (Colable *)n );
     
    3836        }
    3937
     38        sout | head( fred ).i | tail( fred ).i | nl;
     39
    4040        for ( SeqIter(Fred) iter = { fred }; iter >> f; ) {
    4141                sout | f.i | ' ';
     
    5555                addTail( fred, *new( 2 * i + 1 ) );
    5656        }
    57         for ( over( fredIter, fred ); fredIter >> f; ) {
    58                 sout | f.i | ' ';
    59         }
    60         sout | nl;
    61 
    62         for ( i; 9 ) {
     57
     58        Fred * head = new( -1 ), tail = { -2 };
     59        addHead( fred, *head );
     60        addTail( fred, tail );
     61
     62        sout | head( fred ).i | succ( fred, head )->i | tail( fred ).i | nl;
     63        for ( over( fredIter, fred ); fredIter >> f; ) {
     64                sout | f.i | ' ';
     65        }
     66        sout | nl;
     67
     68        remove( fred, *head );
     69        remove( fred, tail );
     70        delete( head );
     71        delete( &dropTail( fred ) );
     72
     73        for ( over( fredIter, fred ); fredIter >> f; ) {
     74                sout | f.i | ' ';
     75        }
     76        sout | nl;
     77
     78        for ( i; 5 ) {
    6379                delete( &dropTail( fred ) );
    6480        }
     
    6985
    7086        for ( over( fredIter, fred ); fredIter >> f; ) {
    71                 delete( &f );
    72         }
    73 
    74         Sequence(Fred) fred0;
    75         Fred * middle;
    76         for ( i; 10 ) {
    77                 if( i == 5) {
    78                         middle = new( i );
    79                         addHead( fred0, *middle );
    80                         continue;
     87                delete( &remove( fred, f ) );
     88        }
     89        for ( over( fredIter, fred ); fredIter >> f; ) {
     90                sout | f.i | ' ';
     91        }
     92        sout | "empty" | nl;
     93
     94        Fred & middle;
     95        for ( i; 10 ) {
     96                addHead( fred, *new( i ) );                                             // reverse oder
     97                if ( i == 5 ) {
     98                        &middle = &head( fred );
    8199                }
    82                 addHead( fred0, *new( i ) );
    83         }
    84 
    85         for ( SeqIterRev(Fred) iter = { fred0 }; iter >> f; ) {
    86                 sout | f.i | ' ';
    87         }
    88         sout | nl;
    89 
    90         Fred * front = new( -1 );
    91         insertBef( fred0, *front, tail(fred0));
    92         insertAft( fred0, *front, *new( -2 ) );
    93         remove( fred0, *front );
    94         delete( front );
    95 
    96         sout | head(fred0).i | nl;
    97         Fred & end = dropTail( fred );
    98         delete( &end );
    99 
    100         for ( over( fredIter, fred0 ); fredIter >> f; ) {
     100        }
     101        for ( SeqIterRev(Fred) iter = { fred }; iter >> f; ) {
     102                sout | f.i | ' ';
     103        }
     104        sout | nl;
     105
     106        head = new( -1 );
     107        insertBef( fred, *head, head( fred ) );
     108        insertAft( fred, *head, tail );
     109
     110        sout | head( fred ).i | succ( fred, head )->i | tail( fred ).i | nl;
     111        for ( over( fredIter, fred ); fredIter >> f; ) {
     112                sout | f.i | ' ';
     113        }
     114        sout | nl;
     115
     116        remove( fred, *head );
     117        remove( fred, tail );
     118        delete( head );
     119        delete( &dropTail( fred ) );
     120
     121        for ( over( fredIter, fred ); fredIter >> f; ) {
    101122                sout | f.i | ' ';
    102123        }
     
    105126        Sequence(Fred) fred2;
    106127
    107         split( fred2, fred0, *middle);
    108 
    109         for ( over( fredIter, fred0 ); fredIter >> f; ) {
     128        split( fred2, fred, middle );
     129
     130        for ( over( fredIter, fred ); fredIter >> f; ) {
    110131                sout | f.i | ' ';
    111132        }
     
    117138        sout | nl;
    118139
    119         transfer( fred0, fred2);
    120 
    121         for ( over( fredIter, fred0 ); fredIter >> f; ) {
    122                 sout | f.i | ' ';
    123         }
    124         sout | nl;
    125 
    126         for ( over( fredIter, fred0 ); fredIter >> f; ) {
     140        transfer( fred, fred2 );
     141
     142        for ( over( fredIter, fred ); fredIter >> f; ) {
     143                sout | f.i | ' ';
     144        }
     145        sout | nl;
     146
     147        for ( over( fredIter, fred ); fredIter >> f; ) {
    127148                delete( &f );
    128149        }
     
    139160                j = p;
    140161        }
    141 
    142162        Mary *& Back( Mary * n ) {
    143163                return (Mary *)Back( (Fred *)n );
    144164        }
    145 
    146165        Mary *& Next( Mary * n ) {
    147166                return (Mary *)Next( (Fred *)n );
     
    149168
    150169        Sequence(Mary) mary;
    151         Sequence(Mary) baz;
    152170        SeqIter(Mary) maryIter = { mary };
    153171        Mary & m;
     
    160178        for ( i; 10 ) {
    161179                add( mary, *new( 2 * i ) );
    162                 add( baz, *new( 2 * i ) );
    163         }
     180        }
     181
     182        sout | head( mary ).i | tail( mary ).i | nl;
    164183
    165184        for ( SeqIter(Mary) iter = { mary }; iter >> m; ) {
     
    180199                addTail( mary, *new( 2 * i + 1 ) );
    181200        }
    182         for ( over( maryIter, mary ); maryIter >> m; ) {
    183                 sout | m.i | m.j | ' ';
    184         }
    185         sout | nl;
    186 
    187         for ( i; 9 ) {
    188                 delete( &dropTail( mary ) );
    189         }
    190         for ( over( maryIter, mary ); maryIter >> m; ) {
    191                 sout | m.i | m.j | ' ';
    192         }
    193         sout | nl;
    194 
    195         transfer( mary, baz );
    196 
    197         for ( over( maryIter, baz ); maryIter >> m; ) {
    198                 sout | m.i | m.j | ' ';
    199         }
    200         sout | "empty" | nl;
    201 
    202         for ( over( maryIter, mary ); maryIter >> m; ) {
    203                 sout | m.i | m.j | ' ';
    204         }
    205         sout | nl;
    206 
     201
     202        Mary * head = new( -1 ), tail = { -1 };
     203        addHead( mary, *head );
     204        addTail( mary, tail );
     205        sout | head( mary ).i | succ( mary, head )->i | tail( mary ).i | nl;
     206        remove( mary, *head );
     207        remove( mary, tail );
     208        delete( (Mary *)head );
     209        delete( &dropTail( mary ) );
     210
     211        for ( over( maryIter, mary ); maryIter >> m; ) {
     212                sout | m.i | m.j | ' ';
     213        }
     214        sout | nl;
     215
     216        for ( over( maryIter, mary ); maryIter >> m; ) {
     217                delete( &remove( mary, m ) );
     218        }
     219
     220        Mary & middle;
     221        for ( i; 10 ) {
     222                add( mary, *new( i ) );
     223                if ( i == 4 ) {
     224                        &middle = &tail( mary );
     225                }
     226        }
     227        for ( SeqIter(Mary) iter = { mary }; iter >> m; ) {
     228                sout | m.i | m.j | ' ';
     229        }
     230        sout | nl;
     231
     232        Sequence(Mary) mary2;
     233
     234        split( mary2, mary, middle );
     235
     236        for ( over( maryIter, mary ); maryIter >> m; ) {
     237                sout | m.i | m.j | ' ';
     238        }
     239        sout | nl;
     240        for ( over( maryIter, mary2 ); maryIter >> m; ) {
     241                sout | m.i | m.j | ' ';
     242        }
     243        sout | nl;
     244
     245        transfer( mary, mary2 );
     246
     247        for ( over( maryIter, mary ); maryIter >> m; ) {
     248                sout | m.i | m.j | ' ';
     249        }
     250        sout | nl;
    207251        for ( over( maryIter, mary ); maryIter >> m; ) {
    208252                delete( &m );
  • tests/collections/stack.cfa

    rb19fdb9 ree56a4f  
    3838        sout | nl;
    3939
    40         sout | head(fred).i | nl;
     40        sout | head( fred ).i | nl;
    4141       
    4242        for ( i; 9 ) {
     
    7070        void ?{}( Mary & mary, int p ) with( mary ) {
    7171                ((Fred &)mary){ p };
    72                 j = i = p;
     72                j = p;
    7373        }
    7474
Note: See TracChangeset for help on using the changeset viewer.