source: libcfa/src/bits/queue.hfa@ 6b33e89

Last change on this file since 6b33e89 was 6b33e89, checked in by Peter A. Buhr <pabuhr@…>, 5 months ago

change backquote call to regular call
  • Property mode set to 100644
File size: 5.5 KB
Line 
1#pragma once
2
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.
10
11forall( T & | { T *& Next ( T * ); } ) {
12 struct Queue {
13 inline Collection; // Plan 9 inheritance
14 T * last; // last element, or 0 if queue is empty.
15 };
16
17 static inline {
18 // wrappers to make Collection have T
19 T & head( Queue(T) & q ) with( q ) {
20 return *(T *)head( (Collection &)q );
21 } // post: empty() & head() == 0 | !empty() & head() in *q
22
23 void ?{}( Queue(T) &, const Queue(T) & ) = void; // no copy
24 Queue(T) & ?=?( const Queue(T) & ) = void; // no assignment
25
26 void ?{}( Queue(T) & q ) {
27 ((Collection &)q){};
28 q.last = 0p;
29 } // post: empty()
30
31 T & tail( Queue(T) & q ) {
32 return *q.last;
33 }
34
35 T * succ( Queue(T) & q, T * n ) { // pre: *n in *q
36 #ifdef __CFA_DEBUG__
37 if ( ! listed( n ) ) abort( "(Queue &)%p.succ( %p ) : Node is not on a list.", &q, n );
38 #else
39 (void) q;
40 #endif // __CFA_DEBUG__
41 return (Next( n ) == n) ? 0p : Next( n );
42 } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q
43
44 T & addHead( Queue(T) & q, T & n ) with( q ) {
45 #ifdef __CFA_DEBUG__
46 if ( listed( &n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, &n );
47 #endif // __CFA_DEBUG__
48 if ( q.last ) {
49 Next( &n ) = &head( q );
50 q.root = &n;
51 } else {
52 root = last = &n;
53 Next( &n ) = &n; // last node points to itself
54 }
55 return n;
56 }
57
58 T & addTail( Queue(T) & q, T & n ) with( q ) {
59 #ifdef __CFA_DEBUG__
60 if ( listed( &n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, &n );
61 #endif // __CFA_DEBUG__
62 if ( q.last ) Next( last ) = &n;
63 else root = &n;
64 last = &n;
65 Next( &n ) = &n; // last node points to itself
66 return n;
67 }
68
69 T & add( Queue(T) & q, T & n ) with( q ) {
70 return addTail( q, n );
71 }
72
73 T & dropHead( Queue(T) & q ) with( q ) {
74 T & t = head( q );
75 if ( root ) {
76 root = Next( (T *)root );
77 if ( &head( q ) == &t ) {
78 root = last = 0p; // only one element
79 }
80 Next( &t ) = 0p;
81 }
82 return t;
83 }
84
85 T & drop( Queue(T) & q ) with( q ) {
86 return dropHead( q );
87 }
88
89 T & remove( Queue(T) & q, T & n ) with( q ) { // O(n)
90 #ifdef __CFA_DEBUG__
91 if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, &n );
92 #endif // __CFA_DEBUG__
93 T * prev = 0p;
94 T * curr = (T *)root;
95 for () {
96 if ( &n == curr ) { // found => remove
97 if ( (T *)root == &n ) {
98 dropHead( q );
99 } else if ( last == &n ) {
100 last = prev;
101 Next( last ) = last;
102 } else {
103 Next( prev ) = Next( curr );
104 }
105 Next( &n ) = 0p;
106 break;
107 }
108 // not found => error
109 #ifdef __CFA_DEBUG__
110 if ( curr == last ) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, &n );
111 #endif // __CFA_DEBUG__
112 prev = curr;
113 curr = Next( curr );
114 }
115 return n;
116 } // post: ! listed( n )
117
118 T & dropTail( Queue(T) & q ) with( q ) { // O(n)
119 T & n = tail( q );
120 return &n ? remove( q, n ), n : *0p;
121 }
122
123 // Transfer the "from" list to the end of queue sequence; the "from" list is empty after the transfer.
124 void transfer( Queue(T) & q, Queue(T) & from ) with( q ) {
125 if ( empty( from ) ) return; // "from" list empty ?
126 if ( empty( q ) ) { // "to" list empty ?
127 root = from.root;
128 } else { // "to" list not empty
129 Next( last ) = &head( from );
130 }
131 last = from.last;
132 from.root = from.last = 0p; // mark "from" list empty
133 }
134
135 // Transfer the "from" list up to node "n" to the end of queue list; the "from" list becomes the list after node "n".
136 // Node "n" must be in the "from" list.
137 void split( Queue(T) & q, Queue(T) & from, T & n ) with( q ) {
138 #ifdef __CFA_DEBUG__
139 if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q, &n );
140 #endif // __CFA_DEBUG__
141 Queue(T) to;
142 to.root = from.root; // start of "to" list
143 to.last = &n; // end of "to" list
144 from.root = Next( &n ); // start of "from" list
145 if ( &n == &head( from ) ) { // last node in list ?
146 from.root = from.last = 0p; // mark "from" list empty
147 } else {
148 Next( &n ) = &n; // fix end of "to" list
149 }
150 transfer( q, to );
151 }
152 } // distribution
153} // distribution
154
155forall( T & | { T *& Next ( T * ); } ) {
156 struct QueueIter {
157 inline ColIter; // Plan 9 inheritance
158 };
159
160 static inline {
161 void ?{}( QueueIter(T) & qi ) with( qi ) {
162 ((ColIter &)qi){};
163 } // post: curr == 0p
164
165 // create an iterator active in queue q
166 void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
167 curr = &head( q );
168 } // post: curr = {e in q}
169
170 void ?{}( QueueIter(T) & qi, T & start ) with( qi ) {
171 curr = &start;
172 } // post: curr = {e in q}
173
174 // make existing iterator active in queue q
175 void over( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
176 curr = &head( q );
177 } // post: curr = {e in q}
178
179 bool ?|?( QueueIter(T) & qi, T && tp ) with( qi ) {
180 if ( curr ) {
181 &tp = Curr( qi );
182 T * n = Next( Curr( qi ) );
183 curr = (n == Curr( qi ) ) ? 0p : n;
184 } else &tp = 0p;
185 return &tp != 0p;
186 }
187 // post: elts == null & !operator|(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator|(tp)
188 } // distribution
189} // distribution
Note: See TracBrowser for help on using the repository browser.