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

ADT ast-experimental
Last change on this file since a0c746df was c407434e, checked in by Thierry Delisle <tdelisle@…>, 5 years ago

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