- Timestamp:
- Dec 28, 2020, 4:00:51 PM (4 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 657c36f
- Parents:
- 1e6f632f
- Location:
- libcfa/src/bits
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/bits/collection.hfa
r1e6f632f r9536761 68 68 69 69 struct ColIter { 70 void * curr; // element to be returned by >>70 void * curr; // element returned by | 71 71 }; 72 72 -
libcfa/src/bits/queue.hfa
r1e6f632f r9536761 2 2 3 3 #include "bits/collection.hfa" 4 5 // A Queue(T) is a Collection(T) defining the ordering that nodes are returned by drop() in the same order from those 6 // added by add(). T must be a public descendant of uColable. 7 8 // The implementation is a typical singly-linked list, except the next field of the last element points to itself 9 // instead of being null. 4 10 5 11 forall( dtype T | { T *& Next ( T * ); } ) { … … 108 114 } // post: ! listed( n ) 109 115 110 T & dropTail( Queue(T) & q ) with( q ) { 116 T & dropTail( Queue(T) & q ) with( q ) { // O(n) 111 117 T & n = tail( q ); 112 118 return &n ? remove( q, n ), n : *0p; … … 155 161 } // post: curr == 0p 156 162 157 // create an iterator active in Queue q163 // create an iterator active in queue q 158 164 void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) { 159 165 curr = &head( q ); … … 164 170 } // post: curr = {e in q} 165 171 166 // make existing iterator active in Queue q172 // make existing iterator active in queue q 167 173 void over( QueueIter(T) & qi, Queue(T) & q ) with( qi ) { 168 174 curr = &head( q ); 169 175 } // post: curr = {e in q} 170 176 171 bool ? >>?( QueueIter(T) & qi, T && tp ) with( qi ) {177 bool ?|?( QueueIter(T) & qi, T && tp ) with( qi ) { 172 178 if ( curr ) { 173 179 &tp = Curr( qi ); … … 177 183 return &tp != 0p; 178 184 } 179 // post: elts == null & !operator >>(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator>>(tp)185 // post: elts == null & !operator|(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator|(tp) 180 186 } // distribution 181 187 } // distribution -
libcfa/src/bits/sequence.hfa
r1e6f632f 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 ); -
libcfa/src/bits/stack.hfa
r1e6f632f r9536761 2 2 3 3 #include "bits/collection.hfa" 4 5 // A Stack(T) is a Collection(T) defining the ordering that nodes are returned by drop() in the reverse order from those 6 // added by add(). T must be a public descendant of uColable. 7 8 // The implementation is a typical singly-linked list, except the next field of the last element points to itself 9 // instead of being null. 4 10 5 11 forall( dtype T | { T *& Next ( T * ); } ) { … … 58 64 } // distribution 59 65 66 // A StackIter(T) is a subclass of ColIter(T) that generates the elements of a Stack(T). It returns the elements in the 67 // order returned by drop(). 60 68 61 69 forall( dtype T | { T *& Next ( T * ); } ) { … … 69 77 } // post: curr == 0p 70 78 71 // create an iterator active in Stack s79 // create an iterator active in stack s 72 80 void ?{}( StackIter(T) & si, Stack(T) & s ) with( si ) { 73 81 curr = &head( s ); … … 78 86 } // post: curr = {e in s} 79 87 80 // make existing iterator active in Stack q88 // make existing iterator active in stack s 81 89 void over( StackIter(T) & si, Stack(T) & s ) with( si ) { 82 90 curr = &head( s ); 83 91 } // post: curr = {e in s} 84 92 85 bool ? >>?( StackIter(T) & si, T && tp ) with( si ) {93 bool ?|?( StackIter(T) & si, T && tp ) with( si ) { 86 94 if ( curr ) { 87 95 &tp = Curr( si );
Note: See TracChangeset
for help on using the changeset viewer.