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