Context Navigation

queue.hfa @ ecfe574

ADTast-experimental

Last change on this file since ecfe574 was c407434e, checked in by Thierry Delisle <tdelisle@…>, 4 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
11	forall( 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
153	forall( 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.

Download in other formats:

Original Format