Changes in / [ac5816d:1e6f632f]
- Files:
-
- 8 edited
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/bits/queue.hfa
rac5816d r1e6f632f 34 34 } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q 35 35 36 voidaddHead( Queue(T) & q, T & n ) with( q ) {36 T & addHead( Queue(T) & q, T & n ) with( q ) { 37 37 #ifdef __CFA_DEBUG__ 38 38 if ( listed( &n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, &n ); … … 45 45 Next( &n ) = &n; // last node points to itself 46 46 } 47 return n; 47 48 } 48 49 49 voidaddTail( Queue(T) & q, T & n ) with( q ) {50 T & addTail( Queue(T) & q, T & n ) with( q ) { 50 51 #ifdef __CFA_DEBUG__ 51 52 if ( listed( &n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, &n ); … … 55 56 last = &n; 56 57 Next( &n ) = &n; // last node points to itself 58 return n; 57 59 } 58 60 59 voidadd( 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 ); 61 63 } 62 64 … … 77 79 } 78 80 79 voidremove( Queue(T) & q, T & n ) with( q ) { // O(n)81 T & remove( Queue(T) & q, T & n ) with( q ) { // O(n) 80 82 #ifdef __CFA_DEBUG__ 81 83 if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, &n ); … … 103 105 curr = Next( curr ); 104 106 } 107 return n; 105 108 } // post: ! listed( n ) 106 109 -
libcfa/src/bits/sequence.hfa
rac5816d r1e6f632f 77 77 78 78 // Insert *n into the sequence before *bef, or at the end if bef == 0. 79 voidinsertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s79 T & insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s 80 80 #ifdef __CFA_DEBUG__ 81 81 if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef ); … … 105 105 Next( Back( &n ) ) = &n; 106 106 } // if 107 return n; 107 108 } // post: n->listed() & *n in *s & succ(n) == bef 108 109 109 110 110 111 // Insert *n into the sequence after *aft, or at the beginning if aft == 0. 111 voidinsertAft( Sequence(T) & s, T & aft, T & n ) with( s ) { // pre: !n->listed() & *aft in *s112 T & insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) { // pre: !n->listed() & *aft in *s 112 113 #ifdef __CFA_DEBUG__ 113 114 if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n ); … … 135 136 Next( &aft ) = &n; 136 137 } // if 138 return n; 137 139 } // post: n->listed() & *n in *s & succ(n) == bef 138 140 139 141 // pre: n->listed() & *n in *s 140 voidremove( Sequence(T) & s, T & n ) with( s ) { // O(1)142 T & remove( Sequence(T) & s, T & n ) with( s ) { // O(1) 141 143 #ifdef __CFA_DEBUG__ 142 144 if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n ); … … 149 151 Next( Back( &n ) ) = Next( &n ); 150 152 Next( &n ) = Back( &n ) = 0p; 153 return n; 151 154 } // post: !n->listed(). 152 155 153 156 // Add an element to the head of the sequence. 154 void addHead( Sequence(T) & s, T & n ) {// pre: !n->listed(); post: n->listed() & head() == n155 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 ); 156 159 } 157 160 // Add an element to the tail of the sequence. 158 void addTail( Sequence(T) & s, T & n ) {// pre: !n->listed(); post: n->listed() & head() == n159 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 ); 160 163 } 161 164 // Add an element to the tail of the sequence. 162 void add( Sequence(T) & s, T & n ) {// pre: !n->listed(); post: n->listed() & head() == n163 addTail( s, n );165 T & add( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n 166 return addTail( s, n ); 164 167 } 165 168 // Remove and return the head element in the sequence. -
libcfa/src/bits/stack.hfa
rac5816d r1e6f632f 25 25 } 26 26 27 voidaddHead( Stack(T) & s, T & n ) with( s ) {27 T & addHead( Stack(T) & s, T & n ) with( s ) { 28 28 #ifdef __CFA_DEBUG__ 29 29 if ( listed( (Colable &)(n) ) ) abort( "(Stack &)%p.addHead( %p ) : Node is already on another list.", &s, n ); … … 31 31 Next( &n ) = &head( s ) ? &head( s ) : &n; 32 32 root = &n; 33 return n; 33 34 } 34 35 35 voidadd( 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 ); 37 38 } 38 39 39 voidpush( 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 ); 41 42 } 42 43 -
tests/collections/.expect/queue.txt
rac5816d r1e6f632f 1 1 empty 2 0 3 18 2 0 18 4 3 0 2 4 6 8 10 12 14 16 18 5 4 18 6 18 5 -1 18 -2 6 -1 18 1 3 5 7 9 11 13 15 17 19 -2 7 7 18 1 3 5 7 9 11 13 15 17 8 18 1 3 5 7 9 empty 8 10 0 1 2 3 4 5 6 7 8 9 9 6 7 8 910 0 1 2 3 4 511 6 7 8 9 0 1 2 3 4 511 5 6 7 8 9 12 0 1 2 3 4 13 5 6 7 8 9 0 1 2 3 4 12 14 empty 15 0 18 13 16 0 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 14 17 18 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 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 -
tests/collections/.expect/sequence.txt
rac5816d r1e6f632f 1 1 empty 2 0 18 2 3 0 2 4 6 8 10 12 14 16 18 3 4 18 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 7 18 1 3 5 7 9 11 13 15 17 8 18 1 3 5 7 9 empty 6 10 0 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 13 9 8 7 6 5 4 3 2 1 14 4 3 2 1 10 15 9 8 7 6 5 11 4 3 1 -2 09 8 7 6 516 4 3 2 1 9 8 7 6 5 12 17 empty 18 0 18 13 19 0 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 14 20 18 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 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 -
tests/collections/queue.cfa
rac5816d r1e6f632f 33 33 } 34 34 35 sout | head(fred).i | nl; 36 sout | tail(fred).i | nl; 35 sout | head( fred ).i | tail( fred ).i | nl; 37 36 38 37 for ( QueueIter(Fred) iter = { fred }; iter >> f; ) { … … 54 53 } 55 54 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 ); 81 96 } 82 add( fred0, *new( i ) ); 83 } 84 85 for ( QueueIter(Fred) iter = { fred0 }; iter >> f; ) { 97 } 98 for ( QueueIter(Fred) iter = { fred }; iter >> f; ) { 86 99 sout | f.i | ' '; 87 100 } … … 90 103 Queue(Fred) fred2; 91 104 92 split( fred2, fred 0, *middle);93 94 for ( over( fredIter, fred 0); fredIter >> f; ) {105 split( fred2, fred, middle ); 106 107 for ( over( fredIter, fred ); fredIter >> f; ) { 95 108 sout | f.i | ' '; 96 109 } … … 102 115 sout | nl; 103 116 104 transfer( fred 0, fred2);105 106 for ( over( fredIter, fred 0); fredIter >> f; ) {107 sout | f.i | ' '; 108 } 109 sout | nl; 110 111 for ( over( fredIter, fred 0); 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; ) { 112 125 delete( &f ); 113 126 } … … 122 135 void ?{}( Mary & mary, int p ) with( mary ) { 123 136 ((Fred &)mary){ p }; 124 j = i = p; 125 } 126 137 j = p; 138 } 127 139 Mary *& Next( Mary * n ) { 128 140 return (Mary *)Next( (Fred *)n ); … … 142 154 } 143 155 156 sout | head( mary ).i | tail( mary ).i | nl; 157 144 158 for ( QueueIter(Mary) iter = { mary }; iter >> m; ) { 145 159 sout | m.i | m.j | ' '; … … 159 173 add( mary, *new( 2 * i + 1 ) ); 160 174 } 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; 166 225 for ( over( maryIter, mary ); maryIter >> m; ) { 167 226 delete( &m ); -
tests/collections/sequence.cfa
rac5816d r1e6f632f 14 14 i = p; 15 15 } 16 17 16 Fred *& Back( Fred * n ) { 18 17 return (Fred *)Back( (Seqable *)n ); 19 18 } 20 21 19 Fred *& Next( Fred * n ) { 22 20 return (Fred *)Next( (Colable *)n ); … … 38 36 } 39 37 38 sout | head( fred ).i | tail( fred ).i | nl; 39 40 40 for ( SeqIter(Fred) iter = { fred }; iter >> f; ) { 41 41 sout | f.i | ' '; … … 55 55 addTail( fred, *new( 2 * i + 1 ) ); 56 56 } 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 ) { 63 79 delete( &dropTail( fred ) ); 64 80 } … … 69 85 70 86 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 ); 81 99 } 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; ) { 101 122 sout | f.i | ' '; 102 123 } … … 105 126 Sequence(Fred) fred2; 106 127 107 split( fred2, fred 0, *middle);108 109 for ( over( fredIter, fred 0); fredIter >> f; ) {128 split( fred2, fred, middle ); 129 130 for ( over( fredIter, fred ); fredIter >> f; ) { 110 131 sout | f.i | ' '; 111 132 } … … 117 138 sout | nl; 118 139 119 transfer( fred 0, fred2);120 121 for ( over( fredIter, fred 0); fredIter >> f; ) {122 sout | f.i | ' '; 123 } 124 sout | nl; 125 126 for ( over( fredIter, fred 0); 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; ) { 127 148 delete( &f ); 128 149 } … … 139 160 j = p; 140 161 } 141 142 162 Mary *& Back( Mary * n ) { 143 163 return (Mary *)Back( (Fred *)n ); 144 164 } 145 146 165 Mary *& Next( Mary * n ) { 147 166 return (Mary *)Next( (Fred *)n ); … … 149 168 150 169 Sequence(Mary) mary; 151 Sequence(Mary) baz;152 170 SeqIter(Mary) maryIter = { mary }; 153 171 Mary & m; … … 160 178 for ( i; 10 ) { 161 179 add( mary, *new( 2 * i ) ); 162 add( baz, *new( 2 * i ) ); 163 } 180 } 181 182 sout | head( mary ).i | tail( mary ).i | nl; 164 183 165 184 for ( SeqIter(Mary) iter = { mary }; iter >> m; ) { … … 180 199 addTail( mary, *new( 2 * i + 1 ) ); 181 200 } 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; 207 251 for ( over( maryIter, mary ); maryIter >> m; ) { 208 252 delete( &m ); -
tests/collections/stack.cfa
rac5816d r1e6f632f 38 38 sout | nl; 39 39 40 sout | head( fred).i | nl;40 sout | head( fred ).i | nl; 41 41 42 42 for ( i; 9 ) { … … 70 70 void ?{}( Mary & mary, int p ) with( mary ) { 71 71 ((Fred &)mary){ p }; 72 j = i =p;72 j = p; 73 73 } 74 74
Note: See TracChangeset
for help on using the changeset viewer.