Changes in libcfa/src/bits/sequence.hfa [a3a76ea:9536761]
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/bits/sequence.hfa
ra3a76ea r9536761 36 36 } // distribution 37 37 38 39 // A Sequence(T) is a Collection(T) defining the ordering of a uStack and uQueue, and to insert and remove elements 40 // anywhere in the sequence. T must be a public descendant of uSeqable. 41 42 // The implementation is a typical doubly-linked list, except the next field of the last node points at the first node 43 // and the back field of the last node points at the first node (circular). 44 38 45 forall( dtype T | { T *& Back ( T * ); T *& Next ( T * ); } ) { 39 46 struct Sequence { … … 52 59 void ?{}( Sequence(T) & s ) with( s ) { 53 60 ((Collection &)s){}; 54 } // post: isEmpty() .55 56 // Return a pointer to the last sequence element, without removing it. 61 } // post: isEmpty() 62 63 // Return a pointer to the last sequence element, without removing it. 57 64 T & tail( Sequence(T) & s ) with( s ) { 58 65 return root ? (T &)*Back( &head( s ) ) : *0p; … … 67 74 } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *s 68 75 69 // Return a pointer to the element before *n, or 0p if there isn't one.76 // Return a pointer to the element before *n, or 0p if list empty. 70 77 T * pred( Sequence(T) & s, T * n ) with( s ) { // pre: *n in *s 71 78 #ifdef __CFA_DEBUG__ … … 73 80 #endif // __CFA_DEBUG__ 74 81 return n == &head( s ) ? 0p : Back( n ); 75 } 76 77 78 // Insert *n into the sequence before *bef, or at the end if bef == 0 .82 } // post: n == head() & head(n) == 0 | n != head() & *pred(n) in *s 83 84 85 // Insert *n into the sequence before *bef, or at the end if bef == 0p. 79 86 T & insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s 80 87 #ifdef __CFA_DEBUG__ … … 137 144 } // if 138 145 return n; 139 } 146 } // post: n->listed() & *n in *s & succ(n) == bef 140 147 141 148 // pre: n->listed() & *n in *s … … 152 159 Next( &n ) = Back( &n ) = 0p; 153 160 return n; 154 } // post: !n->listed().161 } // post: !n->listed() 155 162 156 163 // Add an element to the head of the sequence. … … 158 165 return insertAft( s, *0p, n ); 159 166 } 167 160 168 // Add an element to the tail of the sequence. 161 169 T & addTail( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n 162 170 return insertBef( s, n, *0p ); 163 171 } 172 164 173 // Add an element to the tail of the sequence. 165 174 T & add( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n 166 175 return addTail( s, n ); 167 176 } 177 168 178 // Remove and return the head element in the sequence. 169 179 T & dropHead( Sequence(T) & s ) { … … 171 181 return &n ? remove( s, n ), n : *0p; 172 182 } 183 173 184 // Remove and return the head element in the sequence. 174 185 T & drop( Sequence(T) & s ) { 175 186 return dropHead( s ); 176 187 } 188 177 189 // Remove and return the tail element in the sequence. 178 190 T & dropTail( Sequence(T) & s ) { … … 233 245 ((ColIter &)si){}; 234 246 seq = 0p; 235 } // post: elts = null. 236 247 } // post: elts = null 248 249 // Create a iterator active in sequence s. 237 250 void ?{}( SeqIter(T) & si, Sequence(T) & s ) with( si ) { 238 251 ((ColIter &)si){}; 239 252 seq = &s; 240 253 curr = &head( s ); 241 } // post: elts = null .254 } // post: elts = null 242 255 243 256 void ?{}( SeqIter(T) & si, Sequence(T) & s, T & start ) with( si ) { … … 245 258 seq = &s; 246 259 curr = &start; 247 } // post: elts = null. 248 260 } // post: elts = null 261 262 // Make the iterator active in sequence s. 249 263 void over( SeqIter(T) & si, Sequence(T) & s ) with( si ) { 250 264 seq = &s; 251 265 curr = &head( s ); 252 } // post: elts = {e in s} .253 254 bool ? >>?( SeqIter(T) & si, T && tp ) with( si ) {266 } // post: elts = {e in s} 267 268 bool ?|?( SeqIter(T) & si, T && tp ) with( si ) { 255 269 if ( curr ) { 256 270 &tp = Curr( si ); … … 274 288 ((ColIter &)si){}; 275 289 seq = 0p; 276 } // post: elts = null. 277 290 } // post: elts = null 291 292 // Create a iterator active in sequence s. 278 293 void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) { 279 294 ((ColIter &)si){}; 280 295 seq = &s; 281 296 curr = &tail( s ); 282 } // post: elts = null .297 } // post: elts = null 283 298 284 299 void ?{}( SeqIterRev(T) & si, Sequence(T) & s, T & start ) with( si ) { … … 286 301 seq = &s; 287 302 curr = &start; 288 } // post: elts = null. 289 303 } // post: elts = null 304 305 // Make the iterator active in sequence s. 290 306 void over( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) { 291 307 seq = &s; 292 308 curr = &tail( s ); 293 } // post: elts = {e in s} .294 295 bool ? >>?( SeqIterRev(T) & si, T && tp ) with( si ) {309 } // post: elts = {e in s} 310 311 bool ?|?( SeqIterRev(T) & si, T && tp ) with( si ) { 296 312 if ( curr ) { 297 313 &tp = Curr( si );
Note: See TracChangeset
for help on using the changeset viewer.