Changes in libcfa/src/bits/sequence.hfa [636d3715:5e82d56]
- File:
-
- 1 edited
-
libcfa/src/bits/sequence.hfa (modified) (13 diffs)
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/bits/sequence.hfa
r636d3715 r5e82d56 10 10 inline { 11 11 void ?{}( Seqable & sq ) with( sq ) { 12 ((Colable & ) sq){};12 ((Colable & ) sq){}; 13 13 back = 0p; 14 14 } // post: ! listed() … … 34 34 } // post: empty() & head() == 0 | !empty() & head() in *s 35 35 36 bool empty( Sequence(T) & s ) with( s ) { // 0 <=> *s contains no elements 37 return empty( (Collection &)s ); 38 } 39 40 bool listed( T * n ) { 41 return Next( (Colable *)n ) != 0; 42 } 43 44 T *& Next( T * n ) { 45 return (T *)Next( (Colable *)n ); 46 } 47 36 48 T *& Back( T * n ) { 37 49 return (T *)Back( (Seqable *)n ); 50 } 51 52 T * Root( Sequence(T) & s ) with( s ) { 53 return (T *)root; 38 54 } 39 55 … … 46 62 47 63 // Return a pointer to the last sequence element, without removing it. 48 T &tail( Sequence(T) & s ) with( s ) {49 return root ? (T &)Back( head( s ) ) : *0p; // needs cast?64 T * tail( Sequence(T) & s ) with( s ) { 65 return root ? (T *)Back( Root( s ) ) : 0p; // needs cast? 50 66 } // post: empty() & tail() == 0 | !empty() & tail() in *s 51 67 … … 55 71 if ( ! listed( n ) ) abort( "(Sequence &)%p.succ( %p ) : Node is not on a list.", &s, n ); 56 72 #endif // __CFA_DEBUG__ 57 return Next( n ) == head( s ) ? 0p : Next( n );73 return Next( n ) == Root( s ) ? 0p : Next( n ); 58 74 } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *s 59 75 … … 63 79 if ( ! listed( n ) ) abort( "(Sequence &)%p.pred( %p ) : Node is not on a list.", &s, n ); 64 80 #endif // __CFA_DEBUG__ 65 return n == head( s ) ? 0p : Back( n );81 return n == Root( s ) ? 0p : Back( n ); 66 82 } // post: n == head() & head(n) == 0 | n != head() & *pred(n) in *s 67 83 68 84 69 85 // Insert *n into the sequence before *bef, or at the end if bef == 0. 70 void insertBef( Sequence(T) & s, T & n, T &bef ) with( s ) { // pre: !n->listed() & *bef in *s71 #ifdef __CFA_DEBUG__ 72 if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef );73 #endif // __CFA_DEBUG__ 74 if ( &bef == head( s ) ) { // must change root86 void insertBef( Sequence(T) & s, T * n, T * bef ) with( s ) { // pre: !n->listed() & *bef in *s 87 #ifdef __CFA_DEBUG__ 88 if ( listed( n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, bef ); 89 #endif // __CFA_DEBUG__ 90 if ( bef == Root( s ) ) { // must change root 75 91 if ( root ) { 76 Next( &n ) = head( s );77 Back( &n ) = Back( head( s ) );92 Next( n ) = Root( s ); 93 Back( n ) = Back( Root( s ) ); 78 94 // inserted node must be consistent before it is seen 79 95 asm( "" : : : "memory" ); // prevent code movement across barrier 80 Back( head( s ) ) = &n;81 Next( Back( &n ) ) = &n;96 Back( Root( s ) ) = n; 97 Next( Back( n ) ) = n; 82 98 } else { 83 Next( &n ) = &n;84 Back( &n ) = &n;99 Next( n ) = n; 100 Back( n ) = n; 85 101 } // if 86 102 // inserted node must be consistent before it is seen 87 103 asm( "" : : : "memory" ); // prevent code movement across barrier 88 root = &n;104 root = n; 89 105 } else { 90 if ( ! &bef ) &bef = head( s );91 Next( &n ) = &bef;92 Back( &n ) = Back( &bef );106 if ( ! bef ) bef = Root( s ); 107 Next( n ) = bef; 108 Back( n ) = Back( bef ); 93 109 // inserted node must be consistent before it is seen 94 110 asm( "" : : : "memory" ); // prevent code movement across barrier 95 Back( &bef ) = &n;96 Next( Back( &n ) ) = &n;111 Back( bef ) = n; 112 Next( Back( n ) ) = n; 97 113 } // if 98 114 } // post: n->listed() & *n in *s & succ(n) == bef … … 100 116 101 117 // Insert *n into the sequence after *aft, or at the beginning if aft == 0. 102 void insertAft( Sequence(T) & s, T & aft, T &n ) with( s ) { // pre: !n->listed() & *aft in *s103 #ifdef __CFA_DEBUG__ 104 if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n );105 #endif // __CFA_DEBUG__ 106 if ( ! &aft ) { // must change root118 void insertAft( Sequence(T) & s, T *aft, T *n ) with( s ) { // pre: !n->listed() & *aft in *s 119 #ifdef __CFA_DEBUG__ 120 if ( listed( n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, aft, n ); 121 #endif // __CFA_DEBUG__ 122 if ( ! aft ) { // must change root 107 123 if ( root ) { 108 Next( &n ) = head( s );109 Back( &n ) = Back( head( s ) );124 Next( n ) = Root( s ); 125 Back( n ) = Back( Root( s ) ); 110 126 // inserted node must be consistent before it is seen 111 127 asm( "" : : : "memory" ); // prevent code movement across barrier 112 Back( head( s ) ) = &n;113 Next( Back( &n ) ) = &n;128 Back( Root( s ) ) = n; 129 Next( Back( n ) ) = n; 114 130 } else { 115 Next( &n ) = &n;116 Back( &n ) = &n;131 Next( n ) = n; 132 Back( n ) = n; 117 133 } // if 118 134 asm( "" : : : "memory" ); // prevent code movement across barrier 119 root = &n;135 root = n; 120 136 } else { 121 Next( &n ) = Next( &aft );122 Back( &n ) = &aft;137 Next( n ) = Next( aft ); 138 Back( n ) = aft; 123 139 // inserted node must be consistent before it is seen 124 140 asm( "" : : : "memory" ); // prevent code movement across barrier 125 Back( Next( &n ) ) = &n;126 Next( &aft ) = &n;141 Back( Next( n ) ) = n; 142 Next( aft ) = n; 127 143 } // if 128 144 } // post: n->listed() & *n in *s & succ(n) == bef 129 145 130 146 // pre: n->listed() & *n in *s 131 void remove( Sequence(T) & s, T &n ) with( s ) { // O(1)132 #ifdef __CFA_DEBUG__ 133 if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n );134 #endif // __CFA_DEBUG__ 135 if ( &n == head( s ) ) {136 if ( Next( head( s ) ) == head( s ) ) root = 0p;137 else root = Next( head(s ) );138 } // if 139 Back( Next( &n ) ) = Back( &n );140 Next( Back( &n ) ) = Next( &n );141 Next( &n ) = Back( &n ) = 0p;147 void remove( Sequence(T) & s, T *n ) with( s ) { // O(1) 148 #ifdef __CFA_DEBUG__ 149 if ( ! listed( n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, n ); 150 #endif // __CFA_DEBUG__ 151 if ( n == Root( s ) ) { 152 if ( Next( Root( s ) ) == Root( s ) ) root = 0p; 153 else root = Next( Root(s ) ); 154 } // if 155 Back( Next( n ) ) = Back( n ); 156 Next( Back( n ) ) = Next( n ); 157 Next( n ) = Back( n ) = 0p; 142 158 } // post: !n->listed(). 143 159 144 160 // Add an element to the head of the sequence. 145 void addHead( Sequence(T) & s, T & n ) {// pre: !n->listed(); post: n->listed() & head() == n146 insertAft( s, *0p, n );161 void addHead( Sequence(T) & s, T *n ) { // pre: !n->listed(); post: n->listed() & head() == n 162 insertAft( s, 0, n ); 147 163 } 148 164 // Add an element to the tail of the sequence. 149 void addTail( Sequence(T) & s, T & n ) {// pre: !n->listed(); post: n->listed() & head() == n150 insertBef( s, n, *0p);165 void addTail( Sequence(T) & s, T *n ) { // pre: !n->listed(); post: n->listed() & head() == n 166 insertBef( s, n, 0 ); 151 167 } 152 168 // Add an element to the tail of the sequence. 153 void add( Sequence(T) & s, T & n ) {// pre: !n->listed(); post: n->listed() & head() == n169 void add( Sequence(T) & s, T *n ) { // pre: !n->listed(); post: n->listed() & head() == n 154 170 addTail( s, n ); 155 171 } 156 172 // Remove and return the head element in the sequence. 157 T &dropHead( Sequence(T) & s ) {173 T * dropHead( Sequence(T) & s ) { 158 174 T * n = head( s ); 159 return n ? remove( s, *n ), *n : *0p;175 return n ? remove( s, n ), n : 0p; 160 176 } 161 177 // Remove and return the head element in the sequence. 162 T &drop( Sequence(T) & s ) {178 T * drop( Sequence(T) & s ) { 163 179 return dropHead( s ); 164 180 } 165 181 // Remove and return the tail element in the sequence. 166 T &dropTail( Sequence(T) & s ) {167 T &n = tail( s );168 return &n ? remove( s, n ), n : *0p;182 T * dropTail( Sequence(T) & s ) { 183 T * n = tail( s ); 184 return n ? remove( s, n ), n : 0p; 169 185 } 170 186 … … 175 191 root = from.root; 176 192 } else { // "to" list not empty 177 T * toEnd = Back( head( s ) );178 T * fromEnd = Back( head( from ) );193 T * toEnd = Back( Root( s ) ); 194 T * fromEnd = Back( Root( from ) ); 179 195 Back( root ) = fromEnd; 180 Next( fromEnd ) = head( s );196 Next( fromEnd ) = Root( s ); 181 197 Back( from.root ) = toEnd; 182 Next( toEnd ) = head( from );198 Next( toEnd ) = Root( from ); 183 199 } // if 184 200 from.root = 0p; // mark "from" list empty … … 197 213 from.root = 0p; // mark "from" list empty 198 214 } else { 199 Back( head( from ) ) = Back( head( to ) ); // fix "from" list200 Next( Back( head( to ) ) ) = head( from );201 Next( n ) = head( to ); // fix "to" list202 Back( head( to ) ) = n;215 Back( Root( from ) ) = Back( Root( to ) ); // fix "from" list 216 Next( Back( Root( to ) ) ) = Root( from ); 217 Next( n ) = Root( to ); // fix "to" list 218 Back( Root( to ) ) = n; 203 219 } // if 204 220 transfer( s, to ); … … 215 231 216 232 inline { 217 void ?{}( SeqIter(T) & si ) with( si ) { 218 ((ColIter &)si){}; 233 // wrappers to make ColIter have T 234 T * Curr( SeqIter(T) & si ) with( si ) { 235 return (T *)curr; 236 } 237 238 void ?{}( SeqIter(T) & si ) with( si ) { 239 ((ColIter &) si){}; 219 240 seq = 0p; 220 241 } // post: elts = null. … … 223 244 ((ColIter &) si){}; 224 245 seq = &s; 225 curr = head( s );226 246 } // post: elts = null. 227 247 … … 231 251 } // post: elts = {e in s}. 232 252 233 bool ?>>?( SeqIter(T) & si, T && tp ) with( si ) {253 bool ?>>?( SeqIter(T) & si, T *& tp ) with( si ) { 234 254 if ( curr ) { 235 &tp = Curr( si );236 T * 255 tp = Curr( si ); 256 T *n = succ( *seq, Curr( si ) ); 237 257 curr = n == head( *seq ) ? 0p : n; 238 } else &tp = 0p;239 return &tp != 0p;258 } else tp = 0p; 259 return tp != 0p; 240 260 } 241 261 } // distribution … … 249 269 250 270 inline { 271 // wrappers to make ColIter have T 272 T * Curr( SeqIterRev(T) & si ) with( si ) { 273 return (T *)curr; 274 } 275 251 276 void ?{}( SeqIterRev(T) & si ) with( si ) { 252 277 ((ColIter &) si){}; … … 257 282 ((ColIter &) si){}; 258 283 seq = &s; 259 curr = &tail( s );260 284 } // post: elts = null. 261 285 262 286 void over( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) { 263 287 seq = &s; 264 curr = &tail( s );288 curr = tail( s ); 265 289 } // post: elts = {e in s}. 266 290 267 bool ?>>?( SeqIterRev(T) & si, T &&tp ) with( si ) {291 bool ?>>?( SeqIterRev(T) & si, T *&tp ) with( si ) { 268 292 if ( curr ) { 269 &tp = Curr( si );270 T * 271 curr = n == &tail( *seq ) ? 0p : n;272 } else &tp = 0p;273 return &tp != 0p;293 tp = Curr( si ); 294 T *n = pred( *seq, Curr( si ) ); 295 curr = n == tail( *seq ) ? 0p : n; 296 } else tp = 0p; 297 return tp != 0p; 274 298 } 275 299 } // distribution
Note:
See TracChangeset
for help on using the changeset viewer.
