Changeset a78c3ff for libcfa/src/bits/queue.hfa
 Timestamp:
 Dec 3, 2020, 3:32:44 PM (11 months ago)
 Branches:
 armeh, jacob/cs343translation, master, newastuniqueexpr
 Children:
 aeb31b1
 Parents:
 636d3715
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

libcfa/src/bits/queue.hfa
r636d3715 ra78c3ff 11 11 inline { 12 12 // wrappers to make Collection have T 13 T *head( Queue(T) & q ) with( q ) {14 return (T *)head( (Collection &)q );13 T & head( Queue(T) & q ) with( q ) { 14 return *(T *)head( (Collection &)q ); 15 15 } // post: empty() & head() == 0  !empty() & head() in *q 16 16 … … 23 23 } // post: empty() 24 24 25 T *tail( Queue(T) & q ) with( q ) {26 return last;25 T & tail( Queue(T) & q ) with( q ) { 26 return *last; 27 27 } 28 28 29 T * succ( Queue(T) & q, T *n ) with( q ) { // pre: *n in *q29 T & succ( Queue(T) & q, T & n ) with( q ) { // pre: *n in *q 30 30 #ifdef __CFA_DEBUG__ 31 if ( ! listed( n ) ) abort( "(Queue &)%p.succ( %p ) : Node is not on a list.", &q,n );31 if ( ! listed( &n ) ) abort( "(Queue &)%p.succ( %p ) : Node is not on a list.", &q, &n ); 32 32 #endif // __CFA_DEBUG__ 33 return (Next( n ) == n) ? 0p : Next(n );33 return (Next( &n ) == &n) ? *0p : *Next( &n ); 34 34 } // post: n == tail() & succ(n) == 0  n != tail() & *succ(n) in *q 35 35 36 void addHead( Queue(T) & q, T *n ) with( q ) {36 void addHead( Queue(T) & q, T & n ) with( q ) { 37 37 #ifdef __CFA_DEBUG__ 38 if ( listed( n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q,n );38 if ( listed( &n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, &n ); 39 39 #endif // __CFA_DEBUG__ 40 40 if ( last ) { 41 Next( n ) =head( q );42 q.root = n;41 Next( &n ) = &head( q ); 42 q.root = &n; 43 43 } else { 44 root = last = n;45 Next( n ) =n; // last node points to itself44 root = last = &n; 45 Next( &n ) = &n; // last node points to itself 46 46 } 47 47 } 48 48 49 void addTail( Queue(T) & q, T *n ) with( q ) {49 void addTail( Queue(T) & q, T & n ) with( q ) { 50 50 #ifdef __CFA_DEBUG__ 51 if ( listed( n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q,n );51 if ( listed( &n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, &n ); 52 52 #endif // __CFA_DEBUG__ 53 if ( last ) Next( last ) = n;54 else root = n;55 last = n;56 Next( n ) =n; // last node points to itself53 if ( last ) Next( last ) = &n; 54 else root = &n; 55 last = &n; 56 Next( &n ) = &n; // last node points to itself 57 57 } 58 58 59 void add( Queue(T) & q, T *n ) with( q ) {59 void add( Queue(T) & q, T & n ) with( q ) { 60 60 addTail( q, n ); 61 61 } 62 62 63 T *dropHead( Queue(T) & q ) with( q ) {64 T * t = head( q );63 T & dropHead( Queue(T) & q ) with( q ) { 64 T * t = &head( q ); 65 65 if ( root ) { 66 66 root = Next( root ); 67 if ( head( q ) == t ) {67 if ( &head( q ) == t ) { 68 68 root = last = 0p; // only one element 69 69 } 70 70 Next( t ) = 0p; 71 71 } 72 return t;72 return *t; 73 73 } 74 74 75 T *drop( Queue(T) & q ) with( q ) {75 T & drop( Queue(T) & q ) with( q ) { 76 76 return dropHead( q ); 77 77 } 78 78 79 void remove( Queue(T) & q, T *n ) with( q ) { // O(n)79 void remove( Queue(T) & q, T & n ) with( q ) { // O(n) 80 80 #ifdef __CFA_DEBUG__ 81 if ( ! listed( (Colable &) (*n) ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q,n );81 if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, &n ); 82 82 #endif // __CFA_DEBUG__ 83 83 T * prev = 0; 84 84 T * curr = (T *)root; 85 85 for ( ;; ) { 86 if ( n == curr) { // found => remove87 if ((T *)root == n) {86 if (&n == curr) { // found => remove 87 if ((T *)root == &n) { 88 88 dropHead( q ); 89 } else if (last == n) {89 } else if (last == &n) { 90 90 last = prev; 91 91 Next( last ) = last; … … 93 93 Next( prev ) = Next( curr ); 94 94 } 95 Next( n ) = 0p;95 Next( &n ) = 0p; 96 96 break; 97 97 } 98 98 #ifdef __CFA_DEBUG__ 99 99 // not found => error 100 if (curr == last) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, n );100 if (curr == last) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, &n ); 101 101 #endif // __CFA_DEBUG__ 102 102 prev = curr; … … 105 105 } // post: ! listed( n ) 106 106 107 T *dropTail( Queue(T) & q ) with( q ) { // O(n)108 T *n = tail( q );109 return n ? remove( q, n ), n :0p;107 T & dropTail( Queue(T) & q ) with( q ) { // O(n) 108 T & n = tail( q ); 109 return &n ? remove( q, n ), n : *0p; 110 110 } 111 111 … … 116 116 root = from.root; 117 117 } else { // "to" list not empty 118 Next( last ) = head( from );118 Next( last ) = &head( from ); 119 119 } 120 120 last = from.last; … … 124 124 // Transfer the "from" list up to node "n" to the end of queue list; the "from" list becomes the list after node "n". 125 125 // Node "n" must be in the "from" list. 126 void split( Queue(T) & q, Queue(T) & from, T *n ) with( q ) {126 void split( Queue(T) & q, Queue(T) & from, T & n ) with( q ) { 127 127 #ifdef __CFA_DEBUG__ 128 if ( ! listed( (Colable &) (*n) ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q,n );128 if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q, &n ); 129 129 #endif // __CFA_DEBUG__ 130 130 Queue(T) to; 131 131 to.root = from.root; // start of "to" list 132 to.last = n; // end of "to" list133 from.root = Next( n ); // start of "from" list134 if ( n ==head( from ) ) { // last node in list ?132 to.last = &n; // end of "to" list 133 from.root = Next( &n ); // start of "from" list 134 if ( &n == &head( from ) ) { // last node in list ? 135 135 from.root = from.last = 0p; // mark "from" list empty 136 136 } else { 137 Next( n ) =n; // fix end of "to" list137 Next( &n ) = &n; // fix end of "to" list 138 138 } 139 139 transfer( q, to ); … … 154 154 // create an iterator active in Queue q 155 155 void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) { 156 curr = head( q );156 curr = &head( q ); 157 157 } // post: curr = {e in q} 158 158 159 void ?{}( QueueIter(T) & qi, T *start ) with( qi ) {160 curr = start;159 void ?{}( QueueIter(T) & qi, T & start ) with( qi ) { 160 curr = &start; 161 161 } // post: curr = {e in q} 162 162 163 163 // make existing iterator active in Queue q 164 164 void over( QueueIter(T) & qi, Queue(T) & q ) with( qi ) { 165 curr = head( q );165 curr = &head( q ); 166 166 } // post: curr = {e in q} 167 167
Note: See TracChangeset
for help on using the changeset viewer.