Changes in / [ee56a4f:b19fdb9]


Ignore:
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/bits/queue.hfa

    ree56a4f rb19fdb9  
    3434                } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q
    3535
    36                 T & addHead( Queue(T) & q, T & n ) with( q ) {
     36                void 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;
    4847                }
    4948
    50                 T & addTail( Queue(T) & q, T & n ) with( q ) {
     49                void addTail( Queue(T) & q, T & n ) with( q ) {
    5150                        #ifdef __CFA_DEBUG__
    5251                        if ( listed( &n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, &n );
    … …  
    5655                        last = &n;
    5756                        Next( &n ) = &n;                                                        // last node points to itself
    58                         return n;
    5957                }
    6058
    61                 T & add( Queue(T) & q, T & n ) with( q ) {
    62                         return addTail( q, n );
     59                void add( Queue(T) & q, T & n ) with( q ) {
     60                        addTail( q, n );
    6361                }
    6462
    … …  
    7977                }
    8078
    81                 T & remove( Queue(T) & q, T & n ) with( q ) {   // O(n)
     79                void remove( Queue(T) & q, T & n ) with( q ) {  // O(n)
    8280                        #ifdef __CFA_DEBUG__
    8381                        if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, &n );
    … …  
    105103                                curr = Next( curr );
    106104                        }
    107                         return n;
    108105                } // post: ! listed( n )
    109106

  • libcfa/src/bits/sequence.hfa

    ree56a4f rb19fdb9  
    7777
    7878                // Insert *n into the sequence before *bef, or at the end if bef == 0.
    79                 T & insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s
     79                void 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;
    108107                }       // post: n->listed() & *n in *s & succ(n) == bef
    109108
    110109
    111110                // Insert *n into the sequence after *aft, or at the beginning if aft == 0.
    112                 T & insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) {    // pre: !n->listed() & *aft in *s
     111                void insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) {   // pre: !n->listed() & *aft in *s
    113112                        #ifdef __CFA_DEBUG__
    114113                        if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n );
    … …  
    136135                                Next( &aft ) = &n;
    137136                        } // if
    138                         return n;
    139137                }         // post: n->listed() & *n in *s & succ(n) == bef
    140138               
    141139                // pre: n->listed() & *n in *s
    142                 T & remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
     140                void remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
    143141                        #ifdef __CFA_DEBUG__
    144142                        if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n );
    … …  
    151149                        Next( Back( &n ) ) = Next( &n );
    152150                        Next( &n ) = Back( &n ) = 0p;
    153                         return n;
    154151                }                                                       // post: !n->listed().
    155152
    156153                // Add an element to the head of the sequence.
    157                 T & addHead( Sequence(T) & s, T & n ) {                 // pre: !n->listed(); post: n->listed() & head() == n
    158                         return insertAft( s, *0p, n );
     154                void addHead( Sequence(T) & s, T & n ) {                // pre: !n->listed(); post: n->listed() & head() == n
     155                        insertAft( s, *0p, n );
    159156                }
    160157                // Add an element to the tail of the sequence.
    161                 T & addTail( Sequence(T) & s, T & n ) {                 // pre: !n->listed(); post: n->listed() & head() == n
    162                         return insertBef( s, n, *0p );
     158                void addTail( Sequence(T) & s, T & n ) {                // pre: !n->listed(); post: n->listed() & head() == n
     159                        insertBef( s, n, *0p );
    163160                }
    164161                // Add an element to the tail of the sequence.
    165                 T & add( Sequence(T) & s, T & n ) {                             // pre: !n->listed(); post: n->listed() & head() == n
    166                         return addTail( s, n );
     162                void add( Sequence(T) & s, T & n ) {                    // pre: !n->listed(); post: n->listed() & head() == n
     163                        addTail( s, n );
    167164                }
    168165                // Remove and return the head element in the sequence.

  • libcfa/src/bits/stack.hfa

    ree56a4f rb19fdb9  
    2525                }
    2626
    27                 T & addHead( Stack(T) & s, T & n ) with( s ) {
     27                void 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;
    3433                }
    3534
    36                 T & add( Stack(T) & s, T & n ) with( s ) {
    37                         return addHead( s, n );
     35                void add( Stack(T) & s, T & n ) with( s ) {
     36                        addHead( s, n );
    3837                }
    3938
    40                 T & push( Stack(T) & s, T & n ) with( s ) {
    41                         return addHead( s, n );
     39                void push( Stack(T) & s, T & n ) with( s ) {
     40                        addHead( s, n );
    4241                }
    4342

  • tests/collections/.expect/queue.txt

    ree56a4f rb19fdb9  
    11empty
    2 0 18
     20
     318
    340 2 4 6 8 10 12 14 16 18
    4518
    5 -1 18 -2
    6 -1 18 1 3 5 7 9 11 13 15 17 19 -2
     618
    7718 1 3 5 7 9 11 13 15 17
    8 18 1 3 5 7
     80 1 2 3 4 5 6 7 8 9
     96 7 8 9
     100 1 2 3 4 5
     116 7 8 9 0 1 2 3 4 5
    912empty
    10 0 1 2 3 4 5 6 7 8 9
    11 5 6 7 8 9
    12 0 1 2 3 4
    13 5 6 7 8 9 0 1 2 3 4
    14 empty
    15 0 18
    16130 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18
    171418 18
    18 -1 18 -1
    19 18 18 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17
    20 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
    21 5 5 6 6 7 7 8 8 9 9
    22 0 0 1 1 2 2 3 3 4 4
    23 5 5 6 6 7 7 8 8 9 9 0 0 1 1 2 2 3 3 4 4
     1518 18 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19

  • tests/collections/.expect/sequence.txt

    ree56a4f rb19fdb9  
    11empty
    2 0 18
    320 2 4 6 8 10 12 14 16 18
    4318
    5 -1 18 -2
    6 -1 18 1 3 5 7 9 11 13 15 17 19 -2
    7 18 1 3 5 7 9 11 13 15 17
    8 18 1 3 5 7
     418 1 3 5 7 9 11 13 15 17 19
     518 1
     60 1 2 3 4 5 6 7 8 9
     79
     89 8 7 6 5 4 3 1 -2 0
     94 3 1 -2 0
     109 8 7 6 5
     114 3 1 -2 0 9 8 7 6 5
    912empty
    10 0 1 2 3 4 5 6 7 8 9
    11 -1 -2 0
    12 -1 -2 9 8 7 6 5 4 3 2 1 0
    13 9 8 7 6 5 4 3 2 1
    14 4 3 2 1
    15 9 8 7 6 5
    16 4 3 2 1 9 8 7 6 5
    17 empty
    18 0 18
    19130 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18
    201418 18
    21 -1 18 -1
    22 18 18 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17
    23 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
    24 5 5 6 6 7 7 8 8 9 9
    25 0 0 1 1 2 2 3 3 4 4
    26 5 5 6 6 7 7 8 8 9 9 0 0 1 1 2 2 3 3 4 4
     1518 18 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19
     1618 18 1 1
     17empty
     1818 18 1 1 0 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18

  • tests/collections/queue.cfa

    ree56a4f rb19fdb9  
    3333        }
    3434
    35         sout | head( fred ).i | tail( fred ).i | nl;
     35        sout | head(fred).i | nl;
     36        sout | tail(fred).i | nl;
    3637
    3738        for ( QueueIter(Fred) iter = { fred }; iter >> f; ) {
    … …  
    5354        }
    5455
    55         Fred * head = new( -1 ), tail = { -2 };
    56         addHead( fred, *head );
    57         addTail( fred, tail );
     56        Fred * front = new( -1 );
     57        addHead( fred, *front );
     58        sout | succ( fred, front )->i | nl;
     59        remove( fred, *front );
     60        delete( front );
    5861
    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 ) );
     62        Fred & end = dropTail( fred );
     63        delete( &end );
    6964
    7065        for ( over( fredIter, fred ); fredIter >> f; ) {
    … …  
    7368        sout | nl;
    7469
    75         for ( i; 5 ) {
    76                 delete( &dropTail( fred ) );
     70        for ( over( fredIter, fred ); fredIter >> f; ) {
     71                delete( &f );
    7772        }
    78         for ( over( fredIter, fred ); fredIter >> f; ) {
    79                 sout | f.i | ' ';
     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;
     81                }
     82                add( fred0, *new( i ) );
    8083        }
    81         sout | nl;
    8284
    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 );
    96                 }
    97         }
    98         for ( QueueIter(Fred) iter = { fred }; iter >> f; ) {
     85        for ( QueueIter(Fred) iter = { fred0 }; iter >> f; ) {
    9986                sout | f.i | ' ';
    10087        }
    … …  
    10390        Queue(Fred) fred2;
    10491
    105         split( fred2, fred, middle );
     92        split( fred2, fred0, *middle);
    10693
    107         for ( over( fredIter, fred ); fredIter >> f; ) {
     94        for ( over( fredIter, fred0 ); fredIter >> f; ) {
    10895                sout | f.i | ' ';
    10996        }
    … …  
    115102        sout | nl;
    116103
    117         transfer( fred, fred2 );
     104        transfer( fred0, fred2);
    118105
    119         for ( over( fredIter, fred ); fredIter >> f; ) {
     106        for ( over( fredIter, fred0 ); fredIter >> f; ) {
    120107                sout | f.i | ' ';
    121108        }
    122109        sout | nl;
    123110
    124         for ( over( fredIter, fred ); fredIter >> f; ) {
     111        for ( over( fredIter, fred0 ); fredIter >> f; ) {
    125112                delete( &f );
    126113        }
    … …  
    135122        void ?{}( Mary & mary, int p ) with( mary ) {
    136123                ((Fred &)mary){ p };
    137                 j = p;
     124                j = i = p;
    138125        }
     126
    139127        Mary *& Next( Mary * n ) {
    140128                return (Mary *)Next( (Fred *)n );
    … …  
    153141                add( mary, *new( 2 * i ) );
    154142        }
    155 
    156         sout | head( mary ).i | tail( mary ).i | nl;
    157143
    158144        for ( QueueIter(Mary) iter = { mary }; iter >> m; ) {
    … …  
    173159                add( mary, *new( 2 * i + 1 ) );
    174160        }
    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 
    185161        for ( over( maryIter, mary ); maryIter >> m; ) {
    186162                sout | m.i | m.j | ' ';
    … …  
    189165
    190166        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;
    225         for ( over( maryIter, mary ); maryIter >> m; ) {
    226167                delete( &m );
    227168        }

  • tests/collections/sequence.cfa

    ree56a4f rb19fdb9  
    1414                i = p;
    1515        }
     16
    1617        Fred *& Back( Fred * n ) {
    1718                return (Fred *)Back( (Seqable *)n );
    1819        }
     20
    1921        Fred *& Next( Fred * n ) {
    2022                return (Fred *)Next( (Colable *)n );
    … …  
    3638        }
    3739
    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 
    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 ) {
     57        for ( over( fredIter, fred ); fredIter >> f; ) {
     58                sout | f.i | ' ';
     59        }
     60        sout | nl;
     61
     62        for ( i; 9 ) {
    7963                delete( &dropTail( fred ) );
    8064        }
    … …  
    8569
    8670        for ( over( fredIter, fred ); fredIter >> f; ) {
    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 );
     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;
    9981                }
    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; ) {
     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; ) {
    122101                sout | f.i | ' ';
    123102        }
    … …  
    126105        Sequence(Fred) fred2;
    127106
    128         split( fred2, fred, middle );
    129 
    130         for ( over( fredIter, fred ); fredIter >> f; ) {
     107        split( fred2, fred0, *middle);
     108
     109        for ( over( fredIter, fred0 ); fredIter >> f; ) {
    131110                sout | f.i | ' ';
    132111        }
    … …  
    138117        sout | nl;
    139118
    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; ) {
     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; ) {
    148127                delete( &f );
    149128        }
    … …  
    160139                j = p;
    161140        }
     141
    162142        Mary *& Back( Mary * n ) {
    163143                return (Mary *)Back( (Fred *)n );
    164144        }
     145
    165146        Mary *& Next( Mary * n ) {
    166147                return (Mary *)Next( (Fred *)n );
    … …  
    168149
    169150        Sequence(Mary) mary;
     151        Sequence(Mary) baz;
    170152        SeqIter(Mary) maryIter = { mary };
    171153        Mary & m;
    … …  
    178160        for ( i; 10 ) {
    179161                add( mary, *new( 2 * i ) );
    180         }
    181 
    182         sout | head( mary ).i | tail( mary ).i | nl;
     162                add( baz, *new( 2 * i ) );
     163        }
    183164
    184165        for ( SeqIter(Mary) iter = { mary }; iter >> m; ) {
    … …  
    199180                addTail( mary, *new( 2 * i + 1 ) );
    200181        }
    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;
     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
    251207        for ( over( maryIter, mary ); maryIter >> m; ) {
    252208                delete( &m );

  • tests/collections/stack.cfa

    ree56a4f rb19fdb9  
    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 = p;
     72                j = i = p;
    7373        }
    7474
Note: See TracChangeset for help on using the changeset viewer.