#pragma once

#include "collection.hfa"

forall( dtype T ) {
	struct Queue {
		inline Collection;								// Plan 9 inheritance
		T * last;										// last element, or 0 if queue is empty.
	};

	inline {
		// wrappers to make Collection have T
		T * head( Queue(T) & q ) with( q ) {
			return (T *)head( (Collection &)q );
		} // post: empty() & head() == 0 | !empty() & head() in *q

		bool empty( Queue(T) & q ) with( q ) {			// 0 <=> *q contains no elements
			return empty( (Collection &)q );
		}

		bool listed( T * n ) {
			return Next( (Colable *)n ) != 0;
		}

		T *& Next( T * n ) {
			return (T *)Next( (Colable *)n );
		}

		T * Root( Queue(T) & q ) with( q ) {
			return (T *)root;
		}

		void ?{}( Queue(T) &, const Queue(T) & ) = void; // no copy
		Queue(T) & ?=?( const Queue(T) & ) = void;		// no assignment

		void ?{}( Queue(T) & q ) with( q ) {
			((Collection &)q){};
			last = 0p;
		} // post: empty()

		T * tail( Queue(T) & q ) with( q ) {
			return last;
		}

		T * succ( Queue(T) & q, T * n ) with( q ) {		// pre: *n in *q
#ifdef __CFA_DEBUG__
			if ( ! listed( n ) ) abort( "(Queue &)%p.succ( %p ) : Node is not on a list.", &q, n );
#endif // __CFA_DEBUG__
			return (Next( n ) == n) ? 0p : Next( n );
		} // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q

		void addHead( Queue(T) & q, T * n ) with( q ) {
#ifdef __CFA_DEBUG__
			if ( listed( n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, n );
#endif // __CFA_DEBUG__
			if ( last ) {
				Next( n ) = Root( q );
				q.root = n;
			} else {
				root = last = n;
				Next( n ) = n;							// last node points to itself
			}
		}

		void addTail( Queue(T) & q, T * n ) with( q ) {
#ifdef __CFA_DEBUG__
			if ( listed( n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, n );
#endif // __CFA_DEBUG__
			if ( last ) Next( last ) = n;
			else root = n;
			last = n;
			Next( n ) = n;								// last node points to itself
		}

		void add( Queue(T) & q, T * n ) with( q ) {
			addTail( q, n );
		}

		T * dropHead( Queue(T) & q ) with( q ) {
			T * t = head( q );
			if ( root ) {
				root = Next( root );
				if ( Root( q ) == t ) {
					root = last = 0p;					// only one element
				}
				Next( t ) = 0p;
			}
			return t;
		}

		T * drop( Queue(T) & q ) with( q ) {
			return dropHead( q );
		}

		void remove( Queue(T) & q, T * n ) with( q ) {	// O(n)
#ifdef __CFA_DEBUG__
			if ( ! listed( (Colable &)(*n) ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, n );
#endif // __CFA_DEBUG__
			T * prev = 0;
			T * curr = (T *)root;
			for ( ;; ) {
				if (n == curr) {						// found => remove
					if ((T *)root == n) {
						dropHead( q );
					} else if (last == n) {
						last = prev;
						Next( last ) = last;
					} else {
						Next( prev ) = Next( curr );
					}
					Next( n ) = 0p;
					break;
				}
#ifdef __CFA_DEBUG__
				// not found => error
				if (curr == last) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, n );
#endif // __CFA_DEBUG__
				prev = curr;
				curr = Next( curr );
			}
		} // post: ! listed( n )

		T * dropTail( Queue(T) & q ) with( q ) { // O(n)
			T * n = tail( q );
			return n ? remove( q, n ), n : 0p;
		}

		// Transfer the "from" list to the end of queue sequence; the "from" list is empty after the transfer.
		void transfer( Queue(T) & q, Queue(T) & from ) with( q ) {
			if ( empty( from ) ) return;				// "from" list empty ?
			if ( empty( q ) ) {							// "to" list empty ?
				root = from.root;
			} else {									// "to" list not empty
				Next( last ) = Root( from );
			}
			last = from.last;
			from.root = from.last = 0p;					// mark "from" list empty
		}

		// Transfer the "from" list up to node "n" to the end of queue list; the "from" list becomes the list after node "n".
		// Node "n" must be in the "from" list.
		void split( Queue(T) & q, Queue(T) & from, T * n ) with( q ) {
#ifdef __CFA_DEBUG__
			if ( ! listed( (Colable &)(*n) ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q, n );
#endif // __CFA_DEBUG__
			Queue(T) to;
			to.root = from.root;						// start of "to" list
			to.last = n;								// end of "to" list
			from.root = Next( n );						// start of "from" list
			if ( n == Root( from ) ) {					// last node in list ?
				from.root = from.last = 0p;				// mark "from" list empty
			} else {
				Next( n ) = n;							// fix end of "to" list
			}
			transfer( q, to );
		}
	} // distribution
} // distribution

forall( dtype T ) {
	struct QueueIter {
		inline ColIter;									// Plan 9 inheritance
	};	

	inline {
		// wrappers to make ColIter have T
		T * Curr( QueueIter(T) & qi ) with( qi ) {
			return (T *)curr;
		}

		void ?{}( QueueIter(T) & qi ) with( qi ) {
			((ColIter &)qi){};
		} // post: curr == 0p

		// create an iterator active in Queue q
		void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
			curr = head( q );
		} // post: curr = {e in q}

		void ?{}( QueueIter(T) & qi, T * start ) with( qi ) {
			curr = start;
		} // post: curr = {e in q}

		// make existing iterator active in Queue q
		void over( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
			curr = head( q );
		} // post: curr = {e in q}

		bool ?>>?( QueueIter(T) & qi, T && tp ) with( qi ) {
			if ( curr ) {
				&tp = Curr( qi );
				T * n = Next( Curr( qi ) );
				curr = (n == Curr( qi ) ) ? 0p : n;
			} else &tp = 0p;
			return &tp != 0p;
		}
		// post: elts == null & !operator>>(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator>>(tp)
	} // distribution
} // distribution

// Local Variables: //
// compile-command: "make install" //
// End: //