source: libcfa/src/bits/queue.hfa@ e43aa14

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since e43aa14 was 7d4ce2a, checked in by Peter A. Buhr <pabuhr@…>, 5 years ago

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