source: libcfa/src/bits/queue.hfa@ 1e6f632f

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 1e6f632f was a3a76ea, checked in by Peter A. Buhr <pabuhr@…>, 5 years ago

modify routines to return added/removed node to allow cascading calls
  • Property mode set to 100644
File size: 5.2 KB
Line 
1#pragma once
2
3#include "bits/collection.hfa"
4
5forall( dtype T | { T *& Next ( 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 T & 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 return n;
48 }
49
50 T & addTail( Queue(T) & q, T & n ) with( q ) {
51 #ifdef __CFA_DEBUG__
52 if ( listed( &n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, &n );
53 #endif // __CFA_DEBUG__
54 if ( last ) Next( last ) = &n;
55 else root = &n;
56 last = &n;
57 Next( &n ) = &n; // last node points to itself
58 return n;
59 }
60
61 T & add( Queue(T) & q, T & n ) with( q ) {
62 return addTail( q, n );
63 }
64
65 T & dropHead( Queue(T) & q ) with( q ) {
66 T & t = head( q );
67 if ( root ) {
68 root = Next( (T *)root );
69 if ( &head( q ) == &t ) {
70 root = last = 0p; // only one element
71 }
72 Next( &t ) = 0p;
73 }
74 return t;
75 }
76
77 T & drop( Queue(T) & q ) with( q ) {
78 return dropHead( q );
79 }
80
81 T & remove( Queue(T) & q, T & n ) with( q ) { // O(n)
82 #ifdef __CFA_DEBUG__
83 if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, &n );
84 #endif // __CFA_DEBUG__
85 T * prev = 0p;
86 T * curr = (T *)root;
87 for ( ;; ) {
88 if ( &n == curr ) { // found => remove
89 if ( (T *)root == &n ) {
90 dropHead( q );
91 } else if ( last == &n ) {
92 last = prev;
93 Next( last ) = last;
94 } else {
95 Next( prev ) = Next( curr );
96 }
97 Next( &n ) = 0p;
98 break;
99 }
100 // not found => error
101 #ifdef __CFA_DEBUG__
102 if ( curr == last ) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, &n );
103 #endif // __CFA_DEBUG__
104 prev = curr;
105 curr = Next( curr );
106 }
107 return n;
108 } // post: ! listed( n )
109
110 T & dropTail( Queue(T) & q ) with( q ) { // O(n)
111 T & n = tail( q );
112 return &n ? remove( q, n ), n : *0p;
113 }
114
115 // Transfer the "from" list to the end of queue sequence; the "from" list is empty after the transfer.
116 void transfer( Queue(T) & q, Queue(T) & from ) with( q ) {
117 if ( empty( from ) ) return; // "from" list empty ?
118 if ( empty( q ) ) { // "to" list empty ?
119 root = from.root;
120 } else { // "to" list not empty
121 Next( last ) = &head( from );
122 }
123 last = from.last;
124 from.root = from.last = 0p; // mark "from" list empty
125 }
126
127 // Transfer the "from" list up to node "n" to the end of queue list; the "from" list becomes the list after node "n".
128 // Node "n" must be in the "from" list.
129 void split( Queue(T) & q, Queue(T) & from, T & n ) with( q ) {
130 #ifdef __CFA_DEBUG__
131 if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q, &n );
132 #endif // __CFA_DEBUG__
133 Queue(T) to;
134 to.root = from.root; // start of "to" list
135 to.last = &n; // end of "to" list
136 from.root = Next( &n ); // start of "from" list
137 if ( &n == &head( from ) ) { // last node in list ?
138 from.root = from.last = 0p; // mark "from" list empty
139 } else {
140 Next( &n ) = &n; // fix end of "to" list
141 }
142 transfer( q, to );
143 }
144 } // distribution
145} // distribution
146
147forall( dtype T | { T *& Next ( T * ); } ) {
148 struct QueueIter {
149 inline ColIter; // Plan 9 inheritance
150 };
151
152 inline {
153 void ?{}( QueueIter(T) & qi ) with( qi ) {
154 ((ColIter &)qi){};
155 } // post: curr == 0p
156
157 // create an iterator active in Queue q
158 void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
159 curr = &head( q );
160 } // post: curr = {e in q}
161
162 void ?{}( QueueIter(T) & qi, T & start ) with( qi ) {
163 curr = &start;
164 } // post: curr = {e in q}
165
166 // make existing iterator active in Queue q
167 void over( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
168 curr = &head( q );
169 } // post: curr = {e in q}
170
171 bool ?>>?( QueueIter(T) & qi, T && tp ) with( qi ) {
172 if ( curr ) {
173 &tp = Curr( qi );
174 T * n = Next( Curr( qi ) );
175 curr = (n == Curr( qi ) ) ? 0p : n;
176 } else &tp = 0p;
177 return &tp != 0p;
178 }
179 // post: elts == null & !operator>>(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator>>(tp)
180 } // distribution
181} // distribution
Note: See TracBrowser for help on using the repository browser.